Стандартные и нестандартные структуры управления в Форт-системе T32

(c) ООО ИТФ "Технофорт, 2000
(c) М.Л.Гасаненко, 2000
Данная статья является частью документации к Форт-системе T32 фирмы ООО ИТФ "Технофорт" (см. также страницу новостей). Данная статья может свободно (т.е. бесплатно) распространяться в электронном виде по сетям Internet и Fido при условии неизвлечения прибыли (оплата траффика не в счет), при этом данная статья не должна быть изменена. Запрещается публикация и распространение данной статьи любыми другими методами и средствами (включая поставку вместе с программным обеспечением) без письменного согласия владельцев авторских прав.

Изменения:
09.10.2001 Добавлен раздел "Конструкция DO ... WHILE ... LOOP ... ELSE ... UNLOOP THEN".
15.10.2000 для Т32-Форта версии 1.02

Содержание

Введение
Стандартные структуры управления
   Классические структуры управления
   Принципы реализации структур управления
   Принципы реализации структур управления - резюме
   Слова, реализующие структуры управления
   Слова, реализующие структуры управления - примеры использования
   Стековые эффекты и описания наиболее важных стандартных компилирующих слов
   Стандартные неклассические структуры управления
Нестандартные структуры управления
   Конструкция DO ... WHILE ... LOOP ... ELSE ... UNLOOP THEN
   Конструкция CASE ... ESAC
     Реализация
     Использование CASE ... ESAC в операторе множественного ветвления
     Использование CASE ... ESAC для сокращенного вычисления булевских выражений
     Использование CASE ... ESAC для разрешения нескольких WHILE
     Использование CASE ... ESAC для проверки нескольких условий в условном операторе без части "иначе"
     Использование CASE ... ESAC для проверки нескольких условий в условном операторе с частью "иначе"
   Временное снятие значений orig и dest со стека
   Почему не стоит запоминать глубину стека компилятора
   DONE: еще один способ организации цикла с несколькими выходами
   Рекурсивный блок START ... EMERGE
     Реализация
     Пример 1 - рекурсия
     Пример 2 - замена вспомогательного определения
   Упоминание о бэктрекинге (backtracking)

Введение

Целью введения какой-либо структуры управления в язык программирования должно быть создание такой формы организации кода, с которой удобно работать человеку. Конечной целью является удобство работы с кодом.

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

Кроме этого, выбор тех или иных структур управленния — дело вкуса. (Когда мы чувствуем, что что-то должно быть так, а не иначе, и не можем объяснить почему, мы объясняем это вкусом. Возможно, что психолог тут смог бы говорить об объективных закономерностях человеческого мышления. )

Стандартные структуры управления

Классические структуры управления

Стандартными структурами управления являются:

IF ... THEN
IF ... ELSE ... THEN
BEGIN ... WHILE ... REPEAT
BEGIN ... UNTIL
BEGIN ... AGAIN
DO ... LOOP
?DO ... LOOP
DO ... +LOOP
?DO ... +LOOP
CASE { ... OF ... ENDOF } ... ENDCASE

(Фигурными скобками '{' и '}' выделена часть, которая может повторяться 0 или более раз.) Эти структуры управления описаны в учебниках и здесь не рассматриваются.

Принципы реализации структур управления

Переходы вперед порождаются в два приема:
  1. сначала порождается команда перехода по неуказанному адресу назначения, при этом вырабатывается значение orig (origin — исходная точка), содержащее информацию о недостроенном переходе вперед, в том числе адрес команды перехода;
  2. когда адрес назначения становится известен, значение orig используется для записи адреса назначения в команду перехода.
В стандарте ANS Forth говорится, что значения orig и dest (см. далее) помещаются на стек компилятора (там он называется control-flow stack, стек потока управления). В том же стандарте говорится, что в качестве стека компилятора может использоваться стек данных. (Использование стека данных компилятором во время компиляции не мешает использовать стек данных для передачи параметров во время исполнения.) Чтобы не путать стековые комментарии времени компиляции и времени исполнения, стековые комментарии времени компиляции принято выделять меточкой "C:".

Например, 

\ IF   ( C: -- orig )
\ THEN ( C: orig -- )
: 0MAX
	DUP 0<			( C:  )
	IF			( C: orig )
		DROP 0		( C: orig )
	THEN			( C:  )
;
Слово IF порождает команду перехода неизвестно куда, а слово THEN указывает, куда именно нужно осуществлять переход. Значение orig нужно для того, чтобы слово THEN знало, какую команду нужно поправить.

