Title: Programmers’ Puzzles

Author: Bob Schmidt

Date: 04 January 2018 16:57:31 +00:00 or Thu, 04 January 2018 16:57:31 +00:00

Summary: Francis Glassborow reviews his last challenge and presents a new one.

Body: 

As any magazine editor (commercial or otherwise) knows, the number of responses to a competition is a small fraction of those who tried it. Readers often try competitions and even finish them but choose not to send in their solutions. I know how many of the New Scientist’s puzzles I solved – about 50% in the days when they ran a regular one – yet I never sent in one of my solutions. I also regularly tackle the Bridge competitions in the English Bridge Union magazine but never submit an answer. That behaviour makes me depressingly normal.

My first challenge required you to find some difference between C and C++ that could be exploited to switch the behaviour of a program. The difference could manifest at any stage from pre-processor through to run time behaviour.

I had in mind many little differences that might be exploited. In a way the more interesting ones are those that can trap programmers writing real code. A couple of quick examples:

The way in which the struct keyword introduces a name. C, for reasons that will seem strange to modern programmers, has a completely separate namespace (do not confuse with the C++ keyword namespace) for typenames created by the keywords struct and union. That is the reason that portable code (code that will necessarily behave the same way both as C and C++) couples a typedef with struct in the idiom:

  typedef struct A {
    // declarations
  } A;

A C compiler distinguishes between the plain name A and the elaborated name struct A.

Here is an example from James Holland.

If I understand Francis’s challenge correctly, what is needed is some source code that will produce two different outputs depending on whether the code was compiled by a C compiler or a C++ compiler. I assume using built-in compiler macros is not allowed! The solution must, therefore, rely on the code behaving differently depending on which compiler is used. My solution makes use of the fact that a C++ compiler enters the name of a struct in the scope in which it is declared. A C compiler does not do this. The following code [in Listing 1] makes use of this feature.

#include<stdio.h>
typedef char T;
int main()
{
  struct T {char c[2];};
  printf("I was compiled by a C");
  if (sizeof(T) == 2)
    printf("++");
  printf(" compiler.\n");
}
			

When evaluating sizeof(T), a C compiler will not see T as being the name of the struct as it is not within scope but will see the global typedef and conclude that sizeof(T) is 1. The body of the if statement will, therefore, not be executed. A C++ compiler, on the other hand, will see the locally declared struct and conclude that sizeof(T) is 2. The if statement can then be used to realise the different behaviour as required.

I will deal with James’ assumption about the allowability of built-in compiler macros later. However, there is a flaw in James’ code that means that it will often fail to work as expected because compilers are not prohibited from adding padding at the end of a struct so his test for equality with 2 will often fail because the compiler (usually for alignment purposes) may have added space at the end of T. Existing compilers will frequently return 4 or 8 for the sizeof T (the struct version).

  if( sizeof (T) == 2)

needs to be replaced by

  if (sizeof(T) > 1;

Apart from the flaw, the idea will work for any type, not just char.

Note that James avoided the flawed use of:

  sizeof (char) == sizeof ‘a’;

as a test. This will usually work because character literals are of type int in C and char in C++. However, some compilers (largely for DSPs) use the same storage allocation for int and char types.

The other aspect is that James assumed that built-in compiler macros were not allowed. In these challenges, anything not explicitly excluded is allowed. Every C++ compiler is supposed to have __cplusplus as a built-in macro. This is absolutely essential so that code can test which version of C++ is in use. I leave it to the reader to surf the net to discover what values are required for conforming C++ compilers. Non-conforming C++ compilers will normally provide a value for __cplusplus but one that is not one of the standard values.

Hubert Matthews exploited this in the first of offering in his submission:

Francis threw out a challenge for pieces of code that produce different results when compiled as C or as C++.  Here are two: one cheaty [Listing 2] and one sneaky [Listing 3].

// prints "C" when compiled as C and "C++" 
// when compiled as C++

include <stdio.h>
int main()
{
   puts("C"
#ifdef __cplusplus
   "++"
#endif
 );
}
			

// prints "12" when compiled as C 
// and "13" when compiled as C++

#include <stdio.h>
int main()
{
  auto x = 5.6, y = 7.5;
  printf("%d\n", (int) (x+y));
}
			

I do not think that is a cheat. It shows a grasp of what is provided by the C++ Standard but I think he did not fully exploit the potential of the pre-processor to bizarrely alter the behaviour of code.

Using __cplusplus gives us all kinds of potential. Instead of conditionally adding a couple of characters at compile time, we can define complicated macros. We even have the ability to redefine a C++ keyword that is not also a C keyword for when our code is being compiled as C, without stepping into undefined territory. For example something such as:

  #ifndef __cplusplus
  #define try struct A
  #endif

will work if we can design code that is a try block in C++ but a struct definition in C. That is just an idea for the reader to think about (replacing keywords, not specifically replacing try).

Hubert’s second offering is interesting.

I have not been able to check that auto x without an explicit int specifier is allowed in current versions of C (post the abolition of ‘implicit int’). GCC in C mode gives me a warning that auto x defaults to auto int x, which is sane even if it is not required that strictly conforming C makes the int explicit.

I leave it as an exercise for the reader to work out why this code produces different output. (Hint, you need C++11 or later compiler to reliably see the difference).

My choice of winner of this challenge is Hubert because his use of auto surprised me and highlighted another potential trap for the unwary C programmer accidentally using a C++ compiler. Of course, no reasonable C programmer uses auto and I suspect quite a number do not even know it is a C keyword.

Challenge 2

In the early days of computing, a frequent task was to write code with a missing instruction (such tests were even frequently set in Computer Science A level papers of the early 1980s).

I think it is time to revive this kind of mind exercise. As an example to get you on track, suppose that you have no + available, you could write

  template <typename T> 
  T add (T a, T b){
    T result = -b);
    return  a –result;
  };

which will work for any type that supports minus as an inverse operation to plus. You would then need to specialise for other types such as std::string. That would be an interesting challenge in itself but it is not what I am going to set you.

The challenge is to write code that will assign the sum of two integer values, a and b and store the result in c without using the = symbol in your code. There are several simple solutions. Bonus points for multiple solutions.

You are restricted to C and C++ because those are the languages that I am familiar with (well you could try it in Forth, Prolog or Snobol?)

Notes: 

More fields may be available via dynamicdata ..