Assignment 5: A Heap of Characters

Due: Thurs, Oct 3, 11:59PM (EXTENDED: Sun, Oct 6, 11:59PM)

The goal of this assignment is to extend a compiler with data types that require memory allocation and dereferencing.

You are given a repository with a starter compiler similar to the Hustle language we studied in class. You are tasked with:

• incorporating the Fraud+ features you added in Assignment 4,

• extending the language to include a string data type,

• implementing a number of primitives,

• updating the parser to work for Hustle+.

From Fraud+ to Hustle+

Implement all the features of Fraud+, extended to Hustle+.

Strung out

In the last assignment, you 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.

• string-length ; String -> Natural, which computes the length of the string.

• make-string ; Natural Char -> Natural, which constructs a string of the given length, filled with the given character.

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 are free to change the representation if you’d like, but you will have to update the run-time system to properly print strings. Otherwise, no changes to the run-time system should be necessary.

More operations

Add the following operations to the Hustle+ language:

• box? ; Any -> Boolean, which determines if a value is a box.

• empty? ; Any -> Boolean, which determines if a value is the empty list.

• cons? ; Any -> Boolean, which determines if a value is a pair.

• = ; Number Number -> Boolean, which determines if two numbers are equal.

• < ; Number Number -> Boolean, which determines if the first number is less than the second.

• <= ; Number Number -> Boolean, which determines if the first number is less than or equal to the second.

• char=? ; Number Number -> Boolean, which determines if two characters are equal.

• boolean=? ; Boolean Boolean -> Boolean, which determines if two booleans are equal.

Extending your Parser, yet again!

CHANGE: There have been a couple of omissions in the grammar and the code given to you for the parser. The grammar has been (hopefully) fixed and I have decided to release the code for the parser, so you shouldn’t have to make changes to it. If you have already cloned the repository and starting working on it, just replace your parse.rkt and lex.rkt with these files:

https://raw.githubusercontent.com/cmsc430/assign05/master/parse.rkt

https://raw.githubusercontent.com/cmsc430/assign05/master/lex.rkt

If you have not yet accepted the assignment, these changes should already be included in your code when you do.

Extend your Fraud+ parser for the Hustle+ language based on the following grammar:

There is a lexer given to you in lex.rkt, which provides two functions: lex-string and lex-port, which consume a string or an input port, respectively, and produce a list of tokens, which are defined as follows (only the new parts are shown):

; type Token =

; ...

; | '()

; | String

; type Prim = Prim1 | Prim2 | '-

; type Prim1 =

; | 'add1

; | 'sub1

; | 'zero?

; | 'abs

; | 'integer->char

; | 'char->integer

; | 'char?

; | 'boolean?

; | 'integer?

; | 'string?

; | 'box?

; | 'empty?

; | 'cons?

; | 'box

; | 'unbox

; | 'car

; | 'cdr

; | 'string-length

; type Prim2 =

; | 'make-string

; | 'string-ref

; | '=

; | '<

; | '<=

; | 'char=?

; | 'boolean=?

; | '+

; | 'cons

The lexer will take care of reading the #lang racket header and remove any whitespace.

You must complete the code in parse.rkt to implement the parser which constructs an s-expression representing a valid Hustle+ expression, if possible, from a list of tokens. The parse function should have the following signature and must be provided by the module:

; parse : [Listof Token] -> Expr

As an example, parse should produce '(add1 (sub1 7)) if given

'(lparen (prim add1) lparen (prim sub1) 7 rparen rparen eof)

You should not need to make any changes to lex.rkt.

Testing

You can test your code in several ways:

• Using the command line raco test . from the directory containing the repository to test everything.

• Using the command line raco test <file> to test only <file>.

• Pushing to github. You can see test reports at:

  https://travis-ci.com/cmsc430/

  (You will need to be signed in in order see results for your private repo.)

Note that only a small number of tests are given to you, so you should write additional test cases.

There is separate a repository for tests! The testing set-up is slightly different for this assignment. There is a whole other repository that contains tests. When you push your code, Travis will automatically run your code against the tests. If you would like to run the tests locally, clone the following repository into the directory that contains your compiler and run raco test . to test everything:

https://github.com/cmsc430/assign05-test.git

This repository will evolve as the week goes on, but any time there’s a significant update it will be announced on Piazza.

Submitting

Pushing your local repository to github “submits” your work. We will grade the latest submission that occurs before the deadline.