SICP OpenCourse (Structure and Interpretation of Computer Programs)
PART 1
1.POINT: FUNCTIONAL vs OBJECT, DELAY vs ASSIGNMEN
2.If we have a very long stream, we only compute what we need the thing only get computed when we actually ask for them
- ask for the n-th element of a stream
(define (nth-stream n s)
(if (= n 0)
(head s)
(nth-stream (-1 + n)(tail s))))
(define (print-stream s)
(cond ((empty-stream? s) "done")
(else (print (head s))
(print-stream (tail s)))))
(define (integer-from n)
(cons-stream n
(integers-from (1 + n))))
(define integers (integers-from 1))
- Another way to implement Computing all of the primes => called Eratothens
(define (sieve s)
(cons-stream
(head s)
(sieve (filter
(lambda (x)
(not
(divisible? x (head s))))
(tail s)))))
(define primes
(sieve (integers-from 2)))
- think of the sieve a filter, infinitely recursive filter
3.There's another way to think about stream processing, and that's to focus not on programs that sort of process these elements as you walk down the stream, but on things that kind of process the streams all at once.
(define (add-streams s1 s2)
(cond ((empty-stream? s1) s2)
((empty-stream? s2) s1)
(else
(cons-stream
(+ (head s1)(head s2))
(add-streams (tail s1)
(tail s2))))))
(define (scale-stream c s)
(map-stream (lambda(x)(* x c)) s))
- So given those two, let me show you what I mean by programs that operate on stream all at once.
(DEFINE ONES (CONS-STREAM 1 ONES)) // REALLY => (CONS 1 (DELAY ONES))
(DEFINE INTEGERS
(CONS-STREAM 1
(ADD-STREAMS INTEGERS ONES)))
(define (integral s initial-value dt)
(define int
(cons-stream
initial-value
(add-streams (scale-stream dt s)
int))
int)
(DEFINE FIBS
(CONS-STREAM 0
(CONS-STREAM 1
(ADD-STREAMS FIBS (TAIL FIBS)))))
4.RECURSIVE
- Instead of thinking that recursive procedures, we have recursively defined data objects.
- There's no difference really between procedures and data.
- In fact, in some sense, the underlying streams are procedures sitting there, although we don't think of them that way.
- Well, then it should be natural that we have recursive data, too.
- Problem=> Who is first:
(DEFINE Y
(INTEGRAL // CHANGE INTEGRAL TO ADD DELAY
DY 1 .001)) //CHANGE DY TO (DELAY DY)
(DEFINE DY
(MAP SQUARE Y)) //IT DOSEN'T WORK
PART 3
5.PROBLEM: TOO DIFFICULT TO CONTROL WITH DELAY
- If you have some very complicated system with all kinds of self-loops, it becomes very, very difficult to see where you need those delays.
- And if you leave them out by mistake, it becomes very ,very difficult to see why the thing maybe isn't working.
-FIX => Change the language => all procedures acted like CONS-STREAM
- So that every procedure automatically has an implicit delay around its argument.
- That would mean when you call a procedure, the arguments wouldn't get evaluated.
- Instead, they'd only be evaluated when you need them, so them might be passed off to some other procedure, which wouldn't evaluate them either.
- If we did that, since everything would have a UNIFORM DELAY, called NORMAL-ORDER EVALUATION.
6.NORMAL-ORDER EVALUATION VS APPLICATIVE-ORDER EVALUATION
- What is APPLICATIVE-ORDER EVALUATION : When you evaluate a combination, you find the values of all the pieces. You evaluate the arguments and then you substitute them in the body of the procedure.
- What is NORMAL-ORDER EVALUATION? Normal order say no don't do that. substitute in the body of the procedure, but instead of evaluating the arguments, you just put a promise to compute them there.
- Or another way to say that you take the expressions for the arguments, if you like, and substitute them in the body of the procedure and go on, and never really simplify anything until you get down to a primitive operator.
7.BUT THERE'S PRICE
- Remember how we got here. We're decoupling time in the programs from time in the machines. And if we put delay, that sort of decouples it everywhere not just in streams.
- Remember what we're trying to do . We're trying to think about programming as a way to specify processes. And if we give up too much time, our language becomes more elegant, but it becomes a little bit less expressive.
- There are certain distinctions that we can't draw. One of them, for instance, is iteration called "DRAGGING TAILS"
- Another problem is that normal-order evaluation and side-effects just don't mix.
- You can't simultaneously go around trying to model objects with local state and change at the same time do these normal-order tricks of de-coupling time.
> ASSIGNMENT VERSION
(define x 0)
(define (id n)
(set! x n) n)
(define (inc a)(1 + a)
> DELAY VERSION
(define y (inc (id 3)))
=> x -> ???
y -> 4
x -> ???
- you can't see what kind of a mess that's going to make for debugging interactive programs when you have normal-order evaluation.
-DEEP REASON is DELAY, throw away TIME.
-Because fundamental contradiction in what you want
8.FUNCTIONAL PROGRAMMING
- What is it that you are trying to model and how do you look at the world,called The debate over functional programming.
- So-called "purely functional language" doesn't have side-effect
- So programs really are like mathematics not like MODELS/OBJECTS in the real world.
- Functional no time, so , No synchronization problems
9.REJOINDER
- random generator
- FIX WITH STREAM : RANDOM STREAM --> CESARD TEST -->
- My understanding: TX is Stream. So, use stream style to build an Application.
10.BANK ACOUNT EXAMPLE
> OBJECT VIEW
- request and response
- State
- Time
- Message
> Stream VIEW
----4 2 2 1---> BANK ACCOUNT---7 5 3 1----stream--->
- No state
- User couldn't tell that this system doesn't have state.
(define (make-deposit-account balance deposit-stream)
(cons-stream
balance
(make-deposit-account
(+ balance (head deposit-stream))
(tail deposit-stream))))
Bill&Dave====> MERGE---->BANK ACCOUNT---->
10.SUMMARY
-A very basic problem in computer science, which is how to define a language that somehow can talk about delayed evaluation but also be able to reflect this view that there are objects in the world.
- How do we somehow get both?
- And I think that's very hard problem, that has almost nothing to do with computer science, that with two very incompatible ways of looking at the world.
网友评论