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. CourseNana.COM 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. CourseNana.COM Your code for this homework will go in interp.ml (and backpatch.ml if you choose to do the bonus task). CourseNana.COM

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

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: CourseNana.COM Do not change or remove any lines that start with (*>*. CourseNana.COM 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. CourseNana.COM

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). CourseNana.COM Recall that you will use the definition empty_env and the functions env_add, env_add_placeholder and env_update, as described in class. CourseNana.COM

Testing

Compile and run your code using: CourseNana.COM 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: CourseNana.COM 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. CourseNana.COM ./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. CourseNana.COM

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. CourseNana.COM 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... CourseNana.COM You can test your backpatching code with make backpatch and then ./backpatch CourseNana.COM

Extra questions

These questions are worth 0 points, but are nevertheless important. Answer these questions in interp.ml. CourseNana.COM 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 ([]). CourseNana.COM 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. CourseNana.COM

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. CourseNana.COM When you're finished, use the following commands to submit: CourseNana.COM 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. CourseNana.COM 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. CourseNana.COM