Assignment 4: F♭ Interpreter

For this assignment you are to write an interpreter for F♭ as defined in the book. You need to implement all features except for Let Rec (if you implement Let Rec you can get 5 points extra credit).

The F♭ Development Kit (FbDK)

We have provided you with the FbDK to make your job easier.

  • The FbDK distribution is here, download the zip file and unzip.
  • The README.md in the distribution contains basic instructions on how to install, build, and run the various interpreters in the FbDK.
  • The only file you need to work on is to fill in the very incomplete eval function in the file Fb/fbinterp.ml.
  • File Fb/fbast.ml is the type declaration for the F♭ AST’s. There are many other files in the FbDK which you generally can ignore at this point.
  • The FbDK contains the complete BOOL interpreter that we covered in lecture, in the directory BOOL/. The complete source for the BOOL evaluator is given and can help you get started on your F♭ evaluator.
  • As was shown in class and described in the README.md, you can run your interpreter in OCaml’s utop, or in standalone mode, and additionally we have supplied reference binary implementations to help you – see the README.
  • The source of the F♭ code examples in the book as well as the examples and macros used in the Programming in F♭ lecture are found in the file fb_examples.ml as a separate download.

Interpreter writing hints

  1. Use the F♭ operational semantics rules as the guidepost: all you are doing is implementing those rules, below the line is the case you are dealing with and above the line are the recursive evaluations needed.
  2. For a warm-up, get the numbers and booleans to evaluate properly, then tackle functions. The BOOL interpreter is a very big hint on implementing boolean operations in F♭.
  3. You will need to write several auxiliary functions for performing substitution, etc. Use the substitution function in the book Section 2.3.2 as the guidepost for substitution in your interpreter.
  4. Declare and raise appropriate exceptions.
  5. You will probably want to write at least three functions:
    1. eval, a stub for which is provided,
    2. subst, a function implementing variable substitution
    3. check_closed, a function which determines whether or not an expression is closed. Remember that you must raise an exception if you are provided an expression which is not closed, such as Function x -> y.
  6. There are many implementations of interpreters for functional languages out there which ChatGPT and other friendly tools know about, but you need to hedge closely to the given operational semantics rules in your implementation. For example make sure you are using substitution for function application, etc. We will look over your code to verify this and a significant point deduction will apply for a different form of interpreter.
  7. Typing Printexc.record_backtrace true;; into utop will enable a stack trace to be dumped if your interpreter has a run-time error. If you start the standalone F♭ interpreter with the command line argument --show-backtrace it will accomplish the same thing.

Testing

We don’t provide a test suite but you can make your own or you can test your code against the reference interpreter on the examples in the fb_examples.ml file. Make sure to test the Y combinator examples, even if other things are working they may fail.

Submission

Upload only your fbinterp.ml file with your evaluator code to Gradescope.