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

Groups > comp.lang.c > #168658

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

Show all headers | View raw

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

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

Yes, I agree.  I was not suggesting there was a practical problem.

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

I think this is going to get messy because I contend that C (certainly
freestanding C) already excludes an infinite number of computable
functions because it's model is everywhere bounded.  (Yes, I know we
might want to consider IO to be essentially unbounded.)

But that's a side issue!

I meant only that the kind of processing the example indulged in could
be deemed invalid without affecting C's Turing completeness.  You
considered the program "large" in that it generated a huge
post-processing input.  C could have declared such "large" programs
to be invalid.

For the specific issue that was raised issue, Turing completeness is
irrelevant.  You can have a language that is not TC but exhibits the
same problem (unmanageable compiler-time costs) as well as one that is
TC that does not exhibit the problem.

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

Yes.  "Compile-time costs" was supposed to mean costs (in terms of
resources) incurred at compile time.

-- 
Ben.

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