G711 F '05
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9

Problem Set 8: An Aspect Language for Datatype

Due date: 11/8 @ 5:00 pm

This goal of this problem set is to understand Prof. Lieberherr's lecture.

The statement of this problem set is the result of a long dialog between your two instructors. If you need clarification, send me email; I will reply on the list. -- Matthias Felleisen

The datatype construct in EoPL Scheme specifies the layout of data hierarchies in a manner that is analogous to classes for tree-shaped data. For such class hierarchies, it is common to write quasi-functional programs, also dubbed visitors. Roughly speaking, visitors are functions that, during a traversal of a tree-shaped piece of data, are applied to each node in the tree. The purpose of this assignment is to study traversals and visitors in this context. The syntax of the programming language is given:

  Program is: {prog ClassGraph OG Strategy Visitor}

  ClassGraph is: {DD+}

  DD is: {datatype TypeName Alternative+}

  Alternative is: { AlternativeName {FieldName TypeName}* }

  OG is one of: 
   -- Number 
   -- String 
   -- (AlternativeName OG *)

  Strategy is: {// AlternativeName AlternativeName}

  Visitor is: 
   { visitor Name Expression
     Action* }

  FinishAction is: Expression 

  Action is one of: 
   -- [before AlternativeName Name Expression]
   -- [after  AlternativeName Name Expression]

  Expression is one of: 
   -- Name (the name of the visitor and parameter)
   -- Visitor
   -- ... 

  TypeName, FieldName, AlternativeName, Name is: Symbol
The design of the expression language is up to you. For more information, see the task list below.

Programs in this language must satisfy additional type constraints:

  1. All type names in a class graph must be Number, String, or one of the type names introduced in a datatype clause.
  2. All constructor names in the object graph must come from the alternative clauses in the datatype specifications of the class graph.
  3. All fields of a constructed term must have the appropriate types. Naturally, a constructor must be applied to the appropriate number of argument terms, too.
  4. A strategy may only mention two constructors. The root constructor of the object graph must be the first (start) type of the strategy; the other one is freely chosen.
  5. The visitor may only mention constructors from the class graph. Otherwise type checking is up to you because the rest concerns the expression language.
Make sure to understand these rules. It might be helpful to develop type checking rules in the spirit of my type checking lecture. If you do, add them to your submission.

The interpreter of this language is to traverse the given object graph according to the strategy. Here, strategies (// start end) denote the set of all paths from the root node, constructed with start, to all nodes created with end.

Before the interpreter begins the traversal, it creates the named visitor. Its initial value is determined by the initialization expression. As the interpreter traverses the graph, it applies the visitor's action to the appropriate nodes (before and after visiting them). Each action is a function that has access to two values: the currently visited node via the named parameter and the current value of the visitor via the name of the visitor. The result of the action is a value, which then becomes the new value of the visitor. When all paths have been traversed, the interpreter evaluates the finalization expression, which has no parameter but can naturally refer to the current value of the visitor.

Here is a partial program in this language whose purpose it is to traverse a hierarchy of containers and compute its total weight:

;; class graph:
  { datatype Container 
     {ContainerC {contents ItemList} {capacity Number}} }
  { datatype Item 
     {Complex {c Container}}
     {Atomic  {name String} {weight Number}} }
  { datatype ItemList 
     {More {first Item} {rest ItemList}}}

;; object graph:
 (ContainerC (More (Atomic "apple" 5)
                   (More (ContainerC (More (Atomic "orange" 8) (Empty))

;; strategy:
 {// ContainerC Atomic}

;; visitor: 
 { visitor: totalWeight 0
            [before Atomic a ...]

(Use (read) to get this into S-expression form.) The program is necessarily partial because the expression sublanguage is not yet complete.

Problem 1:

Develop an sublanguage of expressions for the traversal language. The language should be strong enough so that you can complete the above sample program.

Hints: The language has built-in state (the visitor and its actions), one piece to be precise. We suggest that you keep the expression sublanguage functional. You definitely will have to consider how to extract the field values from a given term. Otherwise a language of addition, etc. will do.

Document your design via grammatical rules in the style that we use.

Problem 2:

Develop a data representation for programs in EoPL Scheme.

Design a type checker for the language. If you have a typed programming language, make sure to type check it, too.

Problem 3:

Design an interpreter for the language and demonstrate its workings via the sample program.

last updated on Tue Jun 9 22:21:18 EDT 2009generated with PLT Scheme