Homework 1  Sexpressions
Assignment Instructions

Accept the assignment on GitHub Classroom here.

Do the assignment 🐫.

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:

bin
: a language supporting integers and binary+
and*
operators. This language is similar to the language you worked with last week in HW0.Example programs:
1260
,(+ 1 2)
,(* 3 4)

variadic
: a language supporting integers and variadic+
and*
operators (i.e. operators able to accept any number of arguments).Example programs:
(*)
,(+ 1)
,(* 5 6 6 7)
Expressions
The S_exp
module contains types and functions for working with sexpressions.
We represent sexpressions 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.
 Hint: The
string_of_int
function converts an integer to a string.
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:
 Directly interpret the expression, performing the arithmetic operations as
we go, to produce a value. For example, we would interpret
(+ 1 2)
in OCaml as1 + 2
, which produces3
.  Compile the expression into a lowerlevel sequence of instructions, which can then be evaluated to produce a value.
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 SExpression and not a type defined in OCaml. SExpression
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 SExpressions correspond to our language's grammar. For example,
Sym "asdf"
is a perfectly fine SExpression 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!
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. Instructions that operate on arguments (in this case Add
and
Mul
, which each require two arguments), pop them from the stack as needed.
Stacks are lastinfirstout, meaning that a pop will remove the value
mostrecently 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 producing 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:

Extend the interpreter and compiler of the simpler language to support the new features.

Translate expressions in the extended language into ones that are valid in the simpler one, then use the interpreter and compiler of the simpler language.
Example:
(+ 1 2 3)
translates to(+ 1 (+ 2 3))
.Note: This approach, which is called desugaring (since it takes a sweet/appealing syntax and translates it to an equivalent, often less appealing one), is only possible if the simpler language is capable of expressing the same functionality as the extended one. For instance, we couldn't desugar a division operator into the
bin
language, since no combination of addition and multiplication will achieve the same result.
Task: Implement the function desugar_variadic
that takes a variadic
expression and translates it into the bin
language.
 Hint: Note that
variadic
supports zero or one arguments for+
and*
. You may assume that any missing arguments may default to the identity elements0
and1
, respectively. For example(* 4)
should evaluate to4
and(+)
should evaluate to0
.
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"