CHAPTER 28
DISAMBIGUATION BY COMMON SENSE
IN POLYNOMIAL TIME
The previous chapter showed how to supress an exponential cost for
processing semantics that generate phrases in another language.
We defined what OR-blocks should do, and what shared blocks should do,
to supress exponential blowup.
We now concentrate on the last language in a sequence, such as the
datatype language in our case. We must decide what OR-blocks should
do in the semantics of the datatype grammar, as well as what to do
at shared blocks, again in order to supress exponential or even
infinite blowup.
Unlike the previous chapter, we place no restrictions on the grammar,
which may now have cyclic coercions like:
INT -> REAL
and
REAL -> INT
28.1
What OR-Blocks Should Do In The Semantics Of The ~Datatype ~Grammar
Ambiguities from the syntax grammar generate ambiguous phrases in the
datatype language, as we've just seen. All ambiguities, both
syntactical and those arising from the datatype grammar, are
represented as ambiguous phrases in the datatype language.
All the ambiguities that survive thru datatype processing are actual
ambiguities. They've survived both syntax and datatype processing.
We will ~disambiguate ~by ~common ~sense or ~resistance among those
surviving ambiguities. That is, we will choose a meaning that
involves a minimal number of type conversions.
From Section 15.2, we learned that surviving ambiguities wind
up as OR-blocks in the final semantic structure.
We now consider what OR-blocks ~in ~the ~datatype ~language's
~semantics should do. The previous chapter showed what OR-blocks are
supposed to do within the semantics of the syntax grammar.
28.2
Disambiguation By Common Sense, Or Resistance
Of all possible meanings, common sense would choose the simplest
alternative. The simplest alternative minimizes the number of
conversions from one type to another.
For example, given the datatype rules:
~INT -> ~REAL
and
~REAL -> ~INT
how would you expect the coercions to apply to turn an INT into a
REAL? You probably would pick one application of the first coercion.
However, there are more possible interpretations. For example, an INT
could be turned into a REAL via ~two applications of the first rule
and one application of the second rule, as in:
~INT -> ~REAL -> ~INT -> ~REAL
Clearly, the solution which involves three coercion applications is
less desirable than the direct approach, which applies only one
coercion.
28.2.1
Another Example
For another example, consider the datatype expression (which we show in
the infix notation for convenience):
~INT + ~INT
Consider the datatype grammar (which we also show in the infix
notation):
~INT + ~INT -> ~INT
~REAL + ~REAL -> ~REAL
~INT -> ~REAL
There are two distinct ways by which the ~INT+INT can be interpretted
as a REAL:
a) The two INTs can be summed, using integer addition (the first
rule), resulting in an INT. That INT is then turned into a
REAL (the third rule).
b) Each of the two INTs can be turned into REALs (by two
applications of the third rule). Those REALs
are then summed using floating-point addition, resulting in
a REAL (the second rule).
These are illustrated in figure 28.1(a and b).
If we choose to minimize the total number of coercions employed, then
interpretation (a), which uses only one coercion, will win over
interpretation (b), which uses two coercions.
Figure 28.1(c) shows the CHOICE_OF_PHRASES structure for our example
~INT+INT. There appears to be two full-spanning REALs, one for each
of our two interpretations. In fact, there is only one full-spanning
REAL, but its semantics are ambiguous (see Section 15.2).
Figure 28.2 shows the ambiguous semantics under the one full-spanning
REAL. The figure has two pointers labelled A and B, which show the
two interpretations under the REAL. They are combined via the OR-
block.
28.2.2
Associating A Resistance With Each Block
We introduce resistance into the semantic structure by associating
a resistance at each block. The resistance of a block is the ~sum
of the resistances of the blocks that it references below. Blocks at
the bottom of the structure have resistance zero.
So far, all blocks have resistance zero. However, a coercion
introduces a resistance of one. That is, the resistance of a semantic
block that is the result of a coercion gets as its resistance ~one
~plus the resistance of the block to which it points below.
Figure 28.2 includes with each block its resistance. Interpretation A
has a resistance of one whereas interpretation B has resistance two.
To choose an interpretation that minimizes resistances, each OR-block,
like the one in figure 28.2, chooses the interpretation below having
minimum resistance.
In our example, the OR-block chooses its left alternative (A) and
ceases to reference the more resistive alternative (B). The OR-block
thus ceases to represent two choices. It becomes a ~identity. The
invocation of the disambiguated OR-block merely invokes its one
remaining interpretation, A.
If an OR-block's two interpretations have identical resistances, the
OR-block remains ambiguous, still holding onto both the
interpretations.
BOX: What does it mean to disambiguate by common sense?
BOX:
BOX: What are the two interpretations for rendering a REAL
BOX: from the expression "INT+INT"?
BOX:
BOX: Which interpretation will be chosen after we
BOX: disambiguate?
BOX:
BOX: How many ways are there to render "-INT" as a REAL,
BOX: assuming that "-" is defined for both INTs and REALs?
28.2.3
Implementation Of Resistance
How do we implement this disambiguation by resistance? We need some
way to ask a semantic block what its resistance is.
We make each semantic block perform two tasks. One is to deliver its
resistance and the other is to act out its original meaning that we
expect of the semantic block.
Let's introduce a global variable that dictates to a semantic block
which of the two tasks to perform:
VAR COMPUTE_RESISTANCE = BOOL;
A TRUE value demands a resistance from each semantic block, whereas a
FALSE demands the original semantic action. When a resistance is
demanded, we expect the semantic block to put the computed resistance
into the following global variable:
VAR THE_RESISTANCE = REAL;
For example, the rule we used to write as:
<REAL:X> <REAL:Y> <PLUS> ->
<REAL: INSTRUCTION(270,X,Y); >
must now be implemented as:
<REAL:X> <REAL:Y> <PLUS> ->
<REAL:
BEGIN VAR RES=REAL;
IF COMPUTE_RESISTANCE THEN
"The resistance of X goes into RES..."
<*X*>;
RES:= THE_RESISTANCE;
"Add in Y's resistance..."
<*Y*>;
THE_RESISTANCE::= + RES;
ELSE
INSTRUCTION(270,X,Y)
FI
END
>
When COMPUTE_RESISTANCE is TRUE, we invoke each of X and Y so as to
have each place its resistance into THE_RESISTANCE. We form their
sum and leave it in THE_RESISTANCE, as we are supposed to do. Recall
that the resistance of a block is the sum of the resistances of its
constituents.
In the other case, when COMPUTE_RESISTANCE is FALSE, we perform as we
did originally, calling INSTRUCTION.
We will take the liberty to write this all more simply as:
<REAL:X> <REAL:Y> <PLUS> ->
<REAL:
RESIST => X+Y
USUAL => INSTRUCTION(270,X,Y)
>
This shows the essential information most clearly. The resistance
is X+Y, and the USUAL action calls INSTRUCTION.
For another example, let's revisit how a NUMBER becomes an EXPR:
<NUMBER:N> ->
<EXPR:
<INT:
RESIST => 0
USUAL => LOAD( 1, ADDRESS_OF(N));
>
>
The INT's resistance is zero. Its USUAL action is to load the number
into register 1.
Here is an example coercion, which introduces non-zero resistance:
<INT:X> -> <REAL:
RESIST => X+1
USUAL => INSTRUCTION(300,X);
>
The resistance of the resulting REAL is one greater than that of the
given INT.
28.2.4
Resistance At The OR-Block
Let's modify the OR-block so as to be able to deliver a resistance
like other blocks do, and to disambiguate based on resistances.
Recall that ~within ~the ~function ~GIVE, we assigned into OR the OR-
block as follows:
OR:= //[A;B;] F(A,B); \\ ;
(We used the names NEW and COPY_OLD in place of A and B). F was
left unspecified at the time.
In Section 25.5.4 we decided on what F should do for semantics which
generate phrases in another language (e.g., our syntax grammar),
resulting in this:
OR:= //[A;B;]
<*A*>;
<*B*>; \\ ;
This OR-block causes both alternatives A and B to generate their
phrases, resulting possibly in ambiguous phrases.
In contrast, for the semantics of the datatype grammar, where
resistances exist, we would like to assign into OR as follows:
OR:= //{A;B;} BEGIN VAR RA,RB = REAL;
IF DEFINED(B) "We haven't resolved this ambiguity yet"
THEN
IF COMPUTE_RESISTANCE THEN
<*A*>; RA:= THE_RESISTANCE; "Get A's resistance
into RA"
<*B*>; RB:= THE_RESISTANCE; "Get B's resistance"
THE_RESISTANCE:= RA MIN RB; "Our resistance is the
minimum."
IF CERTAIN "RA and RB are reliable" THEN
"Pick a winner between A and B, and leave the
winner in A... "
IF RA < RB "A wins" THEN B:= NIL;
EF RB < RA "B wins" THEN A:= B; B:=NIL; FI
"A has the winner"
FI
ELSE "Our non-resistance (usual) action... "
<*A*>; "Act as identity. B is ignored. We may
wish to report an ambiguity. We are
making an arbitrary choice."
FI
ELSE "Unambiguous"
<*A*>;
FI END \\ ;
The outer IF-THEN-ELSE enters the big THEN clause only if B is still
defined. B is always defined initially. However, an earlier
invocation of this OR-block might have already caused disambiguation,
by putting NIL into B.
If B isn't defined then we have no ambiguity at all. Here, we
invoke A in the outer ELSE-clause. A is our official meaning when
B isn't defined.
B can be set to NIL in the outer THEN-clause. We set B to NIL as
soon as we can disambiguate, i.e., choose one meaning over the other.
Focus now on the big, outer THEN-clause.
The outer THEN-clause responds to COMPUTE_RESISTANCE properly. If
TRUE, it acquires the resistances of A and B, assigning those
resistances into RA and RB. The minimum of those two is our
resistance (as we will retain only the interpretation having least
resistance).
We then put into A either A or B, whichever has the least resistance.
(This action is done only if CERTAIN is TRUE. So far, it's always
TRUE. It may become FALSE only when we consider cycles (soon to
come)).
In the inner ELSE clause, when we are not computing resistances, we
invoke our favorite A, so that this whole OR-block comes to act exactly
like A alone does.
If A and B have identical resistances, then we make an arbitrary
choice by always choosing A.
28.2.5
Differing Meanings For OR-Blocks
So far, we want OR-blocks to behave one way during the semantics of
the syntax grammar, and another way during the semantics of the
datatype grammar.
OR-blocks are created inside of GIVE. We will need
to introduce an IF-THEN-ELSE in GIVE so as to pick the different
desired OR-block behavior in each case. In fact, this is generalized
so that an OR-action can be dictated on a ~per ~part-of-speech basis.
BOX: What roles do the variables COMPUTE_RESISTANCE and
BOX: THE_RESISTANCE play?
BOX:
BOX: What is the resistance of an OR-block?
BOX:
BOX: What must be true for an OR-block to disambiguate?
28.3
What We Do At Shared Blocks ~In ~The ~Semantics ~Of ~The ~Datatype ~Grammar
Recall that a semantic structure can represent exponentially many
meanings in only polynomial memory. The invocation of the semantic
structure will incur an exponential cost unless we supress all but the
first invocation of any block. This supression achieves a polynomial
cost.
Shared blocks are the only blocks that could be invoked more than once,
since each has more than one pointer pointing to it.
For the computation of resistance, let's remember our computed
resistance upon the first invocation. For subsequent invocations, we
will immediately deliver our previously computed resistance.
We hold onto a variable called LAST_TIME, as we did in Section 27.2.2,
to allow our shared blocks to be reset:
ORIGINAL:= COPY(S);
LAST_TIME:= 0;
MY_RESIST:= INFINITY;
@(S):= //{ ORIGINAL; LAST_TIME; MY_RESIST; }
IF COMPUTE_RESISTANCE THEN
IF PRESENT_TIME > LAST_TIME THEN
LAST_TIME:= PRESENT_TIME; "We will be up-to-date"
<*ORIGINAL*>; "Continue downward thru the semantic
structure, so as to compute our
resistance."
MY_RESIST:= THE_RESISTANCE; "Remember newly computed
resistance."
ELSE " PRESENT_TIME = LAST_TIME.
Announce my resistance... "
THE_RESISTANCE:= MY_RESIST; FI
ELSE "The usual action. (We act as the identity)..."
<*ORIGINAL*>;
FI \\ ;
We first set ORIGINAL to be a copy of S, and LAST_TIME to be zero,
as we had done before for shared blocks in the previous chapter.
We then respond to COMPUTE_RESISTANCE by ultimately setting
THE_RESISTANCE. If this is a non-first encounter, (LAST_TIME =
PRESENT_TIME), we enter the inner ELSE-clause and set THE_RESISTANCE
to our previously computed resistance (MY_RESIST). In contrast, we
enter the inner THEN-clause if this is our first encounter. There, we
invoke ORIGINAL so as to compute our resistance. That result will
reside in THE_RESISTANCE, and we remember that value in MY_RESIST.
If this overall assignment, into "@(S)", is applied to all shared
blocks in a semantic structure, we will have achieved the resistance
computation in only polynomial time, even if there are exponentially
many meanings represented.
BOX: What does a shared block do if LAST_TIME is not equal
BOX: to PRESENT_TIME?
BOX:
BOX: What does it do if those two variables are equal?
BOX:
BOX: What value is in MY_RESIST initially?
28.4
Cycles
We've considered almost all kinds of semantic structures. The one
last topic to consider is ~cycles in the semantic structure.
We now consider how to cope with cycles. In summary, Section 28.4.5
shows the slight modification required for cycles at shared blocks.
Section 28.4.5.1 shows what we need to do at the top of a semantic
structure to deal with cycles.
How can there be a cycle in a semantic structure? Consider the
expressions "5". Suppose we have the two coercions between INT and
REAL:
~INT -> ~REAL
~REAL -> ~INT
There are many ways by which "5" can be turned into the REAL "5.0":
1) INT "5" -> REAL "5.0"
2) INT "5" -> REAL "5.0" -> INT "5" -> REAL "5.0"
3) INT "5" -> REAL -> INT -> REAL -> INT -> REAL "5.0"
In fact there are infinitely many ways to turn the INT into a REAL.
Even with the posiblity of infinitely many meanings, the semantic
structure that contains all of them consume only finite (polynomial)
memory. How is that possible? Figure 28.3(b) shows a finite
structure that represents infinitely many meanings.
The second to topmost block is the semantic block that represents the
REAL. Below that block is an OR-block that offers two meanings for
the INT. One of those INT meanings is directly the number 5.
The other choice refers back to the top of the figure. If you follow
this option, you will have to go thru the top INT, which derived from
the REAL just below it, which is itself derived from the OR-block at
the bottom, an INT.
You can now make a right turn at the OR-block and terminate the trip
at the "5" block, or you can make a left turn and travel once more
thru the top two blocks.
Whenever you make a left turn, you go around the cycle once again.
Your trip is finished as soon as you take a right turn.
In general, N left turns introduces N transistions from INT to REAL
and back to INT.
Oddly enough, the arrows in the diagram point in the ~opposite
direction from the arrows in our coercions. The arrows in the diagram
show that a block ~depends ~on the blocks to which it points. For
example, the coercion:
~REAL -> ~INT
builds an INT block that points back to the REAL block.
28.4.1
How Cycles Are Formed
Figure 28.3 illustrates how a cycle can be created within a semantic
structure. Part (a) shows the original INT (5) at the bottom, along
with the REAL derived from that INT (in the middle). This REAL block
is generated by the application of the coercion:
~INT -> ~REAL
With the creation of the REAL, the other coercion applies:
~REAL -> ~INT
Consider what happens when this new INT is generated (GIVEn).
GIVE takes the new INT and is about to introduce it as a new PHRASE
block on the CHOICE_OF_PHRASES C (not shown in figure).
However, GIVE sees that an INT already exists (the original INT 5),
sharing the same span with the newly proposed INT. GIVE therefore
does not introduce the second INT onto C. Rather, it takes the two
INTs' meanings and ties them together with an OR-block (figure
28.3(a)).
As shown in Section 15.2, GIVE modifies objectively the
original INT's semantics. It uses the "@" operator to place the OR
block directly over the original INT's semantics. Figure 28.3(b) shows
the result. The OR-block now sits where the original INT's semantics
sat.
As discussed in Section 10.2.6, cycles can arise only from the use of
objective modification. Our one use of objective modification in fact
can and here does introduce a cycle.
28.4.1.1
Any Cycle Contains An OR-Block
The cycle we've seen has an OR-block in it. All semantic cycles do.
Recall that a cycle comes to exist only upon an objective modification
(Section 10.2.6). All our objective modifications involve OR-blocks
(inside GIVE). Thus, the moment a cycle comes to exist, it has an
OR-block within it.
OR-blocks provide for the escape from cycles. In our previous cycle
example, a right turn at the OR-block led to the escape from the cycle.
BOX: What causes cycles in a semantic structure?
BOX:
BOX: Can you think of one rule which by itself causes a
BOX: cycle?
BOX:
BOX: How does a cycle represent infinitely many meanings?
BOX:
BOX: Any cycle contains at least one of what kind of block?
28.4.1.2
All Cycles Are Built Only Out Of Coercions, Besides OR-Blocks
A cycle can exist in a semantic structure when one or more rules can
be applied infintely many times. The only kind of rules that can
apply infinitely many times are coercions. All non-coercion rules in
a context-free grammar map ~two ~or ~more items to one item, as in:
UOP EXPR -> EXPR
Such a non-coercion rule performs a rewrite by erasing ~more than
what it puts back into the string. That is, each application of a non-
coercion rule shortens the string. Since the original string given to
parse is finite, non-coercion rules can apply, and hence shorten the
string, only a finite number of times.
Therefore, cycles can contain no non-coercion rules. A cycle can
contain only coercions and OR-blocks.
28.4.2
We Never Want To Travel The Entirety Of A Cycle
Because a cycle consists only of coercions and OR-blocks, consider the
resistance encountered by travelling around the entire cycle once.
Each coercion has a resistance of one, and so if there are N (coercion)
blocks in the cycle, a complete trip around the cycle encounters a
resistance of N.
Any overall trip that goes around an entire cycle is more resistive
than the same trip that avoids the round trip. For example, in going
from Los Angeles To New York, the shortest trip will not pass thru any
given city more than once. Figure 28.4(a) shows a cycle. Part (b)
shows a trip that travels thru the entire cycle. Part (c) shows a
more optimal (less resistive) trip.
28.4.2.1
Cycle Cutting Occurs At OR-Blocks
A ~solution to a semantic structure is an association of resistances
to blocks, and the clipping of all cycles. A cycle is clipped by
cutting off one of the two pointers emanating from an OR-block.
Figure 28.5 shows a cycle with resistances shown. There are two
OR-blocks in the cycle. The lower-right OR-block's two pointers point
to paths having resistances 22 and 40. This OR-block thus chooses to
keep the 22 pointer, and cut the 40 pointer.
The leftmost OR-block sees its two choices having resistances 23 and
20. This OR-block chooses to keep the 20, and clip the 23. It is
this clipping which cuts a cycle.
We prove that any cycle will be clipped, assuming of course that we
can solve for resistances correctly:
Pick any cycle. Not all blocks in the cycle have the same
resistance. A cycle contains at least one coercion, and that
coercion, like any coercion, has resistance one greater than
the block to which it points (e.g., the rightmost block in
figure 28.5).
Thus the coercion block and the block to which it points have
different resistances.
Pick a block in the cycle that has minimal resistance. Go
forward in the cycle until the next block differs in
resistance. That second block has resistance strictly greater
than the first block's minimal resistance, by assumption.
In figure 28.5, the block with lowest resistance (20) is
the OR-block on the left. It points within the cycle to a
block of greater resistance, 23.
Our chosen block of least resistance must be an OR-block,
because the only other kind of block, a coercion block, would
itself point to a block of resistance even less than the
minimum. (That is impossible, by assumption).
For this OR-block to have minimum resistance, the exit pointer
(the pointer that leaves the cycle) must itself be of our
minimal resistance. This is so, because the other pointer
(into the cycle) references a block having resistance strictly
greater than our resistance.
This inequality, between the exit pointer's minimum
resistance and the other pointer's strictly greater resistance,
assures that the pointer into the cycle will be clipped, when
the OR-block ultimately disambiguates (chooses one or the other
pointer).
We have shown that this cycle will be clipped ~at ~least at
the chosen OR-block.
BOX: BOX: Why must a cycle consist only of OR-blocks and
BOX: coercions?
BOX:
BOX: How do you reduce the resistance of a trip that goes
BOX: the entirety of a cycle?
BOX:
BOX: Why, assuming that resistances are computed correctly,
BOX: will any cycle be clipped?
28.4.2.2
Cycles Are Entered At Shared Blocks
Back before we considered cycles (Section 27.4), we introduced a step
that was to be performed ~prior to invoking a semantic structure.
That step discovered all shared blocks, and modified them objectively
so that we could implant a desired behavior at all shared blocks.
Shared blocks play an important role within cycles. Any cycle that
you can get to contains at least one shared block. Figure 28.6(a)
shows a cycle, and 28.6(b) shows a cycle we can get to. The block at
which we enter a cycle is a shared block. It is pointed to from two
places: The block before it in the cycle points to it, and also
our entry pointer points to it.
28.4.3
More Complex Cycle Examples
Figure 28.7(a) shows the semantic structure that arises from the two
pairs of coercions:
A -> B
B -> A
A -> C
C -> A
There are two cycles here. Part (b) shows a path entering thru the
C block. That path represents the coercion
A -> C
Figure 28.7(c) shows the same but with one more coercion:
X -> B
Figure 28.7(d) shows a path thru the two cycles that represents three
coercion applications:
X -> B -> A -> C
28.4.4
Cyclic Encounters
Figure 28.8(a) shows in detail how we traverse a tree structure with
a shared block. For purposes of illustration, we will use ~three
~states now to denote that status of each block:
0 => ~Never ~been ~here ~before
1 => ~Busy
2 => ~Done
A block starts off in state 0, having not yet been seen. Upon
encountering a block, we set the block's state to 1. State 1 means
~busy. We have ~begun processing at that block but we are as yet not
finished processing that block.
The first frame in figure 28.8(a) shows a semantic structure at whose
top we've just arrived. That block enters state 1, and all the blocks
below, which haven't been encountered yet, are still in state 0.
The second frame shows us encountering another block. Its state is set
to 1. The third frame shows us touching one of the bottom blocks in
the structure.
The fourth frame shows that we've finished processing that bottom
block. Its state winds up 2, since we've finished processing it.
So far, every block we've encountered is initially in state 0. The
ninth frame shows us for the first time encountering a block which is
already in state 2. This implies we've been there before. We have
thus discovered a shared block.
This is all exactly the same as the way we detected shared blocks
before. Our states correspond to a block's ~markedness as follows:
0 => ~Never ~been ~here ~before. IT IS NOT MARKED
1 => ~Busy IT IS MARKED
2 => ~Done IT IS MARKED
Part b of figure 28.8 shows what happens when we encounter a cycle.
We begin travelling the cycle, putting encountered blocks into state
1. The fourth frame in figure 28.8(b) shows us encountering a block
in state 1! This is our first encounter with a block in state 1.
We have detected a cycle. We call this a ~cyclic ~encounter. We're
entering for a second time a block whose processing is as yet
unfinished.
BOX: How do you detect a cyclic encounter?
BOX:
BOX: How do you detect a shared block?
28.4.4.1
A Cyclic Encounter While Computing Resistance
Recall our process at shared blocks S. That process appears
immediately following the "@(S):=" in:
ORIGINAL:= COPY(S);
LAST_TIME:= 0;
MY_RESIST:= INFINITY;
@(S):= //{ RESIST; LAST_TIME; ORIGINAL; }
IF COMPUTE_RESISTANCE THEN
IF PRESENT_TIME > LAST_TIME THEN
LAST_TIME:= PRESENT_TIME;
<*ORIGINAL*>;
MY_RESIST:= THE_RESISTANCE;
ELSE THE_RESISTANCE:= MY_RESIST; FI
ELSE <*ORIGINAL*>; FI \\ ;
Let's focus in on the action we do while COMPUTE_RESISTANCE is TRUE:
IF PRESENT_TIME > LAST_TIME THEN
LAST_TIME:= PRESENT_TIME;
<*ORIGINAL*>;
MY_RESIST:= THE_RESISTANCE;
ELSE THE_RESISTANCE:= MY_RESIST; FI
Figure 28.9(a) shows a cycle. It is entered at its top block. We
enter the cycle and then travel around the cycle until our entry block
is reached again. This is a cyclic encounter because upon first entry
into the cycle, we ~began to compute its resistance, but hadn't
finished it yet.
Let's reconsider this action in more detail.
When we entered the top block, we began to compute its resistance,
e.g., by invoking a block:
<*ORIGINAL*>;
It is this invocation that causes the second block (below and to the
left of the top block) to compute its resistance. Its resistance is
computed by first obtaining the resistance of both of the blocks it
points to. That causes the third block in the cycle to be invoked, to
find its resistance. Eventually, the top block is encountered again.
The computation of resistance occurs as we return from our travels:
The top block delivers infinity (MY_RESIST) as its resistance
upon this second encounter. Figure 28.9(a) shows the
resistance delivered by each block in the cycle. The top
block yields infinity, and so the upper-right block also
delivers infinite resistance, since its resistance is based on
the top block.
The bottom-right block computes its resistance like any OR-
block does. It takes the ~minimum of the resistances delivered
by each of the two blocks it points to. The one pointer from
that OR-block that leaves the cycle has some resistance, say
40. That OR-block therefore delivers 40 as its resistance, the
minimum of infinity and 40.
Similarly, the leftmost OR-block delivers as its resistance 20,
which is the minimum of 41 and 20, the resistances of the two
blocks to which the OR-block points. We finally return to the
top block, with a computed resistance of 21.
The top block in the cycle finally has as its resistance 21.
That is indeed the minimum resistance obtainable by starting
at the top block, no matter how one leaves the cycle.
Note the following in this figure and figure 28.10. Each ~entry
points to a ~shared ~block, which is not shown in the figure. The
entered coercion block actually stands for both the coercion block
and our new, inserted shared block which references it. The
resistance stored in the shared block (MY_RESIST) is shown on the
interior of the coercion block.
28.4.4.2
Another Look
Let's assume, as is true initially, that LAST_TIME is less than
PRESENT_TIME.
Upon first entry, the THEN-clause executes, setting LAST_TIME to
PRESENT_TIME. What happens upon the second, cyclic, encounter with
the top block? On the second encounter, we find that LAST_TIME equals
PRESENT_TIME, and so we enter the ELSE-clause.
It is fortunate that we ~don't enter the THEN-clause again.
The THEN-clause would invoke ORIGINAL again, thus
initiating another trip around the cycle. Upon the third
encounter, the THEN-clause would be taken again, leading to
infinitely many trips around the cycle.
Within the ELSE-clause, which is taken upon the second encounter, we
deliver as our resistance the value in MY_RESIST. Unfortunately, that
value is not final. We've begun to compute our resistance, but we
haven't completed it by the time of this second encounter.
BOX: How is it that a block might deliver an inaccurate
BOX: resistance?
BOX:
BOX: What keeps us from going around the cycle more than
BOX: once?
28.4.5
Not All Blocks Have Accurate Resistances
As figure 28.9(a) shows, not all blocks in the cycle have accurate
resistances. The top block may now have an accurate resistance, 21,
but before, when it was a cyclic encounter, it delivered back its
incompletely computed resistance, MY_RESIST, which was infinity then.
From the point of view of a second entry at this cycle (see the
figure), inaccurate resistances are found. That second entry is a
shared block, which remembers its resistance from before, a 40. That
is not the least resistance for that block (see part (b) of the
figure).
Figure 28.9(b) shows the accurate resistances, assuming that the
exits' resistances are accurate (20 and 40). This is achieved by
making the same trip a second time. We enter again at the top block,
and go around the cycle, just like last time. We have a cyclic
encounter again, at the top block. This time however, it yields as its
resistance the 21 instead of last time's infinity. Figure 28.9(b)
shows the new resistances arrived at as a result of our new second
trip. Part (c) shows a path of least resistance that includes part
of this cycle.
It appears that a second trip thru the entire semantic structure may
render all blocks with accurate resistances. This time, cyclic
encounters appear to deliver accurate resistances. However, figure
28.10 shows an example which is not solved completely by two trips
alone. Part (d) shows for the first time that the block with an
asterisk achieves its accurate resistance of 25.
A shared block's computed resistance may differ from the resistance
it delivers at cyclic encounters, MY_RESIST. This change in a block's
resistance is a sign that other blocks may not yet get accurate
resistances. Let's change our activity at shared blocks, by inserting
the italics in the following:
IF LAST_TIME < PRESENT_TIME THEN
LAST_TIME:= PRESENT_TIME;
<*ORIGINAL*>;
~IF ~THE_RESISTANCE ~<> ~MY_RESIST ~THEN
~"Those ~blocks ~that ~depend ~on ~me
~may ~be ~incorrect."
~NEED_ANOTHER_TRIP:= ~TRUE;
~FI
MY_RESIST:= THE_RESISTANCE ;
ELSE THE_RESISTANCE:= MY_RESIST; FI
Now, we set NEED_ANOTHER_TRIP to TRUE if our resistance changes.
28.4.5.1
Obtaining Accurate Resistances Everywhere
We obtain accurate resistances by making trips repeatedly until no
shared block changes:
NEED_ANOTHER_TRIP:= TRUE;
WHILE NEED_ANOTHER_TRIP;
DO
NEED_ANOTHER_TRIP:= FALSE;
PRESENT_TIME::= + 1;
<*TOP*>;
END
We invoke TOP repeatedly until no block's resistance changes
throughout the entire semantic structure. TOP is the semantic
structure in question. TOP may be the semantic structure acquired from
the final rule application that completes the (datatype) parsing.
We increment PRESENT_TIME prior to each trip so that all shared blocks
will recompute resistances. This is necessary in order to
accomodate changes in other shared blocks' resistances. (We do indeed
still need our notion of PRESENT_TIME, because during any ~one trip,
we want to execute shared structures only ~once).
Because faulty resistances can exist on all but the last trip, we hold
CERTAIN to FALSE. Recall that CERTAIN is read by OR-blocks. OR-
blocks will disambiguate (make one choice over the other) only when
CERTAIN is TRUE. When no more trips are needed, (i.e.,
NEED_ANOTHER_TRIP is FALSE), we make one extra trip, this time with
CERTAIN held at TRUE. Disambiguation thus happens only when all
resistances are reliable.
In summary, given a semantic structure TOP, we compute resistance
and disambiguate based on those resistances by:
HOLDING CERTAIN:= FALSE;
COMPUTE_RESISTANCE:= TRUE;
DO NEED_ANOTHER_TRIP:= TRUE;
WHILE NEED_ANOTHER_TRIP;
DO
NEED_ANOTHER_TRIP:= FALSE;
PRESENT_TIME::= + 1;
<*TOP*>;
END
CERTAIN:= TRUE;
<*TOP*>;
ENDHOLD
TOP is now ready to be used for the original semantics (where
COMPUTE_RESISTANCE will be FALSE).
28.4.5.2
Will Taking Extra Trips Ever Terminate?
We must ask: Will NEED_ANOTHER_TRIP ever wind up FALSE? Yes.
For the following argument, let's assume that we set MY_RESIST
not to infinity, but to a finite number greater than the number of
blocks in the entire semantic structure.
Consider that MY_RESIST, in each shared block, can change only by
~decreasing in value. We start it at "infinity". ~All of our
resistance computations involve only additions and MINimums. There are
no minus signs. Therefore, if an input to a resistance computation
drops in value, the result of the computation can either stay the same
or drop in value. The result of a resistance computation cannot ever
increase.
We now know that values in MY_RESIST can only decrease over time.
Since all resistances are integers, and all solved resistances are non-
negative, there can be only finitely many decreases. This assures
that our WHILE-loop will terminate.
We can show even more. Each trip will solve at least part of one
cycle. That follows now.
BOX: What happens to cause NEED_ANOTHER_TRIP to become TRUE?
BOX:
BOX: Why can't a computed resistance ever increase in value,
BOX: assuming that its inputs don't increase in value?
BOX:
BOX: Why will our resistance computation finally end, that
BOX: is, why will NEED_ANOTHER_TRIP stay FALSE at some time?
28.4.6
At Least One ~Cycle ~Fragment Is Solved Per Trip
We would like to prove that each trip throughout the semantic
structure solves at least one cycle. We could then conclude that the
process of solving resistances consumes at worst a cost of K-squared,
where K is the size of the semantic structure.
This conclusion would be possible because a semantic structure of size
K (number of blocks) can have only less than K cycles. Given that
there are only K cycles, and given that each trip solves at least one
cycle, there can be at most K trips required. Each of the K trips
traverses the semantic structure of size K, giving rise to K^2
total cost (total number of blocks encountered).
We will prove however that each trip solves at least one ~cycle
~fragment. As we will see, each cycle fragment will contain at least
one block. From this, we can conclude again a K-squared worst-case
cost, this time associating with each trip a newly solved cycle
~fragment instead of a newly solved cycle.
This analysis is a worst-case performance. In practice, many cycles
(cycle fragments) are solved per trip. In a sense, all cycle fragments
of lowest resistance, like leaves on a tree, are solved on the first
trip. Each subsequent trip solves ~remaining cycle fragments of
lowest remaining resistance. This begins to show that a typical cost
may be only K*log(K) in practice.
Parsing a string of length N may deliver a semantic structure as big
as N^3 (number of blocks) (Section 14.4). In the N^3 structure,
exponentially many, or even infinitely many meanings may be
represented. This size of the semantic structure, K, is equal in
worst case to N^3. K*log(K)-to-K^2 thus translates to:
N^3 log(N) -to- N^6,
28.4.6.1
What Is A Cycle Fragment?
A ~cycle ~fragment is part of a cycle. Recall that cycles are formed
from coercions and OR-blocks. A cycle fragment is shown in figure
28.11(a). A cycle fragment starts off with coercions (on top) and
ends up at OR-blocks (on the bottom).
We allow more than one OR-block at the bottom. For mathematical
convenience, we collect up ~all accessible OR-blocks onto the bottom
of each cycle fragment, so that the leaves of the OR-blocks all point
to non-OR-blocks. If one of those leaves points to another cycle
fragment, it is pointing to a coercion block (not another OR-block).
Again, a cycle fragment that points to another cycle fragment points
to a coercion block, and never to an OR-block in that cycle fragment.
Instead of allowing a cycle fragment to point off to an OR-block, make
that OR-block part of this cycle fragment.
(Any OR-block can belong to several cycle fragments).
28.4.6.2
A Cycle Is Formed Of Cycle Fragments
Any cycle consists exclusively of cycle fragments: Pick any coercion
block in a cycle. Travel backwards thru coercion blocks until an OR-
block is encountered. Go forward one block so as to be at the coercion
block farthest back. This is the top of our first cycle fragment.
Travel forward from the top of the cycle fragment around the cycle,
until encountering an OR-block. Continue down that OR-block, possibly
encountering other OR-blocks. Continue thru the cycle until a non-
OR-block, a coercion, is found. Our first cycle fragment now ends
at the last OR-block, just before the found coercion block.
From there, the found coercion block becomes the top of the next cycle
fragment. This procedure winds up dividing a cycle into only cycle
fragments.
BOX: In a cycle fragment, what will have the lowest
BOX: resistance, a coercion block or an OR-block?
BOX:
BOX: Can a cycle fragment point off to an OR-block?
BOX:
BOX: Why is a cycle decomposable into cycle fragments?
28.4.6.3
Cycle Fragments Of Minimal Theoretical Resistance Are Solved By The Second Trip
We want to show that at least one cycle fragment will be solved per
trip.
Of all blocks in all cycles (cycle fragments), pick one whose
theoretical resistance is the smallest. That block belongs to (at
least) one cycle fragment. Consider any one of those cycle fragments.
We will show that ~at ~least ~upon ~the ~next ~trip, all blocks in
that cycle fragment will achieve their final values. That is, at
least this one cycle fragment will be solved by the next trip.
Consider the chosen cycle fragment, which has a block of minimal
theoretical resistance. All cycle fragments to which our cycle
fragment points cannot affect our fragment's resistance:
Some path thru the OR-tree at the bottom of our cycle
fragment points off to a structure, the top of which will hold
ultimately our minimal theoretical resistance (figure
28.11(c)).
That structure can reference no cycle fragments.
If it did, it would be pointing to a coercion. ~Just ~beyond
~that ~coercion is a block whose resistance is ~one ~less than
the coercion's resistance. The coercion references a block
whose resistance is less than our minimal chosen resistance.
This contradicts our assumption of having chosen a cycle
fragment of minimal resistance.
That minimal structure referenced by our minimal OR-blocks achieves
its theoretical resistance immediately, since it depends on no cycle
fragments. (Only blocks in cycles can change their resistances over
time, due to cyclic encounters).
No matter what resistances are reported by other pointers emanating
from our OR-tree, they will be ignored because they are all no less
than our minimum resistance. If they report inaccurate resistances,
they will be only on the high side. Those values will not affect our
computed ~MINimum resistance.
Because our chosen fragment depends on no others, it depends on no
cycles at all. Since only blocks in cycles can change over time, our
chosen fragment now has its final resistance in each block.
This might lead us to believe that all cycle fragments of minimal
resistance will be solved on the first trip. This is not quite the
case.
BOX: Why can't a cycle fragment of minimum resistance
BOX: point to other cycle fragments?
BOX:
BOX: Why therefore does some block in a cycle fragment
BOX: of minimum resistance achieve its theoretical value
BOX: immediately upon this trip?
28.4.6.3.1
Entry Blocks Into Cycles
Suppose the cycle shown in figure 28.11(d) is first entered at the top
block. That entry, and the continued travel around the cycle arrive
at the first OR-block. Its value is unchanging as shown before,
because the minimum path can reference no cycles. As the invocations
return, that is, as we back out of the cycle, correct, unchanging
resistances are left behind. This trip solves this cycle fragment.
However, a cycle might be entered for the first time halfway thru
the cycle fragment, as shown in figure 28.11(e). The first trip is
shown in figure 28.11(f). The blocks below the entry will be left with
correct, unchanging resistances as we back out from this trip.
However, the blocks above that entry block might have incorrect
resistances that can change, like infinity.
When only part of a cycle fragment is solved by the first trip, we must
rely on the ~next trip to solve the rest of the cycle fragment. The
next trip, which will follow the identical path (as all trips do),
will come around again, meeting the entry block. This time, that entry
block delivers its correct resistance (left by the previous trip).
The second trip returns, backing up along the cycle, starting from the
entry block. Figure 28.11(f) shows with thick blocks the returning
part of this trip. It now leaves correct, final resistances in the
fragment's upper blocks (prior to the entry block).
Thus, we are guaranteed that all cycle fragments of minimal theoretical
resistance are solve by this trip or the very next trip, no matter
what else happens on the next trip.
BOX: Why might it take more than one trip to solve even
BOX: a cycle fragment of minimal resistance?
BOX:
BOX: Why are two trips sufficient to solve such cycle
BOX: fragments?
28.4.6.4
Each Non-First Trip Solves At Least One More Cycle Fragment
Once the first two trips are complete, all cycle fragments of
minimal resistance are solved. Let's now consider all
other cycle fragments.
Once again, pick an ~unsolved cycle fragment whose resistance is
minimal ~among ~the ~unsolved cycle fragments. (This new minimal
resistance is at least one greater than our previous minimum, which had
included all the now ~solved cycle fragments).
The same argument given earlier applies once again for cycle fragments
of the new minimal resistance. They may depend on other cycle
fragments, though, but those other fragments are already solved.
Therefore, all cycle fragments of the new minimal resistance become
solved, during either the overall ~second or ~third trip.
Each trip therefore solves all cycle fragments of a new minimal
resistance. That set includes at least one cycle fragment.
BOX: Why do we solve at least one cycle fragment per non-
BOX: first trip?
BOX:
BOX: Why in practice is the number of trips required
BOX: much less than the number of cycle fragments?
BOX:
BOX: If an arbitrarily large semantic structure contains
BOX: blocks having at most K different resistances, how
BOX: many trips might be required, worst case?