Proposals

[Lynn H. Maxson]

"One difficult part of talking with you is that you 
never answer yes or no to a question, nor do you 
directly address a statement.  You instead discuss
something related to the statement which happened 
to be on your mind at the time."

Billy, part of the time it is guessing game.  You 
realise that you have not communicated well which 
leaves you guessing on what it takes to get on 
track.  Once you done this incorrectly several 
times the task gets even more difficult.  I've 
often considered answering with a simple "yes" or 
"no".  Maybe you have offered me an easy way out.

"I don't understand how your comment about 
"specialties" has any relation to the rest of your 
paragraph.  How does it?

Optimization is not a specialty -- it's 
everything."

The paragraph contained a reference to how IBM has 
relegated its "optimized" code generation for its 
compilers regardless of source language to a group 
devoted to that purpose.  This to my way of 
thinking makes it a specialty.

As to the reference that it is "everything" I must 
somehow protest.  In order of priority of emphasis 
I must place the mapping of the solution set to the 
problem set as first.  If that means using fixed 
decimal integer arithmetic instead of binary, then 
so be it.  

After doing that I am interested in its most 
efficient execution.  To do that I need to know "a 
priori" the mix of the input data.  All programs 
are data driven.  The greater the knowledge I have 
of the input data the better I can organize the 
decision logic to as to minimize the average number 
of decisions made in the aggregate.  This is one 
form of optimization available to me with an HLL.

As I cannot optimize an iteration, considering that 
its decision logic is necessary and sufficient, 
that leaves only sequences.  For me to optimize 
these in terms of generated code I am dependent 
upon feedback from each implementation.  For the 
same compiler whose implementation varies by the 
version that implies that either I go back to all 
the source I have written in all programs using 
that compiler or I simply accept what it produces 
unless its runtime turns out not to be "good 
enough".

" Everyone who's ever written a program is an 
optimiser.  Anyone who's ever walked a new route to 
an old place is an optimiser."

An optimist, maybe.<g>

"There are many specialties within optimization, of 
course.  Some of the most rigorous involve the 
attempt to translate some aspects of optimization 
to a machine-expressible algorithm."

How does it differ as a specialty here from my 
illustration?

"Those responsible for code generators must be, 
yes.  I see you're bringing in a confusion between 
code generation and optimization again; the 
ultimate optimiser is also a code generator, but 
merely making a fancy code generator doesn't give 
you an optimiser.  Optimising is FAR more 
difficult."

Well, if everyone who writes a program is an 
optimiser, how difficult can it be?  One of us 
certainly is confused.<g>  Optimizing compilers 
which internally reorganize the translated source 
statement and then seek to minimize the execution 
time of the generated code are not merely fancy 
code generators, but optimizing code generators.  
That it is difficult for people to do consistently 
is why you incorporate the rules into software.

If you write in a HLL, you have no control over the 
code generated, whether or not you select an 
optimizing option.  The only control you have, 
where you know what code get generated for a 
particular expression, is to write in the form of 
that expression.  Even there the sequence may 
change from one version to the next.  So you dare 
not recompile without reverification.

"The computer won't find the optimum for anything 
but the most trivial imaginable program in a week.  
I disproved this in my last post."

