and returns a list of lists of length n taken from the input list.
You can assume that the input is always valid — that the number is
always positive, and that the number of items in l is some
multiplication of n.
Here are a few tests to clarify this:
(test (n-split '(1 2 3 4 5 6) 3) => '((1 2 3) (4 5 6)))
(test (n-split '(a b c d e f g h) 2) => '((a b) (c d) (e f) (g h)))
(test (n-split '() 2) => '())
Note that the function should be usable with any kind of lists. Remember
to write a proper type declaration and a brief purpose statement.
Question 2: Higher-Order Functions
15 pts
Implement a “cheesy infix” function called infix, that can be used
as a lame substitute for an infix syntax. It’s best to demonstrate it
using some tests:
However, just that is almost trivial to write, so we’re going to make it a
little more ... “sophisticated” ... but will do so in a similarly lame
way... It should be extended so it is possible to use a '? symbol as
the last argument, making it return a function instead of a plain result.
So, this expression
(We could do this for the first too, and also allow it for both; but that
will go beyond the tolerable lameness threshold.)
Make sure you write a correct type declaration (and a purpose statement)
for infix. You only need to write the extended version, not both.
Typed Racket will require a type for the resulting function in the '?
case, but for your answer you can just ignore that.
Note that the the type will involve two unions (U ...).
(And if you really want to be picky, then note that the above tests
wouldn’t work with Typed Racket, since the function will return a result,
or create a function.)
Question 3: BNF Grammar
12 pts
We’ve seen that we can have recursion (or in other words, infinite
computations) without a “magical” definition form such as Racket’s
define. Can the same be said about grammars? It seems like it
doesn’t work there — that a grammar like:
<NUM> ::= <digit> | <digit> <NUM>
cannot be written without the ability to have a <NUM> self-reference. Is
this true? (That it cannot be written without self-reference, either
directly as above or with mutually recursive rules.)
If it is, then explain (as a rough proof sketch) why it’s
impossible.
If it isn’t, then show how the above <NUM> language can be
written without a circular reference.
Either way, keep either the proof sketch or the demonstration as short and
as simple as you can. (Shouldn’t be more than a few lines.)
Question 4: Fill in the blanks
15 pts
For each one of the following expressions, write a definition for blank
in Racket that makes the expression evaluate to 660. For example, a
correct answer for this expression:
(* (blank) 2)
is:
(define blank (lambda () 330))
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.)
You do not need to write types for these definitions (unless one is
explicitly requested).
Do this for the following expressions.
((+) blank)
(first (list blank (blank)))
((lambda (x) (x x)) (blank blank))
(if (blank) blank (blank))
(let ([blank "foo!"] [x blank]) x)
Question 5: Structural Recursion with ASTs
18 pts
Write a to-racket function that translates FLANG code into plain
untyped Racket code in the naive way, using S-expressions (nested lists of
symbols, numbers, etc) to represent Racket code. In other words, the
function header should look as follows:
(: to-racket : FLANG -> Sexpr)
;; Translates FLANG syntax values into Racket code as S-expressions.
(define (to-racket expr)
—«fill-in»—)
For reference, here is the definition of the FLANG AST (used in the
substitution based FLANG evaluator and in the
FLANG-ENV environment one):
The expected results are all quoted (except for the plain number) since
we’re not trying to evaluate some Racket code (that’s what our evaluator
is doing), just create the S-expressions of that code. (Kind of like a
compiler from FLANG to Racket.)
Note that this is a very simple translation — it’s basically just an
unsophisticated recursive scan of the input syntax. Specifically, some of
the above S-expressions are representations of Racket programs that will
not even compile (since Racket insists on not having any free
identifiers), but the translation is still going on fine.
Question 6: Extending the FLANG language
20 pts
It is often useful to have languages that can guarantee some execution
time, but with most languages that is only possible with a (mostly manual)
termination proof and runtime analysis. Moreover, we’ve seen that even
our simple FLANG language is already capable of infinite loops. A common
solution for this is to run the code for a limited time or a limited
number of steps. In this problem we modify the FLANG interpreter to do
this. (This is done for the environment-based evaluator, but it would
look very similar with the substitution evaluator.)
We begin by adding a fuel argument to our eval function, and
throwing an error if it reaches zero:
(: FUEL : Integer)
;; The number of steps a program is allowed to make
(define FUEL 1000)
(define (run str)
(let ([result (first (eval (parse str) (EmptyEnv) FUEL))])
...same code...))
We now need to “thread” the fuel argument throughout the evaluation.
Hint: this is done similarly to the way we threaded the list of
identifiers in the exam question that was reviewed in class (the
normalize). (But don’t try to copy code blindly from there — this
is now the evaluator we’re changing.)
What we need is for eval to return two values — the usual result and
the leftover fuel. Revising the above to use a list with the two values,
we get this:
You can see the modification in some simple cases above. The interesting
bits are in how the rest are modified. Show the change needed for the
Add case and the With cases. (If you really want, you can also do
Call, but it should be obvious by now.)
You need to write only the new cases — so just modify the code in these
two:
[(Add l r) (arith-op + (eval l env) (eval r env))]
[(With bound-id named-expr bound-body)
(eval bound-body
(Extend bound-id (eval named-expr env) env))]
Question 7: Language Features
14 pts
Each of these questions has multiple choices. Choose the correct answer.
Unless stated explicitly, there is only one correct answer.
Some people think that FLANG is essentially the same as Racket when
translated in the obvious way (using single-binding let expression
instead of withs, unary functions, binary arithmetics, braces etc). In
other words, this assumption is that if you run the code that your
to-racket translator from the above question then it will produce
exactly the same value.
This is wrong, however. You need to demonstrate this by providing a
counter example: some piece of FLANG code that would translate to Racket
code with a different meaning.
(Note that this is unrelated to division by zero errors, or the kind of
error messages that you get etc. It’s also applicable to the restricted
Racket, so the arity of arithmetic functions, for example, is irrelevant
too.)
Thick hint: in Racket, + etc are bindings, and in FLANG they’re
keywords. (What happens when you bind them?)
You only need to write the FLANG code that is the counter example (should
be a one liner), and say what values it will produce in FLANG and in
Racket.
(When you do that, you’ll obviously have discovered a subtle bug in the
translation. Phrased differently, that translator works only under some
particular assumption — but you don’t need to fix the code!)
The test form that we use in class catches only errors that your
code throws explicitly, not any Racket errors. For example, since our
FLANG implementation does not check before it divides, this:
(run "{/ 2 0}")
throws an error, but this test:
(test (run "{/ 2 0}") =error> "division by zero")
It’s an arbitrary decision, and there’s no difference between the
two options, either for our use or for the implementation.
It’s important since if test catches Racket errors it would mean
that type checking will interfere with tail calls, which means that we
will lose tail recursion.
Catching Racket errors mean that we get a kind of a “dynamic
scope” for the error, which is unreliable compared to being able to
identify lexically where the error happened.
Catching those Racket errors mean that we will basically “inherit”
Racket’s errors as our own, in a similar way to inheriting its numeric
types and garbage collector. This means that the evaluator is a little
more of a “meta-evaluator” and therefore it’s a little worse in
demonstrating language implementation.
The only reason for this choice is to make us work harder on
homeworks. Writing good errors is hard, and we need to learn by
doing as much work as possible.
Question 8: Schlac
14 pts
In one of the past semesters, there was one piece of code in the Schlac
homework that seemed severely broken:
(define/rec range
(lambda (from to)
(if
((= from to) null)
(cons from (range (+ from 1) to)))))
Clearly, the student that wrote this code was confusing if and
cond, resulting in code that would never work in Racket.
Surprisingly, this code works fine in Schlac. The reason for that is that
(if (C T) E)
evaluates to the same result as
(if C T E)
Show that formally. In other words, show how things would reduce in the
same way (you can work on any each side, showing how it reaches the other,
or doing both until they get to the same expression). Hint: this is
surprisingly easy, and very short.
Feedback Question
[This question is optional, of course. Feel free to write more details and
suggestions, give a single number reply, or just ignore the whole thing if
you’re not interested.]
Exam:
Did you have any issues with this application?
On a scale of 0=“trivial” to 10=“impossible”, how hard was
this exam?
On a scale of 0=“fell asleep” to 10=“fascinating”, how
interesting was this exam?
Any other comments on the exam?
Class:
How well do you follow the material? (0=“what material?”
10=“I already read the whole book, twice”.)
Is it going too slow or too fast? (0=“we could have done what
we did in a week”, 10=“it’s fast enough to feel the Doppler
effect”.)
Is it boring? (0=“it’s so boring that I usually fall asleep”,
10=“I love it, can we have 6-hour classes four times a week?”)
Homeworks:
Are there too little homeworks or too many? (0=“I want more
homework, I need more of teh codes”, 10=“I sleep 20m per night on
weekends — I want a break!”)
Are the homeworks too easy or too hard? (0=“I just slam the
keyboard randomly for 15 minutes and it works”, 10=“I put ice packs
on my head to avoid damage from my inflated brain”)
Materials:
How is the web site working out? (0=“I love it, I’m planning
to show it to all my relative on spring break”, 10=“I have a long
list of complaints and suggestions (which I’ll list below).”)
How is the communication level working out for you? (0=“Just
fine, more than I need”, 10=“I really need much more quality
time.”) (This is in general about getting in touch with me or with
the grader, via email or IRC, or whatever.)
Do you use the textbook? (0=“I read ahead before each class”,
10=“textbook? what textbook?”) (Note that NEU distinguishes
required books from recommended ones, and the textbook should
currently be only recommended, but I’m not sure about this, so
feedback is appreciated.)