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:

`how-many`, which counts the number of leafs in a tree;
`sum`, which sums up all the numbers in a tree;
`replace`, which replaces all occurrences of some `old`
leaf for a `new` in some tree;
`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.

`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:

`fcount`, which counts the number of strings in a forest;
`freplace`, which replaces all numbers in a forest with their equivalent strings;
Hint: Experiment with `number->string`.

`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.