Man or boy

[vak]

Алгол наш кое-как дышит, но главный тест пока не проходит. Циклится где-то на вызовах-возвратах функций.

Много лет назад один клёвый чувак написал хитрый тест для Алгола 60. Да вы все его знаете: это знаменитый Дональд Кнут. Тест называется "man or boy". По нашему можно перевести как "мужик или хлюпик". Только по настоящему серьёзный компилятор Алгола-60 может выполнить этот код правильно. Разобраться как работает этот тест нелегко, но познавательно. На Розетте есть большая подборка вариантов этого теста на разных языках программирования. Я здесь покажу на языке Ди.

Язык Ди сам по себе любопытная вещь, но для нас здесь он просто чуть более продвинутый Си. Вот man or boy на Ди:

import core.stdc.stdio;

int A(int k, const lazy int x1, const lazy int x2, const lazy int x3,
      const lazy int x4, const lazy int x5) 
{
    int B()
    {
        k--;
        return A(k, B(), x1, x2, x3, x4);
    }
    return k <= 0 ? x4 + x5 : B();
}

void main()
{
    printf("%d\n", A(10, 1, -1, -1, 1, 0));
}

Имеется функция A() с аргументами, большинство из которых передаются в "ленивом" виде. Имеется внутренняя функция B() без параметров. Функция A иногда вызывает B. Функция B всегда вызывает A. Тест должен напечатать значение -67.

Как всё это выполняется? Добавим отладочную печать и запустим:

import core.stdc.stdio;

int A(int k, const lazy int x1, const lazy int x2, const lazy int x3,
      const lazy int x4, const lazy int x5)
{
    int B()
    {
        printf("B called, k = %d\n", k);
        k--;
        printf("k := %d\n", k);
        int result = A(k, B(), x1, x2, x3, x4);
        printf("B returns %d\n", result);
        return result;
    }
    printf("A called, k = %d\n", k);
    int result = k <= 0 ? x4 + x5 : B();
    printf("A returns %d\n", result);
    return result;
}

void main()
{
    printf("%d\n", A(10, 1, -1, -1, 1, 0));
}

Результат смотрите здесь: gist.github.com/sergev/938c8c35ede86050f9e83c243295baad

Нехило, верно? Сложно на таком тесте отлаживаться. Чтобы укоротить, можно уменьшать значение первого аргумента при вызове A() с 10 до двух. Тогда тест окажется заметно короче:

A called, k = 2
B called, k = 2
k := 1
A called, k = 1
B called, k = 1
k := 0
A called, k = 0
A returns -2
B returns -2
A returns -2
B returns -2
A returns -2
-2

Вот этого нам и надо добиться на симуляторе Алгола X1.

Comments

[juan_gandhi]

А мне что-то непонятно, где тут такая уж сложность, и какова роль лишних параметров... и что это вообще за язык. Это ж не Алгол 60.

[vak]

И с тех пор 50 лет никому непонятно. 😀
Не думаю, что на Алголе понятнее станет.

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;
        A := if k < 1 then x4 + x5 else B;
    end;
    print(A(10, 1.0, -1.0, -1.0, 1.0, 0.0));
end

[vak]

Кстати, на Скале этот тест тоже имеется.

def A(in_k: Int, x1: =>Int, x2: =>Int, x3: =>Int, x4: =>Int, x5: =>Int): Int = {
    var k = in_k
    def B: Int = {
        k = k-1
        A(k, B, x1, x2, x3, x4)
    }
    if (k<=0) x4+x5 else B
}
println(A(10, 1, -1, -1, 1, 0))

[spamsink]

Роль лишних параметров в том, чтобы при окончательном вычислении суммы x4 + x5 в выражении участвовали лямбды, созданные во многих разных контекстах. Сам Кнут, кстати, при ручном вычислении ожидаемого значения ошибся.

[juan_gandhi]

Понятно. Компилятор попинать. Да.

[sab123]

С 2 - еще не полный эффект, еще значение из B() не доберется до 4-го и 5-го параметров.

Но вообще непонятно, зачем такой гемор. Такое ощущение, что они добрались до стеков и взялись придумывать наиболее запутанный способ их использования.

[vak]

Неполный эффект - неважно, наш алгол уже на этом циклится.

Все претензии к авторам Алгола-60. Так был задуман язык, а тест просто показывает все странные эффекты в полной красе.