Переходы назад порождаются также в два приема:

  1. сначала выясняется, куда нужен переход, и вырабатывается значение dest (destination - место назначения), содержащее информацию об адресе назначения еще не построенного перехода;
  2. затем значение dest используется для построения команды перехода по этому адресу.
Например, 
\ BEGIN ( C: -- dest )
\ UNTIL ( C: dest -- )
\ convert digits until the quotient is zero
: #S ( ud1 -- ud2 )
				( C:  )
	BEGIN			( C: dest )
		#		( C: dest )
		2DUP D0=	( C: dest )
	UNTIL			( C:  )
;
Слово BEGIN вырабатывает значение dest с информацией, по какому адресу нужно вернуться, а слово UNTIL порождает условный переход на этот адрес.

Принципы реализации структур управления — резюме

Итак, orig является описателем недостроенного перехода вперед, а dest является описателем недостроенного перехода назад. Построение команды перехода осуществляется в два приема, при этом слово, начинающее построение перехода, возвращает описатель, который надо передать слову, завершающему построение перехода. Описатели недостроенных переходов передаются через стек.

Слова, реализующие структуры управления

AHEAD ( C: -- orig ) порождает безусловный переход вперед. Адрес назначения указывается словом THEN, так что можно считать, что вся конструкция имеет вид

AHEAD ... THEN

Такое использование слова AHEAD на практике встречается крайне редко, хотя и является допустимым. Слово AHEAD предназначено для использования внутри других компилирующих слов, в том числе компилирующих слов, определяемых пользователем.

Слова CS-PICK, CS-ROLL, CS-DROP и CS-SWAP предназначены для манипулирования со значениями orig и dest. В отличие от слов, реализующих структуры управления (например, IF), эти слова не имеют признака IMMEDIATE.

На приведенных ниже стековых диаграммах символ od обозначает значение orig или dest.

CS-PICK ( C: od[u] ... od[0] u -- od[u] ... od[0] od[u] ) Скопировать u-ое значение orig или dest (нумерация начинается от вершины стека с нуля).
CS-ROLL ( C: od[u] od[u-1] ... od[0] u -- od[u-1] ... od[0] od[u] ) Переместить u-ое значение orig или dest из глубины стека на вершину (нумерация начинается от вершины стека с нуля).
CS-DROP ( C: od -- ) Убрать со стека значение orig или dest.
CS-SWAP ( C: od[1] od[2] -- od[2] od[1] ) Поменять местами на стеке два значения orig или dest.

Из этих слов CS-PICK и CS-ROLL являются стандартными, а CS-DROP предложено для включения в стандарт 2001(?) года. Слово же CS-SWAP можно определить через CS-ROLL как: 

: CS-SWAP 1 CS-ROLL ;

Слова, реализующие структуры управления — примеры использования

Пример использования слова CS-SWAP: 
: ELSE ( orig1 -- orig2 ) [COMPILE] AHEAD CS-SWAP [COMPILE] THEN ; IMMEDIATE
(Слова [COMPILE] будут объяснены позднее).

В конструкции IF ... ELSE ... THEN слово IF порождает команду условного перехода вперед (не указывая адреса назначения) и оставляет на стеке значение orig1. Слово ELSE порождает команду безусловного перехода вперед (на стеке остается orig2), меняет местами этот orig2 с оставленным словом IF значением orig1, и вызывает слово THEN, завершая начатое словом IF построение команды условного перехода. На стеке остается orig2, дожидающийся своего слова THEN. Еще раз: 

			( C:   )
	IF		( C: orig1 )
		...	( C: orig1 )
	ELSE		( C: orig2 )
		...	( C: orig2 )
	THEN		( C:   )
или, с учетом определения слова ELSE, 
			( C:   )
	IF		( C: orig1 )
		...	( C: orig1 )
	AHEAD		( C: orig1 orig2 )
	[ CS-SWAP ]	( C: orig2 orig1 )
	THEN		( C: orig2 )
		...	( C: orig2 )
	THEN		( C:   )
Теперь о словах [COMPILE]. Если мы напишем 
: foo  AHEAD CS-SWAP THEN ; IMMEDIATE
то слова AHEAD и THEN выполнятся во время компиляции, и получится слово, которое ничего не делает. При обращении к этому слову выполнится перожденный словом AHEAD переход на THEN, после чего будет выполнен выход из процедуры. Чтобы слова AHEAD и THEN скомпилировались, перед ними пишется [COMPILE].

Еще один пример. 

