Многие языки семейства Оберон включают в себя сборщик мусора. В основном используется алгоритм Mark-and-Sweep. Сам по себе этот алгоритм не сложный, он основывается на том, что у нас имеется множество начальных указателей, с которых мы начинаем помечать объекты, как используемые, и так далее, если у объекта есть свои указатели, то и эти объекты помечаем как используемые. Далее можно добавить в список свободной памяти все объекты, которые оказались не помеченными.
Нахождение начального множества указателей не такое простое дело, как кажется. Это множество включает в себя глобальные переменные-указатели, локальные переменные-указатели, возможно, регистры, если в них временно хранится какой-нибудь указатель, который нигде больше не хранится. Множество глобальных переменных-указателей обычно сохраняется определенным образом в объектный файл и загручик получает эту информацию из объектного файла и соотвественно сборщик мусора знает, какие из глобальных переменных являются указателями.
А вот как определить какие из локальных переменных являются указателями?
Во многих книгах Никлауса Вирта, этот вопрос как-то обходится стороной. Например, в книге Project Oberon по поводу начальных указателей написано: "We shall postpone the question of how these roots are to be found, and first present a quick tutorial about tree traversal."
Возможно, в книге где-то упоминается реализация поиска начальных указателей в локальных переменных, просто я не нашел. Если кто укажет мне на раздел в книге и страницу, буду очень благодарен.
Возможно, у него есть отдельная статья, где он подробно описывает устройство сборщика мусора.

Проверил, как сборщик мусора устроен в системе BlackBox. В модуле Kernel есть следующая функция:
## Код:
```
PROCEDURE MarkLocals;
        VAR sp, p, min, max: INTEGER; c: Cluster;
    BEGIN
        S.GETREG(FP, sp); nofcand := 0; c := root;
        WHILE c.next # NIL DO c := c.next END;
        min := S.VAL(INTEGER, root); max := S.VAL(INTEGER, c) + c.size;
        WHILE sp < baseStack DO
            S.GET(sp, p);
            IF (p > min) & (p < max) & (~strictStackSweep OR (p MOD 16 = 0)) THEN
                candidates[nofcand] := p; INC(nofcand);
                IF nofcand = LEN(candidates) - 1 THEN CheckCandidates; nofcand := 0 END
            END;
            INC(sp, 4)
        END;
        candidates[nofcand] := max; INC(nofcand);    (* ensure complete scan for interface mark*)
        IF nofcand > 0 THEN CheckCandidates END
    END MarkLocals;
```

Из которой следует, что проверяются не только указатели а все значения в стеке с шагом 4 байта. Если значение хранящееся в 4-х байтах лежит в интервала от min до max, то возможно это указатель и с него надо начинать проверку.
Как мне кажется это не совсем правильный алгоритм, так как если в какой-то переменной случайно окажется значение равное указателю на память, которое больше не используется, то память не будет освобождена, пока эта переменная не изменит свое значение.
Например, можно проделать следующий эксперимент:
Процедура внутри себя выделяет 600 мегабайт и вызывает себя рекурсивно, пока удается выделить память, или пока количество вызовов не достигнет 10. В данном примере, у меня выделяется 2 раза по 600 мегабайт, больше не может выделиться.
## Код:
```
MODULE TestCollector;

    IMPORT Kernel, SYSTEM, Log;

    PROCEDURE Alloc(n: INTEGER); 
    VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
        a: INTEGER;
    BEGIN
        IF n < 10 THEN
            NEW(p);
            IF p # NIL THEN 
                Log.String("OK"); Log.Ln; 
                Alloc(n+1);
            ELSE 
                Log.String("FAIL"); Log.Ln;
            END;
        END;
    END Alloc;
    
    PROCEDURE Do*;
    BEGIN
        Alloc(0);
    END Do;

END TestCollector.
```

Немного изменю программу. Теперь указателю присваивается NIL, и теоретически процедура может очень много раз себя вызвать, так как стоит ограничение 10 раз, то она выполнится 10 раз и остановится.
## Код:
```
MODULE TestCollector;

    IMPORT Kernel, SYSTEM, Log;

    PROCEDURE Alloc(n: INTEGER); 
    VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
        a: INTEGER;
    BEGIN
        IF n < 10 THEN
            NEW(p);
            IF p # NIL THEN
                p := NIL;
                Log.String("OK"); Log.Ln; 
                Alloc(n+1);
            ELSE 
                Log.String("FAIL"); Log.Ln;
            END;
        END;
    END Alloc;
    
    PROCEDURE Do*;
    BEGIN
        Alloc(0);
    END Do;

END TestCollector.
```

А теперь рассматривается случай, когда в переменной типа INTEGER случайно оказалось значение равное указателю. Этот пример отработает только 2 раза, хотя по логике должен был бы отработать 10 раз, как и предыдущий пример.
## Код:
```
MODULE TestCollector;

    IMPORT Kernel, SYSTEM, Log;

    PROCEDURE Alloc(n: INTEGER); 
    VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
        a: INTEGER;
    BEGIN
        IF n < 10 THEN
            NEW(p);
            IF p # NIL THEN 
                a := SYSTEM.VAL(INTEGER, p);
                p := NIL;
                Log.String("OK"); Log.Ln; 
                Alloc(n+1);
            ELSE 
                Log.String("FAIL"); Log.Ln;
            END;
        END;
    END Alloc;
    
    PROCEDURE Do*;
    BEGIN
        Alloc(0);
    END Do;

END TestCollector.
```


В общем основной вопрос этого большого топика в том, как правильно реализовать поиск указателей в локальных переменных?