Due Tuesday, January 31, 2017 at 2pm
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.
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:
-- (function Variable Expression)
-- (Expression Expression)
A Variable is a String.
An DBExpression is one of:
-- (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.
Note This problem is already a true exercise in modeling programming languages.
Deliverable Email a tar.gz bundle to me and Max New at our CCS email addresses. The name of the bundle should combine the last
names of the pair in alphabetical order. The tar bundle must contain
a single .rkt file—
;; NameOfPartner1, NameOfPartner2
;; firstname.lastname@example.org, email@example.com