CS 22

Clab 28: Infinite Streams with recursion and The Meta-circular evaluator I

Last clab, we used delay and force to build a small library of useful procedures. By using stream-filter, we were able to construct a stream of all odd integers and a stream of all even integers. If you didn't finish this, you can get my version at: /home/cfk/pub/cs22/week9/clab27.scm.

Another way to define the even integers is to construct them from the stream of integers by adding each element to itself. Define and think about add-streams and evenstream.

;;; assumes that s1 and s2 are streams of numbers. add-streams ;;; returns a stream that consists of the sums of corresponding ;;; elements in s1 and s2. If one of the streams run out before ;;; the other, its contribution to the subsequent sums is zero. (define (add-streams s1 s2) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (cons (+ (stream-car s1) (stream-car s2)) (delay (add-streams (stream-cdr s1) (stream-cdr s2))))))) ;;; generates a stream of even positive integers (define evenstream (add-streams ints ints)) Test them by evaluating: (stream->list 40 evenstream) which forces the first 40 elements out of evenstream.

Combining infinite streams and recusive definitions can be really mind-blowing. Kids, do not try this at home without your instructor present! Read the bottom of page 328 and page 329 twice. Then evaluate and think about:

;;; fibs generates a stream of fibonacci numbers (define fibs (cons 0 (delay (cons 1 (delay (add-streams (stream-cdr fibs) fibs)))))) Try: fibs (stream->list 50 fibs) which should show the first 50 Fibonocci numbers. Fibs has a promise to deliver any Fibonocci number (there may eventually be a software/hardware limit). It is appropriate to think of fibs as an infinite stream of Fibonocci numbers.

Now that we have a couple of streams and filters, you should be able to write a fairly simple expression that will display the 7th odd Fibonocci number.

Do so and call me over to see it.

Soon, when we write our own scheme interpreter, we will be able to extend our interpreter by adding the special forms: force, delay, and cons-stream. Then, in our interpreter, we can use cons-stream and code from the text.

As part of your homework for Wednesday, do exercise 3.64 on page 338. Here is sqrt-stream from top of page 335.

(define (sqrt-stream x) (cons-stream 1.0 (stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-stream x)))) You'll have to use our work-around to define sqrt-stream. But if you pull the whole thing off, you should be able to get something like: > (msqrt 10000 0.001) 100.0 > (msqrt 1000000 0.001) 1000.0000000000118 >

The Meta-circular evaluator I

SICP takes an appropriate top-down approach to defining the minievaluator. By using abstraction barriers, things like bindings and frames can be represented in different ways without affecting the higher level code in the evaluator. Today we will begin with one possible way of representing a frame. It is not the way used in sicp but it is fairly straight-forward.
For now, a binding is a dotted pair so (cat . 4) is an example of a binding. The variable cat is bound to the value 4. Make a binding by evaluating: (define mybind (cons 'cat 4)) You can check it: >mybind (cat . 4) Now define binding-variable and binding-value and test them: ;;; given a binding returns the variable bound (define (binding-variable binding) (car binding)) ;;; given a binding returns the value bound (define (binding-value binding) (cdr binding)) For example: > mybind (cat . 4) > (binding-variable mybind) cat > (binding-value mybind) 4 Now define set-binding-value! ;;; given a binding changes the value-part to the parameter value ;;; and returns the new binding pair (define (set-binding-value! binding value) (set-cdr! binding value)) test it: mybind (cat . 4) (set-binding-value! mybind 755) mybind ;;;cat is now bound to new value (cat . 755) The procedure make-binding gives us an mnemonic procedure to make a binding. Define it now: (define (make-binding variable value) (cons variable value)) and then evaluate: (make-binding 'x 17). For now a frame will be alist of bindings. So we can make a frame by evaluating: (define myframe (list (make-binding 'x 17) (make-binding 'cat 10) (make-binding 'p 3))) Once we have a frame, we can seek a binding by using binding-in-frame. Define (define myframe (list (make-binding 'x 17) (make-binding 'cat 10) (make-binding 'p 3))) (define no-binding '()) ;;;this assq is like a system primitive but this one returns ;;; '() if there is no match (define (assq key bindings) (cond ((null? bindings) no-binding) ((eq? key (binding-variable (car bindings))) (car bindings)) (else (assq key (cdr bindings))))) ;;;Given the frame specified by the last parameter, binding-in-frame ;;; returns the binding for the variable var in frame if var is ;;; bound there. Otherwise returns '() = no-binding. (define (binding-in-frame var frame) (assq var frame)) then try the following: > myframe ((x . 17) (cat . 10) (p . 3)) > (binding-in-frame 'cat myframe) (cat . 10) > (binding-value (binding-in-frame 'cat myframe)) 10 So, let's write a small evaluator. This will only work for quoted expressions written with the quote spelled out, eg. (quote (a 3 )) not '(a 3), or simple variable names. Define: (define (found-binding? b) (not (eq? b no-binding))) ;;; the following are not quite what we are after but they are a ;;;start ;;;returns the value of variable var in frame (define (lookup-variable-value var frame) (let ((b (binding-in-frame var frame))) (if (found-binding? b) (binding-value b) (error "Unbound variable" var)))) (define atom? (lambda (x) (not (pair? x)))) ;;;returns #t if exp is a quote expression; returns #f otherwise (define (quoted? exp) (if (atom? exp) #f (eq? (car exp) 'quote))) ;;; if exp is a quoted expression, returns its value (define (text-of-quotation exp) (cadr exp)) ;;; returns #t if exp is a simple variable name; returns #f otherwise (define (variable? exp) (symbol? exp)) Think about what they do as you define them. You may want to try them each.
Now define mini-eval. ;;; a really mini-mini eval. evaluates quoted expressions and ;;; simple variables only in one frame. The expression is ;;; parameter exp and the frame is parameter env. (define (mini-eval exp env) (cond ((quoted? exp) (text-of-quotation exp)) ((variable? exp) (lookup-variable-value exp env)) (else (error "unknown expression--mini-eval" exp)))) Try it out. For example try: > myframe ((x . 17) (cat . 10) (p . 3)) > (mini-eval 'cat myframe) 10 > (mini-eval '(quote (a b c)) myframe) (a b c) > (mini-eval 'p myframe) 3 > (mini-eval '(car x) myframe) unknown expression--mini-eval (car x) > Let's review where we are. A binding is a dotted pair so (cat . 4) is an example of a binding. We have defined functions to construct and access bindings (make-binding, binding-variable, binding-value).

