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> }