2. РЕФАЛ В КОМПЬЮТЕРАХрВВефал
| 2.1. Как запустить его |
| 2.2. Программные модули |
| 2.3. Ввод-вывод |
| 2.4. Представление РЕФАЛ-выражений |
| 2.5. Алгоритм сопоставления с образцом |
Ранее были приведены определения только отдельных функций в РЕФАЛе. Теперь желательно записать простую программу и запустить ее на IBM микрокомпьютере (XT или AT) под управлением MS-DOS. Запуск ее в других операционных окружениях аналогичен.
Функция перевода итальянских слов в английские была определена в Разд. 1.6. Допустим, требуется переводить и распечатывать итальянские слова, набираемые на терминале. Пусть слова в строке разделяются любым количеством пробелов. Нужно, чтобы наша программа читала строку, переводила каждое слово и выдавала на принтер строку перевода. Затем программа должна запрашивать следующую строку. Если итальянское слово не может быть найдено в таблице, оно должно замещаться комбинацией *** .
Потребуются некоторые средства для обмена информацией с РЕФАЛ-машиной. Некоторые основные функции ввода-вывода должны обеспечиваться системой, так как они очевидно не могут быть определены посредством РЕФАЛ-предложений. Функции, которые не определены в РЕФАЛе, но все-таки могут применяться в системе, называются встроенными функциями. Перечень встроенных функций РЕФАЛ-5, вместе с кратким описанием их действия, можно найти в Reference Section C. Читателю рекомендуется ознакомиться с Reference Section C перед написанием конкретных программ на РЕФАЛе для того, чтобы знать, какие встроенные функции имеются в его распоряжении.
Для нашей задачи имеются две необходимые встроенные функции: Card и Prout . Во время исполнения <Card> РЕФАЛ-машина ожидает то, что пользователь набирает в строке * , завершая символом возврата каретки. Затем она читает строку и замещает вызов функции результатом, который трактуется как строка символов. Если пользователь вводит специальный символ Конец-Файла, которым в MS-DOS является комбинация Control-Z, <Card> будет замещена числом 0. Это является сигналом для РЕФАЛ-программы, что не осталось строк, подлежащих считыванию. Напомним, что знаки клавиатуры, слова и числа являются различными символами РЕФАЛа. Так как Card обрабатывает строку как последовательность символов, число 0 невозможно спутать с содержимым любой строки.
Поле того, как <Prout Е > , где Е является некоторым выражением, вычислено, машина выдает на принтер Е и стирает вызов. Имеется также и другая функция вывода, Print , которая не уничтожает свой аргумент.
Начнем программирование сверху вниз; т.е., сперва определим общую структуру программы, а затем будем разрабатывать детально. Наша программа транслирует входной текст построчно, поэтому потребуется функция -- назовем ее Trans-line --, такая, что если Е является входной строкой, то вычисление:
<Trans-line Е >
порождает ее перевод. Далее, необходима контролирующая функция, которая вызывает <Card> , проверяет, совпадает ли результат с 0, и либо вызывает Trans-line, либо объявляет окончание работы. Назовем эту функцию верхнего уровня Job. Поскольку Job предназначена для анализа результата Card , она должна вызываться следующим образом:
<Job <Card>>
Теперь попытаемся определить Job двумя предложениями, соответствующими двум разновидностям ее аргумента:
Job { 0 = ;
e.X = <Trans-line e.X>; }
Если результатом <Card> является 0 , поле зрения становится пустым, т.е. пассивным, и это означает конец работы. В противном случае Trans-line осуществит перевод строки и поместит ее в поле зрения. Это не совсем то, что требуется. Во-первых, желательно, чтобы результат выдавался на принтер, а не просто оставался в поле зрения. Во-вторых, следует сделать запрос на следующую вводимую строку, а это означает, что <Job <Card>> должна попасть в поле зрения снова. Напомним, что параллельные (т.е., не вложенные друг в друга) активные подвыражения активизируются слева направо. Поэтому, если нужно, чтобы несколько действий были произведены последовательно, мы объединяем соответствующие подвыражения в требуемом порядке. Приходим к следующему определению:
Job { 0 = ;
e.X = <Prout <Trans-line e.X>>
<Job <Card>>; }
Теперь определим Trans-line . Рассмотрим, какие возможные случаи аргумента следует различать. Прежде всего, он может быть пробелом. Следует его проигнорировать и применить Trans-line к остатку строки:
Trans-line ' 'e.X = <Trans-line e.X>;
Если перед словами имеется по нескольку пробелов, это предложение исключит их все, шаг за шагом. Если первый набираемый символ не является пробелом, он должен быть буквой, с которой начинается слово. Так как слова разделяются пробелами, мы можем выделить первое слово, используя образец:
e.Word ' ' e.Rest
Согласно правилам сопоставления слева-направо, пробел в этом образце будет сопоставлен с первым пробелом в аргументе (если таковые имеются). Поэтому, e.Word становится первым словом. Оно переводится с использованием функции Trans, определенной в Разд. 1.6. Английские слова, продуцируемые Trans, должны отделяться пробелом от слов, которые будут появляться за счет рекурсивного вызова Trans-line . Таким образом, мы имеем предложение:
e.Word' 'e.Rest =
<Trans (e.Word)<Table>>' '
<Trans-line e.Rest>;
Имеются еще две возможности. Одна из них, когда строка полностью использована (т.е. пуста), в таком случае вычисление Trans-line завершено. Другая - когда вся оставшаяся строка является одним словом. Полное определение выглядит следующим образом:
Trans-line {
' 'e.X = <Trans-line e.X>;
e.Word' 'e.Rest =
<Trans (e.Word)<Table>>' '
<Trans-line e.Rest>;
= ;
e.Word = <Trans (e.Word)<Table> >' '; }
ЗАМЕЧАНИЕ: e.Word в последнем предложении не может быть пустым, что вытекает из предыдущего предложения.
Теперь определены все функции, необходимые для программы. Но как поместить начальное выражение в поле зрения РЕФАЛ-машины? РЕФАЛ-5 использует соглашение, согласно которому начальным состоянием поля зрения всегда является:
<Go>
Это значит, что среди функций, определенных в выполнимой программе, всегда должна быть стандартная функция Go без аргументов:
$ENTRY Go { = the initial Refal expression }
Префикс $ENTRY объявляет функцию Go
как входную функцию, которая может быть
вызвана из любого модуля программы (модульная
структура программы описана в следующем разделе).
В нашем случае начальным выражением должно быть <Job
<Card>> .
ЗАМЕЧАНИЕ: Функция Go не может
вызывать сама себя и не может
вызываться никакой другой функцией. Она
служит только для инициации поля зрения.
Теперь соберем все функции в программу и добавим некоторые комментарии. Будем придерживаться правила, согласно которому все строки-комментарии помещаются перед текстом, а прочие комментарии -- после текста, к которому они относятся:
* Translation from Italian into English
$ENTRY Go { = <Job <Card>> }
* The top-level control function.
Job {
0 = ; /* end of file */
e.X = <Prout <Trans-line e.X>>
<Job <Card>>; }
* Translate one line
Trans-line {
' 'e.X = <Trans-line e.X>;
e.Word' 'e.Rest =
<Trans (e.Word) <Table>>' '
<Trans-line e.Rest>;
= ;
e.Word = <Trans (e.Word) <Table>>' '; }
* Italian-English dictionary table
Table { = (('cane') 'dog')
(('gatto') 'cat')
(('cavallo') 'horse')
(('rana') 'frog')
(('porco') 'pig')
}
* Translate Italian word into English by table
Trans {
(e.It)e1((e.It)e.Eng)e2 = e.Eng;
(e.It)e1 = '***'; /* word not in table */
}
Для того, чтобы запустить эту программу, наберите ее в любом текстовом редакторе и сохраните как файл с расширением .ref (например, prog1.ref ). Теперь введите команду:
refc prog1
Она вызывает РЕФАЛ-компилятор, который переводит программу в промежуточный язык RASL (о котором пользователю не нужно знать ничего, кроме того, что он существует) и размещает ее под именем prog1.rsl . Если компилятор обнаруживает синтаксические ошибки в программе, он выдает соответствующее сообщение и создает файл под именем prog1.lis , который содержит листинг программы с индикацией обнаруженных ошибок. Если синтаксических ошибок нет, листинг не порождается.
Для запуска программы вызовите РЕФАЛ-машину, вводя:
refgo prog1
Это приводит к загрузке RASL файла prog1.rsl с диска в оперативную память. Затем начинается интерпретация программы, т.е. эмуляция абстрактной РЕФАЛ-машины. Когда <Card> становится первым ведущим выражением в поле зрения, РЕФАЛ-машина останавливается и ожидает ввода строки с терминала. Введите:
rana cane rana vacca porco
Система выдаст на принтер
frog dog frog *** pig
Введите:
cavallo
и последует ответ:
horse
Введите символ Конец-Файла (control-Z), и программа завершит работу.
Когда вы тестируете и отлаживаете программу, весьма полезен РЕФАЛ-трассировщик. Чтобы применить его, введите reftr вместо refgo :
reftr prog1
Трассировщик распознает множество команд, управляющих выполнением программы. Можно выдавать на принтер текущее содержимое поле зрения либо только ведущее активное подвыражение. Можно проделать некоторое количество шагов и затем снова распечатать поле зрения либо активное подвыражение. Возможно также запустить машину до момента, когда она завершит вычисление текущего активного подвыражения, а затем распечатать полученное объектное выражение. Лучшим способом управления процессом вычислений является определение ряда образцов - так называемых контрольных точек. Тогда РЕФАЛ-машина будет останавливаться и запрашивать дальнейшие команды всякий раз, когда активное подвыражение сопоставлено с одним из образцов.
См. перечень команд трассировщика в Reference Section D .
Использование функции Go является основным путем инициализации РЕФАЛ-машины. Есть и другой способ - через сервис РЕФАЛ-программ с очень коротким именем E (от Evaluator ), который поставляется на системной дискете. Эта программа позволяет вводить активные РЕФАЛ-выражения в поле зрения и вычислять их без вызова refgo или reftr каждый раз. Она имеет две полезных черты. Во-первых, произвольное выражение может быть вычислено, не только стандартное <Go> . Во-вторых, всякий раз при вызове refgo или reftr, программа загружается с диска в оперативную память. Используя E, мы делаем это лишь один раз, при этом все последовательные вычисления (в частности, вычисление <Go> , если мы хотим запускать программу повторно) выполняются без повторной загрузки программы. Вычислитель будет описан в Разд. 6.3 (см. также Reference Section A). В этом месте просто приводится иллюстрация, как работает метод.
Добавим строку:
$ENTRY Upd {e.X = <Mu e.X>;}
в программу prog1 . Затем введем:
refgo e+prog1
На терминале появится следующее сообщение:
Type expression to evaluate. To end: empty line. To end session: empty expression
Введем:
<Table>
и нажмем клавишу Return дважды для ввода пустой строки. Система выдает на печать:
The result is:
(('cane') 'dog')
(('gatto') 'cat')
(('cavallo') 'horse')
(('rana') 'frog')
(('porco') 'pig')
и повторяет приглашение ввести другое выражение. РЕФАЛ-выражение, которое вы представите, может включать вызовы любых функций, определенных в prog1 . Оно может также включать вызовы стандартных встроенных функций. Допустим, вы набрали:
<+ 2 <* 3 <* 4 5>>>
Система выдаст результат 62 .
Может быть вызвана любая комбинация функций. В
частнсти, вы можете вызвать <Go> ,
которое рассматривается как стартовая функция prog1
. Эффект будет таким же, как если бы вы просто
выполнили prog1 , за исключением
следующего:
Упражнение 2.1 Модифицировать prog1так, чтобы система выдавала Please enter a line перед переходом в ожидание ввода, и The translation is: перед выдачей на печать перевода.
Функции, которые однажды уже были определены, не нужно определять повторно. Не требуется и повторная их компиляция. При размещении функциональных определений на языке РЕФАЛ в файлах с расширением .ref , их переводы в промежуточный язык RASL размещаются в соответствующих файлах с расширением rsl . При написании большой программы мы часто разбиваем ее на ряд частей, называемых модулями, тестируем и отлаживаем их отдельно, а затем объединяем их в единую программу.
Некоторые функции в модуле предназначены для вызова из функциями из других модулей. Другие функции являются вспомогательными; пользователю совсем не обязательно знать об их существовании. Это могло бы породить конфликт имен. В самом деле, допустим, что два программиста написали свой модуль и использовали одно и то же имя для одной из вспомогательных функций. Как тогда РЕФАЛ-машина распознает, какое из определений использовать?
Эта проблема решена путем определения некоторых функций в каждом модуле в качестве входных функций. Только входные функции могут вызываться из других модулей. Чтобы определить функцию как входную, просто добавляется ключевое слово $ENTRY перед именем функции, с которого начинается определение. Пусть входная функция F1 определена в модуле Mod1 :
* Module Mod1
$ENTRY F1 { ... }
Для того, чтобы вызвать F1 из другого модуля Mod2 , эта функция должна быть объявлена в Mod2 как внешняя функция:
* Module Mod2 $EXTRN F1; ... <F1 ...> ...
Внешнее утверждение отмечает для компьютера, что F1 определена как входная точка в каком-то другом модуле, а не в текущем. Такой модуль (Mod1 в нашем примере) должен быть включен в вызов refgo или reftr :
refc Mod2+Mod1
В одном внешнем утверждении может быть объявлено несколько внешних функций:
$EXTRN F1,F2,F3;
Имена внешних функций должны быть одними и теми же для всех модулей, которые используются совместно. Функции, которые не объявлены как входные, могут вызываться только из функций. определенных в том же модуле. Таким образом, разрешаются конфликты имен. Во время написания модуля можно изобретать любые имена для вспомогательных функций, не беспокоясь о функциональных именах в других модулях.
Среди модулей, используемых совместно, один должен включать определение стартовой функции Go ; он будет считаться главным модулем. Если, в дополнение к главному модулю Mainmod , желательно использовать некоторые другие модули: Mod1 , Mod2 , и т.д. до Modn , вводится:
refc Mainmod+Mod1+Mod2+ ... +Modn
либо:
reftr Mainmod+Mod1+Mod2+ ... +Modn
Рассмотрим типичную ситуацию. Функция Go , которая выполняет задание, определена в модуле prog1, а некоторые из необходимых функций определены в модуле под названием functions . Требуется также ряд постоянно используемых функций, которые собраны в модуле reflib . Если все три модуля уже имеются в RASL форме, то для запуска prog1 вводится:
refgo prog1+functions+reflib
Помимо главного модуля, другие модули также могут включать определение функции Go . Оно будет игнорироваться до тех пор, пока модуль не займет первое место в списке.
Стандартный ввод и вывод, выполняемый посредством Card и Print, может быть переориентирован на другие файлы с помощью средств, обеспечиваемых операционной системой. Но часто является желательным использование одного или более файлов ввода-вывода в дополнение в операциям с клавиатурой и экраном. Тогда могут быть использованы встроенные функции Get и Put в комбинации с функцией Open .
Файл может использоваться как в режиме чтения (когда вы вводите информацию из него), так и в режиме записи (когда вы выводите в него информацию ). Один и тот же файл может быть использован поочередно в различных режимах. Для того, чтобы использовать файл, его следует вначале открыть посредством активизации:
<Open s.Mode s.Channel e.File-name>
где s.Mode может быть либо 'r' для режима чтения, либо 'w' для режима записи; e.File-name является строкой, которая представляет полное имя файла; s.Channel является целым числом, которое присваивается открываемому файлу. Каналы используются для того, чтобы сделать процесс написания программы независимым от имен файлов, с которыми будет взаимодействовать программа. s.Channel не должно превышать 19.
После того, как в файл произведена запись, он
должен быть закрыт; в противном случае
будет невозможно его читать либо в текущей
программе, либо после ее выполнения (файл,
который был открыт для записи, но не закрыт, будет
показываться в директории как пустой). Однако
РЕФАЛ-функций для закрытия файлов не
существует; это проделывается автоматически в
двух случаях:
Чтобы читать из файла, который открыт для чтения, активизируется:
<Get s.Channel>
Машина считывает одну строку символов из файла, связанного с s.Channel. Если она дошла до символа Конец-Файла, результатом будет число 0. Get полностью аналогична Card .
Чтобы записать строку в файл, открытый для записи, активизируется:
<Put s.Channel e.Expression>
Затем e.Expression будет возвращено в качестве значение и добавлено как строка к текущему содержимому файла, связанного с s.Channel . Таким образом, Put аналогична Print . Функция:
<Putout s.Channel e.Expression>
является аналогичной Prout (возвращает empty). Когда Open применяется для того, чтобы связать канал с файлом, s.Channel не должна быть равным 0. При s.Channel, равном 0, функции Get , Put и Putout используют в качестве файла терминал (т.е., становятся эквивалентны Card , Print и Prout ); однако их нельзя переназначить из операционной системы).
Допустим, строится функция, которая оперирует с тремя файлами в дополнение к операциям с терминалом. Можно присвоить этим файлам только каналы 1, 2 и 3, не вводя для них специальных имен; в функциях Get и Put будут указываться только каналы. Когда функциональное определение готово, можно либо компилировать его как отдельный модуль, либо поместить его в библиотеку. От может быть использован теперь с различными главными модулями и с различными файлами. Все, что требуется, - это присваивание каналов файлам с помощью вызова функции Open из главного модуля. Это невозможно было бы сделать, если бы мы использовали имена файлов непосредственно в функциях ввода-вывода.
Встроенные функции ввода-вывода обрабатывают только одну строку при каждом вызове и то, что они читают или записывают, всегда должно быть простой строкой символов. Но РЕФАЛ-машина имеет дело с выражениями. Трансформация входных строк в объектные выражения, вообще говоря, оставляется на усмотрение программиста, который создает любое специальное приложение к РЕФАЛу. Это обоснованно, поскольку способ, которым пользователь желает представить выражения с помощью символьных строк, может зависеть от специфики приложения. Пользователь должен иметь свободу определения ввода и вывода наиболее удобным способом. Тем не менее, потребность трансформации входных строк в выражения всякий раз, когда мы пишем РЕФАЛ-программу, представляет определенное неудобство. Поэтому был определено некоторое множество стандартных функций ввода-вывода общего назначения, которое поставляется с РЕФАЛ-системой (файл reflib.ref , см. Раздел справочника A).
Чтобы ввести РЕФАЛ-выражение, применяется Input . Для этой функции было принято представление выражений в основном такое же, как при написании программы на РЕФАЛе. Единственным отличием является менее строгое использование кавычек, которые следует допустить, потому всегда читаются объектные выражения, а не РЕФАЛ-программы. Единственными нецифровыми набираемыми символами, которые не могут представлять сами себя, являются круглые скобки, пробелы и одинарные кавычки. Хотя необходима и некоторая осторожность для того, чтобы избегать путаницы между набираемым символом '-' как черточкой в идентификаторе и символами '+' и '-' как знаками действительного числа. Таким образом, кавычки и пробелы должны использоваться. Далее, требование, чтобы первая буква идентификатора была заглавной, ослаблено; она может быть также строчной.
Если желательно считывание более чем одного выражения из одного файла, они разделяются пустыми строками. Пустая строка (дополнительный возврат каретки) будет также завершать ввод выражения в терминала. Когда активизируется
<Input s.Channel>
, РЕФАЛ-машина будет читать файл, связанный с s.Channel до тех пор, пока не встретит пустую строку либо конец файла. Когда этот вызов активизируется снова, она считывает следующее выражение, и т.д.
Функция Input может также быть использована просто вместе с именем файла, который нужно читать:
<Input e.File-name>
Автоматически будет найден свободный канал, ему будет присвоено имя файла e.File-name и последует вызов Open . Для чтения с терминала следует использовать <Input 0> или <Input> .
Input удобна для интерфейса с машиной пользователя, но она может оказаться не лучшим выбором для обмена информацией между оперативной памятью и внешней памятью (магнитными дисками). Нужен более простой код для эффективного информационного обмена. Для этой цели мы готовы пожертвовать удобством чтения файлов (которое достигается в Input путем свободного использования пробелов и переносов). Поэтому наша небольшая РЕФАЛ-библиотекa reflib включает функции Xxin и Xxout (eXpression eXchange IN и OUT). Можно также обнаружить там функцию Xxinr (Xxin в РЕФАЛе). Xxin и Xxinr действуют одинаково; различие только в том, что первая написана преимущественно на языке C и встроена в систему, в то время как вторая написана на РЕФАЛе с целью формального определения. Xxin гораздо более быстрая, чем Xxinr .
Функции обмена выделяют символ #
как исключающий для представления объектов,
не являющихся символами. Код выглядит следующим
образом:
in the view field on the disk
s.Identifier '#' e.Char-string ' '
s.Number> '#' e.Digit-string ' '
( '('
) ')'
'(' '#('
')' '#)'
'#' '##'
Функции Xxin и Xxout противоположны по действию. Xxinr и Xxout могут , как и Input , использоваться либо с именами каналов, либо с именами файлов:
<Xxinr s.Channel> <Xxin e.File-name> <Xxout s.Channel e.Expr> <Xxout (e.File-name)e.Expr>
Эффективная функция Xxin может использоваться только с именами файлов:
<Xxin e.File-name>
Канал 0 соответствует операциям с терминалом.
Переносы не разбивают числа и идентификаторы. Xxout разрезает текст на строки длины
75.
ЗАМЕЧАНИЕ: Функции Input , Xxin и Xxout
используют собственную таблицу свободных и
занятых каналов, которая обозначается номером
153443950 (смотри программы) и ничего не делают
с системной таблицей, которая показывает, какие
каналы действительно задействованы через
функцию Open . Так, одна из этих
функций ввода-вывода может выбрать канал, как
свободный, даже если тот уже задействован в
вызове Open . Поэтому не
рекомендуется использовать совместно имена
каналов и имена файлов в функциях ввода-вывода в
одной и той же программе, поскольку выбор каналов
может вступить в конфликт с автоматическим
выбором. который осуществляют эти функции. Если
все-таки желательно использовать оба метода,
тогда с Open надо использовать
каналы с малыми номерами: 1, 2, 3, и т.д., поскольку
каналы, выбираемые автоматически, будут иметь
номера 19, 18, 17, и т.д.
Ниже приведены несколько примеров корректного и некорректного использования функций ввода-вывода. Во всех примерах целью является чтение файла xfile , запись его обменного кода в файл yfile , затем повторное его чтение и распечатывание.
Простейшим способом является использование только имен файлов:
* Test of I/O functions.Example 1.
* This works
$ENTRY Go { =
<Xxout ('yfile') <Input 'xfile'>>
<Prout <Xxin 'yfile'>>; }
$EXTRN Input,Xxin,Xxout;
В этой программе Xxin закрывает yfile автоматически. Ей известно, что этот файл был открыт для записи, потому что Xxout проделала это по имени файла, а не по имени канала.
Следующий пример демонстрирует некорректное использование каналов:
* Test of I/O functions. Example 2.
* This does NOT work.
$ENTRY Go { =
<Open 'w' 19 'yfile'>
<Xxout 19 <Input 'xfile'>>
<Open 'r' 19 'yfile'>
<Prout <Xxin 'yfile'>>; }
$EXTRN Input,Xxin,Xxout
Ошибка здесь заключается в явном использовании канала 19 вместе с Input . Эта функция ввода переоткрывает канал 19 для чтения. Когда Xxout начинает работу, канал 19 по умолчанию считается открытым. Заменим канал 19 каналом 1:
* Test of I/O functions. Example 3.
* This works.
$ENTRY Go { =
<Open 'w' 1 'yfile'>
<Xxout 1 <Input 'xfile'>>
<Open 'r' 1 'yfile'>
<Prout <Xxin 'yfile'>>; }
$EXTRN Input,Xxin,Xxout
Тогда это корректная программа. Второе Open выражение необходимо для закрытия yfile, который был открыт первоначально для записи. Если бы это не было проделано, как в рассматриваемом ниже случае:
* Test of I/O functions. Example 4.
* This does NOT work.
$ENTRY Go { =
<Open 'w' 1 'yfile'>
<Xxout 1 <Input 'xfile'>>
<Prout <Xxin 'yfile'>>; }
$EXTRN Input,Xxin,Xxout
то программа не стала бы работать. Когда
выполняется Xxin, файл yfile оказывается пустым, так как он
не был закрыт.
ЗАМЕЧАНИЕ: Функции Print
и Prout первоначально
предназначались для распечатывания строк
набираемых символов. Если их аргументы включают
другие РЕФАЛ-объекты, а именно идентификаторы,
числа и скобки, эти функции будут выдавать их в
легко читаемом представлении. Идентификатор
распечатывается большими буквами и
заканчивается пробелом; десятичные цифры в
макроцифрах также заканчиваются пробелом;
скобки выпечатываются как символы '('
и ')' . Таким образом, важно
знать, включает ли аргумент на самом деле
несимвольные объекты или он состоит из строк
символов, которые не изменяют вида при
распечатывании. Это может оказаться
препятствием при отладке; поэтому трассировщик
распечатывает все выражения в обменном коде,
который обладает единственным обратным
отображением (см. Раздел
справочника D). Если имеются сомнения в том, что
выдано посредством Prout,
используйте трассировщик, чтобы выяснить это.
Упражнение 2.2 Пусть приведенные ниже
символьные строки считываются с помощью Input . Записать результатные
выражения в том виде, в котором они должны были бы
появиться в программе, и в обменном коде.
(a) sum-1
(b) sum - 1
(c) sum -1
(d) (95+25)'()'
Упражнение 2.3 Функия Input
работает гораздо медленнее, чем Xxin,
но ее формат более удобен, когда файл написан
человеком. Если один и тот же файл нужно читать
более одного раза, возможно, имеет смысл написать
его для Input , а затем уже
конвертировать его в файл для Xxin
. Написать программу, осуществляющую подобное
конвертирование. Она должна работать с любым
файлом (использовать встроенную функцию Arg ).
2.4. ПРЕДСТАВЛЕНИЕ РЕФАЛ-ВЫРАЖЕНИЙ
При вводе команды refgo или reftr запускается программа, которая является эффективным интерпретатором РЕФАЛа. Тот факт, что она является интерпретатором, означает, что компьютер будет в основном имитировать шаги РЕФАЛ-машины. Будут поддерживаться две области памяти: поле программы и поле зрения; они будут представлениями поля программы и поля зрения абстрактной РЕФАЛ-машины.
На каждом шаге компьютер будет находить
первичное активное подвыражение в поле зрения и
применять к нему одно из предложений из поля
программы. Это будет приводить к замещению
активного подвыражения другим подвыражением.
Название "эффективный" для
интерпретатора означает, что он будет
использовать некоторые адреса памяти для того,
чтобы прямо переходить в нужные пункты памяти, не
проходя через промежуточные выражения, как это
предлагается в абстрактной РЕФАЛ-машине. Он
должен также избегать бесполезного копирования
выражений. Более точно, должны удовлетворяться
следующие требования :
Пользователю РЕФАЛа не нужно знать о реальном представлении выражений ничего, кроме факта, что эти пять требований удовлетворяются. Очевидным способом удовлетворить этим требованиям является применение двухсвязных списков, со скобками, хранящими ссылку на парную скобку, наряду со ссылками на следующую и предыдущую. Это на самом деле и реализовано в РЕФАЛ-системе. Для того, чтобы совершать скачок к следующему активному подвыражению, хранится стэк адресов активных подвыражений (стэк вызовов функций). РЕФАЛ-компилятор, под названием refc , транслирует РЕФАЛ-программу в промежуточный язык RASL и порождает файл, состоящий из подполей, каждое из которых хранит одно из функциональных определений. Доступ к этим подполям во время выполнения программы осуществляется через хэш-таблицу.
Элементы списка, представляющие символы РЕФАЛа, включают коды символьного типа. Таким образом система различает набираемые символы, идентификаторы, макроцифры и действительные числа. Для конвертирования одного типа в другой (например, цифровой строки '321' в макроцифру 321 или идентификатора Sum в строку 'SUM' и т.д.), применяются соответствующие встроенные функции, описанные в Разделе справочника C.
Если это краткое описание внутреннего
устройства РЕФАЛ-системы не особенно много
говорит вам, не беспокойтесь: напоминаем еще раз,
на самом деле вам нет нужды знать о ней, если вы
хотите только пользоваться языком.
Упражнение 2.4 Определить функцию <Merge s.1
s.2>, которая создает новый идентификатор,
объединяя "тела" (строковые представления)
идентификаторов s.1 и s.2 .
2.5. АЛГОРИТМ СОПОСТАВЛЕНИЯ С ОБРАЗЦОМ
Сопоставление с образцом является одной из двух основных операций в РЕФАЛ-машине, поэтому следует рассмотреть его более подробно. Напомним сперва некоторые основные определения.
Выражение, которое не содержит ни активизирующих скобок, ни свободных переменных, считается объектным выражением. Выражение, которое может содержать свободные переменные, но не включает активизирующих скобок, является выражением-образцом, или просто образцом. Операция сопоставления записывается как E : P , где Р является образцом, а Е - объектным выражением. Здесь и далее большие буквы курсивом используются в качестве метасимволов для обозначения объектов языка РЕФАЛ.
Операция сопоставления либо проходит успешно,
либо терпит неудачу. Е : Р
проходит успешно, если есть подстановка S
для свободных переменных в P ,
такая, что когда она выполнена, P
становится тождественным Е. Если
отождествление успешно, говорим, что E
может быть распознано как (частный
случай) P , либо используем
эквивалентное высказывание, что P
можно отобразить на E . Тогда
свободные переменные в P принимают
значения, предписываемые подстановкой. Если
сопоставление неудачно, значения переменных в P
не определены. Может быть несколько подстановок,
преобразующих P в E .
Для того, чтобы обеспечить однозначный
результат сопоставления , используется
следующее соглашение о том, что сопоставление
осуществляется слева направо:
Сопоставление слева-направо. Если существует
более чем один способ присвоения значений
свободным переменным в образце, при котором
сопоставление достигается, то выбирается тот, в
котором самая левая e-переменная принимает самое
короткое значение. Если это не разрешает
неоднозначности, тогда подобный выбор
совершается для следующей e-переменной, стоящей
слева, и т.д.
При таком соглашении сопоставление в РЕФАЛе становится однозначной операцией. Вот и все о результате сопоставления, что пользователь, строго говоря, должен предварительно знать при написании РЕФАЛ-предложений. Можно пропустить окончание этого раздела и все-таки иметь возможность успешно программировать на РЕФАЛе. Однако он поможет мыслить о сопоставлении как о специфическом алгоритме. Поэтому будет определен точный алгоритм для сопоставления объектного выражения Е с образцом Р, как это реализовано в РЕФАЛ-5.
Вхождения символов, скобок и переменных будут называться элементами выражений. Пропуски между элементами будут называться узлами. Сопоставление Е : Р определяется как процесс отображения, или проектирования, элементов и узлов образца Р на элементы и узлы объектного выражения Е . Графическое представление успешного сопоставления приведено на Рис. 2.1. Здесь узлы представлены знаками o.
Рис. 2.1 Сопоставление Е : Р
является отображением Р на Е
. Здесь объектным выражением Е является
'A'((2'B'))'B' ,
а образцом Р является 'A'(e.1 t.2)s.3 .
Следующие очевидные требования должны проверяться на каждой стадии сопоставления:
Общие требования к отображению Р на Е
(сопоставлению Е : Р )
Предполагается, что в начале сопоставления граничные узлы Р отображаются в граничные узлы Е . Процесс отображения описывается при помощи следующих шести правил. На каждом шаге отображения правила 1-4 определяют следующий элемент, подлежащий отображению; таким образом, каждый элемент из Р получает при отображении уникальный номер.
Правила отображения
На Рис. 2.1 сопоставление производится следующим образом. Вначале имеется два жестких элемента с одним отображенным концом: 'A' и s.3 . В соответствии с Правилом 3, отображается 'A' , и этот элемент получает при отображении номер 1. Номера 2 и 3 будут назначены левой и правой скобкам, согласно Правилам 3 и 1. Внутри скобок начинается перемещение справа налево, так как t.2 является жестким элементом, который может быть отображен, в то время как значение e.1 еще не может быть определено. На следующем шаге обнаруживается, что e.1 является закрытой переменной, чью проекцию не требуется обозревать для того, чтобы присвоить ей значение; что бы ни было между двумя узлами, это годится для присвоения (на самом деле, значение e.1 оказывается пустым). Отображение s.3 завершает сопоставление. Расположение отображающих номеров над элементами образца дает наглядное представление описанного алгоритма :
1 2 5 4 3 6 'A' ( e.1 t.2 ) s.3
Рассмотрим другой образец, с отображающими номерами над элементами:
1 6 7 8 2 9 10 11 4 5 3 ( e.1 '+' e.2 ) e.3 '+' e.4 ( e.5 )
Здесь e.1 и e.3 являются открытыми переменными, в то время как e.5 , e.2 и e.4 - закрытые. Скобки в РЕФАЛе используются для перепрыгивания из одной части выражения в другую. Первые четыре шага отображения разбивают выражение на три подвыражения. Последний из них переходит непосредственно к e.5 . В первом подвыражении следует найти первый '+' . Начальное значение e.1 становится пустым. Если следующий (т.е., первый) символ есть '+' , переменной e.2 присваивается окончание подвыражения (т.е., все целиком), и осуществляется переход к номеру 9, который относится к переменной e.3 . Если первый символ не является '+' , значение e.1 удлиняется и становится равным этому символу; затем второй символ сравнивается с '+' , и т.д. Когда (и только когда) обнаружен номер 7 символа '+', продолжается поиск номера 10 для '+'.
Если свободная переменная V из Р
принимае6т значение W, это запишется как
подстановка W 
V.
В отличие от общепринятых обозначений,
переменная находится справа. Обоснование: она
принадлежит правой части операции сопоставления
Е : Р, а ее значение
является подвыражением в левой части.
Пусть указанный выше образец отображается на объектное выражение:
(Apples + Peaches + Plums) Cost $45 + 4% (Tax)
(Заметим, что это выражение записано без
кавычек -- способ, которым его следует записывать
для функции Input . Как упомянуто выше, это
можно делать, когда мы оперируем с объектными
выражениями. Если бы это была часть
РЕФАЛ-программы, следовало бы заключать в
кавычки все набираемые символы.) С
использованием введенного обозначения
присваиваний, результат сопоставления выглядит
как:
Tax <- e.5
Apples <- e.1
Peaches + Plums <- e.2
Cost $45 <- e.3
4% <- e.4
Рассмотрим сопоставление:
('METASYSTEM INDEX')'XYZ' : (e.1 s.X e.2) e.3 s.X e.4
Номерами отображения являются следующие:
1 3 4 5 2 6 7 8 ( e.1 s.X e.2 ) e.3 s.X e.4
После того, как выделены два подвыражения, e.1
становится пустым, а s.X проектируется на 'M'
. Затем e.3 становится пустым, а s.X
под номером 7 следует отобразить на начало
второго подвыражения. Однако это невозможно, так
как s.X должно было бы тогда принять
значение 'X' , в то время как оно уже
приняло значение 'M' . Таким образом
объявляется тупиковая ситуация. Последней
открытой переменной является e.3 ,
поэтому она удлиняется и становится равной 'X'
. Но это не помогает, и удлинение e.3
продолжается до тех пор, пока она не станет
равной 'XYZ' и не сможет удлиняться далее.
Затем удлиняется e.1 , и цикл над 'XYZ'
повторяется. Окончательно приходим к успешному
отображению с помощью подстановок:
'METAS' <- e.1
'Y' <- s.X
'STEM_INDEX' <- e.2
'X' <- e.3
'Z' <- e.4
Следует заметить, что порядок, в котором отображаются жесткие элементы образца, не влияют на окончательный результат сопоставления (ни на состояние успех/неудача, ни на значения переменных); уже установлен некоторый порядок (а именно, слева направо) , который полностью определяет только алгоритм сопоставления. Но порядок, в котором отображаются открытые переменные, имеет значение. В приведенном выше примере, если бы мы выбрали первым отображение e.3 :
1 6 7 8 2 3 4 5 ( e.1 s.X e.2 ) e.3 s.X e.4
в результате получилось бы совершенно другое
присваивание значений переменным:
<- e.3
'X' <- s.X
'YZ' <- e.4
'METASYSTEM_INDE' <- e.1
<- e.2
В образце:
e.1'+'e.2(('**')e.1 t.3)
на первый взгляд переменная e.1 является открытой. Но это не так. Одно из вхождений e1 является закрытым, а другое повторным:
9 10 11 2 3 5 6 4 8 7 1 e.1 '+' e.2 ( ( '*' '*' ) e.1 t.3 )
Упражнение 2.5 Назначить отображающие номера и определить тип (закрытое, открытое, повторное) для каждого вхождения e-переменной в следующих образцах:
(a) e.A (t.2)(Sunday)(s.Day s.Night) (b) (e.Word) e.1 ((e.Word) e.Translation) e.2 (c) (e.1'+'e.2'+'e.3)e.1 '+' e.2(e.3)
Упражнение 2.6 Определить результаты следующих сопоставлений:
(a) 'diffident' : e.A t.1 t.1 e.B (b) 'diffident' : e.1 s.X e.2 s.X e.3 (c) '(Texas)' : (e.State) (d) A B C D : e.1 e.2 e.3 D (e) A(A B)(C)((C))D : e.1 e.X e.X e.2
Следует отметить, что на практике при программировании на РЕФАЛе редко используются очень сложные образцы.