## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Notes

# Lazy Evaluation: Scheme Streams¶

## Bryn Mawr College¶

### Fall 2014¶

Arguments to Scheme functions

All arguments are:

• Evaluated (in some undefined order) prior to calling the function
• Passed by value to the function

Consider:

(f (f2 23) (lambda () 89) 67)

each of:

• (f2 23)
• (lambda () 89)
• 67

is evaluated before being passed in to $f$.

Evaluating, then passing in to the function is called "eager evaluation"

## Lazy Evaluation¶

We can use closures to delay computation!

In [1]:
(define L (lambda () (+ 3 4)))


And we can force the evaluation later:

In [44]:
(L)

Out[44]:
7

Very similar to the idea of a continuation

## Lazy Evaluation:¶

We create some helper functions to create a Domain Specific Language (DSL) inside of Scheme using closures to delay computation. We'll explore define-syntax in detail below.

In [45]:
(define-syntax freeze
[(freeze ?a) (lambda () ?a)])

(define thaw
(lambda (?a)
(?a)))


Lazy Evaluation with freeze and thaw

In [46]:
(freeze (+ 1 2))

Out[46]:
#<procedure>
In [47]:
(define L (freeze (+ 1 2)))
(thaw L)
3

Out[47]:
3

## Scheme Stream¶

A stream is composed of an item (thawed) cons-ed onto a (frozen) stream, recursively.

In [48]:
(define partial-stream (cons 'a (lambda () 'b)))
(car partial-stream)

Out[48]:
a
In [49]:
(cdr partial-stream)

Out[49]:
#<procedure>
In [50]:
((cdr partial-stream))

Out[50]:
b

A stream is composed of an item (thawed) cons-ed onto a (frozen) stream, recursively.

In [85]:
(define partial-stream (cons 'a (freeze 'b)))
(car partial-stream)

Out[85]:
a
In [86]:
(cdr partial-stream)

Out[86]:
#<procedure>
In [87]:
(thaw (cdr partial-stream))

Out[87]:
b

A stream is composed of an item cons-ed onto a frozen stream, recursively.

In [88]:
(define partial-stream (cons 'a (lambda () 'b)))
(car partial-stream)

Out[88]:
a
In [89]:
((cdr partial-stream))

Out[89]:
b

But that is only a partial stream, because the cdr is itself not a stream.

Streams Goal: create tools and data structures to make an infinite stream built on freeze and thaw.

Something like a list, but infinite.

Need something similar to cons, car, and cdr...

## Macros¶

Before we proceed, we need to explore the idea of a macro.

A macro is a process that manipulates concrete syntax. Thus, it just manipulates the text of the code.

In Scheme, we use define-syntax to create macros.

Consider the problem of timing the running of an expression. You need to start a clock before it runs, evaluate the expression, get the stop time, print the time taken, and return the results.

In [100]:
(define-syntax time-it
[(time-it ?expr)
(let ((start (current-time))
(result ?expr))
(printf "The expression took ~a seconds~%" (- (current-time) start))
result)])

In [101]:
(time-it (+ 1 2))

The expression took 0.000684022903442 seconds

Out[101]:
3
In [102]:
(import "time")

Out[102]:
(time)
In [103]:
(time-it (time.sleep 2))

The expression took 2.00317406654 seconds


## Macros to create Streams¶

The heart of what follows is a re-imagined cons$. We "hide" a freeze inside of it: In [ ]: (define-syntax cons$
[(cons$?a ?b) (cons ?a (freeze ?b))])  Car and cdr can be defined as normal functions: In [56]: (define car$ car)

(define cdr$(lambda (stream) (thaw (cdr stream))))  ## Scheme Streams¶ In [57]: (define X (cons$ 'a 'b))
(car$X)  Out[57]: a In [58]: (cdr$ X)

Out[58]:
b
In [98]:
(define long-time
(lambda (item)
(time.sleep 5)
item))

(define X (cons$'a (long-time 'b))) (car$ X)

Out[98]:
a
In [99]:
(cdr$X) ;; ... long time passes  Out[99]: b ## Infinite Stream of Ones¶ Consider making an infinite stream of ones. Infinite? Sure! In [61]: (define ones (cons$ 1 ones))

In [62]:
(car$ones)  Out[62]: 1 In [63]: (cdr$ ones)

Out[63]:
(1 procedure <function b_proc_1_d at 0x7f09aaac7c08> ((lexical-address-aexp 1 173 ones ("In [61]" 1 23 23 1 26 26))) () #<environment>)
In [64]:
(car$(cdr$ ones))

Out[64]:
1
In [65]:
(car$(cdr$ (cdr$ones)))  Out[65]: 1 ## Tools for Streams¶ In [66]: (define get$
(lambda (n stream)
(if (= n 0)
'()
(cons (car$stream) (get$ (- n 1) (cdr$stream))))))  In [67]: (get$ 10 ones)

