Assignment 5: A Heap of Characters
Due: Thursday, April 7th, 11:59PM EDT
The goal of this assignment is to extend a compiler with data types that require memory allocation and dereferencing. A secondary goal is to hone your test-writing skills.
You are given a repository with a starter compiler similar to the Hustle language we studied in class. You are tasked with:
extending the language to include a string data type,
extend the (very few) tests provided to be as comprehensive as possible.
Strung out
In Dodger, we implemented a character data type for representing single letters. In this assignment, you will implement a String data type for representing arbitrarily long sequences of characters.
Strings are disjoint from all other data types and are essentially a fixed-size array of characters. Literal strings are written by enclosing the characters within the string in double quotes ("). Strings can include double quotes by using the escape sequence \".
You must add the following operations to Hustle+:
string? ; Any -> Boolean, which determines if its argument is a string.
string-ref ; String Natural -> Char, which extracts the character at the given index (using 0-based counting). An error is signalled if the index is out of bounds for the given string or if the first argument is not a string.
string-length ; String -> Natural, which computes the length of the string, or yields an error if its argument is not a string.
make-string ; Natural Char -> String, which constructs a string of the given length, filled with the given character If the first argument is not a non-negative integer, of if the second argument is not a character, an error should be returned.
We have already added a String struct in ast.rkt and provided the parsing code in parse.rkt.
More importantly, the run-time system has been updated to account for a string type. It assumes a representation where the length of the string is stored in memory, followed by the characters of the string, in order. You can change the representation if you’d like, but you will have to update the run-time system to properly print strings and discuss it with the instructors beforehand. Not recommended! Otherwise, no changes to the run-time system should be necessary.
If you want to understand the details of how strings are implemented in the run-time system. See the function print_string() in main.c.
In order to get all the points for this section of the assignment you will need to modify the following files:
interp.rkt
interp-prim.rkt
compile.rkt
Add tests!
One thing that has been not stressed enough this semester is the need to add tests. There are 6 files under the test/ directory in the repo. Three of them contain regression tests to ensure that you don’t break functionality when you add the new constructs. These are test-runner.rkt, interp.rkt and compile.rkt. The test-runner.rkt file provides two functions test-runner and test-runner-io which execute a sequence of calls to an input run function, and check that they yield the expected result. This run function is instantiated in interp.rkt with a call to the interpreter, and in compile.rkt with a call to the compiler.
With this setup, when you do raco test test/interp.rkt or raco test test/compile.rkt you should be seeing "76 tests passed".
There are also three similar files with the "-string" suffix in the test directory in the repo (interp-string.rkt, compile-string.rkt, and test-runner-string.rkt. You’ll notice that there are exactly two public tests there - one using io and one not. The second part of the assingment is to extend these tests to thoroughly test the behavior of the four primitives you added.
You should ONLY add tests to test-runner-string.rkt and they should all be of the same form as the ones provided: either (check-equal? (run XXX) Y) for the test-runner function, or (check-equal? (run XXX SSS) (cons YYY ZZZ)) if your tests use IO.
Your test suite will be autograded based on its ability to reveal bugs in a series of implementations we have provided, each with 1 or more bugs injected. That is, we will run raco test using YOUR test-runner-string file against OUR (intentionally faulty) implementations. Of course, your test suite should not be failing any tests for a correct implementation.
Submitting
You should submit on Gradescope. You should submit a zip file that has exactly the same structure that the stub contains. We will only use the compile.rkt, interp.rkt, interp-prim.rkt, and test/test-runner-string.rkt files for grading, so make sure all your work is contained there!
Not breaking past behavior is worth 20 points.
The 4 string primitives are worth 60 points (30 interpreter, 30 compiler).
Finding bugs with your tests is worth 20 points.
Just zipping the empty template we provide is worth ~30 points! Upload often to make sure you don’t run into autograder issues!