Re: What is the Result from Invoking this Halt Function?

From: Dave Vandervies (dj3vande_at_csclub.uwaterloo.ca)
Date: 08/24/04 

Date: Tue, 24 Aug 2004 17:47:20 +0000 (UTC)

In article <r6BUc.143296$8_6.125175@attbi_s04>,
Marc Goodman <marc.goodman@comcast.net> wrote:
>Joe Hendrix wrote:
>> You are redefining your claim. You claimed that code proved that
>> reflection was possible in standard C (by reflection I mean the ability
>> of a program to inspect it's own code at runtime). I merely pointed out
>> that your example was not Standard C, so it is not a counterexample.
>
>You're exactly right. The point I was missing was that Standard C
>is different from standard C. For me, "standard C" is whatever
>compiles with a standard C compiler like gcc and runs on a
>standard computer like a PC with Linux. "Standard C," on the
>other hand, refers to a programming language standard as spec'ed
>out by a standards organization and is an entirely different
>kettle of fish.
>
>I acknowledge that you are probably right that there is no method
>in "Standard C" to cast a function pointer to an int pointer and
>to dereference that pointer. Please take me the last little way
>to the end and cite a URL that states this is forbidden/illegal/etc.
>I ask this not because I disagree with your point but because
>I would like the opportunity to educate myself.

Looking at the last public draft of the new standard ("C99") (I don't
have a URL readily available; google for 'n869' if you want to follow
along), section 6.3.2.3 defines the acceptable pointer conversions, and
"pointer to function -> pointer to data" is not among them.

This brings us to 4#2, which says:
       [#2] If a ``shall'' or ``shall not'' requirement that
       appears outside of a constraint is violated, the behavior is
       undefined. Undefined behavior is otherwise indicated in
       this International Standard by the words ``undefined
       behavior'' or by the omission of any explicit definition of
                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
       behavior. There is no difference in emphasis among these
       three; they all describe ``behavior that is undefined''.
and 3.18#1:
       [#1] undefined behavior
       behavior, upon use of a nonportable or erroneous program
       construct, of erroneous data, or of indeterminately valued
       objects, for which this International Standard imposes no
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
       requirements
       ^^^^^^^^^^^^

So since there's no definition of the meaning of this construct, its
behavior is undefined and can't be relied on unless you have something
outside the C language that defines it (in your case, the processor's
memory model and the code generated by your compiler).

So if you want to demonstrate something that uses introspection on the
code that's running, you shouldn't be calling it C.

>> Since any programming language I know supporting reflection is provably
>> Turing complete (ignoring resource limits), I don't think this affects
>> the halting problem, but that's not really a subject I'm going to post
>> anything (else) about.
>
>I agree completely with the last statement. Since it can be implemented
>in _non_ standard C, you either have to argue that a PC running gcc and
>linux is more powerful than a Turing Machine (which is clearly wrong)
>or that adding reflection does not increase the computational power
>of the model.

The latter isn't difficult to argue: just create an emulator that
doesn't use introspection and treat the entire system+program that does
use introspection as data, and you now have the exact same behavior
without introspection.

dave 

-- 
Dave Vandervies        dj3vande@csclub.uwaterloo.ca
Don't blame me, blame Georg Cantor.
         --James Riden in the scary devil monastery

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... >> reflection was possible in standard C (by reflection I mean the ability ... >> that your example was not Standard C, so it is not a counterexample. ... >to dereference that pointer. ... So if you want to demonstrate something that uses introspection on the ...
    (comp.theory)
  • Re: What is the Result from Invoking this Halt Function?
    ... > reflection was possible in standard C (by reflection I mean the ability ... > that your example was not Standard C, so it is not a counterexample. ... in "Standard C" to cast a function pointer to an int pointer and ... > Since any programming language I know supporting reflection is provably ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... > reflection was possible in standard C (by reflection I mean the ability ... > that your example was not Standard C, so it is not a counterexample. ... in "Standard C" to cast a function pointer to an int pointer and ... > Since any programming language I know supporting reflection is provably ...
    (comp.theory)
  • Re: A C++ Whishlist
    ... In the vast majority of member functions the first thing you will do ... If I feel it needs an extra check because it won't crash cleanly I may ... >> unless you also check the this pointer you aren't checking every ... The standard does not say "the this pointer cannot be NULL". ...
    (comp.lang.cpp)
  • Errata for The C Programming Language, Second Edition, by Brian Kernighan and Dennis Ritchie
    ... Today I found out that the official page of errata for The C Programming Language, Second Edition, by Brian Kernighan and Dennis Ritchie is down: ... The first printing of the book was made before the Standard was finalized; these copies say "Based on Draft-Proposed ANSI C" on the front cover. ... ``A pointer may be converted to another pointer whose type is the same except for the addition or removal of qualifiers of the object type to which the pointer refers. ...
    (comp.lang.c)