F♭ Interpreter and F♭ Programming
Due on Wednesday, February 28th 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: The F♭ Development Kit
Your repository contains a copy of the F♭ Development Kit. This software provides a number of components for your F♭ interpreter:
- A parser to turn text into an AST
- An AST data type to represent F♭ expressions (in
src/Fb/fbast.ml) - A pretty-printer to display the results
- 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/Fb/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, 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 tests/tests.ml. You can build your unit tests by running make tests.byte.
Your Code and the OCaml Toploop
If you want to interact with your code in the OCaml toploop, you can do so by starting an OCaml toploop in the root directory of your project. In the toploop, run #use "debugscript/fb.ml";;. That command will automatically load the compiled F♭ interpreter files into the toploop so that you can call your helper functions and other tools directory from within OCaml.
Boolean Expressions
The F♭ Development Kit also includes a complete implementation of an interpreter for boolean expressions. Check the contents of the src/bool/ directory for an example of how an interpreter might be defined.
Working Binaries
The binaries/ directory contains a number of .byte files. These are compiled, working implementations of various interpreters we will discuss throughout the semester. In particular, binaries/fb.byte is a working implementation of the F♭ interpreter you are writing for this assignment. If you have any questions about the correct behavior of F♭’s evaluation relation, you really should consult the definition in the book. That said, the interpreter is provided here to allow you to experiment. To run this file, invoke it like so: ocamlrun binaries/fb.byte.
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 presently 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.
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.
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!