Project 6: From ML-ish to Scheme-ish

Due Tuesday November 20, 11:59pm

In this assignment, you will write a type-checking compiler that maps MLish, a subset of ML, down to Scish.

Repo Access and Submitting

(a) Instructions to access the psets repo

  1. Click on the assignment link and sign in using your personal GitHub account.
  2. Create a new group or join an existing group. For the sake of blind grading, please make sure your group name has no personal identifiers! (For example, you can generate a random name here.)
  3. You have now created a new repo under the HarvardCS153–2018-Fall organization; commit and push your assignment here!

(b) Instructions to submit

  1. Make sure you are using OCaml version 4.07.0, or at the least that your submission compiles and runs with OCaml 4.07.0. This is our “supported” version and is what we will be using to grade your problem set!
  2. Please list your HUID(s) in the file huids.txt. This will help us perform blind grading.
  3. Your last commit before the deadline to the master branch of your repo is your final submission. Please note that no late submissions will be accepted. Don’t forget to push!

Assignment

In order to implement your MLish compiler, you must complete two tasks:

  1. A type-checker for MLish in mlish_type_check.ml
  2. A translation from MLish AST to a Scish AST (which, you can compile to Cish, which you can compile to Mips) in mlish_compile.ml.

The file mlish_ast.ml defines the abstract syntax for the ML subset that we will be using as well as some pretty printing utilities; ml_lex.mll and ml_parse.mly provide the lexer and parser for the language.
MLish is only a small subset of ML: there is no support for modules, references, pattern matching, type declarations, type annotations, or even recursive functions.

To build the type-checker for MLish, in mlish_type_check.ml complete the definition 

  let type_check_exp (e:MLish_ast.exp) : tipe = raise TODO

(You will need to write a recursive helper function.) You should follow (roughly) the notes presented in class for doing ML-style type inference. Included in mlish_type_check.ml are functions for creating fresh guesses and type variables. You do not need to worry about side-effects when type checking expressions (since the language doesn’t have any).

To build the compiler, complete the definition of

  let rec compile_exp ((e,_):ML.exp) : S.exp = raise TODO

It is up to you how to compile MLish to Scish.

Running make in the current directory will generate an executable proj6_mlish, which expects a file to compile. You can use this to test your compiler. This will first use your type checker; if this succeeds, it will compile to Scish and use the Scish evaluator to return an answer. You can uncomment the print statements in mlish.ml to see each step of compilation.

To test out MLish code, instead of providing an interpreter, you may simply evaluate the code in Ocaml toplevel to see what value you get back. You should get back an equivalent value when you compile the code to Scish and run it in the Scish interpreter. To run MLish code in OCaml, you will need to add a few definitions to the initial basis such as:

let isnil x = match x with [] -> true | _ -> false

Make sure to test your code on all of the language forms. Some tests have been provided to you in the directory test. These tests should not be considered exhaustive: you will need to write more tests to thoroughly test your type inference and compilation!

Notes