[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] /[CS320 Course Materials] [Text Version] lab/11.html Fri Mar 30 03:24:27 PDT 2012
Labs: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]

Contents


    CS320 Lab/11 LISP Laboratory Number 1

      Check out New things on the Course Web Page

      [ http://cse.csusb.edu/dick/cs320/ ]

      Check out the final questions on LISP

      [ ../11q.html ]

      How much LISP is on web?

      [ search?hl=en&lr=&q=LISP+programming&btnG=Search ]

      Who uses Lambda Expressions?

      [ 3683331 ]

      Goal

      This lab should teach you the rudiments of LISP. You should record your insights and confusions in a new cs320 lab page.

      As you do this laboratory take note of what you are learning about LISP in another file. (You can open a window to edit this file at the same time as you run LISP in another terminal window, and also browse pages in a third window)

      Review, edit, check for speeling mistooks, and publish the result. Check out what it looks like and improve if necessary.

      Let me know by calling me across to your workstation when done.

      To earn full credit the work must be done before the end of the lab and should contain a list of at least 10 notes. Each note is a short paragraph with one or two sentences, some LISP expressions, and their values.

      LISP Versions and Commands

      On the computers in JB359 the command xlisp should run XLISP for you. If it doesn't use this command
       		~dick/bin/lisp
      On other servers use:
       		/share/bin/xlisp
      (or add /share/bin to your PATH variable).

      On the many workstations and servers the guile command will probably start up a version of Scheme. The command

       		(exit)
      will terminate it.

      For beginning LISP, use the longer commands:

       		xlisp
      or
       		~dick/bin/lisp
      or
       		/share/bin/lisp
      to run LISP.

      Hints

      Elementary Constants

        Numbers

        Decimal numbers are atoms with a defined meaning - a value
         		1
         		123445
         		-123
         		3.14159
        Some LISPs don't have floating point numbers. The last expression/value will test the interpreter for you.

        Strings

        Strings are also elementary constants:
         		"This is a string"
         		")This is an ok string!"
         		":-)"
        An error will happen with the following:
         			'This is a string'

        Booleans

        The boolean true = "T" is also predefined in most LISPs:
         		T
        The other boolean value is NIL.
         		NIL
        LISP (like C) interprets a NIL as false.

      . . . . . . . . . ( end of section Elementary Constants) <<Contents | End>>

      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

      The empty list = NIL is a predefined constant:
       		()
       		NIL
      All inputs except constants are treated as function calls or variables. The "function" "QUOTE" turns lists into constants however. It returns a copy of its argument with NO evaluation or changes. Quote stops the evaluation process.
       		(quote example)
      Omit the (QUOTE...) and the data is treated as a function or variable often giving an error:
       		example
       		(example)
      Quoted Lists:
       		(quote (all input is fed into an interpreter))
      Quoted lists can contain sublists:
       		(quote (now is the time (he said) to come to the party))
      Quoted lists inside quoted lists are ok.
       		(quote (quote stops the interepreter evaluating a list))
       		(quote a)
      The blip '... is a short hand form. Use it in place of (Quote ....)
       		'example
       		'(all input is fed into an interpreter)
       		'(quote stops the interepreter evaluating a list)
       		'(now is the time (he said) to come to the party)

      Here are some quick review questions. Why do the expressions below work the way they do?

       		'NIL
       		NIL
       		'1
       		1
       		(+ 1 2)
       		'(+ 1 2)
       		'"(quote a)"
       		"(quote a)"
       		(quote a)
       		'a
       		a
       		(a)
       		'(a b c d)
       		(a b c d)
       		'(a b (c d))
       		(a b '(c d))

      Variables are atoms bound to values

      The value of an atom is found when it is in the right context. A value is bound to a global variable by using (setq variable expression). Local variables are created when functions are called: each formal argument is an atom bound to the value of the actual parameter.

      Try these: some do not always work.... why?

       		a
       		(setq a 1234)
       		a
       		'a
       		(quote a)
       		(* a a)
       		(a + a)
       		(setq date '(9 May 2005))
       		date

      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)
      LISP thinks that a variable is a function, if it is the first item in the list being evaluated:
       		a
       		(a)
       		(date)

      Arithmetic Expressions

      Expressions like this and are evaluated inside out...
       		(+ (* 2 3) (- 3 2) )
       		(+ (/ 1.0 1.0 ) (/ 1.0 2.0) (/ 1.0 3.0) (/ 1.0 4.0) )
      The innermost are evaluated before the outermost ones, like this:
      1. (+ (* 2 3) (- 3 2))
      2. (+ 6 (- 3 2))
      3. (+ 6 1 )
      4. 7

      Watch this happen... first turn on tracing for the functions involved and then type in the expressions:
       		(trace + * - / )
       		(+ (* 2 3) (- 3 2) )
       		(* 2  (+ (* 2 3) 1))
                (+ (/ 1.0 1.0 ) (/ 1.0 2.0) (/ 1.0 3.0) (/ 1.0 4.0) )
      You can turn tracing off like this:
       		(untrace + * )
       		(untrace + * - )
       		(untrace + * - /)

      Try enough different LISP expressions for the notation to become a little more natural... and then 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
      6. (1+2)*(3+4)*(5+6)

      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.
      7. append is a new list, formed by placing the second argument at the end of the first argument.

      Don't forget: Unless a list is quoted then it is evaluated, as a function plus arguments.
    1. ATOM::= Test for an atom,
       		(atom 'a)
       		(atom '(a b c))
       		(atom '())
    2. NULL::= Test for an empty list or NIL,
       		(null '())
       		(null nil)
       		(null 'nil)
       		(null 'a))
       		(null '(a b))
    3. CONS::= Construct a new dotted pair
       		(cons (quote a) (quote b))
       		(cons 'a 'b)
       		(cons 'b 'a)
       		(cons 'a)
       		(cons '(a b ))
    4. CAR::=get the first of a dotted (CONSED) pair.
    5. CDR::=get the second of a dotted (CONSed) pair.

      In C++ we would have

    6. struct pair{ pair * car; pair*cdr; ...}
       		(cons 1 3)
       		(cdr '(1 . 3))
       		(cdr '(1 . 3))
       		(car '(a . b))
       		(cdr '(a . b))
       		(cons (car '(a . b)) (cdr '(a . b)))
       		(car (cons 1 2))
       		(cdr (cons 1 2))

    7. LIST::= constructs lists with any number of 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 19 'feb 1999)
       		(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

      The list function assembles lists for you:

       		(setq date (list  9 'may 2005))
       		(setq class (list 'CS320 "Programming Languages" 11 ) )
       		(list class 'on date )
      You can extract any item in a list:
       		date
       		(car date)
    8. CADR::= the CAR of the CDR:
       		(cadr date)
    9. CADDR::= the CAR of the CDR of the CDR:
       		(caddr date)
      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 following expressions to find out which functions (caddd*r ...) our LISP has, and which it does not have:

       		(setq x '(mary had a little lambda))
       		x
       		(car x)
       		(cdr x)
       		(cadr x)
       		(cddr x)
       		(caddr x)
       		(cdddr x)
       		(cadddr x)
       		(caddddr 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 starting with zero. For example, (nth 0 x) gives the same value as (car x).
       		(nth 0 x)
       		(nth 1 x)
       		(nth 2 x)
       		(nth 4 x)

      Here is a very common error made by beginners:

       		(setq x (mary had a little lamb))
      Rule 1: the first thing after a parenthesis is an operator. And 'mary' is not an operator!

      Structure of a list of elements

      A list of elements (a b c d ...) is stored as a pair like 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 1 nil)
       		(cons 1 (cons 2 nil))
       		(cons 1 (cons 3 (cons 4 nil)))

       		(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 are often written by mistake when (append ...) is needed:

       		(a b x)
      (Wrong!)
       		(quote a b x)
      (Wrong!)
       		(cons a b x)
      (Wrong!)
       		(list a b x)
      (Wrong!)

      But this works

       		(append a b x)
      (Excellent!)

      Constructing Lists with back-quotations

      Here is a wierd but elegant feature of LISP.

      You know that LISP has double quoted strings:

       		"I am a string!"
      You already know that a single quotation mark stops the interpreter from evaluating a list.
       		'(+ 1 2)
       		(setq day 'wednsday)
       		'(Today is day)

      A backquoted list has a backquote (`) in front of it -- this is the "blip" near the top left hand corner of the normal keyboard. It is treated as a constant list that contains expressions. You put a comma(,) in front of the expressions. For example:

       		`(Today is ,day)
      (day is replaced by the value of the variable day)

      Or

       		`((+ 1 2) = ,(+ 1 2))

      Or

       		`( example1 ( (sqrt 4.0) = ,(sqrt 4.0) ) ( day = ,day))

      Review Examples of Constructing lists

      Which is good and which bad and why?
       		(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
       		(setq y `(,x x ,x)) ; use Backquoting.

      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") (T "a>b"))

       		(setq b (- b 2))
       		(COND ((= a b) "a=b") ((< a b) "a<b") (T "a>b"))

       		(setq a (+ 1 a))
       		(COND ((= a b) "a=b") ((< a b) "a<b") (T "a>b"))

      XLISP if_then_else

      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 value of b else return value of a.

       		(if T 'a 'b)
       		(if NIL 'a 'b)
       		(if True 'a 'b)
       		(if (> 2 1) 2 1)
       		(if (> 1 2) 1 2)

      Creating new functions

      Next lab! [ 12.html ]

      How To Leave LISP

      To exit lisp, input the EOT character CTRL/D or input the expression (exit).

    . . . . . . . . . ( end of section CS320 LISP Laboratory Number 1) <<Contents | End>>

    See Also

    The WikiWikiWeb has some pages on LISP in Practice: [ wiki?CommonLisp ] [ wiki?SchemeLanguage ] [ wiki?LispLanguage ]

    Also see the brilliant EverythingIsa page: [ wiki?EverythingIsa ] on the WikiWikiWeb.

. . . . . . . . . ( end of section CS320 Lab/11 LISP Laboratory Number 1) <<Contents | End>>

Check the Preparation for next class

[ ../12.html ]

End