Administrative

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:

Implementing a Fake Assembler

In this homework you will see how a programming language can be “implemented” in a very simple way: using just features of a host language to implement features that are common in another. You will therefore not implement (or use) 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 or memory addresses. (And they have an interface that is close to explicit C pointers.)

The second tool is more surprising: we can use thunks (nullary functions) to emulate 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 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 it also include some sample code: an implementation of a fib function in this “assembly”.

Understanding the Code

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 (thunks that return Void). The actual assembly code is divided to chunks, where each chunk is a thunk (used as the label for the chunk). Each chunk has a number of (side-effect) commands, and the last command is a control flow command — usually jumping to a label (conditionally or unconditionally), but sometimes halting. Note that the halt command is implemented as a plain thunk that returns Void, and the implementations of functions always invokes the main chunk and then return the value of some register. In addition, the fact that halt is a Void thunk means that it can be used in a goto as a Label.

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.

Clarification: Your code should never do anything after a goto. For example, if you write:

(define (foo) ...whatever...
              (goto LABEL)
              (goto LABEL2)) ; <-- or anything at all, not just goto!

then your code is wrong!

The explanation that you need to write should make this restriction clear.

Write Some Assembly Code

Once you’ve understood the given code, you need to write a new “assembly” function, 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 fib 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 fib function.

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.)

Notes:

• 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 should comment out the ones that are not used to get complete coverage.

• You don’t need to worry about negative numbers.

• The indentation style in this code doesn’t make DrRacket happy: instead of the common indentation style, we use one that makes sense for what it is. So when you work on this homework, you should use your own indentation without using DrRacket’s auto indent feature. (It must still be consistent and readable, of course).

Generalize It

(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:

  (define (gosub label) (label))

  (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.)