Interpretation

This is the second of the four main algorithms discussed on the Algorithms page.

Recall that the purpose of the Interpretation phase is to convert the IT to the OT.

The interpretation process described here may involve updating feedback attributes on IS instances in the IT. This is because there may be something invalid about those instances that prevented interpretation, and the user needs to be made aware of it. (Or there was something invalid before, and the user has now corrected it, and we're removing negative feedback, and the user should be updated.) This will be accomplished through the same global utilities used for sending feedback from any component of the LDE to the client. Each client will typically listen for such messages and react to them by adding, removing, or updating feedback in the UI in a location and manner that clearly connects the feedback to that portion of the user's input that created the IS that generated the feedback, as covered in the Messages section of the Clients page.

When Interpretation happens

Recall that, at the start of the Algorithms page, we said that API calls cause the LDE to initiate the three consecutive processing steps shown in the bottom row of the diagram on the Design Overview page. We also said that it is acceptable, in the name of efficiency, for the LDE to start all that work only after a small amount of time in which no API calls transpires.

The transition between the phases in the bottom row of that diagram is similar. Specifically, when the Modification phase has completed, it may immediately trigger the Interpretation phase, or not necessarily. In the name of efficiency, it may pause briefly to see if any calls from the client re-start the Modification phase, only initiating the Interpretation phase when a span of time with no re-runs of the Modification phase has taken place.

Similarly, when an API call comes in to modify the IT, any of these phases (Modification, Interpretation, and Validation) that is currently running should be immediately terminated, because it may be wasting its time processing outdated information. Once the API calls are complete, the Modification-Interpretation-Validation chain can be restarted, processing any dirty data, including data that was made dirty in the most recent API calls, or data made dirty in previous ones and whose processing was not completed because it was terminated early.

How Interpretation Traverses the IT

We define a single recursiveInterpret() routine in the IS base class, and subclasses do not typically override it (though they can in rare cases, discussed further below). Subclasses who wish to customize their interpretation will typically define their own interpret() routines, which recursiveInterpret() will call as needed. The details are as follows.

Let $R$ be the root of the IT. Recall that interpretation happens by calling R.recursiveInterpret(). Any X.recursiveInterpret() call takes two parameters, described below.

• accessibles - the ordered list of OSs accessible to the interpretation of $X$

  If this parameter is not provided, it defaults to the empty list, [].

• scope - the ordered list of top-level ISs whose interpretation will be in the scope of $X$'s interpretation (which is most often just the list of all later siblings of $X$)

  We say "top-level" for the following reason: If $Y$ is a sibling of $X$ whose interpretation will be placed after that of $X$, then the interpretation of any descendant of $Y$ will, in some way determined by $Y$, be incorporated into $Y$'s interpretation, and thus will also be in the scope of the interpretation of $X$. So it would be redundant to form a list of not only $Y$ but all of its descendants. Rather, the scope contains only the highest ancestors of each subtree and the descendants are implied.

  This, too, defaults to [].

Thus the call to R.recursiveInterpret() documented above is equivalent to a call to R.recursiveInterpret([],[]). This makes sense, because there is nothing accessible to the document nor is there anything in its scope. (Although it might seem as if dependencies should be accessible to the document, dependencies are actually imported as if they were the first children inside the document, so that they can be interpreted into the OT.)

The constructor for the IS class must initialize to null an attribute for caching the last-computed interpretation of the IS, and will provide a function called lastInterpretation() that returns that cached value. Any call to X.recursiveInterpret(), if $X$ is not dirty, will simply return X.lastInterpretation() and quit immediately, for efficiency. Otherwise, it proceeds as follows.

1. Remember the size of accessibles for later:

   Let $L$ be the current length of the accessibles array.

2. We will be recursively computing child result arrays, and will want to keep a list of them, so initialize that list to empty:

   Let childResults be the empty array, [].

3. As we recursively descend into children, we will want to pass them appropriate values for their scope parameters. So initialize this list to be all children:

   Let childScope be the array of all children of $X$.

4. Now the loop for the recursive work.

   For each child $C$ of $X$ (looping in $\ll$ order) do the recursion as follows:

   1. Remove the first item off the scope list.

   2. For the first child, the same list of accessibles for the parent applies to that child:

      Let childResult be C.recursiveInterpret(accessibles,scope).

   3. But for later children, more things are accessible. Specifically, anything just created by interpreting $C$ should be accessible to C.nextSibling(), so:

      Let accessibles be the concatenation of accessibles with childResult (thus extending accessibles).

   4. And of course remember the result of the recursive call we just made:

      Append childResult as a new entry to the end of childResults (which is an array of arrays).

5. Now that we're done recurring, we want to restore the accessibles array to its old state:

   Let accessibles be just the first $L$ entries of accessibles (restoring it to what it was at the start of this routine).

   This is because we will now ask $X$ to interpret itself in light of (a) what's accessible to it and (b) all the recursive results of interpreting its children.

6. With that updated accessibles array, we can complete the interpretation of $X$:

   Let $X$'s cached lastInterpretation value be X.interpret(accessibles,allChildResults,scope) and mark $X$ as no longer dirty.

   Then return X.lastInterpretation() as the result of X.recursiveInterpret().

When R.recursiveInterpret() completes, replace the OT with the newly cached result, R.lastInterpretation(). Note that, because many cached interpretations of subtrees were re-used, this new OT may contain a great many OSs that the previous OT contained, and is thus typically not entirely new.

This section described the default implementation of recursiveInterpret(), but we will permit customization of it as described under Custom Recursive Interpretation, below. For that reason, we make the following definition.

Definition (interpretation order). We say that an IS $X$ is interpreted before an IS $Y$, written $X \triangleleft Y$, if it is visited earlier in the recursive traversal performed by R.recursiveInterpret(), where $R$ stands for the root of the IT.

If we use the default implementation of recursiveInterpret() given earlier in this section, we have $X\triangleleft Y$ iff $X\ll Y$. But we make the above definition because we will permit more general recursive algorithms in the Custom Recursive Interpretation section, below.

Interpreting Individual ISs

The details in the previous section are heavily dependent on what X.interpret() does, and we cover that function in this section. The X.interpret() routine will be customized by each IS subclass to do the unique work of interpreting instances of that class. The default implementation will be very basic, and is documented further below.

The only calls to X.interpret() should be those made by X.recursiveInterpret(). Thus from the implementation of X.recursiveInterpret() defined above, we can see that X.interpret() receives three parameters:

• accessibles - the list of all OSs accessible to the interpretation of $X$

  Thus X.interpret() doesn't need to inspect the OT at all; it can just look in that pre-crafted array for anything it might need to depend on. X.interpret() can simply search the array (probably in reverse order, so more recent things are found first), because the array is guaranteed to be provided in $\prec$ order. The entries in that array may not actually be assembled into the OT yet.

• childResults - an array of all recursive interpretation results of $X$'s children

  X.interpret() doesn't have to do any recursion on the OT, nor police in any way the recursion that called it. It just assembles the (already recursively computed) results in childResults into zero or more OS trees, and returns an array containing those trees.

• scope - an array of all top-level ISs whose interpretations will be placed, in the OT, somewhere in the scope of the interpretation of $X$

  (See additional details in the documentation of the parameter of the same name above, in How Interpretation Traverses the IT.) \end{description}

The default implementation of X.interpret(accessibles,childResults,scope), provided in the base IS class, behaves as follows.

1. Let result be a new OS, serving as a plain vanilla wrapper node.
2. For each childArray in childResults, for each node in that childArray, append that node as a new child of result.
3. Return [result], that is, an array containing one thing, the result OS we just created and filled with children.

But any subclass of IS can redefine its own interpret(accessibles,childResults,scope) implementation to override that one. Typically, this will be the only thing that an IS subclass needs to customize. Most IS subclasses don't override recursiveInterpret(), which is created once and for all in the IS base class, but we will see in the next section those cases in which one could override recursiveInterpret().

There are a few restrictions that X.interpret() must obey.

1. The result of X.interpret() may be contingent only upon the following data.

   1. The interpretation of any descendant IS $Y$ of $X$. Note that $X$ is not accessible to any such $Y$.

   2. The interpretation of any IS $Y$ accessible to $X$. Note that ancestors of $X$ are not accessible to $X$.

      (All such $Y$ will have been interpreted before $X$, because $Y\prec X$ implies $Y\ll X$ and interpretation proceeds in $Y\ll X$ order. Let us say that $Y'$ is an OS in the interpretation of $Y$. It may be the case that during the interpretation of $X$, $Y'$ does not have some connections that it will gain later in the interpretation process. For example, assume that $Z\gg X$ and $Z\xrightarrow{\text{example}}Y$, with $Z'$ in the interpretation of $Z$. It may be that interpretation will copy the connection between $Z$ and $Y$ (depending on its semantics) so that $Z'\xrightarrow{\text{example}}Y'$. But that cannot happen until $Z'$ exists, which cannot happen until $Z$ is interpreted, which cannot happen until after $X$ has been interpreted, because $Z\gg X$. Thus when using OSs in the accessibles list, beware that they may not yet have all the connections they will have by the end of the entire interpretation process.)

   This is made easy by passing these things as the first two parameters to X.interpret(). So as long as that routine computes its output based on only its first two parameters, as opposed to seeking out other data, this rule is automatically followed.

2. For any two ISs $X$ and $Y$, X.interpret() may call Y.markDirty() only if $Y$ or one of its ancestors is on the scope list.

   This guarantees that the recursive interpretation procedure will terminate with all ISs marked clean, for the following reason. If X.interpret() marks $Y$ dirty, then $Y$ is on $X$'s scope list, meaning that the interpretation of $Y$ will be in the scope of the interpretation of $X$, or equivalently, the interpretation of $X$ will be accessible to the interpretation of $Y$. Therefore we must have $X \triangleleft Y$, so that the eventual call to Y.interpret() can be passed the correct accessibles parameter, which must contain the interpretation of $X$. Thus any $Y$ that X.interpret() marks dirty has yet to be visited by the recursive interpretation, and so we know that it will be processed (and thus marked clean) later in the same (ongoing) traversal of the IT.

   We may choose to police this requirement by adding code that throws an error if Y.markDirty() is called after Y.interpret() began but before R.recursiveInterpret() finished.

It may be a common occurrence for the interpretation of one IS to mark another IS dirty; for instance, if $X$ is something whose interpretation will impact the interpretation of things in $X$'s scope, it may choose to mark any subset of things in its scope as dirty for interpretation.

Definition (Interpretation Directive). We call OSs that may impact the interpretation of things in their IS's scope Interpretation Directives.

To be efficient, we may require IS subclasses to mark themselves as possibly creating Interpretation Directives (versus definitely not creating any). This would permit us to process, in parallel, the interpretation of several $\ll$-consecutive ISs that are not marked as able to create Interpretation Directives. The above definition also lets us also be more specific in item 1.ii., above: Only the Interpretation Directives in the accessibles array are relevant to interpretation, not every single element of that array.

Thus one optional efficiency improvement is to add to the accessibles array the additional feature that it has precomputed the indices of the sublist of Interpretation Directives, and maintains that list of indices as elements are added to or removed from the accessibles array. This permits faster traversal of the list of Interpretation Directives for those interpret() routines that wish to do so.

The existence of a connection between two ISs $A$ and $B$ does not necessitate, nor is it necessitated by, the existence of a corresponding connection between OSs produced by A.interpret() and B.interpret(). Indeed, any connection structure in the OT should be there iff it is useful for validation.

As each subclass implements its own interpret() routine, it should try to make use of the cached value stored as the lastInterpretation() of each instance, for efficiency. But as it does so, there are a few pitfalls it must be sure to avoid.

• No interpretation routine should assume that such a field contains data, because it is always empty the first time interpretation is run.

• Interpretation routines should not assume that the OSs in X.lastInterpretation() have remained untouched or unaltered since they were cached.

  For example, an ancestor of X may choose to leave the interpretation of X or one of X's children out of the OT entirely. Or an IS Y interpreted later than X may have connected some of its corresponding OSs to one of the OSs in X.lastInterpretation(), thus modifying it by adding a connection.

Custom Recursive Interpretation

In rare cases, an IS may not be able to implement its mathematical semantics adequately by implementing just an interpret() routine that will be called by the recursiveInterpret() routine in the IS base class. Specifically, there may be situations in which the semantics of the IS require that the LDE not interpret its children in $\ll$ order. We give two examples.

We can imagine mathematical structures that express the backwards semantics that sometimes occur in mathematical parlance. For instance, we sometimes say things like, "so $x^2+9=k$, where $k$ is defined to be $P(r^t-s)$." The variable $k$ is used before it is declared, but the sentence structure tells us that this is okay, because we are supposed to read it backwards. One way to support such user input is to have the UI encode such input into the IT in the same order the user wrote it, but wrapped in an IS that tells the LDE to interpret the children in a nonstandard order. Thus later expressions in the sentence would be accessible to earlier ones, rather than the other way around. That is, there would be some $X \ll Y$ for which $Y \triangleleft X$ and the interpretation of $Y$ is $\prec$ the interpretation of $X$. Another way to support this same feature is to require the UI reorder the expressions. Regardless of which method is the better design decision, we simply point out here that it is possible to handle it within the LDE, using a nonstandard order of recursion during interpretation.

We can also imagine a client that lets the user designate certain blocks of content as being a single chunk of work, such as an "exercise" or a "proof." We can further imagine that the client might permit the user to turn on or off validation for an entire exercise or proof at once, perhaps to speed up validation for the entire document. In such a context, the correct semantics for the block whose validation has been disabled could be to skip recursively interpreting children altogether. For such a child $X$ not visited by the recursive interpretation, we would have neither $X \triangleleft Y$ nor $Y \triangleleft X$ for any IS $Y$.

To handle either of these two example cases, or any case in which the semantics of the IS require something other than recursive interpretation of children in $\ll$ order, we permit any IS subclass to define its own version of recursiveInterpret(). The only requirements are these:

• The implementation must correctly express the mathematical semantics of the IS subclass.
• It must pass the correct parameters (accessibles, childResults, and scope) whenever it calls interpret().
• It must cache the results of interpret() when it receives them, using the lastInterpretation value in the originating IS, as the default implementation does.

Notice that the second condition forces interpreting children in the $\prec$ order of their interpreted output in the OT, thus constraining $\triangleleft$ in the IT based on $\prec$ in the OT. This may cause $\triangleleft$ to differ from $\ll$ in the IT because of the atypical semantics of the IS subclass.