Proposals

[Lynn H. Maxson]

Billy wrote:
" The problem is that if you pay attention only to 
the <operand><operand><operator> you're
working on now, you'll miss the fact that a 
previous <operand><operand><operator> used a 
subsequence that you could borrow economically if 
you rearranged the program a bit."

No, no, no.  What I tell you three times is 
true.<g>  We have already conceded that multiple 
levels of optimization occur including handling of 
this example.  That's what occurs today.  That's 
what will occur tomorrow.  I am not changing a 
thing.

Look IBM's VisualAge compilers regardless of source 
language (C, C++, JAVA, COBOL, PL/I) translate the 
source into a "common" intermediary symbolic 
(machine-independent) language which is then feed 
into an optimizing code generator for a target 
system.  The same language (source), multiple 
target systems.

In the system I propose you have a hierarchy of 
specifications.  Within that hierarchy the two 
lowest levels contain machine-dependent 
specifications (the machine architectures for RISC 
and CISC systems).  At the level immediately above 
these two, the third level, begins the remaining 
hierarchical levels of machine-independent 
specifications.  

This third level contains the raw material of all 
higher level assemblies.  This raw material 
consists of control structures (sequence, decision, 
iteration) and all the primitive operators.  Just 
as in any manufacturing system all the higher level 
assemblies must eventually decompose into a 
collecton of raw material.

There is no need to use the principal of logical 
equivalence with any of the machine-independent 
specifications (the third level on up) because any 
lower level is explicitly invoked by a higher, i.e. 
the organization of a set of machine-independent 
specifications is pre-determined, pre-set, and 
pre-known.  No search or discovery process is 
necessary.  None is invoked.

The only time it gets invoked, the only time 
logical equivalence comes into play, is making the 
transition from the third level, which is 
machine-independent, to an equivalent form in 
either of the machine architectures of the two 
lower (machine-dependent) levels.  This is code 
generation.

For any given machine architecture we can have a 
set of specifications governing the translation of 
the input stream of third level specifications.  We 
can do optimization iteratively as it is done 
routinely now.  All this is specifiable.

Take a look at LISP, at FORTH, and what you see is 
a decomposition of an expression using either 
prefix, infix, or postfix operator notation.  LISP 
uses prefix operator notation 
(<operator><operand><operand>) which can include 
sub-expressions (lists) in any of the three.  FORTH 
does the same thing only using postfix operator 
notation.

Whenever I have applied a set of global 
optimizations I still end up with a stream 
generically represented by this operator/operand 
triad.  This represents the "basic" executable 
expressions.  Given that I have complete knowledge 
of the attributes of each triad member and a set of 
rules governing every possible combination (I know 
this because we know and use it today), then I have 
no problem finding all the logically equivalent 
executable forms.  For any given triad they are a 
reasonably finite number, in many instances no more 
than one.  I have no problem using another set of 
rules to determine from a list of two or more one 
of which whose performance is not exceeded by any 
other.

Now I have a stream of now I have a stream of 
logically equivalent machine instructions against 
which I can now apply another set of specifications 
regarding their optimization in the machine 
architecture.  The point is that to do all of this 
I only need to use a specification language.  I can 
specify rules.  I can specify hardware.  In fact I 
can specify multiple target hardware systems as 
part of the same run, generating executable code 
for any number of different platforms.  No 
silly-willy, one-at-a-time code generations.<g>

If you don't like my specification language, use 
another logically equivalent one.  I'm not partial 
to it except as an example of a "universal" 
specification language.  As part of its 
universality is the ability to specify any other 
computer language.  If you use its multi-platform 
code generation capability, then you can offer your 
language on any of the other platforms, having only 
written (specified) it once.

Maybe "all possible logically equivalent programs" 
was misleading.  I don't have to generate it at the 
program level.  In fact such generation does not 
occur in practice.  The code generation always 
occurs at a lower level.  It's just that when it is 
done you have an executable program.<g>

"No, you can't precompute all possible encodings of 
all possible expressions."

