Hi Matthias:

Looks good.  Let's use your notation in the homework.
(In my lectures I will use class dictionaries)

Please look for 

QtM (Question to Matthias).

I repaired a few small typos and also added a type check
for the strategy and visitor.

-- Karl

;; --- the language ---
Programs:
A Program is:
  (program: CD OG Strategy Visitor)

Class Dictionaries:

A CD is: (DD ...)

A DD is:
  (datatype TypeName Alternative ...)

An Alternative is:
  (AlternativeName (FieldName TypeName) ...)

Object Graphs:

An OG is one of:
  Number
  String
  (AlternativeName OG ...)

Strategies:

A Strategy is:
  (// TypeName TypeName)
  The first name is called source type and the second one target type.

Visitors:

A Visitor is:
  (visitor Name Expression
   FinishAction
   Action ...
  )

A FinishAction is:
  Expression

An Action is one of:
  -- [before TypeName Expression]
  -- [after  TypeName Expression]

Expression is one of:
  -- Name (the name of the visitor)
  -- // up to you //

;; --- your tasks ---

1. type check the CD:

    In a CD, every DD's alternatives must use TypeNames that
    are defined in CD or Number or String.

2. type check the OG:

    Every constructor is used with the proper arity.
    Every field is occupied by instances of the proper type.

3. type check the Strategy:

   The source type and the target type must be TypeNames that
   are defined in CD or Number or String.

4. type check the Visitor:

   The TypeNames in actions  must be TypeNames that
   are defined in CD or Number or String.

3. Design an expression language for visitors.

    The name of the visitor may occur free in the FinishAction and the Action
    sequence. Otherwise it may not appear anywhere and the rule must obey your
    scoping rules.

QtM: I don't understand what you mean by "the rule must obey your scoping rules"

4. In a program, the type of the object graph must agree with the source type of the strategy.

5. Implement a traversal interpreter that applies a visitor (V) to the object
    graph (OG) according to the strategy (as directed by the class dictionary).

    The visitor's initial value is the value of its first expression.

    On entering a node of TypeName, the visitor evaluates the expression
    associated with a _before_ Action. The result becomes the new value of the
    visitor. On exiting a node of TypeName, the visitor evaluates the expression
    associated with an _after_ Action. The result becomes the new value of the
    visitor.
    
OLD:    When the traversal reaches a node of the end type in the given strategy
NEW:    When the traversal finishes traversing the object graph,

QtM: here I made a change to the semantics.

    the interpreter evaluates the FinishExpression. The result of this
    FinishExpression is the result of the traversal. During the evaluation of any
    expression, the name of the visitor (unless in nested scope) represents for
    its current value.


Extensions:

- two strategy constructors