The theme of this lab is how things work under the hood. When you leave the lab, you will have a little bit of intuition for how data are stored on disk and for how hardware machines work. The ideas apply to your trigrams homework, for which you will be reading and writing models.

Data definitions: stack programs

An atom is one of

An sx, also known as S-expression, is one of

A program, also known as stack-machine program, is one of

A stack is a (listof sx).

What’s happening

The idea of a program is that it is a sequence of instructions for building data structures. To enable us to use natural recursion, programs are written right to left. Unless you read Hebrew or Arabic or manga, you’ll find right-to-left order strange, but bear with it—after Thanksgiving we’ll learn a new design recipe that will make it possible for us to read programs from left to right.

We write an interpreter for the program, which manipulates a state. For us the state is a stack of values, which is another name for a list:

;; interpret : program -> state
;; to produce a stack of values according to the instructions in the program

Here’s how each instruction is interpreted:

What does this have to do with the real world?

Here are the connections:

  1. For the homework project, you will convert your list of models to an sx, and DrRacket will write the sx out to disk. The S-expression is a relatively high-level data structure.

  2. On the disk, all information is stored as a sequence of bytes. DrRacket does the conversion from S-expressions to bytes.

  3. In this lab, you’ll convert an S-expression to a sequence of atoms. (Every program is also a (listof atom).) The sequence of atoms is at a high enough level that you can do it in one lab, but at a low enough level that you will have some idea how it might work with a sequence of bytes.

  4. You’re used to writing programs in BSL and ISL. These programs have rich structure which makes them good for thinking and problem-solving. But hardware doesn’t know a thing about BSL or ISL, and DrRacket has to translate from BSL or ISL to something the machine understands. This translation is a ton of work.

  5. What the machine actually understands is a sequence of machine instructions, which are themselves represented as bytes. If you go on to COMP 40, you’ll learn about machine instructions and how they work.

  6. In this lab, we have very simple programs: a program is a sequence of instructions, and there are only three instructions. You’ll be able to write both a compiler and an interpreter. They will be powerful enough to do something useful but simple enough that you can make progress in the lab.

The lab problems

Solve the following problems:

  1. Write, by hand, a program that first puts an empty list on the stack, then puts 2, then makes a cons cell, then puts 1 on the stack, then makes a cons cell, then finishes.

    Remember the program is written from right to left!

    The program, when interpreted, should produce a stack containing exactly one value:

    (list (cons 1 (cons 2 empty)))

    This stack is the result of computing the value (cons 1 (cons 2 empty)) and pushing it onto an empty stack.

  2. Write an interpreter that is given a program and produces a stack of values.

    Use the design recipe for self-referential data. Use natural recursion.

    Advice: For your functional examples and test cases, you may find it easiest to use the list function to write stacks. Otherwise you may get confused about which cons and empty mean what.

    Also, although you can use quote notation to abbreviate the lists, quote notation works only if you really understand exactly what is going on.

  3. Write a compiler that is given an S-expression and produces a program that, when interpreted, reconstructs the original S-expression. (This is how my function write-file-sexp works.)

  4. Extend the data definition for program so that you can take three values from the stack and make a 2D-point.

  5. Extend your definition of sx to include (2Dpoint sx).

  6. Extend your interpreter and compiler to support 2D-points.

  7. Extend our system (data definitions, interpreter, compiler, tests) so you can save and restore a full (2Dtree sx).

Your results

Once you master the techniques of this lab, you’ll be able to save many forms of data to disk. Here’s the general technique:

To save a data structure, write a program which, when interpreted, reconstructs the original data structure.

Once you master this technique you can use it again and again for whatever projects you work on.

Submitting the lab

Five minutes before the end of the lab, put the following text at the beginning of a DrRacket file. You may use an empty file or the source code you have been working on:

What I did during this lab:
   (you fill in this part)

What I learned during this lab:
   (you fill in this part)


Finally, submit this file through the handin server as lab-serialize. Submit it as lab, not as homework. You will need to submit it using two usernames connected by a + sign, as in


You submit using Jane Doe’s password.