How many levels of pointers can you have?

[Malcolm McLean]

I don't know what exactly you mean by "fully" conforming compilers. I'm
under the impression that you mean a conforming implementation
(or maybe a conforming hosted implementation) that meets certain minimal
QoI standards, but which standards are they?

The standard is published by ANSI.
If a compiler refuses to accept or generates incorrect behaviour on a
conforming program, then the compiler is not conforming.
If you have an insight into how compilers are constructed you can generate
difficult programs. Thinks like sequences that require many tokens of
lookahead to parse correctly will break more naive compilers.

 

[Harald van =?UTF-8?B?RMSzaw==?=]

The standard is published by ANSI.
If a compiler refuses to accept or generates incorrect behaviour on a
conforming program, then the compiler is not conforming.

Then there would not be any conforming implementation.

unsigned fac(unsigned n) {
return n * fac(n - 1);
}

int main(void) {
return fac(-1);
}

This program is strictly conforming. It exceeds none of the limits from
5.2.4.1, and there is no other reason why it might not be. Similar but
slightly more complex programs can be constructed for the rare
implementation that can successfully execute this one.

However, the standard states "The implementation shall be able to translate
and execute /at least one/ program that contains at least one instance of
every one of the following limits:" (emphasis mine), and this is
intentionally so. As clarified in the rationale, the requirements for
conformance are ridiculously low, because with the lowest requirements on
implementations that would actually be of use to programmers,
implementations with bugs would not be considered conforming (!).

Conforming implementations may reject correct programs. They may even reject
strictly conforming programs.

 

[Richard Tobin]

unsigned fac(unsigned n) {
return n * fac(n - 1);
}

Presumably you meant to write something like

return n == 0 ? 1 : n * fac(n - 1);

I assume stack overflow rather than non-termination was intended to be
the significant feature of the program.

-- Richard

 

[Flash Gordon]

Harald van Dijk wrote, On 14/06/07 21:53:

I don't know what exactly you mean by "fully" conforming compilers. If you
mean conforming compilers that accept any correct program (or even just any
strictly conforming program), then such code would prove that the compiler
is not "fully" conforming.

A conforming implementation is only required to work correctly for one
program with certain characteristics. This gives a massive escape for
compiler writers that, as far as I know, they do not take.

> I'll assume you were referring to the complete
implementation (including linker, library, etc.).

An implementation includes the library and everything required to start
with source code and end with something you can run. Normally this
includes a compiler and linker in some form.

> If you just mean
conforming implementations, or if you mean conforming hosted
implementations, then those are intentionally allowed to have bugs, and
because of that there are probably more than six conforming
implementations. If you mean something in between, would you please
clarify? I'm under the impression that you mean a conforming implementation
(or maybe a conforming hosted implementation) that meets certain minimal
QoI standards, but which standards are they?

The C standard defines what it means by a conforming implementation, and
what Chris claimed as the number of conforming implementations sounds
about right for conformance to C99.

I assume that Chris means an implementation that implement all the
normative parts of the C99 standard. I believe you would have the same
number if you looked at compilers claiming full conformance to C99 (as
opposed to implementation like gcc which explicitly state they do not
fully implement C99 or Turbo C 2.0 which does not even mention C99.

Neither Chris nor I are claiming that 6 is the actual number, just that
it is about that.

 

[Harald van =?UTF-8?B?RMSzaw==?=]

Presumably you meant to write something like

return n == 0 ? 1 : n * fac(n - 1);

I assume stack overflow rather than non-termination was intended to be
the significant feature of the program.

Yes, thank you.

 

[Harald van =?UTF-8?B?RMSzaw==?=]

Harald van Dijk wrote, On 14/06/07 21:53:

A conforming implementation is only required to work correctly for one
program with certain characteristics. This gives a massive escape for
compiler writers that, as far as I know, they do not take.
Right.


An implementation includes the library and everything required to start
with source code and end with something you can run. Normally this
includes a compiler and linker in some form.

It always includes a linker in some form, though it need not be usable
separately. Whatever component of the implementation handles translation
phase 8 is a linker.

The C standard defines what it means by a conforming implementation, and
what Chris claimed as the number of conforming implementations sounds
about right for conformance to C99.

By the minimal requirements you mentioned yourself above, the number is far
too low. I assumed this was why Chris used "fully" conforming rather than
just "conforming", and the C standard does not define what it is to be
a "fully" conforming implementation.

I assume that Chris means an implementation that implement all the
normative parts of the C99 standard.

If Chris meant that, then I am not convinced 6 is about right, though it's
believable.

I believe you would have the same
number if you looked at compilers claiming full conformance to C99 (as
opposed to implementation like gcc which explicitly state they do not
fully implement C99 or Turbo C 2.0 which does not even mention C99.

If he meant the number of compilers that claim to conform to C99, as opposed
to the number that do ("fully"), then 6 seems about right to me too.

Neither Chris nor I are claiming that 6 is the actual number, just that
it is about that.

That part was clear to me.

 

[CBFalconer]

.... snip ...

unsigned fac(unsigned n) {
return n * fac(n - 1);
}

int main(void) {
return fac(-1);
}

You have ignored a fundamental rule of computing: A recursive
procedure needs a termination condition.

 

[Chris Hills]

The standard is published by ANSI.

The standard is published by ISO.
ANSI just do an imprint of it like BSI, Din etc. In fact when it came
to C99 ANSI were one of the last to ratify it.

 

[Chris Dollin]

You have ignored a fundamental rule of computing: A recursive
procedure needs a termination condition.

(fx:OT) Not strictly true.

Consider the definition

loadsa x = x: loadsa x

which (modulo syntax -- pick your favourite lazy pure functional
programming language; Miranda or Haskell both handle this) is a
definition of a recursive function `loadsa` that produces an
unbounded list of whatever argument you give it.

No termination condition is required here. (How this unbounded
list is /used/ is what governs termination.)

 

[David Thompson]

I don't know about Honeywell, but DEC/Digital PDP-10 definitely had
that feature, and I believe also the earlier PDP-6 from which the -10
derived. More precisely, most instructions (aside from some special
cases) have a register-memory aka 1.5-address format, containing an
actual (well, virtual on later models) 18-bit address, a 4-bit index
register number which if nonzero causes that register's contents to be
added, and a (single) indirect bit which if set causes the result to
be treated not as the address of the operand, but as the address of an
indirect word which in turn contains address, index, and indirect
bits, thus iterating possibly multiple times.
AIR the actual CPUs had a limit on _clocks_ for a single indirect
chain. But in those days hardware, especially core memory, (almost
always) had a fixed cycle time and latency, so this was effectively a
limit on levels of indirection. One popular emulator now available
(SIMH) does just hardcode a limit of 32.

I doubt C has ever been implemented on that architecture by setting
the relevant bit in pointers. If we have char *****p, then both **p
and ****p are legal expressions: the number of dereferences is
controlled by the program, not the data. C doesn't have a
"dereference as much as you can" operator.
Concur.


I *would* be surprised if there was such a modern computer.

I also -- but pleasantly surprised.

- formerly david.thompson1 || achar(64) || worldnet.att.net