Common Lisp/First steps/Beginner tutorial

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Start up your Lisp implementation. You will most likely see a window with a prompt waiting for your input. This prompt is called a REPL for Read-Evaluate-Print Loop. At this point, Lisp is waiting for the expression to read and then evaluate, which in simple words means to calculate its result.

Type "2" and press Return (or Enter)

2
2

The lisp interpreter looks at 2 and evaluates it. It recognizes it as a number, and applies the rule that numbers evaluate to themselves, so the answer is 2.

Addition[edit | edit source]

Type "(+ 2 2)" and press Return

(+ 2 2)
4

The computer sees the opening parenthesis and realizes it is being given a list. When it reaches the closing parenthesis it is able to work out that it has seen a list of three elements. The first is the + sign, so it knows to add together the values of the remaining items on the list. So it evaluates them, the number 2 having the value 2 as before. Answer: 4

Things to do wrong[edit | edit source]

  • Forget to type return. You always have to type return at the end to tell the computer that you have finished your turn and it's its turn to go.
  • Leave out the first space:
(+2 2)
Illegal function call
  • Think it's a typo and try:
+(2 2)
Illegal function call
  • Think it's a typo and do the infix thing
(2+2)
Warning: This function is undefined
  • Put in spaces
(2 + 2)
Illegal function call

Clarification exercises[edit | edit source]

(+ 1 2 3 4)
10
(+ 1 1 1 1 1 1 1)
7
(+ 1 20 300 4000 50000)
54321

Explanation[edit | edit source]

Instead of writing 1+20+300+4000+50000, one writes the plus sign as the first item of a list that can be as long as you wish.

The list appears to be laid out like one might lay out a shopping list: (potatoes carrots onions bread milk) with no concession to the idea that + is part of arithmetic and a bit special. Be careful though. The first location on the list is special, and + has to come first.

Multiplication[edit | edit source]

For multiplication we use the ‘*’ function.

(* 5 7)
35

Can you use a list as long as you want? Yes.

(* 2 2 2)
8
(* 5 7 11)
385
(* 1 1 5 1 1 1 7 1 1 1 11)
385
(* 1 1 5 1 1 1 7 0 1 1 11)
0

In fact, you can use lists as short as you want.

(+ 23)
23
(* 137)
137
(+)
0
(*)
1

Why? There are depths here that must be deferred until later.

Subtraction[edit | edit source]

Subtraction is as clunky in Lisp as in any other language.

(-)
error
(- 96)
-96
(- 96 23)
73
(- 96 20 1 1 1)
73

In other words,

(- a b c d e)

is the same as

(- a (+ b c d e))

Division[edit | edit source]

Division contains a surprise.

Lisp does fractions

 (+ 1/2 1/2)
1

 (+ 1/2 1/3)
5/6

 (+ 1/10 1/15)
1/6

 (- 1/2 1/3)
1/6

 (* 1/10 1/15)
1/150

 (/ 1/10 1/15)
3/2

This is potentially confusing:

If you try (/ 2 3) you get 2/3 which is probably an unpleasant surprise, if you were expecting 0.6666667. If you had tried (/ 8 12) you would also have got 2/3, which might have been a pleasant surprise. If you don't want a fraction, you can always say

 (float 8/12)
0.6666667

or

 (float (/ 8 12))
0.6666667

Division works the same way as subtraction with

 (/ a b c d e)

being the same as

 (/ a (* b c d e))

This works OK in practice. A calculation such as 6×5×4/(3×2×1) gets translated to the following piece of Lisp:

 (/ (* 6 5 4) 3 2 1)

Binding[edit | edit source]

Binding is the act of specifying a place holder for a value. The concept is analogous to that of a local variable in C or Java. You often want to do this because it is cumbersome to write out long expressions multiple times, or if a computation needs to be done in small parts where a binding needs to be updated at various times during execution. The main way to create bindings is via the “special form” LET.

(let ((5-squared (* 5 5))
      (10-squared (* 10 10)) )
  (* 5-squared 10-squared) )

