This homework is only required for master students. Undergrads can do it too, and you will be graded as usual — but you will not be able to withdraw a graded homework grade, so submit only if you think that your work is good enough to improve your grade. (Note: the homework grades are all weighted to compute your overall grade, so adding another grade means that you get smaller portions for more grades, which can serve as protection against local disasters.)
Note that while undergrads are not required to submit a solution, it will be a very good idea to read the homework and go through the solution when it is later posted — since you are expected to know the material.
This is a very quick homework — for individual submission, do not work on it with your partner.
The language for this homework is:
In this homework you will see how a programming language can be “implemented” in a very simple way: using just features of some host language to implement features that are common in another. You will therefore not use (or implement) an interpreter.
There are two tools that make it possible to mimic assembly code in Racket. The first are boxes: using boxes we can emulate mutable machine code registers. In other words, boxes are essentially mutable memory locations, much like CPU registers. (And they have an interface that is close to explicit C pointers.)
The second tool is less expected: we can use thunks (nullary functions)
gotos. The basic idea is that every “label” is actually a
thunk, and a
goto is performed by just calling the thunk in tail
position (that is, we never need to do anything after the label thunk
returns). This is much simpler than it sounds — instead of long
explanations, you are given a template file that implements some
assembly-like commands, and then uses them to write an assembly-code
version of a
For this homework, you need to do very little. Specifically, you
don’t need to implement or extend the assembly language layer —
the template file has everything you need, and the only thing you need
to do with that part is understand it. Pay attention to the types:
each assembler “command” is either doing some kind of side-effect
(functions that return
Void), or some kind of control flow (functions
that return an
Integer). The actual assembly code is divided to
chunks, each chunk is a thunk (which is used as the label), that has a
number of side-effect commands, and the last command is a control flow
command — usually jumping to a label (conditionally or
unconditionally), and sometimes returning a value. A program can return
a value only once, and that value becomes the result of the Racket
Once you understand all of that, you have two things to do. First, you need to explain why tail call elimination is a crucial aspect in making all of this work properly. Use the template file as a basis for your work, and write this explanation in a comment at the top of the file. It does not have to be long. The second thing you need to do is write some assembly code of your own.
Once you’ve understood the given code, you need to write a new
more-ones?, which consumes two integers, and
determines whether the first one has more
1 bits in its binary
representation than the second. This should look similar to the
definition: a block of definitions that create all the registers that
you need, a block of declarations for all the label names that you use,
then the code itself. The code should use only assembly commands,
nothing else, just like the
Important: You must write a kind of a “routine” to count the number of bits in both input registers without duplicating the code that does that.
You are likely to encounter several difficulties that will make it very tempting to extend the language. The kind of facilities that you will miss will be a good lesson in itself, but still — your solution must not extend the assembly language. (See the next section for more details.)
you’re given a number of tests for the function that you need to implement. It is a good idea to add more.
Your solution will probably not need all of the given assembly functions, you can just comment out the ones that are not used to get complete coverage.
You don’t need to worry about negative numbers.
Note that the indentation style in this code makes sense for what it is, but it is not how DrRacket wants to indent the code. So in this homework you’ll probably want to use your own indentation without letting it auto indent your code (but it must still be consistent and readable, of course).
(No code or text is needed for this question, it’s just a thought experiment. You can still do these changes, but only if you want to, just indicate what you did in a clear comment, or have the new version commented out.)
When you’re done implementing
more-ones?, you will most likely have a
number of ideas on possible ways that the “language” could be extended
to make programming it easier. You could play with a few possible
extensions, doing so will be interesting. A few things you can try:
Indirect registers — implemented as
(Boxof Register), these
correspond very roughly to having addressable memory.
Label registers —
(Boxof Label), similar to being able to put and
use label addresses in registers.
Call stack — implemented as a list of registers that is passed around in all functions, or as a mutable list, which is mutated for push/pop operations.
A cheap facility to call out a subroutine, building on Racket functions:
(This sounds like a simplistic and easy to implement solution, but trying it will be interesting in the kind of problems you’ll run into.)
Or just a bunch of higher level primitives that will somehow make life easier. (This is very easy, since you can implement them using Racket functions.)