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:
Abbreviations:
CG = class graph
OG = object graph (which is a tree)
Program is: { prog CG OG Strategy Visitor }
CG is: { DD+ }
DD is: { datatype TypeName Alternative+ }
Alternative is: { AlternativeName { FieldName TypeName }* }
OG is one of:
-- Number
-- String
-- ( AlternativeName OG * )
Strategy is: { // TypeName TypeName }
Visitor is:
{ visitor Name Expression
FinishAction
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)
-- ...
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:
- All type names in a class graph must be
Number, String, or one of the type names introduced in
a datatype clause.
- All constructor names in the object graph must come from the alternative
clauses in the
datatype specifications of the class graph.
- 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.
- A strategy may only mention two constructors.
KARL
This is confusing because Strategy is (// TypeName TypeName).
Do you want to change this to (// AlternativeName AlternativeName)?
The root constructor of the
object graph must be the first (start) type of the strategy; the other one is
freely chosen.
- 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:
KARL: why so many { } ?
In EOPL Scheme they are ().
{prog
;; class graph:
{
{ datatype Container
{ContainerC {contents ItemList} {capacity Number}} }
{ datatype Item
{Complex {c Container}}
{Atomic {name String} {weight Number}} }
{ datatype ItemList
{Empty}
{More {first Item} {rest ItemList}}}
}
;; object graph:
(ContainerC (More (Atomic "apple" 5)
(More (ContainerC (More (Atomic "orange" 8) (Empty))
8)
(Empty)))
5)
;; strategy:
{// ContainerC Atomic}
;; visitor:
{ visitor: totalWeight 0
totalWeight
[before Atomic a ...]
}
}
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). 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.