Maybe we can assert this as Billy's Theorem where 
Billy operationally defines the difference between 
an "optimiser" (the person), "optimizing" (the 
process), "optimum" (the result), and "efficient" 
(today's optimum).<g>  

"...and in the process, he'll have changed the 
low-level design of the code just a bit to better 
fit the architecture, something your computer can't 
do in a million years."

You must be running scared here to believe that any 
better fit he discovers is not specifiable in 
software.  We can debate whether or not it is 
possible to specify in software a discovery process 
that could "discover" this more efficient form in 
some reasonable time period.  We cannot debate that 
once discovered we can specify our discovery in 
software.

The point is that the "computer" (for some reason 
you still regard this as an independent entity) 
does what the software tells it to do.  If we tell 
the software "with this input produce that output",
it will do it without having to "discover" what to 
do.<g>

"Yes, I do.  I insist that the programmer will code 
NOT the best possible code for the low-level 
design, but rather code which is BETTER than 
possible for that low-level design."

Now I am not sure which of us is more confused.<g>

"Do you still believe any of that?  Then let me 
disprove it in ONE WORD:

Go.

ONE PERSON can defeat a computer at Go, even 
allowing the computer a huge amount of time."

Well, technically no.  The human player would have 
to pass on the next move to his successor as the 
amount of time that the software would need might 
exceed his lifetime.  To say that we have granted 
it a "huge" amount of time is also saying that we 
have also set a limit.<g>

However picking an optimal strategy is different 
from optimizing a code sequence.  That is dependent 
upon finding that code sequence which uses the 
least number of machine cycles each execution 
regardless of the number of executions.  While the 
number of executions may be large all the machine 
logic associated with each iterative execution may 
be optimum.

Moreover the fact that a program may never 
terminate does not mean that it is not executing as 
fast as it possibly can.<g>  Stick with the subject 
of code optimization.

"You're also mistaken when you associate heuristics 
with optimum solutions.  Heuristics don't even try 
to find optimum solutions; they merely find 
solutions which are 'good enough'."

I don't care how humans arrive at a decision, come 
to a conclusion.  Whether optimum or "good enough", 
as long as it can be specified in software it will 
suffice.  If a better, more optimum way is found, 
we can replace the existing choice with the newer 
one.  We may never discover an optimum, but that 
does not prevent us from coming closer and closer 
nor preventing our specifying our discovery in 
software.

I do not argue that software does anything on its 
own, even a discovery process, that is not dictated 
by human-determined rules.  That which we discover 
we specify in software such that we can get maximum 
benefit.  The software functions as a tool 
extending human abilities.  I do not go to war with 
software or regard it as a competitor when in fact 
it is a loyal and blindly obedient servant.

Now it is true that as a human I can master many 
machine architectures and discover hundreds and 
thousands of rules which apply to expression 
evaluation in terms of code generation.  However I 
have determined that I prefer to write in a HLL 
ignorant (independent) of any machine architecture.  
Thus I incorporate my rules into software governing 
the translation of my language into the machine's 
language in the same manner "as if" I had written 
it in its language.

Now whether my discoveries are optimum or not is 
unimportant.  What is important is that among my 
discoveries and those of others is at least one in 
any given input instance that is equal to or better 
than any other in terms of machine cycles required.  
It may not be optimum in any absolute sense, but it 
represents my best choice at the moment.  Until a 
new discovery comes along, gets added to the 
collection, and a new evaluation changes things it 
will have to be "good enough" as it is the best I 
have (currently).

"You're also badly mistaken (shockingly so) when 
you claim that selecting from an infinitely large 
set requires an infinite number of programmers.
The very act of programming IS by definition 
selecting a single program from an infinitely large 
set (the set of all programs); so is optimization 
(the set of all programs which fit the specs).  
This is done all the time by a SINGLE programmer."

It's no wonder that I tend to meander a bit in 
these responses as I ponder a stratagem to pursue 
to get communication back on track.<g>  To quote 
you in a word "go".  The first player makes a move.  
The second player concedes defeat.  There's no 
sense in playing out a game you know you are going 
to lose.<g>

You have great faith in the gestalt abilities of 
every programmer.  It amazes me then how different 
ones come up with different results.  Must be 
something willy-nilly in the individual selection 
process from the same infinite pool of programs.  
The fact of the matter is that you can make a 
non-optimum selection.  To make an optimum 
selection you would have to examine an infinite 
number.  No matter how quickly you eliminated one 
from consideration the time would exceed your 
lifetime.

I won't even bother that the storage capacity of 
the brain would not hold an infinite number even it 
were possible to examine each (which by definition 
of infinite is impossible).  So obviously it does 
not occur in this manner by any single or multiples 
of programmers.<g>

">Moreover there is no way anyone can develop a 
>"secret" heuristic and keep it that way in 
>practice.  Once it exists in machine code the 
>secret is out: it becomes another among a host of 
>heuristics.

What?  That's impossible."

Wrong again.<g>  The longer answer would be that 
for a given input a new output mapping exists.  
That new output is specifiable in software.

"No, it's because heuristics vary.  The same 
heuristic can be coded in different ways; or the 
code to recognise when the heuristic fits might be
better or worse.  The compiler's optimiser might be 
better or worse (and that's one area where there's 
DEFINITELY no one best way).

It's not a technical problem; it's a mathematical 
impossibility."

It does not make a difference how you code a 
heuristic, by definition it must produce the same 
result.  The only possible difference is the time 
required.

It is true that how people code logic can impact 
the application of an heuristic.  That's a people 
difference which we seek to overcome.  That is true 
when it comes to the compiler's optimiser.

From a given set of choices, finite or infinite, 
there may be no "one" best choice (although there 
may be), but there is at least one whose runtime 
performance (regardless of its space requirements) 
is at least equal or better than any other.  For 
what it is worth it is logically true.<g>

"Sure, if you want.  Of course, that's not true; 
optimization is a single process, and performing it 
piecemeal will always result in something inferior.  
However, it's generally good enough."

Optimization is a process.  A process is a set of 
stages (sub-processes).   Each is a piece.  Anytime 
a piece makes a change we transfer control back to 
the intial sub-process to repeat the process.  Once 
we get through this iteration, when no piece makes 
a change, we terminate the process.

If you believe that because every process must be 
executed in a piecemeal manner and therefor must 
produce inferior results, then I will exit any 
further discussion on the subject.<g>

"Ah, but this isn't true!  Ever heard of "loop 
unrolling"?  It can VASTLY speed up code!  Of 
course, it increases the bulk of code..."

Loop unrolling can only occur where the number of 
iterations is fixed and known at "compile time", 
i.e. expressed in the source.  As such it is 
subject to the embedded optimizing rules which can 
account for it as well.  If your statement is that 
it makes a different directed graph, one of 
repetition and not iteration, it still does not 
affect the optimization of the repeated code.

"Do you hear what you're saying?  Read it again!  
Look at what you're saying to me!!!!!!!  Please!  
You're claiming that you're not trying to find when 
a program terminates; what you're actually trying 
to find is WHETHER A PROGRAM TERMINATES IN LESS 
TIME.  Same thing!"

Well, one of us is confused.  I don't have any 
problem with whether a program terminates or not or 
even when it terminates.  The only assumption that 
I make is that in two executions (which could be 
occurring concurrently) that it is possible that 
one is executing faster than the other, that 
somehow their internal coding differences accounts 
for their performance difference.

Strangely enough I can tell you that a program will 
terminate if that program contains a sequence only.  
I can on a given machine with a given set of code  
tell you when it will terminate.  I can because I 
have done so.  I didn't allow somebody's theorem to 
get in the way.  The fact is that there seems to be 
a variation in the runtime between the different 
runs, so you have to iterate it in as near isolated 
conditions as much as possible a thousand or more 
times to have some confidence in the "average" run 
time.

This method comes directly from Abrash's "The Zen 
of Assembly" which is on my bookshelf along with 
the "Tao of Objects" and the "The Art of the 
Metaobject Protocol".  Fortunately Abrash hadn't 
heard of Rice's Theorem either so he could offer a 
terminating code wrapper for my code so that we 
could determine from a set of given expressions 
which one ran faster.  Without proving it other 
than empirically, which is the only real world 
test, I had no other proof in mind.<g>

"... and you profile the program while it's 
running.  Parts
of the program which run frequently can get 
optimised with more
time-consuming optimization processes.

Suprisingly, it seems to work well."

Yes.<g>

"Have you ever attempted to count the number of 
paths in a trivial program?  You're correct that 
it's finite (by your definition of the word 
'path'); however, it's a HUGE number.  Using your 
algorithm, we'd have to optimise each path 
seperately; you miss the fact that any two paths 
can overlap, and usually do."

