Get SICP’s lazy lisp interpreter running and run the following program in lazy-lisp; include the results as a comment.
(define count 0)
(define (id x) (set! count (+ count 1)) x)
(define z (id (id5)))
(display count)
(newline)
(display z)
(newline)
(display count)
(newline)
(display z)
(newline)
(display count)
(newline)
Lazy Evaluation(pick at least one)
Exercise 4.29[bronze]
Exhibit a program that you would expect to run much more slowly without memoization than with memoization. Provide an analysis that shows the difference. #lang sicp.
Exercise 4.29[silver]
Exhibit a program that you would expect to run much more slowly without memoization than with memoization. Provide an analysis that shows the difference. Note: the book’s second version of force-it uses set-car and set-cdr which racket disallows so you’ll have to modify the second force-it to work in #lang racket.
Exercise 4.31[silver]
The approach taken in this section is somewhat unpleasant, because it makes an incompatible change to Scheme. It might be nicer to implement lazy evaluation as an upward-compatible extension, that is, so that ordinary Scheme programs will work as before. We can do this by extending the syntax of procedure declarations to let the user control whether or not arguments are to be delayed. While we’re at it, we may as well also give the user the choice between delaying with and without memoization. For example, the definition
(define (f a (b lazy) c (d lazy-memo))
...)
would define f to be a procedure of four arguments, where the first and third arguments are evaluated when the procedure is called, the second argument is delayed, and the fourth argument is both delayed and memoized. Thus, ordinary procedure definitions will produce the same behavior as ordinary Scheme, while adding the lazy-memo declaration to each parameter of every compound procedure will produce the behavior of the lazy evaluator defined in this section. Design and implement the changes required to produce such an extension to Scheme. You will have to implement new syntax procedures to handle the new syntax for define. You must also arrange for eval or apply to determine when arguments are to be delayed, and to force or delay arguments accordingly, and you must arrange for forcing to memoize or not, as appropriate.
Exercise 4.33[silver]
Ben Bitdiddle tests the lazy list implementation given above by evaluating the expression
(car '(a b c))
To his surprise, this produces an error. After some thought, he realizes that the“lists” obtained by reading in quoted expressions are different from the lists manipulated by the new definitions of cons, car, and cdr. Modify the evaluator’s treatment of quoted expressions so that quoted lists typed at the driver loop will produce true lazy lists.
Reservoir Sampling[gold]
Create a program that uses laziness and streams to perform online reservoir sampling. Imagine you want to select an item at random from a potentially infinite collection of items(or maybe the size of the collection is unknown), reservoir sampling let’s you do this. You can find a python solution to this here.
By November 14th at midnight, submit via google classroom a zip file that expands into a folder with the following files:
cmsc305-lab6-lastname-firstname
lab6warmup.scm
lab6.scm
Remember the scheme file should include your name, email, date, assignment description and collaboration statement. Bring a hard-copy of your programs to the following lab period. Be prepared to run your program and demonstrate your“Theory of the Program.”
Warm-Up
(define count 0)(define (id x) (set! count (+ count 1)) x)(define z (id (id 5)))(display count)(newline)(display z)(newline)(display count)(newline)(display z)(newline)(display count)(newline)Lazy Evaluation (pick at least one)
Exercise 4.29 [bronze]
Exercise 4.29 [silver]
Exercise 4.31 [silver]
(define (f a (b lazy) c (d lazy-memo)) ...)Exercise 4.33 [silver]
(car '(a b c))Reservoir Sampling [gold]
Learning Goals
Tips
Submission Guidelines
cmsc305-lab6-lastname-firstname lab6warmup.scm lab6.scm