F♭ Interpreter
Due on Thursday, October 2nd 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 Courselore or contact the instructor. If you have any doubts about what is okay and what is not, it’s much safer to ask and learn than to guess!
Overview
In this lab, you will use OCaml to write an interpreter for the F♭ language. A framework has been provided, but you will be responsible for implementing the operational semantics.
Teams and Repositories
We will be using Teammaker to form groups to work on this assignment. When you log in to that system, you’ll have the opportunity to select someone to work with on each assignment in the course. (Assignments will be added to the list incrementally as the course proceeds.) The URL of your Git repository will appear in Teammaker once you a team has been formed. If you have any trouble getting access to your Git repository or questions about how this process works, please contact your instructor.
Implementing the 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/fb/fbast.ml) - A pretty-printer to display the results (in
src/fb/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/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 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. Note that the eval function should not evaluate open expressions. You’ll need to implement behavior to ensure that open expressions are met with an error as well.
You are not required to implement Let Rec, but you are encouraged to try!
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. 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/tests.ml. You can build your unit tests by running make tests.
Working Binaries
The binaries/ directory contains a working F♭ interpreter. You can run ./binaries/fb.exe 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.
Syntax Highlighting
The syntax-highlighting directory of your repository contains some small editor extensions to provide syntax highlighting for the F♭ language. You can create files with the .fb extension and run the interpreter on them (e.g. ./fb.exe my.fb or ./binaries/fb.exe my.fb). To install a syntax highlighting package, follow the instructions in the README.md file of the appropriate subdirectory for your editor. You do not necessarily need syntax highlighting for this assigment, but it will help if you decide to write a series of test files.
Submitting
It is not enough to push your work. In your repository, you will find a Python script called submit.py. In order to submit your lab assignment, it should be sufficient to run that script by typing python3 submit.py in your terminal. For this script to work correctly, you must have committed all uncommitted files in your repository and pushed your work so that your repository is in sync with your GitHub remote repository.
The aforementioned Python script is designed to create a Git tag: a name for a specific commit in your repository. (The script also performs a series of checks to help ensure that the tag you create contains what you likely think it contains.) The tag will be named using the words “submission”, the name of your assignment, and a version number. Your instructor will know that you have submitted your work because this tag will appear in your repository. If you need to resubmit your work to correct changes after receiving a grade, you can simply create new commits and then create another tag (preferrably with submit.py). At any given time, only your most recent outstanding submission will be graded.
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 lets me know whether I’m asking for the right amount of work and helps to ensure that it’s a good use of your time.
If You Have Trouble…
…then please contact your instructor! Courselore is the preferred method, but you can reach out via e-mail as well. Good luck!