CHAPTER 24


		    TRANSLATIONS THRU MORE THAN ONE LANGUAGE



	  This chapter introduces a way to require that a specification
	  make sense in ~more ~than ~one ~domain, or language, simultaneously.
	  For example, one might like a new building to make sense both
	  ~structurally and ~financially.  Our primary example involves two
	  domains: the familiar syntax domain and the domain of datatypes.

	  Making sense simultaneously in two or more domains allows any
	  constraints or capabilities to be expressed in the one domain in which
	  its expression is the clearest.  For example, we will implement
	  type checking and type inferencing in our second domain.

	  A multiplicity of domains allows the ~factoring of concerns into
	  separate domains.  In contrast, forcing everything into one domain can
	  cause that domain's complexity to grow multiplicatively.


24.1
Ambiguity Between Domains

	Two domains most often don't fit ~exactly together.  Of all the
	  possible partial fittings, often one will support the entire
	  informational load.  To handle multiple fittings, we maintain many
	  possible interpretations in the domains.

	  The chance of a fitting is greatly enhanced by representing many
	  interpretations, the possibility that one interpretation in one domain
	  will make sense with another interpretation in the other domain.
	  Supporting rich ambiguity (many interpretations) ~between domains
	  multiplies enormously the chances of a meaningful connection.  This
	  makes for much more frequent successful communication.

	  The phrase generation notations presented in the next chapter lets you,
	  the programmer, specify translations ~oblivious ~to ~the ~existence ~of
	  ~any ~ambiguity ~at ~all.  Ambiguity is supported implicitly, and
	  delightfully, it's relatively easy to implement.


24.2
Our Example Compiler

	We saw in Chapter 8 a grammar for a small programming language.
	That grammar consisted of individual rules of grammar, whose semantics
	together generated a machine language program.  In that language, all
	data were of one type, the type INTeger.  That language would compile
	any ~syntactically legal program.  No other constraints were imposed.

	For richer languages, more than correct syntax is required of a program
	specification.  In PASCAL, ADA, and ICL, for example, the program must
	also make sense in the domain of datatypes.  Distinct types like INT
	and REAL must not be confused in the program.  In general, a given
	language may require that sense be made in ~many ~independent ~domains
	beyond that of syntax.

	(The ~strict ~nature of typed languages is eased remarkably in ICL
	by the use of coercion and polymorphism).


24.3
Expressing The Capabilities Of A Domain

	A powerful way to express the constraints and capabilities of a domain
	is by a set of rules.  Like with syntax, each rule expresses a
	capability.  An input passes successfully thru a domain by finding a
	way to apply the domain's rules so as to understand the input.

	  Recall that passage thru the syntax domain requires there be a
	  sequence of syntax rule applications (rewrites) that reduce the input
	  to a full-spanning occurence of the syntax grammar's ~root part-of-
	speech.  Similarly, in non-syntax domains, like the datatype domain,
	an input must be reducible, by datatype rule applications, to a full-
	spanning occurence of a root part-of-speech.  Only if a program passes
	successfully thru ~both syntax and datatypes, is the program considered
	legal.

	We will arrange for an input to pass thru both the syntax and datatype
	domains via two steps.  First, the input will be parsed by the syntax
	grammar.  The semantics of the syntax grammar will no longer generate
	machine language code.  They will generate instead ~phrases ~in
	~another ~language.

	Those generated phrases will be parsed by the ~datatype
	~grammar as they are generated.  When this second step, the datatype
	parsing, is done, the semantics of the datatype grammar are invoked.
	It will now be the semantics of the datatype grammar that generate
	machine language code.


		BOX:	When translating thru more than one language, what
		BOX:	does the semantics of the first phase (syntax) do?


