HW6: Trefoil v3

Due: Wednesday, November 29, 11:59pm Pacific Time

This homework is the next step in our Trefoil journey. You will implement an interpreter for version 3 of Trefoil, which extends version 2 to support functions and a few other features.

Refactoring your previous interpreter.

You should start by making a copy of your hw5 solution and then making the following changes:

• Rename the file trefoil2.ml to trefoil3.ml.
  • Change the line at the top from

    open Trefoil2lib
    

    to

    open Trefoil3lib
    

  • Change the welcome message near the bottom from saying "v2" to "v3"
• Rename the file trefoil2test.ml to trefoil3test.ml.
  • Change the line at the top from

    open Trefoil2lib
    

    to

    open Trefoil3lib
    

• Replace the src/dune file with the updated file from the HW6 starter code.
• Copy-paste the contents of the newtests.ml file into your trefoil3test.ml file. These are additional provided tests for the new features.

Informal description of the language

The Trefoil v3 language is an extension of Trefoil v2. We only describe the differences.

Bindings

There is one new kind of binding, a function binding. We discussed it informally in lecture. For a formal description, see the Trefoil v3 language spec.

Dynamic environment

In order to support function bindings, the dynamic environment maps names to entries, which can be either a variable entry or a function entry, as discussed in lecture.

Expressions

• We update let expressions to support binding multiple bindings as discussed in lecture.
  • Note that bindings cannot refer to other variables being bound by the same let expression.
• We introduce a new cond expression for multiway branching as discussed in lecture.
• We add function calls as discussed in lecture.

Your tasks

1. Extend your previous homework solution to implement the changes described in the Trefoil v3 language spec. Write tests that cover all the normal and error case behavior for all new language features.

   We highly recommend keeping your tests from HW5 around to help you find bugs. You do not need to resubmit tests that you submitted for HW5, but you can if you want to.

2. After your Trefoil v3 interpreter is working, write a trefoil program of your choosing that is at least 10 lines long and uses at least 2 new features from v3. Put this in a file called hw6.trefoil and turn it in.

3. Write a paragraph describing an idea for a final project. Both this task and the final project are optional. You can change your mind about whether to do the final project at any point.

   Some ideas:

   • Extend Trefoil with a new feature
   • Invent a different way of writing Trefoil programs (perhaps fewer parens?) and implement a parser.
   • Create a statically typed version of Trefoil
   • Create a compiler for Trefoil
   • Design and implement a different language not based on Trefoil (or partially based on Trefoil)

   With all of these ideas, it would be easy to go overboard and propose a project that is too big. Try to propose something that you could do in a week while you are also busy with your other end-of-quarter tasks.

   Describe your idea in one paragraph or so. Put your description in a file called proposal.txt and turn it in.

   Submitting a project proposal will earn you a small number of bonus points.

Suggested workflow

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

• Look at the Trefoil v3 language spec to get an idea of the list of expressions and bindings you have to add.
• Refactor your HW5 code by following the instructions above for copying your HW5 code and changing a few 2s to 3s if you haven't already.

Update the dynamic environment to support "entries":

• Edit the definition of type dynamic_env at the top of interpreter.ml to introduce a type called env_entry that is defined simultaneously with dynamic_env.
  • Hint: Review lecture 19 to get started. You will need to adapt this code to support functions with any number of arguments.
• Adapt the function string_of_dynenv_entry from the HW5 starter code so that it works with your new env_entry type. This function is called by trefoil3.ml and your code will not build without it.
• Update the Variable case in interpret_expression to take entries into account.
  • Hint: Use pattern matching to see what kind of entry the name maps to. Review the spec to see what to do in case of an unexpected kind of entry.
• Update the VarBinding case of interpret_binding to take entries into account.
• Your code should now build and all your HW5 tests should pass.

Extend let.

• Change the AST node for let to support multiple variables.
• Update the expr_of_pst case for let to support multiple variables and return your updated AST node.
• Update the interpret_expression case for let to support multiple variables according to the semantics in the spec.
• Update any existing tests of let that you copied from HW5 so that they compile with the new AST node.
• Ensure the provided tests "multi var let", "no var let", and "let swap" pass.
• Write a normal case parsing test for let that compares the output of expr_of_pst to a manually constructed AST. Be sure to exercise multiple variables in your test.
• Write an error case test for a let expression that tries to define the same variable twice within a single let expression. The test should check that an abstract syntax error is thrown.
• Write additional normal or error case tests to cover any other new behavior of let.

Implement cond.

• Define an AST node for cond.
  • Hint: review lecture 20.
• Add a new case to expr_of_pst to parse cond expressions.
  • Hint: You will need to loop through the children of the cond PST. You can use a locally defined recursive helper function, or you can use a higher order function from the standard library.
• Write a parsing test for cond and ensure it passes.
• Add a new case to interpret_expression that implements the semantics of cond.
  • Hint: You will need to loop through the children of the cond AST.
• Ensure the provided tests "basic cond", "empty cond", and "cond parsing malformed" pass.
• Write additional normal case and error case tests to cover the behavior of cond.

Implement function bindings.

• Define an AST node for function bindings.
  • Hint: review lecture 19 to get started. You will need to adapt this code to support functions with any number of arguments.
• Add a new case to binding_of_pst to parse function bindings.
• Write a parsing test for function bindings and ensure it passes.
• Add a new case to interpret_binding that implements the semantics of function bindings.
  • Hint: review lecture 19 and the Trefoil v3 spec.
• You won't be able to test it easily until you implement function calls (below).

Implement function calls.

• Define an AST node for function calls, following lecture 19.
• Add a new case to expr_of_pst to parse function calls
  • Hint: replace this line from the HW5 starter code with your function call parser! All unrecognized operators are parsed as function calls in Trefoil v3.
• Write a parsing test for function calls and ensure it passes.
• Add a new case to interpret_expression that implements the semantics of function calls.
  • Hint: review lecture 19 and the Trefoil v3 spec.
  • Hint: no, really, read the spec carefully.
• Ensure all remaining provided tests pass:
  • "basic function"
  • "lexical scope"
  • "pow"
  • "car_cdr_countdown"
  • "sum_countdown"
  • "sum_cond"
• Write additional normal case and error case to cover function calls and function bindings.

Write some Trefoil.

• Write a small-but-not-tiny Trefoil program as described in task 2.

Brainstorm project ideas.

• Write a paragraph describing an idea for a final project as described in task 3.

Submission

Submit these files to Gradescope:

• ast.ml
• interpreter.ml
• trefoil3test.ml
• hw6.trefoil
• proposal.txt if you want to propose a project