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.


Contents


    CS 320 LISP Laboratory Number 1: The elements of LISP

    Hints


    Net
    1. To start LISP type the UNIX command lisp.
    2. To leave LISP send EOT by holding down CTRL and tapping D
    3. To load files into LISP before you start, use lisp files...
    4. Parentheses (...) are the must important things in LISP.
    5. For info look in the PL Ref Manual pages on LISP and [ 03.html ] [ 13 ] [ lisp.html ]

    (End of Net)

    Rules of LISP

    LISP follows a strict set of rules, so you supply the intelligence.

    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

    1. S-Expressions are evaluated.

    2. An S-expression can be a constant, a variable or a function call.
    3. Constants include numbers, strings, and constant_lists
    4. Variables and other names are words that are not numbers...

    5. 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


    6. An S_expression describes things that are done to Lists.
    7. The arguments in an S-expression must therefore be evaluated to give Lists
    8. S-expressions return Lists as values as well.

    (End of Net)

    Starting LISP

    Start up a window (see under the DeskTop menu->UnixShell) or input:
     		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.

    Elementary Constants

    You input an S-expression. LISP evaluates it. The values of constants like the following are themselves. Start up LISP and input each of the samples below and see what happens:

    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:

     		T
    LISP (oddly?) interprets a NIL as false!

    Summary


    1. Numbers are constants: 1, 23, 1234, 46,...
    2. Strings are constants: "hello world"
    3. NIL is the constant empty list
    4. T is a constant used to indicate True
    5. There are also constant lists: '(Hello Cruel World)

    Numbers

    Decimal numbers are atoms with a defined meaning - a value
     		1
     		3.14159
     		1234567

    Simple Arithmetic expressions

    The operation comes first, followed by its arguments, and the whole thing is put in parentheses:
     		( + 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)

    Constant Lists

    All input except constants are treated as function calls or variables, except if the "function" is "QUOTE". QUOTE returns a copy of its argument with NO evaluation or changes. Quote stops the avaulation process.
     		(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)

  1. constant_list::= "'"list,
  2. 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:
      (if a b c) ::= (COND (a b) (T c)).
    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