No, no, no.  I don't precompute them any more than 
they are precomputed now.  I don't know how many 
different kinds of operators exist in your computer 
languages, but in mine they seem limited to 
boolean, logical, arithmetic, and string.  I'm very 
willing to show you a language-independent means of 
specifying all the possibilities and the rules 
governing their use.  I hate to use PL/I again, but 
it does offer more than any other programming 
language because it uses "practical" not "pure" 
strong typing.

Again you are thinking of a far greater problem 
than I am proposing.

"So I'm guessing that your talk about "exhaustive 
search" was talking about something else, then."

No, no, no.  I'm talking about the rule-based 
exhaustive search (true/false) proof method of 
logic programming.  That the same rules of logic 
can determine that certain paths need not be 
travelled does not change the results, only the 
time to produce them.  I have over and over (and 
over) again explained to you the finite exhaustive 
search that exists for any <oper><opnd><opnd> triad 
regardless of machine architectures or the number 
of them involved.  You have chosen to include 
enumerated logical equivalent forms that my rules 
would not allow.  You are free to do so.  My 
exhaustive search is limited to that permitted by 
the rules, which in turn are derived from 
heuristics.

"I'm not sure what an "iteration" is, but there's 
one thing I'm sure of: it has nothing to do with 
optimization."

Yes, yes, yes.  And no it doesn't.  Neither does an 
exhaustive search.  The optimization occurs after 
the search (or a search instance) is completed.

"I have a better suggestion, though: why not use 
the restrictions and heuristics the compiler 
researchers have been working on all these years to 
the problem?"

Well, well, well.  Here I thought that is what I 
was doing with my rule-based system, except that I 
want to take only the "best" of what they have 
produced.

"Perhaps this is the really important point I'm 
completely missing.  Even if it's not important, 
I'm completely missing it.  You keep bringing up 
the "rules in use in PL/I" as though they had 
anything to do with generating optimal code.  I 
don't understand that at all."

And it is well that you shouldn't as the PL/I rules 
deal with expression evaluation only.  You have to 
have something to optimize, in this instance an 
expression.  Before you can optimize it you must 
produce it.  Therein lies the purpose of the PL/I 
rules.

"I'm guessing you're talking about Baker's "The 
FORTH Shall be First" paper, which was an article 
in an ACM journal.  If so, you misread it."

While it would not be the first time I misread 
something, in this instance it was a different 
paper: Bawden's "Implementing Distributed Systems 
Using Linear Naming".  Having not yet gotten 
through all 156 pages, I will hold off any 
judgements on misreading.<g>

"One, it IS a restriction to permit the optimised 
code to contain only types which were present in 
the programmer's code."

I guess it depends on whose wishes the program is 
supposed to reflect.  You apparently have a problem 
with stupid or careless programmers.  I follow the 
general PL/I philosophy that the programmer is 
"king" and that what you do is the best job 
possible within his restrictions.  This may not 
result in "the" optimal solution, only in an 
optimized instance.  If you specify that the 
interactive tool make clear to the programmer the 
implications of his type choices, then the 
programmer can choose to remain or stay.  I don't 
think tools (or the authors of such tools) should 
be snickering or compensating for the programmer.  
The goal is to have better programmers.  You get 
that by incorporating such help in the tools, not 
in a hidden manner (somewhat arrogant in source) 
compensate for his (perceived) "failures".

"That's great, but this is another example where 
being restricted to the written types is a really 
bad idea.  The problem can be solved most 
economically without using any arithmetic at all -- 
the code "'7' emit" I listed is probably (short of 
some other vaguely possible code which didn't need 
to use a literal) the most efficient 
implementation."

We are confused on purposes here.  I want to 
increase the writer's productivity by offering him 
the utmost in assistance.  It is not my job to 
question his motives, but show him the implications 
of his writing.  If he chooses to remain with fixed 
decimal arithmetic instead of binary, I will honor 
that decision.  If he wants to know which in a 
particular instance performs better, I will honor 
that decision.  I, as a tool, am an assistant, not 
a dictator.

