CM10135 / Programming II:   Tutorial 1

This is an optional first tutorial, designed to give you a feel for programming in a very different language than Java or C.  The intention of this tutorial is to help develop your understanding of what are general considerations of programming, and what are language-specific issues.  In this tutorial you will learn how to run queries and define functions in an interpreted language which is not strictly typed.  You will also get to manipulate a simple data structure, the list.

This tutorial is optional.  You will not be required to know its contents for any of the course work or for the exam.  If you choose, you may spend some or all of the tutorial talking to your tutor about any outstanding questions you have about Java from last term.  Also, this is only the beginning of an introduction to Lisp.  You will get to really understand the language in your second year.

Getting Started

This tutorial must be run from one of the BUCS unix computers.  The language you are using is called Lisp, but from BUCS it is called "euscheme".   (Scheme is actually a dialect of Lisp, but the differences aren't important for us.) Here are some Notes on using Euscheme written by Dr. Bradford, but you probably won't need them for this tutorial.

If you know emacs, you may find it easier to run this program from inside a shell window (Meta-X shell) so that you can have access to editing commands.  If you don't know lisp, just try to type things correctly from the command line.

If you get interested in Lisp and have your own computer, you may want to download a free Lisp IDE LispWorks from  This runs on MS Windows, Mac OS X or Linux.  Notice though that it's a real lisp so will work a little different than the below instructions.

Getting to know the interpreter

If a language is interpreted, then you can run any command in it from a command prompt.  This allows you not only to run functions, but also to look at and change values in its memory.  Lisp has an object system, but unlike Java doesn't force you to use it.  Since this is just a quick tutorial, we won't bother with the object system here.

This is your first interaction with the interpreter.  You have asked it the value of a basic type, and it has told you the answer.

Words are names for memory locations, and odds are you have chosen a word that hasn't already been defined, so you are now in the debugger.  Have a look at the options you have by typing help:, but probably what you want to type now is top: to get back to the prompt.

Now try typing the same word with a single quote in front of it, for example (assuming > is the prompt)
    > 'myword
A quote refers to the token (here 'myword).  You can think of the token as the name for a piece of memory, not the memory itself.

Here is how you set a value in Lisp:

    > (setq myword 5)

Getting to know Lisp syntax

Lisp statements are surrounded by parentheses.  They are in prefix notation, which means that the first word is always a verb of some type, and the rest of the words are arguments.  #'setq, which you used above, takes even numbers of arguments.  The first, third, fifth... arguments are names of locations, the second, fourth, sixth... arguments are values.

There are still types in lisp, & the operators know what types things are.  So (/ 3 5) is different from (/ 3.0 5.0).
That variable has now taken on the type of its contents.  Lisp evaluates all of the arguments of a statement before it trys to execute a statement.

The basic conditional "if" in lisp looks like this (if [test] [then] [else]), where square brackets mean you can put an expression there (the `else' is optional.)  For example, try typing:
Lisp programmers often use a more general form of conditional called cond, which lets you have lots of conditionals before the else case, and also lets you have as many statements as you want within each case.  Cond takes a list of lists as arguments, the first element of each list is the conditional, and they will each be tested in order.)
    ((= 5 (+ 2 2)) (print "I can do math."))
    ((= 6 (+ 3 3)) (print "I can do math second shot.") (print "I don't feel so bad."))
    (#t (print "looks like I can't do math at all."))

Defining a function in Lisp

Here's a very simple function definition in lisp:

(defun add-5 (xxx)  
    (+ 5 xxx))

A defun statement takes a name, a list of variable names, and then any number of statements which are the code that gets run for that function.  It returns the value of the last statement that executes. 
You can see that since you aren't using a compiler or a type system, you can get yourself in trouble!

Lists in Lisp

Lists are the most basic data structure in lisp.  Even statements are really lists.  Lists are also in parentheses.  To refer to them, you also have to put a single quote in front of them, e.g '(1 2 3), otherwise the interpreter will try to evaluate them, like it does a statement.  Lists are such an important concept in lisp, the empty list has a special name, nil.  In lisp, the value of "nil" and '() are exactly the same, which you can test like this:
(eq nil '())
Nil is also the opposite of #t, that is, it is also the boolean value "false".  That's how important lists are to lisp!

Unfortunately, euscheme is a rather archaic version of lisp, so you can't use the contemporary commands "first" and "rest" to take apart a list as you were taught in lecture.  Instead of "first" you have to use "car", and instead of "rest" you have to use "cdr".  It's probably good to learn the old historic names for these functions in case you ever run into them, but it will make the below code look less comprehensible.  Recall also that you build a list by using "cons".  Try running the following code:

(setq shortlist (cons  1 nil))
(setq medlist (cons  1 (cons 2 nil)))
(setq longlist '(1 2 3 4))
(car medlist)
(cdr longlist)
(cdr shortlist)
(cdr medlist)

To test for whether a list is empty, use the predicate "null" like this:

(null nil)
(null (cdr shortlist))
(null (cdr longlist))

Processing lists in Lisp

One of the basic design patterns often used in Lisp is to process a list using recursion.  In this section I will show you an instance of that pattern, and then ask you to write a couple functions.  When you are through with those functions, you are through with this tutorial!

Here's a function that just prints a list out item by item.  I've put an error check in it just to show you that such a thing is possible...

(defun silly-print-list (mylist)
     ((not (listp mylist))
         (cerror "Argument to silly-print-list was not a list!" <bad-type>))
     ((null mylist)
        (print "all done!"))
        (print (car mylist))
        (silly-print-list (cdr mylist))
        ); end of #t option
    )) ; end of cond and defun

(silly-print-list '(my dog has fleas))

Now, here are some functions to try to write:

page author: Joanna Bryson
last updated: 16 Feb 2005