Homework #7: Fake Assembler (graded)Out:   Friday, February 16th, Due:   Friday, February 23rd, 11:23pm (master homework)


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:

#lang pl 07

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


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: