1. Описание входного языка Введение Различные описания языка РЕФАЛ отличаются в некоторых деталях. Ва- риант РЕФАЛа, представленный в работах [1, 2], получил название "базис- ного РЕФАЛа". В системе программирования РЕФАЛ-2 для БЭСМ-6 в рамках мониторной системы "Дубна" [3, 4] в качестве входного языка было взято некоторое расширение базисного РЕФАЛа. Это же расширение было реализовано на ЕС ЭВМ [5, 6, 7, 8]. Описываемая здесь система программирования РЕФАЛ-2 для IBM PC, PDP-11 и VAX-11 совместима по входному языку с реализациями для БЭСМ-6 и ЕС ЭВМ. Ниже описан входной язык системы программирования РЕФАЛ-2, который в дальнейшем для краткости именуется просто "РЕФАЛ". При описании неко- торых конструкций языка использована нотация аналогичная форме Бэку- са-Наура, в которой нетерминалы не обрамляются угловыми скобками "<" и ">", а выделяются курсивом. 1.1. Назначение языка Язык РЕФАЛ (алгоритмический язык рекурсивных функций) был создан в качестве абстрактного метаалгоритмического языка, предназначенного для формализации семантики алгоритмических языков [9, 10]. Хотя РЕФАЛ был задуман как метаалгоритмический язык, он представля- ет собой некоторый язык для обработки символьной информации, поэтому, помимо описания семантики алгоритмических языков, он нашел и другие, не менее важные применения. В первую очередь это машинное выполнение гро- моздких аналитических выкладок в теоретической физике и прикладной мате- матике, интерпретация и компиляция языков программирования, машинное до- казательство теорем, моделирование целенаправленного поведения и т.п. Общим для всех этих применений является то, что мы заставляем машину со- вершать сложные преобразования над объектами, определенными в некоторых формализованных языках (алгоритмические языки, язык алгебры, язык исчис- ления предикатов и т.д.). 1.2. Обрабатываемые данные Данные, обрабатываемые РЕФАЛ-программами, являются языковыми объек- тами, т.е. некоторыми последовательностями знаков. В каждой конкретной реализации РЕФАЛа множество знаков - это тот набор литер, который восп- роизводится устройствами подготовки и отображения данных (перфораторами, дисплеями, принтерами и т.д.). Следующие знаки имеют в РЕФАЛ-программах особое (фиксированное) значение: k . < > ( ) / ' = S W V E s w v e + Эти знаки называются специальными знаками. Они имеются в любой реа- лизации РЕФАЛа. Из знаков строятся более крупные единицы - символы, термы и выраже- ния. Символ является минимальной семантической единицей, не расчленимой на составные части средствами языка РЕФАЛ. Символы делятся на два класса: составные символы и символы-литеры (или, как их еще называют, "объектные знаки"). Составной символ имеет следующий вид: /тело_составного_символа/ где тело_составного_символа - это последовательность литер, не содержа- щая литеру "/". Множество составных символов разбивается на непересекающиеся клас- сы, в соответствии с тем, какой вид имеют их тела. В данной реализации РЕФАЛа имеются следующие классы составных символов: символы-метки, сим- волы-числа и символы-ссылки. Символами-метками называются составные символы, телом которых явля- ется идентификатор, т.е. последовательность букв, цифр и знаков "-", на- чинающаяся с буквы. Длина тела символа-метки не ограничивается, однако принимаются во внимание только первые 255 литер, а все последующие игно- рируются. Таким образом, все символы-метки, у тел которых совпадают пер- вые 255 литер, считаются совпадающими. Например, следующие символы являются символами-метками: /ALPHA/ /L2а4/ /ЭтоПримерДлиннойМетки/ /это-пример-другой-длинной-метки/ /Z---Z---/ Строчные буквы в символах-метках заменяются прописными, поэтому, например, символы /ALPHA/, /Alpha/, /alpha/ и т.д. полностью эквивалент- ны. Символами-числами (макроцифрами) называются составные символы, тело которых представляет собой целое неотрицательное число, т.е. последова- тельность десятичных цифр. Например: /0/ /1/ /512/ /23/ Тело символа-числа должно находиться в диапазоне от 0 до 16777215 (2**24-1). Символами-ссылками называются составные символы, тело которых начи- нается с литеры "%", вслед за которой идет восемь шестнадцатеричных цифр. Например: /%00fffac9/ /%ffffffff/ /%abcdefab/ Символы-ссылки нельзя употреблять в качестве констант в РЕФАЛ-прог- раммах. Они порождаются в процессе работы РЕФАЛ-программы и входят в об- рабатываемые выражения. Назначение и использование символов-ссылок будет описано ниже. Символы-метки используются в программах в качестве имен функций. Символы-числа служат для обозначения чисел. Помимо составных символов имеется еще один класс символов - символы -литеры. Символ-литера имеет следующий вид: 'литера' где литера - произвольная литера, отличная от апострофа. Так как апост- роф тоже является литерой, которую нужно уметь обрабатывать, для него имеется особое обозначение: '', т.е. два апострофа, идущих подряд. Сле- дует заметить, что символ ' ' обозначает не апостроф, а литеру "пробел", которая является такой же полноценной литерой, как и все остальные. По аналогии с языком Си в РЕФАЛе допускается использование специ- альных (управляющих) символов, для изображения которых служит обратная косая черта: '\n' - новая строка (перевод строки), '\t' - горизонтальная табуляция, '\v' - вертикальная табуляция, '\b' - возврат на шаг, '\r' - возврат каретки, '\f' - перевод формата, '\\' - обратная косая черта, '\0' - нулевой символ. Кроме того любой символ может быть представлен последовательностью из трех восьмеричных цифр, обрамленных апострофами с предшествующей об- ратной косой чертой '\ddd', которая задает значение символа в коде ASCII, например, символ 'A' эквивалентен '\061'. Более сложным элементом РЕФАЛа является выражение. Оно строится из символов, круглых скобок "(" и ")" (именуемых структурными скобками), угловых скобок "<" и ">" (именуемых функциональными или конкретизацион- ными скобками) и переменных. Структурные скобки придают обрабатываемым объектам структуру дере- ва. Назначение функциональных скобок и переменных объясняется в следую- щих разделах. Выражением называется произвольная последовательность символов, пе- ременных и скобок, правильно построенная относительно скобок. Например: 'A' 'B' 'C' () (('A') 'B'()) () < ( )> Термом называется выражение, которое представляет собой либо сим- вол, либо выражение, заключенное в структурные или функциональные скоб- ки. Например: '+' ( 'A' 'B' 'C' () ) ((()) ()) Таким образом, всякое выражение есть последовательность из некото- рого (быть может нулевого) числа термов. Приведенные выше определения выражения и терма можно формализовать следующим образом: выражение ::= пусто | терм выражение терм ::= символ | переменная | структурный_терм | функциональный_терм структурный_терм ::= ( выражение ) функциональный_терм ::= < выражение > пусто ::= Очень часто приходится иметь дело не с отдельными символами-литера- ми, а с цепочками из нескольких подряд идущих литер. Для таких случаев предусмотрено сокращенное обозначение. а именно, литеры записываются подряд и вся цепочка литер заключается в апострофы. Например, цепочку литер "ABC", изображаемую как 'A' 'B' 'C' можно в сокращенной форме записывать как 'ABC' Если цепочка литер содержит апострофы, они изображаются парами апострофов. При этом цепочка, составленная из одних апострофов, удваива- ется, но апострофами дополнительно не обрамляется. Например: ABC --> 'ABC' A'C --> 'A''C' ' --> '' '' --> '''' 'A'B --> '''A''B' A'B' --> 'A''B''' где стрелка "-->" обозначает слова "изображается в виде". Таким образом, одну и ту же цепочку символов-литер можно изобразить многими способами. Например, цепочка литер "A'B" может быть представлена любым из следующих способов: 'A' '' 'B' 'A''' 'B' 'A' '''B' 'A''B' Для повышения наглядности РЕФАЛ-программы можно вставлять любое ко- личество пробелов между переменными, скобками, составными символами и цепочками литер. Цепочку литер можно разбить на несколько цепочек, но при этом между получившимися частями обязательно должен стоять по край- ней мере один пробел, так как 'A' 'B' обозначает AB 'A''B' обозначает A'B Кроме того, следует обратить внимание на то, что структурные скобки "(" и ")" в РЕФАЛе не являются символами. Поэтому структурные скобки не имеют ничего общего с символами-литерами '(' и ')'. 1.3. Функции Всякая программа, написанная на РЕФАЛе, определяет некоторый набор функций. Каждая из этих функций имеет один аргумент, значениями которого могут быть выражения. Аргументами функций могут быть не произвольные выражения, а только такие, которые не содержат функциональных скобок и переменных. Такие вы- ражения в дальнейшем именуются объектными. В общепринятой математической записи обращение к функции FUNC с ар- гументом имеет следующий вид: FUNC(аргумент) В РЕФАЛе же принят другой синтаксис для вызовов функций: Т.е. вызов функции заключается в функциональные скобки "<" и ">", а имя функции указывается с помощью символа-метки. Точнее, имя вызываемой функции представляет собой часть функционального терма, а именно - пер- вый символ, стоящий после "<". Символ-метку, являющуюся именем функции, допускается записывать сразу за "<", опуская ограничитель "/" слева и справа, т.е. проще: Для обеспечения совместимости с другими реализациями РЕФАЛа в ка- честве конкретизационных скобок допускаются знаки "k" и ".", например: k/FUNC/ аргумент. При таком способе записи вызова функции нельзя опускать ограничите- ли "/" слева и справа у символа-метки. Возникает вопрос, почему же в РЕФАЛе функции имеют только один ар- гумент? Ответ заключается в том, что список из нескольких аргументов яв- ляется некоторым выражением, поэтому всякое обращение к функции от нес- кольких аргументов FUNC(аргумент1, аргумент2, ..., аргументn) можно рассматривать как обращение к функции от одного "большого" аргу- мента: Программа на языке РЕФАЛ представляет собой описание набора функ- ций. Описание каждой функции имеет вид: FUNC лев_часть_1 = прав_часть_1 лев_часть_2 = прав_часть_2 . . . лев_часть_n = прав_часть_n где FUNC - имя функции, а лев_часть_i = прав_часть_i - суть предложения (правила конкретизации). Каждое предложение является указанием для замены одного выражения на другое, поэтому оно состоит из левой части (заменяемое выражение) и правой части (результат замены). Синтаксически лев_частьi и прав_частьi являются выражениями. Перед левой частью каждого предложения должен находиться хотя бы один пробел. Если предложение не помещается в очередной строке, его можно пере- нести на следующие строки. Перенос допускается делать в тех местах, где разрешается вставлять пробелы. В любом из таких мест можно поставить знак "+" и продолжить предложение с любой позиции следующей строки. Семантика РЕФАЛ-программы описывается в терминах абстрактной РЕФАЛ- машины. РЕФАЛ-машина имеет два запоминающих устройства: поле памяти и поле зрения. Перед началом работы в поле памяти заносится описание набора функ- ций, а в поле зрения - выражение, подлежащее обработке. Пусть, например, в поле памяти находится единственное предложение: XXX = '137' а в поле зрения - выражение Тогда РЕФАЛ-машина заменит содержимое поля зрения на выражение '137' и остановится, поскольку в поле зрения не осталось ни одной пары функци- ональных скобок. А что будет, если занести в поле памяти два предложе- ния: XXX = '137' = '274' Теперь для вычисления пригодно не одно, а два предложения. Неоднозначность устраняется следующим образом. РЕФАЛ-машина просматрива- ет предложения в том порядке, в котором они стоят в описании функции и применяет первое из них, которое окажется подходящим. Таким образом, в данном случае будет заменено на '137'. Поле зрения может содержать сколь угодно много функциональных тер- мов, которые могут быть как угодно вложены друг в друга. Поэтому нужно договориться, каким образом РЕФАЛ-машина будет выбирать выражение, с ко- торого надо начинать процесс вычисления. Пусть в поле зрения находится выражение, в котором имеются функцио- нальные термы. Тогда некоторые из этих термов являются самыми внутренни- ми, т.е. не содержат внутри себя других функциональных термов. Самый ле- вый из таких термов мы будем называть ведущим. Теперь опишем работу РЕФАЛ-машины (для частного случая, когда РЕФАЛ -программа не содержит переменных). Работа РЕФАЛ-машины разбивается на шаги. В начале каждого шага РЕ- ФАЛ-машина находит ведущий функциональный терм. Пусть этот терм имеет вид: где FUNC - имя некоторой функции, а аргумент - объектное выражение. Таким образом, предполагается, что содержимое ведущего терма начи- нается с символа-метки. (Случай, когда это не выполнено, будет рассмот- рен позже.) РЕФАЛ-машина находит описание функции FUNC и начинает сравнивать аргумент с левыми частями предложений в описании этой функции. Пусть i - это номер самого первого предложения, для которого лев_часть_i совпадает с аргументом. Тогда РЕФАЛ-машина производит замену ведущего функционального тер- ма, т.е. заменяется на правую часть этого предложения, т.е. прав_часть_i, после чего РЕФАЛ-машина переходит к исполнению следующего шага. Если же РЕФАЛ-машина не находит ни одного предложения, для которого левая часть совпадает с аргументом, она сообщает, что "отождествление невозможно" и останавливается. Это означает, что либо программа на РЕФА- Ле, либо исходные данные для нее заданы неверно. Работа РЕФАЛ-машины продолжается до тех пор, пока в поле зрения имеется хотя бы один функциональный терм. Если же в поле зрения после завершения очередного шага не остается ни одного функционального терма, РЕФАЛ-машина сообщает, что "вычисление окончено" и останавливается. При этом результатом работы РЕФАЛ-машины считается выражение, которое нахо- дится в поле зрения. Пусть, например, поле памяти содержит следующий набор функций: XXX = '137' = '274' YYY = '2' ADD ('137') '2' = '139' А в поле зрения находится выражение ) > Тогда на первом шаге ведущим будет терм , который заменится на '137', в результате чего поле зрения примет вид: > Теперь подлежит вычислению терм , что дает На третьем шаге применяется функция ADD, и в поле зрения оказывает- ся выражение '139' которое уже не содержит функциональных скобок и является окончательным результатом работы РЕФАЛ-машины. 1.4. Переменные Средства, описанные в предыдущих разделах, позволяют описывать только функции, области определения которых - конечные множества, ибо для каждого конкретного значения аргумента приходилось предусматривать особое предложение. Ясно, что так мы далеко не уйдем. Нужно уметь запи- сывать предложения, применимые более, чем к одному объектному выражению. Для этого нужно ввести в предложения переменные, которые при различных применениях предложения могут принимать различные значения. Языковые объекты, с которыми имеет дело РЕФАЛ-машина, это всегда выражения, которые могут быть, в частности, термами или символами. Поэ- тому в РЕФАЛе используются переменные четырех типов: S-переменные, значениями которых могут быть только символы; W-переменные, значениями которых могут быть только термы; V-переменные, значениями которых могут быть только непустые выраже- ния; E-переменные, значениями которых могут быть выражения (в том числе и пустые). Любая переменная имеет следующий вид: признак_типа спецификация индекс Признак_типа - это один из специальных знаков "S", "W", "V" или "E". Он указывает, к какому из четырех вышеперечисленных типов принадле- жит переменная. Спецификация - это описание дополнительных условий, налагаемых на множество допустимых значений переменной. Спецификация может быть пус- той. В этом случае считается, что на возможные значения переменной не налагается никаких дополнительных ограничений. Т.е. значением S-перемен- ной может быть любой символ, значением W-переменной - любой терм, значе- нием V-переменной - любое непустое выражение, значением E-переменной - любое (в том числе и пустое) выражение. Индекс переменной - это либо цифра, либо буква латинского алфавита. Индексы переменных служат для того, чтобы различать между собой различ- ные переменные. Например, S-переменными являются "S1", "S2" и "SA", W-переменными являются "W1" и "Wх", V-переменными являются "V9" и "Vz", E-переменными являются "E1", "E5" и "EA". Разрешив употреблять переменные в левых и правых частях предложе- ний, мы получаем мощное изобразительное средство. Теперь, чтобы решить, применимо ли предложение лев_часть_i = прав_часть_i к некоторому объектному выражению (аргументу), РЕФАЛ-машина должна опре- делить, является ли оно частным случаем левой части предложения, т.е. можно ли вместо переменных, входящих в нее подставить такие значения, чтобы получившееся объектное выражение совпало с аргументом. При этом значения переменных должны быть допустимыми, т.е. соответствовать их ти- пам и спецификациям. Кроме того, все вхождения одной и той же переменной должны заменяться на одно и то же значение. Описанное выше действие РЕФАЛ-машины, по подбору значений перемен- ных, называется синтаксическим отождествлением. В том случае, если отождествление левой части с аргументом возмож- но, предложение является применимым, в противном случае - неприменимым. Теперь мы следующим образом уточним описание работы РЕФАЛ-машины. На каждом шаге РЕФАЛ-машина просматривает описание функции и нахо- дит самое первое применимое предложение. Затем она заменяет ведущий функциональный терм на правую часть этого предложения, предварительно подставив в нее вместо переменных те значения, которые получили эти пе- ременные в результате синтаксического отождествления. Если же окажется, что все предложения функции неприменимы, РЕФАЛ-машина сообщает, что "отождествление невозможно" и останавливается. Разумеется, в правой части предложения разрешается использовать только такие переменные, которые входят в левую часть. Кроме того, все вхождения одной и той же переменной в левую и правую часть должны иметь одинаковый указатель типа переменной. Рассмотрим несколько примеров. Допустим, что нужно описать функцию FIRST-SYM, которая в качестве значения выдает первый символ аргумента. Например, чтобы результатом вычисления терма был символ 'Z', а результатом вычисления был символ /X1/. Для этого достаточно ввести в поле памяти РЕФАЛ-машины следующее описание функции: FIRST-SYM SA EX = SA Аналогично можно описать функцию, значением которой является пос- ледний символ аргумента: LAST-SYM EX SA = SA 1.5. Рекурсивные функции Поскольку правые части предложений могут содержать функциональные скобки, можно описывать функции в терминах других функций или применять рекурсию. Опишем, например, функцию REV, определенную для всех выражений. Значением этой функции является "зеркально перевернутое" исходное выра- жение. Так, вычисление терма должно давать ('F'('DC')'B')'A' Функция REV описывается тремя предложениями: REV E1 SX = SX E1 (EX) = ( ) = Обратите внимание на то, что структурные скобки "(" и ")" не явля- ются символами, и, в отличие от символов-литер '(' и ')', не могут быть значениями S-переменной. Поэтому, если аргумент кончается на правую структурную скобку, то первое предложение функции - не применимо. В этом случае применяется второе предложение. Рассмотрим другой пример. Функция SYMM принимает значение 'Т' если аргумент - симметричное выражение (т.е. такое, которое не изменяется в результате применения к нему функции REV), и принимает значение 'F', ес- ли аргумент не является симметричным выражением. SYMM EX = > EQUAL (EX) EX = 'T' (EX) EY = 'F' Функцию SYMM можно описать и без обращения к функции REV: SYMM = 'T' SX = 'T' SX EA SX = (EA) = () EA () = (WX E1) EA (E2 WY) = EA = 'F' 1.6. Снятие неоднозначности при отождествлении Будем говорить, что некоторая переменная является VE-переменной, если она является V-переменной или E-переменной. Если левая часть предложения содержит несколько VE-переменных, то может случиться, что существует несколько вариантов приписывания пере- менным значений, приводящих к отождествлению левой части предложения с аргументом функции. Пусть, например, в поле памяти находится функция F E1 ';' E2 = а в поле зрения - выражение Это выражение может быть отождествлено с левой частью таким обра- зом, что переменные E1 и E2 примут следующие значения: E1 <-- 'A1:=A2' E2 <-- 'B1:=B2;C1:=C2' Однако, возможен и другой вариант отождествления, при котором пере- менные примут такие значения: E1 <-- 'A1:=A2;B1:=B2;' E2 <-- 'C1:=C2' Следовательно, необходимо договориться, как поступает РЕФАЛ-машина при наличии такой неоднозначности. Для устранения неоднозначности в РЕФАЛе могут использоваться два метода: отождествление слева направо и отождествление справа налево. При отождествлении слева направо РЕФАЛ-машина выбирает тот вариант отождествления, при котором первая слева VE-переменная принимает самое короткое значение. Если это не устраняет неоднозначности, то такой же отбор производится по второй слева VE-переменной, затем - третьей слева и т.д. В нашем примере будет выбран первый из двух способов отождествле- ния. При отождествлении справа налево РЕФАЛ-машина выбирает тот вариант отождествления, при котором первая справа VE-переменная принимает самое короткое значение. Если это не устраняет неоднозначности, то такой же отбор производится по второй справа VE-переменной, затем третьей справа и т.д. В нашем примере будет выбран второй из двух способов отождествле- ния. Если мы хотим, чтобы при применении некоторого предложения исполь- зовалось отождествление справа налево, следует сообщить об этом РЕ- ФАЛ-машине, поместив перед левой частью предложения ключевой знак R, за которым следует хотя бы один пробел. Если же мы хотим, чтобы при приме- нении некоторого предложения использовалось отождествление слева напра- во, следует сообщить об этом РЕФАЛ-машине, поместив перед левой частью предложения ключевой знак L, за которым следует хотя бы один пробел. Если направление отождествления не указано явно, РЕФАЛ-машина счи- тает, что отождествление следует выполнять слева направо, поэтому ключе- вой знак L указывать не обязательно (и он отсутствовал во всех приведен- ных ранее примерах). Например, описанная выше функция F, выдаст в результате замены Но если описать F следующим образом: F R E1 ';' E2 = то результатом замены будет Отождествления слева направо и справа налево широко используются при программировании на РЕФАЛе. В качестве примера рассмотрим функцию MAKE-SET, которая порождает множество термов, входящих в аргумент на ну- левом уровне скобочной структуры. Эта функция просматривает выражение слева направо терм за термом. Для очередного терма проверяется, не стоит ли справа от него точно такой же терм. Если да, то очередной терм вычер- кивается, в противном случае - оставляется. Оставшееся выражение облада- ет тем свойством, что составляющие его термы попарно различны. Например, результатом вычисления будет выражение 'СDBEAF' Функция MAKE-SET описывается следующим образом: MAKE-SET E1 WX E2 WX E3 = E1 E1 = E1 Функция MAKE-SET вычеркивает все вхождения каждого терма, кроме последнего. Нетрудно, однако, описать функцию MAKE-SETR, которая будет вычеркивать все вхождения терма, кроме первого. Для этого можно восполь- зоваться отождествлением справа налево. MAKE-SETR R E3 WX E2 WX E1 = E1 E1 = E1 При желании можно описать функцию MAKE-SET так, чтобы при отождест- влении не возникало неоднозначностей: MAKE-SET WA E1 = = MAKE-SETX WA (E1) WA E2 = WA (E1) WB E2 = WA (E1) = WA Очевидно, что первоначальное описание было короче и нагляднее. Кро- ме того, во втором описании пришлось использовать вспомогательную функ- цию MAKE-SETX. 1.7. Спецификаторы переменных Любая переменная может иметь спецификацию, которая располагается между признаком типа переменной и ее индексом. Спецификации позволяют накладывать дополнительные ограничения на множества допустимых значений переменных. Например, значением SX может быть любой символ, в то время как значением S('ABC')X могут быть только символы-литеры 'A', 'B' и 'C'. Спецификация может иметь одну из следующих форм: пусто имя_спецификатора ( спецификатор ) Таким образом, если спецификация не пуста, она представляет собой либо имя_спецификатора, либо непосредственно сам спецификатор, заключен- ный в скобки. Между левой скобкой "(" и спецификатором, а также между спецификатором и правой скобкой ")" можно вставлять пробелы. В то же время нельзя вставлять пробелы между указателем типа переменной и специ- фикацией, а также между спецификацией и индексом переменной. Во всех местах, где можно вставлять пробелы, можно также поставить знак "+" и перенести предложение на следующую строку. Имя_спецификатора выглядит так же, как символ-метка, за исключением того, что в качестве ограничителей используются не знаки "/", а знаки ":", т.е. имеет вид :идентификатор: Каждый спецификатор представляет собой описание некоторого множест- ва термов. Это описание строится исходя из некоторого набора элементар- ных множеств, которые будут перечислены ниже. Обозначения этих множеств именуются элементами. Допустимы следующие элементы: 1. В качестве элементов могут использоваться имена других специфи- каторов. В этом случае имя спецификатора обозначает множество, которое задает именуемый им спецификатор. 2. Множество, состоящее из одного символа, изображается самим этим символом. Таким образом, в качестве элемента может использоваться любой символ. 3. Имеется еще конечное множество элементов, перечисленных ниже: S - множество всех символов; B - множество термов вида (Eе), где Eе - произвольное объектное вы- ражение; W - множество всех термов; F - множество символов-меток; N - множество символов-чисел; R - множество символов-ссылок; O - множество символов-литер (объектных знаков); L - множество букв (русских и латинских); D - множество десятичных цифр. Последовательность элементов спецификатора называется цепочкой эле- ментов. Цепочка элементов обозначает множество, которое представляет со- бой объединение тех множеств, которые соответствуют элементам цепочки. Таким образом, если цепочка имеет вид X1 X2 ... Xn то она обозначает множество X1 + X2 + ... + Xn где "+" обозначает объединение множеств. Например, LD обозначает мно- жество букв и цифр. Между элементами цепочки можно вставлять произвольное число пробе- лов. Если в цепочке элементов записано несколько символов-литер подряд, их можно слить в одну цепочку литер. Например, 'A' 'B' '' 'C' эквивалентно 'AB''C' В общем случае спецификатор имеет вид: P1(Q1)P2(Q2)...Pn(Qn)P0 где Pi и Qi - произвольные (может быть пустые) цепочки элементов специ- фикатора. Множество значений, изображаемое спецификатором, вычисляется так: - если n=0, т.е. спецификатор имеет вид P0, то он изображает множест- во P0; - если n>0 и P0 - пусто, то следует в конце спецификатора приписать элемент W, т.е. считать P0 равным W. После этого значение спецификатора вычисляется рекурсивно следующим образом. Пусть R1 - это множество термов, изображаемых спецификатором P2(Q2)...Pn(Qn)P0 Тогда множество термов, изображаемое спецификатором P1(Q1)P2(Q2)...Pn(Qn)P0 вычисляется по формуле R = P1 + (R1 - Q1) где "+" обозначает объединение множеств, а "-" обозначает разность мно- жеств. Ниже приведены примеры спецификаторов. Для каждого спецификатора описано множество, которое он изображает. 'ABC' - любой из символов-литер 'A', 'B', 'C'. ('ABC') - любой терм, за исключением символов-литер 'A','B','C'. ('A') L - любая буква, за исключением буквы 'A'. ('A')L('0')N - любая буква, за исключением буквы 'A' или любая циф- ра, за исключением цифры '0'. Множество значений, обозначаемое спецификатором, можно найти и дру- гим способом. Можно рассматривать спецификатор как предикат, который оп- ределен на множестве термов и для каждого терма вырабатывает одно из двух значений: "истина" или "ложь". Допустим, что задан некоторый терм и нужно узнать, удовлетворяет он спецификатору или нет. Для этого просматриваем спецификатор слева напра- во, элемент за элементом, пока не встретим самый первый элемент, которо- му удовлетворяет проверяемый терм. После этого спецификатор дальше не просматривается и вырабатывается значение "истина" или "ложь". Если найденный элемент принадлежит Qi, т.е. находится внутри ско- бок, то вырабатывается значение "ложь", а если принадлежит Pi, т.е. на- ходится не в скобках, - то вырабатывается значение "истина". Если же мы дошли до конца спецификатора и не нашли ни одного эле- мента, которому удовлетворял бы проверяемый терм, то следует посмотреть, чем заканчивается спецификатор. Если он оканчивается на правую скобку, вырабатывается значение "истина", в противном случае - "ложь". В соответствии с принятыми соглашениями пустой спецификатор обозна- чает пустое множество, а спецификатор вида "()" - множество всех термов. Элементарные множества, обозначаемые элементами спецификатора, об- ладают следующим свойством: для любых двух элементарных множеств X1 и X2 либо пересечение X1 и X2 пусто, либо X1 - подмножество X2, либо X2 - подмножество X1. Поэтому можно доказать, что если два спецификатора представляют множества R1 и R2, то можно представить некоторыми специфи- каторами также R1+R2, R1*R2 и R1-R2, где "+", "*" и "-" обозначают объ- единение, пересечение и разность множеств соответственно. Таким образом, множество спецификаторов замкнуто относительно теоретико-множественных операций. Имена спецификаторов описываются с помощью ключевого знака S. Эти описания имеют следующий вид: идентификатор S спецификатор где идентифтикатор - имя спецификатора без ограничителей ":", например: ADDOP S '+-' MULTOP S '*/' Теперь имена :ADDOP: и :MULTOP: можно употреблять в качестве специ- фикаций и в качестве элементов других спецификаторов. Например, значени- ем переменных S:ADDOP:X и S:ADDOP:Y может быть только '+' или '-'. Опишем более подробно, какой смысл имеют спецификации для перемен- ных различных типов. Спецификация вида :ID: равносильна спецификации (:ID:). Например, переменная S:ZZZ:1 имеет то же множество допустимых значений, что и пе- ременная S(:ZZZ:)1. Если спецификатор задан для S- или W-переменной, то это означает, что значение переменной должно принадлежать множеству, которое описывает спецификатор. Если спецификатор задан для VE-переменной, то это означает, что каждый терм значения переменной, стоящий на нулевом уровне скобочной структуры, должен удовлетворять спецификатору. Например, E('+-')X - это последовательность (может быть пустая) из литер '+' и '-', E(B)X - это выражение вида (E1) (E2) ... (EN), а S(L)X E(LD'-')Y - это идентификатор. В то же время, E(('+-'))X - это выражение, которое не содержит на нулевом уровне скобок ни одной литеры '+' или '-'. Например, в качестве значения годится ('+')('-') , но не годится '+'('-') . Если у переменной есть несколько вхождений в левую часть, то у каж- дого вхождения может быть своя спецификация. Во время отождествления значение каждого вхождения должно удовлет- ворять спецификации этого вхождения. Таким образом, получается, что мно- жество допустимых значений переменной - это пересечение множеств допус- тимых значений ее вхождений. Например, предложение: S(('A'))X S(('B'))X = SX равносильно S(('AB'))X SX = SX Все спецификации, которые заданы для вхождений переменных в правую часть предложения - игнорируются. На использование имен спецификаторов наложено следующее ограниче- ние: если имя некоторого спецификатора используется при описании другого спецификатора, то оно должно быть описано раньше. Благодаря этому ограничению запрещаются циклические определения вроде SPC1 S :SPC2: SPC2 S :SPC1: Приведем примеры использования спецификаторов. Функция IDENT отщепляет от аргумента слева идентификатор максималь- ной длины. IDENT S(L)X E1 = E1 = '*' E1 IDENT1 (EI) S(LD)A E1 = (EI) E1 = (EI) E1 Если использовать отождествление справа налево и специфицированные E-переменные, ту же функцию можно записать короче: IDENT R S(L)X E(LD)Y E1 = (SX EY) E1 E1 = '*' E1 По семантике РЕФАЛа в первом предложении нужно подобрать самое ко- роткое E1, при котором возможно отождествление. Но ведь самому короткому E1 соответствует самое длинное EY! Компилятор распознает такие случаи, и вместо того, чтобы несколько раз удлинять значение E1, он сразу же, слева направо наберет максимально возможное EY. Еще один пример. Функция ERASE-BL просматривает цепочку символов и заменяет каждую группу из нескольких последовательно идущих пробелов на один пробел. ERASE-BL E1 ' ' E2 = E1 ' ' E1 = E1 ERASE-BL- R E(' ')X E1 = 1.8. Общая структура программы В системе программирования РЕФАЛ-2 тексты исходных РЕФАЛ-программ подготавливаются в виде последовательных файлов, которые хранятся на ма- шинных носителях. РЕФАЛ-программы можно либо создавать с помощью стан- дартных редакторов текстов. В любом случае РЕФАЛ-программа представляет собой последователь- ность записей. Запись - это отдельная строка текстового файла. Для совместимости с предыдущими реализациями РЕФАЛ-система исполь- зует только первые 72 позиции, остальные позиции игнорируются и обычно используются для нумерации записей. Любой знак в 72 позиции эквивалентен знаку "+", т.е. означает продолжение Рефал-предложения в следующей запи- си. Все записи делятся на два класса: комментарии и директивы. Записи-комментарии начинаются с литеры "*" (перед которой разреша- ется вставлять от 1 до 70 пробелов). В позициях после "*" они содержат произвольную информацию. Эти за- писи игнорируются РЕФАЛ-системой и не влияют на смысл РЕФАЛ-программы. Записи, которые не являются записями-комментариями, содержат дирек- тивы. РЕФАЛ-программа представляет собой последовательность директив. Каждая директива занимает одну или несколько рядом расположенных запи- сей. Пока что будем предполагать, что каждая директива занимает отдель- ную запись. Правила переноса директив с одной записи на другую будут описаны ниже. Все директивы имеют следующий вид: идентификатор ключ информация где ключ - это ключевой знак или слово, а информация зависит от типа ди- рективы. Присутствие всех трех компонентов директивы не обязательно: часть из них может отсутствовать. Идентификатор отделяется от ключа одним или несколькими пробелами. Если идентификатор опущен, запись должна начи- наться хотя бы с одного пробела. Ключ отделяется от инфтормации одним или несколькими пробелами. Если ключ опущен, а инофрмация начинается с буквы, перед ней должен быть хотя бы один пробел. Допускаются записи, состоящие из одних пробелов. Они не влияют на смысл РЕФАЛ-программы и могут использоваться для улучшения ее читаемос- ти. В качестве ключевых слов допускаются следующие цепочки литер: EMPTY END ENTRY EXTRN L R S SWAP START Основное место в РЕФАЛ-программах занимают предложения, которые служат для описания функций и с которыми мы познакомились ранее. Предло- жения представляют собой директивы с ключевым знаком L или R, причем знак L разрешается опускать. Другой известный нам тип директив - это S-директивы, которые имеют ключевой знак S и служат для описания спецификаторов. Директива, в которой присутствует идентификатор, а ключ опущен или представлен знаками L или R, является признаком начала описания новой функции. А именно, все последующие директивы-предложения, вплоть до на- чала описания следующей функции, считаются относящимися к этой функции. Все прочие директивы будут описаны в последующих разделах. В заключение опишем правила переноса директив с одной записи на другую. Для перехода с одной записи на другую имеется два способа: 1) литера "+" в любой позиции, в которой допустимо вставить пробел; 2) любая литера, отличная от пробела, в 72 позиции. Назовем элементами предложения следующие объекты: цепочку объектных знаков (заключенную в апострофы), составной символ, свободную перемен- ную, знаки "<", ">", "=", "(", ")", "k", ".". Между любыми двумя элементами предложения разрешается вставлять произвольное число пробелов. Кроме того, разрешается вставлять пробелы и между элементами спецификатора и скобками, входящими в спецификатор. Например, спецификатор ('A')LD эквивалентен ( 'A' ) L D. В то же время, нельзя вставлять пробелы между признаком типа переменной и спецификаци- ей, а также между спецификацией и индексом переменной. Теперь правило переноса с помощью "+" формулируется следующим обра- зом: в любом месте, где могут быть вставлены дополнительные незначащие пробелы, можно вставить знак "+" и продолжить директиву с любой позиции следующей записи. Пример. Функцию FUNC E1 '+' E2 = (E1) '+' (E2) S(('+-')ON)X = SX E1 = E1 можно записать следующим образом: FUNC + E1 + '+' + E2 + = + ( E1 + ) '+' (E2) S( + ( + '+-' + ) + O + N + )X = SX E1 = E1 Второй способ переноса - любая литера, отличная от пробела, в 72 позиции. В этом случае (если перенос не был уже сделан с помощью знака "+") первая позиция следующей записи считается непосредственно следующей за 71 позицией текущей записи. Таким образом, директива может быть "разре- зана" в любом месте. Второй способ переноса особенно удобен при автоматической генерации РЕФАЛ-программ, так как можно сначала породить директиву нужного разме- ра, а затем нарезать ее на куски размером в 71 литеру. 1.9. Пустые функции В некоторых случаях возникает желание описывать пустые функции, т.е. функции, описания которых содержат нулевое число предложений. Эти функции имеют пустую область определения, т.к. при любом обращении к та- кой функции возникает останов "отождествление невозможно". Пустые функции обычно бывают полезны, если нужны символы, которые заведомо отличаются от всех остальных и которые имеют удобные для чело- века графические представления. Пустые функции могут быть описаны с помощью директивы EMPTY, кото- рая имеет следующий вид: EMPTY идент_1,идент_2,...,идент_n ,где идент_1, идент_2, ..., идент_n - имена определяемых пустых функций. например: EMPTY ALPHA,PSI Пустые функции можно описывать и еще одним способом: с первой пози- ции записывается идентификатор, а в следующих позициях директивы остают- ся пробелы, например: ALPHA PSI 1.10. Модули Часто бывает удобно разбить РЕФАЛ-программу на части, которые могут обрабатываться компилятором РЕФАЛа независимо друг от друга. Наименьшая часть РЕФАЛ-программы, которая может быть обработана компилятором независимо от других, называется модулем. Результат компиляции исходного модуля на РЕФАЛе представляет собой объектный модуль, который перед исполнением РЕФАЛ-программы должен быть объединен с другими модулями, полученными компиляцией с РЕФАЛа или дру- гих языков. Это объединение (компоновка) выполняется с помощью редактора связей (компоновщика). Детали зависят от используемой операционной сис- темы. Исходный РЕФАЛ-модуль должен начинаться с директивы START и кон- чаться директивой END. Эти директивы имеют следующий вид: имя_модуля START END где имя_модуля - цепочка латинских букв и цифр длиной не более 8, начи- нающаяся с буквы. Имя модуля может быть опущено. Функции, описанные в разных модулях, могут обращаться друг к другу. Если в некотором модуле используется функция, которая описана в другом модуле, эту функцию следует объявить внешней по отношению к данному мо- дулю с помощью директивы EXTRN. Если в некотором модуле описана функция, к которой есть обращения из других модулей, эта функция должна быть объявлена входной точкой дан- ного модуля с помощью директивы ENTRY. Директивы ENTRY и EXTRN имеют идентичный формат: ENTRY идент_1,идент_2,...,идент_n EXTRN идент_1,идент_2,...,идент_n где идент_i - описание входной точки или внешней метки, соответственно. Идентi может иметь одну из двух следующих форм: идентификатор идентификатор(внешний_идентификатор) где внешний_идентификатор - это последовательность латинских букв и цифр длиной не более 8, начинающаяся с буквы. Если кроме имени функции задан еще внешний идентификатор, это озна- чает, что за пределами модуля (в среде, "окружающей модули") функция имеет "внешнее" имя, которое отличается от "внутреннего" имени функции, употребляемого внутри модуля. Таким образом одна и та же функция может иметь разные внутренние имена во всех модулях, в которых она использует- ся, но ровно одно, одинаковое для всех модулей внешнее имя. Если при описании функции в директиве ENTRY или EXTRN внешнее имя не задано, то считается, что внешнее имя совпадает с внутренним. Ограничения, налагаемые операционными системами, таковы, что внеш- ние имена могут содержать только латинские буквы и иметь длину не более 8. Поэтому, в тех случаях, когда внутреннее имя содержит русские буквы, отличные от латинских или имеет длину более 8 литер, следует указывать внешнее имя. В случае слишком длинного имени оно усекается до 8 симво- лов. Пример. Пусть имеется два модуля M1 и M2. В модуле M1 описана функ- ция COMMUNICATION, а в модуле M2 - функция DREAM и пусть эти функции ис- пользуются в модулях M2 и M1, соответственно. Тогда эти модули могут иметь следующую структуру: M1 START ENTRY COMMUNICATION(COMMUN) EXTRN DREAM COMMUNICATION E1 '+' E2 = + END M2 START ENTRY DREAM EXTRN общение(COMMUN) DREAM SX E1 = SX <общение E1> END Здесь функция, которая имеет внутреннее имя COMMUNICATION в модуле M1, имеет внутреннее имя "общение" в модуле M2 и внешнее имя COMMUN. С помощью директив ENTRY и EXTRN можно объявлять входными и внешни- ми не только имена функций, но и имена спецификаторов. Каждое имя, которое употребляется внутри модуля, должно быть описа- но либо как имя внутренней функции или спецификатора, либо как имя внеш- ней функции или спецификатора в директиве EXTRN. 1.11. Первичные функции Во многих случаях возникает необходимость из программ, написанных на РЕФАЛе вызывать программы, написанные на других языках или непосредс- твенно в командах машины. Эта необходимость возникает, в частности, в тех случаях, когда требуется выполнять операции ввода/вывода, операции над числами и другие, которые РЕФАЛ-машина "не умеет" выполнять непос- редственно. Функции, описанные не на РЕФАЛе, которые, тем не менее, можно вызы- вать обычным способом из программ, написанных на РЕФАЛе, называются пер- вичными. Собственно говоря, с точки зрения РЕФАЛ-модуля первичные функции - это просто некоторые функции, внешние по отношению к данному модулю, по- этому, вызывая какую-либо функцию можно даже не знать, что это - первич- ная функция или функция, написанная на РЕФАЛе. Разница состоит только в том, что исполнение вызова первичной функции занимает только один шаг с точки зрения РЕФАЛ-машины, в то время как исполнение вызова обычной функции может занять несколько шагов. Набор первичных функций, предоставляемых в данной реализации, будет описан отдельно. Помимо этих первичных функций пользователь может писать и собственные на языке Си. Как это сделать будет описано отдельно. 1.12. Копилка До сих пор мы считали, что РЕФАЛ-машина имеет два запоминающих уст- ройства: поле памяти и поле зрения. В действительности у нее имеется еще одно запоминающее устройство: копилка, доступ к которому возможен с по- мощью первичных функций BR, DG, CP, RP, DGALL. Имена этих функций имеют следующий смысл: ВR - закопать (bury), DG - выкопать (dig out), СР - скопировать (copy), RР - заменить (replace), DGALL - выкопать все (dig out all). Содержимое копилки всегда имеет следующий вид: (V1'='E1) (V2'='E2) ... (Vn'='En) где V1, V2, ..., Vn и E1, E2, ..., En - произвольные объектные выраже- ния. Смысл содержимого копилки следующий: Vi - есть имя выражения Ei. Перед началом работы программы копилка содержит пустое выражение. Функции ВR, DG, RР и СР предназначены для перемещения выражений из поля зрения в копилку и обратно. обращения к ним имеют следующий вид: <ВR V1 '=' E1> <ВR 'V=B'> копилка преобразуется следующим образом: E0 --> ('V=B')('V=A') E0 Функция DG (выкопать). Функция DG просматривает копилку слева направо в поисках терма вида (Vx'='Ey) и, если находит, удаляет его из копилки и выдает Ey в качестве результата замены. Это можно изобразить следующим образом: поле зрения: --> Ey копилка: E1 (Vx'='Ey) E2 --> E1E2 Если в копилке несколько выражений закопаны под одним именем, то выкапывается самое левое из них, т.е. то, которое закапывалось послед- ним. При повторном обращении к DG с тем же аргументом Vx будет выкопано выражение, закопанное предпоследним и т.д. Если DG не находит в копилке нужного терма, она выдает в качестве результата замены пустое выражение. Функция СР (скопировать). Функция СР, так же, как и функция DG, находит в копилке выражение по имени и выдает его в качестве результата, но копилка при этом не из- меняется, т.е. в поле зрения формируется копия выражения. Таким образом СР работает так: поле зрения: --> Ey копилка: E1 (Vx'='Ey) E2 --> E1 (Vx'='Ey) E2 Если под именем Vx ничего не закопано, СР выдает "пусто". Функцию СР можно было бы следующим образом описать через ВR и DG: CP EX = > CP1 (EX) EY = EY
E1 (Vx'='Ey) E2 Если под именем Vx ничего не закопано, то функция RР делает то же самое, что и ВR. Эквивалентное описание на РЕФАЛе имеет вид: RP EX '=' EY = >
SW2 SX SY = < SX < SY < SX>>> В процессе вычисления обращения в ящики X1 и X2 сначала занесутся символы 'A' и 'B', соответственно. За- тем, в результате вычисления терма ящики поменяются содержимым. Т.е. в ящике X1 окажется символ 'B' ,в ящи- ке X2 - символ 'A' , а в поле зрения останется пустой результат замены. Динамические ящики порождаются в процессе работы программы первич- ной функцией NEW. Функция NEW. В результате вычисления терма создается новый ящик и в него помещается выражение E1. Одновременно по- рождается новый символ-ссылка Rr, который остается в поле зрения в ка- честве результата замены. Символ Rr является именем новой обменной функ- ции, обеспечивающей доступ к созданному ящику. Имена динамических ящиков являются символами особого типа - симво- лами-ссылками. В отличие от имен статических ящиков, являющихся обычными символами-метками, символы-ссылки нельзя употреблять в виде констант в РЕФАЛ-программах. Тем не менее, при отладке РЕФАЛ-программ возникает не- обходимость как-то печатать символы-ссылки. Они печатаются в виде /%hhhhhhhh/ где "hhhhhhhh" - восемь шестнадцатеричных цифр, представляющих собой ад- рес места, по которому расположен динамический ящик в памяти машины. В каждый момент работы программы различным символам-ссылкам соот- ветствуют различные адреса. Один и тот же символ-ссылка имеет один и тот же адрес на протяжении одного запуска программы. Пример. Рассмотрим следующий фрагмент программы, аналогичный приве- денному в предыдущем примере. EXTRN NEW SWR1R2 = > SW2 SX SY = < SX < SY < SX>>> В результате вычисления терма будут выполнены два обраще- ния к функции NEW. В результате чего образуются два ящика, которые могут иметь, например, следующие имена: /%00070613/ и /%00053024/. Ящик /%00070613/ будет содержать символ 'A', а ящик /%00053024/ - символ 'B'. Затем функция SW2 воспользуется символами-ссылками, оставшимися в поле зрения, и поменяет местами содержимое этих ящиков. Обратите внимание на следующий факт: обращение к функции SWR1R2 привело к появлению двух новых ящиков. Можно ли теперь как-нибудь изв- лечь содержимое этих ящиков? Очевидно, что нельзя. Ни в поле зрения, ни в копилке, ни в других ящиках не сохранилось имен этих ящиков. Поэтому дальнейшая работа программы не изменится, если эти ящики уничтожить. Ясно, что если обращаться к функции SWR1R2 много раз, то память РЕ- ФАЛ-машины будет забиваться ненужными ящиками. Конечно, для абстрактной РЕФАЛ-машины это не имеет никакого значения, ибо ее память потенциально бесконечна, но память реальной вычислительной машины рано или поздно должна исчерпаться. Поэтому во всех реализациях РЕФАЛа-2 предусмотрен механизм сборки мусора. Сборка мусора автоматически запускается каждый раз, когда исчерпа- ется свободная память. При этом обнаруживаются и удаляются все ящики, к которым невозможно добраться прямо или косвенно из поля зрения, копилки или статических ящиков. На следующем рисунке изображены поле зрения, ко- пилка и динамические ящики, пронумерованные цифрами от 1 до 8. Звездочки изображают некоторые элементы выражений, которые не являются символа- ми-ссылками. Символы-ссылки обозначены цифрами. поле зрения копилка ___________________ * 1 * * * * * 2 * * * * * | | | | (7): 3 * * 8 (8): 7 * (1): * 4 * * (2): * * 4 * 5 _____________ / |_____| |_______________| |/ \ / (4): * * (5): * 6 * 3 * \ | / \ / \ | (6):* 4 (3):* 5 * * |____________________________| Очевидно, что по ссылке из поля зрения можно добраться до ящика 1, а из него - до ящика 4. Из копилки можно непосредственно добраться до ящика 2 и косвенно (через ящик 2) до ящиков 4, 5, 6, 3. Таким образом, нет способа извлечь информацию из ящиков 7 и 8. Если в этот момент за- пустить сборку мусора, то ящики 7 и 8 будут уничтожены. Если теперь уб- рать символ-ссылку из поля зрения, то станет недоступным и ящик 1. Если же символ-ссылку в поле зрения оставить, но убрать ссылку из копилки, то окажутся ненужными все ящики, кроме 1 и 4. Опишем теперь пять первичных функций, которые часто оказываются удобными для работы с содержимым ящиков. Функция GTR (взять по ссылке). Извлекает содержимое ящика. Результатом замены при вычислении терма где Sr - имя статического или динамического ящика, является содержимое ящика. При этом в ящике остается пустое выражение. Функция RDR (прочитать по ссылке). Как и GTR выдает содержимое ящика в поле зрения, но ящик при этом не изменяется, т.е. происходит копирование его содержимого. Функция PTR (положить по ссылке). Добавляет в ящик новую информацию. В результате вычисления терма где Sr - имя ящика, а E1 - произвольное объектное выражение, ящик меня- ется так: E0 --> E0E1 где E0 - старое содержимое ящика. Результатом замены является пустое вы- ражение. Функция WTR (записать по ссылке). Помещает в ящик новую информацию, при этом старое содержимое ящика уничтожается. Т.е. при вычислении терма где Sr - имя ящика, E1 - произвольное объектное выражение, содержимое ящика меняется так: E0 --> E1 где E0 - старое содержимое ящика. Результатом замены является пустое вы- ражение. Функция SWR (обменять по ссылке). Записывает в ящик новую информацию, а старую выдает в поле зрения. Таким образом происходит такое преобразование поле зрения: --> E0 ящик: E0 --> E1 где Sr - имя ящика; E0 и E1 - объектные выражения. Эти функции можно было бы описать на РЕФАЛе следующим образом: GTR SX = < SX> RDR SX = > RDR1 SX EY = EY < SX EY> PTR SX EY = < SX < SX> EY> WTR SX EY = > WTR1 EY = SWR SX EY = < SX EY> Отличие этих функций от соответствующих первичных функций состоит в том, что они не проверяют, что SX - имя ящика, поэтому их область опре- деления шире, чем у соответствующих первичных функций.