Язык Форт и его реализации

         

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


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

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

Стандарт языка предусматривает ряд слов для построения условных операторов и циклов в некотором конкретном виде. Эти слова используются внутри определений через двоеточие и разделяют тело определения на отрезки. Действия, соответствующие словам из этих отрезков, выполняются, не выполняются или выполняются многократно в зависимости от условий, проверяемых во время выполнения данного определения. Условные операторы и циклы могут свободно вкладываться друг в друга.

Условный оператор строится с помощью слов:

IF А ---> (исполнение) ELSE ---> (исполнение) THEN ---> (исполнение)

Внутри определения через двоеточие отрезок текста IF <часть-то> ELSE <часть-иначе> THEN задает следующую последовательность действий. Слово IF (если) снимает значение с вершины стека и рассматривает его как логическое. Если это ИСТИНА (любое ненулевое значение), то выполняется часть «то» — слова, находящиеся между IF и ELSE, а если ЛОЖЬ (равно нулю), то исполняется часть «иначе» — слова между ELSE и THEN. Сами слова ELSE (иначе) и THEN (то) играют роль ограничителей для слова IF и самостоятельной семантики не имеют. Часть «иначе» вместе со словом ELSE может отсутствовать, и тогда условный оператор имеет сокращенную форму IF <часть-то> THEN.
Если логическое значение, снимаемое со стека словом IF, ИСТИНА, то выполняются слова, составляющие часть «то», а если ЛОЖЬ, то данный оператор не выполняет никаких действий. Обратите внимание, что условие для слова IF вычисляется предшествующими словами.

Для примера рассмотрим определение слова ABS, вычисляющего абсолютное значение числа:

: ABS ( A --->абс A) DUP 0< IF NEGATE THEN ;

Слово DUP дублирует исходное значение, следующее слово 0< проверяет его знак, заменяя копию на логическое значение — результат проверки. Слово IF снимает со стека этот результат, и если это ИСТИНА, то лежащее на стеке исходное отрицательное значение словом NEGATE заменяется на противоположное.

Еще пример: стандартное слово ?DUP дублирует верхнее значение, если это не ноль, и оставляет стек в исходном состоянии, если на вершине ноль:

: ?DUP ( A ---> A,A/0 ) DUP IF DUP THEN ;

В спецификации данного слова косая черта разделяет два варианта результата, который это слово может оставить на стеке. Примером использования полного условного оператора может служить определение слова S>D, расширяющего исходное значение до значения двойной длины распространением знакового разряда:

: S>D ( A ---> AA ) DUP 0< IF -1 ELSE 0 ТНЕN ;

Это слово добавляет в стек -1, если число на вершине стека отрицательно, или 0 в противном случае. Таким образом, выполняется распространение знакового разряда на старшую половину значения двойной точности.

В стандарт языка Форт включены циклы с условием и циклы со счетчиком. Циклы первой группы образуются с помощью слов

BEGIN ---> (исполнение) UNTIL A ---> (исполнение) WHILE A ---> (исполнение) REPEAT ---> (исполнение)



и имеют две формы:

BEGIN <тело> UNTIL BEGIN <тело-1> WHILE <тело-2> REPEAT

В обоих случаях цикл начинается словом BEGIN (начать), которое служит открывающей скобкой, отмечающей начало цикла, и во время счета не выполняет никаких действий.

Цикл BEGIN-UNTIL называется циклом с проверкой в конце.


После исполнения слов, составляющих его тело, на стеке остается логическое значение — условие завершения цикла. Слово UNTIL (пока не) снимает это значение со стека и анализирует его. Если это ИСТИНА (не нуль), то исполнение цикла завершается, т.е. далее будут исполняться слова, следующие за UNTIL, а если это ЛОЖЬ (нуль), то управление возвращается к началу цикла от слова BEGIN. Например, определение слова, вычисляющего факториал, может выглядеть так:

