C++ Puzzle

Discussion in 'C++' started by doublemaster007@gmail.com, Nov 22, 2008.

  1. Guest

    Can we have Puzzle thread here?? If any one has a interesting C++
    question which helps to understand c++ better or makes interview
    easier to face can post here..
     
    , Nov 22, 2008
    #1
    1. Advertising

  2. Daniel T. Guest

    On Nov 22, 6:25 am, ""
    <> wrote:
    > Can we have Puzzle thread here?? If any one has a interesting C++
    > question which helps to understand c++ better or makes interview
    > easier to face can post here..


    I suspect that most of the people here know the answer to this puzzle,
    but I'm continually surprised at how many professional programmers
    that I meet don't:

    (I've turned a basic fact about C++ into a puzzle question below... I
    know the answer. :)

    In C++ a basic rule is that the compiler destroys auto variables in
    the opposite order from which they were constructed. Given this, when
    a destructor is called, how does the system know in what order to
    destroy the member-variables?
     
    Daniel T., Nov 22, 2008
    #2
    1. Advertising

  3. Daniel T. wrote:
    >
    > (I've turned a basic fact about C++ into a puzzle question below... I
    > know the answer. :)
    >
    > In C++ a basic rule is that the compiler destroys auto variables in
    > the opposite order from which they were constructed. Given this, when
    > a destructor is called, how does the system know in what order to
    > destroy the member-variables?
    >


    While the answer to the above question is indeed just a basic fact about
    C++ (not really a puzzle), I still don't understand what does it have to
    do with automatic variables and why you even mention them there.

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 22, 2008
    #3
  4. wrote:
    > Can we have Puzzle thread here?? If any one has a interesting C++
    > question which helps to understand c++ better or makes interview
    > easier to face can post here..


    This is not a question which really helps understanding C++ better nor
    is a good job interview question (well, not unless you are applying for
    a job which involves writing a compiler), but I think it's interesting
    nevertheless:

    C++ is very hard to parse because its syntax is not a so-called
    context-free grammar. Give an example (one full sentence, ie. a full
    expression ending in a semi-colon) of valid code which cannot be
    unambiguously tokenized properly without knowing the environment in
    which the line of code appears (ie. everything else in the same
    compilation unit). In other words, it would be possible to tokenize the
    sentence in at least two completely different ways, and both ways could
    be valid C++ code (if in the proper environment).

    (Note that tokenizing a sentence doesn't require understanding the
    semantics of the expression, ie. it's not necessary to know eg. if some
    type name has been declared earlier or not. Tokenizing simply means that
    the sentence is divided into its constituent tokens, each token having a
    well-defined type, eg. "identifier", "unary operator", "binary
    operator", "opening parenthesis", etc.)

    (And btw, googling is cheating. ;) )
     
    Juha Nieminen, Nov 22, 2008
    #4
  5. Guest

    Re: The following code causes an infinite loop. Can you spot theproblem and explain why?

    class Base
    {
    public:
    Base() {}
    virtual void func() { /* do something */ }
    };

    class Derived : public Base
    {
    public:
    Derived() {}
    virtual void func()
    {
    Base:func();
    /* do something else */
    }
    };

    int main()
    {
    Derived d;
    d.func(); // Never returns!
    }
     
    , Nov 23, 2008
    #5
  6. Guest

    Re: The following code causes an infinite loop. Can you spot theproblem and explain why?

    For each new puzzle..pls change the subject..
     
    , Nov 23, 2008
    #6
  7. Guest

    ANS: The following code causes an infinite loop. Can you spot theproblem and explain why?

    On Nov 23, 10:34 am, ""
    <> wrote:
    > For each new puzzle..pls change the subject..


    Ans:Base:func(); (only single colon) causes the infinet loop. since
    single colon acts as label . hence derived func will be called
     
    , Nov 23, 2008
    #7
  8. onLINES Guest

    Re: The following code causes an infinite loop. Can you spot theproblem and explain why?

    On Nov 23, 12:33 am, ""
    <> wrote:
    > class Base
    > {
    > public:
    >   Base() {}
    >   virtual void func() { /* do something */ }
    >
    > };
    >
    > class Derived : public Base
    > {
    > public:
    >   Derived() {}
    >   virtual void func()
    >   {
    >     Base:func();
    >     /* do something else */
    >   }
    >
    > };
    >
    > int main()
    > {
    >   Derived d;
    >   d.func();  // Never returns!
    >
    > }
    >
    >


    Yes it does. It's syntactically incorrect (moreso, hard to understand)
    as to why you'd have virtual function within the base class, when the
    base class has the same name. The compiler (bad one) would not know
    what to do since both are virtual, and both contain the same name
    along with method parameters.

    However, it does return. And it exists successfully.

    Program execution is as follows.

    Derived Constructor is called, return to last calling point : Main
    Call constructed class, d. Jumps into class Derived : Name is the same
    as base class
    Goes into the called method within Derived.
    Calls Base class
    Returns to last calling point : Derived class
    Returns to last calling point : Main
    Exit
     
    onLINES, Nov 23, 2008
    #8
  9. James Kanze Guest

    On Nov 22, 8:58 pm, Juha Nieminen <> wrote:
    > wrote:
    > > Can we have Puzzle thread here?? If any one has a
    > > interesting C++ question which helps to understand c++
    > > better or makes interview easier to face can post here..


    > This is not a question which really helps understanding C++
    > better nor is a good job interview question (well, not unless
    > you are applying for a job which involves writing a compiler),
    > but I think it's interesting nevertheless:


    > C++ is very hard to parse because its syntax is not a
    > so-called context-free grammar. Give an example (one full
    > sentence, ie. a full expression ending in a semi-colon) of
    > valid code which cannot be unambiguously tokenized properly
    > without knowing the environment in which the line of code
    > appears (ie. everything else in the same compilation unit). In
    > other words, it would be possible to tokenize the sentence in
    > at least two completely different ways, and both ways could be
    > valid C++ code (if in the proper environment).


    > (Note that tokenizing a sentence doesn't require understanding
    > the semantics of the expression, ie. it's not necessary to
    > know eg. if some type name has been declared earlier or not.
    > Tokenizing simply means that the sentence is divided into its
    > constituent tokens, each token having a well-defined type, eg.
    > "identifier", "unary operator", "binary operator", "opening
    > parenthesis", etc.)


    The problem with that is that the question is ambiguous: what do
    you mean by a token? (As for your "well-defined type", that's a
    meaningless statement until you know how the compiler internals
    are implemented.)

    Formally, C++ defines tokens so that you can always "tokenize"
    with at most one character look-ahead (is the next character
    part of this token, or not), and no context. Practically,
    internally, it's impossible to parse C++ if you don't separate
    symbols into names of types, names of templates, and other, and
    I imagine that most compilers treat these as separate tokens.
    Similarly, it's probably advantageous to distinguish between the
    > which closes a template and the > which is the operator less

    than; with the new standard, I suspect that the simplest
    implementation would also distinguish between a >> which closes
    two templates (which is formally a single token which is then
    remapped to two---but if you know that the context would allow
    the remapping, you could do it immediately in the tokenizing
    phase) and the right shift operator.

    So formally, there aren't any, but internally, there could be,
    and in fact, probably are. (In practice, I would be very
    surprised if there were any compilers which didn't use context
    to return different token types for type names, template names
    and other symbols; as long as >> cannot be used to close two
    templates, I expect that that's the only case in most compilers,
    so presumably, that's what you were looking for.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 23, 2008
    #9
  10. James Kanze Guest

    Re: The following code causes an infinite loop. Can you spot theproblem and explain why?

    On Nov 23, 6:42 am, onLINES <> wrote:
    > On Nov 23, 12:33 am, ""
    > <> wrote:
    > > class Base
    > > {
    > > public:
    > >   Base() {}
    > >   virtual void func() { /* do something */ }
    > > };


    > > class Derived : public Base
    > > {
    > > public:
    > >   Derived() {}
    > >   virtual void func()
    > >   {
    > >     Base:func();
    > >     /* do something else */
    > >   }
    > > };


    > > int main()
    > > {
    > >   Derived d;
    > >   d.func();  // Never returns!
    > > }


    > Yes it does.


    No it doesn't. It terminates with stack overflow (formally,
    undefined behavior, but a core dump or the equivalent on most
    general purpose machines).

    > It's syntactically incorrect (moreso, hard to understand) as
    > to why you'd have virtual function within the base class, when
    > the base class has the same name.


    I'm having problems parsing that statement. The base class has
    the same name as what? But the program is definitely
    syntactically correct.

    > The compiler (bad one) would not know what to do since both
    > are virtual, and both contain the same name along with method
    > parameters.


    If you're talking about the function func() (which I suppose
    because that's the only thing which has two declarations), his
    code is a perfectly classical example of how to implement a
    polymorphic class in C++. He defines a virtual function in the
    base class, and overrides it in the derived class.

    > However, it does return. And it exists successfully.


    Did you actually try it? (A good compiler will warn about an
    unreferenced label, but the language itself doesn't require
    labels to be referenced.)

    > Program execution is as follows.


    > Derived Constructor is called, return to last calling point :


    Somewhere before the body of the constructor of Derived is
    entered, the constructor of Base will have been called. But in
    the end, yes, the object gets constructed, and we return in
    sequence.

    > Main
    > Call constructed class, d.


    You call a function, not a class. Next, we call Derived::func.

    > Jumps into class Derived : Name is the same as base class


    > Goes into the called method within Derived.
    > Calls Base class


    Where does it do that? His code never calls Base::func.
    Derived::func calls itself recursively. (Note that for
    Derived::func to call Base::func, he would have to have written
    Base::func, and not Base:func.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 23, 2008
    #10
  11. James Kanze wrote:
    > So formally, there aren't any, but internally, there could be,
    > and in fact, probably are. (In practice, I would be very
    > surprised if there were any compilers which didn't use context
    > to return different token types for type names, template names
    > and other symbols; as long as >> cannot be used to close two
    > templates, I expect that that's the only case in most compilers,
    > so presumably, that's what you were looking for.)


    Actually I was looking for an expression like:

    a < b, c > d;

    That can have two completely different meanings depending on what 'a'
    is. In other words, it can be tokenized as:

    1) Two comma-separated expressions, the first one being a less-than
    comparison between two identifiers, and the second one being a
    greater-than comparison between two identifiers.

    2) A template class instantiation, where the instance name is 'd' and
    the name of the class is 'a'. The class takes two template parameters,
    and is given 'b' and 'c' as them.

    If a parsing tree is built of these two cases, they would look
    completely different (in both geometry and contents). One example of a
    major difference here is that the '<' symbol is either a binary operator
    (less than) or an opening delimiter symbol (opening angle bracket)
    depending on the context. It's impossible to tell from this line of code
    alone which one is it. (For example if some editor software wanted to
    color template instantiations differently from comparison expressions,
    it would be impossible for it to do so without possible error in this
    case, unless it contains a full C++ parser and it uses it to understand
    the proper meaning of that sentence.)
     
    Juha Nieminen, Nov 23, 2008
    #11
  12. Puzzle for the newbies (trivial for more experienced programmers, but
    might be a bit challenging for a newbie):

    Write a "hello world" program which does not use any preprocessor
    # directives.
     
    Juha Nieminen, Nov 23, 2008
    #12
  13. Daniel T. Guest

    On Nov 22, 11:27 am, Andrey Tarasevich <>
    wrote:
    > Daniel T. wrote:
    >
    > > (I've turned a basic fact about C++ into a puzzle question below... I
    > > know the answer. :)

    >
    > > In C++ a basic rule is that the compiler destroys auto variables in
    > > the opposite order from which they were constructed. Given this, when
    > > a destructor is called, how does the system know in what order to
    > > destroy the member-variables?

    >
    > While the answer to the above question is indeed just a basic fact about
    > C++ (not really a puzzle), I still don't understand what does it have to
    > do with automatic variables and why you even mention them there.


    Because non-automatic variables are not destroyed automatically. Since
    they are explicitly destroyed by the programmer, they can be destroyed
    in any order he or she desires.
     
    Daniel T., Nov 23, 2008
    #13
  14. Daniel T. Guest

    On Nov 22, 2:28 pm, (blargg) wrote:
    > Daniel T. wrote:
    >
    > [...]
    >
    > > In C++ a basic rule is that the compiler destroys auto variables in
    > > the opposite order from which they were constructed. Given this, when
    > > a destructor is called, how does the system know in what order to
    > > destroy the member-variables?

    >
    > Answer: the compiler knows by parsing the source code, in particular the
    > definition of the class. The system knows by whatever
    > implementation-defined way the compiler tells it (most likely, via machine
    > code).
    >
    > (sorry, not a very good "puzzle" question IMO)


    I thought of it because several of our recent hires thought the member-
    variables were destroyed in the opposite order in which they were
    initialized in the constructor.
     
    Daniel T., Nov 23, 2008
    #14
  15. Daniel T. wrote:
    >
    > Because non-automatic variables are not destroyed automatically.


    Incorrect. For example, static objects are destroyed automatically. And
    static objects are non-automatic.

    > Since
    > they are explicitly destroyed by the programmer, they can be destroyed
    > in any order he or she desires.


    Apparently you got lost in your own puzzle. Read it again. Your puzzle
    was about the order in which [non-static] member subobjects are
    destroyed (you called them "member-variables", remember?). The order of
    member subobject destruction is aways fixed, it is determined by the
    order in which they are declared. This applies regardless of whether the
    owner object is static, automatic or dynamically allocated. As I said
    before, this has absolutely nothing to do with "automatic variables".

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 23, 2008
    #15
  16. Daniel T. wrote:
    >
    > I thought of it because several of our recent hires thought the member-
    > variables were destroyed in the opposite order in which they were
    > initialized in the constructor.
    >


    The funny part, of course, is that this is an _the_ _correct_ _answer_.
    Member subobjects are always constructed in the order of their
    declaration. And member subobjects are always destructed in the reverse
    order of their declaration. So yes, they are destroyed in the reverse
    order of their initialization.

    On top of that, as I said before, this all has absolutely noting to do
    with automatic variables...

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 23, 2008
    #16
  17. Christian Hackl wrote:
    > Juha Nieminen ha scritto:
    >
    >> Write a "hello world" program which does not use any preprocessor
    >> # directives.

    >
    > Do you mean this?
    >
    > ??=include <iostream>


    No. I said no preprocessor directives. #include is one of them, no
    matter how you encode it.
     
    Juha Nieminen, Nov 24, 2008
    #17
  18. Guest

    On Nov 24, 4:37 am, Christian Hackl <> wrote:
    > Juha Nieminen ha scritto:
    >
    > >   Write a "hello world" program which does not use any preprocessor
    > > # directives.

    >
    > Do you mean this?
    >
    > ??=include <iostream>
    >
    > int main() { std::cout << "Hello world\n"; }
    >
    > --
    > Christian Hackl
    >


    Where is tha answer????
     
    , Nov 24, 2008
    #18
  19. wrote:
    > Where is tha answer????


    Hmm... The answer is so plain and non-interesting that it will probably
    disappoint you. Let me give you a little hint :)

    As you probably know, the '#include' directive simply _inserts_ the
    content of some other file into the current translation unit. Now, in
    order to write a simple Hello-World program, we'd probably have to do
    '#include <stdio.h>'. Imagine that instead of doing '#include <stdio.h>'
    we simply take the content of 'stdio.h' and copy-paste it into the
    source code of our Hello-World program. Now we don't have to do
    '#include <stdio.h>' anymore! The text of 'stdio.h' might in turn have
    some other #include-s, which we can take care of in exactly the same
    fashion. We basically do manually what preprocessor normally does for us
    in response to '#include' directives. That way we'll eventually arrive
    at the Hello-World program which does use any '#include' directives. Now
    let's just get rid of what we don't need... Get it?

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 24, 2008
    #19
  20. James Kanze Guest

    On Nov 23, 4:28 pm, Juha Nieminen <> wrote:
    > James Kanze wrote:
    > > So formally, there aren't any, but internally, there could
    > > be, and in fact, probably are. (In practice, I would be
    > > very surprised if there were any compilers which didn't use
    > > context to return different token types for type names,
    > > template names and other symbols; as long as >> cannot be
    > > used to close two templates, I expect that that's the only
    > > case in most compilers, so presumably, that's what you were
    > > looking for.)


    > Actually I was looking for an expression like:


    > a < b, c > d;


    > That can have two completely different meanings depending on
    > what 'a' is. In other words, it can be tokenized as:


    > 1) Two comma-separated expressions, the first one being a
    > less-than comparison between two identifiers, and the second
    > one being a greater-than comparison between two identifiers.


    > 2) A template class instantiation, where the instance name is
    > 'd' and the name of the class is 'a'. The class takes two
    > template parameters, and is given 'b' and 'c' as them.


    > If a parsing tree is built of these two cases, they would look
    > completely different (in both geometry and contents).


    Certainly. And it's an interesting case. But according to the
    standard < and > are just one token; there aren't two different
    tokens with the same symbol. And in a compiler, I don't think
    I'd bother returning two different tokens from the tokenizer; it
    would be too complex. What I would do is look up the symbols
    (a, b, c and d) in the symbol table, and return a different
    token for the name of a template or for a typename than for a
    normal symbol. In this case, the productions which get matched
    will depend on whether a is the name of a template or not; they
    will not depend on a different token being returned for < and >.
    I *think* that this is how I would handle >> as well; I'd define
    a special production which contained two open templates, and
    then accepted a >> token. Of course, this results in a
    shift-reduce error which must be resolved in favor of reduce,
    rather than shift, so maybe not. I'll let you know for sure
    once I've actually written a C++ compiler.

    > One example of a major difference here is that the '<' symbol
    > is either a binary operator (less than) or an opening
    > delimiter symbol (opening angle bracket) depending on the
    > context.


    According to the standard (and according to the way I think I
    would implement a compiler), it's the same token. Certainly,
    the semantic signification of the token, and how you build your
    parse tree, does depend on context, but not (necessarily) the
    token returned by the parser.

    > It's impossible to tell from this line of code alone which one
    > is it. (For example if some editor software wanted to color
    > template instantiations differently from comparison
    > expressions, it would be impossible for it to do so without
    > possible error in this case, unless it contains a full C++
    > parser and it uses it to understand the proper meaning of that
    > sentence.)


    It would probably also have to be able to resolve all of the
    includes. Which could be very difficult, requiring it to know
    how the compiler looks up its includes, and what options will be
    passed to the compiler. The preprocessor is a source of many
    problems for various tool kits.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 24, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Earl Teigrob
    Replies:
    3
    Views:
    6,652
    Nedu N
    Aug 6, 2003
  2. dwa

    Design Puzzle!

    dwa, Jun 10, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    370
    Cowboy \(Gregory A. Beamer\) [MVP]
    Jun 10, 2004
  3. Shankara Narayanan

    Booking puzzle....

    Shankara Narayanan, Jun 17, 2004, in forum: ASP .Net
    Replies:
    20
    Views:
    933
    bredal Jensen
    Jun 30, 2004
  4. VB Programmer
    Replies:
    2
    Views:
    430
    Alan Lambert
    Nov 4, 2004
  5. G. Stewart

    regex puzzle!

    G. Stewart, Nov 23, 2004, in forum: ASP .Net
    Replies:
    8
    Views:
    518
    G. Stewart
    Nov 25, 2004
Loading...

Share This Page