Safe Serialization Under Mutual Suspicion/"Reversing" Evaluation
From Erights
(Difference between revisions)
(saved with code highlighting and colouring) |
(spans and few newlines removed. 'pragma.syntax("0.8")' added) |
||
Line 12: | Line 12: | ||
<code> | <code> | ||
<pre> | <pre> | ||
- | + | pragma.syntax("0.8") | |
- | + | ||
- | + | def deSubgraphKit { | |
+ | to makeBuilder(scope) :near { | ||
- | + | # The index of the next temp variable | |
- | + | var nextTemp := 0 | |
- | + | ||
- | + | # The frame of temp variables | |
+ | def temps := [].diverge() | ||
- | + | # The type returned by "internal" productions and passed as arguments to represent | |
- | + | ||
- | + | # built subtrees. | |
- | + | def Node := any | |
- | + | # The type returned by the builder as a whole. | |
+ | def Root := any | ||
- | + | # DEBuilderOf is a parameterized type constructor. | |
- | + | ||
- | + | ||
- | + | def deSubgraphBuilder implements DEBuilderOf(Node, Root) { | |
- | + | to getNodeType() :near { Node } | |
+ | to getRootType() :near { Root } | ||
- | + | /** Called at the end with the reconstructed root to obtain the value to return. */ | |
+ | to buildRoot(root :Node) :Root { root } | ||
- | + | /** A literal evaluates to its value. */ | |
+ | to buildLiteral(value) :Node { value } | ||
- | + | /** A free variable's name is looked up in the scope. */ | |
- | + | to buildImport(varName :String) :Node { scope[varName] } | |
- | + | /** A temporary variable's index is looked up in the temps frame. */ | |
+ | to buildIbid(tempIndex :int) :Node { temps[tempIndex] } | ||
- | + | /** Perform the described call. */ | |
- | + | to buildCall(rec :Node, verb :String, args :Node[]) :Node { | |
- | + | # E.call(..) is E's reflective invocation construct. For example, E.call(2, "add", [3]) | |
- | + | # performs the same call as 2.add(3). | |
- | + | ||
- | + | ||
- | + | ||
<u>E.call(rec, verb, args)</u> | <u>E.call(rec, verb, args)</u> | ||
} | } | ||
- | + | /** | |
- | + | * Called prior to building the right-hand side of a defexpr, to allocate and bind the | |
- | + | * next two temp variables to a promise and its resolver. | |
- | + | * | |
- | + | * @return the index of the temp holding the promise. The temp holding the | |
- | + | * resolver is understood to be this plus one. | |
- | + | */ | |
- | + | to buildPromise() :int { | |
- | + | def promIndex := nextTemp | |
nextTemp += 2 | nextTemp += 2 | ||
- | + | def [prom,res] := Ref.promise() | |
temps[promIndex] := prom | temps[promIndex] := prom | ||
temps[promIndex+1] := res | temps[promIndex+1] := res | ||
Line 75: | Line 74: | ||
} | } | ||
- | + | /** | |
- | + | * Called once the right-hand side of a defexpr is built, use the resolver to resolve | |
- | + | * the value of the promise. | |
- | + | * | |
- | + | * @return the value of the right-hand side. | |
- | + | */ | |
- | + | ||
- | + | to buildDefrec(resIndex :int, rValue :Node) :Node { | |
temps[resIndex].resolve(rValue) | temps[resIndex].resolve(rValue) | ||
rValue | rValue | ||
} | } | ||
- | + | # ... buildDefine is an optimization of buildDefrec for known non-cyclic cases. | |
} | } | ||
} | } | ||
- | + | # ... other useful tools | |
} | } |
Revision as of 06:36, 29 January 2008
As we've seen, we make serializers, unserializers, and other transformers like expression simplifiers by composing a recognizer with a builder. The interface between the two is the DEBuilder API, explained in Appendix A: The Data-E Manual. Since most of the API is a straightforward reflection of the Data-E grammar productions, if you wish, you may safely skip these details and proceed here by example.
Evaluating Data-E
The semantics of Data-E are defined by the semantics of its evaluation as an E program. We could unserialize using the full E evaluator. However, this is inefficient both as an implementation and as an explanation. Instead, here is the Data-E evaluator as a builder, implementing exactly this subset of E's semantics.
pragma.syntax("0.8") def deSubgraphKit { to makeBuilder(scope) :near { # The index of the next temp variable var nextTemp := 0 # The frame of temp variables def temps := [].diverge() # The type returned by "internal" productions and passed as arguments to represent # built subtrees. def Node := any # The type returned by the builder as a whole. def Root := any # DEBuilderOf is a parameterized type constructor. def deSubgraphBuilder implements DEBuilderOf(Node, Root) { to getNodeType() :near { Node } to getRootType() :near { Root } /** Called at the end with the reconstructed root to obtain the value to return. */ to buildRoot(root :Node) :Root { root } /** A literal evaluates to its value. */ to buildLiteral(value) :Node { value } /** A free variable's name is looked up in the scope. */ to buildImport(varName :String) :Node { scope[varName] } /** A temporary variable's index is looked up in the temps frame. */ to buildIbid(tempIndex :int) :Node { temps[tempIndex] } /** Perform the described call. */ to buildCall(rec :Node, verb :String, args :Node[]) :Node { # E.call(..) is E's reflective invocation construct. For example, E.call(2, "add", [3]) # performs the same call as 2.add(3). <u>E.call(rec, verb, args)</u> } /** * Called prior to building the right-hand side of a defexpr, to allocate and bind the * next two temp variables to a promise and its resolver. * * @return the index of the temp holding the promise. The temp holding the * resolver is understood to be this plus one. */ to buildPromise() :int { def promIndex := nextTemp nextTemp += 2 def [prom,res] := Ref.promise() temps[promIndex] := prom temps[promIndex+1] := res promIndex } /** * Called once the right-hand side of a defexpr is built, use the resolver to resolve * the value of the promise. * * @return the value of the right-hand side. */ to buildDefrec(resIndex :int, rValue :Node) :Node { temps[resIndex].resolve(rValue) rValue } # ... buildDefine is an optimization of buildDefrec for known non-cyclic cases. } } # ... other useful tools }