HW5: Trefoil v3

This homework has three parts:

1. Port Trefoil v2 to be implemented in OCaml
2. Add structs and pattern matching to Trefoil
3. Write a reasonably substantial amount of code in Trefoil v3

Before you start: One more OCaml package

We decided to use one more OCaml package. Please run

opam install ppx_deriving

Otherwise, the starter code will not build.

Detailed tour of the starter code

You made it into the hw5/ subdirectory. Here's what you see.

• README.md: this file, your guide to HW5
• LANGUAGE.md: the specification for Trefoil v3
• FEEDBACK.md: our usual questions about homework, to fill out after you're done
• src/: OCaml files implementing and unit testing the interpreter

In src/ there are several files.

• trefoil3.ml: main entry point of the interpreter
  • Defines a main function that supports either keyboard or file input
  • In the local function loop, it parses one PST at a time, converts it to a binding, and then interprets that binding.
• errors.ml declares exceptions you will throw in various situations, similar to Trefoil v2
• pstparser.ml implements the same PST parser as we used on HW3, but now in OCaml.
  • You do not need to read or understand this file unless you want to.
• pst.ml declares the PST type in OCaml as a variant with two constructors, Symbol and Node.
  • You will need to read and understand (but not edit) the declaration of the pst type.
• ast.ml declares AST types for each syntactic category (expressions, bindings, and patterns).
  • ASTs are represented with variant types, as usual in OCaml.
  • There are also functions for converting PSTs into expressions, bindings, and patterns here.
• interpreter.ml implements the semantics of expressions, bindings, and patterns.
• trefoil3test.ml contains unit tests for the interpreter.

You only need to edit ast.ml, interpreter.ml, and trefoil3test.ml.

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, the struct binding, which declares a new struct type. For example, the binding (struct my-record name age) declares a struct called my-record with fields name and age. We have discussed this binding extensively in lecture. In short, it generates a constructor, a predicate function, and field accessor functions for each field.

Expressions

There are three new user-facing expressions, all of which we have discussed in lecture.

• Trefoil symbols, which are kind of like strings without spaces in them. They start with an apostrophe: '.
• cond expressions, which are a nicer syntax for nested if-else chains.
• match expressions, which implement pattern matching.
  • A big deal with match expressions is that they use patterns, which is a new syntactic category in Trefoil v3 (see below).

There are also three new "internal" forms of expression, which we have not discussed in lecture yet, but you will use to implement struct bindings. By "internal", we mean that there is no way for the Trefoil programmer to write these expressions directly in their code. Instead, when the Trefoil programmer writes a struct binding, your interpreter will autogenerate some functions that use these internal expressions in their bodies. Then the Trefoil programmer can call those autogenerated functions to indirectly use these new expressions. Here they are:

• struct constructor expressions, which represent the results of calling the struct constructor
• struct access expressions, which allow accessing fields of a struct constructor value
• struct predicate expressions, which tell you whether a value was built with a particular struct's constructor

See LANGUAGE.md for more details about the syntax and semantics of the internal expressions.

We also make a few changes to the Trefoil v2 semantics of expressions:

• The = operator now works on all values, not just integers.
• The semantics of function calls is extended so that you can "call a struct name" (which calls that structs constructor) in addition to "calling a function name" like normal. These two kinds of function call have the same syntax, and which one happens depends on whether the name being called is bound to a struct or a function. See LANGUAGE.md.

Patterns

Patterns are a new syntactic category in Trefoil v3 that represent "the left hand side of a match clause", similar to patterns in OCaml that you are used to using.

There are 8 kinds of patterns, which we have discussed informally in lecture, and which are discussed in detail in LANGUAGE.md.

Your tasks: An overview

We have left several TODOs throughout the code. Here is an overview of what there is to do. Part 2 is by far the most work, and it is worth more points. See the Grading section at the end of this file.

Part 1: Port Trefoil v2 to OCaml

• Implement the Trefoil v2 spec in OCaml.
• We have done 90% of the work for you already. You have quite a bit of code to read in the starter code.
• You need to fill in a few TODOs to complete the port.
  • We left out let expressions. Add them back in.
  • We didn't quite finish implementing function calls. Finish them.
  • We left out test bindings. Add them back in.
  • We ported the starter tests from HW3, but not much more than that. Add a few more tests.
• Find and explain a difference between your two implementations of Trefoil v2.

