Организация циклов
Возможно, одним из наиболее полезных свойств компьютера является его способность многократно и с очень большой скоростью повторять операции. Циклы составляют часть программы, в которой повторяются одни и те же действия. Почти в каждой программе так или иначе применяются циклы. Как вы увидите в гл. 15, сам Форт работает как бы в бесконечном цикле.
В предыдущих главах мы пользовались наиболее распространенной формой цикла типа DO-LOOP. Однако мы еще не использовали все его возможности. Кроме того, существуют и другие типы циклов с еще большими возможностями, например циклы типа BEGIN...UNTIL, которые вызывают повторение программы только до тех пор, пока не будет удовлетворяться некоторое определенное условие. Сначала мы рассмотрим, как работают счетные циклы DO-LOOP и некоторые их применения.
Циклы типа DO-LOOP
Вы уже знакомы с простейшей формой счетного цикла: : 10LOOPS 10 0 DO 5 . LOOP , Слово 10LOOPS при исполнении напечатает на экране число 5 10 раз (т.е. от 0 до 9), а когда будет достигнут счет 10, циклическая программа прекратится. Между прочим, так же, как и конструкцию IF...THEN, счетный цикл можно использовать только внутри определений через двоеточие. По-видимому, самый простой счетный цикл, имеющий практическое применение, это : PAUSE 2790 0 DO LOOP ; ( Пауза) который приостанавливает программу, пока исполняется пустой цикл. Таким образом, слово PAUSE приостанавливает программу на время 2790 циклов или на 1/10 с на IBM РC в версии MMSFORTH; слово PAUSE может быть вставлено в другой цикл для получения еще больших задержек. (Если вы привыкли к языку Бейсик, то для вас будет неожиданностью, насколько быстрее выполняются циклы в Форте.) Очень важным моментом является то, что циклы могут вставляться в другие циклы. Если вы определите слова : 1LOOP 5 0 DO ." Внутренний цикл" LOOP ; и : 2LOOP 5 0 DO CR ."Внешний цикл" CR CR 1LOOP LOOP ; тогда каждый раз, когда будет исполняться цикл в программе 2LOOP, она напечатает в начале строки свое сообщение "Внешний цикл", сделает два перевода строки, а затем напечатает сообщение из программы 1LOOP 5 раз, пока будет исполняться эта программа; так будет повторяться 5 раз, следовательно, сообщение "Внутренний цикл" будет напечатано 25 раз.
Циклы, находящиеся внутри других циклов, называются вложенными; глубина вложенности может быть такой, какой она практически потребуется. Ради интереса попробуем, пользуясь циклами, сравнить скорость работы языка Форт по отношению к Бейсику. Цифры, приведенные здесь, относятся к IBM PC для МMSFORTH и версии Бейсика фирмы Microsoft. Первая программа цикла на Бейсике 10 DEFINT I,C 20 FOR I=1 ТО 10000 30 NEXT I выполняется 11.5 с (заметьте, что для корректности по отношению к Бейсику мы пользуемся целыми числами). Если мы напишем программу : TEST 10000 0 DO LOOP : то она будет исполняться слишком быстро, поэтому для определения времени ее работы мы будем вынуждены включить ее во вложенный цикл: : TESTA 10 0 DO TEST LOOP ; который исполняется в течение 3.6 с, поэтому слово TEST, которое повторяет пустой цикл 10000 раз, исполняется за 0.36 с. Таким образом, счетный цикл на Форте работает в 32 раза быстрее, чем на Бейсике. Рассмотрим теперь некоторые арифметические операции. Если мы вставим 25 C=10 в первую программу, то ее исполнение удлинится до 17.5 с. Программа на Форте, эквивалентная ей в первом приближении: : TEST 10000 0 DO 10 DROP LOOP ; исполняется за 0.71 с. Теперь в строке 25 на Бейсике поместим 25 С=10+10 тогда выполнение программы займет 23.1 с. Следовательно, исполнение 10000 сложений целых чисел занимает 23.1 - 17.5, или 5.6 с. На Форте для исполнения программы : TEST 10000 О DO 10 10 + DROP LOOP : потребуется 1.13 с, т.е. 1.13 - 0.71 " 0.42 с на 10000 операций сложения. Следовательно, Форт быстрее Бейсика по операции сложения в 13 раз. Аналогичное испытание показывает, что для операции умножения на Бейсике требуется 5.7 с, а на Форте - 0.7 с, т.е. в 8 раз меньше. Другими словами, для операций с целыми числами Форт работает примерно в 8 - 30 раз быстрее, чем Бейсик. Еще более интересно сравнить операции над числами с плавающей запятой для процессора Intel 8087. При замене строки 25 на 25 D=10E10 программа работает 21.4 с; если а строке 25 будет 25 D=10Е10+10Е10.
то программа исполнится уже за 28.2 с, т.е. время исполнения 10000 сложений чисел с плавающей запятой составляет 28.2 - 21.4 = 6.8 с. Программа на Форте : TEST 10000 0 DO % 10Е10 FDROP LOOP ; потребует 0.79 с, а программа : TEST 10000 0 DO % 1Е10 % 1Е10 F+ FDROP LOOP ; исполняется за 1.23 с, т.е. 10000 сложений чисел с плавающей запятой происходят за 1.23 - 0.79 = 0.44 с, в 15.5 раза быстрее, чем на Бейсике, и менее чем на 5% медленнее операции сложения целых чисел на Форте. Умножение на Бейсике занимает 16.8 с, на Форте - 0.46 с, т.е. в 16 раз быстрее и фактически на 34% быстрее, чем умножение целых чисел на Форте (мы уже говорили в гл. 4, что некоторые операции с плавающей запятой на процессоре 8087 выполняются быстрее, чем с целыми числами). Извлечение квадратного корня на Бейсике производится за 14.5 с, а на Форт - за 0.87 с, т.е. в 39 раз быстрее. На самом деле эти сравнения не очень корректны по отношению i Форту, поскольку последний совместно с процессором 8087 имеет в 100 раз больший диапазон представления чисел и более чем в 4 раза лучшую точность по сравнению с числами одинарной точности в языке Бейсик. Если на Бейсике производится умножение чисел двойной точности, то фактор преимущества в скорости для Форта равен 48, и это, несмотря на больший диапазон и повышенную точность. Умножение на современной быстродействующей универсальной ЭВМ типа CDC Cyber выполняется в 20 раз быстрее, чем на Форте с микропроцессором 8087. Однако затратив менее 10i долл., можно увеличить скорость ваших вычислений больше, чем при переходе на универсальна ЭВМ стоимостью около миллиона долларов.
Возвращаясь из нашего экскурса, мы должны рассмотреть индекс счетного цикла. Индекс представляет собой текущее значение счетчика, начинающего счет с нижнего значения и при каждое повторении цикла изменяющегося на заданную величину приращения. (Индекс помещается на вершину стека словом I, наименование которого происходит от Index, или, если вам больше нравится, указывающего, что выполняется I-й цикл.) Таким образом,программа : SHOW-INDEX 10 5 DO I .
LOOP ; напечатает на экране 5 6 7 8 9
Заметьте, что числа следуют только до 9. Так происходит потому, что индекс цикла инкрементируется словом LOOP и, когда он достигает крайнего значения, в данном случае 10, происходит вы ход из цикла без возврата к слову DO еще раз. Очевидно, что если повторение исполнения цикла производится с помощью DO, то в стеке должны быть по крайней мере два числа. Верхнее число служит начальным значением индекса цикла, с которым происходит вход в цикл. Второе число на стеке - это предельное значение параметра цикла, по достижении которого с помощью инкрементирования индекса происходит выход из цикла. Если мы определили слово как ; SHOW-INDEX 7 2 DO I . LOOP ; то оно выдаст на экране 2 3 4 5 6 Обе последние программы повторяются по 5 раз, но дают разные результаты вследствие различных начальных и конечных значений индекса цикла. Задание диапазона изменения индекса - это важный момент, потому что значение индекса часто используется для вычислений внутри цикла. Имеются некоторые отличия в способе завершения счетного цикла в стандартах Форт-79 и Форт-83. Рассмотрим слово : 1LOOPTEST 5 5 DO I . LOOP ; в Форт-79 слово 1LOOPTEST попросту напечатает число 5 и программа остановится, напротив, в Форт-83 вы увидите 5 6 7 ... 32766 32767 -32768 -32767 ... -1 0 1 2 3 4 т.е. будут напечатаны 65535 чисел. Теперь рассмотрим пример другой программы: : 2LOOPTEST -32766 32766 DO I U. LOOP ; которая в Форт-79 также напечатает только одно число 32766 и остановится, в то время как в Форт-83 она выдаст 32766 32767 32768 32769
Согласитесь, что эти различия приводят в замешательство.
Что же происходит? Что касается Форт-79, то объяснение простое. Слово LOOP добавляет 1 к индексу и после этого проверяет, не нужно ли выйти из цикла, если индекс достиг или превысил величину предельного значения параметра цикла, рассматриваемого как число со знаком. Поэтому обе тестовые программы в Форт-79 печатают только одно число - начальное значение индекса и прекращают работу.
Что касается Форт-83, то его реакция более хитроумная. Он принимает решениe выйти из цикла не на основании факта равенства или превышения индексом предельного значения параметра цикла, а, скорее, на основании факта перехода от состояния, когда предел не был достигнут, к состоянию, когда индекс достигает значение предела. В первом случае 1LOOPTEST, инкрементируя индекс, изменяет его с 5 на 6, поэтому необходимое изменение состояния не происходит, следовательно, цикл должен продолжаться со значениями индекса 7, 8 и т.д. После достижения индексом значения 32767 добавление единицы приводит к изменению знака числа, так как число без знака 32768 представляет собой число со знаком -32768, но опять же изменение состояния не происходит. Каждый раз при исполнении цикла индекс увеличивается на 1 до тех пор, пока он не достигнет значения 4, а затем изменится на 5, тут и происходит выход из цикла.
Действие второй тестовой программы в Форт-83 можно проанализировать аналогичным образом, Добавление единицы к 32766 приводит к превышению предела, но переход от состояния индекса ниже предела к состоянию, когда он равен пределу или превышает его, не происходит, поэтому цикл продолжается до тех пор, пока не произойдет переход от -32767 к -32766 или, если рассматривать числа без знака, от 32769 к 32770. Это как раз необходимый переход состояния, поэтому цикл прекращается. Важно помнить, что если в Форт-83, начальное значение индекса равно или превышает предельное значение, то цикл будет продолжаться до тех пор, пока индекс не приблизится к пределу снизу. Форт-83 работает именно таким образом, в особенности если используются числа без знака; это обеспечивает возможность обращения с помощью индексации циклов ко всем 64К ячейкам памяти.
Следует также помнить о том, что Форт-79 выходит из цикла, принимая во внимание значение числа со знаком, поэтому программа : 3LOOPTEST 3 -3 DO I . I U. LOOP ; выдает -3 65533 -2 65534 -1 65535 0 0 1 1 2 2 Очевидно при первом инкрементировании величина индекса без знака превышает значение предела, но слово LOOP следит за условием с учетом знака.
Форт- 83 даст такой же результат, но не из-за того, что рассматривается число со знаком или без знака, а потому что происходит переход значения индекса от величины ниже предела к величине, равной пределу. Эти тонкости прекращения цикла могут быть особенно обескураживающими в случае, когда начальное значение индекса равно пределу, в частности в языках Бейсик, Фортран и других. Например, программа на Бейсике 10 FOR I = 5 ТO 5 20 PRINT I 30 NEXT I не будет ничего делать, потому что индекс цикла равен пределу и тело цикла игнорируется (операторы PRINT I и NEXT I никогда не исполняются). С другой стороны, мы видели, что в программе 1LOOPTEST, которая также начинается со значения индекса, равного пределу, слова внутри цикла исполняются, печатая 5, хотя зачастую это нежелательно. Хуже того, программа 1LOOPTEST в Форт-83 исполняется 65535 раз, пока не произойдет переход от 4 к 5. Очевидно, что вы этого вовсе не хотели. Можно избежать неудобств с помощью конструкции IF-THEN. Если не исключена возможность, что в цикле типа DO...LOOP начальное значение индекса больше или равно пределу, то вы можете защитить программу, например, таким образом: ... OVER OVER >
IF DO ( тело цикла) LOOP THEN ...
Если начальное значение индекса больше предела, цикл не будет исполняться. Циклы в Форте не так изящны, как в Бейсике, но, как вы уже видели, они работают существенно быстрее. Следует иметь в виду еще одну деталь: слово I может встречаться только в определениях слов, которые включают в себя циклы DO-LOOP. Поэтому не будут работать следующие определения: : IN-LOOP I . ; : TRY-LOOP 5 0 DO IN-LOOP LOOP ; Слово IN-LOOP выдаст вам какую-нибудь бессмыслицу. Во многих версиях Форта предусмотрено необязательное слово I', которое должно работать следующим образом. Если мы переопределим слова предыдущего примера: : IN-LOOP I' . ; : TRY-LOOP 5 0 DO IN-LOOP LOOP : то слово IN-LOOP напечатает значение индекса цикла, т, е. что мы хотели бы увидеть в первом примере. Таким образом, слово I' возвращает значение индекса цикла, если оно используется внутри слова, которое вызывается из цикла.
В большинстве реализации Форта слово I' исполняется только в том случае, если оно используется в слове, вызываемом непосредственно из цикла, поэтому нельзя написать программу : 2IN-LOOP I' . ; : 1IN-LOOP 2IN-LOOP ; : TRY-LOOP 5 0 DO 1IN-LOOP ; И поэтому TRY-LOOP выдает что-нибудь несуразное. Причину этого вы поймете в следующей главе. В большинстве версий слово I' вызывается непосредственно внутри цикла, где оно выдает предельное значение индекса цикла. Так, программа : SHOWLIMIT 5 0 DO I . I' . CR LOOP ; напечатает 0 5 1 5 . . . 4 5
Для получения значений индексов вложенных циклов используются еще два слова. Если слово I выдает значение индекса внутреннего цикла, то J возвращает значение индекса внешнего по отношению к нему цикла, а К - индекс следующего внешнего цикла. (Слово J входит в стандарты Форт-79 и Форт-83, а слово К предусмотрено только в некоторых версиях.) В качестве примера рассмотрим программу : TEST 5 0 DO 5 0 DO 5 0 DO I . J . К . CR LOOP LOOP LOOP ; Запустив слово TEST, вы получите на экране 0 0 0 1 0 0 2 0 0 . . . 4 0 0 0 1 0 1 1 0 . . . 0 0 1 1 0 1 . . . 4 4 4
Возможность пользоваться вложенными циклами и их индексами обеспечивает широкий диапазон применений, одним из которых является обращение с двумерными массивами. Пусть у вас имеется матрица MATRIX размерности 5х5 в версии MMSFORTH. Программа .MATRIX (печать_матрицы), которую мы приводим, напечатает эту матрицу по строкам с аккуратно оформленными столбцами: : .MATRIX 5 0 DO 5 0 DO I J MATRIX @ 6 .R LOOP CR LOOP ;
Внешний цикл обеспечивает переход от строки к строке, в то время как внутренний цикл перебирает элементы матрицы в строке, извлекает их содержимое и печатает значения элементов матрицы, производя выравнивание их вправо в поле шириной шесть позиций. С помощью циклов можно сделать еще многое, но, прежде чем продвигаться дальше, рассмотрим еще один пример, а потом перейдем к упражнениям. Циклы очень важны в программировании, но мы можем только слегка затронуть рассмотрение их возможностей.
Другие примеры мы приведем в следующих главах. Давайте попробуем написать программу, которая возводит в степень второе число в стеке, при этом показатель степени указывается числом на вершине стека. Таким образом, 2 4 ** должно выдать число 16. Вот эта программа: : ** ( n1 n2 - n1^n2 ) OVER SWAP 1- 0 DO OVER * LOOP SWAP DROP ; Рассмотрим возведение числа 2 в 4-ю степень. Если числа 2 и 4 находятся в стеке, то последовательность операций OVER SWAP 1- возвратит в стек 223. Затем 0 DO запустит цикл, который будет исполняться 3 раза, а в стеке останется число 2. Затем после каждого исполнения цикла в стеке будет наблюдаться следующее: 2 4 2 8 2 16 Предложение SWAP DROP производит уничтожение в стеке числа 2, которое остается после завершения цикла. Данный пример показывает три общих проблемы применения циклов. Во-первых, часто необходимо переставить данные в стеке, прежде чем войти в цикл. Во-вторых, поскольку цикл многократно использует число, обычно нужно применять на вершине стека операции DUP, OVER и др. И, в-третьих, по завершении цикла в стеке может что-то оставаться, поэтому в конце программы может потребоваться оператор DROP. Но не будем торопиться, посмотрим, что произойдет, если мы захотим возвести число в первую степень? Программа ** выполнит один цикл и выдаст в результате квадрат числа, т.е. введете ли вы 1 или 2, получится один и тот же ответ. Это как раз пример неудобства проверки индекса в Форте на предельное значение, о котором мы уже говорили выше. Но выход есть. Сделаем определение ** таким: : ** ( n1 n2 - n1^n2 ) OVER SWAP 1- 0 OVER OVER <>
IF DO OVER * LOOP ELSE DROP DROP THEN SWAP DROP ; Предложение OVER OVER <> IF разрешает запустить цикл только в том случае, если показатель степени больше 1. В противном случае значение показателя степени и его копия снимаются со стека двумя словами DROP, заключенными между словами ELSE и THEN. Этот пример приведен для того, чтобы показать как можно вообще избежать запуска цикла, если оба значения параметра цикла равны между собой.
Еще более эффективной будет следующее определение слова **: : ** ( n1 n2 -- n1^n2) DUP <>
IF OVER SWAP 1- 0 DO OVER * LOOP SWAP DROP THEN ; Предоставляем вам самостоятельно разобраться, как работает это определение и почему оно лучше, Но и это не все. Осталась еще одна проблема. Любое число, возведенное в нулевую степень, принимается равным 1. Это также должно быть учтено в программе **. Поэтому окончательное определение ** будет таким: : ** ( n1 n2 - n1^n2 ) ?DUP 0= IF DROP 1 ELSE DUP 1 = IF DROP ELSE OVER SWAP 1- 0 DO OVER * LOOP SWAP DROP THEN THEN ; В гл. 16 вы познакомитесь с определением слова ** на языке ассемблера, которое работает значительно быстрее. Следующие упражнения позволят вам еще больше узнать о циклах DO-LOOP.
Упражнения
1. Опишите слово ASCIITAB. предназначенное для того, чтобы напечатать коды ASCII и их алфавитно-цифровые эквиваленты. Перед тем, как использовать это слово, в стеке должны находиться верхнее и нижнее значения кодов ASCII. Тогда 65 68 ASCIITAB должно печатать 65 А 66 В 67 С 68 D 2. Модифицируйте программу ASCIITAB и назовите ее ASCIICHAR. так чтобы она печатала коды и соответствующие и' символы в следующей форме: 33 34 35 36 37 38 39 40 41 42 ! " # $ % & ' - . / ... 113 114 115 116 117 118 119 120 121 122 q r s t u v w x y z по 10 кодов в строке, показывая все печатные символы с кодами от 32 до 122. 3. Опишите слово ZERDIAG, которое обнуляет диагональ матрицы, т.е. результатом ее работы должно быть что-то вроде 0 3 6 7 8 2 0 9 4 3 5 5 0 9 8 1 2 8 0 9 6 1 6 9 0 4. Опишите слово SUMVOL, которое должно вычислять сумму чисел в каждом столбце матрицы размерности 5х5 из чисел длиной в 1 байт, если задан адрес матрицы. Пять значений суммы должны быть выданы в стек. 5. Напишите слово Х^5, которое должно возводить число, находящееся на вершине стека, в 5-ю степень. 6. Полезно было бы иметь эквивалент слова ** для чисел двойной длины D**, которое выдает в результате число двойное длины, если входное число имеет одинарную длину.
Опишите слово D**. 7. Напишите слово DUMP1, которое должно, начиная с известного начального адреса в памяти, представлять на экране следующие 160 байтов в шестнадцатеричной системе в виде таблицы из 10 строк по 16 чисел в каждой. 8. Измените слово DUMP, назвав его DUMP2, так чтобы в начале каждой строки слева был показан адрес первого байта в данной строке. Используйте представление чисел с выравниванием вправо, так чтобы все числа были выровнены в столбцах. 9. Измените слово DUMP, назвав его DUMP3, таким образом, чтобы оно печатало 10 строк (всего 80 байт), в каждой из которых сверху печатались бы числа, а под ними - соответствующие им символы ASCII. Так как символы с кодами меньше 32 нельзя напечатать, замените их точками. 10.Создайте переменную SPCS (от spaces - пробелы). Опишите слово для подсчета пробелов в текстовом массиве размером 1024 байта, начинающемся с адреса, указанного числом в стеке; результат должен быть записан в SPCS. 11. Создайте массив ALPHA, число элементов которого равно числу букв алфавита. Напишите слово ALPHACOUNT (число_букв), которое должно анализировать указанное количество алфавитно-цифровых байтов и записывать число встретившихся в массиве букв в элементах массива ALPHA. Тогда фраза 32201 500 ALPHACOUNT будет просматривать массив из 500 байтов, начинающийся с адреса 322201. и считать число различных байтов, причем число встретившихся литер "А" будет запоминаться в нулевом элементе массива, число литер "В" - в первом и т.д. Желательно превратить все литеры нижнего регистра в литеры верхнего регистра, чтобы не учитывать коды меньше 65 и больше 90. 12. Опишите слово ALPHAPLOT для представления в виде гистограммы частоты появления литер в массиве ALPHA, при этом каждый столбик постройте из соответствующих букв. 13. Не заглядывая в ранее приведенные определения, опишите слово .S.
Еще о циклах типа DO-LOOP
В некоторых случаях нужно, чтобы шаг приращения индекса в цикле был равен не единице, а большему числу. А иногда необходимо, чтобы цикл проходился в обратном направлении.
В таких случаях нужно использовать слово +LOOP. Испробуйте следующую программу: : SKIPLOOP 10 О DO I . 2 +LOOP ; тогда вы увидите на экране 0 2 4 6 8 Индекс в цикле инкрементируется на 2, т.е. на то число, которое +LOOP находит в стеке. Теперь определим слово : COUNTDOWN 0 10 DO I -2 +LOOP ; (обратный счет) Использование слова COUNTDOWN приводит к выводу на экран чисел 10 8 6 4 2 0 Другими словами, индекс получает приращение -2, пробегая от 10 до 0. Обратите внимание, что нуль также был напечатан. Если +LOOP декрементирует индекс (обратный цикл), то цикл заканчивается только тогда, когда индекс оказывается меньше предела в Форт-79 или когда он совершает переход от значения, равного пределу, к значению на единицу меньше предела в Форт-83, в то время как при возрастающем индексе (прямой цикл) выход из цикла происходит, когда индекс становится больше или равен пределу. Заметьте также, что различия в критериях для выхода из цикла +LOOP в Форт-79 и Форт-83 такие же, как и для выхода из цикла LOOP. В последующих упражнениях мы рассмотрим применение циклов с +LOOP.
Бывают случаи, когда необходимо выйти из цикла раньше, чем индекс достигнет значение предела. Чтобы сделать это, применяется слово LEAVE. Попробуйте этот практически бесполезный пример: : LEAVE-LOOP 10 0 DO I . I 5 = IF LEAVE THEN ."Loop" LOOP ; На Форт-79 исполнение LEAVE-LOOP (выйти_из_цикла) дает 0 Loop 1 Loop 2 Loop 3 Loop 4 Loop 5 Loop Обратите внимание, что слово "Loop" (цикл) было напечатано после номера 5, хотя слово LEAVE встретилось раньше и уже было исполнено. Так происходит потому, что в Форт-79 LEAVE просто устанавливает значение предела равным значению индекса, исполняет все, что осталось в цикле, а затем выходит из цикла в том месте, где LOOP проверяет величину индекса. На Форт-83 слово LEAVE-LOOP при исполнении выдает на экране 0 loop 1 loop 2 Loop 3 loop 4 loop 5
Слово "Loop" после номера цикла 5 отсутствует. Это объясняется тем, что на Форт-83, когда встречается слово LEAVE, оно, не обращая внимания на индекс и предел, делает скачок на слово, которое следует сразу же после LOOP.
Различия такого рода незначительные и достаточно тонкие, но, если их не осознавать, они могут вызвать недоумение, когда с ними сталкиваешься. (Мелкое замечание: I. I 5 = в программе LEAVE-LOOP можно записать иначе: I DUP. 5 =, но предыдущая запись предпочтительнее, поскольку она более понятна, а по скорости работы обе конструкции одинаковы.)
Приведем определение более полезного слова GET$. Это слово принимает счетную строку литер с клавиатуры, помещая длину строки в PAD, за которой следуют литеры строки: : GET$ 0 PAD С! 256 0 DO KEY DUP 13 = IF DROP LEAVE ELSE DUP EMIT PAD C@ 1+ PAD C! I PAD + 1+ C! THEN LOOP ;
По адресу PAD вначале записывается нуль, затем запускается цикл, ожидающий ввод с клавиатуры с помощью KEY до 256 символов. Если KEY вводит код 13 (код возврата каретки, одновременно запуска программы), то слово LEAVE выводит программу из цикла или подготавливает к выходу в зависимости от того, в какой версии, Форт-79 или Форт-83, применяется программа. В противном случае следующие после ELSE слова посылают на экран принятый байт и запоминают его в соответствующем месте после адреса PAD, а также увеличивают значение счетчика введенных символов на 1. Можно проверить работу этого слова, если ввести PAD COUNT TYPE. (Заметим, что лучшее определение слова GET$ будет дано в гл. 9.) Другие применения циклов с +LOOP и LEAVE лучше всего рассмотреть в упражнениях.
Упражнения
1. Опишите слово .ARR для печати содержимого одномерного массива чисел одинарной длины, начальный адрес которой и его длина находятся в стеке. 2. Опишите аналогичное слово .SQARR для печати содержимого квадратной матрицы чисел одинарной длины (но не байтов, как в предыдущем примере) в виде строк и столбцов, если адрес и число строк (столбцов) находятся в стеке. 3. Повторите упражнения 1 и 2, но для чисел двойной длины. 4. Преобразование температуры по Фаренгейту в значение, выраженное в градусах Цельсия, производится по формуле С = 5(F - 32)/9 Напишите слово, которое создает таблицу из двух колонок величин, выраженных в градусах Фаренгейта, преобразованных в величины, выраженные в градусах Цельсия через 10 градусов от 0 до 200 градусов Фаренгейта.
Меньшие значения должны стоять в таблице сверху. Переделайте это слово для печати в четыре колонки. 5. Переделайте определение слова из упражнения 4, чтобы большие значения находились сверху таблицы. 6. Напишите слово FINDCHAR (найти_символ), которое будет просматривать последовательность из 1024 литер и выдавать адрес, по которому впервые встречается литера, код ASCII которой помещается на вершине стека. Начальный адрес должен быть вторым в стеке. 7. Опишите слово $=, которое будет просматривать две счетные символьные строки, адреса которых находятся в стеке, и возвращать значение истина, если обе строки идентичны, и ложь в противном случае. Сначала должны быть проверены длины строк, и, если они равны, строки нужно сравнивать посимвольно, применяя цикл, который должен прерываться, если обнаружено несовпадение, чтобы сократить время. 8. Опишите слово $FIND для поиска строки в символьном массиве из 1024 элементов, которое выдает адрес, если заданная строка обнаружена и 0 в противном случае. Адрес начала блока должен быть вторым в стеке, адрес заданной счетной строки поиска должен быть на вершине стека. Используйте цикл для поэлементного сравнения строки с содержимым массива. и, конечно, если какой-либо символ не совпадает, нужно перейти к следующей строке, начинающейся на следующем символе. Считайте, что первый байт в массиве содержит длину строки.
Стек возвратов
Мы уже раньше упоминали о том, что в Форте имеются фактически два стека. Одним из них мы пользовались. Это стек данных, иначе, стек параметров или стек пользователя. Стек возвратов используется главным образом самой Форт-системой. Его основное назначение состоит в слежении за адресом возврата при исполнении слова. Кроме того, в большинстве реализации языка в нем также сохраняются значения пределов для циклов и текущего значения индекса (хотя стандарты этого не требуют). Его также можно использовать для временного хранения чисел. При этом важно помнить, что, если стеком возврата пользуется программист, его нужно восстанавливать в исходное состояние до окончания определения слова или до выхода из цикла.
Для операций в стеке возвратов предусмотрены три стандартных слова: >R (в_стек), R> (из_стека) и R@ (выдать_содержимое). Слово >R берет слово из стека параметров и помещает его в стек возвратов, слово R> забирает число из стека возвратов и помещает его в сек параметров, а слово R@ выдает копию содержимого стека возвратов в стек пользователя, не изменяя содержимое стека возвратов. Приведенные слова используются в стеке возвратов в основном для временного хранения чисел, которые во время исполнения слова могут потребоваться несколько раз. Это может сильно упростить некоторые манипуляции в стеке и зачастую позволяет обойтись без переменных для хранения чисел. Приведем пример. Пусть вы хотите извлечь однобайтовые элементы 5, 7, 11 и 12 из массива с именем DATA в стек пользователя. Вот как это можно определить: : @ELEMENTS ' DATA 5 + С@ ' DATA 7 + С@ ' DATA 11 + С@ ' DATA 12 + С@ ; Однако многократное повторение ' DATA снижает быстродействие. Быстрее будет работать следующая программа: : @ELEMENTS ' DATA >R R@ 5 + С@ R@ 7 + С@ R@ 11 + C@ R> 12 + С@ ;
Обратите внимание, что в последний раз адрес массива DATA берется из стека возвратов с помощью R>, поэтому в нем не остается ничего лишнего, когда мы завершаем исполнение слова по ;. Использование стека возвратов в счетных циклах также очевидно. При исполнении операторов, находящихся внутри цикла, верхний предел цикла лежит вторым в стеке возвратов, а текущее значение параметра цикла, т.е. индекс, - на вершине стека возвратов. Попробуйте исполнить следующее слово: : TRY-IT 5 0 DO R@ . R> R@ . >R SPACE LOOP ; Вы увидите 0 5 1 5 2 5 3 5 4 5 Выражение R@. печатает число с вершины стека возвратов, т.е. индекс, поэтому R@ . можно использовать вместо I . . Затем R> снимает число с вершины стека возвратов, a R@. извлекает число, которое было вторым в стеке возвратов, и печатает его. Это число 5, т.е. верхний предел цикла: Затем >R снова помещает индекс в стек возврата. Попробуйте теперь действие следующих слов: : I-BAD R@ ; (неверное_I) и : TRY-THIS 5 0 DO I-BAD .
LOOP :
Если вы исполните слово TRY-THIS, то увидите какую- то чушь. Но мы только что сказали, что R@ - то же самое, что I, где же ошибка? Вспомните, мы говорили раньше, что стек возвратов используется для экономии внешних ячеек памяти, когда слово вызывается из определения через двоеточие. При обращении к I-BAD адрес возврата помещается в стек возвратов, его вы и видите. Другими словами, когда вызывается I-BAD, адрес возврата помещается на вершине стека возвратов - выше, чем текущее значение параметра цикла (индекса). Поэтому правильное определение I должно быть таким: : I R> R@ SWAP >R : Слово I должно сначала снять число с вершины стека возвратов, потом извлечь содержимое индекса, а затем заменить число на вершине стека возвратов.
Теперь мы сможем дать определение I'. Просмотрите снова слова TRY-LOOP и IN-LOOP несколькими страницами назад и вспомните, что I' вызывается внутри слова, включенного в цикл, чтобы извлечь индекс. IN-LOOP помещает в стек возвратов число (адрес) сверху индекса, а I' еще выше помещает другой адрес. Поэтому, чтобы извлечь индекс, нужно вначале снять из стека возвратов два числа. Правильное определение I' будет таким: : I' R> R> R@ SWAP >R SWAP >R ; Вам должно быть понятно, как работает это определение по аналогии с I. Понимаете ли вы, почему, если использовать его внутри цикла, оно возвращает значение верхнего предела параметра цикла?
Вот так (в упрощенном виде) работает счетный цикл в Форт-79. Слово DO переносит первые два 'пела из стека параметров в стек возвратов. Когда встречается слово LOOP, оно сначала прибавляет I к числу, находящемуся на вершине стека возвратов, а затем сравнивает результат со вторым числом в стеке возвратов, т.е. с пределом на равенство либо превышение. Если это произошло, то управление передается слову, которое стоит после LOOP. Если же индекс не равен пределу и не превосходит его, то управление возвращается слову, которое стоит после DO. Цикл типа +LOOP работает в Форт-79 аналогично, но вместо добавления 1 к числу, находящемуся на вершине стека возвратов, добавляется число, находящееся на вершине стека параметров.
Оперируя стеком возвратов, мы можем определить другие полезные слова для работы с циклами, но лучше всего рассмотреть их в упражнениях.
Упражнения
1. Опишите слово 4PICK, пользуясь стеком возвратов для временного хранения чисел, которое должно печатать и удалять из стека параметров четвертое сверху число. Почему в определении нельзя использовать цикл DO-LOOP? 2. Используя стек возвратов, дайте возможное (но не эффективное) определение DUP с именем DUP1. 3. Что находится в стеке возвратов на первых четырех местах сверху вложенного цикла? Исходя из этого, дайте определение слова J (под именем J1). Не забудьте, что само слово J выдает число в стек. 4. Напишите определение слова К. 5. Опишите слово J', которое выполняло бы функции слова I', т. е. слово, в котором используется J', помещенное во вложенный цикл глубины 2, должно давать значение индекса внешнего цикла. 6. Дайте определение слова LEAVE, назвав его NEWLEAVE, которое будет правильно работать на Форт-79 (вы должны установить значение индекса цикла равным значению его предела). 7. Как можно изменить предел цикла из тела цикла? 8. Вы хотите, чтобы в цикле, завершающемся по LOOP. по достижении индексом значения 10 он изменялся на 15. Какие слова нужно включить в дело цикла, чтобы сделать это? 9. Опишите слово, которое заставляет индекс цикла изменяться на n, где n - число, которое находится в стеке в момент исполнения слова. 10. Что будет делать следующее слово: : DUMB 5 1 DO R> DUP . 1- >R LOOP ; (Оно очень коварно; будьте готовы к перезагрузке вашего компьютера.)
Для тех, кто знаком с дифференциальным исчислением
Упражнения
1. Поэкспериментируйте с разными значениями N в приведенном примере. Программа не работает, если N меньше 200. Почему? Если вы пользуетесь версией Форт, позволяющей работать с плавающей запятой, перепишите программу для чисел с плавающей запятой; она будет работать с меньшими начальными значениями. 2. Напишите программу, которая определяет, через какое время популяция в приведенном примере удваивается.
Используйте LEAVE. 3. Прирост популяции при ограничении на ресурсы описывается уравнением dN К - N ---- = rN ----- dt К где r - максимально возможная скорость роста и К - максимальная популяция, которая может сохраняться при ограниченных ресурсах. Напишите программу, моделирующую процесс роста популяции при начальном значении 1000, г, равном 1/200, и К, равном 3000. 4. А эта задача для честолюбивых. Просмотрите программы для построения гистограмм из гл. 5 и напишите программу для представления роста популяции к упражнению 3.
Циклы с неопределенным числом повторений
Циклы типа DO-LOOP имеют ограниченные пределы, задаваемые из стека. Однако часто нужно иметь циклическую программу, выход из которой зависит от выполнения некоторого условия, которое ею проверяется. Слово LEAVE позволяет это делать, однако существует более удобная форма цикла - цикл с неопределенным числом повторений, который включает слова BEGIN...UNTIL или BEGIN...WHILE..REPEAT. Как и цикл DO-LOOP, неопределенные циклы могут быть исполнены только в определениях через двоеточие.
Рассмотрим вначале цикл BEGIN-UNTIL. Слово BEGIN отмечает начало цикла. Если в стеке находится 0 (флаг ложь), то, когда его встречает слово UNTIL, исполнение повторяется со слова, которое стоит после BEGIN. Иначе говоря, цикл BEGIN-UNTIL повторяется до тех пор, пока в стеке перед словом UNTIL не встретится число, не равное нулю. Для примера определим слово : TIL-10 BEGIN DUP . 1+ DUP 9 > UNTIL DROP ; Исполняя 5 TIL-10, мы увидим 5 6 7 8 9 То есть программа печатала число, находящееся на вершине стека, увеличивала его на единицу до тех пор, пока оно не стало равным 10, и тогда она вышла из цикла.
Приведем более полезный пример. Предположим, что вы сделали в 1989 г. вклад 500 долл. из расчета 10% годовых. Когда на вашем счету будет 1000 долл. или более и сколько будет каждый год? Можно рассчитать это с помощью программы VARIABLE TOTAL 500 TOTAL ! : ?YEAR BEGIN TOTAL @ 10 / TOTAL +! 1+ TOTAL @ 1000 >
UNTIL TOTAL @ . . 500 TOTAL ! ; Обратите внимание, что.
как и в случае цикла DO-LOOP, слова, находящиеся между BEGIN и UNTIL, будут исполнены хотя бы один раз, потому что проверка условия производится последним словом в цикле.
Более гибкой является другая конструкция неопределенного цикла BEGIN...WHILE...REPEAT. Она подобна BEGIN...UNTIL, за исключением того, что REPEAT будет повторять цикл до тех пор, пока в стеке слово WHILE встречает ненулевое значение. Если флаг, предшествующий WHILE, имеет значение истина, то цикл исполняется до слова REPEAT, а затем вновь возвращается к слову BEGIN. Если флаг имеет значение ложь, исполнение переходит на слово, которое следует за REPEAT, покидая цикл. На рис.8.1 схематически показана эта идея.
Рассмотрим другое определение слова TIL-10 из предыдущего примера: : TIL-10 BEGIN DUP 10 < WHILE DUP . 1+ REPEAT : Как и раньше, при исполнении 5 TIL-10 получим 5 6 7 8 9. Но разница есть. Если в первом примере вместо 5 мы введем 15, то будет выведено только число 15, потому что цикл исполнится по крайней мере один раз. Если ввести 15 перед BEGIN во втором примере, то WHILE передаст управление после слова REPEAT и число 15 выведено не будет. Иначе говоря, если конструкция BEGIN...UNTIL требует исполнения находящихся между ними слов по крайней мере один раз, то конструкция BEGIN...WHILE...REPEAT позволяет пропустить все без исполнения, если это необходимо. Вот еще один пример. Это слово, которое разрешает ввод только цифры: : GET# CR ." Введите цифру " BEGIN KEY DUP DUP 48 < SWAP 57 > OR WHILE ." Неверно, должна быть ЦИФРА " REPEAT ; Фрагмент, предшествующий WHILE, будет исполняться всегда, по крайней мере, один раз, а слово после WHILE никогда не будет исполняться при выходе из цикла.
В сущности BEGIN...WHILE...REPEAT можно использовать вместо конструкции IF...THEN (хотя и очень неэффективно). Немного подумав, вы увидите, что BEGIN WHILE ... 0 REPEAT будет действовать так же, как IF ... THEN Почти точно так же BEGIN ... 0= WHILE REPEAT будет давать тот же результат, что и BEGIN ...
UNTIL разумеется, более медленно. Вероятно, чаще всего используют конструкцию BEGIN...WHILE...REPEAT для того, чтобы исключить даже однократное исполнение находящихся внутри слов, пока не будет удовлетворено некоторое условие, как в примере TIL-10. Другое общепринятое применение бесконечного цикла - для того, чтобы какой-либо фрагмент не исполнялся, когда начнет удовлетворяться некоторое условие, как в примере слова GET#. Вот более сложный пример программы, которую вы можете использовать как учебное пособие для освоения кодов ASCII. Она позволяет проверить знание до 20 символов: : ASK CR ." Какой код имеет литера " ; : TOOBIG CR ." Число очень велико. Попробуйте еще." ; : TOOSMALL CR ." Число очень мало. Попробуйте еще. " ; : GUESS 20 О DO CR ." Нажмите любую клавишу буквы или цифры " KEY DUP EMIT >R BEGIN ASK R@ EMIT #IN DUP R@ <>
WHILE R@ < IF TOOSMALL ELSE TOOBIG THEN REPEAT CR ." Вы УГАДАЛИ!!! " R> DROP LOOP ;
После небольшого анализа вы поймете, как работает эта "угадайка". Этот пример незатейливой обучающей программы GUESS показывает, что, применяя цикл BEGIN...WHILE...REPEAT, можно написать программу значительно проще, чем используя только цикл BEGIN...UNTIL.
Упражнения
1. Определите слово .S под именем NEW.S, используя цикл BEGIN... 2. Определите слово ST-SUM для суммирования содержимого стека, используя цикл BEGIN... Дайте другое определение с именем ST-SUM1 с помощью цикла DO-LOOP. 3. Измените программу ?YEAR, назвав ее ?YEAR1. чтобы она печатала год, увеличение вклада за год и сумму на счете в конце каждого года. 4. Пусть популяция мышей увеличивается на 0.05, или 1/200, за каждый день. Напишите слово, позволяющее рассчитать, через сколько дней популяция удвоится. Используйте при этом цикл BEGIN... и LEAVE. 5. Дайте новое определение слова GET$. приведенного выше, с использованием цикла BEGIN... и без ограничения длины строки 256 символами. 6. В MMSFORTH предусмотрено слово Y/N, которое печатает (Y/N)? и останавливается в ожидании нажатия клавиши.
Если нажата клавиша "Y", в стек кладется 0. если "N" - то 1. Если нажимают любую другую клавишу, ожидание продолжается. Определите слово Y/N с именем Y/N1.
Выводы
Циклы представляют собой управляющие структуры, как и рассмотренные в гл. 7 конструкции IF...THEN. И так же, как конструкция IF...THEN относится к фундаментальным средствам управления программным потоком, циклы представляют главное средство повторного выполнения программ, для чего в основном и используются компьютеры. Самой важной причиной могущества компьютеров является их способность манипулировать с битами информации с очень большой скоростью. Если бы не существовало циклов, скорость их работы не приносила бы практической пользы. Иначе говоря, циклы важны для составления практически полезных программ. По существу, язык Форт (либо другой язык с диалоговым режимом, программа редактора и многое другое) представляет собой бесконечный цикл, который периодически посматривает на клавиатуру и исполняет то, что вы приказываете.
Известны циклы двух типов: такие, как DO-LOOP с определенными извне пределами, и неопределенные циклы типа BEGIN...UNTIL, в которых пределы устанавливаются внутри цикла. Язык Форт обращается с циклами по крайней мере не хуже других языков программирования. Заметьте, между прочим, что неопределенные циклы могут быть также, что называется, "бесконечными". Например, следующий цикл никогда не закончится: : INFINITY BEGIN KEY EMIT 0 UNTIL ; Слово UNTIL никогда не встретит значение флага истина, поэтому цикл не прекратится никогда. Следовательно, циклы могут быть опасны, если вы допустите подобную оплошность.
Фактически известен еще один тип цикла, который позволяет организовать так называемую рекурсию. Рекурсия попросту состоит в том, что слово имеет возможность вызывать само себя, что в некоторых случаях может быть очень полезным. Однако для ее правильного использования необходимо хорошо понимать внутреннее устройство самого языка Форт, и мы вернемся к этому вопросу в гл. 15.
