Two for the road

Lynn H. Maxson
Tue, 27 Jun 2000 09:17:54 -0700 (PDT)

To support the proposal that the Tunes HLL be a 
specification language based on logic programming I 
would like to offer two examples of the "complete 
rethinking" possible in software.  The first deals 
with optimization, achieving performance equal to 
or better than the best assembly language program.  
The second deals with "universal" migration of 
executables from any other language into Tunes 

One concept which permeates all of formal logic is 
"logical equivalence", the fact that two different 
expressions can produce the same result.  We rely 
on this, for example, in any decomposition process 
of "reducing" a higher level abstraction to lower 
level forms.

In logic programming this decomposition process is 
subject to a two-stage proof process: (1) 
completeness in that we have enough information to 
proceed, and (2) exhaustive true/false testing.  
The net result of the exhaustive true/false test is 
either 0, 1, or more true instances.  If 0, then we 
do not have a decomposable instance.  Otherwise we 
have 1 or more logically equivalent decomposed 
instances.  Just as in any SQL query we have "all" 
the possible instances.

Compilers and interpreters go to great pains to 
insure that one and only one decomposition (code 
generation) is possible.  The user then is "stuck" 
with the "limits" of the implementation (ultimately 
the implementer).  Given the capabilities of logic 
programming the point is "why?".  Why not generate 
all the possibilities (all the true logically 
equivalent instances).  Logically from the set of 
"productions" there exists at least one whose 
performance is equal to or better than any other.  
Whatever that "one" is is also at least equal to or 
better than any an implementer can produce.

If we truly believe in the principles of reflective 
programming and meta-programming, then we must 
specify the ability of a tool which produces an 
executable to incorporate "reflection" within it.  
Among other things that means "knowing" where the 
executable spends it time.  If, for example, we 
determine that some "high level function" 
representing an hierarchy of lower level functions 
needs "improvement", then we can "mark" (or 
otherwise specify) that this particular function 
instance (and all its included functional instances 
down to the machine code level) be executed 
"inline".  This provides a logically equivalent, 
though better optimized, execution within the 

Two things to note here.  

One, an executable is a production (generated code) 
not source.  No change to source is necessary to 
allow this form of optimization to occur.  Thus the 
modularity (the separateness) of the source 
remains, but its "boundaries" need no longer to be 
respected, i.e. embedded within the executable.

Two, the fact that the source remains "intact" but 
"blurred" within an executable, i.e. only one 
source with multiple "interpretations", is 
something not possible with an assembly language 
programmer.  To achieve the same he must have 
matching source for each executable.  He could do 
it, but historically he cannot afford the "time".

In such a manner the Tunes HLL through its 
implementation should allow the generation of 
executables whose performance cannot be exceeded by 
an other programming language (from symbolic 
assembly on up).  In short this has eliminated the 
last vestige of any excuse for less than optimal 
performance, e.g. 50% of C++.  Any offering whose 
implementation "accepts" less should be dropped 
from consideration.

Now to drop the second shoe.

If you follow the principle of logical equivalence 
in the decomposition process and accept the 
"standard" exhaustive true/false proof process of 
logic programming which results in 0, 1, or more 
logically equivalent forms (results), then accept 
that the same principle (logical equivalence) 
applies to a composition process, the constructing 
of higher abstraction levels from lower.

It's important to understand that the decomposition 
of the lowest level of machine-independent 
abstractions, that which contains the control 
structures (sequence, decision, iteration) and 
primitive operators, into machine-dependent 
abstractions (machine instructions) is complete: 
every possible translation from the higher to the 
lower exists (and is known).  This has significance 
when it comes to migration strategies.  It, in 
fact, reduces to a single (universal) strategy.  
Instead of writing separate "translators" for the 
source of other languages to the Tunes HLL, write 
one that translates the executables of those 
languages into Tunes HLL source.

I offer these two strategies, one on optimization 
and the other on migration, as examples of 
rethinking computing systems.  Again I make the 
admonition, if we are going to completely rething 
computing systems, I suggest that we do so.