Part 2: Implement new Trefoil v3 features

• Implement the new extended semantics of =.
• Finish the implementation of cond.
• Add struct bindings and the three "internal" struct expressions.
• Add match expressions and patterns.

Part 3: Extending and using Trefoil v3

• Add your own feature.
• Write a fairly substantial program of your choice in Trefoil v3.

Suggested detailed workflow

Part 1: Port Trefoil v2 to OCaml

Familiarize yourself with the provided files.

• First, skim this whole file. Then, use the "file tour" above to skim the starter code. Pay special attention to ast.ml and interpreter.ml. Be sure you understand how ASTs are represented in OCaml as variant types, how dynamic environments are represented as association lists, and how the interpreters for expressions and bindings do their job.
• Install one more opam package:

  opam install ppx_deriving

• Ensure you can build the code by running dune build. (You can run this command either in the hw5/ directory or the hw5/src directory. It will do the same thing.)
  • dune build will report many warnings. This is expected. Most of the warnings have to do with unused variables in functions where you have a TODO to finish writing the function.
  • dune build should not report any errors.
• Ensure you can run the unit tests by running dune runtest. You should see a bunch of messages followed by FAILED 37 / 63 tests.
• You can use dune utop similar to HW4.
  • After dune utop, type open Trefoil3lib;;.
  • Then you can refer to functions from the file ast.ml by prefixing them with Ast. as in Ast.expr_of_pst. Or, if you don't like that, you can say open Ast;; and then refer expr_of_pst.
• You can also run the interpreter interactively by running

  dune exec ./src/trefoil3.exe

  from this directory. (Or, from the src directory, run dune exec ./trefoil3.exe.) You can also pass a filename to the interpreter like this

  dune exec ./src/trefoil3.exe my-program.trefoil

• Have a look at LANGUAGE.md to get an idea of the list of expressions, bindings, and patterns you will be implementing.

Add let expressions to the starter code port.

• Check out the provided expr type in ast.ml. It has one constructor for each kind of expression.
• Fix the TODO to add a constructor to expr representing let.
  • Hint: It should have the same information as the AST class for let expressions had in HW3.
• Check out the provided function expr_of_pst, also in ast.ml. It has the same purpose as Expression.parsePST from HW3.
  • Notice the way we have implemented the starter code. Every expression AST whose PST syntax is a PST Node has two cases in the inner pattern match -- one for the normal case and one for syntax error case.
    • For example, look at the cases for if expressions.
    • In the normal case, we use list patterns to match on the arguments and make sure the number is correct. For if, there should be three arguments.

      | Pst.Symbol "if", [branch; thn; els] -> (* and then construct the AST node *)

    • If the number is wrong, we fall through to the next case with a wildcard pattern.

      | Pst.Symbol "if", _ -> (* and then raise an AbstractSyntaxError *)

• Fix the TODO to add cases for let expressions in expr_of_pst
  • Warning/hint: let is more complicated than most of the other operators in Trefoil, because it has doubly nested parentheses. For example, it would not be correct to say "well, my let AST node has three arguments, so I'll just copy the cases for if expressions, which also have three arguments", because the PST syntax of lets has parentheses in weird places. You will need to exercise your knowledge of nested patterns to make sure you pare lets correctly!
• Check out the provided tests in trefoil3test.ml. Find the test that has a local variable "manually_constructed_let". This is a parser test for let expressions.
• Test your parser by fixing the TODO in trefoil3test about "manually_constructed_let" (see the comments there) and ensuring that the test now passes (you should see the number of failures decrease).
• Write a test or two to cover different ways that let expressions can be malformed. We have provided a template to help check that an abstract syntax error is thrown.
• Check out the provided function interpret_expression in interpreter.ml. It has the same purpose as Interpreter.interpretExpression from HW3.
  • As in HW3, the interpreter for expressions takes a dynamic environment as input, represented by the type dynamic_env, which is defined at the very top of interpreter.ml as an association list of (string, entry) pairs, where an entry is a variant type with constructors for variable entries, function entries, and struct entries.
    • One weird thing about the definition of entry and dynamic_env is that they are mutually recursive, meaning that the definition of entry refers to dynamic_env (in the arguments to FunctionEntry) while the definition of dynamic_env also refers to entry in its definition. Normally, this is not allowed in OCaml, because bindings are ordered, and can only refer to earlier bindings. But, it is useful sometimes in situations exactly like this to allow two bindings to both refer to each other. OCaml supports this through the and keyword used to separate the definitions of entry and dynamic_env. The keyword and replaces the keyword type, and it means "these are defined at the same time".
    • The key operation on dynamic_env is lookup, which is provided for you. We decided to make lookup return an option instead of throwing an exception because you might want to throw a different exception in different situations. So each call site of lookup will match and in the None case, throw an appropriate exception.
      • Notice that lookup traverses the list of pairs in left-to-right order and stops when it finds the first match. So adding a pair to the front of the list overrides any existing pair with the same key. This is key to how we will manipulate the dynamic environment below.
    • Check out the case for variables in interpret_expression. It calls lookup and uses nested patterns to handle three different cases: nothing found, variable found, and something besides variable found (function or struct).
