Please use the alphabetical Index, Contents List, and your browsers search feature to find what you need.

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

This page is part of the CS320: Programming Languages Course on the Computer Science Department's WWW Server at CalState, San Bernardino, California, USA. It was generated by Doc Dick Botting.

CS 320 LISP Laboratory Number 1: The elements of LISP

Hints

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 ]

Rules of LISP

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

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

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:
1. Function calls start with an open parenthesis and end with a matching close parentheses.
2. Inside the parentheses there is a function name and then its data.
3. If it looks like this (xxxx yyyy zzzz) then it is a call:
  1. The function name is xxxx.
  2. The first argument/parameter is yyyy
  3. 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.

Starting LISP

 		xterm &

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

Elementary Constants

Numbers

 		-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:

Summary

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)

Numbers

 		3.14159

Simple Arithmetic expressions

 		( + 2 3 )

 		( * 2 3 )

 		(+ 1 2)

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

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

1*2

 		( 2 + 3 )

 		(*2 3)

Constant Lists

 		(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)

constant_list::= "'"list,
list::=NIL | atom | string | pair | longer_list.
1. Empty: NIL
2. An atom
3. A string
4. A number
5. A pair: left parenthesis, list, dot, list, right parenthesis.
6. 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
1. 12*12 - 4 * 2 *3
2. 12*(12 - 4)*2 *3
3. 12+12-4*2*3
4. 1+2+3+4+5+6+7
5. 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:
1. atom is T if parameter's value is an atom else returns NIL
2. null is T if parameter's value is a NIL else returns NIL
3. cons constructs a new list. It is pair of the value of the first parameter, and the value of the next parameter.
4. car is the head of the list that is the value of the parameter
5. cdr is the tail of the list that is the value of the parameter
6. 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
1. For all x and y, if z=(cons x y) then (car z ) = x and (cdr z) =y.
2. For all x, y, and z, if (car z ) = x and (cdr z) =y then z=(cons x y).
3. For all x and y, (atom (cons x y)) = NIL.
4. 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.
'mary' is not 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:
1. (COND (C1 E1) (C2 E2) (C3 E3) ...) means
2. Try each Cn until one has a non-NIL value and return
3. 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:
1. 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>>

Formulae and Definitions in Alphabetical Order

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

This page is part of the CS320: Programming Languages Course on the Computer Science Department's WWW Server at CalState, San Bernardino, California, USA. It was generated by Doc Dick Botting.

Contents

CS 320 LISP Laboratory Number 1: The elements of LISP

Hints

Rules of LISP

Starting LISP

Variables are atoms

Function definitions

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

How to construct new lists from old ones

Be careful constructing lists:

Conditional expressions

Defining new functions in XLISP and SCHEME

To Leave LISP

Formulae and Definitions in Alphabetical Order