: ФАКТОРИАЛ ( N ---> N! ВЫЧИСЛЕНИЕ N ФАКТОРИАЛ) DUP 2 < IF DROP 1 ( 1 ЕСЛИ N<2, ТО N!=1) ELSE ( N ИНАЧЕ ) DUP ( S,K S=N,K=N ) BEGIN ( S,K ) 1- ( S,K' K'=K-1 ) SWAP OWER ( K',S,K' ) * SWAP ( S',K' S'=S*К' ) DUP 1 = ( S',K',К'=1 ) UNTIL ( S',1 S'=N! ) DROP THEN ; ( N! )

Как и ранее, в комментариях, сопровождающих каждую строчку текста, мы указываем значения, которые остаются на вершине стека после ее исполнения. Такое документирование облегчает понимание программы и помогает при ее отладке.

Цикл с проверкой в начале BEGIN-WHILE-REPEAT используется, когда в цикле есть действия, которые не надо выполнять в заключительной итерации. Исполнение слов, составляющих его тело-1, оставляет на стеке логическое значение — условие продолжения цикла. Слово WHILE (пока) снимает это значение со стека и анализирует его. Если это ИСТИНА (не нуль), то исполняются слова, составляющие тело-2 данного цикла до ограничивающего слова REPEAT (повторять), после чего вновь исполняется тело-1 от слова BEGIN. Если же значение условия ЛОЖЬ (нуль), то исполнение данного цикла завершается и начинают выполняться слова, следующие за REPEAT. Заметьте, что в отличие от цикла BEGIN-UNTIL, значение ИСТИНА соответствует продолжению цикла. Для примера рассмотрим программу вычисления наибольшего общего делителя по алгоритму Евклида:

: НОД ( A,B ---> C:НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ) 2DUP < IF SWAP THEN ( ТЕПЕРЬ A>=B ) BEGIN DUP ( A,B,B ) WHILE ( ПОКА B НЕ НОЛЬ ) 2DUP MOD ( A,B,C:ОСТАТОК ) ROT ( B,C,A ) DROP ( A',B' A'=B,B'=C ) REPEAT DROP ; ( НОД )



Для организации циклов с целочисленной переменной — счетчиком цикла — используются слова

DO A,B ---> (исполнение) LOOP ---> (исполнение) +LOOP A ---> (исполнение) I ---> A (исполнение) J ---> A (исполнение) LEAVE ---> (исполнение)

Такие циклы записываются в одной из следующих двух форм: DO <тело> LOOP или DO <тело> +LOOP. В обоих случаях цикл начинается словом DO (делать), которое снимает со стека два значения: начальное (на вершине стека) и конечное (второе сверху) — и запоминает их. Текущее значение счетчика полагается равным начальному значению, после чего исполняются слова, составляющие тело цикла. Слово LOOP увеличивает текущее значение счетчика на единицу и проверяет условие завершения цикла. В отличие от него, слово +LOOP прибавляет к текущему значению счетчика значение шага, которое вычисляется на стеке телом цикла и рассматривается как число со знаком. В обоих случаях условием завершения цикла является пересечение границы между A–1 и A при переходе от прежнего значения счетчика к новому (направление перехода определяется знаком шага), где A — конечное значение, снятое со стека словом DO.

Если пересечения не произошло, то тело цикла исполняется вновь с новым значением счетчика в качестве текущего.

Такое определение позволяет рассматривать исходные параметры цикла (начальное и конечное значения) и как числа со знаком, и как числа без знака (адреса). Например, текст 10 0 DO <тело> LOOP предписывает выполнять тело цикла 10 раз со значениями счетчика 0, 1, 2, ..., 9, а в случае 0 10 DO <тело> LOOP тело цикла будет исполнено 65 526 раз со значением счетчика 10, 11, ..., 32767, -32768, -32767, .... -1 или (что то же самое) со значениями счетчика 10, 11, ..., 65535. В то же время цикл 0 10 DO <тело> -1 +LOOP будет исполняться 11 раз (а не 10) со значениями счетчика 10, 9, ..., 0, поскольку пересечение границы между -1 и 0 произойдет при переходе от значения счетчика 0 к следующему значению — -1.


Цикл 10 0 DO <тело> -1 +LOOP будет исполняться 65  527 раз со значениями счетчика 0, -1, -2, ..., -32768, 32767, ..., 10 или (что то же самое) 0, 65535, 65534, ..., 10. Таким образом, цикл со счетчиком всегда выполняется хотя бы один раз. Некоторые реализации предусматривают слово ?DO, которое не исполняет тело цикла ни разу, если начальное и граничное значения оказались одинаковыми.

Внутри тела цикла слово I кладет на стек текущее значение счетчика. Например, следующее определение вычисляет сумму квадратов первых N натуральных чисел:

: SS2 ( N ---> S:СУММА КВАДРАТОВ ОТ 1 ДО N) 0 SWAP ( 0,N S[0]=0 ) 1+ 1 ( S[0],N+1,1 ) DO I ( S[I-1],I ) DUP ( S[I] S[I]=S[I-1]+I*I) LOOP ; ( S[N] )

Слово LEAVE (уйти), употребленное внутри цикла, вызывает прекращение исполнения его тела; управление переходит к словам следующим за словом LOOP или +LOOP.

В программировании часто применяется конструкция цикл в цикле. Чтобы во внутреннем цикле получить текущее значение счетчика объемлющего цикла, используется слово J: DO ... I ... DO ... I ... J ... LOOP ... I ... LOOP. Первое вхождение слова I дает текущее значение счетчика внешнего цикла. Следующее вхождение I дает уже значение счетчика внутреннего цикла. Чтобы получить счетчик внешнего цикла, надо использовать слово J.

По выходе из внутреннего цикла доступ к этому значению вновь дает слово I. Этим слова I и J отличаются от переменных цикла в традиционных языках программирования. Некоторые реализации предусматривают еще и слово К для доступа к счетчику третьего объемлющего цикла.


Содержание раздела