Lab 6

The idea behind this lab is to develop functions that will be useful in performing random testing on your solutions to Assignment 4 and beyond.

This lab does not require you to do "testing" in the standard sense; the functions you’re writing will be probabilistic, and will be difficult to test in a straightforward way. That is to say, you do not need to write any test expressions for this lab.

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

• Copy your ExprC definition from Assignment 3.

• The random and random-seed functions can be used to pick random numbers. To allow you to use the random and random-seed functions in plai-typed, import them like this:

  (require (typed-in racket

  [random : (number -> number)]

  [random-seed : (number -> void)]))

• Develop the function randomSymbol 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 randomBaseTerm that produces a random expression that does not contain any other expressions. Choose randomly from the set of non-self-referential expressions. Use the randomSymbol function to generate identifiers.

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

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

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

• Refine your function randomBaseTerm to randomClosedTerm 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.

• OPTIONAL: Can you shrink the language by omitting numbers, binops, booleans, 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?