recitation 22: lazy evaluation & streams

------------------------------------------------------------------------
* What stream does the following expression return?

  (define alt (cons-stream 0 (interleave integers alt)))




* Write a function that merges two ordered streams of integers, removing
  duplicates as it goes. Assume that each individual stream contains no
  duplicates.

  (define (merge-stream s1 s2)





* Write a function that removes duplicates from an unordered stream.
  Use stream-filter.

  (define (remove-duplicates s)





* why do we like streams?  
  real-time signal/data processing, e.g., speech processing


------------------------------------------------------------------------
* (delay-it <exp> <env>)  ==>  <thunk>

  This is a promise to return a value when needed later or 'forced'.

* (force-it <thunk>)  ==>  <value>

  This forces the evaluation of a thunk or delayed expression. 
  We can "memoize" a thunk by mutating it into an evaluated thunk.

------------------------------------------------------------------------
* Applicative Order - Call by Value (strict)
  Scheme is an applicative order language, which means that before
  applying a procedure, scheme evaluates all the sub-expressions, even
  if some of those sub-expressions will never be used.
  Advantages:
  - Simple and well understood.  
  - Predictable. 
  - Easily implemented. 
  - Interacts well with other languages. 
  Disadvantages:
  - Doesn't allow infinite lists. 
  - May compute unneeded values. 

* Normal Order - Call by Need (lazy)
  Advantages:
  - Infinite Lists. 
  - Never compute unneeded values. 
  - Don't get stuck in infinite recursions if return value not used. 
  - Used to easily implement if, and, or. 
  Disadvantages: 
  - Confusing to program. 
  - Difficult to predict, especially with side effects. 
  - Doesn't link well to other languages. 

------------------------------------------------------------------------
* Do applicative order and normal order evaluators always result in
  the same answer?  What is the value of the following expression
  using applicative order and normal order?

  (define (try a b)
    (if (= a 0) 1 b))

  (try 0 (/ 1 0)) 


* Note that normal-order is (approximately) equivalent to systematically
  delaying each argument on a combination and forcing each parameter:
 
  (try (delay 0) (delay (/ 1 0)))

  (define (try a b)
    (if (= (force a) 0) 1 (force b)))

------------------------------------------------------------------------
* in applicative-order scheme, streams need to be implemented as
  SPECIAL FORMS.  Explain how to do this in our original evaluator.




* in our evaluator with lazy semantics, streams can be implemented as
  FUNCTION DEFINITIONS.  How?




------------------------------------------------------------------------
* Ben Bitdiddle wants a stream of random numbers for simulation.
  Help him decide between the following two implementations.  

  A.  (define random-stream 
         (cons-stream (random 100) random-stream))

  B.  (define (make-random-stream) 
         (cons-stream (random 100) (make-random-stream)))
      (define random-stream (make-random-stream))




* Does it matter if the evaluator uses memoization?  What does our
  lazy evaluator do?  How can we change it to do the other?





------------------------------------------------------------------------
* lets add apply to the evaluator.  what about adding apply to the lazy
  evaluator?