Here, 5-SQUARED and 10-SQUARED are place holders ("local variables") for the results of the calculation (* 5 5) and (* 10 10), respectively. It is good to note at this time that there are very few rules regarding what can be used as a place holder. These place holders are called symbols and it can have a name that includes most any characters with the exception of quotes, open or close parenthesis, colons, backslashes, or vertical bars (‘|’). These all have special syntactical meaning in Common Lisp. It is good to note that all of these things actually can be in the name of a symbol but they require special escaping.

Bindings have a limited scope. Once the LET form closes, the binding is invalidated. This means that this is an error, because a is referred to outside of the enclosing LET form.

(let ((a (sqrt 100))))
(print a)

It is interesting to note the behavior if you bind a symbol that has already been bound. Once the inner binding is released, the outer one is in effect again.

(let ((a 1))
  (print a)
  (let ((a 2))
    (print a) )
  (print a) )

==> 1
    2
    1

The story gets a bit more complex, there are two types of way to make bindings in Common Lisp, lexical, which we have just seen, and dynamic. For our purposes at this point, dynamic bindings are not much different from lexical bindings, but they are made in a different way and do not have the same finite extent of the LET form. We can use DEFVAR and DEFPARAMETER to make dynamic bindings. These can hold a value in between inputs.

(defvar a 5)

(print a)

(let ((a 10))
  (print a) )

(print a)

==> a
    5
    10
    5

Variables[edit | edit source]

In Lisp, variables have some extra features, and are called symbols. A variable is a box containing a value. A symbol is a somewhat larger box, with its name written on the side. A symbol has two values, a general purpose value, and a function value used instead in particular circumstances. You can use the symbol as a thing in itself, without regard to its value.

setf[edit | edit source]

We start by setting a symbol's general purpose value. There are several commands for setting the values of symbols, set, setq, setf, psetq, psetf. One can get a long way with just setf so we start with that one

(setf my-first-symbol 57)
57

This sets the general purpose value of the symbol MY-FIRST-SYMBOL to 57, and returns 57. Now we can type

my-first-symbol
57

and

(+ my-first-symbol 3)
60
(setf second-symbol (+ 20 3))
23

Well, plainly this has performed the calculation, and returned the answer, but what did the general purpose value of our second-symbol get set to? Have we used it to record the calculation we requested, (+ 20 3), or the answer that the computer calculated?

second-symbol
23

If we want to record the calculation for future reference we must "quote" it. Think of the computer as a horse and the quote as a bridle, reining it in, stopping it from rushing on to evaluate things before you want it to.

(setf third (quote (+ 20 3)))
(+ 20 3)

Now

third
(+ 20 3)

the general purpose value of our third symbol contains a calculation, which the computer is champing at the bit to execute.

eval[edit | edit source]

If quote pulls on the reins, how do we get started again? The answer: eval.

(eval third)
23

It is controversial to use quote in the first lesson because it is seldom typed in explicitly. One types