• Fix the TODO to add a case for let expressions in interpret_expression.
  • Hint: Review the HW3 semantics of let expressions and your HW3 solution.
  • Hint: We have implemented the dynamic environment quite differently in OCaml than in Java. To extend the environment, simply cons (::) onto the front of it.
  • Hint: For inspiration, it may help to check out the (provided) case for top-level variable bindings in interpret_binding. It makes a similar manipulation of the dynamic environment. Note that let expressions differ from top-level variable bindings in that let expressions construct a temporary environment to evaluate the body, while top-level variable bindings construct a new environment which gets returned and propagated through the rest of the program.
• Ensure the three provided tests for interpreting let expressions pass. (You should see the number of failures decrease.)

Finish the starter code's implementation of function calls.

• Check out the expr constructor for Call (in ast.ml) and be sure you understand how it corresponds to the HW3 LANGUAGE.md syntax for function calls (and to your HW3 solution).
  • Function calls are already parsed for you. Check out the last case of expr_of_pst if you are curious.
• Back in interpreter.ml check out the starter code for Call expressions. We have handled the first few steps for you -- looking up the function name in the callenv and making sure that lookup returns a function binding.
  • The starter code contains a very important line that extends the defining environment with a recursive binding for the function being called. This is different than how we handled recursion in HW3, and avoids the need for mutation! :mind-blown:
• Fix the TODO to implement function calls.
  • Hint: Follow the same semantics as HW3.
  • Hint: Use the provided helper function interpret_expr_list to evaluate the list of argument expressions to a value.
  • Hint: Perhaps the hardest part is constructing the list of variable-value pairs that you want to extend the dynamic environment with. Remember this motto for OCaml programming:

    Whenever you feel like you need a loop, what you really need is a locally defined recursive helper function!

  • Hint: Define a local recursive helper function that takes the parameter names and argument values and returns a list of variable entries combining them. Then append this list on the front of the defining environment.
  • Hint: Don't forget to make sure your helper function signals a runtime error if the number of parameter names is different than the number of argument values. (You can do this without calling List.length if you are careful about it.)
• Many more tests should now pass. Ensure that all remaining failures have to do with test bindings, struct bindings, cond expressions, or match expressions. In particular, double check that the "basic function" and "lexical scope" tests pass.

Implement test bindings.

• Fix the TODO to add a constructor to the binding type in ast.ml for test bindings. Follow the abstract syntax of test bindings as defined in HW3.
• Parse test bindings in binding_of_pst in ast.ml at the location indicated by the TODO. Similar to expr_of_pst, you should have two cases: one that checks for the correct number of arguments and one that uses a wildcard to accept any wrong number of arguments and report an error
  • Hint: Check out the other cases in binding_of_pst for inspiration. In particular, variable bindings are pretty similar to test bindings, just without the variable. So the code should be pretty similar.
• Write a normal case parsing test and a malformed parsing test for test bindings by filling out the provided test templates "test binding parsing" and "test binding parsing malformed".
• Implement test bindings by fixing the relevant TODO in interpret_binding in interpreter.ml.
• Ensure the provided "simple test binding" and "failing test binding" tests pass.

At this point, you may want to read through the rest of the provided tests and play with the language a bit.

Find and explain a difference between your Java and OCaml implementations of Trefoil v2

• You now have implemented Trefoil v2 twice, in two very different metalanguages. Chances are, your two implementations are not perfectly equivalent.
• Find a difference in behavior between your two implementations.
  • If you are stuck, we have discussed a few examples in class.
    • Error messages
    • Integer overflow.
    • What happens when you write an infinite loop by accident.
  • Try to make the difference interesting and not on the list above if you can!
