Safe Serialization Under Mutual Suspicion/"Reversing" Evaluation
From Erights
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.
<span class="keyword">def</span> <span class="defobj">deSubgraphKit</span> {
<span class="keyword">to</span> <span class="defobj">makeBuilder</span>(<span class="defvar">scope</span>) :near {
<span class="comment"># The index of the next temp variable</span>
<span class="keyword">var</span> <span class="defvar">nextTemp</span> := 0
<span class="comment"># The frame of temp variables</span>
<span class="keyword">def</span> <span class="defvar">temps</span> := [].diverge()
<span class="comment"># The type returned by "internal" productions and passed as arguments to represent</span>
<span class="comment"># built subtrees.</span>
<span class="keyword">def</span> <span class="defvar">Node</span> := any
<span class="comment"># The type returned by the builder as a whole.</span>
<span class="keyword">def</span> <span class="defvar">Root</span> := any
<span class="comment"># DEBuilderOf is a parameterized type constructor.</span><span class="comment"></span>
<span class="keyword">def</span> <span class="defobj">deSubgraphBuilder</span> implements DEBuilderOf(Node, Root) {
<span class="keyword">to</span> <span class="defverb">getNodeType</span>() :near { Node }
<span class="keyword">to</span> <span class="defverb">getRootType</span>() :near { Root }
<span class="comment">/** Called at the end with the reconstructed root to obtain the value to return. */</span>
<span class="keyword">to</span> <span class="defverb">buildRoot</span>(<span class="defvar">root</span> :Node) :Root { root }
<span class="comment">/** A literal evaluates to its value. */</span>
<span class="keyword">to</span> <span class="defverb">buildLiteral</span>(<span class="defvar">value</span>) :Node { value }
<span class="comment">/** A free variable's name is looked up in the scope. */</span>
<span class="keyword">to</span> <span class="defverb">buildImport</span>(<span class="defvar">varName</span> :String) :Node { scope[varName] }
<span class="comment">/** A temporary variable's index is looked up in the temps frame. */</span>
<span class="keyword">to</span> <span class="defverb">buildIbid</span>(<span class="defvar">tempIndex</span> :int) :Node { temps[tempIndex] }
<span class="comment">/** Perform the described call. */</span>
<span class="keyword">to</span> <span class="defverb">buildCall</span>(<span class="defvar">rec</span> :Node, <span class="defvar">verb</span> :String, <span class="defvar">args</span> :Node[]) :Node {
<span class="comment"># E.call(..) is E's reflective invocation construct. For example, E.call(2, "add", [3])</span>
<span class="comment"># performs the same call as 2.add(3).</span>
<u>E.call(rec, verb, args)</u>
}
<span class="comment">/**</span>
<span class="comment"> * Called prior to building the right-hand side of a defexpr, to allocate and bind the</span>
<span class="comment"> * next two temp variables to a promise and its resolver.</span>
<span class="comment"> * </span>
<span class="comment"> * @return the index of the temp holding the promise. The temp holding the</span>
<span class="comment"> * resolver is understood to be this plus one.</span>
<span class="comment"> */</span>
<span class="keyword">to</span> <span class="defverb">buildPromise</span>() :int {
<span class="keyword">def</span> <span class="defvar">promIndex</span> := nextTemp
nextTemp += 2
<span class="keyword">def</span> [<span class="defvar">prom</span>,<span class="defvar">res</span>] := Ref.promise()
temps[promIndex] := prom
temps[promIndex+1] := res
promIndex
}
<span class="comment">/**</span>
<span class="comment"> * Called once the right-hand side of a defexpr is built, use the resolver to resolve</span>
<span class="comment"> * the value of the promise.</span>
<span class="comment"> * </span>
<span class="comment"> * @return the value of the right-hand side.</span>
<span class="comment"> */</span>
<span class="keyword">to</span> <span class="defverb">buildDefrec</span>(<span class="defvar">resIndex</span> :int, <span class="defvar">rValue</span> :Node) :Node {
temps[resIndex].resolve(rValue)
rValue
}
<span class="comment"># ... buildDefine is an optimization of buildDefrec for known non-cyclic cases.</span>
}
}
<span class="comment"># ... other useful tools </span>
}
