Due date: 9/21 @ at the beginning of class

Purpose: The goal of this problem set is to acquire basic competence in designing metafunctions.

Constraint: Your solution must use the Redex programming language for all problems. The function may escape to the Racket programming language for simple tasks like multiplying two numbers or determining the length of a list.

---

Problem 1:

Here is a data (language) definition for trees over numbers:

      (define-language tree-lang 
	(t l        ;; leaf 
	   (t + t)) ;; composite 
	(l number))
    

Define five sample trees, with at least three composites.

Design the following functions:

1. how-many, which counts the number of leafs in a tree;
2. sum, which sums up all the numbers in a tree;
3. replace, which replaces all occurrences of some old leaf for a new in some tree;
4. depth, which determines the maximal depth of all leaves in a tree;

   Def.: The depth of a leaf is the number of +s between the leaf and the root of the tree.

5. dive, which replaces all leaves with their depth.

Problem 2:

Here is a data (language) definition for forests over strings and numbers:

      (define-language forest-lang 
	(f (t ...))
	(t l (t * t))
	(l number string))
    

Define five sample forests, with at least three composites.

Design the following functions:

1. fcount, which counts the number of strings in a forest;
2. freplace, which replaces all numbers in a forest with their equivalent strings;

   Hint: Experiment with number->string.

3. fdive, which replaces all leaves in a forest with their containing tree's distance to the first tree in the surrounding forest.

   Def.: The distance between two trees in a forest is the number of trees between them.

Problem 3:

Develop a Redex language definition for the following toy subset of the Lisp/Scheme/Racket language, presented with a Java-style grammar notation:

An Expression is one of:

• Variable
• (function Variable Expression)
• (Expression Expression)

A Variable is a String.

The token function is the only keyword in the language.

Design fv. The function consumes an Expression in the above language. It replaces all free Variable occurrences with "free" and all others with "bound".

Def: A Variable v is free in an Expression if it is not contained within a function expression whose second part is v.

Deliverable:

Send in a single Racket file. Its name should consist of the two last names in alphabetical order separated with a hyphen; the suffix is of course .rkt.

Your file must start with the following two lines:

  ;; NameOfPartner1, NameOfPartner2 
  ;; email@of.partner1.com, email@of.partner2.com

appropriately instantiated of course. Also separates problems with lines of the shape ";; " followed by 77 "-". That gives you a width of 80 chars. Try to stick to this width for all code; it ensures basic readability.