Hi Johan:

Binoy suggested that we use printing and parsing for marshalling.
A discussion of an alternative approach is below. But the 
printing-parsing approach seems much better.

The problem is:

> > Given a strategy graph S, and a class graph G.
> > Required is an algorithm MARSHAL[S,G](O)
> > which takes an object graph O and which
> > encodes the subobject O' traversed by S as a string m so that from
> > S, G and m, we can quickly reconstruct O'.

Solution:
Use a function M which creates a marshalling cd: 
strategies x classgraphs -> class dictionaries
The idea is that M(S,G) contains enough syntax so that with
M(S,G) a short sentence m can be created from O using
a PrintVisitor with S and so that the parser can reconstruct
O' using m and M(S,G). M(S,G) can be transmitted
across the network or recomputed on the other side.

preprocessing: 
  compute M(S,G)
MARSHAL[S,G](O):
  print O with respect to S and M(S,G) -> m

UNMARSHAL[M(S,G)](m):
  parse o with respect to M(S,G)

Example:

G:
A = B C D E F.
B = .
C = .
D = String.
E = Integer.
F : G | H.
G = .
H = .

S:
from A bypassing D to *

M(S,G):
A = B C [D] E F.
B = .
C = .
D = String.
E = Integer.
F : G | H.
G = "g".
H = "h".

This grammar is LL(1). Objects are:

Transmitted		After reconstruction
1000 g			A(B(),C(),null,Integer(1000),G())
1000 h			A(B(),C(),null,Integer(1000),H())

The question is how to compute a minimal marshalling cd M(S,G).
It must contain optional parts where the strategy omits parts
but it must also contain minimal syntax. We have the abstract problem:

Input: class graph G
Output: Minimal syntactic extension G' of G such that G' is LL(1).

We want to make it minimal since minimality reduces the length of the
strings sent across the network. But close to minimal is fine too.

Johan, please can you propose a solution for the marshalling problem
and then implement it for Ridl using RMI.

Check the Demeter/C++ system: It contains an algorithm which makes any
class dictionary LL(1). Does it create a minimal grammar?
Cun Xiao implemented that part.

-- Karl

===========================
Hi Boaz:
thank you for your clever algorithm design.

>From boaz@ccs.neu.edu Tue Sep 30 21:46:45 1997
>From: Boaz Patt-Shamir <boaz@ccs.neu.edu>
>To: Karl Lieberherr <lieber@ccs.neu.edu>
>Subject: marshaling
>cc: dem@ccs.neu.edu, boaz@ccs.neu.edu
>
>Karl Lieberherr writes:
> > 
> > Given a strategy graph S, and a class graph G.
> > Required is an algorithm MARSHAL[S,G](O)
> > which takes an object graph O and which
> > encodes the subobject O' traversed by S as a string m so that from
> > S, G and m, we can quickly reconstruct O'.
> > 
> > Are there some intresting tradeoffs in this problem? Can we reconstruct
> > O' faster if we know the strategy which produced it?
> > The overall  goal is to make the string m = MARSHAL[S,G](O) small
> > and the reconstruction algorithm fast.
> > 
>The way I see the problem is the following:
>
>The difference between full marshalling and marshalling according to a
>strategy is that some parts of the object graph are pruned. 
>
>So on one extreme of the spectrum is the solution where each pruned
>reference is somehow marked with a literal null pointer. This solution
>allows for fast reconstruction, but the communicated string is
>longer. Call this algorithm T.
>
>The other extreme is to apply the traversal algorithm at the receiving
>end, so that pruned branches are identified and hence their null value
>can be inferred without explicit space-consuming nulls in the
>communicated string. This algorithm assumes that the strategy and the
>class graph are known a priori by the unmarshalling algorithm. Of

I think this is what Crista does for her simplified strategies.

>course, the reconstruction is now slower (note that it isn't slower
>than the construction!). Call this algorithm S.

Since the reconstruction has the overhead of the strategy compilation algorithm,
it can be slower than the construction?
>
>Algorithm T is better when the number of pruned branches is small, and
>algorithm S is better when the number of pruned branches is large (the
>exact meaning of "small" and "large" depends on the relative costs we
>assign to time and space). The problem is that determining this number
>requires another traversal!
>
>The solution for this difficulty is a hybrid algorithm with a
>parameter k: First, algorithm T is used for the first k pruned
>branches; if there are more pruned branches, then algorithm S is used
>for the remainder. Determining k depends on the cost we assign to time
>and communication. A nice property of the hybrid algorithm is that one
>can prove that its cost is at most a constant factor more than the
>best one. (To see that, note that the worst case for the hybrid
>alg. is when the number of pruned branches is k+1.)

A nice analysis indeed. Since traversal strategies are new, your analysis
is probably new. k can, for example, be  determined based on
quality of service information about the network.

>
>Boaz
>
-- Karl