# [e-lang] Review requested: Fixing the ordering problem in Data-E

Kevin Reid kpreid at switchb.org
Mon May 31 09:23:33 PDT 2010

```I wrote this three years ago and finally got around to dusting it off
and integrating it... This is a rough draft patch; I would like
feedback on whether this is going about things the right way.

Particular things I'd like input on:

* What should the FQNs of Really and makeAssembler be?

* Where should the assembler be plugged into the Data-E system, and
should it
be optional?

For easy browsing, a copy of the updoc explanation, also included in
the patch:
------------------------------------------------------------------------

# Copyright 2010 Kevin Reid, under the terms of the MIT X license

XXX TODO: Dig up the mailing list discussion for this topic.

XXX linewraps
The problem is that, depending on the order of serialization, Data-E
unserialization may proceed in an order which fails to unserialize,
because some reference must be near; in particular, when the recipient
of a given call is an object whose creation was deferred.

For example, suppose A and B refer to each other, and A is encountered
first:

/-------\
V       |
+---+   +---+
-->| A |-->| B |
+---+   +---+

Furthermore, object C is a facet of A, and B refers to A:

/-------\
V       |
+---+   +---+
-->| A |-->| B |
+---+   +---+
*^*      |
+---+     |
| C |<----/
+---/

Then the deSubgraphKit algorithm:
* meets A, descends into its components
* meets B, descends into its components
* meets A again, produces a promise for A
* meets C, descends into its components
* meets A again as the receiver for C's uncall

This last step is the problem. We find we have the Data-E code:
def t_A := makeA(makeB(t_A, t_A.makeC()))
which will fail with not-synchronously-callable at makeC. (Note that
this problem can only occur if the *recipient* of an object's uncall
is another object in the subgraph, which participates in cycles,
rather than being an exit or non-cyclic subgraph.)

Another case is when C is not a facet of A, but is the product of
makeC(_ :near); this will also fail since t_A is not near when
makeC(t_A) is done. Note that unlike the previous case, this cannot be
fixed 'statically' (based only on the Data-E graph structure) since it
depends on the requirements for makeC's parameters.

The general solution to both of these problems is to recognize that
the 'order of execution' in unserialization is not part of the
meaningful content of a Data-E graph; therefore, we use the *caller*
hook of deSubgraphKit.makeBuilder to include a module which defers
calls until they may succeed.

The algorithm used is an incremental topological sort. Before each
call is performed, it is examined for dependencies (such as the
recipient being near). If it has any, it is deferred until those
dependencies have also executed.

The component which replaces E.call in unserialization is called an
'assembler', because its job is to perform the steps of assembling the
subgraph from the disorganized parts (calls) in the proper order until
it is complete.

Testing the assembler by itself
-------------------------------

XXX review: The assembler has more general use, as speculated in the
April 18 2007 mail; what should the FQN really be?

? def Really := <elib:slot.Really>

? def makeAssembler :=
<import:org.erights.e.elib.serial.makeAssembler>
# value: <makeAssembler>

>     if (portrayal =~ [list :Really[List], =="asSet", []]) {
>         for x in list { addDependency(x) }
>     }
> }

The parameters to makeAssembler are a callback which may inspect calls
invoked until the call constructing the recipient has been performed),
and the caller which should be used for the underlying real calls
(that this is wrapping).

? def a := makeAssembler(setDependencyBuilder, E)
# value: <assembler>

? def [y, s, l, x] := [a(1).next(),
>                      a(l).asSet(),
>                      a(__makeList).run(x, y),
>                      a(0).next()]
> a.finish()
> [y,s,l,x]
# value: [2, [1, 2].asSet(), [1, 2], 1]

XXX test the call() based interface.

? def l := a(["hello world", a(l).readOnly()]).diverge()
> a.finish()
> l

Data-E ordering
---------------

To test Data-E, we use the problem case described at the beginning of
this document.

? def b
> def a := ["this is A", b]
> bind b := ["this is B", a, a.diverge()]
> a
# value: ["this is A", ["this is B", <***CYCLE***>, ["this is A",
<***CYCLE***>].diverge()]]

? def surgeon := <elib:serial.makeSurgeon>.withSrcKit(""); null
? print(def ser := surgeon.serialize(a))
# stdout: def t__0 := ["this is A", ["this is B", t__0,
t__0.diverge()]]

? surgeon.unserialize(ser)
# value: ["this is A", ["this is B", <***CYCLE***>, ["this is A",
<***CYCLE***>].diverge()]]

XXX possibly add the default feature of using rangeSubsetOf to check
if the guards of the parameters in the the recipient's alleged type
are known to reject promises.

------------------------------------------------------------------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: assembler.patch
Type: application/octet-stream
Size: 13549 bytes
Desc: not available
Url : http://www.eros-os.org/pipermail/e-lang/attachments/20100531/797ed268/attachment.obj
-------------- next part --------------

--
Kevin Reid                                  <http://switchb.org/kpreid/>

```