Встреча с FORTH
Cистемы типа Matlab/Octave можно рассматривать как
своего рода калькуляторы, только высокого
уровня: в них есть векторы, матрицы —
всё, что нужно для реализации научных
вычислений. Однако, они большие и требуют
мощного компьютера с операционной системой. Интересно, что давным давно, во времена, когда персональные компьютеры были немногим сильнее калькулятора, как, например, мой HP 35s существовало интересное решение.
Например, персональный компьютер Jupiter Ace со встроенным языком программирования FORTH. Особенность этого языка программирования в том, что ему не нужна ни операционная система, ни файлы, ровным счетом ничего, кроме чистого железа. Это позволило оснащать довольно слабые по современным меркам компьютеры даже офисным программным обеспечением, как например, компьютер Canon Cat. Набор приложений был записан в ПЗУ. В него входили: стандартный пакет офисных программ, орфографический словарь на 90 000 слов, программа связи и средства программирования на Форт и языке ассемблера.
FORTH использует технологию «шитого кода».
Проще говоря, это массив вызовов
подпрограмм. Указатель выполнения кода
последовательно принимает адреса
подпрограмм, которые исполняются.
Передача параметров происходит через
стек.
Шитый код используется в программировании калькулятора HP 35s
Шитый код используется в программировании калькулятора HP 35s
Контрольные слова (для определений
ветвлений и циклов) имеют атрибут
IMMEDIATE. FORTH позволяет управлять входным
потоком слов и определять управляющие
конструкции, т. е. слова с инструкциями
для состояния интерпретации и компиляции.
Вот пример корректной программы на FORTH:
: ПОЛОСКАТЬ НАЛИТЬ-ВОДУ СТИРАТЬ ВЫЛИТЬ-ВОДУ ;
: СТИРАЛЬНАЯ-МАШИНА СТИРАТЬ ВЫКРУЧИВАТЬ ПОЛОСКАТЬ ВЫКРУЧИВАТЬ ;
Нравится? Читаем книгу Л. Броуди. Начальный курс программирования на языке ФОРТ.
Сразу отмечу, что FORTH - не способ программирования на естественном языке, это скорее метод формализации естественного языка на строгий алгоритмический язык конечного автомата с несколькими стеками. Простота достигается за счёт применения стеков и обратной польской записи, а также за счёт отсутствия синтаксиса, типов данных и прочих абстракций программирования. Однако, если какие-то абстракции нужны - их всегда можно определить, так как вам угодно, а не создателям языка.
Nick Morgan любезно предоставил всем желающим попробовать FORTH прямо в окне браузера.
Знакомство
Далее я перечислю места, где в настоящее время встречается FORTH.
В космических аппаратах!
Программирование микроконтроллеров: семейства AtmelAVR8 Atmega, Microchip 8-bit PIC18F и 16-bit PIC24, 30, 33 и Arduino UNO и многих других. Читайте тут.
Встроенный скриптовый язык:
Игровая платформа настольных игр на ПК - Zillions of Games, в ней FORTH это способ разрабатывать свои игры, см. пост.
Скриптовый язык в XYPLOT - Extensible Plotting and Data Analysis Program for 32-bit x86 GNU/Linux, в планировщике задач nnCron и других приложениях.
тогда как более общая структура, граф выражения уже требует операций со стеком: перестановок, копирования и т.п.
Сравните выражение в обычной и обратной польской нотации (a + b)*c+7 = a b + c * 7 + и попробуйте записать (a + b)/(a + b*c)! В итоге программы на FORTH начинают выглядеть как жонглирование элементами стека.
Почему бы не решить проблему переменными? Они есть в FORTH. Кажущаяся проблема в том, что переменные глобальны и не связаны с единственным определяемым словом. В Си-подобных языках избегают глобальных переменных из-за того, что исчерпываются уникальные имена, сложно отслеживать значение переменной, если доступ к ней возможен из любого места программы...
Подводные камни
Обратная польская нотация очень удобна в калькуляторах, однако, она не всегда подходит для решения задач. Попытки избавиться от традиционного подхода с переменными бывают трагичны. В самом деле, как отмечает в своем блоге Yossi Kreinin, для стека подходят деревья выраженийтогда как более общая структура, граф выражения уже требует операций со стеком: перестановок, копирования и т.п.
Сравните выражение в обычной и обратной польской нотации (a + b)*c+7 = a b + c * 7 + и попробуйте записать (a + b)/(a + b*c)! В итоге программы на FORTH начинают выглядеть как жонглирование элементами стека.
: siftDown ( a e s -- a e s)
swap >r swap >r dup ( s r)
begin ( s r)
dup 2* 1+ dup r'@ < ( s r c f)
while ( s r c)
dup 1+ dup r'@ < ( s r c c+1 f)
if ( s r c c+1)
over over r@ precedes if swap then
then drop ( s r c)
over over r@ precedes ( s r c f)
while ( s r c)
tuck r@ exchange ( s r)
repeat then ( s r)
drop drop r> swap r> swap ( a e s)
;
Всё это приводит к тому, что язык Си кажется единственным, кто может с этим справиться. Одна из таких трагедий описана у Yossi Kreinin.
Почему бы не решить проблему переменными? Они есть в FORTH. Кажущаяся проблема в том, что переменные глобальны и не связаны с единственным определяемым словом. В Си-подобных языках избегают глобальных переменных из-за того, что исчерпываются уникальные имена, сложно отслеживать значение переменной, если доступ к ней возможен из любого места программы...
Я написал кажущаяся проблема, потому что на самом деле проблемы нет вовсе. Странно, что об этой особенности FORTH не упоминается в книгах явно и с предупреждением, но глобальные переменные FORTH ведут себя не так, как в Си.
Единственная книга, в которой обсуждается способ взаимодействия определения с окружением это книга Christian Queinnec. Lisp In Small Pieces. Поведение определений в FORTH попадает в класс гиперстатического связывания. Проще показать на примере.
: foo ." foo!" ; : bar foo ." bar!" ; bar foo! bar! ok. : foo ." bizzle!" ; Redefine foo. ok. foo bizzle! ok. bar foo! bar! ok.
Слово bar состоит из foo и вывода строки ." bar!". Однако, когда термин foo оказывается переопределён, то поведение bar остаётся неизменным! Определение слова сохраняет его контекст, слова в определении имеют ровно то значение, которое было на тот момент.
Отсюда следует, что нет никакой причины беспокоиться о том, что кончатся имена переменных и так далее. Вам нужна новая переменная my_variable? Так и назовите её, ничего из того, что связано было с ней ранее не изменится. Нет смысла вводить новый синтаксис и правила обращения с локальными переменными (хотя таких попыток в FORTH было много и разных), достаточно перед тем словом, где нужна переменная определить её, а после него определить новую с тем же самым именем.
Подытожим. FORTH это
С этих теоретических понятий уже можно собрать свой FORTH. Каноническая инструкция как это сделать написана Richard W.M. Jones, читайте по ссылке.
В dosbox'е устанавливаю F-PC 3.60 (читайте C.H. Ting. F-PC: FORTH optimized for IBM-PC // SIGFORTH Newsl. 1(1) (1989) 15-17 DOI:10.1145/382122.382928)
Это полноценная IDE с редактором кода
Справочником-помощью
а также отладчиком
Словом, весь джентльменский набор!
Поскольку FORTH интересовал меня с точки зрения математических вычислений, альтернатива Matlab и прочим Scientific Python, то я избавился от жонглирования стеком и режущими глаз мушками вроде f@ - чтение переменной/ f! - запись значения в переменную.
Вот как это работает.
Алгоритмы на FORTH получаются компактные, сам язык очень способствует факторизации кода. Например, сортировка:
Подытожим. FORTH это
С этих теоретических понятий уже можно собрать свой FORTH. Каноническая инструкция как это сделать написана Richard W.M. Jones, читайте по ссылке.
FORTH на вкус
Далее я расскажу о своем опыте погружения в античные времена MS DOS и существовавшей для него среды FORTH.В dosbox'е устанавливаю F-PC 3.60 (читайте C.H. Ting. F-PC: FORTH optimized for IBM-PC // SIGFORTH Newsl. 1(1) (1989) 15-17 DOI:10.1145/382122.382928)
Это полноценная IDE с редактором кода
Поскольку FORTH интересовал меня с точки зрения математических вычислений, альтернатива Matlab и прочим Scientific Python, то я избавился от жонглирования стеком и режущими глаз мушками вроде f@ - чтение переменной/ f! - запись значения в переменную.
Вот как это работает.
fload sfloat.seq fload eval.seq macro: get-name bl word count r@ place ; macro: $name r@ count ; macro: .. pad +place ; : cell: here >r get-name " variable *" pad place $name .. " : :" .. $name .. " *" .. $name .. " ! ; " .. " : " .. $name .. " *" .. $name .. " @ ; " .. r> drop pad count eval ; : float: here >r get-name " fvariable *" pad place $name .. " : :" .. $name .. " *" .. $name .. " f! ; " .. " : " .. $name .. " *" .. $name .. " f@ ; " .. r> drop pad count eval ; : cells: ( n -- ) 0 do cell: ( name ) loop ; : floats: ( n -- ) 0 do float: ( name ) loop ;Теперь если в каком-то определении нужны переменные, то перед ним я пишу
3 floats: x y zПрисваиваю им значения при помощи автоматически созданных слов
0.0e :x 0.0e :y 1.0e :zи получаю их значения на стек легко и естественно
x x f* y y f* z z f* f+ f+ fsqrtкак если бы делал это на калькуляторе. При необходимости легко переопределить имена x, y, z - на работе предыдущих слов это никак не скажется. Гиперстатическое связывание - удобная штука!
Алгоритмы на FORTH получаются компактные, сам язык очень способствует факторизации кода. Например, сортировка:
\ Heapsort is an in-place sorting algorithm with worst case
\ and average complexity of O(n*log[n]). The basic idea is
\ to turn the array into a binary heap structure, which has
\ the property that it allows efficient retrieval and removal
\ of the maximal element. We repeatedly "remove" the maximal
\ element from the heap, thus building the sorted list from
\ back to front.
0 1 2constant endless
defer item@
defer item!
defer greater?
6 cells: arr n p q r s
: maxi :r :q :p :n :arr
p :s
q n < if arr q item@ arr s item@ greater? if q :s then
then
r n < if arr r item@ arr s item@ greater? if r :s then
then s ;
: downheap :p :n :arr
endless do
arr n p p 2* 1+ p 2* 2 + maxi :q
q p = if leave then
arr p item@ arr q item@
arr p item! arr q item!
q :p
loop ;
2 cells: arr n
: heapsort :arr
arr @ :n
0 n 2 - 2/ do arr n i downheap -1 +loop
n 0 do
arr n i - 1- item@ arr 0 item@
arr n i - 1- item! arr 0 item!
arr n i - 1- 0 downheap
loop ;
: item-get item @ ;
' item-get is item@
: item-set item ! ;
' item-set is item!
' > is greater?
Стоит обратить внимание на конструкцию
defer word ... ' method is wordКоторая позволяет отложить определение какого-либо слова в определении термина до того момента, пока оно не станет известено. А вот реализация метода нахождения корня уравнения, её вполне можно сопоставить с таковой в других языках.
\ Using Ridder's method, return the root of a function func
\ known to lie between x1 and x2.
fload vars.seq
defer f(x)
10 floats: x1 x2 xm xnew fl fm fh fnew s result
-1.11e30 fconstant UNLIKELY-VALUE
1.0e-9 fconstant ACCURACY
50 constant MAXIT
: fsign ( r1 -- r1 ) f0< dup not - ifloat ;
: f~ ( r1 r2 r3 -- flag ) f-rot f- fabs f> ;
: root-not-bracketed? ( fl fh -- flag )
fdup f0< fover f0> and
( fh ) f0> ( fl ) f0< and or not ;
: ridder ( r1 r2 -- r1 ) :x2 :x1
x1 f(x) :fl
x2 f(x) :fh
fl f0= if x1 exit then
fh f0= if x2 exit then
fl fh root-not-bracketed?
if abort" root must be bracketed in zriddr" then
UNLIKELY-VALUE :result
false
MAXIT 0
do
x1 x2 f+ 2.0e f/ :xm xm f(x) :fm
fm fdup f* fl fh f* f- fsqrt :s
s f0= if result true leave then
fl fh f- fsign xm x1 f- f* fm f* s f/ xm f+ :xnew
xnew result ACCURACY f~
if result true leave then
xnew :result xnew f(x) :fnew
fnew f0= if result true leave then
fnew fsign fm f* fm f= not
if xm :x1 fm :fl result :x2 fnew :fh
else fnew fsign fl f* fl f= not
if result :x2 fnew :fh then
fnew fsign fh f* fh f= not
if result :x1 fnew :fl then
then
x1 x2 ACCURACY f~
if result true leave then
loop
if result drop
else ." zriddr exceed maximum iterations" drop then ;
float: x
\ : func :x x fcos x x x f* f* f- ; \ 0.0-1.0 x = 0.865474
: func :x x x x f* f* 10.0e x x f* f* f- 5.0e f+ ; \ 0.6-0.8 x=0.7346
' func is f(x)
0.6e 0.8e ridder f(x) f. cr
Не хуже чем Matlab? Учитывая, что это может работать на микроконтроллере, без колдовства с компилятором. На то можно возразить, что в Matlab'е есть средства высокого уровня, а тут где они? Продолжение следует.
Комментариев нет:
Отправить комментарий