Homework 1 - S-expressions

Assignment Instructions

  1. Accept the assignment on GitHub Classroom here.

  2. Do the assignment 🐛.

  3. 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.

Introduction

In this homework, you'll be implementing interpreters and compilers for two languages capable of basic arithmetic:

Expressions

The S_exp module contains types and functions for working with s-expressions. We represent s-expressions with the s_exp type:

type s_exp = Num of int | Sym of string | Lst of s_exp list

To parse an expression from a string, we already provide the parse function:

parse : string -> s_exp

Additionally, you can produce a debugging representation of an expression with the provided show function:

show : s_exp -> string

You do not need to modify any aspect of the S_exp module. These functions might be useful to you if you wish to interact with them in the toplevel.

Tasks

All the functions you need to complete, along with their signatures, are in the hw1/arith.ml file.

Note: all functions you must implement are defined with let, but you may change any of them to let rec as you see fit. However, please do not change the type signature of any required functions.

Stringifying expressions

Task: To get some practice working with the s_exp type, implement the string_of_s_exp function, which should produce the string representation of the expression it is given. We have included some tests for this function; feel free to add more.

Bin

As described above, bin is a language that supports integers and binary + and * operators.

The grammar of bin is as follows:

<expr> ::= <num>
         | (+ <expr> <expr>)
         | (* <expr> <expr>)

Task: Implement the function is_bin that determines whether or not an s_exp is valid in bin.

To get a value out of a bin expression, we'll explore two options:

Task: Implement the function interp_bin that takes the first approach to evaluate expressions. If an expression cannot be evaluated, raise the Stuck exception.

Note: This logic should be similar to eval from last week's homework, except the input is an S-Expression and not a type defined in OCaml. S-Expression syntax is what we're mainly going to be using throughout the class, as it is the direct result of parsing our language. The tradeoff is that we don't have any guarantee that the S-Expressions correspond to our language's grammar. For example, Sym "asdf" is a perfectly fine S-Expression that OCaml will accept as an input for interp_bin, but it is not in our language and therefore should raise an error. Make sure you understand this distinction before moving on!

For the second approach, compiling expressions to instructions requires a definition of "instruction". We'll use this one:

type instr = Push of int | Add | Mul

A Push instruction takes an integer and pushes it onto a stack, a list of integers that serves as the working memory of whatever is evaluating the instructions. For instructions that operate on arguments (in this case Add and Mul, which each require two arguments), pop them from the stack as needed and then push the result. Arguments should be evaluated left-to-right. Stacks are last-in-first-out, meaning that a pop will remove the value most-recently added to the stack. For convenience, a stack type is defined as an alias for int list.

Task: Implement the function interp_instr, which interprets an instruction in the context of a stack to produce an updated stack, and the function interp_program that interprets a list of instructions, producing the resulting value (which will be the last value pushed to the stack).

Note: Raise the ShortStack exception if there aren't enough arguments on the stack to perform an instruction.

Task: Implement the function compile_bin that compiles an expression into a list of instructions.

Variadic

The variadic language adds support for variadic + and * operators. That is, both operators will be callable with any number of arguments.

The grammar of variadic is as follows:

<expr> ::= <num>
         | (+ <expr> ...)
         | (* <expr> ...)

There are two main ways to go about adding this support:

Task: Implement the function desugar_variadic that takes a variadic expression and translates it into the bin language.

Task: Implement the function interp_variadic that directly interprets a variadic expression (i.e. without relying on desugar_variadic).

Testing

In test/test_arith.ml, test the funtions you just implemented. To test variadic, compare the desugaring and direct interpreting approaches against each other on a variety of different inputs. For an example of this type of testing, look at the test we've provided for string_of_s_exp.

Two testing provided testing forms you might find useful are assert_equal and assert_raises. Here is an example of their usage:

(* Asserts that the two arguments must be equal *)
assert_equal (1 + 2) 3

(* Asserts that the exception specified in the first argument will
be raised by running the second argument (a thunk) *)
assert_raises Division_by_zero (fun () -> 1 / 0)

Additionally, assert_equal takes an optional printer parameter that specifies how to print the arguments if the test fails. Example usage is as follows:

(* Without printer argument *)
assert_equal 10 15
(* Results in "Failure: not equal" *)

(* With printer argument *)
assert_equal ~printer:string_of_int 10 15
(* Results in "Failure: expected: 10 but got: 15" *)

For examples of using OUnit tests, here's how we could test s_exp parsing:

let test_s_exp_parse _ : unit =
   assert_equal (Lst []) (parse "()");
   assert_equal (Num 42) (parse "42");
   assert_equal (Num (-20)) (parse "-20");
   assert_equal (Sym "a") (parse "a");
   assert_equal (Lst [Sym "a"; Sym "b"]) (parse "(a b)");
   assert_equal
     (Lst [Sym "+"; Num 3; Lst [Sym "*"; Num 4; Num 5]])
     (parse "(+ 3 (* 4 5))")

Additionally, feel free to look at the tests from last homework.

Don't worry if you are unfamiliar with the OUnit test framework - this will be the last time we are using this testing framework for testing this semester.

Useful commands

dune build builds everything.

dune runtest -f runs the tests in the test/ directory.

dune utop runs a toplevel. You can access the functions you're developing for this homework by running, e.g.,

# dune utop
utop> open Hw1.Arith;;
utop> string_of_s_exp (Num (-45));;
"-45"