Re: What is the meaning of an expression?

Not to continue to belabor this overly drawn-out discussion, but
gah4's question of feeding a compiler a logical inconsistency and
having it crash is vaguely relevant.


I have two examples. The first one, hearsay, from what I consider
normally reliable sources.


The template mechanism of C++ is Turing Complete and unfortunately,
some programmers have taken advantage of that in an attempt to
optimize their programs to an unreasonable extent. The result is
compilations that take hours for programs that run in seconds and may
only be run once. I can only imagine someone writing an NP-complete
problem, say 3-SAT as a template and wondering why their compilation
never finishes when they give it a problem with one hundred variables.


The template mechanism may be Turing Complete, but the implementation
doesn't have all the limitations and declarations that make programs
tractable. Moreover, no one has spent years optimizing the template
processor for such cases, and it is not clear that it would be
possible to do so. We don't know how to solve the halting problem. And
the template processor is supposed to *be* the Oracle, not require
one.


The second one was from my own experience working on the Alpha
optimizer at DEC. The C++ compiler was one of the last pieces of
software to use the one based upon Fred Chow's work. That was my
responsibility at the time (the optimizer, not the C++ compiler). In
any case, the front end writers were very aggressive in inlining
subroutines and doing whole-program optimization by that trick. The
result was very massive files of the intermediate representation. The
result, for certain large (and important) C++ programs the compiler
would work for days before it had filled up all the paging space on
the engineering cluster at DEC, which was multiple disks of paging and
as a result crashed not only the compiler, but in some cases the
entire cluster. This made for some very unhappy users, because they
had waited days and they still didn't get a successful compilation.


Fortunately, a small amount of analysis on my part allowed me to
realize that most of the optimizers data structures while N-squared in
size, were actually filled with mostly zero values. Thus, with a
couple days of work I was able to come up with easily implemented
compression schemes that drastically reduced that footprint. The
result was that the compilation finished in mere minutes, not days,
and more importantly, actually finished, not filled the paging disk
and crashed.


-----


Thus, in that respect the "meaning" of an expression might be vaguely
relevant if the compiler is required to "figure it out". And, so
while it doesn't take a logical inconsistency to crash a compiler, we
do have the means to do so. It isn't actually that hard.


--
******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.