проФорт

Разбирать программу на форте всегда надо с конца, с главной процедуры (если есть она) или с примеров использования. В данном случае примеры — есть, смотрим их:

... 
( test ) 

s-define v1 
s-define v2 

s( 1 ->s 2 ->s 3 ->s 4 ->s 5 ->s 6 ->s 7 ->s 8 ->s )s v1 set 
...

Интуиция подсказывает что s-define является неким определяющим словом, set — устанавливает значение для созданной через s-define переменной, а s( )s скобки отграничивают "выражение" со словом ->s кладущим в выражение число со стека.

Отсюда можно пойти посмотреть как написано или слово s-define или ->s или скобки s( )s. Особенно много тумана каждое из них не рассеивает, но от определения ->s, можно дойти до p->s которое как по названию, так и по реализации говорит, что оно является частью группы слов для чтения из/записи в некий стек s (при этом по здравому смыслу можно предположить что p в названиях слов p->s и s->p обозначает parameter stack, стек параметров, т.е. — обычный стек).

Дальше уже мельком можно обнаружить рядом слова s-drop, s-dup, s-over — они не требуют даже разбора, названия их вполне "говорящие". Точно так же, мельком, видим что ещё чуть пониже есть определения слов для работы с ещё одним стеком "с".

Далее, несколько нелогично прекратив разбор исходника, чего-то решил собственно запустить файл s-expr.f (что по идее, надо было сделать сразу). Запуск вывел:

(1 2 3 4 5 6 7 8 )(1 4 9 16 25 36 49 64 ) 
\ Вывод: 34 

Что говорит первая строчка вывода?.. Два списка, первый — перечисление от 1-го до 8-и (переменная v1), второй — квадраты этого перечисления. А где делаются эти квадраты от списка?.. Ищем операцию умножения, смотрим в примерный код, так вот оно, умножение:

: foo1 
   s( ['] s-> xt->s ['] DUP xt->s ['] * xt->s ['] ->s xt->s )s 
   v1 get map v1 get s-swap () cons cons v2 set ; 

Что происходит на второй строчке этого отрывка?.. xt процедур s-> DUP * записываются в список, только "разделителем" на этот раз в отличие от первого примера является не ->s, а xt->s. То есть выбор слова записывающего в список определяет тип элемента. Уже это одно много даёт для понимания: сразу можно вернуться к ->s соседствующим с xt->s и обнаружить что они оба каким-то образом берут пустой элемент списка (на данный момент слово (cons) изучать не хочется) и кладут в поле структуры .s-tag дескриптор (определитель типа). Исходя из там же написанного слова s-> можно увидеть что определитель типа заодно является и xt для выдачи его (значения "определителей типа" хранятся в переменных 'pair, 'null, 'number, 'code). Ещё пониже обнаруживаем слова pair?, number?, null?, code? с говорящими названиями и стековой нотацией и простым определением.

Замечание 1: 'pair в нашем случае определяет так называемую "пару", где оба поля элемента списка (и поле данных и поле связи) являются ссылками на другие элементы.

Замечание 2: все поля элемента списка задаются в самых первых строчках кода, они аналогичны этим SPF-овским:

0 
CELL -- .s-mark 
CELL -- .s-tag 
CELL -- .s-car 
CELL -- .s-cdr 
CONSTANT /s-obj 

То есть кроме стандартных поля данных (car) и поля связи (cdr), есть также поле отметки для сборщика мусора (mark), и поле типа элемента (про типы элементов списка — на пару абзацев выше).

Замечание 3: Встречающаяся конструкция примерно такого вида: [ 4 CELLS ] LITERAL смущать не должна, просто true-grue хотел сохранив ANS-совместимость (а она есть, и, в результате программа пускается не только на SPF, но и на SwiftForth, gforth и Win32Forth) и не потерять копейки при обсчёте в runtime чему равно 4 умножить на 4.

Потом возвращаемся к отрывку примерного кода. После определения списка с исполняемыми процедурами (s-> DUP * ->s), этот список вместе со значением списка v1 (...v1 get...) идёт в процедуру map. Далее по этимологии можно предположить что это слово map аналогично лисповскому, то есть выполняет некие действия для каждого элемента заданного списка. Исходя из получаемых результатов становится понятно что там и происходит взятие в квадрат каждого из элементов списка v1 и составление нового списка, который как видно из последующего кода примера, записывается в переменную v2 (опять же, что делает cons должно быть примерно понятно исходя из аналогии с его лисповым тёзкой).

Далее чисто для убеждения что всё понято правильно, пару запусков-проверок:

