SICP OpenCourse (Structure and Interpretation of Computer Programs)

PART 1

1.POINT: STREAM A DIFFERENT WORLDVIEW.

2.REVIEW 

    - Key Concept: Assignment, State, Change, Time, Identity, Object, Share

    - It's harder way to look at things

    - Because we have to think more mechanistically about our programming language

    - We can't just think about it as mathematics.

3.Why? How'd we get into mess?  The answer is MODULARITY.

    - May be the real reason that we put such a price to write programs that mirror our view of reality is that we have the wrong view of reality.

    - May be time is just an illusion and nothing ever changes.

    - See for example, if I take this chalk, it's an Object and it has a state. At each moment it has a position and a velocity. And if we do something, that, that state can change.

    - But if we studied any relativity, for instance, you know that you don't think of the path of that chalk as something that goes on instant by instant.

    - It's more insightful to think of that whole chalk's existence as a path in space-time. that's all splayed out . There aren't individual positions and velocities. There's just its unchanging existence in space-time.

4.FROM MICO PERSPECTIVE TO MACRO PERSPECTIVE

    - Similarly, if we look at this electrical system, if we imagine this electrical system is implementing sort of signal processing system, the signal processing engineer who put that thing together doesn't think of it as , well, at each instance there's a voltage coming in. And that translates into something. And that effects the state over here.

    - Nobody putting together a signal processing system thinks about it like that.

    - Instead, you say there's the signal that's splayed out over time.

    - And it this is acting as a filter, this whole thing transforms this whole thing for some sort of other output.

    - You don't think of it as what's happening instant by instant as the state of these things.

    - And some how you think of this box as a whole thing not as little pieces sending messages of state to each other at particular instants.

    - Today we're going to look at another way to decompose systems more like the signal processing engineer's view of the world than it is like thinking about Objects that communicate sending messages.

    - That's called "STREAM PROCESSING"

5.COMPARE TWO PROCEDURES 

- Purpose : sum the odd squares from a tree

(define (sum-odd-squares tree)
    (if (leaf-node? tree)
        (if (odd? tree)
            (square tree)
            0)
        (+ (sum-odd-squares
                (left-branch tree))
            (sum-odd-squares
                (right-branch tree)))))

- Purpose : Find the odd Fibonacci number among the first n.

(define (odd-fibs n)
    (define (next k)
        (if (> k n)
            '()
            (let ((if (fib k)))
                (if (odd? f)
                    (cons f (next (1 + k)))
                    (next (1 + k))))))
    (next 1))

- PROBLEM : The program don't chop things up in the right way.

    -Going back to this fundamental principle of CS that in order to control something, you need the name of it, We don't really have control over thinking about things this way because we don't have our hands in them explicitly.

    - We don't have a good language for talking about them.

    - Well let's invent an appropriate language.

6. NEW LANGUAGE: KEY IS WHAT IS SIGNAL? => DATA STRUCTOR=> "STREAM"

(CONS-STREAM x y)    //CONSTRUCTOR

(HEAD s)    //SELECTOR

(TAIL s)        //SELECTOR

For any x y

(HEAD (CONS-STREAM x y)) => x    //AXIOM

(TAIL (CONS-STREAM x y)) => y    //AXIOM

THE-EMPTY-STREAM

7.START CONSTRUCTING THE PIECES OF THE LANGUAGE TO OPERATE ON STREAMS

(define (map-stream proc s)
    (if (empty-stream? s)
        the-empty-stream
        (cons-stream
            (proc (head s))
            (map-stream proc (tail s)))))

(define (filter pred s)
    (cond
        ((empty-stream? s) the-empty-stream)
        ((pred (head s))
            (cons-stream (head s) (filter pred (tail s))))
        (else (filter pred (tail s)))))

(define (accumulate combiner init-val s)
    (if (empty-stream? s)
        init-val
        (combiner (head s)
                        (accumulate combiner init-val 
                                (tail s)))))

(define (enumerate-tree tree)
    (if (leaf-node? tree)
        (cons-stream tree the-empty-stream)
        (append-stream
            (enumerate-tree
                (left-branch tree))
            (enumerate-tree
                (right-branch tree)))))

