Two for the road
Lynn H. Maxson
lmaxson@pacbell.net
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
source.
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
executable.
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.