Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is my non-recursive sqrt function recursive?

I have the following C++ test program called test.cpp:

#include <cmath>
#include <iostream>

double sqrt(double d) { return std::sqrt(d); }

int main()
{
    std::cout << "sqrt(4): " << sqrt(4) << std::endl;
}

This is some pretty contrived code, and as you might have guessed I'm just trying to do an exercise out of Stroustrup. He declared double sqrt(double), and wants the reader to define it.

I compiled the above code using g++ 4.8 (from the MINGW release of Qt 5.1):

C:\Windows\Temp>g++ -o test.exe -g test.cpp

When I ran the resulting executable, Windows 7 said "test.exe has stopped working".

To see what went wrong, I ran test.exe in the GNU debugger. Debugger commands and output:

C:\Windows\Temp>gdb -q test.exe
Reading symbols from C:\Windows\Temp\test.exe...done.
(gdb) b main
Breakpoint 1 at 0x401625: file test.cpp, line 8.
(gdb) run
Starting program: C:\Windows\Temp\test.exe
[New Thread 12080.0x2ba0]

Breakpoint 1, main () at test.cpp:8
8           std::cout << "sqrt(4): " << sqrt(4) << std::endl;
(gdb) s
sqrt (d=4) at test.cpp:4
4       double sqrt(double d) { return std::sqrt(d); }
(gdb) s
sqrt (d=4) at test.cpp:4
4       double sqrt(double d) { return std::sqrt(d); }
(gdb) s
sqrt (d=4) at test.cpp:4
4       double sqrt(double d) { return std::sqrt(d); }
(gdb) s
sqrt (d=4) at test.cpp:4
4       double sqrt(double d) { return std::sqrt(d); }
(gdb) q
A debugging session is active.

        Inferior 1 [process 12080] will be killed.

Quit anyway? (y or n) y

C:\Windows\Temp>

From the behavior and warning, I infer that std::sqrt must be calling sqrt from the global namespace -- which causes my function to be repeatedly invoked.

It would be easy enough to work around the unwanted recursion by changing the name of my sqrt function, or by putting it inside a namespace. But I would like to understand why std::sqrt is implemented in such a way that ::sqrt is called. I thought the whole point of the std namespace was to prevent name clashes with unqualified names in user code.

I took a peek at the source code for the GNU implementation of <cmath>. However, I lost the trail after following a few #includes in the chain. Maybe you can make more sense of it:

00052 #include <math.h>
00053 
00054 // Get rid of those macros defined in <math.h> in lieu of real functions.
....
00076 #undef sqrt
....
00081 namespace std
00082 {
....
00393   using ::sqrt;
00394 
00395   inline float
00396   sqrt(float __x)
00397   { return __builtin_sqrtf(__x); }
00398 
00399   inline long double
00400   sqrt(long double __x)
00401   { return __builtin_sqrtl(__x); }
00402 
00403   template<typename _Tp>
00404     inline typename __enable_if<double, __is_integer<_Tp>::_M_type>::_M_type
00405     sqrt(_Tp __x)
00406     { return __builtin_sqrt(__x); }
....
00437 }

Incidentally, this is not just a GNU puzzle. Compiling with the Visual C++ compiler instead of g++ yields the following warning:

C:\Windows\Temp>cl /nologo /EHsc test.cpp
test.cpp
c:\windows\temp\test.cpp(4) : warning C4717: 'sqrt' : recursive on all control
paths, function will cause runtime stack overflow

I guess that makes this a fair question to ask on StackOverflow. :)

Running the resulting executable leads to the expected outcome: "test.exe has stopped working".

like image 214
Spacewaster Avatar asked Oct 31 '13 01:10

Spacewaster


2 Answers

The problem is that the functions inherited from the C standard library like, e.g., the <cmath> functions are somewhat funny beasts: they are made to look as if they live in namespace std but really they are extern "C" functions living in the global namespace. Basically calling std::sqrt(x) effectively calls ::sqrt(x) which happens to be the function you just defined!

I haven't checked what the C++ standard says about these names in the global namespace but I'd be fairly certain that it classifies them as reserved names. That is, you'd better not define ::sqrt in any shape or form. Define the function in a suitable namespace and you'll be fine.

OK, I checked. The relevant clause is 17.3.24 [defns.reserved.function]:

reserved function

a function, specified as part of the C++ standard library, that must be defined by the implementation [ Note: If a C++ program provides a definition for any reserved function, the results are undefined. —end note ]

... and 17.6.4.3.3 [extern.names] paragraph 3 and 4:

Each name from the Standard C library declared with external linkage is reserved to the implementation for use as a name with extern "C" linkage, both in namespace std and in the global namespace.

Each function signature from the Standard C library declared with external linkage is reserved to the implementation for use as a function signature with both extern "C" and extern "C++" linkage, or as a name of namespace scope in the global namespace.

like image 196
Dietmar Kühl Avatar answered Nov 20 '22 14:11

Dietmar Kühl


17.6.4.3.3/2 Each global function signature declared with external linkage in a header is reserved to the implementation to designate that function signature with external linkage.
17.6.4.3.3/3 Each name from the Standard C library declared with external linkage is reserved to the implementation for use as a name with extern "C" linkage, both in namespace std and in the global namespace.
17.6.4.3.3/4 Each function signature from the Standard C library declared with external linkage is reserved to the implementation for use as a function signature with both extern "C" and extern "C++" linkage, or as a name of namespace scope in the global namespace.

like image 33
Igor Tandetnik Avatar answered Nov 20 '22 13:11

Igor Tandetnik