← Back to context

Comment by InfamousRece

25 days ago

Will it compile Knuth’s test? https://en.wikipedia.org/wiki/Man_or_boy_test

4 comments

InfamousRece

Reply
chuckadams  25 days ago

That test is short enough to just paste it in here:

    begin
      real procedure A(k, x1, x2, x3, x4, x5);
      value k; integer k;
      real x1, x2, x3, x4, x5;
      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(1, A(10, 1, -1, -1, 1, 0))
    end

The whole "return by assigning to the function name" is one of my least favorite features of Pascal, which I suppose got it from Algol 60. Where I'm confused though is, what is the initial value of B in the call to A(k, B, x1, x2, x3, x4)? I'm guessing the pass-by-name semantics are coming into play, but I still can't figure out how to untie this knot.

  • svat  25 days ago

    Yeah that's one of the things the test was designed to catch: at that point, B is a reference, to the B that is being defined. Here's a C++ translation from https://oeis.org/A132343 that uses identity functions to make the types consistent:

        #include <functional>
    #include <iostream>
    using cf = std::function<int()>;
    int A(int k, cf x1, cf x2, cf x3, cf x4, cf x5)
    {
        int Aval;
        cf B = [&]()
        {
            int Bval;
            --k;
            Bval = Aval = A(k, B, x1, x2, x3, x4);
            return Bval;
        };
        if (k <= 0) Aval = x4() + x5(); else B();
        return Aval;
    }
    cf I(int n) { return [=](){ return n; }; }
    int main()
    {
        for (int n=0; n<10; ++n)
            std::cout << A(n, I(1), I(-1), I(-1), I(1), I(0)) << ", ";
        std::cout << std::endl;
    }

    So in the expression `A(k, B, x1, x2, x3, x4)`, the `B` there is not called, it simply refers to the local variable `B` (inside the function `A`), that was captured by the lambda (by reference): the same B variable that is currently being assigned.

    • chuckadams  24 days ago

      Thanks, that's a bit easier to trace: I think what broke my brain initially is that the x1-x5 parameters were declared as real, when they're apparently nullary functions returning a real. Brings to mind CAFs in Haskell. And all that that in 1960 when most things had less CPU power than the chip in my credit card.

fanf2  25 days ago

No, because Knuth’s test was for Algol 60 and Algol 68 is a very different programming language.