AdministrativeThis exam was given in the Fall semester of 2016. 

One of the major ways in which Racket diverged from other Scheme
implementations was when lists (and cons cells in general) were made
immutable. In other Schemes there are two operations for mutating
pairs: setcar!
and setcdr!
, which change what the car
part (or
first
) and the cdr
part (or rest
) point to. Note that setcar!
and setcdr!
return a void result (i.e., their output type is Void
).
Note also that in a world where cons is used only for lists, setcdr!
should be used with a list, otherwise the pair that it sets becomes
something that is not a proper list.
Using these, a number of popular “destructive” utilities can be
implemented, usually with the idea of reducing memory use, both overall,
and the amount of work the garbage collector has to do. For example,
consider this variant of map
:
This can be used in cases when we know that the input list is no longer
needed, so we mutate it into the output list. Note, however, that
calling this map!
function is done in a different way than map
,
which can be seen in its type: this version would return a Void
.
To fix this, we can rewrite map!
so the above is an internal helper
function — fill in the missing part in the following (write only the
missing part):
What would be a good type declaration for this fixed version of map!
?
(: map! : (All (A B) (A > B) (Listof A) > (Listof B)))
(: map! : (All (A B) (A > B) (Listof A) > (Listof (U A B))))
(: map! : (All (A) (A > Any) (Listof A) > (Listof Any)))
(: map! : (All (A) (A > A) (Listof A) > (Listof A)))
(: map! : (Any > Any) (Listof Any) > (Listof Any))
(: map! : (All (A) (A > Void) (Listof A) > Void))
Another common destructive utility is reverse!
which reverses a list
“inplace”. The idea is to flip the cdr
pointers back as we make our
way down the list. This can also be done with a local helper function.
Complete the following definition (write only the helper definition, no
need for types):
Note that this function changes the structure of the list rather than
its contents, so you should use setcdr!
. Another hint: you will
probably need either a let
or a begin
.
The reason that the Racket implementors decided to make pairs immutable can be demonstrated by a nasty surprise that results from uses of this kind of mutation. To do this, assume that the following expressions are entered at the REPL, and write the printed values of the last two expressions:
As we have seen, there are cases where dynamic scoping is useful, in
particular for creating “dynamically customizeable bindings”. We
mentioned the fact that Racket implements this via parameters. Before
such a solution was popular, an approximate hack that was used was a
form called fluidlet
. The idea is that when
is evaluated, the following happens:
The existing global value of x
is saved,
E1
is evaluated and assigned (using the set!
form that we
mentioned in class a few times) to x
(note that this is the global
x
, no new binding is created),
E2
is evaluated now (when x
’s value is the new one set above),
The original global value of x
is restored (by set!
ing it again
into x
),
The result of evaluating E2
is returned.
All of this can be implemented via a macro. Here is an interactive example of using this macro:
Implement fluidlet
as a macro. For simplicity, make it a macro that
handles exactly one “dynamic” binding, no more, and no less.
An interesting puzzle is how to continue the following sequence:
This is a selfreferential sequence: if you read the numbers in pairs, you’ll see that this sequence starts with 1, 1 and continues with a description of itself (as a runlength encoding). (This is described in more details in this page of the OIES.)
You need to implement this infinite list in our #lang pl lazy
language. Given your implementation, we should be able to define the
list with:
and get it to be the solution sequence:
You need to implement this: fill in the missing part in the above
definition, as well as any utillity function you need to make. Very
thick and definitely nonsubtle hint: look at the midterm solution for
the first question (but don’t copy it blindly). [Another thick hint:
since we build the description from the first 1,1, but we included the
following 2,1, you will need a restofrest there too, or the cddr
function.]
Note that the definition of puzzle
starts with the first four
elements instead of just the first two. Why is that? In other words,
what would we get if we started with just the first two values of 1,1
?
(A short answer for this!)
In this question we will extend the type system that we have seen in class so that in addition to the “kind of resulting value” property that we dealt with, it will also keep track of sideeffects. First, we will do that for the language definition — we’ll use the Picky2 language for our work.
We start with the BNF which is extended with a set!
expression (just
so we have some sideeffects), and we also extend the type so there’s
an <STYPE>
that wraps the usual type with a Pure
or Impure
that
specify expressions that have no sideeffects, and expressions that do
respectively.
The idea is that a type in this extended language is either a
(Pure ...)
or an (Impure ...)
as an outer wrapper around the types
that we have used previously. The typing axioms and judgments should be
adjusted for this, for example, the two axioms about numerals and
identifiers will now specify a Pure
type (since there are no side
effects in either of them):
Continuing with the rule for smallerthan, to take a simple example, we get this, which is a bit tedious just because we use simple patternmatchinglike specification for these things:
To make a long story short, we’ll assume that all other rules are adjusted properly. You only need to do the following:
Define the type judgment for a set!
expression. To do this, you need
to know its semantics… For this extension, we’re going to say that to
evaluate a {set! x E}
expression, we evaluate E
, assign the result
to x
(mutate it), and return that result. (That is, the mainstream
feature where assignment as an expression returns the newly assigned
value.) Another thing that you need to know is that set!
cannot
change the type of an identifier.
Now you can write this rule (which might need several instances similar to how the smallerthan rule above has four “clauses”).
Now, for the code extension: first, the AST types are extended according to the BNF:
And assuming that everything else was done (ie, all of the TYPE
s were
converted to STYPE
s when needed etc), you need to write two pieces of
code from the typecheck*
function:
Write the branch that would typecheck a Set
expression:
To deal with the arithmetics, we’ll change the twonums
helper so it
also takes the type to return, so it’s used as follows:
You now need to change the definition of twonums
so that it does the
right thing based on the purity of the two expressions.
In the final exam that was given last semester, students had to
implement a CPS rule for converting if
expressions. Reminder: the
solution that was given is:
And a little shorter alternative:
One student had this incorrect answer:
This answer is incorrect in a way that is hard to see at first.
Describe what’s wrong with it. Note: this is not an essay question.
You answer should describe exactly how (if C T E)
gets evaluated with
this implmentation, which would explain what’s wrong with it.
As an example, the description of the correct implementation of if
above is: