Homework #9: Fake Assembler
Out: ? Saturday, February 18th, Due: ? Friday, March 3rd, 11:00pm (master homework)

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:

#lang pl 09

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

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

Once you understand all of that, you have two things to do. First, you need to explain why tail call optimization 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.

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:

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: