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