vak | Отладка алгольной программы

Покажу, чем развлекаюсь в выходной день. Ищу багу в программе на Алголе-60, точнее в рантайм библиотеке. Где-то неправильно сохраняется-восстанавливается контекст выполнения, а именно отображение лексического уровня вложенности на фреймы в стеке. Вот тест, на котором проявляется ошибка:

begin
    procedure A(k, x);
        value k;
        integer k, x;
    begin
        procedure B(y);
            integer y;
        begin
            print(k, x, y);
            if x > -10 then A(456, -10);
            if y < 0 then B(20);
        end B;

        print(k, x);
        B(x - 1);
    end A;

    A(123, -1);
end

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

Нарисуем последовательность вызовов.

      Stack Frames: 1-----------2---------------3---------------4-----------5-----------6
Program
    | A(123, -1)    A
    |-------------->|
    |               | B(-1-1)   B
    |               |---------->|
    |               |           | A(456, -10)   A
    |               |           |-------------->|
    |               |           |               | B(-10-1)      B
    |               |           |               |-------------->|
    |               |           |               |               | B(20)     B
    |               |           |               |               |---------->|
    |               |           |               |               |    return |
    |               |           |               |               |<----------|
    |               |           |               |    return     |
    |               |           |               |<--------------|
    |               |           |        return |
    |               |           |<--------------|
    |               |           |
    |               |           | B(20)         B
    |               |           |-------------->|
    |               |           |               | A(456, -10)   A
    |               |           |               |-------------->|
    |               |           |               |               | B(-10-1)  B
    |               |           |               |               |---------->|
    |               |           |               |               |           | B(20)     B
    |               |           |               |               |           |---------->|
    |               |           |               |               |           |    return |
    |               |           |               |               |           |<----------|
    |               |           |               |               |    return |
    |               |           |               |               |<----------|
    |               |           |               |        return |
    |               |           |               |<--------------|
    |               |           |        return |
    |               |           |<--------------|
    |               |    return |
    |               |<----------|
    |        return |
    |<--------------|
    |

Соотнести лексические уровни со стековыми фреймами нам поможет двумерная картинка. Это первая половина, до момента, когда процедура B(20) завершается на уровне 5:

 Stack  |               Lexical Scope Level
 Level  |   0 (global)      1                       2
--------|---------------|-------------------|------------------------
    0   | A(123, -1)    |                   |
--------|---------------|-------------------|------------------------
    1   |               | procedure A:      |
        |               | display[1] = 0    |
        |               | k = 123           |
        |               | print "123, -1"   |
        |               | B(x-1)            |
--------|---------------|-------------------|------------------------
    2   |               |                   | procedure B:           
        |               |                   | display[2] = 011       
        |               |                   | print "123, -1, -2"    
        |               |                   | A(456, -10)            
--------|---------------|-------------------|------------------------
    3   |               | procedure A:      |
        |               | display[1] = 020  |
        |               | k = 456           |
        |               | print "456, -10"  |
        |               | B(x-1)            |
--------|---------------|-------------------|------------------------
    4   |               |                   | procedure B:           
        |               |                   | display[2] = 031       
        |               |                   | print "456, -10, -11"  
        |               |                   | B(20)                  
--------|---------------|-------------------|------------------------
    5   |               |                   | procedure B:           
        |               |                   | display[2] = 040       
        |               |                   | print "456, -10, 20"   
--------|---------------|-------------------|------------------------

Вторая половина:

 Stack  |                 Lexical Scope Level
 Level  |   0 (global)      1                   2
--------|---------------|-------------------|------------------------
    0   | A(123, -1)    |                   |
--------|---------------|-------------------|------------------------
    1   |               | procedure A:      |
        |               | display[1] = 0    |
        |               | k = 123           |
        |               | B(x-1)            |
--------|---------------|-------------------|------------------------
    2   |               |                   | procedure B:
        |               |                   | display[2] = 011
        |               |                   | B(20)
--------|---------------|-------------------|------------------------
    3   |               |                   | procedure B:
        |               |                   | display[2] = 020
        |               |                   | print "0, 4718593, 20"
        |               |                   | A(456, -10)
--------|---------------|-------------------|------------------------
    4   |               | procedure A:      |
        |               | display[1] = 027  |
        |               | k = 456           |
        |               | print "456, -10"  |
        |               | B(x-1)            |
--------|---------------|-------------------|------------------------
    5   |               |                   | procedure B:
        |               |                   | display[2] = 040
        |               |                   | print "456, -10, -11"
        |               |                   | B(20)
--------|---------------|-------------------|------------------------
    6   |               |                   | procedure B:
        |               |                   | display[2] = 047
        |               |                   | print "456, -10, 20"
--------|---------------|-------------------|------------------------

Ошибка выделена цветом. Эти значения неправильно извлекаются из стека.