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.