Proposals

[btanksley@hifn.com]

I spent some time reviewing our past correspondance, since it seems that
we're not communicating.  I discovered several things, the most alarming of
which is that most of our correspondance took place off the list, simply
because the tunes-list doesn't set its Reply-To: correctly, so that replying
to the list requires special action on the part of the user.  Why is this
the case?

From: Lynn H. Maxson [mailto:lmaxson@pacbell.net]

The longer we converse, the more confused I become.  I've taken some care
now in going over your past posts and sifting through the immense quantity
of prose; I find myself still confused on all but one point.

That one point is that you want to generate NOT all logically equivalent
expressions, but rather all sequences of machine code which implement a
given, FIXED expression.  That (single) fixed expression is the result of
some other optimiser, which probably has no relationship to your code
generator.

>Maybe we have finally hit upon what separates us: 
>we had different topics in mind.<g>

Precisely.  No doubt you've been pondering the same possibility for some
time; I certainly have.

I won't go through a list of the things you've said which convinced me that
you were talking about something else; however, I will point out the
following, which IMMEDIATELY followed the sentance you just spoke:

>I claimed that 
>it was possible to produce optimal code equal to or 
>better than the best in assembly language 
>programmers.

You see, the problem is that this sentance is nonsense when restricted to
what you're ACTUALLY talking about (code generators).  However, it makes
complete sense when it's what I'm talking about (optimisers).

No code generator could ever HOPE to come close to an assembly language
programmer; this is doubly true for a code generator for a language which
isn't platform specific, or for a program written in a platform-specific
language by a person who didn't understood the assembly he was going to
produce better than the assembly language programmer did.  However, an
optimiser _could_ beat any assembly language programmer; if only the
optimiser could examine all of the possibilities.

The fact that it's impossible to examine all of the possibilities renders
such an optimiser impossible; and that should have been my clue that you
were talking about something else.

Unfortunately, what you're actually talking about IS possible, but isn't as
glorious as you'd hoped.  It would indeed beat all heuristic code
generators, but it would not beat a clever human, since the human can
combine optimization with code generation (as it should be).  I don't think
that it would beat an optimiser which worked together with a code generator;
the two operations are rather tightly coupled in reality (although not in
theory).

It does (at this point) occur to me to wonder how much time your code
generator would require.  It would seem to take a HUGE amount of time to
generate all the possible translations.  Let me re-run my earlier
calculation, this time based on what you're actually discussing:

We have a one million line program.  Each line contains three operators.
Therefore there are only three choices to make per line; let's suppose for
the sake of argument that there were only two possibilities for each
operator.  Therefore there are 2^(3000000) possible programs.  Nope, never
mind; that's not possible either.  So we can't actually generate all
possible programs; we have to do a tree-based search, pruning unlikely
branches using various heuristics.  I doubt that the result would be
practical for such a large program, but I suspect that I could handle it for
the 6000-line C file I'm working on at work (although I couldn't have waited
for 2^6000 programs to generate; I think my patience would run out at 2^20
or so).

You are, however, bypassing the importance of Rice's Theorem, and I don't
understand why you feel justified in that.  If it's impossible to decide
which program is faster, how can you be justified in claiming that you can
choose the fastest?  I myself would choose instead the smallest, not the
fastest; I wouldn't always be right, but at least I would often be, and it's
a decision which is easy to make.

You're also missing another point: that even if we can decide which program
was faster, what if one of the programs was faster for one input, and
another one for another input?

-Billy