Select this to skip to main content [CSUSB] >> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CSci620] >> 14 [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 14:13:59 PDT 2004

Contents


    CS620 Session 14 LISP101

      Previous

      [ 13.html ]

      Preparation

      Study pages 169..178 and the LISP handout. Prepare questions on both LISP and the reading in the text.

      Topics

        Why LISP

        S-Expressions

        Composing Functions

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

      Questions

        What is John McCarthy doing now?

        He is a professor emeritus at Stanford. Here [ http://www-formal.Stanford.EDU/jmc/ ] is his home page.

        Is LISP case sensitive?

        No.... except inside strings.

        Do NULL and NIL mean the same thing?

        No.

        NIL is a constant (think of it as the zero of list structures).

        NULL is a Boolean function or predicate that test to see if it's argument is NIL.

        Try these

         	(NULL NIL)
         	(NIL NULL)

        What is a macro name?

        Any atom that is bound to a macro is a macro name.

        A Macros For?

        First they are convenient. Second, we need at least one (QUOTE) to stop call by value evaluating expressions. Third, they are a way to extend the language: I don't like writing macros but the only way to add a Scheme like define command was to use a macro (and hack the compiler).

        However you will not need to write any for CSci620.

        If you are really curious see [ scheme.lsp ] and notice the weird way the ",(.....)" is an inverse quote operator! You don't have to figure it all out!

        Does the Quadratic Equation functions in the handout work?

        I thought they did. This is copied and pasted from the copy on my laptop hard disk [ quad.lsp ] that I downloaded and tested.

        Explain the definition of NTH in the handout

        Hmmmm there may be an error! It looks like I fixed this in my laptop but did not get the latest version duplicated. The rule is
      1. For n>0 and any x,
      2. (NTH n x) = (NTH (- n 1) (CDR X)) This means that the nth item of a list x is the (n-`1)th item in the tail of x.

        NTH is a function that picks out an item in a list as if it was an array:

      3. (nth 0 '(a b c)) has value a.
      4. (nth 1 '(a b c)) has value b.
      5. (nth 2 '(a b c)) has value c.

        Page 170 why is (4, 5, 6) in the list and nonatomic.

        The list is
      6. (1, 2, 3, (4, 5, 6)) and this has elements
      7. 1
      8. 2
      9. 3
      10. (4, 5, 6) SO (4,5,6) is the fourth item in the list.

        But (4,5,6) starts with a "(" and can not be an atomic value. Atomic values are numbers and words.

        Does the blip "'" do anything?

        It is a special abbreviation:
      11. '(x y z ...) is (QUOTE (x y z ....)). It is very important for indicating the data passed to a function from the user. If it is missing you are likely to get Error: bad function x.

        At the bottom of page 171, is there a blip missing?

        No. You can leave off a blip on a single number because the value of a number is itself:
      12. '1 has value 1 and
      13. 1 has value 1.

        At the bottom of page 171, are the answers correct?

        Yes.

        Explain cadr, caddr, etc.

      14. car = the first item in a list
      15. cdr = list of all the rest.
      16. cadr = car o cdr -- the car of the cdr -- the second item.
      17. caddr = car o cdr o cdr -- the car of the cdr of the cdr -- the third item.

        Functions like cadar are also OK and in this case extracts the first item of the tail of the first item of a list.

        It is worth drawing the tree structures and tracing the a/d paths. I will be giving you a function that takes it's data apart like this:

         		> (show '( ( a b ) 2 ( x y )))
         		cr = ((A B) 2 (X Y))
         		car = (A B)
         		caar = A
         		cdar = (B)
         		cadar = B
         		cddar = NIL
         		cdr = (2 (X Y))
         		cadr = 2
         		cddr = ((X Y))
         		caddr = (X Y)
         		caaddr = X
         		cdaddr = (Y)
         		cadaddr = Y
         		cddaddr = NIL
         		cdddr = NIL
         		"Ok"

        Why is (car(cdr(car '((1 2 3 4 ) 5 6 7))) equal to 2?

      18. The car of ((1 2 3 4 ) 5 6 7) is (1 2 3 4).
      19. The cdr of (1 2 3 4) is (2 3 4)
      20. The cdr of (1 2 3 4) is (2 3 4)
      21. The car of (2 3 4) is 2

        Can LISP be Infix or Postfix

        LISP is a consistently Prefix notation:
      22. ( operator operand ...)

        You can try to write a translator from infix or postfix to prefix if you wish. We will see an interpretter for postfix expressions in the near future.

        Why do we use T in place of ELSE

        First: LISP was invented in the 1950's and the idea or "ELSE" was invented in the 1960's (Algol 60). Second, people had got into the habit of using T. Third, T is used in too much code for the language to lose it. Fourth, Scheme uses ELSE! Finally, you save 3 characters by using T in place of ELSE.

        If you want to fix it try

      23. (setq else t)

        What is the difference between FUNCALL and APPLY

        Both functions take another function and call it with some arguments. The syntax is different:
      24. (FUNCALL function arg1 arg2 arg3 ....)
      25. (APPLY function list_of_arguments )

        So for example

         		> (cons 1 2)
         		(1 . 2)
         		> (apply 'cons '(1 2))
         		(1 . 2)
         		> (funcall 'cons 1 2)
         		(1 . 2)
         		> (funcall cons 1 2)
         		error: unbound variable - CONS

        We use one or the other when we have an expression that returns a function. For example: (lambda(x) (* x x)).

        Also see [ fun.lsp ] (stupid funcalls "make it so"), [ apply.lsp ] (experiments with apply), [ sortfun.lsp ] (using apply for a version of quicksort).

        Are there any object oriented aspects to LISP

        Scheme provides a neat way to create an object that is surrounded by functions that manipulated. There may be more to it than I've heard.

        Common Lisp had objects added to it in the 1980's creating

      26. CLOS::=Common LISP Object System.

        CLOS is a very dynamic object oriented language: full inheritance and polymorphism, PLUS the ability for classes to gain methods as a program runs, and for objects to change classes(I think). I have an examples in [ Objects%20in%20XLISP in index ] using XLISP.

        What was the machine with a CAR and CDR?

        I think it was an early IBM Mainframe: IBM 701 or 704. This was when machines (in the states) didn't have names but numbers.

        When we end a COND with T is this like a default in a switch?

        Yes.

        What is the difference between Common LISP and Scheme?

        Very different philosophies. Common LISP has everything that was in any popular version of LISP. Scheme has the absolute minimum.

        Scheme also introduce static scoping.

        Finally, Scheme changed some function names:
        LISPScheme
        CARhead
        CDRtail
        ATOMatom?
        NULLnull?
        EQeq?
        And so on

        What data types are there in LISP?

        These have increased over time.
        1. atoms and lists
        2. + integers
        3. + floating point numbers
        4. + strings
        5. + arrays/vectors
        6. and so on

        What is an impure operator?

        Pure LISP has functions, conditions, recursion, and lists.

        Adding variables and assignments and we move away from functional programming.

        Why is functional programming good?

        See Strachey's classic paper in the 1966 Scientific American.
        • Christopher Strachey
        • Systems analysis and programming
        • Scientific American (Sep 1966)
        • (republished in reprints on "The World of Mathematics")

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

      History of Functional Programming

      Strachey's work had lead to a very powerful language called CPL. There are very few interpreters or compilers for it.

      However, it inspired Basic BCPL and Functional Decomposition methods for data processing systems!

      In turn BCPL was used (with Algol 68), at the AT&T Bell Labs (now Lucent) as a basis for the language B, which was superceded by C as the UNIX system programming language. You will notice that C makes a lot of use of functions, even tho' it also includes imperative features like assignments.

      Laboratory

      Exercises based on expressions and function in reading: [ lab14.html ]

      Next

      Study Chapter 7 pages 178-185 (more LISP) [ 15.html ] Outline:

    . . . . . . . . . ( end of section CS620 Session 14 LISP101) <<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