Lab 6

The idea behind this lab is to develop functions that will be useful in developing your intuition for the syntax of the VVQS language.

More specifically, you must develop a simple "quiz" engine that displays legal VVQS expressions, and then challenges the user to produce the parsed representation.

This lab does not require you to do "testing" in the standard sense on any function except for the unparse function, which you should test thoroughly; the other functions you’re writing will be probabilistic, and will be difficult to test in a straightforward way.

Please note that the word "term" here means the same thing as "expression".

• Copy your ExprC definition from Assignment 5. If you haven’t finished it yet, go ahead and do that first. Just the ExprC part.

• The random and random-seed functions can be used to pick random numbers. Read their docs.

• Develop the function random-symbol that produces a random symbol from a fixed set of size 8. That is: define a fixed set of symbols, and write a function that returns one of them randomly.

• Develop the function random-base-term that produces a random expression that does not contain any other expressions. Choose randomly from the set of non-self-referential expressions. Use the random-symbol function to generate identifiers.

• Develop the function random-term that accepts a maximum depth and produces an expression tree whose depth does not exceed the given one. Use the random-base-term function in order to "bottom out". For function definitions and applications, use a random arity in the range 0-3.

  Please don’t worry about the fact that the terms you’re generating won’t evaluate correctly. For instance, they may add numbers to functions, or try to make a function call to a boolean, or have terrible arity issues. That’s no problem. The only thing that matters is that the range of your random-term function includes all well-formed expression trees with variables chosen from your specified set, and with no more than three parameters to functions, and with no more than three arguments to function calls.

• Develop the unparse function that takes a parsed expression and produces concrete syntax that corresponds to this, represented as an s-expression. This function is testable. Test it! Write the test cases before the function body!

• Develop the quiz function that generates a random term, prints its concrete syntax, and returns the term.

• Use this code to quiz yourself:

  (define secret (quiz))

  Each time you run the program, you get one challenge. When you evaluate secret, you see the answer.

• Now: quiz yourself!

1 Optional Super-PL Fuzzing Section

• OPTIONAL: Copy your interp function from Assignment 5, along with its helper functions. Try calling interp on one of your random terms.

• OPTIONAL: Write a recursive function run-trials that accepts a number of trials and a maximum depth and runs the given number of trials, calling interp on a random term each time. Use a try block to compute what fraction of random programs complete without an error.

• OPTIONAL: Refine your function random-term so that it only produces "closed" CFAEs: that is, those with no free variables. To do this, your function must accept a list of currently-bound variables, so that it can be sure to pick varrefs only from this list. Call this function random-closed-term.

• OPTIONAL: Can you shrink the language by omitting numbers, booleans, strings, and ’if’, and fixing the number of arguments at one so that no errors can occur? If so, can you search for a term that loops forever?