SICP OpenCourse (Structure and Interpretation of Computer Programs)

PART 1

1.POINT: Universal machine, Eval&Apply, Y Combinator

2.CODE IS A CHARACTER STRING DESCRIPTION OF A WIRING DIAGRAM

    - Problem is picture is too big

3.EVAL IS A "UNIVERSAL MACHINE"

    - Eval takes as input a description of another machine. It could take the wiring diagram of a factorial machine as input.

    - Eval is a machine

    - Which takes as input a description of another machine

    - It becomes a simulator for the <factorial machine

    - The most amazing part of it is that it fits on a blackboard.

(DEFINE EVAL
    (LAMBDA (EXP ENV)
        ((COND
            ((NUMBER? EXP) EXP)
            ((SYBOL? EXP)(LOOKUP EXP ENV))
            ((EQ? ((CAR EXP) 'QUOTE)(CADR EXP))
            ((EQ? (CAR EXP) 'LAMBDA)
                (LIST 'CLOSURE (CDR EXP) ENV))
            ((EQ? (CAR EXP) 'COND
                (EVCOND (CDR EXP) ENV))
            (ELSE (APPLY (EVAL (CAR EXP) ENV)
                                    (EVLIST (CDR EXP) ENV))))))

>
3->3
X->3
'FOO => (QUOTE FOO) -> FOO
(LAMBDA(X)(+ X Y)) -> (CLOSURE((X)(+ X Y))<EVN>)
(COND (P1 E1)(P2 E2)...)
(+ X 3)

(DEFINE APPLY
    (LAMBDA (PROC ARGS)
        (COND
            ((PRIMITIVE? PROC)
                (APPLEY-PRIMOP PROC ARGS))
            ((EQ? (CAR PROC) 'CLOSURE)
                (EVAL (CADADR PROC)
                            (BIND (CAADR PROC)
                                        ARGS
                                        ((ADDR PROC))))
            (ELSE ERROR))))

PART 2

4.EXAMPLE

(EVAL '(((LAMBDA(X)(LAMBDA(Y)(+ X Y))) 3) 4) <E0>)

(APPLY (EVAL '((LAMBDA(X)(LAMBDA(Y)(+ X Y))) 3 <E0>)
              (EVLIST '(4) <E0>)

(APPLY (EVAL '((LAMBDA(X)(LAMBDA(Y)(+ X Y))) 3) <E0>)
                (CONS (EVAL '4 <E0>)
                             (EVLIST '() <E0>)))

(APPLY (EVAL '((LAMBDA(X)(LAMBDA(Y)(+ X Y))) 3) <E0>)
                (CONS 4 '()))

(APPLY (EVAL '((LAMBDA(X)(LAMBDA(Y)(+ X Y))) 3) <E0>)
                '(4))

(APPLY (APPLY (‘CLOSURE ((X)(LAMBDA(Y)(+ X Y)))<E 0>
                            '(3))
               ‘(4))

(APPLY (EVAL '(LAMBDA(Y)(+ X Y)) <E1>)
                '(4))

(APPLY '(CLOSURE ((Y)(+ X Y)) <E1>)
                '(4))

(APPLY '(CLOSURE ((Y)(+ X Y)) <E1>)
                '(4))

(EVAL '(+ X Y) <E2>)

(APPLY (EVAL '+ <E2>)

(APPLY (EVAL '+ <E2>))(EVLIST '(X Y) <E2>))

(APPLY '+: '(3 4))

7

5.Curry's Paradoxical Combinator of Y

Y = (LAMBDA (f)
            ((LAMBDA(X)(f (X X)))
                (LAMBDA(X)(f X X))))

(Y F) = ((LAMBDA (X)(F (X X)))
                (LAMBDA(X)(F (X X))))

        = (F ((LAMBDA(X)(F(X X)))(LAMBDA(X)(F (X X))))

(Y F) - (F (Y F))

    - So, Y is a magical thing which, when applied to some function, produces the object which is the fixed point of that function, if it exists, and if this all works,

    - What Lisp is the fixed point of the process that's which says, if I knew what Lisp was and substituted it in for eval, and apply, and so on, on the right hand sides of all those recursion equations, then if it was a real good lisp, is a real one, then the left hand side would also be lisp.

    - Purpose : There is no define/let in purl Lambda, only need alpha/beta/eta

    - 参考： 魂断不动点——Y组合子的前世今生