Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #168642

Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?)

Show key headers only | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> antispam@math.uni.wroc.pl writes:
>>
>>> Lynn McGuire <lynnmcguire5@gmail.com> wrote:
>>>
>>>> I doubt that any modern C/C++ compilers refuse to take any legal
>>>> C/C++ code.  I would not be surprised that modern C/C++ compilers
>>>> detect certain benchmarks
>>>
>>> Some time ago I posted here a simple C program.  It looks legal
>>> (nobody here objected to legality of this program).  In principle
>>> compiler should generate pretty small executable, but it looks
>>> that no existing compiler can handle that program.  One can say
>>> that compiler does not "reject" the program, simply compiler runs
>>> out of memory.  But for the user effect is the same:  compiler
>>> will not handle legal program.
>>
>> And the answer is the same as before.  The C language is
>> infinitely large (and indeed must be if it is to be Turing
>> complete).  Compilers are programs;  no program can deal with
>> unboundedly large inputs (not counting the vanishingly small
>> fraction of programs whose output set is finite rather than
>> infinite).  No competent person expects a compiler (or indeed any
>> non-trivial program) to be able to handle unboundedly large
>> inputs.  A program that is unable to handle a large input simply
>> because of its size is not "refusing" to handle the input, and
>> anyone who says otherwise is just being obtuse.
>
> But the program was not particularly large.

It is true that the original input was small.  On the other hand,
the semantics of that input is defined by a textual processing
step, and said step yields a huge output.  It's naive to think
that this pre-processing and subsequent program analysis would
be accomplished in any way that is significantly different than
would the program that corresponds to the output of expanding the
original input in a straightforward manner.  Certainly it is no
stretch to say that antispam@math.uni.wroc.pl is not naive.

> Instead, the program required a large amount of compile-time
> processing which the standard /could/ have deemed to be not
> strictly conforming by, say, putting a limit on the number of
> tokens permitted in the result of a macro expansion.

Sure, that could be done, but there is no point in doing so.  The
translation limits that the C standard does define all have the
property that they might be transgressed accidentally.  What
limit would someone propose for the size of a program after doing
macro expansion?  2**30?  No program is going to exceed such a
limit accidentally.  But if the limit were significantly smaller,
even say on the order of 2**20, there are useful program that
would exceed that.  The purpose of translation limits is to put a
useful lower bound on what compilers must accept (and note, not
what they must successfully /translate/, but what they must
/accept/, which is quite another thing).  Putting an upper bound
on the size of a macro expansion (which, by the way, is not easy
to define, because the expansion might not all be done at once),
serves no useful purpose.

> The standard does not do that, so there are small, strictly
> conforming programs that one can't reasonably expect to be
> processed.

Okay.  So what?  Programming languages that include some kind of
macro processing all have this property.  In practice it doesn't
matter.

Translation limits in the C standard are there so implementations
can use fixed-size tables for certain data structures and not
worry about not being conforming.  It is not purely a coincidence
that the translation limits defined are all small numbers.  But
there is no such small number or data structure for performing
macro expansions, because of how they are processed and how they
have been used historically.  To say this another way, putting a
large upper bound on program size or how big a macro expansion
would be doesn't do anything to help compilers.  Putting one in
would be artificial and not really helpful in any useful way.

> Also, I think the reference to C being Turing complete is a red
> herring.  C could be defined in such as way that valid inputs to
> the compiler are always "small" and never require unbounded
> processing without compromising the language's completeness.
> There need not be any language feature that can incur exponential
> (let along unbounded) compile-time costs for a language to the
> Turing compete.

Either I don't know what you're getting at here or what you're
saying is wrong.  To be Turing complete a language must be
infinite rather than finite.  Restricting a language to "small"
programs, if "small" means some finite bound, will necessarily
exclude an infinite number of computable functions.  Even if we
accept that all "useful" programs will be "small", there is no
reason to impose an artificial limit on program size;  any
particular limit will either be so large that it cannot be
accommodated, or sufficiently small that it might intrude on the
set of programs that people might reasonably want to write.
There is no way to pick a limit that is sufficiently large so
that it certainly includes all useful programs, but no so large
that it isn't just absurd.

Incidentally, the processing time needed is irrelevant.  The
compiler will run out of memory long before it runs out of CPU
cycles.

My guess here is that all this discussion is a consequence of
antispam not understanding the purpose of defining "strictly
conforming" programs.  Being strictly conforming has nothing to
do with whether a compiler will successfully process a program.
Which programs a compiler will successfully process is purely a
quality-of-implementation issue, and the C standard consciously
avoids such questions.

> C++ has this issue in spades because the template sub-language
> is Turing complete.

I don't think of large macro expansions in C as being a problem
with the C language.  Templates in C++ being Turing complete is a
different situation, because it isn't possible to tell if a
template "program" will terminate.  In any case I think it would
be better for my mental health not to think any further about
problems in the C++ language.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) KP2 KP2 <jungletrain@outlook.com> - 2022-12-10 13:06 -0800
  Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Lynn McGuire <lynnmcguire5@gmail.com> - 2022-12-10 20:57 -0600
    Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Lynn McGuire <lynnmcguire5@gmail.com> - 2022-12-10 22:57 -0600
    Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) antispam@math.uni.wroc.pl - 2022-12-11 20:31 +0000
      Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Robert Latest <boblatest@yahoo.com> - 2022-12-12 14:39 +0000
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) antispam@math.uni.wroc.pl - 2022-12-13 12:15 +0000
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-13 16:23 +0000
      Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-26 05:20 -0800
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 14:37 +0000
          Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-26 10:30 -0800
            Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 16:45 +0000
              Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-27 19:38 -0800
                Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-29 02:09 +0000
                Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-29 19:56 -0800
  Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) antispam@math.uni.wroc.pl - 2022-12-11 20:12 +0000
    Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Lynn McGuire <lynnmcguire5@gmail.com> - 2022-12-12 14:33 -0600
      Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) scott@slp53.sl.home (Scott Lurndal) - 2022-12-12 21:12 +0000
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-12-12 16:09 -0800
  Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Jack Lemmon <invalid@invalid.net> - 2022-12-12 20:30 +0000
    Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Lynn McGuire <lynnmcguire5@gmail.com> - 2022-12-12 15:20 -0600
    Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-12-12 21:28 +0000
      Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) scott@slp53.sl.home (Scott Lurndal) - 2022-12-12 22:39 +0000
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-12-12 22:49 +0000
          Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) "minf...@arcor.de" <minforth@arcor.de> - 2022-12-31 04:01 -0800
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-12-12 15:56 -0800
          Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) scott@slp53.sl.home (Scott Lurndal) - 2022-12-13 14:55 +0000
            Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) David Brown <david.brown@hesbynett.no> - 2022-12-13 16:26 +0100
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) David Brown <david.brown@hesbynett.no> - 2022-12-13 14:50 +0100
        Re: Limitation of MS-DOS C compiler? (was Re: Should I convert FORTRAN code to C?) Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-12-13 18:56 +0300

csiph-web