9 Lazy

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.

Furthermore, to understand laziness from an interpreter perspective, see the Laziness chapter in PLAI 3/e.

9.2.2 Optional Reading🔗

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.

9.3 Assignment🔗

You will complete this assignment in the following steps:

Implement your lazy lang
Extend some functions to support variable arity
Implement a caching mechanism to improve performance

9.3.1 Part 1: Lazy Paret🔗

9.3.1.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 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"

9.3.1.2 Macro Particulars🔗

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:

#lang racket
(provide (rename-out [lazy-app #%app])) ; overrides #%app with lazy-app

(define-syntax (lazy-app ...)   ; 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.

Note that Racket uses different names for the primitive operators defined in the lazy grammar. In your macros, use string-append for ++, = for num=, and string=? for str=. You can search in Racket’s documentation for more details.

9.3.1.3 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.

9.3.1.4 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.

Recall that the body of a lambda is not evaluated when the lambda is defined, but rather when the lambda is applied. If we want to prevent an argument from being evaluated eagerly, we can simply wrap the argument in a lambda and apply the lambda later on. Your implementation should use Racket’s thunk form to easily create nullary functions (that is, functions of zero arguments) for the purpose of suspending computations.

9.3.1.5 Strictness Points🔗

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 +, ++, first, second, 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.
lazy-app should force the function to be evaluated.
The top-level should force its result to be evaluated (so it can show the end-user an answer).

To enforce strictness for a given expression, your implementation should call force-and-cache on that expression. For part 1, force-and-cache only wraps the ! operator (which should do all of the forcing). Implementing ! is the main goal of part 1, while implementing the and-cache piece of force-and-cache will come later in part 3.

#lang racket
(force-and-cache <expr>)

We will use force-and-cache to simulate top-level strictness when we run tests against your implementation by wrapping the top-most expression with (force-and-cache ...), so as long as you implement force-and-cache 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.

9.3.1.6 Nested Suspension🔗

! should perform shallow evaluation; that is, you should not recursively force values inside of a concrete value. In particular, you should not recursively force values inside of pairs. However, if ! forces a suspended computation and gets back another suspended computation, the expression isn’t fully forced, and ! will need to recur.

You might be wondering how to tell if a value is another suspended computation. After all, a thunk expression is just a lambda. The solution is to add a new type, computation-suspend, that wraps the thunk expression. If the type of an evaluated expression is still a computation-suspend, then the value is still a suspended computation. The computation-suspend struct does not have an “environment” parameter since #lang racket will automatically provide proper identifier binding and lookup to your thunks.

9.3.1.7 Testing🔗

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.

The stencil code provides the define form from Racket, which will allow you to create named functions (and other bindings) in your test programs.

9.3.2 Part 2: 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.

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.

9.3.2.1 Testing🔗

Expand your test suite to include instances of variable arity.

9.3.3 Part 3: 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. It’s time to implement the and-cache piece of force-and-cache to cache expressions after evaluation.

To cache expressions, we need to introduce a new, mutable wrapper that can contain either a computation-suspend or an evaluated expression. For this use-case, Racket provides a helpful datatype, box.

9.3.3.1 How to Use Boxes🔗

A box is like a single element vector, normally used as minimal mutable storage.

The basic syntax for creating a box type is:

#lang racket
(box <value>)

Now, you should wrap your (computation-suspend (thunk ...)) expressions with a box.

Once you have a box defined, you can access the contents through unbox. For example:

#lang racket
(unbox (box "hello")) ; "hello"

You can update the box’s field in-place using (set-box! <box> <value>).

For more information about boxes, see the documentation.

9.3.3.2 Force and Cache🔗

Your implementation should now extend force-and-cache to not just force expressions, but cache them after evaluation.

#lang racket
(define (force-and-cache b)
  (match b
    [(box comp)
     ; TODO: Force the computation and store the result in b
     ...]
    [else ...]))

9.3.3.3 Testing🔗

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 should see a dramatic change in performance.

9.4 Macros Grammar🔗

The Lazy Paret grammar is as follows:

<file> ::= <form> ...

| <expr>

<un-op> ::= first | second | is-pair | force-and-cache

<bin-op> ::= num= | str= | pair

<extended-op> ::= + | ++

| <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 and is already provided for you.

9.4.1 Starter Code🔗

GitHub Classroom

We’ve provided starter code for your macro implementation at my-lazy.rkt.

There are no chaffs for this assignment, and you do not need to submit a separate test suite. You can assume we will not test your implementation on any error cases.

9.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 boxs, 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 box 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 boxs. 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.) Provide an explanation for why your program is more performant using caching.

9.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.

contents ← prev up next →

	Syllabus and Course Policies
	Assignments
	Exams
	Diversity and Professionalism
	Staff
	Capstone
	Credits

	SMo L
	Stacker
	Mystery Languages
	Implementation
	Analysis

1	Testing Guidelines
2	Interpreter
3	Desugar
4	Macros
5	OMac
6	Type Checker
7	SMo LTalk
8	Type Checking and Interpretation
9	Lazy
10	From Assertions to Security

9.1	Introduction
9.2	Readings
9.3	Assignment
9.4	Macros Grammar
9.5	Analysis
9.6	What To Hand In