The most trivial program is a sequence of a single 
statement.  Counting the number of paths is quite 
simple: one.  I have in fact accounted for the 
number of paths in a non-trivial program.  When 
called upon I depend upon my PL/I compiler to 
enumerate the number of paths in a program.

As I write structured code I don't seem to have the 
overlap problem you referred to.  I do have 
reusable paths, but they are logically 
non-overlapping.  Using my algorithm we would have 
to optimize each path separately.  If that meant 
that reusable portions would differ, then we would 
generate multiple versions of each portion.  That 
may bother your optimizer, but not mine.<g>

"You speak of "finite" additional time -- but are 
you sure that the time is finite?"

This gets back to the "infinite possibilities" 
thing you laid on me.  In any give language we have 
only a certain (finite) number of operators.  In 
order for there to be infinite possibilities at 
least one of these operators must fall into this 
category.  I would be more than happy at some other 
time to take each operator in turn for any given 
machine architecture to show for each there were 
only a finite number of choices.

I understand your definition of logical 
equivalence.  I also understand the concept of 
machine cycles.  I also understand how I can use an 
heuristic regarding one to restrict what I have to 
consider out of the universe of the other, a 
restriction which reduces what I produce to a 
finite number.  It is no more than saying that 
while the set of integers is infinite, the set of 
those equal to or greater than zero and equal to or 
less than 37 is not.  

