HW5: Trefoil v2

Get the starter code.

Due: Friday, November 17, 11:59pm Pacific Time

This homework is the next step in our Trefoil journey. You will implement an interpreter for version 2 of Trefoil, which supports nested syntax based on parenthesized symbol trees (PSTs). (Everyone in the world except for us calls PSTs S-expressions, in case you want to Google.)

Detailed tour of the starter code

This tour is careful to discuss every file, so you might want to only skim this tour on first reading.

• ast.ml: represents the abstract syntax tree (AST) of expressions and bindings
  • Expressions:
    • For every kind of expression in the language, there will be a constructor of the variant type expr, similar to the examples like IntLit, Plus, etc. in the starter code.
    • We will ask you to use the existing expr variants as well as add several new ones.
    • The function expr_of_pst converts (or tries to convert) a PST into an expression AST.
      • For each variant of expr there should be a case in expr_of_pst that produces it from the corresponding PST.
      • Check out the examples in the starter code of symbol keywords and operators. We will ask you to add more of each kind of keyword as you produce new ASTs that you add.
  • Bindings:
    • For every kind of binding, there is a constructor of binding.
    • You will need to understand the existing bindings.
    • We will ask you to add one new top-level binding.
• dune: the build file
• errors.ml
  • This file declares several exceptions, which you will need to raise at various places.
• interpreter.ml: the interpreter!!
  • Interprets expressions and bindings in the context of a dynamic environment.
  • You will need to understand the starter code in this file thoroughly. Your primary task is to extend it.
    • interpret_expression evaluates an expression to a value in a given dynamic environment
    • interpret_binding transforms and returns a dynamic environment as the result of executing the given binding
    • You will extend both of these functions with several new cases.
  • This file also defines the dynamic_environment type, which implements a map from strings to values.
• pst.ml: represents a PST
  • You will need to understand and use (but not edit) the pst type defined in this file.
• pstparser.ml implements a parser for PSTs that you do not need to understand or edit. Of course, you are free to read the file if you are curious how it works. It is not too complicated.
  • The primary entrypoints to this file is parse_pst and pstparser_of_source
• trefoil2.ml: main entry point of the interpreter
  • Skim the main function. We won't ask you change it, but it might be useful for debugging (see comments)
    • The main function supports either keyboard or file input. If you pass a file name on the command line, then it will read input from that file. Otherwise, it will read input from standard input.
    • It constructs a pstparser and then repeatedly reads PSTs off the input
    • For each PST, it parses it as an AST using Ast.binding_of_pst, and then interprets the binding.
    • This is the semantics of Trefoil v2 programs!
    • At the end of the program, main prints the final environment.
• trefoil2test.ml: defines several starter tests
  • You will need to understand how the tests are set up so that you can debug failing tests and write your own new tests.

A note on deriving

The starter code uses the [@@deriving show] annotation, which automatically generates "toString" like functions for various types.

You need to install this feature with

opam install ppx_deriving

Please ask questions on Ed if you get stuck!

Informal description of the language

A Trefoil v2 program is a sequence of bindings which are evaluated in order in a (initially empty) dynamic environment. The environment can be transformed by each binding as that binding executes.

Bindings

There are three kinds of bindings: variable bindings, top-level expressions, and test bindings.

We have discussed all but test bindings in lecture. See the slides and demo code for an informal description of those. See the Trefoil v2 language spec for a formal description.

Test bindings are written like this example:

(test (= 3 (+ 1 2)))

A test binding evaluates its expression. If expression evaluates to true, the test passes and nothing happens to the environment. If the expression evaluates to anything other than true (false or any other value, e.g., 17), the test fails and a (nice) error is reported to the Trefoil programmer.

Expressions

There are 15 kinds of expressions. See the lecture material for an informal introduction and the spec for a formal list and description.

The only expressions we did not discuss in lecture are:

• Equality on integers, written (= (+ 1 2) 3). = is a binary operator that takes two integers, just like + does, except that = returns a boolean indicating whether its arguments are equal. Note that = only works on integers. It is a runtime error to pass anything besides an integer to =.
• Checking if a value is a pair, written (cons? (+ 1 2)). cons? is a unary operator similar to nil? that returns true if its argument is a pair. Unlike nil?, which returns true only on nil, there are many different values on which cons? returns true: for example, (cons 0 1), (cons true (cons false nil)), etc.

Your tasks

Complete the starter code to implement the Trefoil v2 language as specified. Write tests that cover the normal and error case behavior for all language features.

