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:

    LISP	Scheme
    CAR	head
    CDR	tail
    ATOM	atom?
    NULL	null?
    EQ	eq?
    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