Previous

[ 15.html ]

Preparation

Study Chapter 7 pages 185-194 (advanced LISP)

Topics

LISP in the Lab

Interpreting Expressions

The book doesn't use a useful abbreviation for constructing n-tuples -- lists with 1 ,2, 3, ... items

Shorthand	Full form
(list x)	(cons x NIL)
(list x y)	(cons x (cons y NIL))
(list x y z)	(cons x (cons y (cons z NIL)))
(list w x y z)	(cons w (cons x (cons y (cons z NIL))))

Here [ p185.lsp ] is the code for the 'ev' function using the list operator. It also includes tidied up stack operations and a quick test. Enjoy!

Note. This interpreter is written in normal prefix notation LISP. It interprets postfix expressions like (1 2 +) or (1 2 + 3 *). Like most post-fix interpreters it puts the data onto a stack until the operator comes along. Then the right number of data items are taken off the stack and the operator is applied to them. The result is pushed back onto the stack.

Meta-Interpreter

If you don't like global variables (I don't) you can use P-lists (get/putprop/...) or embed all the functions that share a collection variables inside a LET. Here [ stack1.lsp ] is an example where stack is a local variable shared by some functions.

Questions

Does any one still use LISP?

Yes. It is still the basis for a lot of rule based and expert systems. The Cyc project uses it. And Dr. Gomez uses Linux Scheme on his Linux workstation as a calculator and spread sheet.

What is a higher-order function?

A higher-order function uses another function as data and may return a function as a result. In the differential calculus, differentiation is a higher-order function, as an example.

In LISP we have several standard higher order functions:

(apply f args)	apply a f to args
(funcall f [args]...)	call function with args
(mapc f e) (mapcar f e) (mapl f e) (maplist f e)	apply f to all (cars, cdrs, elements) in list.

As an example if we (defun sq(X) (* x x)) to square numbers then:

 		(mapcar (function sq) '(1 2 3 4 5))

outputs

 		(1 4 9 16 25)

The (function f) form is a special form of quotation that allows the function f to be distinguished from a variable named f.

On page 188 and 189 how does instance work and what does it mean?

The function instance instantiates an expression by replacing variables by values. To get the trace on page 189 you would input:

 		(instance '(+ (+ (+ a b) a) 3) '((a 2) (b 3)))

1. instantiation::=to create a particular version of an expression by replacing variables by values.

   The best way to understand the code is to either try it by hand or to do the Laboratory below.

   What is crtenv and its relation to env on page 191?

   The variable/parameter env is what we call an environment: a set of pairs where each pair has a variable and a value. It is an A-list/Association-List:

    		((a 3) (b 4))

   means that variable a = 3 and variable b = 4 in this environment.

   The function crtenv creates an environment in which a function is executed in the meta-interpreter. A typical test might be

    		(crtenv '(a b)   '(4 3)   NIL)

   The first argument (a b) is a list of variables/parameters. The second argument (4 3) is a list of values, assumed to be the same length as the first argument. The last argument NIL is the previous environment to which (a 4) and (b 3) is to be added. The trace is on page 191.

   On page 187 what is a "meta-program".

   A meta-program reads another program and treats it as data. All compilers and interpreters are meta-programs. We use the term in particular when we have a program in language L that manipulates (as data) programs written in L.

   The idea goes back to Alan Turing, Alonzo Church, and other working on Computability Theory. There are several ways of defining computing: Turing Machines, Recursive Functions, Markov Algorithms, etc. They all have a single Universal that takes a description of a Turing Machine, Recursive Function, Markov Algorithm, etc. and interprets it. These are examples of meta-programs.

   LISP was introduced to the world with a meta-interpreter defining the syntax. It was called evalquote. If you had a list expression E then (evalquote 'E) would evaluate it for you.

   I learned LISP in the 1960's, without a computer, by executing evalquote on a simple expression.

   Do variables in LISP have a scope?

   Yes. Variables created by typing (setq V A) into the interpreter create a variable V with global scope. This means V can be used in any later expression or function definition.

   Each argument in a function definition is a variable with local scope. It can not be accessed from out side the function. Local variables hide global ones in the usual way.

   The PROGN, LET, and LET* functions all create a new scope with variables that belong to it.

   What is the difference between consp and atom?

   They are both predicates. They take an argument and either return t (true) or NIL (false). (atom X) is true if and only if X is an atom. (consp X) is true if and only if X is a constructed pair.

   How do you trace the project function?

   How do do Exercise 6?

   Carefully and slowly on a blackboard, or slowly and carefully on paper with a pencil.

   While you do this let a part of your mind hover and notice patterns. Don;t let the patterns drive the simulation. Just observe any patterns and later prove that what you noticed was true.

   Explain the crtenv function on page 191.

   The expression (crtenv variables values environment) returns a new environment which contains the new variables and their values stored in it.

    		(crtenv '(a b) '(4 3) NIL)

   matches a to 4 and b to 3 giving (a 4) and (b 3). It then adds these pairs to the NIL list giving

    		((a 4)  (b 3))

   as a result. The Laboratory is designed to help you understand this function.

   What does the succ function on page 192 do?

   Good question! I'm not sure, but here it is in C/C++/Java:

    		long succ(int i){ return (a>5? a: succ(a+2));}

   or

    		long succ(int i){ if(a>5)return a; else return succ(a+2));}

   If you work out some example values:

   i	(succ i)
   7	7
   6	6
   5	(succ 7)	7
   4	(succ 6)	6
   3	(succ 5)	7

   you will see a pattern emerge. Then see if you can express it in a simple closed form.

   Can you do exercise 6?

   Given (defun s(x y) (cond ((null y) x) (t (s (+ (car x)) (cdr Y))))) what is (s '0 '(10 20 30 40 50 60))?

   Answer 210.

   We didn't have time to do the full trace. But here is a simpler case:

    		(s '0 '(10 20))

   calls

    		(s '10 '(20))

   calls

    		(s '30 '())

   returns

    		30

   Has the author tested the code of the metaintepreter?

   There is a bug in it.... thanks to work done in the Laboratory!

   What is the LISP machine on page 193?

   Symbolics made/makes a super-computer that executes LISP as its machine code.

   Was LISP the first programming language to demonstrate meta-programming?

   I think so. Before LISP we had the theory and FORTRAN and COBOL. Writing a COBOL interpreter in COBOL is almost easy(!). But nobody would want to. FORTRAN 1 in FORTRAN is almost impossible. Most earlier languages were not very high level. So, yes, LISP is probably the first high level language to be defined by a meta-interpreter and to consciously encourage higher-level functions and meta-programming.

   Is John McCarthy usually credited with creating LISP?

   Yes.

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

Laboratory

More LISP functions [ lab16.html ]

Next

Chapter 8 pages 211-222 Hello Prolog. Outline: [ 17.html ]

. . . . . . . . . ( end of section CS620 Session 16 LISP 103) <<Contents | Index>>

Glossary