This page generated on Tue Jan 8 12:21:36 PST 2002.

- CS 320 LISP Laboratory Number 1: The elements of LISP
- : Hints
- : Rules of LISP
- : Starting LISP
- : Elementary Constants
- : Numbers
- : Simple Arithmetic expressions
- : Constant Lists
- : Variables are atoms
- : Functions
- : More complex arithmetic expressions
- : Creating new functions
- : Function definitions
- : A Function with two arguments
- : Exercise
- : Lists
- : The Empty List
- : Functions of lists
- : Constructing Pairs
- : Disassembling constructed Pairs
- : Some Axioms of LISP
- : Lists of 1 or more elements
- : Variables and Lists
- : Constructing and disassembling lists
- : A Newbie Error
- : Structure of a list of elements
- : How to construct new lists from old ones
- : Be careful constructing lists:
- : Conditional expressions
- : Defining new functions in XLISP and SCHEME
- : Classic factorial
- : To Leave LISP
- Index of defined terms etc.

- To start LISP type the UNIX command
*lisp*. - To leave LISP send EOT by holding down CTRL and tapping D
- To load files into LISP before you start, use
*lisp files...* - Parentheses (...) are the must important things in LISP.
- For info look in the PL Ref Manual pages on LISP and [ 03.html ] [ 13 ] [ lisp.html ]
- S-Expressions are evaluated.
- An S-expression can be a constant, a variable or a function call.
- Constants include numbers, strings, and constant_lists
- Variables and other names are words that are not numbers...
- Function calls are more complex S-Expressions:
- Function calls start with an open parenthesis and end with a matching close parentheses.
- Inside the parentheses there is a function name and then its data.
- If it looks like this (xxxx yyyy zzzz) then it is a call:
- The function name is xxxx.
- The first argument/parameter is yyyy
- The next is zzzz

- An S_expression describes things that are done to Lists.
- The arguments in an S-expression must therefore be evaluated to give Lists
- S-expressions return Lists as values as well.
- Numbers are constants: 1, 23, 1234, 46,...
- Strings are constants: "hello world"
- NIL is the constant empty list
- T is a constant used to indicate True
- There are also constant lists: '(Hello Cruel World)
- constant_list::= "'"list,
- list::=NIL | atom | string | pair | longer_list.
- Empty: NIL
- An atom
- A string
- A number
- A pair: left parenthesis, list, dot, list, right parenthesis.
- A longer list: left paren, zero or more lists, right paren.

Review....'NIL

NIL

'1

1

'"(quote a)"

"(quote a)"

(quote a)

'a

a

(a)

'(a b c d)

(a b c d)

## Variables are atoms

The value of an atom is found by treating it as a variable. A value is bound to a global variable by using (setq variable expression).a

(setq a 1234)

a

'a

(quote a)

## Functions

LISP thinks the first word in a list to be evaluated is a function. The rest of the list are the arguments (if any). Arguments are evaluated by the same rule as the whole expression.(+ 1 2)

(* 3 2)

(- 3 2)

(/ 24 2)

(+ 1 2 3 4 5 6 7)

(* 1 2 3 4 5 6 7)

LISP thinks that even a variable is a function, if it is the first item in the list being evaluated:a

(a)

On some systems*date*is a built-in LISP function and in others it is not implemented, but in either case in the following expression the syntax requires*date*to be a function:(date)

## More complex arithmetic expressions

These are evaluated inside out...(+ (* 2 3) (- 3 2) )

The innermost are evaluated before the outermost(+ (* 2 3) 1)

(+ 6 1)

(* 2 (+ (* 2 3) 1))

To watch this happen... turn on tracing for the functions involved:(trace + * - )

(+ (* 2 3) (- 3 2) )

(* 2 (+ (* 2 3) 1))

Try enough different LISP expressions for the notation to become a little more natural... Try to express the following in LISP- 12*12 - 4 * 2 *3
- 12*(12 - 4)*2 *3
- 12+12-4*2*3
- 1+2+3+4+5+6+7
- 2*3*4*5*6*7

## Creating new functions

In Common LISP the DEFUN function DEFines Functions: DEFine FUNction A with no arguments and value 4321( defun a () 4321)

(a)

a

'a

(quote a)

## Function definitions

Here is how we would define the LISP version of the C/C++ function definition:List_type square(List_type x){ return x*x; }

(DEFUN square (x) (* x x))

Here is how you test it...

(square 3)

(square 4)

(square 5)

Here is how you can use it:

(square (+ 1 2 3))

(+ (square 3) (square 4) )

## A Function with two arguments

Here is a function with two arguments in C/C++:List_type pythagoras(List_type x, List_type y){ return square(x)+square(y); }