24.4
The Datatype Grammar, With Its Own Syntax

	To emphasize the independence of the syntax and datatype grammars,
	we will choose for the datatype grammar a very simple syntax, called
	~reverse ~Polish.  In reverse polish, an operator always ~follows its
	operands.

	Where we might be tempted to write a datatype rule as:

		~REAL  +  ~REAL		->	~REAL

	let's write this rule instead in reverse polish:

		    ~REAL  ~REAL	+	    ->	~REAL


	  By our convention that the semantics of the syntax grammar generate
	  phrases in the datatype language, it is natural that the ~syntax rule:

		    EXPR  BOP  EXPR	    ->	EXPR

	  will generate the reverse polish datatype phrase:

		    ~TYPE_OF_EXPR(1)  ~TYPE_OF_EXPR(2)  ~the_BOP

	  This reverse polish phrase will be understood by the datatype grammar.
	  A more specific example will come shortly.
	---------------- Parentheses in previous paragraph mean subscripting! ---

	  Coercion rules in the datatype grammar, like:

		    ~INT		  ->	    ~REAL

	  are not affected by our reverse polish convention.	They remain
	  unchanged.


24.4.1
Example

	  A given input:

		    1 + 2.5

	  will be seen by the EXPR-BOP-EXPR syntax rule.  This rule generates the
	  reverse polish phrase:

		    ~INT  ~REAL  +

	  since "1" is an INT and "2.5" is a REAL.  Now, given only the datatype
	  rules:

		    ~REAL  ~REAL	+	    ->	~REAL
	  and
		    ~INT			    ->	~REAL

	  we can see how our generated phrase will be parsed.	 The phrase:

		    ~INT  ~REAL  +

	  is first affected by the rule:

		    ~INT		  ->	    ~REAL

	  so as to become:

		    ~REAL  ~REAL	+

	  This is finally rewritten to:

		    ~REAL

	  by the first of our datatype rules.

	  The given input "1+2.5" has now made sense syntactically and in the
	  domain of types.  The given EXPR is of type REAL.

	  Where the syntax grammar uses the part-of-speech EXPR, the datatype
	  grammar uses datatypes as its parts-of-speech, like INT and REAL.

	  The complete specification of syntax rules that generate phrases
	  in the datatype language will appear in Chapter 26.


		    BOX:	What are the parts-of-speech of the datatype grammar?
		    BOX:
		    BOX:	What is the syntax of the datatype grammar?


24.4.2
Some Possibly Built-in Datatype Rules

	  We would expect that at least the following rules are already built-in
	  to the datatype grammar:

		    ~INT  ~INT  +		    ->	~INT
		    ~REAL ~REAL +		    ->	~REAL
		    ~POINT ~POINT +	    ->	~POINT

		    ~INT  ~INT  *		    ->	~INT
		    ~REAL ~REAL *		    ->	~REAL

	  They show that "+" operates on INTs, REALs, and POINTs, etc.


24.5
Declarations Augment The Datatype Grammar

	  Often, the essence of a declaration is the new datatype rules it
	  contributes.

	  For example, consider the function declaration:

		    DEFINE	F( A(1):TYPE(1)  A(2):TYPE(2)	 ...
								A(n):TYPE(n) )  =	 TYPE(0):.

				...
		    ENDDEFN

	  The processing of this declaration contributes the (reverse polish)
	  rule:

		    ~TYPE(1)  ~TYPE(2)	...  ~TYPE(n)  f	  ->	    ~TYPE(0)

	  This rule will be used when somebody calls the function F.

	---------------- Parentheses in previous paragraph around "0", "1"
	----------------	"2", and "n" mean subscripting! -----------------------

	  For example, a function call is seen by the function call syntax rule:

		    ID ( EXPR , EXPR , ... , EXPR )		  ->	    EXPR

	  Its semantics generate the reverse polish phrase:

		~TYPE_OF_EXPR(1)	~TYPE_OF_EXPR(2)	...  ~TYPE_OF_EXPR(n)  the_id

	---------------- Parentheses in previous paragraph around "1"
	----------------	"2", and "n" mean subscripting! -----------------------

	  For a specific example, the function declaration:

		    DEFINE	MIX( A:INT	B:REAL  C:REAL ) = REAL:    ...	ENDDEFN

	  introduces the datatype rule:

		    ~INT  ~REAL  ~REAL	mix		->	  ~REAL

	  Upon the function call:

		    MIX( 1, 2.5, 3 )

	  the function call syntax rule generates the phrase:

		    ~INT  ~REAL  ~INT  mix

	  After applying the coercion rule:

		    ~INT	->	  ~REAL

	  upon the third operand (an INT), we get the phrase:

		    ~INT  ~REAL  ~REAL	mix

	  The datatype rule contributed by the declaration of MIX rewrites this
	  entire phrase to the type REAL.  Now the expression

		    MIX( 1, 2.5, 3 )

	  has made sense both syntactically (it is an EXPR) and in the datatype
	  domain (it is a REAL).