: WHILE     [COMPILE] IF CS-SWAP ; IMMEDIATE
: REPEAT    [COMPILE] AGAIN [COMPILE] THEN ; IMMEDIATE
Вот как это работает: 
	BEGIN		( C: dest )
		...	( C: dest )
	WHILE		( C: orig dest )
		...	( C: orig dest )
	REPEAT		( C:  )
или, более подробно, 
	BEGIN		( C: dest )
		...	( C: dest )
	IF		( C: dest orig )
	[ CS-SWAP ]	( C: orig dest )
		...	( C: orig dest )
	AGAIN		( C: orig )
	THEN		( C:  )
Нетрудно видеть, что WHILE (вызывая слово IF) начинает построение условного перехода вперед, а REPEAT (вызывая слово THEN) завершает построение команды перехода.

Стековые эффекты и описания наиболее важных стандартных компилирующих слов

IF ( C: -- orig ) Начать построение условного перехода вперед
AHEAD ( C: -- orig ) Начать построение безусловного перехода вперед
THEN ( C: orig -- ) Закончить построение перехода вперед
ELSE ( C: orig1 -- orig2 ) Выполняет слова AHEAD CS-SWAP THEN
BEGIN ( C: -- dest ) Начать построение перехода назад
UNTIL ( C: dest -- ) Закончить построение условного перехода назад
AGAIN ( C: dest -- ) Закончить построение безусловного перехода назад
WHILE ( C: od -- orig od ) Выполняет слова IF CS-SWAP
REPEAT ( C: dest orig -- ) Выполняет слова AGAIN THEN

Замечание. Фраза "выполняет слова" не означает, что приведенный далее текст можно помещать в фортовское определение. Если Вы хотите скомпилировать вызовы этих слов в текущее определение, то перед словами с признаком IMMEDIATE надо ставить [COMPILE], например, [COMPILE] IF. А если Вы хотите выполнить эти слова при компиляции текущего определения, то слова без признака IMMEDIATE надо заключить в квадратные скобки, например [ CS-SWAP ].

Стандартные неклассические структуры управления

Раз уж REPEAT является сокращением для AGAIN THEN, почему бы нам не завести цикл с двумя WHILE, завершающийся фразой AGAIN THEN THEN? Или с тремя WHILE, завершающийся фразой AGAIN THEN THEN THEN?

Ответ: стандарт языка Форт позволяет это. Приведем несколько примеров.

Пример 1. 

	BEGIN		( C: dest )
		...	( C: dest )
	WHILE		( C: orig1 dest )
		...	( C: orig1 dest )
	WHILE		( C: orig1 orig2 dest )
		...	( C: orig1 orig2 dest )
	AGAIN		( C: orig1 orig2 )
	THEN		( C: orig1 )
	THEN		( C:  )
Пример 2. То же самое, но с использованием REPEAT. 
	BEGIN		( C: dest )
		...	( C: dest )
	WHILE		( C: orig1 dest )
		...	( C: orig1 dest )
	WHILE		( C: orig1 orig2 dest )
		...	( C: orig1 orig2 dest )
	REPEAT		( C: orig1 )
	THEN		( C:  )
Пример 3. Выход из цикла возможен как через WHILE, так и через UNTIL. 
	BEGIN		( C: dest )
		...	( C: dest )
	WHILE		( C: orig dest )
		...	( C: orig dest )
	UNTIL		( C: orig )
	THEN		( C:  )
Пример 4. В зависимости от того, невыполнение какого условия привело к прекращению цикла, нужно выполнить те или иные действия. 
	BEGIN		( C: dest )
		...	( C: dest )
	WHILE		( C: orig1 dest )
		...	( C: orig1 dest )
	UNTIL		( C: orig1 )
	\ если вышли через until
		...	( C: orig1 )
	ELSE		( C: orig2 )
	\ если вышли через while
		...	( C: orig2 )
	THEN		( C:  )
	...	    \ общая часть
Пример 5. В зависимости от того, невыполнение какого условия привело к прекращению цикла, нужно выполнить те или иные действия. 
	BEGIN		( C: dest )
		...	( C: dest )
	WHILE		( C: orig1 dest )
		...	( C: orig1 dest )
	WHILE		( C: orig1 orig2 dest )
		...	( C: orig1 orig2 dest )
	AGAIN		( C: orig1 orig2 )
	THEN		( C: orig1 )
	\ если вышли через второй while
		...	( C: orig1 )
	ELSE		( C: orig3 )
	\ если вышли через первый while
		...	( C: orig3 )
	THEN		( C:  )
	...	    \ общая часть
Разумеется, AGAIN THEN можно заменить на REPEAT.

Вот что говорится в стандарте ANS Forth (American National Standard for Information Systams — Programming Languages — Forth, American National Standards Institute, 1994):

