Задача на тему "дерева в памяти" мне показалась любопытной. Не буду сейчас поднимать вопрос практической целесообразности, в конце концов, написание программ на Форте часто сравнивают с разгадыванием головоломки в духе "Судоку".
Итак, за основу возьму описание структуры силами фортовского DSL, а на выходе создам "дерево в памяти", которое еще и распечатаю в виде S-выражения. Почему не в виде C-выражения? Так ведь надо же что-то (кроме вывода возможны и преобразования дерева) оставить и в качестве упражнения для читателя!
Я несколько отвык от Форта за последнее время, так что прошу простить мне "не идиоматический подход". В частности, я не собираюсь тратить время на определяющие слова и словари. Более того, мне и со SWAP, ROT и подобными фортизмами связываться не хочется. Поэтому начну я с реализации локальных переменных.
Код:
create locals 1024 cells allot
variable lptr locals lptr !
: loc+ ( n) cells lptr +! ;
: loc ( i) lptr @ swap 2 + cells - @ ;
: loc! ( x i) lptr @ swap 2 + cells - ! ;
: loc: ( .. n) lptr @ >r 0 do lptr @ ! 1 loc+ loop
r> lptr @ ! 1 loc+ ;
: loc; -1 loc+ lptr @ @ lptr ! ;
Никаких имен, только индексы. Код с применением таких конструкций не является читабельным, но, по крайней мере, его несколько удобнее писать.
Чем потенциально хороши DSL на Форте? Помимо последовательностей слов, разделяемых пробелами, достаточно выразительно выглядят "префиксные" выражения с использованием WORD. Но работу со строками в Форте удобной не назовешь. Тот же WORD сохраняет текст во временную область. Раз уж взялся за задачу, реализую хранилище для строк.
Код:
create strings 1024 allot
variable sptr strings sptr !
: >str ( a - a) dup count 1 + 3 loc: sptr @ 1 loc!
0 loc sptr @ 2 loc cmove 2 loc sptr +! 1 loc loc; ;
Слово >str получает строку со счетчиком и сохраняет ее в области strings.
Как же хранить пресловутое дерево в памяти? Буду использовать классический алгоритм размещения дерева в линейном массиве. Сначала в массив помещаются дочерние узлы, затем -- родительский узел. Каждый узел состоит из числа элементов и последовательности адресов дочерних узлов.
Код:
create nodes 1024 cells allot
variable nptr nodes nptr !
: node+ ( n) cells nptr +! ;
: node ( .. n) nptr @ >r dup r@ ! 1 node+
dup >r loc: r> 0 do i loc nptr @ ! 1 node+ loop
loc; r> ;
Слово node берет со стека n дочерних узлов и формирует с их помощью новый узел в nodes.
Теперь следует заняться печатью дерева в виде S-выражения. Буду считать атомом узел, у которого вместо адреса первого дочернего узла хранится 0.
Код:
: .atom ( a) count type ;
: n@ ( a i - a) cells + @ ;
: .ast ( a) dup 1 n@ 0 = if 2 n@ .atom exit then
." (" dup @ 2 loc: 1 loc if 0 loc 1 n@ .atom
1 loc 1 - 0 ?do ." " 0 loc i 2 + n@ recurse loop
." )" then loc; ;
Далее понадобится несколько вспомогательных слов.
Код:
: id ( "name" - a) bl word >str 1 loc:
0 0 loc 2 node loc; ;
: ` postpone postpone ; immediate
: tree: 1 loc+ ;
: tree; -1 loc+ ;
Наконец, пришло время реализовать DSL.
Код:
: (var) 0 loc 1 + 0 loc! 2 1 loc: ;
: var: ( "name")
` (var) c" var" ` literal id ` literal ; immediate
: var; 0 loc node loc; ;
: array: ( "name")
` (var) c" array" ` literal id ` literal ; immediate
: array; var; ;
: struct: ( "name")
` (var) c" struct" ` literal id ` literal ; immediate
: struct; var; ;
: (type) 0 loc 1 + 0 loc! 2 node ;
: type: ( "name")
c" type" ` literal id ` literal ` (type) ; immediate
: max: ( "name")
c" max" ` literal id ` literal ` (type) ; immediate
: min: ( "name")
c" min" ` literal id ` literal ` (type) ; immediate
: default: ( "name")
c" default" ` literal id ` literal ` (type) ; immediate
: size: ( "name")
c" size" ` literal id ` literal ` (type) ; immediate
Привожу пример описания и вывода структуры.
Код:
: code-tree
tree:
struct: UserGroup
var: priority
type: int min: 10 max: 10 default: 10
var;
array: name
type: char size: MAX_GROUP_NAME_LENGTH default: ""
array;
struct;
tree; ;
code-tree .ast
(struct UserGroup (var priority (type int) (min 10) (max 10) (default 10)) (array name (type char) (size MAX_GROUP_NAME_LENGTH) (default "")))
Как можно видеть, ручная реализация примитивных операций в Форте не так уж сложна. По моему опыту, она во многих случаях проще, чем попытки приспособить какие-то готовые конструкции из стандартного Форта. Как известно, Форт -- язык не алгебраический. И дело тут даже не в отсутствии способов записи инфиксных выражений. В Форте, к сожалению, мало уделяется внимания таким важным свойствам математических структур, как замкнутость и композиционность.