►7400:   i  PPL (Spring 2017)
▼Problem Sets
    ← prev  up  next → 

Problem Set 2

home work!

Topic Basic Redex Programming

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.

image

Problem 1 Wikipedia describes a mobile as follows:

  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.

Here is a rigorous, structured description:

  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.

Here is a data (language) definition for a mobile:
(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.

Design the following functions:

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

Problem 2 Here is a data (language) definition for a graph representation, including two sample graphs:
(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))))
A quick check shows that both g1 and g1 are members of Graph’s language:
> (redex-match? Graph g g1)

#t

> (redex-match? Graph g g2)

#t

At the same time, g2 contains an edge that clearly mentions the name of a node that does not exist.

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.

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.

Next, develop a Redex language definition for the following:

  An DBExpression is one of:

   -- Number

   -- Variable

   -- (function Variable DBExpression)

   -- (DBExpression DBExpression)

  A Variable is a String.

Again, the token function is the only keyword in this language.

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.

For example, when given

  (function "y"

    ((function "x"

       ("x" "y"))

      ("x" "y")))

db produces

  (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 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—with the same name as the tar ball—and a README.txt file.

The README.txt file must start with the following lines:

  ;; NameOfPartner1, NameOfPartner2

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

appropriately instantiated of course. Stick to a line width of 80 characters for all of your code and follow DrRacket’s indentation rules to ensure some basic readability.

    ← prev  up  next →