We are being buried in software maintenance, either 
changing something that exists or adding something 
new.  This expense in cost and time has continued 
to increase in spite of using "enhanced software 
methodologies", e.g. OO.  Obviously languages are 
not the solution nor are they the problem.  The 
problem (and its solution) lies in their 
implementation, in the tools.  If you had the 
"right" tool, the "right" kind of implementation, 
with any language capable of expressing the range 
of interest, software technology could maintain 
pace with hardware.

Our current tool set sucks.  I don't care how much 
better this tool set is better than that.  If 
neither allow software technology to maintain pace 
with hardware, it sucks.  It's just that simple.

You have to solve the problem.  Dealing with 
esoteric and exotic language features doesn't cut 
it.  Whether slots or sluts (a higher level slot) 
unless it addresses, unless it is part of the 
solution, it remains mired in the problem.  

LISP is one of the oldest programming languages.  
It has sprouted probably hundreds of dialects.  Yet 
no LISP or LISP-like development/maintenance 
environment functions to maintain the pace of 
software with hardware technology.  This is not an 
anti-LISP statement.  It is a statement of fact.  
It is a statement of fact about every other 
software language and methodlogy attempted.

Therefore the fault cannot lie with LISP or any 
other language.  It can only lie with their 
implementations which govern our use of them.  

While I cannot speak to the current state of 
affairs, initially LISP permeated all of AI 
systems, logic programming.  It was used to create 
the first Prolog compilers.  Why?  Because in an 
exhaustive true/false proof process may result in 
0, 1, or more true instances.  That my friend is a 
list, a native data type (an aggregate) in LISP.  
It permits rule-based operations on lists.

The fact is that this ability lies at the heart of 
logic programming.  It is intrinsic in any 
specification language like Prolog, Trilogy, or in 
my proposed SL/I.  Again the problem does not lie 
with the language used, but with its 
implementation.

I don't want to discuss philosophical differences 
regarding whether we follow the programmer's 
dictates or adopt a do-gooder attitude about 
knowing what's best for him.  You are entitled to 
have either in your implementation of choice.  My 
goal is to enable you to have that choice, not 
dictate to you what choices you have.

I want to bring down software costs (and time) to a 
minuscule fraction of their current burden.  In so 
doing provide for the first time in history the 
ability of software technology to outpace hardware.  
I want to solve a real problem that has continued 
to get worse over the last forty-plus years.  I 
cannot solve it with a language, but I must have 
one which allows me to express the solution.  I 
then need an implementation of the solution.  In my 
proposed methodology this is a single interactive 
tool I have dubbed "The Developer's Assistant".

If you in your infinite wisdom want to change it to 
"The Developer's Better Half", I want to enable you 
to do so.  I do not know what is best.  Therefore I 
prefer to enable, not impede others who might be on 
the right path.

Now a fourth generation, "universal" specification 
language includes all the capabilities of all other 
languages of all other generations.  That comes 
directly from logic and the fact that all computer 
systems and software are 100% logic based.  You may 
regard it as a restriction.  I won't argue it.  To 
me it is simply a fact that presents an opportunity 
to solve a problem besetting the entire IT 
profession.

"I'm confused.  I thought you just said that the 
optimiser would never change a type the user gave 
it (as when you claimed that the user had given 
decimal numbers); yet you admit that binary numbers 
would be faster.  This is a minor case, but there 
are many far worse ones: if the optimiser can't 
choose its own types and operations, how can you 
claim that the programmer is free???"

The confusion is that the programmer is free to 
behave stupidly and the optimizer is charged with 
doing the best it can with what he has done.  If 
you don't like that form of optimization, then 
change the rules.  I'm just giving you the rules I 
operate under.

I had many an account move from PL/I to COBOL 
because programmers did not use the tool, the 
compiler, intelligently.  Rather than improve the 
programmer the account made the decision to have 
another compiler dictate terms on his freedom.  Not 
my argument.  I use PL/I because out of the box I 
have never had to employ any other language to 
achieve a result.  It remains the most powerful 
programming language available today.