A frame is a list of bindings. Once we have a frame, we can access it by using the functions: binding-in-frame, found-binding?, lookup-variable-value. In order to define a really small evaluator, we introduced: quoted?, text-of-quotation, variable?, then we wrote a mini-evaluator.

Important note: eval and apply are built in Scheme primitives. In order not to clash with them, I will use mini-eval wherever the text uses bare eval and I will use mini-apply where the text uses bare apply.

Even though our evaluator is not much (yet), we would like to put the user into a world where she uses our environment and our evaluator. This is essentially a read-eval-print loop which is like the larger world that drscheme provides for us. So evaluate the following definitions for the-global-environment and driver-loop.

;;; The driver loop reads an expression, evaluates it in the global ;;; environment, and prints the result. Note that the driver ;;; uses a prompt of "MC-EVAL==> " to help you avoid confusing typing to the ;;; metacircular evaluator with typing to the underlying SCHEME interpreter. ;;; (Also, we have called our evaluator procedures MINI-EVAL and MINI-APPLY ;;; to help you avoid confusing them with Scheme's EVAL and APPLY.) ;;; When/If your interaction with the evaluator bombs out in an error, ;;; you should restart it by calling DRIVER-LOOP again. ;;; make the global environment our little frame for now (define the-global-environment myframe) (define (driver-loop) (newline) (display "MC-EVAL==> ") (let ((input (read))) (if (equal? input '(quit)) "exiting-mini-eval" (begin (display (mini-eval input ;;;;change display to user-print later the-global-environment)) (driver-loop))))) Recall that myframe is ((x . 17) (cat . 10) (p . 3)). Now try our mini-micro Scheme interpreter. You type the bold face stuff.

: (driver-loop)

MC-EVAL==> x
17
MC-EVAL==> cat
10
MC-EVAL==> p
3
MC-EVAL==> (quote (hell0 there))
(hell0 there)
MC-EVAL==> (quit)
"exiting-mini-eval"

If you haven't saved anything yet, now would be a good time to save this stuff in a week10 subdirectory. I called my code so far: neval1.scm.

What we have here is a mini-micro Scheme interpreter. Once the user types (driver-loop), he is in our world. Our interpreter evaluates whatever expressions are typed by the user until the user quits (or bombs out by typing something our interpreter cannot handle). We have a lot of work to do to turn this into a reasonable interpreter, but this is a start. Make sure you understand how this little interpreter works and ask for help if you need it.

In order to have a really functional interpreter, we need to add a lot. Users should be able to define their own variables and give them values. We should provide some primitive operations that users can use. Users should be able to define their own functions and invoke them.

We will begin by working on the environment handling functions so that users can define their own variables inside our interpreter. Since we know that eventually we will want to work with environments that consist of more than one frame, we will define environment functions that allow for such complex environments.