"[Известные читателю] основные структуры управления могут быть дополнены, как показано на примерах ... (см. выше — М.Г.), конструкциями BEGIN ... UNTIL и BEGIN ... WHILE ... REPEAT с добавочными WHILE. Однако, для каждого добавочного WHILE в конце структуры необходим THEN. THEN и WHILE образуют единую систему, THEN показывает, с какого места следует продолжать исполнение когда WHILE передает управление. Использование более чем одного добавочного WHILE возможно, но случается редко. Обратите внимание, что если пользователь находит такое использование THEN нежелательным, можно определить слово-синоним с более привлекательным именем."

"Дополнительные действия могут быть выполнены между словом, завершающим цикл (REPEAT или UNTIL) и словом THEN, соответствующим добавочному WHILE. Более того, если для случаев раннего завершения и нормального завершения требуются дополнительные, взаимоисключающие действия, эти действия могут быть отделены друг от друга обычным фортовским ELSE. Все действия при завершении цикла указываются после конца цикла."

Обратите внимание, что когда WHILE ставится в соответствие ELSE или THEN, REPEAT создает некоторую неправильность, больше всего заметную при сравнении со случаем BEGIN ... UNTIL. Дело в том, что число ELSE или THEN будет на единицу меньше числа слов WHILE из-за того, что REPEAT [один раз выполняет THEN, разрешая одно WHILE (здесь в стандарте небольшая путаница — М.Г.)]. Как и в вышеупомянутом случае, если пользователь находит такое несоответствие в подсчете нежелательным, REPEAT можно заменить в исходном тексте на его собственное определение (то есть, на AGAIN THEN — М.Г.)."

Нестандартные структуры управления

Конструкция DO ... WHILE ... LOOP ... ELSE ... UNLOOP THEN

Строго говоря, стандарт не позволяет использовать WHILE внутри цикла DO ... LOOP, т.к. размер значения do-sys может отличаться от размера orig и dest. В Форте T32, однако, размеры do-sys, orig и dest совпадают.

Marcel Hendrix в сообщении <9pq1s2$46g$1@news.IAEhv.nl> привел следующий пример: 


CREATE tbl  1 , 2 , 4 , 33 , 77 , 7 , 0 , 457 , 99 , 100 ,
 
: .OK? ( -- )
       10 0 DO      I CELLS tbl + @ 456 < 
             WHILE  I .
            LOOP    CR ." All values OK"
             ELSE   CR ." Bad value in tbl: " I . UNLOOP
             THEN
         CR ." Finished checking the table" ;

.OK?
0 1 2 3 4 5 6
Bad value in tbl: 7
Finished checking the table ok[Dec]
Обратите внимание на то, что если в массиве оказывается "плохой" элемент (больший 456), WHILE передает управление на код за ELSE, т.е. за пределы цикла, однако параметры цикла со стека возвратов еще не убраны. Мы можем получить значение счетчика цикла с помощью слова I, однако убирать параметры цикла нам приходится самим — мы применяем слово UNLOOP. Если бы мы забыли слово UNLOOP, это скорее всего закончилось бы ошибкой "access violation".

Разумеется, ничто не препятствует использовать слово DONE или несколько частей WHILE (включая использование CASE ... ESAC для разрешения нескольких WHILE или даже применение для этого CASE ... ELESAC ... THEN). Не увлекайтесь, однако наворотами. Подобные структуры управления нужны очень редко.

Конструкция CASE ... ESAC

Эту конструкцию предложил Wil Baden. Точнее, у него в разное время ESAC работал по-разному, а то, что описано здесь, является некоторой переработкой. По крайней мере, идеи использования слова esac в качестве имени фортовского слова, а также применения ESAC для сокращенного вычисления булевских выражений и для разрешения нескольких WHILE я узнал от него через телеконференцию comp.lang.forth. (По некоторым сведениям, это Wil Baden разработал для ANSI-стандарта спецификацию взаимодействия компилирующих слов, таких как WHILE и THEN).

Слово CASE оставляет на стеке компилятора пометку. После слова CASE на стеке компилятора может остаться любое количество значений orig (описателей перехода вперед). Слово ESAC завершит построение всех переходов, описатели которых лежат выше отметки, выполнив для каждого из этих значений слово THEN.

В конструкции
CASE { ... OF ... ENDOF } ... ESAC
ESAC отличается от ENDCASE только тем, что ENDCASE компилирует DROP:
CASE { ... OF ... ENDOF } ... ENDCASE
эквивалентно
CASE { ... OF ... ENDOF } ... DROP ESAC