• Write an example Trefoil v2 program that demonstrates the difference.
• Explain the difference and your example program in FEEDBACK.md.

Part 2: Implement new Trefoil v3 features

Trefoil Symbols and Structural Equality

• Familiarize yourself with the syntax and semantics of Trefoil-symbol literals in LANGUAGE.md.
• Check out the provided AST declaration for symbols in ast.ml.
  • See the Symbol constructor of the expr type.
• Check out the provided parsing code in expr_of_pst in ast.ml
• Implement symbols in interpret_expr in interpreter.ml.
• Implement the new extended semantics of =.
  • Hint: This involves only deleting code from the starter code!!!
• Near the top of FEEDBACK.md, answer the question about structural equality.

Finish the implementation of cond.

• Familiarize yourself with the syntax of cond in LANGUAGE.md.
• Review the Cond constructor of expr in ast.ml and be sure you understand how it corresponds to the syntax of cond described in LANGUAGE.md.
• Parse cond by completing the TODO in expr_of_pst inside of the clause_loop helper function.
• Test the normal case and malformed case of parsing by filling out the test templates "cond parsing test" and "cond parsing malformed". Ensure these tests pass.
• Familiarize yourself with the semantics of cond in LANGUAGE.md.
• Interpret cond by completing the TODO in interpret_expression in the loop helper function inside the Cond case.
• Ensure the provided "sum cond" test passes.

Add struct bindings.

• Familiarize yourself with the syntax of struct bindings in LANGUAGE.md.
• We have already declared a constructor of binding for structs, called StructBinding, using the record type struct_binding. Be sure you understand how it corresponds to the syntax.
• Parse struct bindings by fixing the TODO in binding_of_pst.
  • Hint: Broadly, parsing structs is similar parsing function definitions, except that there are fewer parentheses and no function body expression.
  • Hint: Use check_symbols to convert field_names to a list of strings.
  • Hint: Use has_duplicates to check if the resulting list of field names has any duplicates. If it does, report an abstract syntax error.
    • Note: unlike functions, which cannot have the same name as one of their arguments, a struct is allowed (according to LANGUAGE.md) to have the same name as one of its fields. So the list you pass in to has_duplicates will be slightly different than how the starter code handles function bindings.
• Write a normal case parsing test and a malformed parsing test for struct bindings by filling out the provided test templates "struct binding parsing" and "struct binding parsing malformed".
• Familiarize yourself with the semantics of struct bindings in LANGUAGE.md.
  • Eventually we need to extend the dynamic environment with an entry for the struct binding, a function entry for the predicate function, and function entries for each field accessor function.
• Check out the case for StructBinding in interpret_binding.
• Fix the first TODO in this case by adding a mapping to the dynamic environment for the struct binding as a whole, using StructEntry.
• Now that the struct's name is bound in the dynamic environment, let's use it to implement the "constructor" functionality.
• Review the (internal) syntax of StructValue in LANGUAGE.md and the corresponding AST node in the expr type.
  • Since users cannot write StructValue in their programs, there is no need to parse it.
• Review the changed semantics of function calls in LANGUAGE.md.
• Back in the function call case in interpret_expression, fix the "part 2" TODO about "calling" a struct by following the semantics.
  • Hint: Be sure you signal a runtime error if the number of argument values is different than the number of fields of the struct.
• Ensure the provided "struct mynil constructor" and "struct mycons constructor" tests pass.
• Next, let's tackle struct predicate functions.
• Review the (internal) syntax of StructPredicate in LANGUAGE.md
• Define an AST node for StructPredicate in the expr type.
  • Since users cannot write StructPredicate in their programs, there is no need to parse it.
• Review the semantics of StructPredicate in LANGUAGE.md
• Implement the semantics of StructPredicate in interpret_expression.
  • You cannot test your implementation until you also implement predicate function generation in the semantics of struct bindings. Let's do that now.
• Review the semantics of struct bindings again, this time focusing on how struct predicate functions get generated.
• Back in the StructBinding case for interpret_binding, generate a function binding for the struct's predicate function.
  • Hint: The function's definition is described in LANGUAGE.md "as if by the binding ..." with a binding that is not valid user-facing syntax because it uses StructPredicate. So, you cannot use the parser to generate this binding, and you must instead construct it manually using the AST constructors for function bindings, StructPredicate, and variables.