and in LISP:(DEFUN pythagoras (x y) (+ (square x) (square y)))

(pythagoras 3 4)

Notice that*(DEFUN pythagoras (x,y) (+ (square x) (square y)))*is not correct. (WHY???)## Exercise

Code the following C/C++ in LISP:List_type pyth2(List_type x, List_type y){return x*x + y*y ;}

Test the result...## Lists

Unless a list is quoted then it is evaluated, as a function plus arguments.'(a)

'(a b)

('a 'b)

(a 'b)

('a b)

## The Empty List

The empty list () is symbolyzed by the atom NIL and its predefined value is NIL as well.()

nil

## Functions of lists

Lists are handled by functions that have one or more lists as arguments and produce a single list as a result. Here is a list of the basic functions in Common LISP:- atom is T if parameter's value is an atom else returns NIL
- null is T if parameter's value is a NIL else returns NIL
- cons constructs a new list. It is pair of the value of the first parameter, and the value of the next parameter.
- car is the head of the list that is the value of the parameter
- cdr is the tail of the list that is the value of the parameter
- list is a new list, of any length constructed of the values of the parameters in the order that they occur.

(atom 'a)

(atom '(a b c))

(atom '())

(null '())

(null nil)

(null 'nil)

(null '(a b))

## Constructing Pairs

(cons (quote a) (quote b))

(cons 'a 'b)

(cons 'b 'a)

(cons 'a)

(cons '(a b ))

## Disassembling constructed Pairs

The function*car*extracts the head or first item of a pair. The function*cdr*is the tail of the pair.(cons 1 2)

(cdr '(1 . 2))

(cdr '(1 . 3))

(car '(a . b))

(cdr '(a . b))

(cons (car '(a . b)) (cdr '(a . b)))

## Some Axioms of LISP

- For all x and y, if z=(cons x y) then (car z ) = x and (cdr z) =y.
- For all x, y, and z, if (car z ) = x and (cdr z) =y then z=(cons x y).
- For all x and y, (atom (cons x y)) = NIL.
- For all x and y, (null (cons x y)) = NIL.

(car (cons 1 2))

(cdr (cons 1 2))

(cons (car '(a . b)) (cdr '(a . b)))

## Lists of 1 or more elements

(list 1)

(list 1 2)

(list 1 2 3)

(1 2 3)

(list 1 2 3 4 5 6 7 8 9 )

(list 'a 'b 'c)

(list 13 'jan 1997)

(list 'CS320 "Programming Languages" 4 )

(list CS320 "Programming Languages" 4 )

## Variables and Lists

(setq x '(a . b))

x

'x

(atom x)

(car x)

(cdr x)

car (x)

'(car x)

(cons (car x) (cdr x))

(setq x (+ 1 2))

x

'x

## Constructing and disassembling lists

(setq date (list 13 'jan 1997))

(setq class (list 'CS320 "Programming Languages" 4 ) )

(list class date )

(setq x '(mary had a little lamb))

x

'x

The function*car*extracts the head or first item of a pair. The function*cdr*is the tail of the pair, so cadr is the head of the tail - the second item. cddr is the cdr of the cdr and so the tail of the tail. So caddr is the 3rd item in a list. Try the foloowing to find out which functions our LISP has, and which it does not have:(car x)

(cdr x)

(cadr x)

(cddr x)

(caddr x)

(cdddr x)

(cadddr x)

(caddddr x)

(setq x '(mary had a little

lambda))

x

(car x)

(cdr x)

(cadr x)

(cddr x)

(caddr x)

(cdddr x)

(cadddr x)

(caddddr x)

(cadddddr x)

(cddddddr x)

(caddddddr x)

(cdddddddr x)

Most modern versions of LISP have a function*nth*that extracts one item from a list:*(nth 12 x)*is the 12th item in*x*.(nth 4 x)

## A Newbie Error

Try this:(setq x (mary had a little lamb))

Rule 1: the first thing after a parenthesis is an operator.## Structure of a list of elements

A list of elements (a b c d ...) is stored as a pair likne this (a . (b c d ...) ). In other words (car l) is always the first element in the list and (cdr x) is always the rest of the list.(cons 'a nil)

(cons 'a 'b)

(cons 'a (cons 'b nil))

(cons 'a (cons 'b (cons 'c nil)))

(cons 'a (cons 'b (cons 'c (cons d

nil ))))

(cons (cons (cons 'a 'b) 'c) 'd)

(cons nil nil)

## How to construct new lists from old ones

Use (append ...). Here I set up three variables with names x,a, and b:(setq x '(surprised))

(setq a '(mary had a little

lambda))

(setq b '(the doctor was) )

Now I combine them into a single list:(append a b x)

## Be careful constructing lists:

The following a commonly written when (append ...) is needed:(a b x)

(Wrong!)(quote a b x)

(Wrong!)(cons a b x)

(Wrong!)(list a b x)

(Wrong!)(append a b x)

(Excellent!)More examples... which is good and which bad?

(setq y (x x)) ; see Rule 1 above

(setq y '(x x)) ; Rule 2: A quoted list can't have any variables

(setq y (CONS x x)) ; Cons only constructs pairs, not lists.

(setq y (LIST x x)) ; Use list to make lists of lists

(setq y (LIST x x x))

(setq y (APPEND x x x)) ; use APPEND to concatenate lists

## Conditional expressions

(COND ....) is the earliest structured conditional statement:- (COND (C1 E1) (C2 E2) (C3 E3) ...) means
- Try each Cn until one has a non-NIL value and return
- the value of the matching En.

(COND (T 'a) (NIL 'b))

(COND (NIL 'a) (T 'b))

(COND (NIL 'a) (T 'b) (NIL 'c))

(COND (NIL 'a) (NIL 'b) (T 'c))

A three way comparison:

(setq a 1) (setq b 3)

(COND ((= a b) "a=b") ((< a b) "a<b") ((> a b) "a>b"))

XLISP has an if. It is shorthand for a COND:-
(if a b c) ::= (COND (a b) (T c)).
- If a is true then return a else return c.

(if T 'a 'b)

(if NIL 'a 'b)

(if True 'a 'b)

(if (> 2 1) 2 1)

(if (> 1 2) 1 2)

## Defining new functions in XLISP and SCHEME

DEFUN defines functions in XLISP.(defun max2 (a b) (if (> a b) a b))

(max2 1 17)

(max2 17 1)

(max2 (max2 3 5) (max2 4 1))

In Scheme (and in Sebesta's book) we use (define (name arguments) expression). I have programmed a simulation of Scheme inside XLISP:(define (square1 x) (* x x))

square1

(square1 4)

(define (summer L) (if (null L) 0 (+ (car L) (summer (cdr L)))))

summer

(summer '(1 2 3))

(define (square L) (if (null L) NIL (cons (square1 (car L)) (square (cdr L)))))

(square '(1 2 3))

(summer (square '(1 2 3)))

## Classic factorial

We now define a new function, command and kind of expression that calculates the factorial of a positive integer. The factorial of the number 0 is 1, and for all other positive integers n you work out n times the factorial of n-1. In LISP we say:(define (factorial n)

(if (= n 0) 1 (* n ( factorial ( - n 1 ) ))

)

)

Here you print out the definition of factorial:

factorial

Here you input expressions that apply factorial to simple numbers:(factorial 0)

(factorial 3)

(factorial 5)

Below you use

*factorial*is more complicated ways:(setq n 3)

(factorial n)

(setq f (factorial n))

f

(setq f (factorial f))

f

(factorial (factorial 3))

## To Leave LISP

To exit lisp, input the EOT character CTRL/D*. . . . . . . . . ( end of section CS 320 LISP Laboratory Number 1: The elements of LISP)*<<Contents | Index>>

Net

(End of Net)

LISP interprets your input as a stream of special expressions. These are called
"syntax expressions" or *S-expression*s for short.

Each "command" you input is therefore an S-expression.

Net

(End of Net)

xterm &into the Console window. In the new window input the command .A_is lisp You can now high light text in this page/window and pste it (middle button) into the other window.

Take note of what happens to each example and how you would explain it.

Numbers

1

123445

-123

Strings

"This is a string"

")This is an ok string!"

":-)"

The empty list = NIL is a predefined value:

()

NIL

The boolean *true* = "T" is also p[redefined in LISP:

TLISP (oddly?) interprets a NIL as false!

Summary

1

3.14159

1234567

( + 2 3 )

( * 2 3 )Operators are atoms + - * / rem and other symbols.

(+ 1 2)

(+ 1 2 3 4 5 6 7 8 9)Try a few of your own!

Now try some mistakes so you can see what various messages mean:

1*2

( 2 + 3 )

(*2 3)

(quote example)

Omit the (QUOTE...) and the data is treated as a function or variable.

example

(example)

Quoted Lists:

(quote (all input is fed into an interpreter))

Quoted lists inside quoted lists.

(quote (quote stops the interepreter evaluating a list))

(quote a)

The blip ' gives a short hand form

'example

'(all input is fed into an interpreter)

'(quote stops the interepreter evaluating a list)

- (Function definition)
- constant_list (Definition)
- list (Definition)