Re: Translator design decisions

Chris F Clark <>
Wed, 23 Jan 2008 00:10:25 -0500

          From comp.compilers

Related articles
Translator design decisions (Mario Suvajac) (2008-01-19)
Re: Translator design decisions (Hans-Peter Diettrich) (2008-01-20)
Re: Translator design decisions (Chris F Clark) (2008-01-21)
Re: Translator design decisions (Tony Finch) (2008-01-22)
Re: Translator design decisions (Ken Rose) (2008-01-22)
Re: Translator design decisions (Chris F Clark) (2008-01-23)
Re: Translator design decisions (=?ISO-8859-1?Q?Pertti_Kellom=E4ki?=) (2008-01-23)
Re: Translator design decisions (Hans-Peter Diettrich) (2008-01-23)
Re: Translator design decisions (2008-01-26)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Wed, 23 Jan 2008 00:10:25 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 08-01-050 08-01-054 08-01-062 08-01-063
Keywords: UNCOL
Posted-Date: 23 Jan 2008 00:18:32 EST

The UNCOL problem is actually quite simple. It's not the foundations
are insecute, but our ability to build subtly different structures on
top of the foundation so easily that is the cause. A perfect example
is printing. Find two languages that have exactly the same printing
operations with the same semantics. We can't even get operating
systems to agree on how to terminate lines in text files.

And therein lies the rub. All those seemingly trivial differences can
easily be represented in an assembly language program, but determining
which of those differences is relevant to any given program requires
solving something equivalent to the halting problem. So, as one
builds an UNCOL, one has to capture all the differences down to the
most minute level.

        As an aside, there are two ways to attempt that: either the union
        or intersection approach. In the union approach one keeps adding
        new operators for each new conceptual combination, and the number
        of operators grows without bound due to the combinatorial
        explosion of choices that can be combine. In the intersection
        approach, one keeps attempting to find a finer grain of atomic
        principles out of which everything can be constructed, and one
        fails due to the unbounded combinations reducing the intersections
        to essential infinitesimals.

In any case, when one attempts to build an UNCOL, one ends up building
a massive bloatware structure, where there are hundreds of unused
combinations that have to be represented, analyzed, and dealt with.
None of these combinations are used in any one language, but they are
the cross-products of features from different languages that have to
exist in a unified solution, because if the cross-product doesn't
work, then at some point a language will be added to the set that will
depend upon that cross-product and it won't work.

This is not the problem in the single language case, because one
simply never considers the combinations that can never occur. One may
not even be aware that some of the combinations exist, because they
are impossible due to some other characteristic of the language. This
is wonderful and allows us to deal with simple things simply. When
one starts buiding an UNCOL, one slowly expands that set, slowly
making things more and more complex as new interactions that were
previously impossible become evident. When you've added enough
combinations, one simply cannot understand all the potential
interactions and things become unmaintainable, because when fixing one
thing, one somehow forgets some other cross-product that needs a
slightly different interpretation and one then breaks that.

It's like the diagonalization argument for proving one set is larger
than another. There exsits some language that you will need to
represent in your UNCOL whose semantics at each point is distinct from
each language previously enumerated in your UNCOL. Thus, there is the
UNCOL writers' full-employment theorem.

Hope this helps,

Chris Clark Internet:
Compiler Resources, Inc. or:
23 Bailey Rd Web Site:
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.