Homework 0 - Introduction to OCaml
Accept the Assignment on GitHub classroom here
Complete all TODOs in the
lib\hw0.mlfile (assignment details below).
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 to OCaml
In this homework, you'll be familiarizing yourself with the OCaml programming language, which we'll be using in all of our assignments throughout this course to build our compiler.
This assignment has two parts. The first consists of a set of exercises meant to assess your comfort with OCaml going into this class. We strongly encourage those who do not have prior OCaml experience and feel like they need additional practice to attend the OCaml Gearup, which will happen shortly after this homework is due. Details about the gearup will be provided in class and over EdStem.
In the second part of this homework, you'll put OCaml into use and implement a small interpreter.
All parts of this homework should be completed in the
If you haven't written any OCaml before (we don't assume that you have!), we have a few different resources for you to try the language
- A First Hour with OCaml
- The second chapter of OCaml Programming: Correct + Efficient + Beautiful.
demosfolder in this assignment also includes some OCaml demos on lists, recursion, higher order functions, datastructures, and options. These are the things that we think are important to know about OCaml for this class
A note on grading
Your score on this assignment will not meaningfully impact your grade in this class. However, you are required to complete this assignment, and we will be looking at each submission and asking those who struggle to attend the gearup.
For this homework and only this homework, a complete test suite is provided--you
can look at the tests in
dune build builds everything.
dune runtest -f runs the tests in the
dune utop runs a toplevel. You can access the functions you're developing for
this homework by running, e.g.,
# dune utop utop> open Hw0_demos;; utop> open D1_list;; utop> head [1; 2];; - : int = 1
(If you leave off the
open Hw0_demos and
open D1_list;;, you'll get an error when you try to call
Part 1: OCaml
demos/ folder, we supply a few OCaml code examples to help you solve the
exercises in this section. We encourage you to look through and reference these!
Task: Using recursion, write the function
take_while that takes in a list of
integers, a predicate function
f and collects the elements until an element
that doesn't satify the predicate is reached
Task: Using pattern matching, write the function
take_last_two that finds the last
two elements of a list, as an option. If the length of the list is less than 2,
None, otherwise, return
fold_right to write your own
Task: Write a function
depth : 'a tree -> int that returns the number of nodes in any
longest path from the root to a leaf. We have provided an ADT representing a Tree.
For example, the depth of an empty tree (simply Leaf) is 0, and the depth of
tree t above is 3. Hint: there is a library function max : 'a -> 'a -> 'a that
returns the maximum of any two values of the same type.
Part 2: Baby Interpreter
As you know from lecture, while compilers translate from a source language into a target language, interpreters evaluate languages and return a final value.
Let's make an interpreter for a language
arith representing a subset of arithmetic
that can add or multiply numbers. Here is
arith's representation in OCaml:
type arith = Add of arith * arith | Mul of arith * arith | Num of int
Here are some examples of how various expressions look in
|2 + 4
|Add (Num 2, Num 4)
|(2 * 3) + 4
|Add (Mul (Num 2, Num 3), Num 4)
Task: Write a function
eval that takes in an
arith expression and returns
int result of that expression.