F♭ Interpreter and F♭ Programming
Due on Wednesday, February 26th at 11:59 PM. This is a team lab. You may work alone or you may work with a partner. If you’d like to work with a partner, make sure to indicate your preferred partner using Teammaker and be familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.
Overview
This lab contains two major components. First, you will write an interpreter for the F♭ language. Second, you will write some programs in F♭ to demonstrate your understanding of encodings.
As in the last assignment, we will be using Teammaker to form groups to work on this assignment.
Part I: F♭ Interpreter
Your repository contains starter code for an F♭ interpreter. Most of the components of the interpreter are already provided:
- A parser to turn text into an AST
- An AST data type to represent F♭ expressions (in
src/fbast.ml) - A pretty-printer to display the results (in
src/fbpp.ml) - A toploop to allow you to experiment with F♭
- A command-line interface to permit you to run files
One key component that is (intentionally) missing from this software is the evaluator. The file src/fbinterp.ml contains a simple function eval which is meant to evaluate an F♭ AST into a value. Presently, it just returns the expression in an unevaluated form.
Your task for the first part of the assignment is to implement the eval function according to the language specification provided in Section 2.3 of the book. Your eval function must implement precisely the F♭ language that is defined by the evaluation relation discussed in that section. In cases in which evaluation is undefined, you should raise the TypeMismatch exception declared in that same file.
You are not required to implement Let Rec, but you are encouraged to try and you will receive a small amount of extra credit if you succeed.
Developing the F♭ Interpreter
In order to compile your F♭ interpreter, simply run make from the root of your project. This will produce, among other files, a program fb.byte. Running that program without any arguments will launch the F♭ toploop.
The F♭ toploop is similar to the OCaml toploop in that each valid expression separated by ;; is evaluated and the result is printed. This evaluation is handled by the eval function of src/Fb/fbinterp.ml, so it won’t actually evaluate anything until you’ve implemented that function. Unlike the OCaml toploop, there is no declaration syntax (e.g. let x = 4;;); all inputs must be expressions (e.g. Let x = 4 In x) and all expressions are evaluated independently.
Note that, in order to implement your interpreter, you’ll need to write more than just an eval function. You can include as many helpers in fbinterp.ml as you like. One good candidate, for instance, would be a helper function to perform variable substitution.
If you would like to write unit tests for any of your code, you may do so in the file src/tests.ml. You can build your unit tests by running make tests.byte.
Experimentation
If you want to experiment with your code, you can create executables other than fb.byte. For instance, you could create a file src/sandbox.ml with the following contents:
open Fbast;;
let e : expr = Plus(Int 4, Int 2);;
let v : expr = Fbinterp.eval e;;
print_endline (Fbpp.pretty_print v);;
You can then run make sandbox.byte in order to create an executable which will build that program. If you write complicated code in an environment like this, you are strongly encouraged to turn it into a unit test. This approach can be useful, though, if you want to print-debug or step-debug (via ocamldebug) an OCaml code snippet which uses your interpreter.
Working Binaries
The binaries/ directory contains a working F♭ interpreter. You can run ocamlrun binaries/fb.byte to get a sense as to what your implementation should do. Note that this should not be your primary way of understanding how F♭ behaves; if you have any questions about the definition of the F♭ evaluation relation, you should consult the definition in the book. This binary interpreter is meant to permit you to experiment so you can check your understanding.
Part II: Writing F♭ Programs
Your repository also contains a file encodings.fb. This file contains F♭ definitions in the form of a series of Let ... In ... expressions. It also contains a number of comments directing you to write several definitions in F♭. Your task for this part of the assignment is to complete the work described by the encodings.fb file by writing the definitions correctly.
After the last In in the encodings.fb file, there is initially the expression 0. You may replace that expression with whatever test expression you like and then run the entire file by running ./fb.byte encodings.fb from the command line. This provides you a means to test your various definitions without resorting to copying and pasting your code into the F♭ toploop. You will not be graded on anything that appears in that position of the file.
You are strongly encouraged to write and test your encodings.fb definitions one at a time and to commit each definition once you have completed it. Since this is a single large file in a language for which we have poor development tools, finding e.g. a missing parenthesis could be extremely difficult. It’s much easier to find these sorts of problems when you’re making small increments of progress.
Syntax Highlighting
Your instructor uses the Atom text editor to prepare these assignments and so found it convenient to write an Atom syntax highlighting package for F♭. If you would like to use that same package, it appears in this repository. The following command should be sufficient on CS network computers to install that Atom package for use in your editor:
cp -a fb-atom/language-fb ~/.atom/packages
After running that command, reload your editor window (Ctrl+Shift+F5 or just Ctrl+Shift+P and type “reload”) to get syntax highlighting in .fb files.
Submitting
To submit your lab, just commit and push your work. The most recent pushed commit as of the due date will be graded. For more information on when assignments are due, see the Policies page.
Lab Questionnaire
In addition to completing the lab itself, you’ll also need to complete a questionnaire describing your experience in the lab. Under most circumstances, this questionnaire will take only about a minute to complete and is part of your participation grade. Please make sure to do this; the information is useful to develop the course and the credit you get is basically free!
If You Have Trouble…
…then please contact your instructor! Piazza is the preferred method, but you can reach out via e-mail as well. Good luck!