How many levels of pointers can you have?

[madhawi]

This question is occur in interview. Please help me.

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

Malcolm McLean wrote:

"Harald van D?k" <tr*****@gmail.comwrote in message

>Chris Hills wrote:

>>In article <46*********************@news2.asahi-net.or.jp>, Neil Booth
<dev@null.?.invalidwrites
Chris Hills wrote:

That is what I said.
95% of the C compilers aren't fully C99 conforming anyway.
AFAIK there are only about 6 compilers in the world that are fully
>C99 conforming. The other 100 odd are not to a greater or lesser
>extent.

By that definition there isn't even one.

I think there are about 6 fully conforming C99 compilers

You give me a C compiler, I'll give you conforming code it won't
compile.

Which proves what?

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.

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.

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.

[Richard Tobin]

In article <f4**********@news3.zwoll1.ov.home.nl>,
Harald van Dijk <tr*****@gmail.comwrote:

>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
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Flash Gordon]

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

Chris Hills wrote:

>In article <46*********************@news2.asahi-net.or.jp>, Neil Booth
<dev@null.?.invalidwrites

>>Chris Hills wrote:

That is what I said.
95% of the C compilers aren't fully C99 conforming anyway.
AFAIK there are only about 6 compilers in the world that are fully
C99 conforming. The other 100 odd are not to a greater or lesser extent.
By that definition there isn't even one.

I think there are about 6 fully conforming C99 compilers

>>You give me a C compiler, I'll give you conforming code it won't compile.

Which proves what?

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

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

Richard Tobin wrote:

In article <f4**********@news3.zwoll1.ov.home.nl>,
Harald van Dijk <tr*****@gmail.comwrote:

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

Yes, thank you.

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

Flash Gordon wrote:

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

>Chris Hills wrote:

>>In article <46*********************@news2.asahi-net.or.jp>, Neil Booth
<dev@null.?.invalidwrites
Chris Hills wrote:

That is what I said.
95% of the C compilers aren't fully C99 conforming anyway.
AFAIK there are only about 6 compilers in the world that are fully
C99 conforming. The other 100 odd are not to a greater or lesser
extent.
By that definition there isn't even one.
I think there are about 6 fully conforming C99 compilers

You give me a C compiler, I'll give you conforming code it won't
compile.
Which proves what?

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.

Right.

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.

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.

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.

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]

Harald van D?k wrote:

>

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

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net

--
Posted via a free Usenet account from http://www.teranews.com

[Chris Hills]

In article <_s******************************@bt.com>, Malcolm McLean
<re*******@btinternet.comwrites

>"Harald van D?k" <tr*****@gmail.comwrote in message

>Chris Hills wrote:

>>In article <46*********************@news2.asahi-net.or.jp>, Neil Booth
<dev@null.?.invalidwrites
Chris Hills wrote:

That is what I said.
95% of the C compilers aren't fully C99 conforming anyway.
AFAIK there are only about 6 compilers in the world that are fully
>C99 conforming. The other 100 odd are not to a greater or lesser extent.

By that definition there isn't even one.

I think there are about 6 fully conforming C99 compilers

You give me a C compiler, I'll give you conforming code it won't compile.

Which proves what?

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.

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 Hills Staffs England /\/\/\/\/
/\/\/ ch***@phaedsys.org www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

[Chris Dollin]

CBFalconer wrote:

Harald van D?k wrote:

>>

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

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

--
Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

[David Thompson]

On 6 Jun 2007 22:06:35 GMT, ri*****@cogsci.ed.ac.uk (Richard Tobin)
wrote:

In article <f4***********@smof.fiawol.org>,
John Cochran <jd*@smof.fiawol.orgwrote:

I have a vague memory from many years back about what I believe was a
Honeywell mainframe (36 bit words, 18 bit addressing). One of the features
of this beast was indirect addressing where if a bit was set in a word
when it was accessed, it indicated that the word should be used as an
address pointing to where the actual parameter was. And if *that* had that
magic bit set, then it was also an address pointing to where the actual
parameter was. This indirection could in theory go quite a distance. However

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.

the computer would throw an exception if too many levels of indirection
were being used. I don't remember how many levels this was.

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.

But given that the above feature could be used to implement pointer to pointer
to ..... in a fairly efficient C implementation. I can see a "must be able
to do at least X levels of indirection" requirement based upon the limits
of the computers with this capability.

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.

Now this is pure speculation, but I wouldn't be surprised if there exists
a modern computer that has this indirect capability and has a limit on
how many levels of indirection it's willing to perform without causing
an exception.

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

I also -- but pleasantly surprised. :-)

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