Homework 0 - Introduction to OCaml

Assignment Instructions

  1. Accept the Assignment on GitHub classroom here

  2. Complete all TODOs in the lib\hw0.ml file (assignment details below) 🐛.

  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 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 /lib/hw0.ml file.

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

Testing

For this homework and only this homework, a complete test suite is provided--you can look at the tests in test/test_hw0.ml.

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 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 head.)

Tasks

Part 1: OCaml

Demos

In the 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!

Exercises

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, return None, otherwise, return Some(..., ...).

Task: Use fold_left or fold_right to write your own map and filter functions

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 arith:

expression in arith
3 Num 3
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 the int result of that expression.