• Ensure the provided test "struct mynil mycons predicate" passes.
• Finally, we will add struct field accessors. Review the syntax of StructAccess in LANGUAGE.md.
• Define an AST node for StructAccess in the expr type.
  • Since users cannot write StructAccess in their programs, there is no need to parse it.
• Review the semantics of StructAccess in LANGUAGE.md
• Implement the semantics of StructAccess in interpret_expression.
  • Be sure you signal an error if the value is not built from the same struct name as the access.
  • You cannot test your implementation until you also implement accessor function generation in the semantics of struct bindings. Let's do that now.
• Review the semantics of struct bindings again, this time focusing on how struct access functions get generated.
• Back in the StructBinding case for interpret_binding, generate function bindings to access each of the structs fields.
  • Hint: We have provided starter code for a locally defined recursive helper function that loops over the fields and calls fun_entry_for_accessor with the field name and field index. Implement this function by following LANGUAGE.md. As with struct predicates, since the AST nodes are "internal", you cannot use the parser to construct the binding. Call the AST constructors manually.
• Ensure the tests "struct mycons accessors" and "struct mycons accessors error case" pass.
• Ensure the test "cond struct binding sum countdown" passes.
  • This test uses cond as well as all three aspects of structs, so if you have a test failure here, be sure all the tests above are passing before debugging this one.

Add match expressions

• Skim the syntax of match expressions and patterns in LANGUAGE.md.
• The starter code at the top of ast.ml implements an AST for patterns. We have provided AST nodes for wildcard patterns (_) and cons patterns. There is also a parsing function as usual called pattern_of_pst, which we have implemented for the two provided patterns (plus given you some hints about other cases).
• All of this provided code about patterns is currently unused in the starter code, because the only place patterns appear in Trefoil v3 is in match expressions, and the starter code does not include match expressions. Let's fix that now.
• Review the syntax of match expressions in detail in LANGUAGE.md.
• Declare a new AST node for match expressions by adding a constructor in the expr type where the TODO is marked.
  • Hint: The AST node should be relatively similar to Cond, except that match takes a "scrutinee" expression as its first argument, in addition to a list of clauses. Also, a cond clause is two expressions, but a match expression is a pattern and an expression.
• Add a case to expr_of_pst to parse match expressions.
  • Hint: It is relatively similar to parsing cond, with the differences noted above. Use a local recursive helper function to parse the list of clauses which is similar to clause_loop in cond, except that it uses pattern_of_pst in one place instead of expr_of_pst.
• Test the normal case and malformed case of parsing by filling out the test templates "match parsing test" and "match parsing malformed". Ensure these tests pass.
• Skim the semantics of match expressions and patterns in LANGUAGE.md.
• The semantics of patterns is implemented in interpret_pattern in the starter code. We have implemented the semantics of wildcard patterns and cons patterns for you.
• Review the semantics of match expressions in detail in LANGUAGE.md.
• Implement match expressions in interpret_expression by fixing the TODO.
  • Hint: It is relatively similar to interpreting cond, with the differences noted above. After evaluating the scrutinee to a value, use a local recursive helper function to loop over the clauses. For each clause, check if the clause pattern matches the scrutinee's value by calling interpret_pattern. If yes, be sure to evaluate the right hand side of the clause in an appropriately extended environment. Unfortunately, you won't be able to test whether your environment is extended correctly until you add variable patterns.
• Ensure the provided tests "match expression with wildcards and cons 1" and "... 2" pass.

Add the remaining patterns

• The starter code only implements wildcard and cons patterns. Now let's add the rest.
• Skim the syntax of patterns again in LANGUAGE.md.
• You can do them in any order, but here's one order.
• Declare a pattern AST node for integer literal patterns by adding a constructor to the pattern type in ast.ml.
  • Hint: The AST node will have the same arguments as the one for integer literal expressions. That's because integer literals (also boolean literals, nil, etc.) are syntactically valid as both expressions and patterns. Don't get confused though -- they have different semantics depending on whether they are an expression or pattern!
• Parse integer literal patterns by fixing the first TODO in pattern_of_pst.
  • Hint: The starter code calls int_of_string for you. All you have to do is pass the result to your constructor.