The reason you have an assistant as a tool, one who 
readily presents the results of any decision, is to 
improve "on" what you are doing and "at" your 
ability to do it.  If you have no curiosity, no 
desire to improve, it gives you the best with what 
you have provided.  However, it always stands at 
the "ready".

" The information you're ignoring is the fact that 
programs contain *internal* information, that is
information not visible, and that information is 
"an implementation detail"."

I'm sorry, but no way Jose.  Programs contain only 
written source.  I am proposing a tool in which 
nothing, absolutely nothing, is hidden "ever" from 
the writer.  It is a system of "perfect 
information", i.e. everything that can be known is.

"I'm running out of guesses.  If we agree that both 
satisfy the constraints, then why would you 
eliminate one of them?"

Both satisfy the constraints.  Only one passes the 
rules.  We can agree without the rules agree with 
us.<g>

"Because you explicitly said that there was only a 
couple of ways to express a "+", all of them having 
to do with addition.  Since there are actually an
infinite number of ways to do that, and only a 
"few" of them have to do with addition, it's quite 
obvious that you've done something akin to 
forgetting."

You have this fascination with binary arithmetic 
and using logical operators to perform arithmetic.  
I simply do not.  Whether or not they applied in a 
particular instance in which the operands are fully 
known, e.g. as literal values, would be determined 
by the rules.  If an XOR or OR provided the best 
choice, the rules would use it.  Thus I did not 
forget or ignore it.  To repeat there is not an 
infinite number of ways to process a triad.  I'm 
sorry.  Just not true.

" What does this have to do with the fact that "an 
instruction sequence which satisfies "0 3 + 4 1 * 
+" does also satisfies "3 4 +""?"

Look, what did the writer express?  That's what 
guides the rules for expression evaluation.  No 
attempt is made to produce all possible logically 
equivalent expressions the writer could have 
written.  The object is to do the best with what is 
given.  It may be that optimization produces a 
change, but the guidelines remain the same even for 
the optimized form.

The earlier point is that if "a" can only equal 
zero, i.e. a declare constant, then you can use one 
form of optimization.  If "a" can contain other 
values than zero, then optimization occurs for the 
general case, not the specific.  I'm sorry that's 
so confusing.

"They "limit" you from using a more efficient
representation, even when the more efficient 
representation is logically equivalent."

If you change what a writer has written, e.g. the 
data type, you have imposed a limit in turn.  You 
have made it impossible for a writer to impose his 
style in source.  I do not give a damn frankly 
about a more efficient representation unless 
circumstances demand it.  I do not want systems to 
place demands on or second-guess me.  I do not mind 
if I am notified that a better representation is 
possible.  That's the kind of help I expect from an 
assistant.  I do not mind if an assistant suggests 
a different representation, based upon my approval.

"You've just spent a long time telling me that 
current compiler technology doesn't work.  Now 
you're telling me that it does.  If the current
technology isn't broke, why do you want to spend 
energy fixing it?"

Current compiler technology (and into this you can 
toss in all the other available tools) doesn't 
enable software technology to keep pace with 
hardware.  For my money anything that doesn't do 
that is not "working" regardless of what useful 
results it may produce.  That you can take existing 
software technology tools and reform them in a 
manner that does solve the problem and allow 
software to have a greater pace than hardware is 
why I want to spend energy fixing them.

This compiler or that tool sucks, doesn't work, or 
whatever you want to accuse it of, not because it 
doesn't do what it is supposed to do, but what it 
does do does not solve the cost and time spiral.  I 
have no argument with what it does "right".  I want 
to turnaround what it does "wrong" so that the 
whole thing is right.  It turns out to do that I 
don't need more than one interactive tool, my 
software assistant.

"As far as I can tell, the optimiser you're 
describing now is utterly simple: it takes in PL/I 
code, and emits machine code which impliments 
*exactly* what the programmer requested, same type, 
same sequence of operations, same everything.  I 
wouldn't call that an optimiser; my first attempt 
at my Oberon compiler was far more sophisticated."

