This is a sample midterm that was given in the 2017 spring semester.
In this question we’ll be dealing with “signal functions”: functions that read some value in the real world, and monitor it as it changes. An example of such a function can be a fuel-level reading function, that is used to display the level in your car’s dashboard.
The problem is that if we make the display show the result of calling the function periodically, the display is most likely going to constantly change as the gauge goes up and down when the car moves. One way to deal with this is to use a moving average: instead of using the actual readings as they come in, we use the average of the current measurement and the previous result (which is also such an average, etc).
We will start by implementing some simulation functionality for testing.
function->sequence function that takes a unary function and
produces a signal function with values that are results of successive
applications of this function starting from a given initial value. This
function is implemented for you:
To test it, we implement a quick
and here are some tests:
The only thing missing is the type for this
function and the
n-values utility, fill them in. (Write just the two
type declaration lines, no need to copy the body.) Note that these
functions should be polymorphic.
list->signal simulation function. This should take in two
To clarify, here are two tests:
Note that the values of successive calls to the simulation function
returns values from a list of values, where each cycle is taken from a
list determined by the
next function. The implementation of this is a
generalization of the
random-bag function from sample midterm #3, but
instead of always using
shuffle, we’re using the given
over the list of values. Furthermore, instead of maintaining an
additional state for the list of value, we use the above
Fill in the missing type declaration and the missing line in the body. (Again, this function should be polymorphic.)
Finally, you can now implement the moving average functionality, an
averager function. Here you need to provide both the type and the
implementation. Here is a test that demonstrates it:
(list->signal '(1 2) identity) function returns
on its first call, then
2, etc. The
function initializes its internal state to the first call —
the resulting moving-average function is called, it will invoke the
signal function again, getting
2, and returning the average of
the previous state of
1, resulting in
1.5. On a second call, the
signal function returns
1, which is averaged with
1.5, resulting in
1.25. We then get the average of the next signal value of
1.25, resulting in
(Note that this unlike the previous ones, this function cannot be polymorphic.)
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.
Write a BNF grammar for a limited variant of the FLANG. The idea is
restricting it so that
fun expressions are only called immediately,
but we want to still allow curried calls. We therefore allow
expressions in only two places: either the first sub-expression in a
call, or as the immediate body expression of a
fun. Here is an
example for demonstration:
(Ideally we would also enforce a kind of a curried arity check so the
above would be valid, but not if there was another nested
fun or if
there was one less
fun — but this cannot be done in a BNF grammer.)
Begin with a copy of the FLANG BNF, and modify it accordingly to the above.
We will now implement the restricted language properly: implement a
syntactic predicated called
valid? which determines when the input
expression is valid in that:
fun expressions are allowed only in the first argument subexpression
call or as the nested body expression of such a
In fact, the first subexpression argument of
call must be a
(or a nested
Even more: the number of nested
fun expressions matches the number
Hint: an easy way to implement this functionality is to have the main
work done by a recursive function with an extra argument which is the
expected number of nested
fun expressions. If you do it right, you
will also allow more “interesting” nestings of
expression as long as the overall arity matches.
Here are some tests for demonstration:
Don’t forget a type declaration and a purpose statement for
When we talked about dynamic scope, we’ve mentioned how a few languages solved the problem of introducing lexical scope into a language that was initially implemented as dynamically scoped. Specifically, we discussed how in Common Lisp (and Perl too, to some extent), some variables can be declared “special” and therefore they use dynamic scope, while other bindings are all lexical. In this question we will implement such a language.
We start from the plain FLANG language that we’ve worked with in class, we’ll use the one based on environments.
Most of the steps are the usual ones:
We add a
dwith binder form for dynamically-scoped names
Extend the type definition accordingly
Extend the parser with a rule similar to
Now, for the actual implemntation, we will cheat and use Racket’s parameters for the implementation of dynamically-scoped names — the same functionality that we’ve seen when we talked about the advantage of using a dynamically scoped value for customizing code.
We will need to define a new kind of values that hold Racket parameters:
The next step is to make such bindings evaluate to the value that is stored in the parameter, for this, we need a helper function
Finally something for you to do: write the new evaluation case for
to use this utility. (This is about the
eval code fragment.)
Implement the new case for
DWith: this would be very similar to the
With case, except that you should use the new
ParamV and a
parameter (using Racket’s
make-parameter that creates a parameter with
an initial value).
We’re almost done now — the last thing to do is to make the evaluator extend an environment in one of two ways based on whether we get a dynamic binding or not.
We will use a helper function to do the work — so the evaluation of
Call change to:
Note that the
extend-and-eval function takes four arguments:
extend-and-eval, using this template:
Note that you will need to use Racket’s
parameterize, which looks like
For reference, here is the definition of the
get-param utility that is
used above — there’s nothing here that you need to do. This code is
very similar to
lookup, only it returns #f instead of an error, and in
case of a non-
At the end of the “Alternative Church Encoding” (Lecture #13) section we
have seen a way to define types in a way that is similar to our own
cases. This could have been used, for example, to
implement natural numbers, based on their structural definition.
Roughly speaking, we’d say that a natural number is either zero or a
successor of some other natural number. With out type definitions:
Using the method in that section, we would implement natural numbers as
z is used for for the zero case, and
s for the successor case.
Following this, we would write the following definitions for
Zero is a constant, and therefore doesn’t take any
n, the preceding natural number.
As a usage example, here is addition in Racket (with the Racket
and in Schlac:
Your task is to write utility functions to convert our regular Church
encoded numbers to/from this encoding. Let’s use
nnat to refer to
these “new naturals”, so name the two conversion functions accordingly.
nat->nnat, converting a regular church encoded natural to
nnat->nat, going back
If your implementation is correct, it would make the following two tests pass:
sub, they won’t help (really, they will only make your implementation redundantly longer).
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.)
Why couldn’t we specify the proper restrction of matching arities in the BNF question?
Because our language is strict.
Because the arity property is dynamic, and we cannot use
Because this cannot be done by a context free grammar, including BNF.
Because, as seen in the AST question, it requires actual Racket code to check that kind of validity.
What’s the main problem with the restricted language that we have specified correctly in the AST question?
It requires laziness, otherwise we will not be able to treat functions as first-class.
It requires lexical scope, otherwise we will not be able to treat functions as first-class.
By forbidding other uses of
fun forms, we make the language
fun is equivalent to
with, so we lose the ability to
deal with first class functions.
fun is equivalent to
with, so we lose the ability to
abstract over code, we lose actual functions.
How does our extended FLANG +
dwith language compare to a dynamically
scoped laguage? (Reminder: choose the best answer.)
We implemented dynamic scope, so it’s no wonder that the result is suffering from exactly the same issues as a dynamically scoped language — it’s just as bad.
We added dynamic scope to a lexically scoped language, which means that not only can we not rely on meanings of identifiers, but we also get potential confusion between the two scopes, so things are much worse.
It is slightly better since we have some lexical scope, and we can
choose to not use the dynamic
Things are a little better because we have some number of lexically scoped variables, and therefore we can do the same reasoning (and compiler optimizations etc) for some parts of the code.
It is much better because the dynamic scope is delimited by
expressions, and therefore there is no global change in code from
other programmers whose code we use.
It could be much better because we control the scope as #5 says, but in practice this is because our language is limited, specifically, there is no way to combine multiple pieces of code from different people.