Re: Coercion, membranes, serialization, and printing are the same thing

Hi Kevin,

I have been thinking about generalizing membranes in similar ways.

You mention serialization as a special case of membranes. There's another
similar case I've come across: wrappers that convert between language
boundaries (e.g. E and Java, or AmbientTalk and Java). This is even closer
to membranes in the sense that the language mapping also requires two
directions, which are each other's inverse.

This has been studied to some extent in academic circles, where it's called
"linguistic symbiosis" or "inter-language reflection". For instance, the
equations on p.9 of the following paper <
http://scg.unibe.ch/archive/papers/Gybe06aSymbioticReflectionESUGJournal.pdf>
remind me a lot of the "dry to wet" and "wet to dry" conversions (or
"in->out" and "out->in" conversions) that revocable membranes must
implement.

As it happens, I'm working on trying to express another possible use case
of membranes: the ability to confine objects through ownership types
(seminal paper: Ownership types for Flexible Alias Protection, Clarke et
al., OOPSLA '98 <
http://www.cs.cornell.edu/courses/cs711/2005fa/papers/cpn-oopsla98.pdf>).

The basic idea of ownership types is that you can prevent objects that are
"owned" by an aggregate object to leak from the aggregate. The example used
in the paper is a Car class that has an Engine, but doesn't want any of its
clients to be able to directly refer to the Engine. Ownership types can
catch such leaks statically.

Last year at the Dynamic Languages Symposium, there was a paper about
expressing these ideas in a dynamically typed language (i.c. Smalltalk) <
http://scg.unibe.ch/archive/papers/Wern12c.pdf>. However, they don't use
proxies to implement the confinement, but dynamic checks embedded in the
runtime. I believe this approach suffers from dynamic scoping issues, and I
think membranes based on proxies might provide an alternative solution that
is more aligned with ocaps. (At least, the authors of the DLS paper are
aware of ocaps, they cite the Paradigm regained paper, and they're aware of
membranes).

If anyone is interested in exploring these ideas further, drop me a line.

Regards,
Tom



2013/10/12 Kevin Reid <kpreid-M/[email protected]>

> 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.)
>
> --
> Kevin Reid                                  <http://switchb.org/kpreid/>
>
>
> _______________________________________________
> e-lang mailing list
> [email protected]
> http://www.eros-os.org/mailman/listinfo/e-lang
>

_______________________________________________
e-lang mailing list
[email protected]
http://www.eros-os.org/mailman/listinfo/e-lang