vak: (Default)
Serge Vakulenko ([personal profile] vak) wrote2024-08-19 11:17 pm

Man or boy

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

Много лет назад один клёвый чувак написал хитрый тест для Алгола 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.

Post a comment in response:

This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org