(setf third '(+ 20 3))
(+ 20 3)

Notice that this is a very special abbreviation. Not only are the five letters of quote shortened to the single character ', but the brackets are also omitted. It should be noted that when we use a lisp interpreter, we are essentially in an infinite READ-EVAL-PRINT loop. Thus, we are really using eval all the time.

list[edit | edit source]

We have set three symbols so far and are perhaps in danger of forgetting what they contain. The function list builds a list, e.g.

(list 1 2 3)
(1 2 3)

so lets build a list of the values of our three symbols

(list my-first-symbol second-symbol third)
(57 23 (+ 20 3))

There are two potential confusions here. One of them is figuring out which value is which. Perhaps we should turn off evaluation using quote:

(list 'my-first-symbol my-first-symbol 'second-symbol 
second-symbol 'third third)
(MY-FIRST-SYMBOL 57 SECOND-SYMBOL 23 THIRD (+ 20 3))

The second and more serious confusion arise from comparing

(list 1 2 3)
(1 2 3)

and

(list my-first-symbol second-symbol third)
(57 23 (+ 20 3))

It looks as though list is somehow deciding whether or not to evaluate its arguments, refraining in the first instance and rushing ahead in the second.

With quote and eval we can investigate this. Let us evaluate 1 zero times, once, twice, and three times

'1
1
1
1
(eval 1)
1
(eval (eval 1))
1

Compare this to evaluation third, zero, one, two, and three times.

'third
THIRD
third
(+ 20 3)
(eval third)
23
(eval (eval third))
23

Numbers are not symbols. There is no box containing two values. They just are, and they evaluate to themselves. Since numbers are not symbols,

(setf 1 '1)
error

does not work. You can get a feel for what is going on by typing

(setf my-symbol-1 'my-symbol-1)
MY-SYMBOL-1

Now my-symbol-1 evaluates to itself. It shrugs off evaluation just as numbers do.

'my-symbol-1
MY-SYMBOL-1
my-symbol-1
MY-SYMBOL-1
(eval my-symbol-1)
MY-SYMBOL-1
(eval (eval my-symbol-1))
MY-SYMBOL-1

I'm going to belabor this point. I have a reason. The metaphor of a variable as a box that contains things is a good one. Much of the time the metaphor works well. You keep something in the box for a while. Then you throw the contents away and use the box to keep something else instead. Unfortunately the metaphor is fundamentally flawed. Both the box and its contents are immaterial. Consider

(setf 4th third)

Has the list describing a simple calculation been put in the box 4th?

4th
(+ 20 3)

Yes.

Has it been taken out of third?

third
(+ 20 3)

No.

Has it been copied? No. You make a copy like this:

(setf 5th (copy-list 4th))

Has it been moved? No. To the extent that the metaphor of motion works at all, you move things like this

(setf 6th 5th 5th nil)

There is a command (shiftf 6th 5th nil) which writes nil to 5th after moving the contents to 6th, but it returns the old contents of 6th, so it cannot be used on shiny new variables with no contents.

If it has not been copied and it has not been moved, what has happened? Something special to the immaterial world of tangled boxes, which we will not explore today.

For a striking example do

(setf red 'green)
(setf green 'blue)
(setf blue 'red)

now

'red
RED
red
GREEN
(eval red)
BLUE
(eval (eval red))
RED

Now for the key test. What happens with (+ 1 (* 2 3)) and (+ 1 '(* 2 3))? The second of these is easy to understand. We have used quote to prevent evaluation, so (* 2 3) is a list of three items, giving instructions for an arithmetical calculation to be carried out at some later time. It is not the result of the calculation it describes and is not a number. Sure enough:

(+ 1 '(* 2 3))
Argument Y is not a NUMBER: (* 2 3).

By contrast

(+ 1 (* 2 3))
7

appears cleverer than it really is. It looks like the interpreter looks at its arguments and decides which ones to evaluate. For example it looks as though

(+ 1 (* 2 3) (* 10 10) 30)
137

is realizing that it needs to evaluate argument 2 and 3 while leaving 1 and 4 alone.

In fact

(* 2 3)
6

only looks like it is doing what you think. It is evaluating 2 and 3, getting 2 and 3 as the results of the two evaluations, then multiplying the two results to get six.

When the interpreter evaluates (+ 1 (* 2 3)) it evaluates 1 and (* 2 3). 1 evaluates to 1, (* 2 3) evaluates to 6. Then it adds them to get 7.

There is something worth pondering here. Get a cheap, old, pocket calculator out of a drawer and try 1 + 2 x 3 Typically, when you press x, the calculator, lacking an extra register to hold pending results, carries out the addition of the one and the two. One ends up calculating 3 x 3 and getting 9, rather than 7. Modern calculators follow the standard rules of precedence, and defer performing the addition until after they have multiplied 2 by 3, eventually arriving at 7, as desired.

Computer languages have many more operations than addition and multiplication and often have elaborate systems of precedence controlling which operations are carried out first. Lisp has no such subtlety. One either writes

(1+2)x3 as

(* (+ 1 2) 3)

or one writes

1+(2x3) as

(+ 1 (* 2 3))

there is no way to preserve the ambiguity of 1+2x3

This turns out to be for the best in practice.

Obscure note: You could try (+ 1 * 2 3). At the top level, * is used for recalling the result of the previous command. If that was a number it will give the wrong answer. If that was not a number the interpreter will signal an error. Within a program, (+ 1 * 2 3) will generate an error message saying that * has no value. More on this later.

Let us return to third. Remember that we set our third symbol to a list of three items. We can see the whole list by typing third

third
(+ 20 3)

Lisp has functions for extracting items from a list. First gets the first item

(first third)
+

The function second gets the second item on the list.

(second third)
20

If we would prefer multiplication we can change the symbol at the start of the list

(setf (first third) '*)
*
third
(* 20 3)
(eval third)
60

We can change the second item

(setf (second third) 7)
7
third
(* 7 3)
(eval third)
21

and, mysteriously, we can do the same with the third item

(third third)
3
(setf (third third) 4)
third
(* 7 4)
(eval third)
28

How does this work? Remember what I said earlier "A symbol has two values, a general purpose value, and a function value used instead in particular circumstances."

The particular circumstances are when eval is evaluating the first symbol in a list. The function that eval applies, to the result of evaluating the other items in the list, is the function value of the symbol, not the general purpose value of the symbol.

symbol-function, symbol-value[edit | edit source]

To make this clear, use symbol-function and symbol-value

(symbol-function 'third)
#<Function THIRD {103C7F19}>
(symbol-value 'third)
(* 7 4)
(symbol-function 'my-first-symbol)
Error in KERNEL:%COERCE-TO-FUNCTION:  the function MY-FIRST-SYMBOL is undefined.
(symbol-value 'my-first-symbol)
57
(symbol-function '+)
#<Function + {10295819}>
(symbol-value '+)
(SYMBOL-FUNCTION '+)

This is very confusing. The interpreter stores the last command executed as the general purpose value of the symbol +, so (symbol-value '+) depends on what you did last. In side a program (symbol-val '+) will do something like

(symbol-value '=)
Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER:  the variable = is unbound.

just the same as

(symbol-value 'my-misspelled-simbol)
Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER:  the variable MY-MISSPELLED-SIMBOL is unbound.

boundp[edit | edit source]

All these error messages are quite annoying. Is there any way to avoid them? Yes. boundp checks whether there is a general purpose value, and fboundp checks whether there is a function value,

(fboundp '+)
T

T is used for true

(fboundp 'my-first-symbol)
NIL

NIL is used for false, rather than F

(boundp 'my-first-symbol)
T
(boundp 'my-misspelled-simbol)
NIL

Introductions to Lisp usually keep quiet about symbol-function. I understand why. Now that I have told you about it, you are equipped to wreck havoc, and undertake all sorts of devious mischief.

For example

(symbol-function '*)
#<Function * {1005F739}>

and

(symbol-function  '+)
#<Function + {10295819}>

give access to the functions that add and multiply.

Lets save them for later

(setf mult (symbol-function '*) add (symbol-function  '+))

Notice that you can set as many symbols as you want with a single setf.

Notice also that I have put these functions in the general purpose values of the symbols

(fboundp 'mult)
NIL
(boundp 'mult)
T
(symbol-value 'mult)
#<Function * {1005F739}>

Notice that

mult
#<Function * {1005F739}>

works as well. I'm using symbol-value to make the parallel to symbol-function more apparent.

You can store functions in general purpose value of a symbol. It really is the general purpose the value of the symbol, not the data value of the symbol.

(mult 4 5)
Warning: This function is undefined:
MULT
Error in KERNEL:%COERCE-TO-FUNCTION:  the function MULT is undefined.

doesn't work. When eval tries to evaluate a list that starts with a symbol, it looks for the function value of the symbol, and signals an error if it cannot find one.

(funcall mult 4 5)
20

works. So does

(apply mult '(4 5))
20

and

(apply mult (list 4 5)).
20

and

(apply add '(1 2 3 4))
10

It is worth remembering that apply subsumes funcall, i.e. all of these work

(apply add '(1 2 3 4))
(apply add 1 '(2 3 4))
(apply add 1 2 '(3 4))
(apply add 1 2 3 '(4))
(apply add 1 2 3 4 '())

Back to mischief

(setf (symbol-function '+) mult)
(setf (symbol-function '*) add)

He he, you've got it, I'm swapping round + and *

(+ 5 7)
35
(* 25 75)
100

I'd better put them back

(setf (symbol-function '+) add (symbol-function '*) mult)
(+ 5 7)
12
(* 25 75)
1875

phew, that's better.

symbol-function is heavily used. So not only is there an easier way of writing it, (function +) instead of (symbol-function (quote +)), but the simplified way even has its own abbreviation #'+. Err, that's not quite right, but it will have to do for now.