I use the PL/I optimizing compiler on OS/2, 
otherwise known as VisualAge PL/I Enterprise 
Edition (the expensive spread).  If I specify a 
decimal operand instead of a binary one, it assumes 
I know what I am doing.  If in the course of 
optimization it rearranges the containing 
expression, so be it.  I have never been arrogant 
as a software author, being always sensitive to the 
needs of my user.  If that meant allowing them to 
make a decision more in keeping with their comfort 
zone than in efficiency of operation, then that's 
what I did.  I know who is paying the bills and who 
is entitled to his choice.  I may inform him that 
better options are available, but the choice is 
his.  In no way do I assert my superior knowledge 
without his expressed consent.  We just happen to 
have a philosophical difference on this point.  I 
in no way want to impose mine on you any more than 
you imposing yours on mine.  The purpose of an 
assistant is to assist.  That says it is 
subservient to its "master".

"If you're going to pretend that optimization is 
possible in multiple steps, you should at least 
admit that the steps aren't discrete: each step 
affects all of the others, including the ones 
before it."

I'm not going to pretend at all.  Optimization can 
be an iterative process, occurring through multiple 
levels until in one pass through the levels no 
change takes place.  If that means starting over at 
the top after every change, then that's the price 
paid.

Optimization is an art form, a specialty within a 
specialty.  I am not going to claim any expertise 
whatsover, neither deny not claim any of the 
possibilities you mention.  What I do know is that 
when executed in software they follow the rules of 
logic.  As such they are specifiable in a 
"universal" specification language.  As long as 
they are specifiable (by someone) and I know from 
experience that they exist, I have no further 
concern (or interest).  If they are not in the 
specification pool, then they do not exist for me.  
I must content myself with what is available.

"This is because you clearly and repeatedly talked 
about how your program would explore all programs 
which are logically equivalent to the 
specifications.  If you're not in fact going to do 
that, then it would be highly proper of you to not 
say you are."

Let's lay this puppy to rest.  If I say it except 
in the context of translating machine-independent 
specifications of the third level into those of 
either the second or first machine-dependent 
specifications, then understand I didn't mean that: 
I only meant this.  It certainly does not occur at 
the program level only at the operator/operand 
level expression level.

"Rice's theorem applies quite well: you claim that 
you can generate a set of possible programs, then 
choose the fastest from among them (and resolve 
ties by choosing the smallest).  Rice's theorem 
points out that program termination is 
uncomputable; there's no computable way of knowing 
whether an arbitrary program will terminate, much 
less how long it takes to do so."

As hopefully we are off the logically equivalent 
program nonsense and into the only area in which 
logical equivalence applies (translation of 
machine-independent specifications into 
machine-dependent ones), then we will cease our 
concerns about upsetting Rice's Theorem.<g>  That 
bothered some people, thinking that I was somehow 
belittling a respected achievement in computer 
science.  Of course, I wasn't doing that at all.  I 
was simply operating in a different arena.

"I never cared one whit about expression 
evaluation.  Optimization is our topic.  Only the 
inputs and outputs of the program matter."

Maybe we have finally hit upon what separates us: 
we had different topics in mind.<g>  I claimed that 
it was possible to produce optimal code equal to or 
better than the best in assembly language 
programmers.  I also claimed (as others in private 
responses have confirmed) that the performance 
difference does not lie in optimization but in 
deliberately imposed "overhead" expense.  We do not 
perform as well because we can't, but because we 
choose not to.  For that reason it remains an 
option to write in a HLL and achieve the best in 
assembly language performance.  The issue is 
comparing apples to apples, same to same.  If you 
do, then assembly language offers no 
advantages--regardless of what your friend does.<g>

"You were, just a few messages ago, talking about 
how the current compilers didn't meet your desires.  
Now they suddenly seem to make you very happy."

Meeting my desires is one thing.  Having the best 
of a bad situation is another.  Until I have 
something better I will content myself with the 
best available: PL/I.  Besides I can be happy in a 
bad situation.  That like anything else is a choice 
we make.