Если использование конструкции CASE ... ESAC ограничено только что упомянутым случаем, то ESAC можно определить как эквивалент 0 ENDCASE. Однако, неверно было бы считать, что ESAC эквивалентно 0 ENDCASE в общем случае: внутри стандартной конструкции CASE ... ENDCASE можно использовать только OF ... ENDOF.

Слово esac (по-русски читается "езак") является словом case, написанным наоборот. Впервые этот словесный урод появился в Пересмотренном сообщении об алгоритмическом языке Алгол-68 (Ван-Вийнгаарден и др.).

Реализация 

: CASE      ?COMP   $CA5E 0 ; IMMEDIATE
: OF        ?COMP   COMPILE (OF)  >MARK ; IMMEDIATE
: ENDOF     ?COMP   [COMPILE] ELSE ; IMMEDIATE
: ESAC      ?COMP
            BEGIN   ?DUP WHILE  [COMPILE] THEN     REPEAT
            $CA5E ?PAIRS
; IMMEDIATE
: ENDCASE   ?COMP   COMPILE DROP [COMPILE] ESAC
; IMMEDIATE
: ELESAC    [COMPILE] AHEAD  2>R   [COMPILE] ESAC   2R>
; IMMEDIATE
Слово ELESAC описано ниже.

О подходах к реализации см. также в разделе "Почему не стоит запоминать глубину стека компилятора".

Использование CASE ... ESAC в операторе множественного ветвления

Конструкция выглядит так:

CASE ( n )
  значение1 ( n n1 ) OF (   ) действия-A1 ENDOF
  условие1  ( n f1 ) IF ( n ) действия-B1 ENDOF
  ...
  значениеN ( n nN ) OF (   ) действия-AN ENDOF
  условиеM  ( n fM ) IF ( n ) действия-BM ENDOF
  ( n ) действия-в-противном-случае
ESAC

в конструкции можно использовать IF и OF вперемешку,
слово OF эквивалентно фразе OVER = IF DROP,
слова ENDOF и ELSE являются синонимами,
значения должны иметь стековый эффект ( -- n ) или ( n1 -- n1 n2 ),
условия должны иметь стековый эффект ( n -- n flag ),
действия-в-противном-случае должны снять со стека значение n.

Использование CASE ... ESAC для сокращенного вычисления булевских выражений 

: CAND POSTPONE DUP POSTPONE IF POSTPONE DROP ; IMMEDIATE
: COR  POSTPONE DUP POSTPONE IFNOT POSTPONE DROP ; IMMEDIATE
Слово cand ("канд") означает conditional and, а cor ("кор") — conditional or. Или, если угодно, сокращенные and и or. Или and и or для использования внутри case. Конструкция выглядит так:

CASE условие1 CAND условие2 CAND ... условиеN ESAC

или

CASE  условие1 COR  условие2 COR ... условиеN ESAC

Каждое условие и вся конструкция в целом имеют стековый эффект ( ... -- ... f ).

Каждое следующее условие вычисляется только в том случае, если результат еще не ясен (т.е. исполнение продолжается только если CAND получает через стек истину, а COR — ложь). Условия вычисляются слева направо, приоритет операций CAND и COR один и тот же.

У Wil'а Baden'а слова CAND и COR назывались ANDIF и ORIF. Эти имена представляются мне неудачными, я никогда не могу вспомнить, что именно делают ANDIF и ORIF, а вот смысл CAND и COR вспоминается легко — это как && и || в языке Си. Недостатком имен ANDIF и ORIF является то, что они, имея внутри себя if, не поглощают, а модифицируют логическое значение. Baden'а это, впрочем, не смущает — он запросто может написать и ANDIF ... EXIT THEN, оставив читателя наедине с этой головоломкой.

Использование CASE ... ESAC для разрешения нескольких WHILE

Конструкция выглядит так: 

CASE BEGIN ... WHILE ... WHILE ... WHILE ... AGAIN ESAC
Немного непонятно, да? Давайте распишем: 
	CASE		( C: case-label )
	  BEGIN		( C: case-label dest )
		...
	  WHILE		( C: case-label orig1 dest )
		...
	  WHILE		( C: case-label orig1 orig2 dest )
		...
	  WHILE		( C: case-label orig1 orig2 orig3 dest )
		...
	  AGAIN		( C: case-label orig1 orig2 orig3 )
	ESAC		( C:  )
Действительно, ESAC разрешает все недостроенные переходы вперед. ESAC — это как несколько THEN. Точнее, как THEN для всех orig выше отметки.

Конструкция предложена W.Baden'ом в одном из сообщений из comp.lang.forth.

