This exam was given in the Spring semester of 2017.
The full Racket language has
for loops. The complete details of these
loops are not needed for this question, it is enough to know that
their general shape is
These loops are used only for their side-effects. (There are also other loop forms that can collect an output list of values and more, these are also not relevant for this question.)
Just to give a little more “taste” of how these things are used, here are two examples of looping over integers and over elements of a list:
We want to extend this with constructs that are common in C-like languages:
break: prematurely abort the loop
continue: abort the current body execution and start the next
iteration (if any)
We will do that via a new
forx macro. For example, the following
when is a one-sided conditional):
will print 1, 3, 5, 7, 9, 11.
The macro should be implemented using continuations. Here is a template for your definition:
We’re using the simple
define-syntax-rule, since there is no
need for multiple rewrite rules.
range will match the range clause, no matter what it contains, since
it is irrelevant. Similarly, we don’t care how the body looks like.
There is a problem here: as we discussed in class, these “high level
macros” are hygienic, which means that they cannot create a binding
that will be visible in code that uses the macro. For the purpose of
this question, ignore this problem, and assume that when you bind
continue in the macro, they will be visible in macro
let/cc is the most convenient way that we’ve seen to bind
the current continuation to some identifier. Examples from class:
In these examples the continuation is used with a single argument, which becomes the value that us returned to the continuation that we jump to. But if theis value is not used, we can just call the continuation without arguments. In our case, you can assume for simplicity that you can always call continuations with no arguments.
Implement the macro. (Note: it needs to expand into a
What would happen if we use value of
continue instead of
directly calling it?
It won’t work: we’ll get an error. Continuations have no “value” in
the same way that other macros like
define don’t have a
It will work, but it would be useless since the continuations will become invalid as soon as we exit the loop. This means that we can pass them around as values only to eventually call them only while the loop is running.
It will work, and calling them at any point – inlucding after the
loop is done – will jump to the same context. Using the value of
break after the loop will jump to the continuation of the loop
again, and using the
continue value will jump again into the loop.
Continuations are stack snapshots, or in other words, they’re just buffers holding data. It is therefore not possible to call them as functions.
The type system that we have discussed in class was very simple. We talked about its explict lack of overlapping types which simplifies things to the point that there is no choice for types. What if we extend the type system with a typed-racket-like union type?
Extending the picky type system with a
U type constructor would
require a few things. (Note that we’re talking about the type system
specification here, not the code implementation.) Add the following to
the Picky1 rules to get an extended system:
Add a new rule for introducing a union, as a result of a conditional
if expression where the two results are not restricted to have the
Scratch that – I’ll do it for you as an example:
We also need a subtyping rule, saying that if we want to prove that E
has some type t2, and we know that it has type
t1 which is a subtype
t2 (written as
t1 <: t2), then that proves that E has type t2
too. Since this is essentially the rule, I’ll do it for you also:
Note that the right goal is not a typechecking goal, it is rather a check on the actual types to verify that the first is a subtype of the second. We therefore need to specify the subtyping rules too. We’ll do that in plain logic terms (or rather pseudo-logic, to keep it less formal):
Specify the subtyping rules for
U – union types. Well, I can just as
well do this quick bit for you too:
This works as a specification of the subtype relation, together with a bunch of trivia that we won’t care about (like transitivity, reflexivity, etc).
What about function types? Aha! Finally something that I’ll leave for
you to do. This should describe the subtype relationship between two
function types, say
(t1a -> t2a) and
(t1b -> t2b). You need to
express the relationshiip between the two types in the form of some
implication, some logical rule like the one in (c) (except that this one
has some implication).
Finally, all of that is not too useful if we don’t have a flip side of
if rule – some way to use a union type. The way typed racket
does this is via “occurrence typing”, which is a rule about specific
uses of an
if conditional with a type-distinguishing predicate that
can identify members of a specific type. For example, the
predicate is true only for values that are
Numbers. This is described
by a rule that you need to complete:
Fill in the left goal specification for
E1. (Ignore the right
Why didn’t I ask you to fill in the right goal in the above rule?
It’s trivial: it would be completely symmetric to the left goal.
It’s easy: symmetric to the left goal except that
x is not a
number, and in our simple type system that means that
x must be a
It’s not needed, since if the predicate is false, then it doesn’t say anything on E2.
It’s more difficult since it requires also a notion of type subtraction which we didn’t define.
Consider the core
eval of our lazy Sloth language:
On review of this code, something looks fishy: we use
eval* as a way
to delay evaluations and get lazy semantics as a result – but how come
we didn’t convert all of the
eval calls to be lazy? (Note: we’re
eval* difference of an extra argument – focus
eval as plain evaluation and
eval* as wrapping it in an
So let’s review each of these calls.
Clearly, in (3) and (7) there is no difference between using delayed
evaluation or not, since the result is fed into
strict anyway (and we
eval* just because it was more convenient).
(2) and (4) are similar, due to the similarity of applying a function
and using a local binder (recall
call with an immediate
So let’s focus on just (2): is that lazy
eval* needed? If it is
needed, demonstrate the need by writing an expression that will evaluate
in a wrong way if it wasn’t lazy. If it’s not needed, explain why (in a
(1) and (5) are also similar, so consider only (1). How come it is
using the plain non-lazy
eval? Is this a bug? If so, demonstrate the
bug with an expression that is evaluated in a wrong way, and if it is
not a bug, explain why that particular evaluation doesn’t need to be
delayed (in a short-one-sentence comment).
Finally, what about (6)? It uses a delayed evaluation – is that needed? Again, if it is, demonstrate the need by writing an expression that will evaluate in a wrong way if it wasn’t lazy. If it’s not needed, explain why (in a short-one-sentence comment).
In the “Turbo Toy” homework (Homework #12) we have implemented an extension
to the Toy language that has by-reference
rfun functions. In
contrast, C achieves similar functionality via an alternative approach:
extend the language with a new kind of “reference” values which hold the
box that is the location of some variable.
This kind of an extension should be a familiar process: we’re taking some feature of our language that is currently second-class, and we promote it to a first class value that is accessible from inside the language. In the C case, this means exposing raw machine pointers; and in our case, we take the boxes that are used to store binding values and expose them. These boxes are currently available only in the extended Toy implementation – in Racket code. We will make them accessible inside the language, so they can be passed around and used as any other kind of values in Toy code.
To get a quick idea of how this extension will look like, here is a test that will eventually work:
As usual, we begin by extending the BNF,
the AST type definition,
and the parser is extended accordingly. We then extend the kind of TOY values with a new “reference” type:
And we now proceed to implement the new functionality: evaluating the new special form and a function that uses the new kind of values.
To evaluate the new special form, we need to have an additional case in
the body of the
eval function for a
Ref syntax, which should return
RefV value holding the appropriate box:
Fill in the missing code here.
Now that we have a working way to construct these values, we need to
implement a way to use them. We do this with a new
function, that can be used as:
to set the value referenced by
foo to the
bar value. However, we
need to implement it directly rather than construct it with
racket-func->prim-val. First, the binding is added with:
and now we need to implement it as
setref-function. We need to follow
the same calling protocol as for all primitive functions, meaning that
it should be a function from a list of
VAL inputs to a
and and this means that we need to check that we’re getting the right
number of input arguments. Finally, we also need to make sure that the
value that we receive is indeed a
Fill in the missing code.
(Hint: there are two expressions that are needed there. (But both are very short.))
Now comes an important part: users will often want features that make
their life easier, even when in the long run the potential for problems
is higher. In this case, your users want to be able to treat these
reference values (
RefV for you) as if they were not there. For
example, in the sample test code given above note that the mutation
x is used as a plain value too. To give our users the maximum
comfort (and maximize their chance of shooting their feet), we’re going
to implement this. First, we write a utility function that consumes
VAL, and if it happens to be a
RefV, it will dereference it,
otherwise it will return the value it received as-is:
Fill in the missing part. Note that this is again a very simple function.
Finally, we need to use this
deref-value in places where a value is
needed. The first such place is in the primitive function
application, in the function that
unwrap-rktv. This code:
needs the value held in
a – so we change it to:
There are three more places that need to use
run), find them. You only need to specify which
expressions need it, there’s no need to actually change the code.