Forth CPU. Что это такое? (Часть 2)

В прошлой статье мы рассматривали простейший Forth CPU J1. Теперь самое время рассказать что за язык этот Форт, и как его хорошо компилировать для этого процессора.

Грамматика языка

Форт — идеальный язык для парсера. Программа состоит из слов, слова разделены пробелами. Слова — это аналог функций, например:

open read close

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

\ однострочный комментарий
( многострочный 
  комментарий )

Все предельно просто. Единственное, что может огорчить, так это обратная польская запись (RPN). Например сложение трех чисел пишут так:

1 2 3 + + или 1 2 + 3 +

Программа на Форте есть ничто иное как:
— определение своих слов на основе уже существующих
— выполнение каких-то действий посредством вызова этих слов

Стандартные слова

Давайте определим какой-то минимум слов, на основе которых можно будет строить свои конструкции. Для каждого слова я постараюсь использовать комментарий, как принято в Форте — описывать состояние стека до вызова слова и после.

noop ( -- ): ничего не делать
+ ( a b -- a+b ): сложение двух чисел на вершине стека
xor ( a b -- a^b ): исключающее ИЛИ
and ( a b -- a&b ): побитовое И
or ( a b -- a|b ): побитовое ИЛИ
invert ( a -- ~a ): инверсия
= ( a b -- a==b?1:0 ): сравнение двух чисел
< ( a b -- a<b?1:0 ): тоже сравнение
swap ( a b -- b a ): перестеновка двух чисел на вершине стека
dup ( a -- a a ): копирование числа
drop ( a b -- a ): удаление числа с вершины стека
over ( a b -- a b a): установка на вершину стека предпоследнего числа
nip ( a b -- b ): удаление предпоследнего числа из стека
>r ( a -- ): перемещение числа из стека данных в стек вызовов
r> ( -- a ): перемещение числа из стека вызовов в стек данных
@ ( a -- [a] ): получение числа из памяти по адресу
! ( a b -- ): установка числа в памяти по адресу ([b]:=a)
1- ( a -- a-1): декремент

Все эти слова можно реализовать одной ALU-инструкцией J1 (кроме "!", там есть хитрость — нужно два элемента со стека убирать, а J1 этого не умеет).

Есть еще несколько слов, которые можно реализовать инструкциями, но не будем усложнять, а перейдем к созданию своих слов.

Создание новых слов

Для того чтобы описать слово используют такой синтаксис:

: my-word ( before -- after ) ........ ;

Здесь двоеточие означает декларацию нового слова, my-word — собственно слово, точка с запятой в конце — возврат из функции (ведь вызов слова — это по сути инструкция CALL, значит должет быть RETURN).

Например, есть такое слово — rot ( a b c — b c a ). Выполняет оно сдвиг последних трех чисел на стеке по кругу (т.е. помещает третье число от вершины стека на вершину). Так как стандартные слова оперируют только двумя числами, то третье нам придется где-то временно хранить. Для этого нам пригодится стек вызовов r. Например:

: rot ( a b c -- b c a )
	>r   ( a b )
	swap ( b a )
	r>   ( b a c )
	swap ( b c a )
	;
( например )
1 2 3 rot ( ожидаем 2 3 1 на стеке )

Вот другая интересная инструкция (возвращает одно из двух чисел в зависимости от третьего):

: merge ( a b m -- m?b:a )
	>r          ( a b )
	over xor    ( a a^b )
	r> and      ( a a^b&m )
	xor
	;

Это слово уже выглядит сложнее. Но зато Форт заставляет писать короткие слова, которые можно легко проверить отдельно от всего кода. И тогда код тоже будет простым и понятным. Это здравая мысль возникла у Чарльза Мура еще в 1970х.

Управляющие конструкции и другие элементы языка

В языке есть переменные, константы, циклы, ветвления. Описание переменных и констант выглядят таким образом:

( константы: значение constant имя )
0 constant false
1 constant true
42 constant answer
( переменные: variable имя )
variable x
variable y
( переменные - это адреса в памяти. Поэтому скажем x=2;y=x+1 выгдядит так )
2 x ! ( x = 2 )
x @ ( stackTop = x ) 
1 + ( stackTop = stackTop + 1 )
y ! ( y = stackTop )

Цикл вида do..while записывают так: begin… condition until:

5 begin 1 - dup 0 = until

Перед циклом заносим на стек число 5. В цикле уменьшаем на единицу. Сравниваем результат с нулем, и если не ноль — повторяем цикл.

Условный оператор в зависимости от значения на вершине стека выполняет одну из своих веток. Число с вершины стека удаляется.

( есть две формы:
 condition IF ... THEN 
 condition IF ... ELSE ... THEN )

Вот основные конструкции языка. Есть еще циклы со счетчиком и с предусловием, и многое другие, но это уже выходит за формат одного поста.

Вывод

Язык довольно простой и интересный. Если привыкнуть, то код можно даже читать. Простенький компилятор для J1 доступен здесь. Умеет компилировать пока очень мало, но может кому интересно будет. Написан тоже на языке Go, как и эмулятор.

В реальной жизни применяют Forth в основном в embedded потому что очень уж мало места занимает байт-код (порой даже меньше чем C). Из серьезных проектов на Forth могу назвать OpenFirmware и биос лэптопов OLPC (по сути тоже openfirmware). Кстати, у OLPC на сайте и учебник неплохой по форту есть.