Re: What is the meaning of an expression?

From	Christopher F Clark <christopher.f.clark@compiler-resources.com>
Newsgroups	comp.compilers
Subject	Re: What is the meaning of an expression?
Date	2022-01-19 20:13 +0200
Organization	Compilers Central
Message-ID	<22-01-071@comp.compilers> (permalink)
References	(1 earlier) <22-01-060@comp.compilers> <22-01-066@comp.compilers> <22-01-067@comp.compilers> <22-01-068@comp.compilers> <22-01-069@comp.compilers>

Show all headers | View raw

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
------------------------------------------------------------------------------

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

What is the meaning of an expression? Roger L Costello <costello@mitre.org> - 2022-01-14 12:15 +0000
  Re: What is the meaning of an expression? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-01-14 18:20 +0000
  Re: What is the meaning of an expression? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-01-15 00:28 +0100
  Re: What is the meaning of an expression? gah4 <gah4@u.washington.edu> - 2022-01-14 17:58 -0800
  Re: What is the meaning of an expression? George Neuner <gneuner2@comcast.net> - 2022-01-15 02:05 -0500
  Re: What is the meaning of an expression? "matt.ti...@gmail.com" <matt.timmermans@gmail.com> - 2022-01-15 06:21 -0800
    Re: What is the meaning of an expression? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2022-02-03 12:50 +0000
  Re: What is the meaning of an expression? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-01-16 07:44 -0800
    Re: What is the meaning of an expression? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-01-17 15:45 -0800
      Re: What is the meaning of an expression? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-01-18 10:03 -0800
        Re: What is the meaning of an expression? gah4 <gah4@u.washington.edu> - 2022-01-18 15:18 -0800
          Re: What is the meaning of an expression? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-01-19 11:54 +0100
            Re: What is the meaning of an expression? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-01-19 09:17 -0800
              Re: What is the meaning of an expression? gah4 <gah4@u.washington.edu> - 2022-01-19 14:03 -0800
              Re: What is the meaning of an expression? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-01-20 13:02 +0100
                Re: What is the meaning of an expression? dave_thompson_2@comcast.net - 2022-01-30 22:51 -0500
            Re: What is the meaning of an expression? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-01-19 20:13 +0200
              Re: What is the meaning of an expression? Thomas Koenig <tkoenig@netcologne.de> - 2022-01-22 20:46 +0000
  Re: What is the meaning of an expression? Thomas Koenig <tkoenig@netcologne.de> - 2022-01-19 20:51 +0000

csiph-web