Kevin Reid
2013-10-12 05:18:43 UTC
A motivating problem
--------------------
One of the things that bugs me about E's design as it currently stands is that the obvious application of a guard on circular structure does not terminate.
That is, suppose we write:
def Binary := nullOk[Tuple[Binary, Binary]]
Used as a guard, this will do exactly what it looks like it ought to do, provided that the value is acyclic; if the value is cyclic then the guard application will not terminate, because the guard protocol does not have any cycle-breaking provision.
This seems to me to be against the spirit of E: all things which _can_ sensibly operate on cyclic structure _should_ do so (just as equality does).
The obvious solution
--------------------
We can see an invocation of a guard as the momentary existence of a fragment of a membrane: it maps references on one side to references on the other, as controlled by the guard's coercion. It is not a membrane in that it does not fully enclose a subgraph, and that there is no (need for a) reverse mapping.
This is then simply the memoization-with-cycle-support of the individual guards' coercions. A straightforward implementation:
def coerceWithCycleSupport(value, guard, ejector) {
def seen := [].asMap().diverge()
def subCoerce(value, guard) {
def key := makeTraversalKey([value, guard])
return seen.fetch(key, fn {
def [p, r] := Ref.promise()
seen[key] := p
r.resolve(guard.coerce(value, ejector, subCoerce))
p
});
}
return subCoerce(value, guard)
}
(Note that subCoerce can be captured. This will be useful later.)
We add a third parameter to guards' coerce method, which they use to invoke their sub-guards with cycle breaking. As an example, a partial implementation of the Tuple parameterized guard:
def makeCTuple2(A, B) {
return def tupleGuard {
to coerce(value, ejector, subCoerce) {
def [a, b] exit ejector := value
return [subCoerce(a, A), subCoerce(b, B)]
}
}
}
Then to use such guards, where current E would do
G.coerce(specimen, ejector)
it is instead
coerceWithCycleSupport(specimen, G, ejector).
This is loosely analogous to the use of 'throw.eject' in place of directly calling an ejector object.
I'm not sure that this is actually a good idea to add to guards, because of the additional complexity-of-mechanism and the runtime cost (though it could be optimized by not constructing any promises, or the seen table, unless subCoerce is actually invoked by the particular guard, so that simple guarding like ':int' doesn't end up allocating anything).
(It is also arguable that deep structural guards are a bad idea, since naïvely using them can result in increasing time complexity due to redundant traversals/reconstructions of the same structure.)
The common structure
--------------------
What I find interesting about this is that we have defined a generic reference graph transformation. The algorithm inside of coerceWithCycleSupport is exactly the same as the one used for printing, serialization, and membranes, with some minor differences:
• Printing and serialization do not output reference graphs, and would rather explicitly handle cycles than get promises on the output side.
• Membranes have a bidirectional mapping (i.e. the inverse function of subCoerce is available) and may invoke subCoerce arbitrarily later in time.
It might well be the case that these applications have enough individual quirks that they should be implemented individually -- the core algorithm is not especially lengthy or hard to implement correctly -- but I think it is worth thinking about whether there is value in conceptual unification, or even in shifting the protocols of these four operations to be more similar to each other.
(One of these things which definitely needs changing is the printing system -- for usability, it should be possible to print a structure which contains far references using their specfic __printOn rather than as "<Far ref>", which is not possible in the current approach. The graph transformation technique may make this more straightforward to define -- I am unsure.)
--------------------
One of the things that bugs me about E's design as it currently stands is that the obvious application of a guard on circular structure does not terminate.
That is, suppose we write:
def Binary := nullOk[Tuple[Binary, Binary]]
Used as a guard, this will do exactly what it looks like it ought to do, provided that the value is acyclic; if the value is cyclic then the guard application will not terminate, because the guard protocol does not have any cycle-breaking provision.
This seems to me to be against the spirit of E: all things which _can_ sensibly operate on cyclic structure _should_ do so (just as equality does).
The obvious solution
--------------------
We can see an invocation of a guard as the momentary existence of a fragment of a membrane: it maps references on one side to references on the other, as controlled by the guard's coercion. It is not a membrane in that it does not fully enclose a subgraph, and that there is no (need for a) reverse mapping.
This is then simply the memoization-with-cycle-support of the individual guards' coercions. A straightforward implementation:
def coerceWithCycleSupport(value, guard, ejector) {
def seen := [].asMap().diverge()
def subCoerce(value, guard) {
def key := makeTraversalKey([value, guard])
return seen.fetch(key, fn {
def [p, r] := Ref.promise()
seen[key] := p
r.resolve(guard.coerce(value, ejector, subCoerce))
p
});
}
return subCoerce(value, guard)
}
(Note that subCoerce can be captured. This will be useful later.)
We add a third parameter to guards' coerce method, which they use to invoke their sub-guards with cycle breaking. As an example, a partial implementation of the Tuple parameterized guard:
def makeCTuple2(A, B) {
return def tupleGuard {
to coerce(value, ejector, subCoerce) {
def [a, b] exit ejector := value
return [subCoerce(a, A), subCoerce(b, B)]
}
}
}
Then to use such guards, where current E would do
G.coerce(specimen, ejector)
it is instead
coerceWithCycleSupport(specimen, G, ejector).
This is loosely analogous to the use of 'throw.eject' in place of directly calling an ejector object.
I'm not sure that this is actually a good idea to add to guards, because of the additional complexity-of-mechanism and the runtime cost (though it could be optimized by not constructing any promises, or the seen table, unless subCoerce is actually invoked by the particular guard, so that simple guarding like ':int' doesn't end up allocating anything).
(It is also arguable that deep structural guards are a bad idea, since naïvely using them can result in increasing time complexity due to redundant traversals/reconstructions of the same structure.)
The common structure
--------------------
What I find interesting about this is that we have defined a generic reference graph transformation. The algorithm inside of coerceWithCycleSupport is exactly the same as the one used for printing, serialization, and membranes, with some minor differences:
• Printing and serialization do not output reference graphs, and would rather explicitly handle cycles than get promises on the output side.
• Membranes have a bidirectional mapping (i.e. the inverse function of subCoerce is available) and may invoke subCoerce arbitrarily later in time.
It might well be the case that these applications have enough individual quirks that they should be implemented individually -- the core algorithm is not especially lengthy or hard to implement correctly -- but I think it is worth thinking about whether there is value in conceptual unification, or even in shifting the protocols of these four operations to be more similar to each other.
(One of these things which definitely needs changing is the printing system -- for usability, it should be possible to print a structure which contains far references using their specfic __printOn rather than as "<Far ref>", which is not possible in the current approach. The graph transformation technique may make this more straightforward to define -- I am unsure.)
--
Kevin Reid <http://switchb.org/kpreid/>
Kevin Reid <http://switchb.org/kpreid/>