CS 7400 Machine Problem 3: Extending a Language

Out: Thursday, 10/1/09

Due: Thursday, 10/8/09

For this machine problem, you will extend a language discussed in class. Please note the requirement on page 40 of EOPL3:

In the following exercises, and throughout the book, the phrase ``extend the language by adding...'' means to write down additional rules or equations to the language specification, and to implement the feature by adding or modifying the associated interpreter.

For this problem, you will modify the systems found in /course/cs7400/interps/lecture03/letrec-lang.

With this language as a basis, do the following. Each problem is worth 10 points. Turn in your solution as a single set of PLT Scheme modules containing all these extensions.

  1. Exercise 3.9 (lists)
  2. Exercise 3.18 (unpacking lists)
  3. Exericse 3.14 (Bool-exps)
  4. Exercise 3.8 (numeric predicates)
  5. Add to the language the following construction: 
    Bool-exp ::= allof Bool-exp {and Bool-exp}* end
    This expression takes the conjunction ("and") of several boolean expressions, such as 
    allof zero?(x) end
allof zero?(x) and zero?(y) end
allof zero?(x) and zero?(-(y,1)) end
allof zero?(x) and not(zero?(y)) and zero?(-(u,x)) end
    This is to evaluate the expressions from left to right, and produce a true value iff all expressions have a true value, so that one could write an expression like if allof x and y end then x else z. It is, however, a "short-cutting" operator: if one expression gives a false value, then the rest of the expressions should not be evaluated. Here are a few tests to get you started: 
    (allof-1-arg-1 
   "if allof zero?(0) end then 3 else 4" 
    3)

(allof-2-get-second
    "
let x = 0 in let y = 1 
in if allof zero?(x) and zero?(y) end
      then 33 else 44"
    44)

(allof-2-check-shortcutting
   "
let f = proc (x) aha   % raises error if called
in if allof zero?(1) and (f 1) end
   then 3 else 4"
   4)

Be sure to add enough test items to the test suite so that your extensions will be adequately tested. As before, you will be evaluated on the quality of your test suite.

Your tests should include the following: Write and test a procedure "remove" in the defined language. "remove" should take a number n and a list of numbers lon, and produce a list like lon except that there are no occurrences of n.

Last modified: Thu Oct 22 14:12:16 -0400 2009