CS 2420-20 Homework 1

Due: Monday, January 17th, 2011 9:10am

Implement an assembler for the Jam2000 machine, which converts a Jam2000 assembly program to a disk (i.e., a sequence of machine codes).

A Jam2000 assembly program is a sequence of Racket S-expressions, possibly containing Racket comments. See also the slides from class.

The files mandelbrot.jam and list.jam contain example assembly programs. The assembled form of mandelbrot.jam is a sequence of 89 numbers.

Your assembler can assume that a given Jam2000 assembly program is well-formed. You can also assume that names defined by const, label, and data are distinct from register and instruction names.

Implement the program in racket, and use the assembly.rkt module included in jam.zip. Start your program with #lang racket, which will give you most of what you expect to be in the language from your experience with the HtDP languages—plus a lot more.

Your program can accept the input program through “standard input,” expect it in a particular file, or accept a filename as a command-line argument. It should produce the result to “standard output.”

The parts below are intended as a hint for how to implement the assembler. You are not required to implement the program as the parts suggest.

Part 1 – Files, Input, and Output

Use the Racket functions file->list or port->list to turn a Jam2000 assembly program into a list of S-expressions. For example, with

  (define decls (port->list))

then piping into standard input the Jam2000 assembly program

  (const X 7) ;; in case we need X
  (halt) ;; all done

will bind decls to the Racket value '((const X 7) (halt)). In general, decls will be bound to a list of declarations, where each declaration is a list that has a symbol followed by symbols and numbers.

Alternately, if you’d prefer that the input is provided as a input.jam file, then use

  (define decls (file->list "input.jam"))

To write list of numbers codes to standard output, use

  (for-each displayln codes)

Part 2 – Collecting Names

Implement collect-names, which takes a list of declarations (like decls above) and produces a dictionary mapping names to values. You might implement the dictionary as a list of structures, for example.

The collect-names function will need an accumulator to keep track of how many code-generating declarations have been processed, since that count is needed to determine values for label and data declarations.

To write tests using check-expect, require the library test-engine/racket-tests, and add (test) after all check-expect forms to run the tests. To suppress messages when all the tests pass (but not when they fail), use (test-silence true) before (test).

Part 3 – Finding Names

Implement find-name, which takes a symbol or number and a dictionary and returns a symbol or number. The result is the same as the given symbol or number, unless the symbol has a value in the dictionary, in which case the symbol’s value is returned instead.

Part 4 – Substitute

Implement subst, which takes a declaration and a dictionary and returns a declaration where each symbol that has a value in the dictionary is replaced by its value.

Part 5 – Assemble

Implement subst-and-assemble, which takes a list of declarations and a dictionary and returns a list of numbers (for machine codes). For each declaration, the result should contain a corresponding machine code (if the declaration generates a machine code) that is either the data value for a data declaration or the result of assemble (as provided by assembly.rkt) for an instruction.

Part 6 – Go

Combine your subst-and-assemble function with input and output to assemble a program supplied by a user to its machine code.