CS 440 HW3

In this homework you will be writing an interpreter for the language MiniML. See the language spec, walkthrough video and README.md in your starter code repo for more information on MiniML and the codebase. Note that you will be using the same starter code for homework 4.

For HW3, MiniML is dynamically typed, so no type-checking is done, and type errors (Interp.TypeError or Interp.UnboundVariable) may arise at runtime. This also means you can write expressions like 1::"Hello"::[] which are not well-typed in OCaml.

Your code for this homework will go in interp.ml (and backpatch.ml if you choose to do the bonus task).

Collaboration

This assignment is to be completed individually, subject to the academic integrity policy on the course website. Make sure you read and understand these.

At the end of this assignment, we will ask you to list any students you discussed the homework with, as well as any websites or other resources (please list specific URLs when applicable) you referred to.

Important notes about grading

Your submissions will be graded automatically for correctness, as well as checked by hand. Please keep our autograder (and Xincheng, who has to run it) happy:

  1. Do not change or remove any lines that start with (*>*.

  2. Do not change the names or types of any functions defined in the starter code. This includes adding rec to functions that don't have it.

MiniML Interpreter (30 points)

Fill in the remaining cases of interp_expr in interp.ml. We've provided a few of the cases (mainly the ones we did in class) for you. You need to add cases for all of the other constructors of expressions (OCaml should warn you when you try to compile if you missed any cases).

Recall that you will use the definition empty_env and the functions env_add, env_add_placeholder and env_update, as described in class.

Testing

Compile and run your code using:

    make hw3
    ./hw3

This will open something similar to the OCaml toplevel, which will let you type declarations and will print out the bindings introduced:

    Welcome to MiniCaml. Type #quit;; to exit.
    # let x = 1;;
    x = 1
    # let f y = x + y;;
    f = <fun>
    # let x = 2;;
    x = 2
    # f 2;;
    - = 3

You can also use the binary hw3 in "batch mode" by giving it a .ml file on the command line, e.g.

    ./hw3 ../src/examples/rec.ml

    sum = <fun>
    length = <fun>
    map = <fun>
    int_to_string = <fun>
    onetwothree = (""one")::((""two")::((""three")::([])))

This will interpret the entire file and print out the value of every top-level binding. We've provided some sample files in the examples folder (ignore the subfolder error for now), and you're welcome to write your own.

Bonus: Recursion using backpatching (5 points)

Backpatching isn't just good for making recursive environments, we can also use it to implement recursive functions. In backpatch.ml, define the function fact: int -> int, which computes the factorial of the given integer (remember: fact(0) = 1; fact(1) = 1; for n > 1, fact(n) = n (n - 1)). Do not use the rec keyword or any builtin functions. You *may (and will need to) use references.

Hint: When implementing fact, assume we have another function fact', which computes the factorial of numbers smaller than n. This is the same trick we used earlier in the class to think about recursion: if you can use let rec, then fact' is just fact. So we want to let fact' be fact. Unfortunately, we need fact' in fact, so we can't make fact' be fact until after we define fact...

You can test your backpatching code with make backpatch and then ./backpatch

Extra questions

These questions are worth 0 points, but are nevertheless important. Answer these questions in interp.ml.

  1. Fill in students_collaborated_with with a list of strings giving the names of other students with whom you discussed this homework, and urls_consulted with a (string) list of web URLs or other resources you consulted while doing the homework. Be as specific and thorough as possible, within reason. Remember that this helps clear up confusion if we have any questions about your work. If either answer is "None", you should still fill in the empty list ([]).

  2. Also fill in minutes_worked with the (approximate) number of minutes you spent working on this assignment. Your honest feedback will help us with future assignments.

Submission

When you are done with your work, make sure you have compiled your code using make (and ideally tested it using the instructions above). Submissions that do not compile will receive no credit.

When you're finished, use the following commands to submit:

    git add interp.ml
    git add backpatch.ml
    git commit -m "HW3 submit"
    git push

(You only need to add backpatch.ml if you edited it.) Please do actually use the commit message "HW3 submit" so we know when you intended to submit your homework and can also differentiate this from when you submit HW4.

There are no additional files you need to add to the repo, just interp.ml (and backpatch.ml if you did the bonus). There are also no automatic tests, so you will not see a green check mark (or red X) on GitHub. As usual, double check GitHub and make sure you can see your latest code.