This chapter brings semantics into the parsing process.  In conjunction
	  with the change that assured termination (previous chapter), something
	  new must arise, ~ambiguous ~semantics.	They provide for the
	  representation of exponentially many meanings in only a polynomial
	  amount of memory.

Introducing The SEM Field

	  Our discussion of the parser to this point has ignored semantics
	  entirely.	 We incorporate semantics by augmenting the type PHRASE
	  so as to have a new, SEM (semantics) field:

						POS:	INT

	  As discussed in chapter 4, we always render semantics in terms of the
	  type BASIC_PROCESS.  Even though we write the rule:

		    <FORM:a>  +  <TERM:b>	  ->	     <FORM:	 <*a*> + <*b*>  >

	  we actually get:

		    <FORM:a>  +  <TERM:b>	  ->

						 <FORM:  //[a;b;]	 <*a*> + <*b*>  \\ >

	  All semantic data are constructed by the //...\\, even though you are
	  freed from having to specify this.

	  Let's see how to turn this rule into a program, including
	semantics.  The want-phrase is unchanged, i.e., this rule is programmed

		P1:= P;

			FOR P2 $E P1.LEFT;  WITH  P2.POS = '+' ;
			FOR P3 $E P2.LEFT;  WITH  P3.POS = <FORM> ;

	The give-phrase, the "??", is specified by using GIVE, as follows:


			SEM:  //[P1;P3;]  <*P1.SEM*> + <*P3.SEM*>  \\   ]  );

	The parameter to GIVE is of type PHRASE, as always.  What's new here is
	  the inclusion of the SEM field in the PHRASE.	 The SEM field, the

		    //[P1;P3;] ... \\

	  is a process which retains access to P1 and P3, so that it can perform
	  the necessary semantics by using P1 and P3, as in:

		    <*P1.SEM*>  +	 <*P3.SEM*>

	  The invocation of our semantics thus will execute this sum, where the
	  two integers are acquired by invoking the semantics of P1 and of P3.

	  In fact, we actually translate:

		    <FORM:a>  +  <TERM:b>	 ->	   <FORM: ... >


		    P1:= P;
		    IF  P1.POS = <TERM>	 THEN

				FOR P2 $E P1.LEFT;  WITH  P2.POS = '+';
				FOR P3 $E P2.LEFT;  WITH  P3.POS = <FORM>;
					  ~A:= ~P3.SEM;	"New"
					  ~B:= ~P1.SEM;	"New"

					  GIVE(  [LEFT: P3.LEFT	 POS: <FORM>

						    SEM:  ~//[A;B;]  ...   ~\\  ]  );

	  Notice that the variables mentioned in the rule, A and B, hold the SEM
	  fields of the matched want-phrase.

	  Thus, the user's semantic specification can continue to use the
	variables A and B, the ones the user specified in the rule's want-

		    Recall that the execution of

				//[A;B;]  ...  \\


		    is very fast. It makes merely a new block that holds the
		    contents of A and B, and a pointer to the "..." program (figure
		    15.1). That "..." program is ~not executed now. (This was
		    introduced in Chapter 2).

	  In general, we translate:

		    <POS(1):V(1)>	 ...	<POS(n):V(n)>	  ->

				<GIVE_POS: semantic_program >


		    P(n):= P;
		    IF  P(n).POS = <POS(n)>  THEN

				FOR P(n-1) $E P(n).LEFT;  WITH P(n-1).POS = <pos(n-1)>;
				FOR P(1) $E P(2).LEFT;	WITH	P(1).POS = <pos(1)> ;
					  V(1):= P(1).SEM;
					  V(2):= P(2).SEM;
					  V(n):= P(n).SEM;

					  GIVE(  [LEFT: P(1).LEFT  POS: <GIVE_POS>

						    SEM:  //[V(1);...;V(n);]

								   Semantic_Program	\\
						   ]	);


	  Figure 15.2 shows the PHRASE block we're passing to GIVE.  Its SEM
	field is itself a block.  That semantic block's first bin points to the
	  already compiled semantic_program.  The remaining bins hold the values
	  of variables, V(1)...V(n), which will come alive with those values upon
	  invocation of this SEM block.
	---------------- Parentheses in previous paragraph except after "GIVE"
	----------------	mean subscripting! ------------------------------------

	  (The program block "Semantic_Program" is not recreated now.  It has
	  existed since we first gave our grammar to the computer).


	  Figure 15.3a shows an occurence of the following rule's want-phrase:

		<FORM:a>  +  <TERM:b>	    ->	     <FORM:  <*a*> + <*b*>  >

	Each of the <FORM> and <TERM>'s semantic blocks are shown, although
	  we don't show their insides, the variables nor the pointers to some
	program blocks.

	Figure 15.3(b) shows the situation after this rule applies.  The new
	<FORM> PHRASE block (on the bottom) shares the same span with the
	want-phrase.  Its SEM field is an BASIC_PROCESS, a block containing
	the address of a program and the values in variables.  That block is
	the second to rightmost block in the figure, labelled "SEMANTICS".
	Notice that those values in A and B are the semantics taken from the
	want-phrase's <FORM> and <TERM> blocks respectively.	The semantic
	  program is:

		    <*A*> + <*B*>

	  It means invoke each of A and B so as to acquire their INTeger values,
	  and deliver their sum.

		    BOX:	How are semantics included in our parser?
		    BOX:	How is it that the semantic specification can continue
		    BOX:	to use the variables specified in the want-phrase?
		    BOX:	Where does the implicit "//...\\" get introduced.

General Rewrite Rules

	  Each element in the give-phrase of a ~general ~rewrite ~rule
	  (introduced in Section 1.3) specifies its own semantics, e.g.,

		    <A:a>  <B:b>	     ->	 <X:...>  <Y:...>	 <Z:...>

	  Each of X, Y, and Z gets its own semantics.  As we GIVE each of X, Y,
	  and Z, we now supply a value for the SEM field each time, in the PHRASE
	  block that is passed to GIVE.

	  There is no notion of semantics associated with the rule as a whole.
	  Each GIVEn PHRASE block has its own independent semantics.  Those
	  semantics can read the variables "a" and "b".

Ambiguous Semantics Arise When Duplicate PHRASE Blocks Are Supressed

	  Recall that GIVE is now defined by:


				IF  FOR P1 $E C;	NEVER	 (P.POS=P1.POS) &

				THEN	  C:= C $> P;


	  That is, we put P on C and call the grammar with P ~as ~long ~as ~P
	  ~isn't ~a ~duplicate of something already in C.  If P is a duplicate,
	then we have so far ignored P entirely, including its semantics.

	We chose to supress duplicate PHRASE blocks because they added
	nothing new.  They only created duplicates of existing
	phrases.  We argued that all the new phrases caused by a duplicate
	PHRASE block would be duplicates of those generated by the original.

	We defined "duplicate" to mean "matching in both POS and LEFT".
	Now that we've introduced semantics, "duplicate" no longer means
	  "identical".  "Duplicates" can have different semantics.	However,
	  GIVE and the grammar ~never read semantics (until the last rule
	  applies).	 Thus, GIVE's and the grammar's execution still depend in no
	  way upon semantics.

	  Suppose we didn't supress duplicates at all.  Upon GIVing the original,
	many new phrases resulted.  The semantics in those phrases were also
	built up.  If we let GIVE call the grammar upon receiving the 
	duplicate, the grammar will build exact duplicates of the phrases and
	semantics grown by the original.


	Figure 15.4(a) shows the semantics delivered with the original PHRASE
	block (OLD).  We show arrows coming from above, representing other
	semantics built up in terms of the original PHRASE block's semantics.
	  Figure 15.4(b) shows the semantics of the duplicate PHRASE block (NEW).
	  The same arrows above the original semantics appears over this new
	  semantic block.	 After all, GIVE behaves identically the first and
	  second times around.	The same semantic structure built over NEW
	  was built over OLD upon receipt of the original.

	  Let's call all points-of-view that can see OLD "View(OLD)".  All
	the structure above NEW is identical to that above OLD.  That is, by
	letting the duplicate PHRASE block pass thru GIVE, we gain two

		View(OLD) and View(NEW)

	Any point of view in View(OLD) has a corresponding point of view in
	View(NEW).  (The "view" structures are identical).

	As long as one point of view in View(OLD) can participate in an
	overall understanding of the user's input, then so will the
	  corresponding point-of-view in View(NEW).  ~Both will be part of the
	  understanding, or neither will.


	  Figure 15.5(a) shows View(OLD) and View(NEW).	 Part (b) shows how we
	  can represent that exact same ambiguity, by burying the ambiguity
	  under one view.

	  We represent both View(OLD) and View(NEW) in only one structure by

		    View( OLD ~or NEW )

	  That is, you can use the structure View(OLD) to act also as the
	  structure View(NEW).	You put both OLD and NEW under the same (old)
	  structure.  The "OLD ~or NEW" is an instance of ambiguous semantics.

	  The block that ties NEW and OLD together is called the ~OR-block, as
	  it represents the choice of NEW ~or OLD.

		    BOX:	What causes ambiguous semantics?
		    BOX:	Why does GIVE behave identically when given a PHRASE
		    BOX:	block and later when given a duplicate of it?

Turning View(OLD) Into View( OLD ~or NEW )

	  We represent OLD ~or NEW like any other semantics.	It is the

		    //[OLD;NEW;]	f( OLD , NEW )   \\

	  The BASIC_PROCESS's invocation will perform

		f( OLD , NEW ).

	F may invoke OLD or invoke NEW.  We leave that unspecified for now.
	If f invokes OLD, then we have represented View(OLD).  If f invokes
	NEW, then we have represented View(NEW).  (Part 7, Section 25.5.4 and
	Chapter 28 reconsider F).

	We modify the OLD semantic block ~in ~place so as to represent now
	"OLD ~or NEW".  We proceed in three steps.  First, we copy the OLD
	semantic block, and call it COPY_OLD:


	Figure 15.4(c) shows COPY_OLD as well as View(OLD), OLD, and NEW.
	We set OR to be the new OR block:

		OR:= //[NEW;COPY_OLD;]  f(NEW,COPY_OLD)   \\ ;

	This is shown in figure 15.4(d) with thick lines.  We leave unspecified
	the function "f" called within OR.  It may choose to invoke NEW or

	Finally, we write over the OLD block:

		@(OLD) := OR ;

	Figure 15.4(e) shows the result.  All points of view that could see OLD
	now see (at the same address) the OR block.  This is an objective
	modification.  Thus, what was OLD has become NEW ~or OLD.  View(OLD)
	now acts as View(NEW ~or OLD).

	These semantics concerns are implemented in our final definition for



			IF  FOR P1 $E C;  NEVER  (P.POS = P1.POS)  &
						 (P.LEFT=P1.LEFT) ;

			THEN	"No duplicate found."

				C:= C $> P ;


			ELSE	"This ELSE clause is what's new ..."

					  "P is the duplicate of P1.	(That FOR-loop
					   above leaves in P1 the (first) PHRASE block
					   that matches P)"

					  "The OLD and NEW semantic blocks..."

					  OLD:= P1.SEM;
					  NEW:= P.SEM;

					  "Prepare to modify OLD objectively..."

					  COPY_OLD:= COPY( OLD );

					  OR:= //[NEW;COPY_OLD;]  f(NEW,COPY_OLD)	 \\ ;

					  @(OLD) := OR;

	  You may wonder why we bothered to make a COPY of the OLD block, why we
	  put it into COPY_OLD, and why the OR block references COPY_OLD instead
	  of OLD.  Figure 15.4(f) shows the situation if we didn't copy OLD.  Upon
	  executing the objective modification:

		    @(OLD) := OR ;

	  the OR block's third bin, which is intended to represent the old
	  semantics, references now the OR block itself.  The old semantics used
	  to reside there, but those data have been lost.  Our use of COPY_OLD
	  preserves the old semantics, albeit at a different address.

		    BOX:	How does GIVE retain the semantics of both the
		    BOX:	original and duplicate block?
		    BOX:	What might the function "f" do?  (Part 7 introduces
		    BOX:	more examples, in particular Sections 25.5.4 and
		    BOX:	28.1).
		    BOX:	Why must OLD be copied?

	What If The OLD and OR Blocks Are Of Different Sizes?

	  You might wonder how this can work, particularly if the OLD, NEW,
	  and OR blocks are of different sizes.  Figure 15.4 shows them all being
	  three bins large.  In fact the sizes may differ.  It has been clearest
	  to show semantic blocks (of type BASIC_PROCESS) as single blocks (of
	  varying sizes).


	  However, the implementation actually represents
	  BASIC_PROCESSs as a linked list of fixed size blocks, as shown in
	  figure 15.6(b).	 We use always blocks of size two.	These blocks are
	  linked so that one points to the next, and the last one points to the
	  program.	Figure 15.6(c) shows OLD, NEW, and COPY_OLD as they are
	  really represented.  Part(d) shows the OR BASIC_PROCESS, referencing
	  COPY_OLD and NEW.  Part (e) shows the situation after executing the
	  objective modification:

		    @(OLD) := OR ;

	  Only the first block need be overwritten, as that is sufficient to make
	  the point of view OLD now represent the OR BASIC_PROCESS.
Examples Of Ambiguous Semantics

Example 1

	  The ICL expression

		    A + B # C

	  is syntactically ambiguous, as it represents both possible groupings:

		    (A+B) # C   and
		    A + (B#C)

	  (We haven't seen the grammar rules involving "#", which allow for this


	  Figure 15.7 shows the semantic structure built up for A+B#C.  The top
	  block is the OR block.  It represents the semantics of
	  (A+B)#C ~or A+(B#C).

		    These semantic pictures omit the program blocks.	Instead of a
		    pointer to a program block, we have written just "(+)" or
		    "(#)", to represent the semantic programs associated with the
		    "+" rule and the "#" rule.

	  Notice in figure 15.7 how the semantic block (A+B)#C references the
	  semantic block (A+B) and the semantic block for C.	Similarly, the
	  slanted A+(B#C) block references the A and the (B#C) blocks.  Also
	  note that both overall interpretations share the A, B, and C blocks.

Example 2

	  Let's consider a more complex example of ambiguous semantics.  For
	  this purpose, let's assume that even the "+" operator alone is also
	  ambiguous, so that:

		    1+2+3	  could be either		(1+2)+3  or	 1+(2+3)
		    1+2+3+4	  could be either of	((1+2)+3)+4	 or
								(1+(2+3))+4	 or
								(1+2)+(3+4)	 or
								1+((2+3)+4)	 or

	  (This ambiguity can be obtained by replacing the rule:

				<FORM>  +  <TERM>		->	  <FORM>


				<FORM>  +  <FORM>		->	  <FORM>

		    We introduce this ambiguity only for the purposes of this
		    example.  However, ICL does indeed have a class of operators
		    that introduces this kind of ambiguity, the ~infix notation
		    for calling functions:

				paramter_1	\Function_name  parameter_2

		    The grouping of:

				value1  \Function1  value2  \Function2  value3

		    is ambiguous, just like the example with the "+" and "#".  Do
		    we call Function1 first, or Function2?)

	  Consider two of the five possibilities for 1+2+3+4:

		    ((1+2)+3) + 4	 and
		    (1+(2+3)) + 4


	  The distinction between these two interpretations occurs within the
	  1+2+3 part, independent of the 4 part.	Figure 15.8 shows the semantics
	  for these two interpretations.  The distinction between the
	  two interpretations for 1+2+3 is ~buried within the semantics for
	  (1+2+3)+4.  That is, the "?" in "?+4" is ambiguous.

	  We have not shown the semantics for 1+(2+3+4) nor (1+2)+(3+4).	The
	  former, the:

		    1 + (2+3+4)

	  represents actually two interpretations, as did our old (1+2+3)+4:

		    1 + ((2+3)+4)
		    1 + (2+(3+4))

	  Again, the ambiguity in this case involves only the 2+3+4, independent
	  of the 1.

Example 3

	  Consider an even more complex example:


	  We will limit our attention to only those interpretations that group
	  the 1+2+3 together:

		    (1+2+3) + (4 + 5)	 or
		   ((1+2+3) + 4) + 5

	  Both these interpretations ~share the same representation for the
	  (1+2+3).	Here we have an ambiguity ~within an ambiguity.	 The two
	  lines just shown form the outer ambiguity.  Within each of those two
	  interpretations, the 1+2+3 part represents the inner ambiguity,
	  representing both:

		    (1+2)+3	  and


	  Figure 15.9 illustrates this nested ambiguity.  There is an OR block in
	  the center of the figure, which represents both interpretations for
	  1+2+3.  That OR block is referenced from above, twice, once within the:

		    ( (1+2+3) + 4 ) + 5

	  and once within the

			(1+2+3) + (4+5).

Exponentially Many Meanings In Only Polynomial Space


	  Figure 15.10 is an abstraction of figure 15.9, showing only the OR
	  blocks.  The essential ingredient is that both interpretations
	  represented by the upper OR block come to share the other OR block
	  below.  Figure 15.10(b) shows a similar nesting, this time involving
	  three OR blocks.

	  This nesting of ambiguities within ambiguities gives rise to
	  exponentially many distinct meanings represented in only polynomial
	  memory.  Each OR block represents a two-way choice.
	  If there are N OR blocks nested like this, then there are 2-to-th-Nth
	  possible overall choices.

	  Our parser represents at least exponentially many phrases in only
	  polynomial memory.  We see the same thing here with semantics.	Both
	  exponentials are possible because of sharing.	 Distinct meanings
	  share much in common.	 Only the essential differences among
	  meanings are represented, thus giving us this wonderful savings.

	  Since our parser consumes only polynomial execution time, the amount of
	  memory used to represent all phrases and all semantics is also bounded
	  above by the polynomial.  Within that polynomial memory, we know that
	  at least exponentially many distinct phrases and meanings must be
	  represented, as there is at least exponentially many ways to introduce
	  parentheses around the expression of lenght N:

		    1+2+ ... +N

	  Our examples for 1+2+3+4 and 1+2+3+4+5 showed only some of the
	  possible interpretations.  There are many more, and they are also
	  represented with a great deal of sharing.  For example, the two

		    (1+(2+3))+4	and

	  share in common the (2+3).

	  How do we handle ultimately such voluminous semantics?  If
	  exponentially many meanings are indeed represented, won't it take an
	  exponential amount of time to process all of them?	Certainly if we
	  enumerate all the possible meanings, exponential time will be consumed.
	  However, many kinds of very useful processing can be done in only
	  polynomial time!  Part 7 continues with these considerations.

		    BOX:	How can exponentially many meanings be represented
		    BOX:	in only polynomial space?
		    BOX:	Why are there at least exponentially many possible ways
		    BOX:	to place parentheses within a string like "1+2+...+N"?