CSC302 2007S, Class 15: The Design of LISP
Admin:
* Since Sam missed Wednesday, he can't complain about people
who are late or absent today.
* How did yesterday's presentation go?
* Don't forget Kumail's Comedy, tomorrow at 7 p.m.
* I believe I distributed Monday's reading (The Roots of Lisp)
last week.
* Wednesday's readings distributed today.
Overview:
* Summary of the Paper.
* S-Expressions, S-Functions, and M-Expressions.
* Eval.
* Other Topics.
/What is "Recursive Functions ..." about?/
* A new formalism for describing computation
* Using the M&S notations
* Including some basic procedures: atom, eq, car, cdr, cons, lambda and label...
* The building blocks of the formalis
* As compared to things like ff, assoc
* "Look, the formalism can be implemented as a language you might use"
* And here are the basic ideas of the implementation
/To understand the paper, You must understand the notation/
* Predicate logic
* The new "conditional expression"
( p1 -> e1 , ... , pn -> en )
[ p1 -> e1 ; p2 -> e2 ; ... ; pn -> en ]
* "mathematics is invariant of notation"
* Meaning:
Evaluate p1
If it holds, return the value of e1
If not, keep going through the p's until you find one that
holds (say pi) and return the value of the corresponding
expression (say ei)
* This expression is not alway defined
* No p's can hold
* The e for the first holding p can be undefined
* If any p "that gets examined" is undefined
* S-expression - Start as data
* A symbol is an s expression
* If S1 and S2 are s expressions, so is the dotted pair of S1 and
S2
(S1 . S2)
* Simplified notation
* Instead of (S1 . (S2 . NIL)) => (S1, S2)
* Later versions eliminated the comma
* S-functions - Procedures whose domain and range are the S-expressions
* The basic functions: atom, car, cdr, cons, ...
* Newly defined ones: ff, pair, append, assoc, ...
* M-expressions - The notation for describing S-functions
* Doesn't use parens, uses square brackets
* Places the operation outside of the brackets, rather than inside
* And uses some infix operations
* EVERY M-EXPRESSION CAN BE REPRESENTED BY AN S-EXPRESSION
* Our world need only incorporate S-expressions
* Many of you had trouble with M notation
sqrt(a, x, e) =
(|x^2 - a| < e -> x, T -> sqrt(a, 1/2(x+a/x), e))
/The Second Big Result: Eval/
* You can write an s-expression that will compute the value of
any other s-expression
* It's pretty damn short
* Let's try