(define (append-streams s1 s2)
    (if (empty-stream? s1)
        s2
        (cons-stream (head s1)
                               (append-stream s (tail s1 s2))))

(define (enum-interval low high)
    (if (> low high)
        the-empty-stream
        (cons-stream low 
            (enum-interval (1 + low) high))))

8. USE NEW LANGUAGE TO IMPLEMENT SUM-ODD-SQUARE

(define (sum-odd-squares tree)
    (accumulate
        +
        0
        (map 
            square
            (filter odd
                (enumerate-tree tree)))))

(define (odd-fibs n)
    (accumulate
        cons
        '()
        (filter
            odd
            (map fib
                (enum-interval 1 n)))))

9.WHAT'S THE ADVANTAGE OF THIS NEW LANGUAGE?

    - Well, for one thing, we now have pieces that we can start mixing and matching.

    - If I wanted to change this, compute the squares of the integers and then filter them, all I need to do is pick up a standard piece like this it's a map square and put it in.

    - See, The advantage of this stream processing is that we're establishing, this is one of the big themes of the course, CONVENTIONAL INTERFACES.

    - Conventional interfaces that allow us to glue things together.

    - It allows us to see the commonality of programs.

    - Generate and test paradigm for programs. 

    - MAP, FILTER, ACCUMULATE => CAN INSTALL MORE THAN 60% CODE

    - My understanding: Stream is Context.

PART 2

10.QUEEN PROBLEM

    - Traditional way called BACK TRACKING SEARCH

    - TIME

        - Why is it complicated? this program is too inordinately concerned with time

        - if I stop worrying about time so much, there will be a simpler way to describe.

        - My understanding: In our life , we should stop worrying about time. then we will see the whole picture, the truth , THE ONE.

            - Because , TIME means Separate. And the real understanding base on the whole view.

            - Entropy reduction is a whole view

            - Abstract perspective is the way to get a whole view

            - So, learn abstract thinking can let use understand truth.

(SAFE? <ROW> <COLUMN> <REST-OF-POSITIONS>)

11.CHANGE VIEW TO STREAM STYLE

(define (queens size)
    (define (fill-cols k)
        (if 
            (= k 0)
             (singleton empty-board)
            (collect......)
    (fill-cols size)

    - All possible ways under k-1 level

    - How do I extend that? => How to find next safe position?

    - From level k-1 to level k

    - My understanding: STREAM VIEW IS RECURSIVE STYLE, 

        - You don't need to know all thing, you just make the path which from this level to next level. 

        - You just need to focus on "Direction of behavior" with a MICO perspective  and with a whole promise with a MACRO perspective.

        - SO, the key point is, with two different perspective : MICO and MACRO.        

12. WHY USE STREAM IS SIMPLER?

    - We threw away the whole idea that is some process that happens in time with state.

    - And we just said it's a whole collection of staff that's why it simpler.

    - Right? We've changed our view of what it is we're trying to model. We stop modeling things that evolve in time have steps and have state.

    - And instead, we're trying to model this global thing like the whole flight of the chalk, rather than its state at each instant.

PART 3

13.PURPOSE: HOW TO MAKE STREAM STYLE AS EFFICIENT AS RUNNING TRADITIONAL PROGRAMMING STYLE.

    - What I mean by that is that  we really can write stream programs exactly like the ones I wrote and arrange things so that when the machine actually runs, it's as efficient as running this traditional programming style, that mixes up the generation and the test.

14. EXAMPLE: Find the second prime between 10,000 and 1,000,000

(head 
    (tail (filter
            prime?
            (enum-interval 10000 1000000))

INTERVAL 10,000 1,000,000    ==>    FILTER PRIME?    ==>

    - No computation gets done except when you tug on these things

    - Version one -> stream is List

--Stream(100%)-->DEALER-->Stream(100%)-->DEALER-->Stream(100%)-->

    -Version two 

--Stream(1%)-->DEALER-->Stream(1%)-->DEALER-->Stream(1%)-->

15.HOW DO WE MAKE THIS THING?

    - We want to arrange for a stream to be a data structure that sorts of computes itself incrementally, sort of "on-demand" data structure.

CONS-STREAM

HEAD

TAIL

(CONS-STREAM x y)
    ABBREVIATION FOR =>
        (CONS x (DELAY y))    // DEALY is PROMISE, DELAY is the essential of asynchronization.

(HEAD s) =>( CAR s)

(TAIL s) => (FORCE (CDR s))    //FORCE is PULL

(DELAY <exp>)
    ABBREV FOR =>
            (LAMBDA () <exp>)

(FORCE P) => (P)

16.SUMMARY

    - We said the old style, traditional style of programming is more efficient.

    - And the stream thing is more perspicacious.

    - And we managed to make the stream procedures run like the other procedures by using delay.

    - And the thing that delay did for us was to DE-COUPLE the apparent order of events in our programs, from the actual order of events that happen in the machine.

    - That's really what delay is doing => THE WHOLE PINT

    - We're given up the idea that our procedures, as they run, or as we look at them, mirror some clear notion of time.

    - By giving that up, we give delay the freedom to arrange the order of events in the computation the way it likes.

    - We DE-COUPLE the apparent order of events in our programs from the actula order of events in the computer.

    - Problem => need one little hack => "MEMOIZATION"

(tail (tail(tail.....)

change DELAY=> (MEMO-PROC (LAMBDA ()<exp>))

    - And remeber,again, the whole idea of this is that we've used the fact that there's no really good dividing line between procedures and data . We've written data structures that, in fact, are sort of like procedures And what that's allowed us to do is take an example of a common control structure in this place iteration. And we've built a data structure which, since itself is a procedure, kind of has this iteration control structure in it. And that's really what stream are.

    - PUREPOSE => EUM 1 ~ 1,000,000, THE REALLY IMPLEMENT

        - First Step to build one PARI, CAR is point to 1, CDR is point to a Promise

        - Second Step to build another PARI, CAR is point to 2, CDR is point to a Promise.Then, First PARI's CDR is change to point to the Second PARI. 

        - Promise actually is a procedure

        - This example shows two different view , MICO and MACRO, MICO means determinacy, MACRO means nondeterminacy.