That means all I have to have for each operator is 
a "starter set" of machine code.  I never have to 
consider anything which exceeds its number of 
machine cycles.  Machine cycles is what determines 
from a set of choices which is best, whether 
optimum or not.  The optimum choice is either equal 
to or less than this.  If less than this, then it 
must be in the "computable" finite set.

"You've said this before, and I don't understand 
it.  How does your system cause this to happen?  I 
don't understand at all."

You understand public domain.  Here's a 
specification language whose definition is 
specified in the language, i.e. exists as a set of 
specifications.  Here's a tool written in that 
language.  Here's the source for both in the public 
domain.

What is it that you don't understand?  Here is a 
language and a tool whose only input is source.  It 
has rules of syntax and semantics.  As long as the 
source follows the rules you cannot introduce 
incompatibilities.  You can introduce 
contradictions, but that simply means selecting one 
or the other or a process which includes both.

The user owns the tool and the source.  When he 
wants an application written he finds someone to 
write the additional specifications expressed in 
the source language.  These get added to the user's 
source: they remain his property.

This is no more than what occurs in large accounts 
with their own IT departments today.  All this does 
is bring it down to the level of the individual 
user.  If the minimal claim of "50 times time 
reduction, 200 times cost reduction" is valid, it 
means that a single user can afford to have a 
"build to order" (custom) solution now instead of a 
"build to stock" (package) currently.

If users keep adding source into the public domain, 
then more and more applications become less and 
less expensive.  In that manner the current 
advantage that vendors have over users disappears.  
In such a system the user dictates and the vendor 
obeys.

The beauty of a specification and a formal 
specification language lies in its non-proprietary 
nature.  You cannot own "what" something does, only 
"how" it does it.  If I personally have a "what" in 
mind, and a means of producing an executable on my 
own, i.e. not for resale, then nothing or no one 
can physically, legally, or otherwise stop me.  If 
I submit my "what" to the public domain, all of 
whose members have the same capability, then 
nothing can stop them either.

You cannot introduce incompatibilities.  You have 
no need for standards other than rules of syntax.  
There's no way for anyone to establish a monopoly 
and quash competition.  You (and maybe a few 
friends together) can afford to have custom 
specifications written (if you cannot or do not 
want to write them yourself).  What you have is a 
viable market segment down to a single user.

Now what is it that you don't understand?<g>