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
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.
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.
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!
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.
#lang s-exp "my-lazy.rkt" <your code goes here>
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—
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.
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.