Safe Serialization Under Mutual Suspicion/"Reversing" Evaluation

From Erights

(Difference between revisions)
Jump to: navigation, search
(continuing wikification #7)
m (continuing wikification #7.1)
Line 209: Line 209:
Since the values of the unscope are Strings or ints, we can use <tt>null</tt> to detect whether <tt>obj</tt> was found.
Since the values of the unscope are Strings or ints, we can use <tt>null</tt> to detect whether <tt>obj</tt> was found.
|}
|}
-
      <blockquote>
+
<code><pre>
-
        <pre>               <span class="keyword">if</span> (unscope.fetch(obj, thunk{}) =~ <span class="defvar">varID</span> :notNull) {
+
                <span class="keyword">if</span> (unscope.fetch(obj, thunk{}) =~ <span class="defvar">varID</span> :notNull) {
                     <span class="keyword">return</span> genVarUse(varID)
                     <span class="keyword">return</span> genVarUse(varID)
                 }
                 }
Line 222: Line 222:
         }
         }
     }
     }
-
}</pre>
+
}
-
 
+
</pre></code>
-
      </blockquote>
+
----
----
This is part wikified from the original [http://www.erights.org/data/serial/jhu-paper/recog-n-build.html Part 2: "Reversing" Evaluation]
This is part wikified from the original [http://www.erights.org/data/serial/jhu-paper/recog-n-build.html Part 2: "Reversing" Evaluation]

Revision as of 01:31, 30 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 

}

As we see, the E.call(..) underlined above is where all the object construction is done. All the rest is plumbing to hook the up the references among these objects.

The only extra parameter to the above code, in addition to those specified by the DEBuilder API, is the scope parameter to makeBuilder(..). Typically, we will express unserialization-time policy choices using only this hook. With a bit of pre-planning at serialization time, this can be a surprisingly powerful hook, and will often prove adequate.

Unevaluating to Data-E

Because the keys of a unscope table may be arbitrary values, including unresolved promises, it needs to be the special kind of map called a CycleBreaker. For present purposes, we can ignore this issue.

We are now ready for the heart of serialization -- the Data-E subgraph recognizer. It has two parameters for expressing policy -- the uncallerList and the unscopeMap.

Since we are evaling "in reverse", we need the inverse of a scope, which we call an unscope. An unscope maps from arbitrary values to a description of the "variable name" presumed to hold that reference. In the unscope table passed in as unscopeMap, each description is a normal variable name string, as would be used to look the value up in a scope. On each recognize(..), the ".diverge()" makes a private copy of the unscopeMap we put in the variable unscope, which we use from there. This private unscope table gets additional mappings from values to integers representing temporary variable indices.

The uncallerList is used to obtain a portrayal of each object, as we explain below.

def makeUnevaler(uncallerList, unscopeMap) :near {
    def unevaler {
        to recognize(root, builder) :(def Root := builder.getRootType()) {

            def Node := builder.getNodeType()

            def uncallers := uncallerList.snapshot()
            def unscope := unscopeMap.diverge()

            # forward declaration 

            def generate

            /** traverse an uncall portrayal */
            def genCall(rec, verb :String, args :any[]) :Node {
                def recExpr := generate(rec)
                var argExprs := []
                for arg in args {
                    argExprs := argExprs.with(generate(arg))
                }
                builder.buildCall(recExpr, verb, argExprs)
            }

            /** When we're past all the variable manipulation. */

            def genObject(obj) :Node {

Below we see another bit of E syntax. In the pattern-match expression, there is a subexpression on the left of the "=~" operator, like "obj" below, and a sub-pattern on the right. The subexpression is evaluated to a specimen, and the pattern is asked to try matching the specimen. If it succeeds, the pattern-match expression returns true, and any bindings defined by the match are available in the successor scope -- here, the body of the if's then-part. When this pattern is a variable declaration, like "i  :int", the pattern matches if the specimen is compatible with the declared type (i.e., is successfully coerced by the guard). This gives us, in effect, a type-case. This last test below is passed by "bare twine", which for present purposes just means "String". These are all the types that can be represented literally in E and in Data-E.

                if (obj =~ i :int)     { return builder.buildLiteral(i) }
                if (obj =~ f :float64) { return builder.buildLiteral(f) }
                if (obj =~ c :char)    { return builder.buildLiteral(c) }
                if (obj =~ twine :Twine && twine.isBare()) {
                    return builder.buildLiteral(twine)
                }

To the right of the "=~" below is a list pattern. A list pattern is written as a list of subpatterns. It matches a specimen list of the same length if and only if each subpattern matches the corresponding element of the specimen list. An uncaller should respond to .optUncall(obj) with either null or a list of three elements, so the following tests that the resulting specimen wasn't null, and if it wasn't, binds these three elements to variables named rec, verb, and args [ref destructuring-bind]. More on the meaning of this uncall-triple <a href="#uncalling">below</a>.

                for uncaller in uncallers {
                    if (<u>uncaller.optUncall(obj)</u> =~ [rec, verb, args]) {
                        return genCall(rec, verb, args)
                    }
                }
                throw(`Can't uneval ${E.toQuote(obj)}`)
            }

            /** Build a use-occurrence of a variable. */

            def genVarUse(varID :(String | int)) :Node {
                if (varID =~ varName :String) {
                    builder.buildImport(varName)
                } else {
                    builder.buildIbid(varID)
                }
            }

            /**
             * The internal recursive routine that will traverse the
             * subgraph and build a Data-E Node while manipulating the
             * above state.
             */

            # "bind" resolves a forward declaration
            bind generate(obj) :Node {

The ":notNull" declaration below accepts any value except null. The call map.fetch(key,func) returns the value associated with key if one is found, or func() otherwise. The expression thunk{} evaluates to a no argument function that return null. Since the values of the unscope are Strings or ints, we can use null to detect whether obj was found.

                <span class="keyword">if</span> (unscope.fetch(obj, thunk{}) =~ <span class="defvar">varID</span> :notNull) {
                    <span class="keyword">return</span> genVarUse(varID)
                }
                <span class="keyword">def</span> <span class="defvar">promIndex</span> := builder.buildPromise()
                unscope[obj] := promIndex
                <span class="keyword">def</span> <span class="defvar">rValue</span> := genObject(obj)
                builder.buildDefrec(promIndex+1, rValue)
            }

            builder.buildRoot(generate(root))
        }
    }
}

This is part wikified from the original Part 2: "Reversing" Evaluation

Personal tools
more tools