SICP OpenCourse (Structure and Interpretation of Computer Programs)

PART 1

1.POINT: IMPLEMENT META-CIRCULAR EVALUATOR BY HARDWARE

2.PURPOSE

    - What I'm really going to show you is how a piece of machinery can be built to do a job that you have written down as a program. That program is, in fact, a description of a machine.

    - Then later show you a not very complicated program, how the evaluator transforms into a piece of hardware.You have mede the Universal transition and can execute any program imaginable with a piece of well-defined hardware.

3. Example: GCD(Greatest Common Divisor)

(define (gcd a b)
    (if (= b 0)
        a
        (gcd b (remainder a b))))

    - Data path for a GCD machine & Controller for a GCD machine:

    - A specification of the GCD machine

(data-paths
    (registers
        ((name a)(buttons ((name a<-b)(source (register b)))))
        ((name b)(buttons ((name b<-t)(source (register t)))))
        ((name t)(buttons ((name t<-r)(source (operation rem))))))
    (operations
        ((name rem)
            (inputs (register a)(register b)))
        ((name =)
            (inputs (register b)(constant 0)))))

(controller
    test-b
        (test =)
        (branch (label gcd-done))
        (t<-r)
        (a<-b)
        (b<-t)
        (goto (label test b))
    gcd-done)

(DEFINE (REMAINDER N D)
    (IF (< N D)
            N
            (REMAINDER (- N D) D)))

PART 2

4.USE A STACK TO IMPLEMENT RECURSION, TO SIMULATE THE EXISTENCE OF AN INFINITE MACHINE.

    - The real space is a list. 3D world is from 1D LIST

(DEFINE (FACT N)
    (IF (= N 1)
        N
        (* N (FACT (- N 1))))))

    - USE STACK TO SIMULATE MANY FACTS

    - The important thing is that here I have something that happens before and after, in the outer machine, the execution of the inner machine.

    - So this machine has to have a life. It has to exist on both times sides of this machine(Inner machine)

    - So somehow, I have to have a place to store the things that this thing needs to run.

5.ORGANIZATION OF DEGISTER MACHINE

    - One of the most amazing thing about computation is that after a while, you build up a little more features and a few more features, and all of the sudden, you've got everything you need.

    - I don't need much more to make a UNIVERSAL COMPUTER.