Select this to skip to main content [CSUSB] >> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CSci620] >> 15 [Source]
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Grading]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16]
Tue May 18 16:54:06 PDT 2004

Contents


    CS620 Session 15 LISP 102

      Previous

      [ 14.html ]

      Preparation

      Study Chapter 7 pages 185

      Topics

        LISP in the Lab

        Advanced Features of LISP

        Association Lists

        On page 183 the function has an obvious error in the last line, the arguments A and B are missing. I think there is another, subtle error as well... YES! This [ p183.lsp ] has a corrected version called as. I changed the name because our XLISP has another version of assoc already defined that you will meet in the Laboratory.

        Now I'm suspicious of the assoc on page 182. This is most odd. To get the behavior described in the book you need this [ p182.lsp ] code. To get the behavior in the predefined XLISP assoc then you use the code on page 182. More in the lab! Oddly the LISP2.0 manual(Steele) defines the behavior of assoc in accordance with the book's code, not the author's ideas.

        Property Lists

        The XLISP property list functions are different. In XLISP we have:
        • (get symbol property) ; book's get
        • (putprop symbol value property) ; almost book's put
        • (remprop symbol property) ; remove a property
        • (symbol-plist symbol) ;get the property list of a symbol
        More in the Laboratory.

        The code on page 185 is also way too long... [ p184.lsp ] is shorter. It is also unrealistic: only one parent per child?

      Questions

        What is the reverse function of TRACE?

        UNTRACE is the reverse of TRACE.

        You can (TRACE F1 F2 F3) to start tracing calls of these three functions, and then (UNTRACE F2) to stop the tracing of F2.

        What is setq and set?

        setq is the equivalent of an assignment statement. After (setq V E) the value of E is stored as the value of V.

        set is more powerful. In (set VP E) both VP and E are evaluated. If VP has an atomic value, say V, then that variable, V, is changed to have the value of E.

        What is setf?

        I don't know.

        It means: set field.

        How does a consp differ from an atom?

        consp is a test to see if something is a cons. A cons is a constructed pair. Atoms are not constructed but are a single piece and can not be disassembled with car and cons.

        On page 184 the book says that "null" is returned, but I get "NIL"!

        The "null" is in quotes and is a metaphor meaning "nothing". In LISP this is shown as NIL.

        Why wasn't T removed from LISP?

        Many millions of lines of code use T as true. All this code would need fixing if T was removed. It will be part of LISP for a long time to come.

        How does one differ from (one)

        one is an atom but (one) is a list with a single element. (one) is a dotted pair with car=one and cdr=NIL.

        Does our LISP have put?

        No. It has putprop.

        Why doesn't put work on my CLisp?

        On many LISPs the function is putprop not put. The syntax is different:
      1. (put x y z) == (putprop x z y). So
      2. (defun put(x y z) (putprop x z y)) should fix it. See the Laboratory.

        What must be in X for (CADAR X) to work?

        The function cadar is the head of the tail of the head of its argument! Suppose that (cadar X) returns Y. Then we know that
      3. (cadar X) = (car (cdr (car X))) = Y.

        If (car A) = B then for some C, A = (cons B C).

        So

      4. (cdr(car X)) = (cons Y Z) for some Z.

        If (cdr A) = B then for some C, A = (cons C B)

        So

      5. (car X) = (cons W (cons Y Z)) for some W.

        So

      6. X = (cons (cons W (cons Y Z)) V) for some V.

        So

      7. X = ( (? (Y . ?)) . ?).

        Here is a test using XLISP and presetting variables v,w,y,z to be them selves:

         		> (setq x (cons (cons W (cons Y Z)) V) )
         		> (cadar x)
         		Y

        What does eval do?

        The function eval evaluates an argument twice!

        In an expression (eval x), first x is evaluated by the interpreter. Then the result is re-evaluated again.

        Try this in our XLISP:

         		>(setq e '(+ 1 2)); e is an expression
         		(+ 1 2)
         		> e
         		(+ 1 2)
         		> (eval e); evaluate e
         		3
         		> (eval (list '* 2 3))
         		6
         		> (setq f '(* 2 3))
         		(* 2 3)
         		> (setq g (list '+ e f)); construct a complex list out of e and f
         		(+ (+ 1 2) (* 2 3))
         		> (eval g)
         		9

        Page 182 Why does (assoc m 2) =two?

        It doesn't. It should return (2 two)!

        Why do we ever cons something with an empty list?

        We put a NIL at the end of a list as a sentinel. It is a null pointer! A list like this (A B C D .... Z) has a series of cars A B C.... until you get to the end with a NIL.

        This includes a list with one element like (A)!

      8. (A) = (A . NIL) and is the result of
      9. (cons 'A NIL) (try it in the lab).

        How are (A), (A B), and (A B C) expressed as dotted pairs

         	(A) = (A . NIL)
         	(A B) = (A . (B.NIL))
         	(A B C) = (A . (B. (C . NIL)))

        The list function does a very good job of creating these lists in programs:

      10. list::a function of any number of LISP expressions,
      11. (list a b c .... z)= `evaluate all the arguments and then make a list (cons a (cons b (cons c (cons d (............(cons z NIL)....))))).

        On page 182: what does (setq m '((add +) (minus -))) mean in C++?

        The setq function is the LISP assignment operator so this is rather like the C++ statement
         	m = "((add +) (minus -))";
        but this doesn't express the structure of the right hand side.

        Perhaps something like this:

         	m = cons( cons("add", "+"), cons("minus", "-") );
        except that we don't have a list function in C++. However, using the STL pair class:
         	class List;
         	typedef pair<List*, List*> * List;
         	List * cons( List* x, List* y){ return new pair(x, new pair(y, NULL));}
        is getting close to doing the right thing in C++, but needs garbage collection and some other (nasty) details sorted out.

        However the only real way to map LISP into C++ is write a LISP data type in C++. For example, somewhere in [ http://www.csci.csusb.edu/dick/cs320/lisp/src/ ] are the C functions for interpreting LISP expressions. This is the code for our XLISP.

        If assoc is a mapping why isn't it called map?

        The name goes back to the original LISP1.5 at least. I don't know why McCarthy chose it. I do know that map is a different function in LISP that we don;t have time to cover.

        If assoc doesn't find a key what does it return?

        NIL.

        Book's arguments for assoc are in a different order to XLISP and the handout?

        The handout was taken directly from the source code and documentation for XLISP. The books version is different:
      12. (bookAssoc list atom) = (assoc atom list).

        I think that XLISP follows the standard LISP and the book does not.

        Is it OK to omit a ' in front of a number (page 183)?

        Yes. All the numbers are recognized and return as a value a binary number representing them.
      13. '123 = 123

        Why program in LISP?


        1. LISP is required in many Computer Science departments.
        2. It is small, clean, and logical.
        3. Instant universal data structure.
        4. 90% of all Artificial Intelligence research is done in LISP.
        5. Many tools and techniques developed in Artificial Intelligence research use LISP.
        6. It turns up, surprisingly, in many applications: Rational Rose, Emacs, AutoCAD, Cyc, ...
        7. When you get into the syntax and semantics, it is fun.
        8. No bugs in the LISP system.
        9. It is easy to add a LISP interpreter to any program you write. You want to be able to define functions and arithmetic and data handling and not fight with parsing infix expressions etc.... Use LISP.
        10. Some things are very simple in LISP that are rather messy in other languages.
        11. Real computer scientists know LISP as well as well as two other languages. What do you say in a job interview when they ask you what (car (cdr (cons 'A (cons 'B 'C)))) is?

        Is AI dead?

        No. Not until the last AI researcher fails to recruit students to continue the tradition or the funding disappears. As long as we have problems that are solvable, but no practical solution, the AI community will be tackling them..... probably using tools based on LISP.

      . . . . . . . . . ( end of section Questions) <<Contents | Index>>

      Laboratory

      Some simple LISP functions [ lab15.html ]

      Next

      Semantics of LISP Chapter 7 185 onward [ 16.html ] (outline).

    . . . . . . . . . ( end of section CS620 Session 15 LISP 102) <<Contents | Index>>

    Glossary

  1. BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
  2. EBNF::="Extended " BNF.
  3. HTML::= "HyperText Markup Language", used on the WWW.
  4. HTML_page::syntax= "<HTML>" head body.
  5. Java::="An " OO " Language from Sun".
  6. LISP::= "LISt Processing Language".
  7. LRM::="Language Reference Manual".
  8. OO::="Object-Oriented".
  9. Prolog::="Programming in Logic".
  10. TBA::="To Be Announced".
  11. UML::="Unified Modeling Language".
  12. URL::=Universal_Resource_Locator,
  13. Universal_Resource_Locator::syntax= protocol ":" location, where
    Net
    1. protocol::= "http" | "ftp" | "mailto" | ... ,
    2. location::= O( "//" host) O(pathname).

    (End of Net)
  14. WWW::= See http://www.csci.csusb.edu/dick/cs620/, index to web site for this class.
  15. XBNF::="eXtreme" BNF, developed by the teacher from EBNF, designed to ASCII input of syntax, semantics, and other formal specifications.


Formulae and Definitions in Alphabetical Order