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 http://www.lispworks.com/.
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.
- To begin with, type an integer (for example, 5) and see what
happens.
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.
- Now try typing a character or word. (A character will be
interpreted as a short word.)
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)
- Try setting your word to an integer value.
- Now what happens when you type it without a quote?
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.
- Try adding 2 and 2. The symbol for addition in Lisp is +,
just
like in Java.
- Does / work like it does in Java?
- What
happens when you use / for integers? for reals? for
strings?
There are still types in lisp, & the operators know what types
things are. So (/ 3 5) is different from (/ 3.0 5.0).
- Try adding 2, 3 and 5 in a single statement.
- Try
adding something to the word you've set to a value using setq
earlier.
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.)
(cond
((= 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."))
)
- Try playing with the integer values in these examples so that you
can
see how to reach each of the cases. Notice what the return value
is for the cond,
especially for the case that two statements got
executed.
Defining a function in Lisp
Here's a very simple function definition in lisp:
(defun add-5 (xxx)
(+ 5 xxx))
- What does the interpreter return to you when you have typed this
code
in?
- What happens now if you type in the word add-5 to the
interpreter?
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.
- Try typing (add-5 12). What happens?
- How
about (add-5 'myword)?
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)
(cond
((not
(listp mylist))
(cerror "Argument to silly-print-list was not
a list!" <bad-type>))
((null
mylist)
(print "all done!"))
(#t
(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:
- Write a simple function called "add-two" that takes two
arguments, both numbers and sums them.
- Write a function called "sum list" which uses add-two and
recursion to sum all the numbers in a list. (Obviously you could
just do this with +, but the point is to practice recursion!)
- Write a function called "reverse" that builds up a list (remember
"cons"!) that is the reverse of its input list. So (reverse '(a b
c)) returns '(c b a).
- Extra bonus question --- can you write a function "deep-reverse"
which reverses lists inside
of lists? E.g. '(1 2 3 (4 5) (6 7 8))
page author: Joanna Bryson
last updated: 16 Feb 2005