7 Lazy
7.1 Introduction
For this assignment, you will implement a modified version of Paret (called Lazy Paret) that uses call-by-need (i.e. lazy) evaluation and to support pairs.
Lazy programming is an idea from the 1970s and 1980s that is finally making it into mainstream programming, e.g., through Java 8’s streams.
7.2 Readings
7.2.1 Directly Useful for the Assignment
To understand laziness from a desugaring perspective, read the DCIC section about streams, which also shows how they can be encoded in an eager language.
7.2.2 Optional Reading
However, streams are only a small example of what we can do with laziness. To see more examples, and understand the beautiful programming patterns that laziness enables, read this classic paper by John Hughes (not Brown’s Spike), entitled
Why Functional Programming Matters.
7.3 Features to Implement
7.3.1 Pairs
You will add pairs to the language:
(pair f s) constructs a pair with two elements, f and s.
(first p) gets the first element of a pair p.
(second p) gets the second element of a pair p.
(is-pair v) evaluates to true if v evaluates to a pair; otherwise, it evaluates to false.
Pairs in Lazy Paret are not type homogeneous; that is, both elements of a pair do not have to be the same type.
7.3.2 Lazy Evaluation
Lazy evaluation means that arguments to functions should not be evaluated if they are not used in the body. As a result, function calls and the pair constructor must be lazy: that is, a function must not evaluate its argument if it is not used, and a pair must not evaluate its parts if they are not used. let’s value should also be lazy.
7.3.2.1 Strictness Points
On the other hand, certain parts of the language should force their arguments to be evaluated. These strictness points should force an expression to have a value. Specifically:
The operators +, ++, num=, str=, and is-pair should force all of their arguments to be evaluated.
if should force its condition to be evaluated as well as the target branch of the conditional (that is, if the condition evaluates to true, then the consq branch should be forced, and if the condition evaluates to false, then the altern branch should be forced).
first and second should force the accessed element of the pair to be evaluated.
Identifier resolution should force the referenced identifier to be evaluated.
The top-level should force its result to be evaluated (so it can show the end-user an answer).
All forced evaluations should be shallow; that is, you should not recursively force values inside of a concrete value. In particular, you should not recursively force values inside of pairs.
7.3.3 Desugaring Simplification
For simplicity, the and and or sugar forms have been removed from the language; however, your language still needs to handle the let form.
7.4 Assignment
You will now implement the lazy Paret language using Racket macros to define your own lazy #lang. You will also implement a caching mechanism to improve performance.
7.4.1 Implementing a #lang
In previous assignments, we have defined and used macros in the same file. However, macros are written in #lang racket, and Racket has an eager semantics. Instead, we want to define a lazy #lang and write our programs in that #lang.
To avoid name-confusion with the already existing #lang lazy, we will call your language my-lazy instead. Creating a fully-fledged #lang my-lazy requires some knowledge of Racket intricacies that are outside the scope of the course, so we will adopt a simpler solution.
You will instead create a my-lazy.rkt module (described below) to define a lazy language. Then, you can use this language in a new file by writing:
#lang s-exp "my-lazy.rkt" |
|
<your code goes here> |
7.4.2 Macro Particulars
In addition to providing the constructs defined in the Paret specification above, you need to override the way function application works to enforce laziness. Racket provides a convenient way to do this: the #%app macro. Every application in a regular program—for example, (f x)—is actually an invocation of the #%app macro: it’s really (#%app f x). The default #%app macro in Racket enforces eager evaluation. Your job is to define an #%app macro that enforces lazy evaluation (which can rely on eager evaluation underneath).
Doing this requires a little care. If you override #%app in my-lazy.rkt, you will end up changing the function application behavior within the module itself. Instead, we will use the rename-out construct in Racket to export a local macro as the #%app macro for our client program:
(provide (rename-out [lazy-app #%app])) ; overrides #%app with lazy-app |
|
(define-syntax (lazy-app fun arg ...) ; implementation of lazy application |
; TODO: Implement me! |
....) |
The stencil uses this pattern to maintain the normal behavior of various other Racket constructs that would be helpful in your macro implementation, but that we ultimately want to override in the client program.
7.4.3 Alternative to Forcing the Top-Level
While
Strictness Points states that we should ensure that our language forces at the top-level, implementing this exact behavior requires some knowledge of Racket internals that are distracting for our purposes. In other words, it is not easy for us to modify the Racket interpreter to enforce top-level strictness for our lazy macros.
Instead, your implementation should provide a ! construct that enforces strictness for a given expression:
! should perform shallow evaluation; that is, you should not recursively force values inside of a concrete value. However, if ! forces a suspended computation and gets back another suspended computation, the expression isn’t fully forced, and ! will need to recur.
We will use
! to simulate top-level strictness when we run tests against your implementation by wrapping the top-most expression with
(! ...), so as long as you implement
! correctly, your implementation of Lazy Paret does not have to handle top-level strictness in any special way. However, your implementation must enforce the remaining parts of the
Strictness Points specification.
7.4.4 Representing Computations in Racket
We’ve included a Computation type using Racket structs:
(struct computation ()) |
(struct computation/suspend computation (body)) |
(struct computation/value computation (value)) |
To implement lazy evaluation properly, you should use the
computation/suspend struct to store non-evaluated expressions as thunks.
computation/suspend struct does not have an “environment” parameter, since
#lang racket will automatically provide proper identifier binding and lookup to your thunks. The
computation/value variant is explained further
Caching):
You can use Racket’s
thunk form to easily create nullary functions (that is, functions of zero arguments) for the purpose of suspending computations.
7.4.5 Caching
A lazy language must necessarily not have side-effects. Therefore, there is no need to re-evaluate any lazy expression: it suffices to evaluate it once and then cache its value, trading space for time.
When a computation is forced, its result should be cached so it doesn’t have to be computed a second time. We have provided the ref-comp struct for this purpose:
(struct ref-comp (comp) #:mutable #:transparent) |
As mentioned above in
Representing Computations in Racket, the
computation struct has a
computation/value variant, which represents an
evaluated computation. When arguments to functions are thunked, they should be stored in a
ref-comp via a
computation/suspend. If that argument needs to be evaluated (due to forcing), your implementation should evaluate the
body stored in the
computation/suspend, then update the
ref-comp with a
computation/value containing the computed value of that expression.
By marking the ref-comp struct as #:mutable, Racket automatically defines a set-ref-comp-comp! function that will allow you to update the ref-comp’s comp field in-place. You should use this to update a ref-comp after computing its value for the first time.
As a hint, your ! function will likely need to do different things based on whether or not the input ref-comp is of type computation/suspend or computation/value:
| #lang racket |
| (define (! rc) |
| (match rc |
| [(ref-comp comp) |
| (match comp |
| ; A computation/suspend is a non-evaluated computation. |
| [(computation/suspend body) |
| ; TODO: Evaluate the body to a value v, then update the ref-comp in-place |
| ; with (set-ref-comp-comp! rc (computation/value v)). |
| ....] |
| ; A computation/value is a computation that has been previously evaluated. |
| [(computation/value value) |
| ....])] |
| ; The case when the input is not a ref-comp |
| [else ...])) |
7.4.6 Variable Arity
Certain operators in Racket are variable arity procedures. We’d like to emulate this in our Lazy Paret macros. Specifically, if at least two arguments are supplied to the + and ++ operators, the operator should be applied pairwise from left-to-right across the arguments and the final result of those applications should be returned. (Raise an error if less than two arguments are supplied to those operators.)
Additionally, your implementation should also extend the lam and let forms to support a variable number of arguments and bindings.
The strictness point specification from
Lazy Evaluation still applies to all of these updated forms.
It’s worth observing that, in Racket, some operators (such as + and ++) are defined as functions (and not macros), which allows the operators themselves to be passed as arguments to other functions. However, for simplicity, we do not require you to implement the operators as functions in your Lazy Paret macro. The main requirement for your operators is that they support the macros grammar, given below.
7.4.7 define
Finally, your language should provide the define form from Racket, which will allow you to create named functions (and other bindings) in your test programs. The stencil code already provides define for you, which should be sufficient for the purposes of your implementation.
7.4.7.1 Error Handling
Your Lazy Paret macro should raise and handle all of the error cases from
Interpreter plus the addition of the following two error cases:
If the argument to first or second is not a pair, you should raise an error.
If the number of arguments supplied to a function does not match with the number of arguments in the function definition, you should raise an arity mismatch error.
However, the priority order and handling of error cases in your implementation is undefined, and you can assume that we will not test your implementation on any error cases.
7.4.8 Macros Grammar
The Lazy Paret grammar is as follows:
<file> ::= <form> ... |
<form> ::= <define-statement> |
| <expr> |
|
<un-op> ::= first | second | is-pair | ! |
<bin-op> ::= num= | str= | pair |
<extended-op> ::= + | ++ |
|
<expr> ::= <num> |
| <string> |
| <id> |
| true |
| false |
| (if <expr> <expr> <expr>) |
|
| (<bin-op> <expr> <expr>) |
| (<un-op> <expr>) |
| (<extended-op> <expr> <expr> ...+) |
|
| (lam (<id> ...) <expr>) |
| (let ([<id> <expr>] ...) <expr>) |
| (<expr> ...+) |
where
<define-statement> follows the grammar for Racket
defines.
7.4.9 Testing Your Macros
To test your program, save a file (say, test.rkt) in the same directory, and put #lang s-exp "my-lazy.rkt" at the top. Once you’ve implemented your lazy language, the code in the test.rkt file should now follow lazy Paret semantics.
You should aim to write test code that exercises your caching feature to ensure it works. When you do this (and it works correctly), you may see a potentially dramatic change in performance.
7.4.10 Starter Code
We’ve set up a GitHub Classroom assignment that contains all necessary stencil code and support code
here.
We’ve provided starter code for your macro implementation at my-lazy.rkt. This includes template macro definitions for Paret’s syntax forms as well as the computation struct and new ref-comp struct.
There are no wheats and chaffs for this assignment, and you do not need to submit a separate test suite.
7.5 Analysis
You should also concisely answer the following questions:
In the Caching section, we say “A lazy language must necessarily not have side-effects.” Explain why.
Instead of using ref-comps, we could implement applications using a global hash table that maps the quoted version of computed expressions to their result. For instance, when we compute an expression (+ 1 2), we could map ’(+ 1 2) to the value 3. If we compute (+ 1 2) again, we check if the cache contains a mapping for ’(+ 1 2), and if so, return the stored value. The main advantage with this strategy over the ref-comp approach is that if an expression is passed as an argument in multiple places in the program, our cache only has to maintain one reference to that expression instead of multiple ref-comps. Does this caching strategy work? If so, explain why. If not, provide a counter-example.
Provide an example of a program that runs in your macros implementation that demonstrates the Caching power of your macros implementation. (Specifically, your submitted program for this question should run significantly slower if your macros implementation had not implemented caching.)
7.6 What To Hand In
You will submit the following files for this assignment:
my-lazy.rkt, which should be uploaded to the “Lazy - Macros (Code)” drop on Gradescope.
Submit your answers to the Analysis questions to the “Analysis” drop on Gradescope.
You will need to upload your answer to Question 3 as a .rkt file.
You can update your submissions as many times as you want before the deadline.