|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Notes | |||
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!
(define L (lambda () (+ 3 4)))
And we can force the evaluation later:
(L)
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.
(define-syntax freeze
[(freeze ?a) (lambda () ?a)])
(define thaw
(lambda (?a)
(?a)))
Lazy Evaluation with freeze and thaw
(freeze (+ 1 2))
(define L (freeze (+ 1 2)))
(thaw L)
3
Scheme Stream¶
A stream is composed of an item (thawed) cons-ed onto a (frozen) stream, recursively.
(define partial-stream (cons 'a (lambda () 'b)))
(car partial-stream)
(cdr partial-stream)
((cdr partial-stream))
A stream is composed of an item (thawed) cons-ed onto a (frozen) stream, recursively.
(define partial-stream (cons 'a (freeze 'b)))
(car partial-stream)
(cdr partial-stream)
(thaw (cdr partial-stream))
A stream is composed of an item cons-ed onto a frozen stream, recursively.
(define partial-stream (cons 'a (lambda () 'b)))
(car partial-stream)
((cdr partial-stream))
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.
(define-syntax time-it
[(time-it ?expr)
(let ((start (current-time))
(result ?expr))
(printf "The expression took ~a seconds~%" (- (current-time) start))
result)])
(time-it (+ 1 2))
(import "time")
(time-it (time.sleep 2))
Macros to create Streams¶
The heart of what follows is a re-imagined cons$. We "hide" a freeze inside of it:
(define-syntax cons$
[(cons$ ?a ?b)
(cons ?a (freeze ?b))])
Car and cdr can be defined as normal functions:
(define car$ car)
(define cdr$
(lambda (stream)
(thaw (cdr stream))))
Scheme Streams¶
(define X (cons$ 'a 'b))
(car$ X)
(cdr$ X)
(define long-time
(lambda (item)
(time.sleep 5)
item))
(define X (cons$ 'a (long-time 'b)))
(car$ X)
(cdr$ X)
;; ... long time passes
Infinite Stream of Ones¶
Consider making an infinite stream of ones. Infinite? Sure!
(define ones (cons$ 1 ones))
(car$ ones)
(cdr$ ones)
(car$ (cdr$ ones))
(car$ (cdr$ (cdr$ ones)))
Tools for Streams¶
(define get$
(lambda (n stream)
(if (= n 0)
'()
(cons (car$ stream)
(get$ (- n 1) (cdr$ stream))))))
(get$ 10 ones)
Integers¶
(define integers-from
(lambda (n)
(cons$ n (integers-from (+ n 1)))))
(define integers (integers-from 0))
(get$ 10 integers)
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."
Schrödinger's cat
Fun with Streams!¶
Adding two streams together:
(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)
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?!
(define fibs
(cons$ 0
(cons$ 1
(add$ fibs
(cdr$ fibs)))))
(get$ 10 fibs)
multiply$¶
(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!
- Assume that a stream exists
- Do something with it that (almost) gives you the stream
- Adjust the first elements to give you the stream
Factorials
(define facts
(cons$ 1
(multiply$ facts
natural-numbers)))
Factorials¶
(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$
(define map$
(lambda (f stream)
(cons$ (f (car$ stream))
(map$ f (cdr$ stream)))))
(get$ 10 (map$ (lambda (n) (+ n 1)) ones))
(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
(define sieve
(lambda (stream)
(cons$ (car$ stream)
(sieve (filter$
(lambda (x) (not (= (% x (car$ stream)) 0)))
(cdr$ stream))))))
(define primes (sieve (integers-from 2)))
(get$ 10 primes)