This exam is intended for two hours. The question scores sum up to a total of 125 points, but it will be graded “out of a 100” so you can skip a question, a few pieces, or just shoot for a bonus.
Note about Typed Racket: unless told otherwise, make sure that you write proper type declarations for functions that you implement. Grading will not be strict about type declarations syntax, but we will be looking at them. Note that some given examples might be missing type annotations for brevity. This should not be a problem for understanding them.
Remember: the correct answers are short. Also, questions that ask for a verbal answer rather than code should still be answered correctly and based on facts (and they should also be short).
As we have seen in class, the configuration aspect of dynamic scoping can be a useful feature in itself. Often, this feature is mimicked using plain mutable values: the idea is to change the value when starting a dynamic scope, run some code, then restore the value.
In this question you need to do just that. Implement a
function that takes in a box, a new value for the box, and a thunk (a
nullary function that takes no argument).
with-box-value will then
proceed by doing exactly the above: set the box to the given value, run
the thunked code, restore the box, and return the result of the thunk.
To demonstrate it, here is a simple example as a test case:
In this example the
a-box is a global binding, but this would work
with local boxes too.
Make sure that you write a proper (polymorphic) type and purpose statement too. (You do not need to add tests…)
For each one of the following expressions, write a definition for
blank in Racket that makes the expression evaluate to
example, a correct answer for this expression:
If you think that it is impossible to write such a definition, explain
why this is the case. Remember: this is Racket, not Schlac or FLANG, or
any other language that we’ve seen. In other words, assume a language
#lang pl. More accurately, unless explicitly asked, assume a
#lang pl untyped — the language that doesn’t do any type checking
— so you do not need to write types. Also, assume NO MUTATION is
(Note: you’re doing the “filling-in” via a definition of
with some literal substitution.)
Do this for the following expressions.
In homework 2 we had a version of the AE language that had sequences of
expressions with a
set. One thing that some people asked
about was further restricting the syntax to make
get required, as a
way to avoid the ambiguity. To show that this is possible, start with
the simple AE syntax that we changed into a variant that allows a
and create a grammar for a new “AEg1” language that requires one
operation, not more, and not less. In other words, only a single
and it must be included. In your answer, it will be useful to refer to
<AE> as the original language, defined as:
Note: you can just use it, no need to copy this bit of a BNF, and
specifically, you should not modify it. Also, no mention of
this question — just ignore it.
A common approach for having an evaluation function in a language is to expose its own evaluation rather than re-implement the language in itself. In this question we will do just that.
First, we need to have a kind of values that we can use to represent
code, and strings are the usual obvious choice (at least in non-Lisp
circles). Assume a version of the environment-based FLANG
language that is extended to include string values.
That is, the
FLANG type definition becomes:
and we also need parsing,
and finally, evaluation:
Now to implement an eval, we need to further extend the FLANG AST:
Using this type definition, you need to implement two additional bits:
parse-sexpr function to parse
eval expressions into
Eval instances. (Please DO NOT copy the function, just write the
match case that is needed.)
And the meat of the implementation: the evaluation semantics. You need
to write the evaluation fragment that deals with
Since we’re simply exposing our own
eval, this fragment should be
relatively short. Note that we need to ensure that the given value is a
string — but since we need to do it just once, you should do it in
your evaluation fragment (similar to function values in the
rather than a helper function (in the style of
You need to write just the new case for
Eval, no need for the rest of
Just to show off what we get, here is a test case (note that the syntax
for string values in arguments to
string->sexpr uses single-quotes)
that shows how it works:
Even better, we demonstrate a nested use of
eval (to get a quote in a
string->sexpr string, we use two single quotes):
Usually, using a raw
eval function as we did in the previous question
is bad in that it can be slow since it essentially performs the complete
pipeline from code to execution at runtime. In other words, if we view
our parser as part of compilation of the language, then we are basically
compiling code dynamically, at runtime.
But there could be cases that could be “pre-compiled”: when the
evaluated string is known in advance. You need to implement such a
flatten-evals, which takes in a piece of syntax in our
extended language, and “flattens” out string literals in
expressions so there is no need for the
To make this more concrete, here are some simple test cases that show
what this function does (note that we’re using
parse in the expected
test result to make these tests more readable):
Remember to write a type and a purpose statement.
(You don’t need to worry about errors.)
To continue in an eval-themed spirit, we can show that we can implement a “universal lambda calculus evaluator” by using the same code that we had in class — we’ll use WAE to keep it simple. To implement this, we will use the “match-style” definitions which we’ve talked about in class.
To see the class text, open Lecture #13, and it’s about 25% down the text (look for “Another interesting way to implement…”).
To make it even shorter, we will not use a parser, and we’ll stick to
just addition expressions (and
Num will stand for the simple natural
numbers that we’ve used in class).
First, the translated type definition:
You need to fill-in the definition of the With constructor (note that it also uses a number for the bound id name):
Write just this definition, don’t copy the above.
Next is the subst function: we assume to have a
= function (such as
the one you have or will imlement in the homework):
Fill in just the
With case — the last
Finally, the evaluation function: again, fill in just the
Unless told otherwise, choose the best answer in each of the following questions. (Note that there could be several answers that are correct, but one should be the most accurate.)
eval implementation in question 4, is there any
practical benefit for exposing our own
eval rather than
re-implementing our own language?
No. In fact, the opposite is true: as we have seen several times, implementing the language instead of exposing features of the host language is a better explanation of how the language works.
No. In fact, the opposite is true, as clearly demonstrated by the
fact that our own language is something that we implemented ourselves
instead of using Racket’s
The two approaches would end up in an implementation of the same language and therefore the way to get there makes no difference.
Yes: beyond having no duplicated code we are also guaranteed to get
the same exact language on both levels. For example, if there is a
bug in our language implementation we want the same bug to happen in
eval so it is a faithful evaluator of the same exact
Yes: it avoids duplicating code. However, there is a problem that we
might inherit bugs from our own language into the one implemented by
Continuing with discussing our
eval implementation: how come our
eval function has two arguments, but the one inside the extended
FLANG has just one?
This is a trick question: they both have the exact same arguments.
This is only because our
eval is a Racket function, but in our
FLANG language it is not a binding but a fixed operator similar, in
the same way we implemented
- etc, all with a different arity
than Racket’s same-named functions.
env argument is not needed when we go one level down from
our language to the language implemented within our language.
What we did in this question is expose
eval to users, but we did
not expose the concept of “the runtime environment”. We could have
done that too, which would make the exposed
eval require two
arguments as well.
Still sticking with our Flang with
eval implementation, how would it
look like if we had chosen to extend the substitution-based evaluator
rather than the environment-based one? To make this more specific,
consider the test case that we’ve seen:
Would this test change?
No, it would still be a valid test, with the same result.
Yes, the result will be 111.
Yes, there is a problem with having
eval that makes it behave in a
similar way to dynamic scope, and if we extend the substitution-based
evaluator we don’t run into this problem — and we would get 111
instead of 112.
We will get an error since the string is an opaque value and by the
time we get to perform the evaluation the
y names are no
We would get an error as said above, except if we complicate the implementation to somehow perform substitutions in strings too, and then we would get 111.
In the Schlac question we’re using a language that is dynamically typed, why is it crucial that we stick with strict proper types for every bit of code that we write?
It is not needed to keep the types, it just makes it a little easier to explain the code.
Schlac has no errors at all, so any value can be used as any type, and if we make a mistake we get nonsensical results. We need the types to make sense.
Schlac has no errors at all, so any value can be used as any type, and if we make a mistake we get nonsensical results. We need to stick to known types in each of the constructors since we cannot tell types of values apart when working inside the language.
The dynamic typing of Schlac means that scope can get messed up. We need to have proper types to get proper lexical scoping.
It’s a low-level assembly-like language, it would be impossible to read and write such code unless we keep things very organized.