We have left several TODOs for you throughout the code.

Suggested workflow

You can do anything in whatever order you want, but here is one suggested path.

Familiarize yourself with the provided files:

• Skim this handout without looking at the starter code.
• Then go back and read the "detailed tour" section of this handout more carefully and poke around at the starter code files so you know where too look later.
• Run opam install ppx_deriving if you haven't already.
• Run dune build ensure there are no errors.
• Run dune test to run the tests in trefoil2test.ml and ensure that 26 tests fail out of 34. (!) The passing tests are due to features we have implemented for you in the starter code.
• Look at the Trefoil v2 language spec to get an idea of the list of expressions and bindings you have to add.

Implement new expressions:

• Start with true. The AST node is already defined (BoolLit), and expr_of_pst is done for you in the starter code in ast.ml. All that's left is to implement the case in interpret_expression in interpreter.ml.
  • Hint: it is similar to the case for IntLit
  • Ensure that the test called "interpret_true" passes.
• Now implement with false.
  • The AST node is the same as true, just with a different value for its argument.
  • This time, you have to implement the case in expr_of_pst.
    • Hint: it is similar to the case for true.
    • Ensure that "parsing_false" passes.
  • Make sure your interpreter handles false as well. Depending on how you handled true, you may not need any code changes.
  • Ensure that "interpret_false" passes.
• Implement - and *. They are similar to +.
  • First, define their AST variant constructors by copying Plus and renaming it.
  • Next, extend expr_of_pst with cases for - and *.
    • Write tests analogous to "parsing_false" but for - and *.
      • You can compare the parsed result with a manually constructed AST by calling Minus(IntLit 3, IntLit 17) or whatever.
      • Ensure these tests pass.
  • Finally, extend interpret_expression with cases for - and *.
    • Ensure that "interpret_minus" and "interpret_times" pass.
  • Write error tests for minus and times that check for incorrectly typed arguments, and ensure your new tests pass.
    • Be sure you are handling type errors for these operators just like you are for +. You must throw RuntimeError and not anything else.
    • Hint: see "test_plus_wrong_types" for a similar example
  • Write error tests for minus and times that check what happens when too few or too many arguments are given. Ensure they pass.
    • Be sure you are handling abstract syntax errors for these operators just like the starter code handles them for + in expr_of_pst. You must throw AbstractSyntaxError and not anything else.
    • Hint: see "test_plus_abstract_syntax_error"
• Implement = following the workflow below.
  • Remember that this operator only works on integers!!!
    • The interpreter should throw RuntimeError if = is given anything other than integers.
  • Workflow for all new expression forms
    • Be sure you understand the syntax and semantics as specified in the Trefoil v2 language spec.
    • Declare new AST variant constructor
    • Write new case in expr_of_pst
    • Write a test for the new case in expr_of_pst by comparing it to a manually constructed AST, and ensure the test passes.
    • Write new case in interpret_expression.
    • Ensure that the provided normal case test for this expression passes (if any).
    • Write (additional) normal case tests to cover all behavior of the feature.
    • Write error case tests for the feature covering the following:
      • wrong type of data passed as argument (should throw RuntimeError)
      • wrong number of arguments passed to primitive operation (should throw AbstractSyntaxError)
• Implement if following the workflow.

Implement the new test binding:

• Implement the test binding using this modified workflow.
  • Since test is a binding not an expression:
    • Declare the new AST variant constructor of binding.
    • Extend binding_of_pst instead of the similar function for expressions
    • Extend interpret_binding instead of the similar function for expressions
  • Ensure the provided tests with "test binding" in their name pass.
  • Still write a binding_of_pst test with a manually constructed AST
  • Write any additional normal case or error case tests you think are appropriate and ensure they pass.

Finish implementing the other expressions:

• Implement let following the workflow.
  • Ensure the "test let..." tests pass.
• Implement nil, cons, nil?, cons?, car, and cdr following the workflow for each.
  • No provided tests for nil? and cons?. You should write both normal and error case tests for these.

Implement your own feature (optional):

• Design and implement a new expression or binding.
  • Spend as much or as little time as you want on this. It's fine if your feature is super simple. It's also fine to skip this part. It is for just a couple of bonus points. Save some creative energy for later in the quarter, where we will ask you to do a more substantial feature of your own choosing.

Submission

• Submit these files to Gradescope:
  • ast.ml
  • interpreter.ml
  • trefoil2test.ml
• Congrats! You finished a "real" interpreter!!