CS G111 Machine Problem 9: Favoring Implicit Calls and Communication

Out: November 27, 2007

Due: December 4, 2007

Instead of actively calling your functions, practice implicit calling using DemeterF.

Part 1: Extending your Type-Checker for DemeterF

Extend class dictionary language from MP8 with: optional parts and collection classes (zero or more elements). We call the extended class dictionary language CDS.

Because of html issues, I use + to start and end a part name. A = +b+ B. is a class with one part called b. In your program you use the normal class dictionary syntax.

For the purpose of type checking, we can translate A ~ {B}. into A = +element+ B. and also A = [+b+ B]. into A = +b+ B. This can be done easily with a preprocessor in DemeterF.

Example:

  Object : Exp | String | Integer.
  Exp : Lambda | Var.
  Lambda = +arg+ String [+body+ Exp] .
  Var : Sym | Addr.
  ExpList ~{Exp}.

is translated into:

  Object : Exp | String | Integer.
  Exp : Lambda | Var.
  Lambda = +arg+ String +body+ Exp .
  Var : Sym | Addr.
  ExpList = +element+ Exp .

Implement a type checker for CDS.

Part 2: Extending the Capacity Checker with a Repair Capability

In mp6 we modified the capacity checking problem: /home/lieber/.www/courses/csg111/f07/machprobs/f07/mp6/capacity Add a repair functionality to the capacity checking problem. This means that a container that is over capacity passes up a list of surplus items that are selected in any way. The enclosing container might have free capacity and can absorb some items on the surplus list.

Input:
A container C.

Output:
A container C' with no capacity violations plus a list of
surplus items S. C' and S contain the same elements.
If the surplus list is not empty for a container then adding
any element from the list to the container 
would bring the container over capacity.
(In other words, elements are put on the surplus list only when needed.)

Part 3: Automate Demeter Class Dictionary to EOPL datatype Translation

Write a translator using DemeterF that translates the class dictionary language of MP 8 into an equivalent EOPL Scheme define-datatype expression. The starting point is: /home/lieber/.www/courses/csg111/f07/machprobs/f07/mp8/self-descr The translation should be simple and not attempt to generate the smallest passible define-datatype input.

A concrete class B translates into (define-datatype B B? [a-B parts]). An abstract class C translates into (define-datatype C C? [a-alt1 (contents alt1?)] ...).

Example:

Class dictionary:
PathSpec : Simple | Join | Merge.
Simple =  +source+ Node +target+ Node.
Join = +first+ PathSpec +second+ PathSpec .
Merge = +first+ PathSpec +second+ PathSpec .
Test = +simple+ Simple +join+ Join +merge+ Merge.

Datatypes:
(define-datatype path-spec path-spec?
   [a-simple (contents simple?)]
   [a-join (contents join?)]
   [a-merge (contents merge?)])

(define-datatype simple simple?
   [simple (source symbol?)
           (target symbol?)])

(define-datatype join join?
   [join (first path-spec?)
         (second path-spec?)])

(define-datatype merge merge?
   [merge (first path-spec?)
          (second path-spec?)])

define-datatype test test?
   [test
        (simple simple?)
        (join join?)
        (merge merge?)])

Use a ToString class similar to the one in http://www.ccs.neu.edu/research/demeter/DemeterF/FuncTest.java because it is a simple linear translation.

Last modified: November 28, 2007 by Karl Lieberherr