• Skim the semantics of patterns in LANGUAGE.md.
  • In the semantics, patterns are described as returning "no" or "yes and B". In the code, we implement this using an option type, specifically

    dynamic_env option

    where "no" corresponds to None in the code, and "yes and B" corresponds to Some B in the code, where B is implemented as a list of string * entry, or in other words, a dynamic environment.
  • Review the semantics of integer literal patterns in detail.
• Implement integer literal patterns in the interpreter by adding a case to interpret_pattern.
  • Hint: You should not need to change interpret_expression at all, only interpret_pattern.
• Ensure the provided tests "match expression with int literal patterns" and "match expression with int literal patterns and cons" pass.
• Boolean literal patterns
  • Review syntax in LANGUAGE.md.
  • Declare AST node in pattern type in ast.ml.
  • Parse by adding cases in pattern_of_pst.
    • Hint: The starter code shows you where to add the case for "true". "false" is similar.
  • Review semantics in LANGUAGE.md.
  • Implement by adding a case to interpret_pattern in interpreter.ml.
  • Ensure provided tests "match expression with bool literal patterns 1" and "... 2" pass.
• Nil literal patterns
  • Review syntax in LANGUAGE.md.
  • Declare AST node in pattern type in ast.ml.
  • Parse by adding a case in pattern_of_pst.
  • Review semantics in LANGUAGE.md.
  • Implement by adding a case to interpret_pattern in interpreter.ml.
  • Write a simple test involving a nil pattern and ensure it passes.
• Trefoil symbol patterns
  • Review syntax in LANGUAGE.md.
  • Declare AST node in pattern type in ast.ml.
  • Parse by fixing the corresponding TODO in pattern_of_pst.
  • Review semantics in LANGUAGE.md.
  • Implement by adding a case to interpret_pattern in interpreter.ml.
  • Ensure provided test "match expression with symbol literal patterns" passes.
• Variable patterns
  • Review syntax in LANGUAGE.md.
  • Declare AST node in pattern type in ast.ml.
  • Parse by fixing the corresponding TODO in pattern_of_pst.
  • Review semantics in LANGUAGE.md.
  • Implement by adding a case to interpret_pattern in interpreter.ml.
    • Hint: This is the first pattern you implement where the bindings list is nonempty!
    • Hint: Use the VariableEntry constructor.
  • Ensure provided test "match expression with variable patterns" passes.
• Struct patterns
  • Review syntax in LANGUAGE.md.
  • Declare AST node in pattern type in ast.ml.
    • Hint: This is the most complicated kind of pattern in the language, because it has a list of sub-patterns. It also has a string (the name of the struct).
  • Parse by fixing the corresponding TODO in pattern_of_pst.
    • Hint: Parsing is challenging because of the list of sub-patterns.
    • Hint: It's sort of similar to parsing a function call expression. You may want to review that code in the starter code of expr_of_pst.
    • Hint: Use a locally defined recursive helper function to loop over the children and call pattern_of_pst on each of them.
  • Review semantics in LANGUAGE.md.
  • Implement by adding a case to interpret_pattern in interpreter.ml.
    • Hint: Be sure to check the struct name strings are equal!
    • Hint: The hard part again is the fact that the pattern has a list of sub-patterns, and the struct value has a list of sub-values. Use a local recursive helper functions to loop over these two lists "in lock step", matching each pattern against the corresponding value. Check that all the matches return "yes and ..." and append together all the bindings introduced.
  • Ensure provided test "match struct binding" pass.
• According to LANGUAGE.md, it is an error if any pattern in a match expression repeats a variable name. Fix this in your interpreter so that the test named "sum_with_match_error" passes.
  • Hint: In ast.ml, write a function vars_of_pattern that takes a pattern and returns a list of strings containing all the variable names that appear anywhere in the pattern.
  • Hint: In expr_of_pst in the case for match expressions, first parse the pattern, then check that vars_of_pattern applied to the parsed pattern returns a list with no duplicates. (Use has_duplicates.)

Part 3: Extending and using Trefoil v3

(Optional) Add your own feature to Trefoil v3

