►7400:   i  PPL
▼Problem Sets
    ← prev  up  next → 

Problem Set 2

home work!

Programming Language Basic Redex Programming

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 Here is a data (language) definition:
(define-language tree-lang
  (t l        ; leaf
     (t * t)) ; composite
  (l string))

Define five sample trees, with at least three composites.

Design the following functions:

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

Problem 2 Here is a data (language) definition for a graph representation, including two sample graphs:
(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))))
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 clearly mentions the name of a node that does not exist.

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

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

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

    ← prev  up  next →