24.5.1
Type Declarations Also Augment The Datatype Grammar

	  The declaration of a type may contribute rules as well.  For example,
	  the declaration:

		    TYPE	LIST =  { ELEMENT }  ;

	  contributes the following datatype rule for indexing into lists:

		    ~LIST  ~INT  index			->	  ~ELEMENT

	  Given a list and an INT, the ~index operator turns them into the
	  ELEMENT type.  In terms of our more familiar syntax, this rule would
	  look like:

		    ~LIST  [  ~INT  ]			->	  ~ELEMENT

	  The previous, reverse polish rule however is the official datatype
	  rule.

	  This declaration of LIST also introduces rules to capture the ~list
	  ~synthesis notation:

		    { EXPR ; EXPR ; ... ; EXPR }

	  The new datatype rules contributed are:

		    ~ELEMENT  start_list		->	  ~LIST

		    ~LIST  ~ELEMENT  continue_list	->	  ~LIST

	  The syntax rule:

		    { EXPR ; EXPR ; ... ; EXPR }		  ->	    EXPR

	  generates the datatype phrase:

		    TYPE_OF_EXPR(1)  start_list   TYPE_OF_EXPR(2)  continue_list
							    TYPE_OF_EXPR(3)  continue_list
							    ...
							    TYPE_OF_EXPR(n)  continue_list

	  If the TYPE_OF_EXPR(k) is always ELEMENT, then the phrase looks like:

		    ~ELEMENT  start_list    ~ELEMENT  continue_list
						    ~ELEMENT  continue_list
						    ...
						    ~ELEMENT  continue_list

	  The "~ELEMENT start_list" rewrites to ~LIST, and so we have:

		    ~LIST	~ELEMENT  continue_list
				~ELEMENT  continue_list
				...
				~ELEMENT  continue_list

	  The first line rewrites in its entirety to ~LIST, and that same rule
	  applies repeatedly, rendering the whole phrase as type ~LIST.

	---------------- Parentheses in previous paragraph mean subscripting! ---

	  Thus, a list all of whose elements can be seen as the type ~ELEMENT,
	  forms a new instance of the type ~LIST.	 This capability for reduction
	  resides in the datatype grammar.


24.5.2
Type Declarations May Also Introduce Coercion Rules

	  You may recall from Chapter 23 that some of our type constructors
	  introduce coercions into the datatype grammar.  The following:

		    TYPE	D = DISK C ;

	  introduces the coercion:

		    ~D	->	  ~C

	  so that a disk-resident object (D) can be treated as though it were
	  always core-resident (C).

	  Also, the variant constructor, as in:

		    TYPE	FRUIT	 =  EITHER
						    ONE = APPLE
						    TWO = ORANGE
					    ENDOR ;

	  introduces two coercions:

		    ~APPLE		  ->	    ~FRUIT
		    ~ORANGE		  ->	    ~FRUIT


	    BOX:  BOX:	How does a function declaration augment the datatype
		    BOX:	grammar?
		    BOX:
		    BOX:	What rules of grammar are contributed by the list type-
		    BOX:	constructor?
		    BOX:
		    BOX:	What type-constructors introduce coercion rules into
		    BOX:	the grammar?


24.6
Epilog

	  We explore in the next chapter convenient notations by which to
	  generate phrases in another language.  Our syntax grammar will use
	  these notations in its semantics, to generate phrases in the datatype
	  language.	 One language translates to the next by generating phrases
	  in that next language.

	  We will see how ambiguities in one language propogate to the next
	  language and intermix with ambiguities within that second language.
	  Finally, Chapter 28 shows how to disambiguate sensibly among all the
	  ambiguities.