34 v1 get .list 
\ Вывод: 1 2 3 4 5 6 7 8  Ok 
v1 get length . 
\ Вывод: 8  Ok 
v1 get s-eval 
\ Вывод:  Ok ( [8].. 4 5 6 7 8 ) 

s( 
    10 ->s 
    1  ->s 
  ' +  xt->s 
  ' .  xt->s 
)s s-eval 
\ Вывод: 11  Ok

Дальше разбирать осталось собственно самое важное для чего всё это затевалось — сам сборщик мусора, он записан в слово с логичным названием gc (gc — garbage collector). В лексикон к нему входят слова: s-reserve, s-mark, s-sweep. Смотря на s-reserve можно понять что оно создаёт эдакую отдельную "кучу", при заданных на стеке при запуске слова начале и длине её этой "кучи". То что "куча" в данной программе берётся вся целиком статически и ограничивается 256-ью элементами максимум для всех видов списков-"выражений" — не суть важно.

Замечание 4: я никогда до этого момента не встречался с и не изучал алгоритмы сборки мусора. Хотя, примерное моё представление о том как это делается совпало с реализованным здесь mark'n'sweep.

Далее, s-reserve, кроме того что задаёт в переменных s-heap и s-size кучу, очищает поля меток у пустых пока элементов и налаживает связи между ними сцепляя пустышки друг с другом. При этом начиная с элемента хранящегося в s-free у нас всегда должен быть связанный через поле cdr список пустых элементов.

s-mark рекурсивно проходит начиная от заданного элемента p и выставляет в нём и связанных с ним элементах метку.

s-sweep делает цикл по всей куче и из неотмеченных элементов (то есть тех на которые никто не ссылается и они является таким образом "мёртвыми") составляет новый список "пустышек" с последним элементом в s-free.

Взглянув на gc можно сообразить что у нас имеется три стека (точнее говоря — источника) в которых хранятся активные на данный момент списки — это стек "s" ("дно" его хранится в s-locals), стек "c" используемый в процедурах которые сами генерируют списки внутри себя (append, map) плюс ещё "глобальный" список, составленный из определяемых через s-define переменных (в нашем примере это v1 и v2). Пройдясь по всем источникам списков мы должны отметить все элементы участвующие в них, чтобы затем s-sweep мог найти "мёртвые" элементы на которые никто из наших трёх источников не ссылается.

(cons) берёт из кучи новый элемент и заполняет его поля car и cdr взятыми значениями из стека. При этом предварительно проверяется наличие в списке "пустышек" (s-free) свободного элемента, если его не находится, то запускается сборщик мусора gc который поскребя по сусекам должен найти "мёртвые" элементы и составить из них новый список "пустышек".

Выводы:

• Для подхода к изучению чужого кода нужно во-первых иметь хотя бы примерное знакомство с предметной областью, теорией (совсем необязательно досконально знать, достаточно хотя бы "плавать" в терминах, а непосредственные детали реализации можно будет уяснить из самого кода). Если не отходить далеко от нашего примера — к началу конкретного этого разбора я знал в чём состоит задача "сборки мусора", знал что она обозначается как gc, имел смутное представление о том "как оно работает".
  
• Правило "читай с конца" применённое в самом начале разбора обосновывается технологическими особенностями Форта. Так как forward-ссылки в форте из-за однопроходности компилятора не используются, то определения (процедуры) идут в тексте по мере нарастания сложности, из-за чего "главные", наиболее мощные слова оказываются в конце текста. Отсюда и идёт правило что разбирать программу на форте надо с конца и разматывать клубок нужно, начиная с "торчащей нитки" — главного слова или одного из них.
  
• Последовательность разбора каждой процедуры примерно такая: имя, комментарии, код. Если смысл слова становится понятен на более раннем этапе, то остальные делать соответственно незачем.
  
• Авторы всегда стараются давать говорящие названия своим процедурам (по крайней мере — говорящие им), ваша задача — постараться понять что имелось в виду. Есть стихийно сложившийся "пиратский кодекс" по построению названий форта, который был обзорно описан в "Этимологии", он может помочь. Также можно посмотреть советы по именованию от ~pinka. Но главное подспорье — это здравый смысл (как впрочем и всегда).
  
• Проверяйте ваши "догадки", осознанные предположения о структуре/работе программы эмпирически — то есть непосредственно запуская програму и прогоняя тестовые куски.
  

Связанные ссылки:

• Авторский обзор s-выражений на Форте, сама наработка и пример её использования — решение задачи нахождения минимальной выпуклой оболочки.