Homework 2 - Characters

Assignment Instructions

1. Accept the assignment on GitHub Classroom here.

2. Read the lab 2 README. Accept the assignment here

3. Do the assignment 🐛.

4. Upload the assignment on Gradescope. The most convenient way to do this is by uploading your assignment repo through the integrated GitHub submission method on Gradescope, but you may also upload a .zip of your repo.

Lab 2

This assignment comes with an interpreter and compiler that you will be expanding upon. This is the pattern that many future homeworks will follow. Lab 2 is from a previous iteration of the course with lots of helpful information about the code structure, our OCaml representation of Assembly, the compiler runtime, testing, and running the interpreter and compiler manually.

Task: Read the lab 2 README. If you want some practice with these concepts, the lab includes some excersises that you can complete and get checked off at hours.

Introduction

In this homework, the interpreter and compiler in the stencil supports a language with numbers, booleans, and several unary operations. You'll be extending both the compiler and the interpreter with a new type for individual characters, as well as three additional unary operations:

• (char? e), which returns true if its argument is a character and false otherwise
• (char->num e), which converts its argument from a character to a number representing its ASCII code. When the argument is not a character, the result is undefined (and the interpreter should raise an exception).
• (num->char e), which converts its argument from a number representing an ASCII code to its corresponding character. When the argument is not a number, the result is undefined (and the interpreter should raise an exception).

The parser in the S_exp module handles parsing characters. In our Lisp dialect, characters are written as #\ followed by either a single (printable) character, "newline", or "space". For instance, all of the following are characters:

• #\a
• #\A
• #\;
• #\newline
• #\space

Grammar

<bool> ::= true
         | false
<expr> ::= <num>
         | <bool>
         | <char>
         | (<unary_op> <expr>)
<unary_op> ::= num? | char?
             | add1 | sub1 | zero?
             | not
             | char->num | num->char

Testing

Task: Write a set of examples in the examples directory that exercise character functionality. Examples end in .lisp. You should include the anticipated output for the file X.lisp in a file called X.out.

You can compare the output of the compiler and the interpreter (as well as the anticipated output in .out files) by running dune runtest -f.

For example, you could create a file examples/char-a.lisp with the following content:

(char? #\a)

And it's associated output in examples/char-a.out:

true

Gradescope

When you submit your implementation to Gradescope, your suite of examples will be run against a reference interpreter and compiler. This is analogous to comparing your compiler with an existing implementation, one of the testing strategies we mentioned in class. You can always use Gradescope to check the expected behavior of an example.

If the reference implementation fails on any of your examples, Gradescope will show you how its output differed from the expected output of your example (if you wrote a *.out file for it).

You can do this as many times as you want. We encourage you to use this option to develop a good set of examples before you start working on your interpreter and compiler!

Extending the interpreter

Inside of lib/interp.ml, extend the interpreter with support for characters.

Task: Add Char as a variant of the value type (consisting of an OCaml char) and extend display_value to support it.

Note: Be careful to handle #\space and #\newline correctly, as OCaml's sprintf will format them as ' ' and '\n'.

Task: Add support for character constants to interp_expr.

Task: Add support for the new primitives operations to interp_primitive.

Extending the runtime

Before extending the compiler, the runtime must be made aware of characters. We'll represent characters during runtime as their ASCII values shifted left 8 places and tagged with 0b00001111.

Task: Inside of lib/runtime/runtime.c, extend the print_value function to handle printing characters in the #\a form our Lisp dialect uses.

Note: Be careful to handle #\space and #\newline correctly, as C's printf will format them as ' ' and '\n'.

Extending the compiler

Inside of lib/compile.ml, extend the compiler with support for characters.

Task: Add constants char_mask and char_tag to tag character immediates as required by the runtime (similar to how we've tagged numbers and booleans).

Task: Implement a function operand_of_char : char -> operand to make an immediate from a character constant.

Task: Add handling for character constants to compile_expr. This should be similar to the handling for Num and include a call to operand_of_char.

Task: Add support for new character primitive operations to compile_primitive.

Running the compiler and the interpreter

You can run the interpreter on a file:

dune exec bin/interp.exe -- <file.lisp>

You can also run the compiler:

dune exec bin/compile.exe -- <file.lisp> output

The resulting .s file (containing assembly code) and .exe file (an executable) will be in the output/ directory. You can run the executable with

./output/<file.lisp>.exe

You can also tell the compiler to run the executable immediately after compiling by adding -r, e.g.:

dune exec bin/compile.exe -- <file.lisp> output -r