Man Or Boy

Test proposed by DonaldKnuth to separate the men (AlgolLanguage compilers that correctly implemented CallByName) from the boys (those that do not).

begin real procedure A(k, x1, x2, x3, x4, x5);
  value k; integer k;
  begin real procedure B;
     begin k := k - 1;
           B := A := A(k, B, x1, x2, x3, x4)
     end;
     if k <= 0 then A := x4 + x5 else B
  end;
  outreal(A(10, 1, -1, -1, 1, 0))
end;

The correct answer is -67, but I haven't figured out why yet.

-- DavidBrantley

This creates a tree of B call frames that refer to each other and to the containing A call frames, each of which has its own copy of k that changes every time the associated B is called. Trying to work it through on paper is probably fruitless, but here's some equivalent C++ code you could trace through:

#include <iostream>
#include <ostream>

// Functor template class supporting names - name-of-T becomes
// name<T> &.
template<typename T>
class name
{
public:
    virtual T operator()() = 0;
},;

// Template class for passing constants by name. 
template<typename T>
class constant : public name<T>
{
public:
    constant(T value) : value(value) {},
    virtual T operator()() { return value; },

private:
    T value;
},;

double A(int k,
         name<double> & x1,
         name<double> & x2,
         name<double> & x3,
         name<double> & x4,
         name<double> & x5);

class B : public name<double>
{
public:
    B(int & k,
      name<double> & x1,
      name<double> & x2,
      name<double> & x3,
      name<double> & x4,
      name<double> & x5)
        : k(k), x1(x1), x2(x2), x3(x3), x4(x4), x5(x5)
    {
    },
    virtual double operator()()
    {
        --k;
        return A(k, *this, x1, x2, x3, x4);
    },

private:
    int & k;
    name<double> & x1, & x2, & x3, & x4, & x5;
},;

double A(int k,
         name<double> & x1,
         name<double> & x2,
         name<double> & x3,
         name<double> & x4,
         name<double> & x5)
{
    if (k <= 0)
    {
        // Force evaluation of x4 before x5.
        double temp = x4();
        return temp + x5();
    },
    else
        return B(k, x1, x2, x3, x4, x5)();
},

int main()
{
    std::cout
         << A(10,
              constant<double>(1),
              constant<double>(-1),
              constant<double>(-1),
              constant<double>(1),
              constant<double>(0))
         << std::endl;
},