Использование CASE ... ESAC для проверки нескольких условий в условном операторе без части "иначе"

Конструкция выглядит так:

CASE условие1 IF условие2 IF ... условиеN IF действия ESAC

Чтобы выполнились действия необходимо, чтобы все условия оставили на стеке истину.

Использование CASE ... ESAC для проверки нескольких условий в условном операторе с частью "иначе"

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

CASE условие1 IF условие2 IF ... условиеN IF действия-если-да ELESAC действия-если-нет THEN

действия-если-да выполняются тогда, когда выполнены все условия;
действия-если-нет выполняются тогда, когда хотя бы одно условие не выполнено.

Слово ELESAC определено как 

: ELESAC ( C: case-label orig1 ... origN -- orig-new )
	[COMPILE] AHEAD  2>R   [COMPILE] ESAC   2R>
; IMMEDIATE
Здесь используется знание того, что роль стека компилятора играет стек данных, и того, что размер значения orig на стеке — две ячейки. Обратите внимание на сходство с ELSE: 
: ELSE ( orig1 -- orig2 )
	[COMPILE] AHEAD   CS-SWAP   [COMPILE] THEN
; IMMEDIATE
: ELSE ( orig1 -- orig2 )
	[COMPILE] AHEAD 2>R   [COMPILE] THEN   2R>
; IMMEDIATE
С учетом сделанных выше предположений, эти два определения слова ELSE эквивалентны. Нетрудно видеть, что ELESAC отличается от ELSE тем, что в нем вызывается ESAC там, где в ELSE вызывается THEN.

Этимология слова ELESAC. В языке Алгол-68 имеется слово esac, это записанное наоборот слово case. Слово elif образовано как else+if. По аналогии с и в память об Алголе-68, elesac=else+esac. На самом деле в таком словообразовании ничего страшного нет: в Советском Союзе do ... od для русской версии Алгола-68 вообще было переведено как цк ... кц, однако репрессирован за это никто не был.

Преимуществом конструкции CASE ... IF ... IF ... ELESAC ... THEN над CASE ... CAND ... ESAC IF ... ELSE ... THEN является то, что в первом случае вспомогательное логическое значение не используется и, стало быть, сокращается число сущностей, о которых надо думать и с которыми могут быть связаны ошибки.

Временное снятие значений orig и dest со стека

J.Brien предложил(а) следующий простой механизм: 
\ Программа стандарта ANS Forth с зависимостями от окружения:
\ - компилирующие слова оставляют orig и dest на стеке данных;
\ - размер значений orig и dest - два элемента стека.
CREATE temp 2 CELLS ALLOT
: >: temp 2! ;   IMMEDIATE
: <: temp 2@ ;   IMMEDIATE
Пример использования: 
: vvv
    DUP 2 AND
    IF
            DUP 1 AND
            IF
                    DUP 4 AND
                    IF
                          ." yes"
                    ELSE
                    >:
            THEN
    THEN
                          ." no"
                    <:
                    THEN
    .
;
То же самое в записи "структуры управления справа" (такая запись всегда более компактна и читается не хуже — если к ней привыкнуть): 
: vvv
    DUP 2 AND                     IF
    DUP 1 AND             IF
    DUP 4 AND     IF
        ." yes"   ELSE >: THEN    THEN
        ." no" <: THEN
    .
;
Понять такой пример можно только если отойти от понятия условного оператора и вспомнить, что IF компилирует условный переход вперед, THEN указывает адрес назначения такого перехода, связь между ними осуществляется через значения orig, а ELSE — это AHEAD [ CS-SWAP ] THEN.

Если мы вспомним все это, становится понятным, что каждый IF в случае неудачи проверки передает управления на соответствующий THEN (в последнем примере IF располагается над соответствующим ему THEN). Фраза ELSE :> компилирует безусловный переход вперед и разрешает находящийся над ней IF в предыдущей строке; значение orig прячется в переменной temp. Фраза <: THEN достает значение orig из переменной temp и разрешает соответствующую команду перехода вперед.

Мы определим слова
[>Z] ( C: ... orig|dest -- ... ) Спрятать orig|dest. Слово с признаком immediate.
[Z>] ( C: ... -- ... orig|dest ) Достать ранее спрятанное словом [>Z] значение orig|dest. Слово с признаком immediate.

Почему такое имя. Z — последняя буква в алфавите, так что [>Z] означает "запрятать подальше", а [Z>], соответственно, "вытащить оттуда".

Реализация предполагает, что:

