пятница, 31 декабря 2010 г.

FORTH - программирования язык стековый

Введение

FORTH - весьма необычный язык программирования. Во-первых, Форт-программа записывается в постфиксной нотации, например:

2 2 + 4 = IF ... ELSE ... THEN

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

Разработка на Форте, как правило, осуществляется снизу-вверх: сначала определяются базовые слова, а затем, на их основе строятся всё более и более высокоуровневые определения. Таким образом, хорошая Форт-программа обычно состоит из большого количества маленьких слов.

Благодаря простоте языка, Форт-интерпретаторы могут работать на самых примитивных процессорах, поэтому Форт часто используют во встраиваемых системах: управление оборудованием, бытовая техника, телеметрия, измерительные приборы, авионика и прочее.

Также нельзя обойти стороной и расширяемость языка: пользовательские слова имеют такой же уровень доступа ко всем внутренним механизмам Форта как и встроенные определения. Эта особенность позволяет буквально написать специальный язык программирования для решения конкретной задачи.

Завершу своё введение короткой исторической справкой. Автором Форта является Чак Мур (Chuck Moore). Разработан язык был аж в 1960-х годах и продолжает использоваться по сей день. По задумке автора, язык должен был называться FOURTH (язык четвёртого поколения), но поскольку машина IBM 1130, на которой тогда велась разработка, допускала максимум пятизначные идентификаторы, пришлось довольствоваться FORTH-ом. Сам Чак Мур и по сей день участвует в разработке, стандартизации и внедрении Форта (http://forth.com).

FORTH на примере

В качестве примера приведу решение всем известной задачи о Ханойских башнях:
( ----------------------------------------------------------- )
( DESCRIPTION: Tower of Hanoi )
( AUTHOR: Alexander Simakov, <xdr [dot] box [at] Gmail> )
( http://alexander-simakov.blogspot.com/ )
( LICENSE: Public domain )
( HOW-TO RUN: gforth tower_of_hanoi.fs -e 'bye' )
( ----------------------------------------------------------- )


( Constants )
5 CONSTANT N_DISKS ( number of disks )
1 CONSTANT EXTRA_PAD ( extra disk padding )
250 CONSTANT DELAY ( animation delay )

( Peds )
CREATE A N_DISKS CELLS ALLOT
CREATE B N_DISKS CELLS ALLOT
CREATE C N_DISKS CELLS ALLOT

VARIABLE #MOVE_NUMBER
VARIABLE #TOTAL_MOVES

: RESET_PED ( ped_addr -- )
N_DISKS CELLS ERASE
;

: STACK_ALL_DISKS_ON_PED ( ped_addr -- )
N_DISKS 0
DO
DUP I CELLS + ( current cell address )
N_DISKS I - ( current disk number )
SWAP
! ( put next disk onto the top of the ped )
LOOP
DROP
;

: INIT_PEDS ( -- )
A STACK_ALL_DISKS_ON_PED
B RESET_PED
C RESET_PED

0 #MOVE_NUMBER !
1 N_DISKS LSHIFT 1- #TOTAL_MOVES !
;

: DISK_PADDING ( disk_number -- pad_size )
N_DISKS SWAP - EXTRA_PAD +
;

: REVERSE_DISK_INDEX ( direct_disk_index -- reverse_disk_index )
N_DISKS SWAP - 1-
;

: PRINT_DISK ( disk_number -- )
DUP DISK_PADDING SPACES ( left padding )
DUP
2 * 0
?DO
[CHAR] = EMIT
LOOP
DISK_PADDING SPACES ( right padding )
;

: PED_LABEL_PADDING ( -- )
N_DISKS 2 * 2 - 2 / EXTRA_PAD +
;

: PRINT_PED_LABEL ( ped_label -- )
PED_LABEL_PADDING SPACES
[CHAR] # EMIT
EMIT
PED_LABEL_PADDING SPACES
;

: PRINT_PED_LABELS ( -- )
[CHAR] A PRINT_PED_LABEL
[CHAR] B PRINT_PED_LABEL
[CHAR] C PRINT_PED_LABEL
;

: PRINT_STATS ( -- )
." Move number/total moves: "
#MOVE_NUMBER @ .
." / "
#TOTAL_MOVES @ .
;

: PRINT_PEDS ( -- )
PRINT_STATS CR
N_DISKS 0
DO
CR
A I REVERSE_DISK_INDEX CELLS + @ PRINT_DISK
B I REVERSE_DISK_INDEX CELLS + @ PRINT_DISK
C I REVERSE_DISK_INDEX CELLS + @ PRINT_DISK
LOOP
CR
PRINT_PED_LABELS
;

: REFRESH_PEDS ( -- )
PAGE
PRINT_PEDS
DELAY MS
;

: GET_TOP_DISK_ADDR ( ped_addr -- top disk addr )
DUP N_DISKS 1- CELLS + ( top ped addr )
BEGIN
DUP @ IF NIP EXIT THEN
1 CELLS -
2DUP >
UNTIL ( until start addr > cur addr )
ABORT" Ped is already empty"
;

: GET_FREE_SLOT_ADDR ( ped_addr -- free slot addr )
DUP N_DISKS 1- CELLS +
SWAP
BEGIN
DUP @ 0= IF NIP EXIT THEN
1 CELLS +
2DUP < ( until end addr < cur addr )
UNTIL
ABORT" Ped is already full"
;

: MOVE_DISK ( from_ped to_ped -- )
GET_FREE_SLOT_ADDR SWAP
GET_TOP_DISK_ADDR SWAP
OVER @ SWAP ! ( copy disk to new ped )
0 SWAP ! ( remove disk from old ped )
1 #MOVE_NUMBER +! ( increment move number )
;

: TOWER_OF_HANOI ( from_ped to_ped tmp_ped n_disks -- )
RECURSIVE

DUP 1 = IF
2DROP
MOVE_DISK
REFRESH_PEDS
EXIT
THEN

3 PICK ( push from_ped )
2 PICK ( push tmp_ped )
4 PICK ( push to_ped )
3 PICK 1- ( push n_disks-1 )

TOWER_OF_HANOI

3 PICK ( push from_ped )
3 PICK ( push to_ped )

MOVE_DISK
REFRESH_PEDS

1 PICK ( push tmp_ped )
3 PICK ( push to_ped )
5 PICK ( push from_ped )
3 PICK 1- ( push d_disks-1 )

TOWER_OF_HANOI

2DROP
2DROP
;


INIT_PEDS
REFRESH_PEDS
A C B N_DISKS TOWER_OF_HANOI
CR

Скачать файл: tower_of_hanoi.fs

Для запуска можно использовать GNU Forth:
gforth tower_of_hanoi.fs -e 'bye'
Также имеется анимация в виде консольного ролика tower_of_hanoi_animation.ttyrec. Для его воспроизведения понадобится пакет ttyrec:
ttyplay tower_of_hanoi_animation.ttyrec
Заключение

Когда начинаешь изучать Форт, то возникает ощущение будто бы раньше писал сидя за столом, правой рукой и при вклчённом свете, а теперь просят сделать тоже самое, но в темноте, лёжа, да ещё и левой ногой. Естественно, по-началу это несколько обескураживает, но потом привыкаешь и потраченные усилия начинают окупаться засчёт интересного опыта и удовольствия от решения остроумных головоломок.

Ссылки