7.3.7 B:   Lazy
On this page:
7.3.7.1 Interpreter
7.3.7.2 Macros
7.3.7.2.1 Naming Logistics
7.3.7.2.2 First Macro Implementation
7.3.7.2.3 Second Macro Implementation:   With Caching
7.3.7.3 Stencil Code
7.3.7.4 Submission
7.3.7 B: Lazy

In a lazy language, arguments are not evaluated at the time a function is called; rather, they are only evaluated when certain parts of the language (called strictness points) force an expression to have a value. Typical strictness points are the test position of a conditional (to decide which branch to take), arithmetic operators (so they can perform the primitive arithmetic operations), and—in an interactive environment—the top level of a REPL (so it can show an answer).

In this assignment, the following will have strictness points: +, -, *, /, string-append, equal?, is-empty?, first, rest, if, and, or. Note that while the others are strict in all their arguments, the last three are strict only in the first sub-expression.

In this assignment, you will implement lazy evaluation in multiple ways.

7.3.7.1 Interpreter

We will join two assignments: the interpreter of C: Interpreter and the extended language of C: Type Checker. That is, you will create a lazy interpreter for the language for which you wrote the type-checker.

You may need to augment your previous definitions. In particular, you now have another kind of value: a lazy computation.

7.3.7.2 Macros

You will now implement this again using macros. Except this time you will go one step up. So far, you’ve been able to define and use macros in the same file (or module). Now this doesn’t make as much sense. Your macros are written in racket, but Racket has an eager semantics. Really, you want to define a lazy language, and write your programs in that language. In other words, you would like to effectively implement #lang lazy, just like the various languages you’ve used in the Mystery Languages assignments.Be careful: Racket already provides a built-in #lang lazy that implements lazy evaluation. Do play with it, but don’t use it to solve the assignment!

7.3.7.2.1 Naming Logistics

To avoid name-confusion, we will call your language “My Lazy” instead.

There are a few extra steps you need to make a full-fledged #lang my-lazy. If you’re interested, several resources will tell you how: in addition to the official documentation (which you may find somewhat hard going for a beginner), there are several handy guides like F*dging up a Racket, Beautiful Racket,We have paid for Beautiful Racket at the Educator level, so you can use the book without paying. and Realm of Racket (the chapter “Good-Bye: Close Paren”). The example in F*dging is fun, but the code is no longer up-to-date. We therefore especially recommend Beautiful Racket.

But since the point of this assignment (and course) is not the intricacies of Racket, we will adopt a slightly simpler solution: you will instead create a my-lazy.rkt module (described below) to define a lazy language, and write
#lang s-exp "my-lazy.rkt"
 
<your code goes here>
to use it. This is effectively the same as #lang my-lazy but much easier to define.

7.3.7.2.2 First Macro Implementation

Implement a module, my-lazy.rkt, that provides at least the constructs your interpreter provides, with the same strictness policy.

You should also provide a function, !, that enforces strictness. This can be useful for writing sample programs.

Finally, you need to override the way function application works, to enforce laziness. Racket provides a very convenient way to do this: the #%app macro. Every application in a regular program—e.g., (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 behavior of that module itself. Rather, you will want to use the rename-out construct in Racket to export a local macro as the #%app macro of the client module.

Finally, save a file (say test.rkt) in the same directory, and put #lang s-exp "my-lazy.rkt" at the top (or, if it’s in a different directory, adjust the pathname accordingly). This file should now behave according to lazy evaluation.

7.3.7.2.3 Second Macro Implementation: With Caching

A lazy language must necessarily not have side-effects.Why not? 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 you do this, you can sometimes see a change (even a dramatic change) in performance. Implement this as my-lazy-cached.rkt. Write a cached-test.rkt that has code that exercises this feature.

Hint: think about implementing the Fibonacci sequence as a stream. If it’s not clear after you’ve thought about it for a while, see here.

7.3.7.3 Stencil Code
7.3.7.4 Submission

Form