### Problem Set 2

Due Tuesday, February 2, 2016 at 1pm

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.

A mobile is a type of kinetic sculpture constructed to take advantage |

of the principle of equilibrium. It consists of a number of rods, from |

which weighted objects or further rods hang. The objects hanging from |

rods balance each other, so that the rods remain more or less horizontal. |

Each rod hangs from only one string, which gives it freedom to rotate |

about the string. |

A Mobile is one of: |

-- a Weight |

-- a composite of two Mobiles and a Weight |

A Weight is a natural number (0, 1, 2, ...). |

Interpretation: The weight in the first clause represents an |

"atomic" sculpture; it is a number indicating how much that |

sculpture weighs. The weight in the second clause represents |

the weight of the beam connecting the two Mobiles. |

(define-language mobile (m w ; atomic sculpture (weight) (m m w)) ; composite (w number)) ; weight is a number

Define five sample mobiles, with at least three composites.

num-atomics, which counts the number of atomic sculptures in a mobile;

total-weight, which determines the total weight of a mobile;

depth, which determines the maximal number of links from the top of a mobile to one of its atomic sculptures;

replace, which replaces all atomic sculptures with an old weight with atomic sculptures of a new weight in some mobile;

balanced?, which determines whether or not a mobile is balanced. A mobile is balanced if the weight of the mobile on one end is equal to the weight of the mobile on the other end. The weight of a mobile naturally includes the beams.

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

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

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

Design the function good, which determines whether or not the edges in a Graph g mention only names that also name a node in g.

An Expression is one of: |

-- Variable |

-- (function Variable Expression) |

-- (Expression Expression) |

A Variable is a String. |

An DBExpression is one of: |

-- Number |

-- Variable |

-- (function Variable DBExpression) |

-- (DBExpression DBExpression) |

A Variable is a String. |

Design db. The function consumes an Expression and produces a DBExpression. For each variable introduced by the first clause in an Expression, db replaces it with the number of function nodes between it and the closest enclosing function node that comes with the same variable. If there is no such node, the variable is left unchanged in the output.

(function "y" |

((function "x" |

("x" "y")) |

("x" "y"))) |

(function "y" |

((function "x" |

(0 1)) |

("x" 0))) |

Note This problem is already a true exercise in modeling programming languages.

Deliverable 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 |