• (Optional) Design and implement your own feature in Trefoil v3.
  • Try to make your feature relevant to structs and/or pattern matching. Here are some ideas.
    • Add a new kind of pattern or improve match expressions.
      • In OCaml, you can use an "or" pattern, like this line from the starter code

        match e with
        | IntLit _ | BoolLit _ | Nil | StructConstructor _ -> e

        where the left hand side of the clause is the "or" of four different patterns.
        • Think about what happens if any of the sub-patterns of an "or" pattern contain variable patterns.
      • What about "and" patterns or "not" patterns.
      • Add nicer syntax for matching on lists, sort of analogous to matching on [p1; p2; p3] in OCaml.
        • If you do this, you might as well add it as an expression as well.
      • Add guards to pattern matching. In OCaml, you can write something like

        match foo with
        | x :: xs   when is_even(x) -> ...

        which only goes into the right hand side if the pattern x :: xs matches foo and if is_even(x) is truthy.
        • Think about what environment to evaluate the guard expression (is_even(x)) in.
        • Think about whether this feature should be a new pattern or an extension to the match expression. (What's the difference?)
          • In OCaml, it's an extension to match expressions, which is fine. But it would be even more "compositional" if you make it a pattern, so that it can nest.
    • Improve struct bindings in some way.
      • Make structs "generative".
        • Currently, if the Trefoil programmer declares two different structs with the same name, then the interpreter can get confused because it uses the declared name to decide if the struct matches a pattern or if a field access should be allowed.
        • "Generative" structs change the semantics of struct bindings so that each struct declaration is guaranteed to generate a separate type that can never be confused with another.
        • Design and implement this feature.
        • Start by writing a Trefoil program that declares two different structs with the same name but a different number of fields, and show that it can lead to confusing results where a struct predicate returns true but the struct accessor signals an error because the field index is out of bounds. After you implement generative structs, show that the struct predicate correctly returns false instead.
    • Add predicate functions for all the built-in types: int?, bool?, symbol?.
  • Or, if you have another idea unrelated to structs an pattern matching, go for it.
    • We prefer that you don't "just" port your feature from HW3. Feel free to do that! But then extend it somehow.
• (Optional) Describe the syntax an semantics of your feature in FEEDBACK.md.
• (Optional) Write a test that uses your new feature.

Write a substantial program in Trefoil v3

• Aim for 25 or more lines
• You are welcome to port an existing program from OCaml or Java.
  • For example, you could solve some HW2 or HW4 problems in Trefoil.
  • Or you could implement a tiny programming language in Trefoil.
  • Or anything else you like.
• Try to do something that use structs or pattern matching in an interesting way.
• Or, use a feature you added in an interesting way.
• Put your program in a file in this folder with a name ending in .trefoil and submit it with the rest of your code.
• Tell us the name of your file in FEEDBACK.md so we know where to look.
• Describe your program in FEEDBACK.md

Grading

330 "syllabus points" are available on this homework.

We try to give a detailed points breakdown below, but your homework will be graded manually, and we judge your work holistically as well. In practice this means you can get some points for doing well overall even if you mess up one part.

• 80 points for part 1
  • 20 points for declaring AST node, parsing, testing parsing, and interpreting let expressions.
  • 20 points for implementing function calls
  • 20 points for declaring AST node for, parsing, testing parsing, and interpreting test bindings.
  • 20 points for finding and explaining a difference between your two Trefoil v2 implementations, and for giving an example Trefoil program illustrating the difference.
• 160 points for part 2
  • 20 points for implementing the new semantics for = and answering the question in FEEDBACk.md.
  • 10 points for parsing, testing parsing, and interpreting cond.
  • 10 points for parsing, testing parsing, and mapping the struct name in the dynamic environment for struct bindings.
  • 10 points for implementing "calling a struct" to call the constructor.
  • 20 points for declaring the AST node, interpreting, and generating the user-facing wrapper binding for StructPreciate.
  • 20 points for declaring the AST node, interpreting, and generating the user-facing wrapper binding for StructAccess.
  • 30 points for declaring, parsing, testing parsing, and interpreting match expressions.
  • 10 points for declaring, parsing, and interpreting integer literal patterns.
  • 10 points for boolean literal patterns, nil literal patterns, and trefoil symbol patterns.
  • 10 points for variable patterns.
  • 10 points for struct patterns.
• (Optional) Up to 40 points for designing, implementing, and describing your new feature.
• 60 points for writing a substantial program in Trefoil and describing it in FEEDBACK.md.
• 30 points for filling out the "Feedback" section of FEEDBACK.md

Total points: 370, of which 330 are "on the syllabus" and 40 are optional/extra.

Submission

Submit your code to the HW5 assignment on Gradescope. If possible, we prefer you submit via the Gitlab button. See the instructions.