### Problem Set 2

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

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.

(define-language tree-lang (t l ; leaf (t * t)) ; composite (l string))

Define five sample trees, with at least three composites.

count, which counts the number of leafs in a tree;

cat, which concatenates all the strings in a tree from left to right;

substitute, which replaces all occurrences of some old leaf for a new in some tree;

height, which determines the height (maximal distance from root to any leaf) of a tree;

dive, which replaces all leaves with their distance to the root.

(define-language Graph (g (graph n ...)) (n (node x connects-to x ...) (node x)) (x variable-not-otherwise-mentioned)) (define g1 (term (graph (node a connects-to b c) (node b) (node c)))) (define g2 (term (graph (node a connects-to b c) (node b))))

> (redex-match? Graph g g1) #t

> (redex-match? Graph g g2) #t

Design the function good, which determines whether or not a Graph g mentions only names on connects-to clauses that also name a node.

An Expression is one of: |

-- Variable |

-- (function Variable Expression) |

-- (Expression Expression) |

A Variable is a String. |

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

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

Deliverable (Revised Wed Jan 15 12:24:04 EST 2014) Email a tar.gz bundle to my CCS email address whose name
combines the last names of the pair in alphabetical order. The tar bundle
must contain a single .rkt file—

;; NameOfPartner1, NameOfPartner2 |

;; email@of.partner1.com, email@of.partner2.org |