На самом деле последнее предположение является достаточно серьезным ограничением: некоторые реализации CASE ... ENDCASE используют глубину стека для управления циклом, разрешающим ссылки вперед. Понятно, что если структура управления написана в предположении, что все изменения глубины стека связаны с нею и только с нею, то правильно работать с [>Z] и [Z>] она не будет. T32 не использует глубину стека для управления разрешением ссылок в ESAC или других структурах управления. В общем же случае для хранения значений orig|dest надо заводить отдельный стек. 
\ file: Z.FTH

\ ANS Forth code snippet requiring ROLL and ?DO from CORE EXT
: -ROLL  DUP 0 ?DO DUP >R ROLL R> LOOP DROP ;

\ ANS Forth code snippet
\ with the environmental dependencies that:
\ - control-flow stack is the same as data stack
\ - orig's and dest's are two-cell values
\ - control-flow stack elements are not bound to stack depth
\ - control structures do not remember stack depth
: [>Z] ( C: ... orig|dest -- orig|dest ... )
        DEPTH 1- -ROLL
        DEPTH 1- -ROLL
; IMMEDIATE
: [Z>] ( C: orig|dest ... -- ... orig|dest )
        DEPTH 1- ROLL
        DEPTH 1- ROLL
; IMMEDIATE


\ ANS Forth code requiring [>Z] and [Z>] defined above

: vvv
        DUP 1 AND                              IF
        DUP 2 AND                        IF
        DUP 4 AND                  IF
          ." OK "       AHEAD [>Z]
                                   THEN  THEN  THEN
          ." NO "
                        [Z>] THEN
        U.
;

\ 1 vvv
\ NO 1  ok
\ 2 vvv
\ NO 2  ok
\ 4 vvv
\ NO 4  ok
\ 3 vvv
\ NO 3  ok
\ 7 vvv
\ OK 7  ok
\ 6 vvv
\ NO 6  ok
С помощью этих слов слово ELESAC можно определить как 
: ELESAC    [COMPILE] AHEAD  [COMPILE] [>Z]  [COMPILE] ESAC  [COMPILE] [Z>]
; IMMEDIATE

Почему не стоит запоминать глубину стека компилятора

Некоторые структуры управления допускают произвольное число элементов, например CASE ... ENDCASE допускает произвольное число частей OF ... ENDOF. Одно из слов (чаще всего последнее, в нашем примере ENDCASE) разрешает произвольное число ссылок вперед (или назад). Разумеется, такая конструкция должна каким-то образом отличать "свои" элементы стека управления от "чужих".

Стандарт ANS Forth этого вопроса вообще не затрагивает, оставляя все вопросы реализации на усмотрение разработчиков.

Наиболее популярны два способа разметки стека — с помощью вспомогательных значений и путем запоминания глубины стека компилятора.

В стандарте ANS Forth имеется слово CS-ROLL. Это слово позволяет поднять значение orig|dest из глубин стека компилятора на вершину.

Если структура управления, такая как CASE ... ENDCASE, запоминает исходную глубину стека компилятора, последствия применения CS-ROLL непредсказуемы. Точнее, до некоторой степени предсказуемы, поскольку ясно, что взамен "импортированного" из-под отмеченной глубины значения под отметкой окажется одно из принадлежащих конструкции значений orig|dest. Это приведет к появлению неочевидной ошибки.

В случае же использования в качестве отметки положенного на стек компилятора значения, отметка "опускается" вместе с остальными значениями. Другое дело, что если размер отметки отличается от размера значения orig|dest (например, отметка — целое число, а orig — адрес и число), пользоваться словом CS-ROLL нельзя. С другой стороны, если мы знаем, что в качестве стека компилятора используется стек данных и знаем размеры значений, мы можем пользоваться словом ROLL (стандарт рекомендует в таком случае задокументировать сделанные предположения об архитектуре системы).

Другим примером конструкции, нарушающей предположение о неизменности расположения значений на стеке компилятора, являются слова [>Z] и [Z>].

DONE: еще один способ организации цикла с несколькими выходами

J.Brien предлагает следующий способ организации цикла с несколькими выходами: 
: DONE POSTPONE ELSE CS-SWAP ; IMMEDIATE
Возможны следующие варианты использования: 
  1. 
	CASE
	 BEGIN
		...
		... IF .... DONE
		... IF .... DONE
		... IF .... DONE
		...
	 AGAIN
	ESAC
    После того, как выполняется код между словами IF и DONE, выполняется выход из цикла. Для разрешения ссылок вперед используется CASE ... ESAC. 
  2. 
	BEGIN
		...
		... IF .... DONE
		... IF .... DONE
		... IF .... DONE
		...
	AGAIN
	THEN THEN THEN
    То же самое, но для разрешения ссылок вперед используются THEN. 
  3. 
	BEGIN
		... IF .... DONE ...
	REPEAT
    Последний пример эквивалентен конструкции 
    	BEGIN
		... 0= WHILE ...
	REPEAT
	....
    и отличие состоит только в подчеркивании того, что действия, обозначенные четырьмя точками, логически относятся к циклу.

