CSC302 2011S, Class 33: The Design of LISP

Overview:
* Summary of the Paper.
* S-Expressions, S-Functions, and M-Expressions.
* Eval.
* Other Topics.

Admin:
Missing: AC, CF3, DG
* Reading for Monday: Graham, Paul. (2002). The Roots of Lisp.
* I may be changing the topic for next Wednesday's class to macros.
* No more homework this semester!  (Yes, I know I promised you "implement LISP", I think I'd rather not add to your workload.)
* Reminder: Presentations start a week from today.
* Congratulations to the two new CS Phi Beta Kappans: 
  Jordan Shkolnick and Charles Fratz.
* Due to prereg and College committee work, I need folks to sign up for appointments.  Times at http://www.cs.grinnell.edu/~rebelsky/Schedule/signup.2011S.txt.  Signup via email.
* EC for today's CS Table.
* Quiz

QUIZ
(define l-s
  (lambda (fun left)
    (lambda (right)
      (fun left right))))

What is

(l-s l-s l-s)

Gives you a function that fills the left side of left section.

How do you figure it out?

(l-s l-s l-s) =>

    (lambda (right1)
      (l-s l-s right1))

    (lambda (right1)
     (lambda (right2)
      (l-s right1 right2)))

    (lambda (proc)
     (lambda (right2)
      (l-s proc right2)))

    (lambda (proc)
     (lambda (right2)
      (lambda (right3)
       (proc right2 right3))))

    (lambda (proc)
     (lambda (left)
      (lambda (right)
       (proc left right))))

Another strategy: Mess around with it


   

`
;;; Procedure:
;;;   binary-curry
;;; Parameters:
;;;   bf, a binary function
;;; Purpose:
;;;   Curries bf
;;; Produces:
;;;   caf, a unary function
;;; Preconditions:
;;; Postconditions:
;;;   caf's one parameter must have the same type as the first parameter
;;;     of bf
;;;   


(define fubar (l-s l-s l-s)

 
SUMMARY OF THE PAPER

* Who is the paper's audience?
  * Academics and industry
  * More geared toward academics: Theory of computation
    * But also toward programming language crowd: Conditional, Implementation
* What is the author's claim/thesis?
  * Maybe there wasn't one: Was it just laying out definitions?
  * I have defined a new model of computation that is Turing complete,
    nicer than other things known to be Turing complete, and usable
    on a real computer.
  * I invented the conditional [proof by assertion]
* What is the argument?
  * "Here's a formalism"
  * Apply has the role of a universal turning machine
    * Assumption: Anything that can define a system of recursive functions
      is equally powerful to a Turing machine.
    * Apply's definition shows that the languge is turing complete.
  * Big example: The AI Thingamajigger.
  * Smaller example: Lots of simple program
  * Discuss details + "Believe me"
* Do we accept the argument?
  * Yes.  Well, not necessarily.

THREE ISSUES: S-EXPRESSIONS, S-FUNCTIONS, and M-EXPRESSIONS

* M-expressions: Intended as the expressions available in the language.
  FUN[PARAM;PARAM]
* S-expressions: Internal representation of M-expressiosn
  (fun, param, param)
  Which is really
  (fun . (param . (param . NIL)))
* S-functions: Functions on S-expressions, typically defined in the
  M language.
* The S-notation ended up being the only part really used.
  * Easy to parse!

EVAL

(define (apply f args) 
  (eval (cons f (appq args)) nil))

(define (appq m)
  (cond
    ((null? m) nil)
    (true (cons (list (quote (car m)))
                (appq (cdr m)))))

(define (eval e a)
  (cond
    ((atom? e) 
     (assoc e a))
    ((atom? (car e))
     (cond
      ((eq? (car e) quote) 
       (cadr e))
      ((eq? (car e) atom) 
       (atom (eval (cadr e) a)))
      ((eq? (car e) eq) 
       (eq? (eval (cadr e) a) (eval (caddr e) a)))

OTHER TOPICS

* How would you change this to be lazy?
* What's the difference between dynamic and lexical scope?
* Where is this difference encoded in apply?