Out[67]:
(1 1 1 1 1 1 1 1 1 1)

### Integers¶

In [68]:
(define integers-from
(lambda (n)
(cons$n (integers-from (+ n 1))))) (define integers (integers-from 0)) (get$ 10 integers)

Out[68]:
(0 1 2 3 4 5 6 7 8 9)

### Integers¶

We can think of it looking like:

(0 . (1 . (2 . (3 . (4 . #<procedure>))))

but these cdr's don't exist until they are evaluated.

Some have supposed that quantum mechanics' collapsing wavefunction is similar to lazy evaluation.

### Nature's Lazy Evaluation¶

"To put it in most simple terms, nature doesn't decide certain intrinsic properties of elementary particles until they are observed! This is in some sense similar to computer languages supporting functional programming paradigms, where an infinite array can be defined. Access to any element in the array is dynamically computed to return the value, as practically, it's not possible to store an array with infinite elements. Nature seems to do the same."

natures-lazy-evaluation-algorithm

Schrödinger's cat

### Fun with Streams!¶

In [70]:
(define add$(lambda (s1 s2) (let ((h1 (car$ s1))
(h2 (car$s2))) (cons$ (+ h1 h2)
(add$(cdr$ s1) (cdr$s2)))))) (define twos (add$ ones ones))
(get$10 twos)  Out[70]: (2 2 2 2 2 2 2 2 2 2) ## Fibs¶ Notice:  (0 1 1 2 3 5 8 13 21 ... (1 1 2 3 5 8 13 21 34 ... + ------------------------------- (0 1 1 2 3 5 8 13 21 34 55 ... If we assume the fibs exist, then add$ them to the cdr$ of the fibs and start with 0, 1 then we get the fibs. Fun with Recursive Streams?! In [72]: (define fibs (cons$ 0
(cons$1 (add$ fibs
(cdr$fibs))))) (get$ 10 fibs)

Out[72]:
(0 1 1 2 3 5 8 13 21 34)

### multiply$¶ In [35]: (define combine$
(lambda (op)
(lambda (s1 s2)
(cons$(op (car$ s1) (car$s2)) ((combine$ op) (cdr$s1) (cdr$ s2))))))

(define multiply$(combine$ *))


## Factorials¶

Notice that:

Facts:     (1 1  2   6  24  120   720  5040  40320 ...
Nats:      (1 2  3   4   5    6     7     8      9 ...
Multiplied: ---------------------------------------
1 2  6  24 120  720  5040 40320 362880 ...

Almost the Factorials!

1. Assume that a stream exists
2. Do something with it that (almost) gives you the stream
3. Adjust the first elements to give you the stream

Factorials

In [36]:
(define facts
(cons$1 (multiply$ facts
natural-numbers)))


### Factorials¶

In [37]:
(define facts (cons$1 (multiply$ facts natural-numbers)))

(define !
(lambda (n)
(nth n facts)))

(define nth
(lambda (n stream)
(cond
((= n 0) (car$stream)) (else (nth (- n 1) (cdr$ stream))))))


map$In [73]: (define map$
(lambda (f stream)
(cons$(f (car$ stream))
(map$f (cdr$ stream)))))

(get$10 (map$ (lambda (n) (+ n 1)) ones))

Out[73]:
(2 2 2 2 2 2 2 2 2 2)
In [79]:
(define the-empty-stream (cons$'() the-empty-stream)) (define null$?
(lambda (stream)
(null? (car$stream)))) ;; filter$
(define filter$(lambda (f stream) (let ((item (car$ stream)))
(cond
((null$? stream) the-empty-stream) ((f item) (cons$ item (filter$f (cdr$ stream))))
(else (filter$f (cdr$ stream)))))))


Primes?

(2 . (stream with all divisible by 2 removed))

(2 . (3 . (stream with all divisible by 2 and 3 removed))

(2 . (3 . (5 . (stream with all divisible by 2, 3, 5 removed)))

Sieve of Eratosthenes

In [83]:
(define sieve
(lambda (stream)
(cons$(car$ stream)
(sieve (filter$(lambda (x) (not (= (% x (car$ stream)) 0)))
(cdr$stream)))))) (define primes (sieve (integers-from 2)))  In [84]: (get$ 10 primes)

Out[84]:
(2 3 5 7 11 13 17 19 23 29)