Рекурсивный блок START ... EMERGE

Следует отметить, что:
  1. структуры управления не исчерпываются системами переходов
  2. стандарт ANS Forth не позволяет выйти за рамки систем переходов.
Примером структуры управления, которая не может быть реализована через переходы, является рекурсивный блок START ... EMERGE. (Другим примером является бэктрекинг (backtracking, метод откатов).) Структура имеет вид:

START { ... DIVE ... } ... EMERGE

Слова START и EMERGE обозначают границы блока, DIVE обозначает рекурсивный вызов блока. Слово DIVE# ( C: ... "n" -- ... ) обеспечивает вызов n-го объемлющего блока (DIVE# 1 эквивалентно DIVE).

Реализация 

\ : (CALL)   R@ REF+ >R< REF@ >R ;
\ : (START)  R@ REF@ >R< REF+ >R ;
: START     ?COMP COMPILE (START) >MARK <MARK 201 ; IMMEDIATE
: EMERGE    ?COMP 201 ?PAIRS CS-DROP COMPILE EXIT >RESOLVE ; IMMEDIATE

\ ищем #-ый набор (  forward  backward 201 ),
\ при этом addr после (START)
: (DIVE#) ( an .. a1 # --> an a1 )
    DEPTH 5 >                                               IF
    DEPTH 5 - 1+ 1                                  DO
    ( an .. a1 # )                          CASE
    I PICK 201 =                            IF
    I 1+ PICK backward =                    IF
    I 3 + PICK forward =                    IF
    I 2 + PICK   I 4 + 1+ PICK REF+  =      IF
    I 4 + PICK REF- TOKEN@ ['] (START) =    IF
    1- DUP 0=                               IF          \ # -- счетчик
            DROP        ( одно значение сброшено!)
            COMPILE (CALL)
            I 1+ PICK   ( это значение номер i+2 )
            I 1+ PICK   ( это значение номер i+1 )
              <RESOLVE
            UNLOOP EXIT                     ESAC    LOOP    THEN
    1 ABORT" more than nesting level" ;

: DIVE ?COMP 1 (DIVE#) ; IMMEDIATE
: DIVE# ( "n" -- )
        ?COMP
        S$GETWORD S$NUMBER? -1 <> ABORT" single number expected"
        D>S (DIVE#)
; IMMEDIATE
\ DIVE# n calls the n-th enclosing block.
\ DIVE# 1 is equivalent to DIVE .

Пример 1 — рекурсия

Приведем пример на использование рекурсивного блока. Слово fib. ( i -- ) распечатывает i-ое число Фибоначчи. 
: fib. START DUP 3 < IF DROP 1 EXIT THEN DUP 1- DIVE SWAP 2 - DIVE + EMERGE . ;
: tst 11 1 DO I fib. SPACE LOOP ;

DECIMAL tst
1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987   ok

Пример 2 - замена вспомогательного определения 

: ttt START R@ @ R> CELL+ >R EMERGE [ 6 , ] . ;
 ok
ttt
6  ok
В этом примере текст START R@ @ R> CELL+ >R EMERGE играет роль слова LIT. 
: tttt LIT [ 6 , ] . ;
 ok
tttt
6  ok
: newLIT R@ @ R> CELL+ >R ;
 ok
: vvv newLIT [ 8 , ] . ;
 ok
vvv
8  ok

Упоминание о бэктрекинге (backtracking)

Было бы неправильно совсем не упомянуть бэктрекинг в тексте с таким заголовком. Однако обзор методов реализации бэктрекинга занял бы больше места, чем весь остальной текст. Кроме того, бэктрекинг — вещь довольно специфическая. Так что в этой версии этой статьи бэктрекинг не рассматривается совсем. Отметим только, что для реализации бэктрекинга требуется манипулирование адресами возврата.

Приведем только несколько ссылок:

A BNF PARSER IN FORTH by Bradford J. Rodriguez, Ph.D.

НОВЫЕ СТРУКТУРЫ УПРАВЛЕНИЯ В ЯЗЫКЕ FORTH дипломная работа Гасаненко М.Л., к.ф.-м.н., и другие статьи про бэктрекинг.

М.Л.Гасаненко