Язык рефал


Содержание

Язык рефал

Ура! Сегодня, 30.05.2005, наконец появилась адаптированная к современным платформам Windows-(95/98/ME/NT/2000/XP) и UNIX (FreeBSD, Linux) реализация языка Рефал-2. Работа выполнена по открытой лицензии и свободно доступна для любых применений, включая коммерческое использование.
Подробности на рефал-сайте http://www.refal.net/

belous/refal2-r.htm ) .

    Другие рефал-сайты:
  • Cодружество «РЕФАЛ/Суперкомпиляция»
  • Сервер Группы пользователей и разработчиков языка РЕФАЛ
  • Refal+ programming language
  • Институт РЕФАЛа
  • Благодарности
  • Обо мне
  • История написания версии рефала
  • Лицензия
  • Компилятор в форму удобную для интерпретации
  • Выполнение программы на рефале (интерпретатор)
  • Встроенные рефал-функции (машинные процедуры)
  • Полезные рефал-функции (написанные на рефале)
  • Другие рефал-функции (написанные на рефале)
  • Рефал — это просто! См. Пример программы на рефале
  • Новости

Выполнение программы на рефале (интерпретатор)

В настоящее время имеется три версии программы интерпретатора рефала:

  • refal.exe — MS DOS версия [скачать: программу (14652 байта), исходники ]
  • refalb.exe — Win32-консольное приложение [скачать: программу (42342 байта), исходники (38907 байт), вариант портированный на FreeBSD Дм.Подкорытовым (32281 байт) в нем подправлен баг (не контролировался дескриптор файла после попытки открытия) и переведены на английский сообщения компилера ]
  • refalw.exe — Win32-неконсольное приложение [скачать: программу (15102 байта), исходники (47473 байта)]

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

Хочу выразить свою благодарность Топунову Владимиру Леонидовичу, который в конце 70-х годов прошлого XX-го века привлек меня к работе с этим замечательным языком программирования.

Хочу также выразить признательность Леониду Белоусу, предложившему включение моего сайта в число сайтов рефал-диаспоры и этим стимулировавшему существенное расширение его части посвященной Рефалу.

Не могу также не отметить Алексея Веденова и Сергея Романенко, знакомство с исходными текстами рефал-систем которых существенно облегчило выполнение этой реализации Рефал/2, избавив от страха непосильности задачи.

История написания этой версии Рефала

В апреле-мае 1998, когда появились задачи с текстовой обработкой данных (формирование html-страниц для публикации библиотечных указателей в интернет), не найдя дистрибутива рефала в Интернет (сейчас есть Сервер Группы пользователей и разработчиков языка РЕФАЛ, не говоря уж о сервере Cодружества «РЕФАЛ/Суперкомпиляция»), написал на Turbo-C простенький интерпретатор языка сборки (скачать 5382 байта 06.05.98). Написал на Макро-ассемблере (командами определения данных) простенький компилятор исходного текста программы на язык сборки (скачать 8048 байт 06.05.98). И скомпилировал первую версию компилятора на язык сборки на самом же рефале (скачать 2396 байт 06.05.98). Далее в несколько итераций этот комилятор улучшил. [см. Базисный рефал и его реализация на вычислительных машинах (методические рекомендации). М.: ЦНИИПИАСС, 1977. — 258 с. (Фонд алгоритмов и программ для ЭВМ в отрасли «Строительство». Вып. V-40). ]

Компилятор в форму удобную для интерпретации

Компилятор в форму удобную для интерпретации, а точнее на язык сборки [см. Базисный рефал и его реализация на вычислительных машинах (методические рекомендации). М.: ЦНИИПИАСС, 1977. — 258 с. (Фонд алгоритмов и программ для ЭВМ в отрасли «Строительство». Вып. V-40). ] написан на самом рефале.
Скачать: программу (3998 байт), исходный текст (3976 байта)

Пример выполнения компиляции.
Если Вы сохранили Пример программы на рефале, например, под именем a.ref , то командные строки на компиляцию этой программы при помощи трех различных версий рефал-интерпретатора будут выглядеть так: refal.exe refal.cm a.ref a.cm >a.1
refalb.exe refal.cm a.ref a.cm >a.1
refalw.exe refal.cm a.ref a.cm a.1
здесь refal.cm — компилятор рефала (в форме удобной для интерпретации);
a.ref — исходный текст компилируемой рефал-программы;
a.cm — результат компиляции;
a.1 — протокол выполнения — может содержать сообщения об ошибках компиляции. Для выявления возможных неточностей в работе компилятора в случае возникновения ошибки в копилируемом тексте после диагностического сообщения выдается Поле зрения рефал-машины на момент определения ошибки, и процесс компиляции завершается. Ограничения реализации

    В данной реализации вызывает ошибку при компиляции:
  • использование пустых и пробельных строк;
  • использование знаков табуляции (не в константах);
  • использование комментария в первой строке программы.
  • 29.01.2020 Наконец-то понадобилась функция LAST — выделение последних n термов. Написал ее на рефале (как аналог FIRST).
  • 25.10.2015 Добавил текст программы Конвертирование во входной формат ИРБИС
  • 25.01.2013 Наконец-то понадобилась функция CVBN. Написал ее на рефале.
    Очередной раз написал перевод строки в 16-ричный вид.
  • 15.12.2010 Добавил функции ADD, SUB, MUL, DR, AD2, GETS, FLEN и LSEEK см. Встроенные рефал-функции (машинные процедуры)
  • 25.11.2010 Перекомпилировал Интерпретатор в BCC32 версии 5.5.1 for Win32. Добавил функцию CHR см. Встроенные рефал-функции (машинные процедуры)
  • 18.04.2008 Добавил раздел Другие рефал-функции (написанные на рефале)
  • 24.11.2006 Описал работу с файлами см. Встроенные рефал-функции (машинные процедуры) с примерами чтения и записи
  • 06.10.2006 Наконец реализовал общую работу с файлами см. Встроенные рефал-функции (машинные процедуры)
  • 30.03.2004 Добавлен вариант портированный на FreeBSD Дм.Подкорытовым см. Выполнение программы на рефале
  • 21.11.2003 Добавлены исходники функций add, mul, ЗП и FIRST
  • 18.11.2003 Добавлены исходники «исторической» версии программы
  • 14.11.2003 Разрешены ссылки скачать в подразделах Интерпретатор и Компилятор
  • 10.11.2003 Начата разработка части сайта, посвященной языку программирования Рефал/2 и моей реализации этого языка. Предполагается применение в отношении Рефала принципов Open Source, т.е. все рассматриваемые программы будут доступны и снабжены исходными текстами.

Понравилась мне Лицензия Леонида Белоуса, да еще и принципа Open Source в отношении рефала я стал придерживаться по его инициативе. поэтому получилось очень похоже.

Копирайт c 2003 Василий Стеллецкий
Все права сохранены.

Разрешаются дальнейшие распространение и использование, как в исходном, так и в двоичном видах, с модификацией или без неё, при соблюдении следующих условий:

  1. Дальнейшие распространения исходного кода должны воспроизводить предупреждение из предыдущего копирайта, указанный перечень условий и приведенный ниже отказ от обязательств и гарантий.
  2. Дальнейшие распространения в двоичном виде должны воспроизводить предупреждение из предыдущего копирайта, указанный перечень условий и последующий отказ в документации и/или в других материалах, предусматриваемых при дистрибутиве.
  3. Имя автора не может быть использовано при рекламировании либо при продвижении продуктов, полученных с помощью указанного программного обеспечения, без специального предварительного письменного на то разрешения.

ЭТО ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПОСТАВЛЯЕТСЯ АВТОРОМ «КАК ОНО ЕСТЬ» БЕЗ ЛЮБЫХ ЯВНЫХ ИЛИ ПОДРАЗУМЕВАЕМЫХ ГАРАНТИЙ, ВКЛЮЧАЯ, ПОДРАЗУМЕВАЕМЫЕ ГАРАНТИИ ПРИБЫЛЬНОСТИ И ПРИМЕНИМОСТИ СО СПЕЦИАЛЬНОЙ ЦЕЛЬЮ.
НИ В КОЕМ СЛУЧАЕ АВТОР НЕ БУДЕТ НЕСТИ ОТВЕТСТВЕННОСТЬ ЗА ЛЮБЫЕ ПРЯМЫЕ, КОСВЕННЫЕ, СЛУЧАЙНЫЕ, НАМЕРЕННЫЕ, ОБРАЗЦОВЫЕ ЛИБО ПРОИСТЕКШИЕ УБЫТКИ (ВКЛЮЧАЯ, НО НЕ ИСКЛЮЧАЯ, ПОСТАВКИ СУРРОГАТНЫХ ТОВАРОВ ИЛИ УСЛУГ; ПОТЕРЮ ПРИМЕНИМОСТИ, ДАННЫХ, ИЛИ ПРИБЫЛЕЙ; ИЛИ НАРУШЕНИЕ БИЗНЕСА) И ВСЕ ЖЕ ОСНОВАННЫЕ НА ЛЮБОЙ ТЕОРИИ ОТВЕТСТВЕННОСТИ, БУДЬ ТО КОНТРАКТ, СТРОГАЯ ОТВЕТСТВЕННОСТЬ, ИЛИ ГРАЖДАНСКО-ПРАВОВОЙ ДЕЛИКТ (ВКЛЮЧАЯ ХАЛАТНОСТЬ ИЛИ ЧТО-ЛИБО ЕЩЕ) ВОЗНИКАЮЩЕЕ ПРИ ЛЮБОМ СЛУЧАЕ ЗА ПРЕДЕЛАМИ ИСПОЛЬЗОВАНИЯ ЭТОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ, ДАЖЕ В СЛУЧАЕ ИЗВЕЩЕНИЯ О ВОЗМОЖНОСТИ ТАКОГО УЩЕРБА.

АНКЕТА ДЛЯ ЗАПОЛНЕНИЯ СТУДЕНТАМИ 3 КУРСА

В учебном пособии описываются ключевые понятия и базовые механизмы функционального языка Рефал – одного из немногих отечественных языков программирования, получивших известность за рубежом. В последние годы учебные материалы по этому языку не публиковались, и данное пособие восполняет этот пробел. Рассматриваются особенности двух наиболее известных диалектов языка (Рефал-2 и Рефал-5), подробно разбираются примеры рефал-программ. В пособие включено также описание заданий практикума на языке Рефал, проводимого для студентов кафедры алгоритмических языков факультета ВМиК МГУ. >>>

С о д е р ж а н и е : Назначение языка, Обрабатываемые данные, Функции, Переменные, Рекурсивные функции, Снятие неоднозначности при отождествлении, Спецификаторы переменных, Общая структура программы, Пустые функции, Модули, Первичные функции, Копилка, Статические и динамические ящики. &nbsp >>>

340 Kb. &nbsp Скачать &nbsp &nbsp (Документация в папке DOC)

Так же возможно написание на версиях, описанных на http://www.refal.net/. Но проблема со сдачей тогда лежит на Вас. Если версия будет требовать установки, то сдавать в маш.зале не получится. Приходите со своими ноутбуками.

NOTEPAD

Удобные текстовые редактры

Notepad++ &nbsp &nbspАрхив zip

1.3 Mb. &nbsp &nbsp Скачать &nbsp &nbsp &nbsp &nbsp &nbsp сайт

Notepad2 &nbsp &nbsp Архив zip

240 Kb. &nbsp &nbsp &nbsp Скачать &nbsp &nbsp &nbsp &nbsp &nbsp сайт &nbsp

Refal Studio (Refal 2)

Если Вы не используете в своей программе символ-метки, то можно попробовать работать с РЕФАЛом в этой интегрированной среде. Учтите, что программа находится в стадии тестирования, возможны ошибки.
Если Вы уверены, что Ваша программа должна работать, но такого не происходит при запуске из Refal Studio, попробуйте запустить ее на обычном Рефале-2. Если там программа заработает, то пришлите мне текущюю версию программы с описанием проблемы. Это поможет устранить ошибки. Спасибо!

13 MB. &nbsp Скачать &nbsp &nbsp (Установка не требуется, просто запустите exe файл)

тБУЫЙТЕООЩК ЖХОЛГЙПОБМШОЩК БОБМПЗ СЪЩЛБ тЕЖБМ ДМС НХМШФЙРБТБДЙЗНБМШОПЗП РТПЗТБННЙТПЧБОЙС

бООПФБГЙС:

сЪЩЛ тЕЖБМ ВЩМ РТЕДМПЦЕО ч.ж.фХТЮЙОЩН Ч 1966 ЗПДХ[8]. ч.ы.лБХЖНБО ПФНЕЮБЕФ УИПДУФЧП ЙЪПВТБЪЙФЕМШОЩИ УТЕДУФЧ тЕЖБМБ У ОПТНБМШОЩНЙ БМЗПТЙФНБНЙ нБТЛПЧБ[1]. рБТБДЙЗНХ СЪЩЛБ тЕЖБМ лБХЖНБО ОБЪЩЧБЕФ УЙФХБГЙПООЩН РТПЗТБННЙТПЧБОЙЕН , ЧЩДЕМСС ДЧЕ ЛМАЮЕЧЩЕ БВУФТБЛГЙЙ — БОБМЙЪ ЙУИПДОПК УФТХЛФХТЩ ДБООЩИ Й УЙОФЕЪ ТЕЪХМШФЙТХАЭЕК УФТХЛФХТЩ.

тЕЖБМ ЮТЕЪЧЩЮБКОП ХДПВЕО РТЙ ТЕЫЕОЙЙ ЪБДБЮ, УЧСЪБООЩИ У РТЕПВТБЪПЧБОЙСНЙ УЙНЧПМШОЩИ ДБООЩИ. ч.ж.фХТЮЙО ЙЪОБЮБМШОП РПЪЙГЙПОЙТПЧБМ тЕЖБМ ЛБЛ НЕФББМЗПТЙФНЙЮЕУЛЙК СЪЩЛ[9] Й РПЪДОЕЕ ЙУРПМШЪПЧБМ ЕЗП, Ч ЮЙУМЕ РТПЮЕЗП, ДМС ЙЪХЮЕОЙС ЬЛЧЙЧБМЕОФОЩИ РТЕПВТБЪПЧБОЙК РТПЗТБНН[10]. ч.й.уЕТДПВПМШУЛЙК ПФНЕФЙМ ХДПВУФЧП СЪЩЛБ ДМС ТБВПФЩ У БМЗЕВТБЙЮЕУЛЙНЙ ЖПТНХМБНЙ[3]. у УЕТЕДЙОЩ ЧПУШНЙДЕУСФЩИ ЗПДПЧ Й ДП ОБУФПСЭЕЗП ЧТЕНЕОЙ тЕЖБМ ХУРЕЫОП РТЙНЕОСЕФУС Ч ЙУУМЕДПЧБОЙСИ, УЧСЪБООЩИ У УХРЕТЛПНРЙМСГЙЕК Й ЮБУФЙЮОЩНЙ ЧЩЮЙУМЕОЙСНЙ[11].

л ОБУФПСЭЕНХ ЧТЕНЕОЙ УХЭЕУФЧХЕФ ОЕУЛПМШЛП ДЙБМЕЛФПЧ СЪЩЛБ тЕЖБМ, УТЕДЙ ЛПФПТЩИ ОБЙВПМЕЕ ДЙОБНЙЮОП ТБЪЧЙЧБАФУС тЕЖБМ-5[12] Й тЕЖБМ рМАУ. тБЪТБВПФБОЩ НЕФПДЩ ЬЖЖЕЛФЙЧОПК ТЕБМЙЪБГЙЙ СЪЩЛБ; УПЪДБОЩ УЙУФЕНЩ РТПЗТБННЙТПЧБОЙС ДМС ТБЪМЙЮОЩИ РТПЗТБННОП-БРРБТБФОЩИ РМБФЖПТН.

оЕУНПФТС ОБ ЬФП, тЕЖБМ ЛТБКОЕ ТЕДЛП РТЙНЕОСЕФУС Ч ЙОДХУФТЙБМШОПН РТПЗТБННЙТПЧБОЙЙ (РПД ЙОДХУФТЙБМШОЩН РТПЗТБННЙТПЧБОЙЕН НЩ РПОЙНБЕН РТЕЦДЕ ЧУЕЗП ЙЪЗПФПЧМЕОЙЕ РТПЗТБННОЩИ РТПДХЛФПЧ ДМС ЛПОЕЮОПЗП РПМШЪПЧБФЕМС, ОБИПДСЭЕЗПУС ЪБ РТЕДЕМБНЙ ЛПНРШАФЕТОПК ЙОДХУФТЙЙ). рТЙ ЬФПН тЕЖБМ ОЕМШЪС ОБЪЧБФШ ОЕЙЪЧЕУФОЩН СЪЩЛПН; НОПЗЙЕ РТПЖЕУУЙПОБМШОЩЕ РТПЗТБННЙУФЩ У ЬФЙН СЪЩЛПН ЪОБЛПНЩ. рП-ЧЙДЙНПНХ, ПУОПЧОПК РТЙЮЙОПК УМБВПК ЧПУФТЕВПЧБООПУФЙ СЪЩЛБ СЧМСЕФУС ФТХДОПУФШ ЕЗП ЙОФЕЗТБГЙЙ У ДТХЗЙНЙ СЪЩЛБНЙ (Ч ЮБУФОПУФЙ, У СЪЩЛБНЙ, РТЕДУФБЧМСАЭЙНЙ ОБЙВПМЕЕ РПРХМСТОЩК Ч УПЧТЕНЕООПК ЙОДХУФТЙЙ ЗЙВТЙД ЙНРЕТБФЙЧОПЗП Й ПВЯЕЛФОП-ПТЙЕОФЙТПЧБООПЗП РТПЗТБННЙТПЧБОЙС).

ч УФБФШЕ [5] НПЦОП ОБКФЙ ВПМЕЕ РПДТПВОПЕ ПВУХЦДЕОЙЕ РТПВМЕНЩ НЕЦШСЪЩЛПЧПК (НХМШФЙРБТБДЙЗНБМШОПК) ЙОФЕЗТБГЙЙ Й РТЕДЧБТЙФЕМШОПЕ УППВЭЕОЙЕ П НЕФПДЕ, ПУОПЧБООПН ОБ НПДЕМЙТПЧБОЙЙ БМШФЕТОБФЙЧОЩИ РБТБДЙЗН ЛБЛ РТЕДНЕФОЩИ ПВМБУФЕК УТЕДУФЧБНЙ ВБЪПЧПЗП ПВЯЕЛФОП-ПТЙЕОФЙТПЧБООПЗП СЪЩЛБ (ОБ РТЙНЕТЕ СЪЩЛПЧ уЙ++[7] Й мЙУР). дЕФБМШОПЕ ПРЙУБОЙЕ ЬЛУРЕТЙНЕОФБМШОПК ТЕБМЙЪБГЙЙ НЕФПДБ (ВЙВМЙПФЕЛЙ ЛМБУУПЧ уЙ++ InteLib, НПДЕМЙТХАЭЕК БМЗЕВТХ S-ЧЩТБЦЕОЙК СЪЩЛБ мЙУР) ДБЕФУС Ч ТБВПФЕ [6]. фБН ЦЕ РТЙЧПДСФУС УППВТБЦЕОЙС РП РПЧПДХ НПДЕМЙТПЧБОЙС УТЕДУФЧБНЙ СЪЩЛБ уЙ++ РБТБДЙЗНЩ СЪЩЛБ тЕЖБМ.

гЕМША ОБУФПСЭЕК УФБФШЙ СЧМСЕФУС ПРЙУБОЙЕ ТЕЪХМШФБФПЧ ЬЛУРЕТЙНЕОФБМШОПК ТЕБМЙЪБГЙЙ ПВЯЕЛФОП-ПТЙЕОФЙТПЧБООПК НПДЕМЙ РБТБДЙЗНЩ СЪЩЛБ тЕЖБМ.

вЙВМЙПФЕЛБ InteLib, РЕТЧПОБЮБМШОП ПТЙЕОФЙТПЧБООБС ОБ ЙНРПТФ Ч уЙ++-РТПЕЛФЩ РБТБДЙЗН СЪЩЛБ мЙУР, ПУОПЧБОБ ОБ НПДЕМЙТПЧБОЙЙ БМЗЕВТЩ S-ЧЩТБЦЕОЙК, РТЕДУФБЧМЕООПК Ч СЪЩЛЕ мЙУР, У РПНПЭША ЙЕТБТИЙЙ РПМЙНПТЖОЩИ ЛМБУУПЧ, ДМС ЛПФПТЩИ РЕТЕПРТЕДЕМСАФУС ОЕЛПФПТЩЕ УФБОДБТФОЩЕ ПРЕТБГЙЙ уЙ++ ФБЛЙН ПВТБЪПН, ЮФПВЩ ПВЕУРЕЮЙФШ ХДПВОПЕ ДМС РТПЗТБННЙУФБ ПФПВТБЦЕОЙЕ РТЙЧЩЮОЩИ мЙУР-ЛПОУФТХЛГЙК ОБ УЙОФБЛУЙУ, ДПРХУФЙНЩК Ч уЙ++-ЛПДЕ.

чУЕ S-ЧЩТБЦЕОЙС РТЕДУФБЧМСАФУС Ч InteLib ПВЯЕЛФБНЙ ОЕЛПФПТЩИ ЛМБУУПЧ, СЧМСАЭЙИУС РПФПНЛБНЙ ПВЭЕЗП ВБЪПЧПЗП ЛМБУУБ LTerm (ЬФП ЙНС ЧПЪОЙЛМП ОБ ТБООЕК УФБДЙЙ РТПЕЛФЙТПЧБОЙС ВЙВМЙПФЕЛЙ Й УПИТБОЕОП Ч УЙМХ ЙУФПТЙЮЕУЛЙИ РТЙЮЙО). фБЛ, S-ЧЩТБЦЕОЙЕ ФЙРБ » РТЕДУФБЧМСЕФУС ПВЯЕЛФПН ЛМБУУБ LTermString, МЙУРПЧУЛЙК УЙНЧПМ (Ч ФЕТНЙОПМПЗЙЙ, ФТБДЙГЙПООПК ДМС УФБОДБТФБ Common Lisp[4]) ЙМЙ ЙДЕОФЙЖЙЛБФПТ (Ч ФЕТНЙОБИ, РТЙОСФЩИ Ч СЪЩЛЕ Scheme[2]) НПДЕМЙТХЕФУС ПВЯЕЛФПН ЛМБУУБ LTermSymbol, ФПЮЕЮОБС РБТБ — ПВЯЕЛФПН ЛМБУУБ LDotPair Й Ф.Р. дМС ДПУФХРБ Л ПВЯЕЛФБН ЙЕТБТИЙЙ LTerm, УХЭЕУФЧХАЭЙН ЧУЕЗДБ Ч ДЙОБНЙЮЕУЛПК РБНСФЙ, ЙУРПМШЪХАФУС ПВЯЕЛФЩ ЛМБУУБ LReference. лМБУУ LReference РП УЧПЙН УЧПКУФЧБН БОБМПЗЙЮЕО РТПУФПНХ ХЛБЪБФЕМА, Ч ДПРПМОЕОЙЕ Л ЮЕНХ ЙУРПМОСЕФ ЖХОЛГЙЙ УВПТЭЙЛБ НХУПТБ.

дМС РПУФТПЕОЙС МЙУРПЧУЛЙИ УРЙУЛПЧ, УПУФПСЭЙИ ЙЪ ФПЮЕЮОЩИ РБТ, ЙУРПМШЪХАФУС ДЧЕ ВБЪПЧЩЕ ПРЕТБГЙЙ — УПЪДБОЙЕ УРЙУЛБ ЙЪ ПДОПЗП (РЕТЧПЗП) ЬМЕНЕОФБ Й ДПВБЧМЕОЙЕ ОПЧПЗП ЬМЕНЕОФБ Ч ЛПОЕГ. дМС ЧЧЕДЕОЙС РЕТЧПК ПРЕТБГЙЙ ЙУРПМШЪХЕФУС ЛМБУУ LListConstructor У РЕТЕЛТЩФПК ПРЕТБГЙЕК | ; Ч ЛБЮЕУФЧЕ УЙНЧПМБ ДМС ПВПЪОБЮЕОЙС ЧФПТПК ПРЕТБГЙЙ ЙЪ УППВТБЦЕОЙК ОБЗМСДОПУФЙ ЧЩВТБОБ ДЧХИНЕУФОБС ПРЕТБГЙС » , РЕТЕПРТЕДЕМЕООБС Ч ЛМБУУЕ LReference. лМБУУ LReference ЙНЕЕФ ЛПОУФТХЛФПТЩ РТЕПВТБЪПЧБОЙС ДМС ЧУЕИ УФБОДБТФОЩИ ЧУФТПЕООЩИ ФЙРПЧ СЪЩЛБ уЙ++, ЮФП, Ч УПЮЕФБОЙЙ У НЕИБОЙЪНПН ОЕСЧОЩИ РТЕПВТБЪПЧБОЙК, ДБЕФ ЧПЪНПЦОПУФШ ЙУРПМШЪПЧБОЙС, ОБРТЙНЕТ, УМЕДХАЭЙИ ЛПОУФТХЛГЙК: дМС ХДПВУФЧБ РПУФТПЕОЙС ФПЮЕЮОЩИ РБТ Й ФПЮЕЮОЩИ УРЙУЛПЧ РТЙНЕОСЕФУС ПРЕТБГЙС || , ЪБНЕОСАЭБС НЕФЛХ ЛПОГБ УРЙУЛБ (УЙНЧПМ NIL) Ч МЕЧПН ПРЕТБОДЕ ОБ РТБЧЩК ПРЕТБОД. ч ТПМЙ МЙУРПЧУЛПЗП УПЛТБЭЕОЙС ДМС ЖПТНЩ (QUOTE A) (БРПУФТПЖ) ЙУРПМШЪХЕФУС ПРЕТБГЙС

(ФЙМШДБ). рТЙЧЕДЕН ЕЭЕ ОЕУЛПМШЛП РТЙНЕТПЧ: оЕПВИПДЙНП РПСУОЙФШ, ЮФП L — ЬФП ЙНС ПВЯЕЛФБ ЛМБУУБ LListConstructor, MEMBER — ЬФП ЙНС ПВЯЕЛФБ LReference, УУЩМБАЭЕЗПУС ОБ ПВЯЕЛФ ЛМБУУБ LTermSymbol, Й Ф.Д.

оБЛПОЕГ, ДМС РТСНПЗП РПУФТПЕОЙС ФПЮЕЮОПК РБТЩ ЙЪ МЕЧПЗП Й РТБЧПЗП ЪОБЮЕОЙС ЙУРПМШЪХЕФУС ПРЕТБГЙС ^ .

лМБУУ LTerm ЙНЕЕФ ЧЙТФХБМШОХА ЖХОЛГЙА Evaluate(), РТПЙЪЧПДСЭХА ЧЩЮЙУМЕОЙЕ УППФЧЕФУФЧХАЭЕЗП ЧЩТБЦЕОЙС Ч УНЩУМЕ мЙУРБ. дМС ЛПОУФБОФ (ЮЙУМПЧЩИ, УФТПЛПЧЩИ Й ЛПОУФБОФОЩИ УЙНЧПМПЧ) НЕФПД Evaluate ЧПЪЧТБЭБЕФ УУЩМЛХ ОБ ЙУИПДОПЕ ЧЩТБЦЕОЙЕ. дМС ЛМБУУПЧ, ОБУМЕДХЕНЩИ ПФ LTerm Й НПДЕМЙТХАЭЙИ ДТХЗЙЕ (ОЕЛПОУФБОФОЩЕ) ФЙРЩ S-ЧЩТБЦЕОЙК, ЖХОЛГЙС Evaluate() УППФЧЕФУФЧХАЭЙН ПВТБЪПН РЕТЕЛТЩЧБЕФУС.

тБУУНПФТЙН ДМС РТЙНЕТБ ЖХОЛГЙА ОБ СЪЩЛЕ мЙУР, ПРТЕДЕМСАЭХА, ЙНЕАФ МЙ ДЧБ ДЕТЕЧБ ЙЪПНПТЖОХА УФТХЛФХТХ (ДЧБ ДЕТЕЧБ УЮЙФБАФУС ЙЪПНПТЖОЩНЙ ФПЗДБ Й ФПМШЛП ФПЗДБ, ЛПЗДБ ПОЙ ПФМЙЮБАФУС ФПМШЛП ЪОБЮЕОЙСНЙ Ч МЙУФШСИ): еУМЙ УЮЙФБФШ, ЮФП УЙНЧПМЩ, УППФЧЕФУФЧХАЭЙЕ УФБОДБТФОЩН ЖХОЛГЙСН мЙУРБ, ХЦЕ ПРЙУБОЩ УППФЧЕФУФЧХАЭЙНЙ ПВЯЕЛФБНЙ ЛМБУУБ LSymbol, ФП НПЦОП ЪБРЙУБФШ ОБ уЙ++ ЛПД, ЬЛЧЙЧБМЕОФОЩК ЧЩЫЕРТЙЧЕДЕООПНХ: уМЕДХЕФ ПУПВП ПФНЕФЙФШ, ЮФП ДБООЩК ЖТБЗНЕОФ ЛПДБ СЧМСЕФУС ЛПДПН ОБ СЪЩЛЕ C++, ОЕ ФТЕВХАЭЙН ЛБЛПЗП-МЙВП ДПРПМОЙФЕМШОПЗП РТЕРТПГЕУУЙТПЧБОЙС. фБЛЙН ПВТБЪПН, ОЕ ЧЩИПДС ЪБ РТЕДЕМЩ СЪЩЛБ C++, НЩ РПМХЮБЕН ЧПЪНПЦОПУФШ РТЙНЕОЕОЙС РБТБДЙЗН СЪЩЛБ Lisp Ч C++-РТПЕЛФЕ.

дТЕЧПЧЙДОЩЕ ДБООЩЕ, УПУФПСЭЙЕ ЙЪ УФТПЛ ФЕТНЙОБМШОЩИ УЙНЧПМПЧ, УЙНЧПМПЧ-НЕФПЛ, УЙНЧПМПЧ-ЮЙУЕМ Й УФТХЛФХТОЩИ УЛПВПЛ (ФП ЕУФШ ЧЩТБЦЕОЙС, ДПРХУФЙНЩЕ ОБ ЧИПДЕ Ч ТЕЖБМ-ЖХОЛГЙА), ПЮЕЧЙДОЩН ПВТБЪПН ЙЪПНПТЖОЩ МЙУРПЧУЛЙН ДЕТЕЧШСН, УПУФПСЭЙН ЙЪ УФТПЛПЧЩИ ЛПОУФБОФ, УЙНЧПМПЧ Й ЮЙУЕМ. оБРТЙНЕТ, ТЕЖБМШУЛПЕ ЧЩТБЦЕОЙЕ УППФЧЕФУФЧХЕФ Ч УНЩУМЕ ТБУУНБФТЙЧБЕНПЗП ЙЪПНПТЖЙЪНБ МЙУРПЧУЛПНХ оЕПВИПДЙНП ПФНЕФЙФШ, ЮФП ЙЪПНПТЖЙЪН СЧМСЕФУС ДПУФБФПЮОП ХУМПЧОЩН. оБ УБНПН ДЕМЕ, ТЕЖБМШУЛЙЕ ПВЯЕЛФОЩЕ ЧЩТБЦЕОЙС ЙЪПНПТЖОЩ РПДНОПЦЕУФЧХ МЙУРПЧУЛЙИ S-ЧЩТБЦЕОЙК, Б ЙНЕООП — НОПЦЕУФЧХ УРЙУЛПЧ, Ч ЛПФПТЩИ ОЙЗДЕ ОЕ ЧУФТЕЮБЕФУС ДЧХИ УЙНЧПМШОЩИ УФТПЛ РПДТСД. ч ТЕБМЙЪПЧБООПК ЧЕТУЙЙ ВЙВМЙПФЕЛЙ БФПНБТОЩЕ S-ЧЩТБЦЕОЙС Й ФПЮЕЮОЩЕ УРЙУЛЙ УЮЙФБАФУС ОЕ УППФЧЕФУФЧХАЭЙНЙ ОЙЛБЛЙН ЧЩТБЦЕОЙСН СЪЩЛБ тЕЖБМ Й РТЙ РПРЩФЛЕ ЙУРПМШЪПЧБОЙС Ч ЛБЮЕУФЧЕ ФБЛПЧЩИ ЧЩЪЩЧБАФ ПЫЙВЛХ. юФП ЛБУБЕФУС УРЙУЛПЧ У ДЧХНС Й ВПМЕЕ УФТПЛПЧЩНЙ ЛПОУФБОФБНЙ РПДТСД, ФП ФБЛЙЕ УРЙУЛЙ УЮЙФБАФУС ЬЛЧЙЧБМЕОФОЩНЙ УРЙУЛБН, Ч ЛПФПТЩИ УМЕДХАЭЙЕ РПДТСД ЛПОУФБОФЩ ЪБНЕОЕОЩ ОБ ЙИ ЛПОЛБФЕОБГЙА.

тБУУНПФТЕООЩК ЙЪПНПТЖЙЪН РПЪЧПМСЕФ ЙУРПМШЪПЧБФШ ДМС РТЕДУФБЧМЕОЙС ТЕЖБМШУЛЙИ ЧЩТБЦЕОЙК ХЦЕ УХЭЕУФЧХАЭЙЕ УТЕДУФЧБ, ТБЪТБВПФБООЩЕ ДМС мЙУРБ. рТЙЧЕДЕООПЕ ЧЩЫЕ ЧЩТБЦЕОЙЕ НПЦОП РТЕДУФБЧЙФШ ОБ уЙ++ ЛБЛ

дМС РТЕДУФБЧМЕОЙС ТЕЖБМШУЛЙИ ХЗМПЧЩИ УЛПВПЛ, ПВПЪОБЮБАЭЙИ ЧЩЪПЧЩ ЖХОЛГЙК (ФБЛ ОБЪЩЧБЕНЩЕ » ), ЧЧЕДЕН ОПЧЩК ЛМБУУ RfCall, ОБУМЕДХЕНЩК ПФ LTerm Й ЙОЛБРУХМЙТХАЭЙК ПВЩЮОЩК УРЙУПЛ. дМС РПУФТПЕОЙС ФБЛЙИ БЛФЙЧОЩИ УРЙУЛПЧ ЧЧЕДЕН ЛМБУУ, БОБМПЗЙЮОЩК ПРЙУБООПНХ ТБОЕЕ LListConstructor. оБЪПЧЕН ЕЗП, ОБРТЙНЕТ, RfListConstructor Й ПРЙЫЕН ЕЗП ЕДЙОУФЧЕООЩК ЬЛЪЕНРМСТ У ЙНЕОЕН R. фБЛЦЕ ЧЧЕДЕН ХОБУМЕДПЧБООЩК ПФ LReference ЛМБУУ RfCallReference, РТЕДОБЪОБЮЕООЩК ДМС ТБВПФЩ У БЛФЙЧОЩНЙ УРЙУЛБНЙ. пУОПЧОПЕ ПФМЙЮЙЕ RfCallReference ПФ LReference УПУФПЙФ Ч ЙЪНЕОЕООПК УЕНБОФЙЛЕ ПРЕТБГЙЙ » , ЛПФПТБС Ч ДБООПН УМХЮБЕ РТЕДРПМБЗБЕФ, ЮФП МЕЧЩН ПРЕТБОДПН СЧМСЕФУС ОЕ УРЙУПЮОПЕ S-ЧЩТБЦЕОЙЕ, Б ЧЩТБЦЕОЙЕ ФЙРБ RfCall. уППФЧЕФУФЧЕООП, ДПВБЧМЕОЙЕ ОПЧПЗП ЬМЕНЕОФБ РТПЙЪЧПДЙФУС Л ЙОЛБРУХМЙТПЧБООПНХ Ч ОЕЗП УРЙУЛХ.

фЕРЕТШ ТЕЖБМШУЛПЕ НПЦЕФ ВЩФШ РТЕДУФБЧМЕОП Ч ЧЙДЕ (R|FUN1,»a»,SYM1,»b») .

дМС РТЕДУФБЧМЕОЙС ТЕЖБМШУЛЙИ РЕТЕНЕООЩИ ПРЙЫЕН УРЕГЙБМШОЩК ЛМБУУ RfVariable, ФБЛЦЕ ОБУМЕДХЕНЩК ПФ LTerm. уФТПЗП ЗПЧПТС, ОЙЛБЛЙНЙ УЧПКУФЧБНЙ ФЕТНБ ТЕЖБМ-РЕТЕНЕООБС ОЕ ПВМБДБЕФ, Й ФБЛПЕ ОБУМЕДПЧБОЙЕ РТЕУМЕДХЕФ ЕДЙОУФЧЕООХА ГЕМШ — РПЪЧПМЙФШ ЙУРПМШЪПЧБФШ ДМС РПУФТПЕОЙС РТБЧЙМ РТЕПВТБЪПЧБОЙС ХЦЕ УХЭЕУФЧХАЭЙЕ УТЕДУФЧБ.

лМБУУ RfVariable ЙНЕЕФ НЕФПДЩ, ЙУРПМШЪХЕНЩЕ Ч РТПГЕУУЕ УПРПУФБЧМЕОЙС ЧЩТБЦЕОЙК У ПВТБЪГБНЙ. уБН ЛМБУУ RfVariable СЧМСЕФУС БВУФТБЛФОЩН, Б РЕТЕНЕООЩЕ ЛПОЛТЕФОЩИ ФЙРПЧ ПРЙУЩЧБАФУС У РПНПЭША ОБУМЕДХЕНЩИ ПФ ОЕЗП РПДЛМБУУПЧ.

рХФЕН ЧЧЕДЕОЙС ДПРПМОЙФЕМШОЩИ ЛМБУУПЧ — ОБУМЕДОЙЛПЧ LReference Й РЕТЕЛТЩФЙС ДМС ЬФЙИ ЛМБУУПЧ ПРЕТБГЙК () (ЫФБФОП ПВПЪОБЮБЕФ ЧЩЪПЧ ЖХОЛГЙЙ) Й [] (ЫФБФОП ЙУРПМШЪХЕФУС ДМС БДТЕУБГЙЙ Ч НБУУЙЧЕ) НПЦОП ДБФШ ДПУФБФПЮОП ОБЗМСДОЩЕ УТЕДУФЧБ ДМС ПРЙУБОЙС ТЕЖБМ-ЖХОЛГЙК. оБРТЙНЕТ, ЖХОЛГЙС » , ЙНЕАЭБС ОБ тЕЖБМЕ-5 ЧЙД НПЦЕФ ВЩФШ РТЕДУФБЧМЕОБ ОБ уЙ++ ЛБЛ

уФТБФЕЗЙС ЧЩЮЙУМЕОЙС ТЕЖБМ-ЧЩТБЦЕОЙК УХЭЕУФЧЕООП ПФМЙЮБЕФУС ПФ УФТБФЕЗЙЙ ЧЩЮЙУМЕОЙС S-ЧЩТБЦЕОЙК Ч УНЩУМЕ мЙУРБ. оБРТЙНЕТ, ТЕЪХМШФБФПН ЧЩЮЙУМЕОЙС РТПУФПЗП УРЙУЛБ Ч УНЩУМЕ мЙУРБ ВХДЕФ РТЙНЕОЕОЙЕ ЖХОЛГЙЙ, ЪБДБООПК РЕТЧЩН ЬМЕНЕОФПН УРЙУЛБ, Л ПУФБФЛХ УРЙУЛБ ЛБЛ Л УРЙУЛХ ЖБЛФЙЮЕУЛЙИ РБТБНЕФТПЧ (ПВЩЮОП РПДМЕЦБЭЙИ, Ч УЧПА ПЮЕТЕДШ, ЧЩЮЙУМЕОЙА РЕТЕД РЕТЕДБЮЕК Ч ЖХОЛГЙА), ФПЗДБ ЛБЛ ТЕЪХМШФБФПН ЧЩЮЙУМЕОЙС ФПЗП ЦЕ УРЙУЛБ Ч УНЩУМЕ тЕЖБМБ ВХДЕФ РТПУФБС ЛПОЛБФЕОБГЙС ТЕЪХМШФБФПЧ ЧЩЮЙУМЕОЙС ЧУЕИ ЬМЕНЕОФПЧ УРЙУЛБ (ПРСФШ ФБЛЙ, Ч УНЩУМЕ тЕЖБМБ). рПЬФПНХ ДМС ЧЩЮЙУМЕОЙС S-ЧЩТБЦЕОЙК Ч УНЩУМЕ тЕЖБМБ РТЙНЕОСЕФУС ОЕ НЕФПД Evaluate(), ЧЧЕДЕООЩК Ч ЛМБУУЕ LTerm, Б ЧОЕЫОСС РП ПФОПЫЕОЙА Л ЙЕТБТИЙЙ LTerm ЖХОЛГЙС, ОБЪЧБООБС RefalMachineCall.

лТПНЕ ФПЗП, РПМШЪПЧБФЕМА ДПУФХРОЩ ЖХОЛГЙЙ RefalMatch (РТПУФПЕ ТЕЖБМШУЛПЕ УПРПУФБЧМЕОЙЕ У ПВТБЪГПН), RefalReplaceVars (РПДУФБОПЧЛБ ЪОБЮЕОЙК ЧНЕУФП РЕТЕНЕООЩИ Ч ЧЩТБЦЕОЙЙ) Й RefalSimplifyView (ОПТНБМЙЪБГЙС ТЕЖБМ-ЧЩТБЦЕОЙС). рПД ОПТНБМЙЪБГЙЕК РПОЙНБЕФУС ЪБНЕОБ УФТПЛПЧЩИ ЛПОУФБОФ, ЙДХЭЙИ Ч УРЙУЛЕ РПДТСД, ОБ ЙИ ЛПОЛБФЕОБГЙА, ФБЛ ЮФП Ч ТЕЪХМШФЙТХАЭЕН ЧЩТБЦЕОЙЙ ОЙЗДЕ ОЕ ЧУФТЕЮБЕФУС РПДТСД ДЧХИ УФТПЛПЧЩИ ЛПОУФБОФ. ч УЙФХБГЙЙ НХМШФЙРБТБДЙЗНБМШОПЗП РТПЗТБННЙТПЧБОЙС, Ф.Е. Ч ХУМПЧЙСИ, Ч ЛПФПТЩИ ТЕЖБМ-ЛПОУФТХЛГЙЙ СЧМСАФУС ПДОЙН ЙЪ ЧПЪНПЦОЩИ, ОП ОЕ ЕДЙОУФЧЕООЩН УРПУПВПН ПВТБВПФЛЙ ДБООЩИ, РТЙНЕОЕОЙЕ ФБЛЙИ ЖХОЛГЙК, ТЕБМЙЪХАЭЙИ ЮБУФОЩЕ ЧПЪНПЦОПУФЙ ТЕЖБМ-НБЫЙОЩ, ЪБЮБУФХА ВЩЧБЕФ ПЮЕОШ ХДПВОП.

рПД РЕТЕНЕООПК Ч тЕЖБМЕ РПОЙНБЕФУС УРЕГЙЖЙЮЕУЛБС БФПНБТОБС УПУФБЧМСАЭБС ЧЩТБЦЕОЙС-ПВТБЪГБ, ЛПФПТПК НПЦЕФ УФБЧЙФШУС Ч УППФЧЕФУФЧЙЕ МАВПЕ ТЕЖБМ-ЧЩТБЦЕОЙЕ ЙЪ ОЕЛПФПТПЗП НОПЦЕУФЧБ.

ч тЕЖБМЕ-5 УХЭЕУФЧХАФ РЕТЕНЕООЩЕ ФТЕИ ФЙРПЧ (S-РЕТЕНЕООЩЕ, T-РЕТЕНЕООЩЕ Й E-РЕТЕНЕООЩЕ). S-РЕТЕНЕООПК НПЦЕФ ВЩФШ РПУФБЧМЕО Ч УППФЧЕФУФЧЙЕ МАВПК УЙНЧПМ (Ч ФПН ЮЙУМЕ УЙНЧПМ-НЕФЛБ ЙМЙ УЙНЧПМ-ЮЙУМП). еУМЙ ЧПУРПМШЪПЧБФШУС ЧЧЕДЕООЩН ЧЩЫЕ ЙЪПНПТЖЙЪНПН, НПЦОП ЗПЧПТЙФШ, ЮФП S-РЕТЕНЕООБС УФБЧЙФУС Ч УППФЧЕФУФЧЙЕ УЙНЧПМХ ЧОХФТЙ УФТПЛПЧПК ЛПОУФБОФЩ, МЙУР-УЙНЧПМХ ЙМЙ ЮЙУМПЧПК ЛПОУФБОФЕ. T-РЕТЕНЕООПК НПЦЕФ ВЩФШ РПУФБЧМЕОП Ч УППФЧЕФУФЧЙЕ, ЛТПНЕ ЧЩЫЕРЕТЕЮЙУМЕООПЗП, МАВПЕ ЧЩТБЦЕОЙЕ, ЪБЛМАЮЕООПЕ Ч УЛПВЛЙ. оБЛПОЕГ, E-РЕТЕНЕООБС НПЦЕФ УППФЧЕФУФЧПЧБФШ МАВПНХ ЧЩТБЦЕОЙА, Ч ЛПФПТПН УПВМАДЕО ВБМБОУ УЛПВПЛ, Ч ФПН ЮЙУМЕ РХУФПНХ. оЕУМПЦОП ЧЙДЕФШ, ЮФП РТЙ ЧЩРПМОЕОЙЙ ПРЕТБГЙЙ УПРПУФБЧМЕОЙС ЧЩТБЦЕОЙС У ПВТБЪГПН (ОБРТЙНЕТ, УМЕЧБ ОБРТБЧП, ЛБЛ ЬФП ДЕМБЕФУС Ч тЕЖБМЕ-5), ДМС ЧУФТЕЮЕООЩИ ОБ ПЮЕТЕДОПН ЫБЗЕ S- Й T-РЕТЕНЕООЩИ НПЦОП УТБЪХ ПРТЕДЕМЙФШ, ЧПЪНПЦОП МЙ УПРПУФБЧМЕОЙЕ ЧППВЭЕ Й ЕУМЙ ДБ, ФП ЛБЛПЕ ЙНЕООП ЧЩТБЦЕОЙЕ ДПМЦОП ВЩФШ УПРПУФБЧМЕОП ДБООПК РЕТЕНЕООПК. еУМЙ ЦЕ Ч ЧЩТБЦЕОЙЙ ЧУФТЕЮБЕФУС РЕТЕНЕООБС ФЙРБ E, Ч ПВЭЕН УМХЮБЕ ОЕПВИПДЙНП РПУМЕДПЧБФЕМШОП ТБУУНПФТЕФШ ТБЪОЩЕ ЧБТЙБОФЩ УПРПУФБЧМЕОЙС, ДМС ЮЕЗП НПЦЕФ РПОБДПВЙФШУС БМЗПТЙФН РПЙУЛБ ТЕЫЕОЙС У ЧПЪЧТБФБНЙ (backtracking).

ч ВПМЕЕ ТБООЙИ ЧЕТУЙСИ тЕЖБМБ НПЦОП ВЩМП ХЛБЪБФШ ПЗТБОЙЮЕОЙС ОБ ЧЩТБЦЕОЙС, ЛПФПТЩЕ НПЗХФ ВЩФШ УПРПУФБЧМЕОЩ ДБООПК РЕТЕНЕООПК (Ч ДБООПН ПВТБЪГЕ). фБЛ, ПВТБЪГХ ‘ab’ s(‘cd’)1 ‘ef’ НПЗМЙ УФБЧЙФШУС Ч УППФЧЕФУФЧЙЕ ФПМШЛП ДЧЕ УФТПЛЙ — ‘abcef’ Й ‘abdef’ . ч УПЧТЕНЕООЩЕ ЧЕТУЙЙ тЕЖБМБ ЬФЙ ЧПЪНПЦОПУФЙ ОЕ ЧПЫМЙ, ЧЙДЙНП, ЙЪ УППВТБЦЕОЙК ЬМЕЗБОФОПУФЙ СЪЩЛБ. дПРПМОЙФЕМШОЩЕ ХУМПЧЙС ОБ ЪОБЮЕОЙС РЕТЕНЕООЩИ Ч тЕЖБМЕ-5 НПЗХФ ВЩФШ ЪБДБОЩ У РПНПЭША ФБЛ ОБЪЩЧБЕНЩИ » ЗДЕ -РТЕДМПЦЕОЙК»> ( where clauses), ЮФП РП УЧПЙН ЧПЪНПЦОПУФСН РТЕЧПУИПДЙФ НЕИБОЙЪН УРЕГЙЖЙЛБФПТПЧ ТБООЙИ ЧЕТУЙК тЕЖБМБ, Ф.Л. РПЪЧПМСЕФ ОБЛМБДЩЧБФШ ОБ РЕТЕНЕООЩЕ УПЧЕТЫЕООП РТПЙЪЧПМШОЩЕ ПЗТБОЙЮЕОЙС. лБЛПЧП ВЩ ОЙ ВЩМП ПЗТБОЙЮЕОЙЕ ОБ РЕТЕНЕООЩЕ v.1, v.2, . v.n , ЧУЕЗДБ ЧПЪНПЦОП ПРЙУБФШ ОБ тЕЖБМЕ ИБТБЛФЕТЙУФЙЮЕУЛХА ЖХОЛГЙА-РТЕДЙЛБФ ЧЙДБ , ЛПФПТБС ЧПЪЧТБЭБМБ ВЩ, ОБРТЙНЕТ, ЪОБЮЕОЙЕ true ДМС ДПРХУФЙНПК ЛПНВЙОБГЙЙ ЪОБЮЕОЙК РЕТЕНЕООЩИ Й false Ч РТПФЙЧОПН УМХЮБЕ. фПЗДБ ЛПОУФТХЛГЙС ФЙРБ where ЧЙДБ , : true ЧЧЕДЕФ Ч ТЕЖБМ-РТЕДМПЦЕОЙЕ ФТЕВХЕНПЕ ПЗТБОЙЮЕОЙЕ. хОЙЧЕТУБМШОПУФШ НЕИБОЙЪНБ УМЕДХЕФ ЙЪ БМЗПТЙФНЙЮЕУЛПК РПМОПФЩ СЪЩЛБ тЕЖБМ.

дМС РТПЗТБНН, УПУФБЧМСЕНЩИ ГЕМЙЛПН ОБ тЕЖБМЕ, ФБЛПК НЕИБОЙЪН, ВЕЪХУМПЧОП, РТЕДРПЮФЙФЕМШОЕЕ. пДОБЛП Ч УЙФХБГЙЙ, ЛПЗДБ ПУОПЧОЩН СЪЩЛПН РТПЕЛФБ СЧМСЕФУС уЙ++ ЙМЙ ДТХЗПК ПВЯЕЛФОП-ПТЙЕОФЙТПЧБООЩК СЪЩЛ, Б ПФ тЕЖБМБ ЙУРПМШЪХАФУС ФПМШЛП ЙЪПВТБЪЙФЕМШОЩЕ РБТБДЙЗНЩ, ЧПЪНПЦОПУФШ ЧЧЕДЕОЙС ДПРПМОЙФЕМШОЩИ ФЙРПЧ ТЕЖБМ-РЕТЕНЕООЩИ НПЦЕФ РПЧЩУЙФШ ОБЗМСДОПУФШ, Б Ч ОЕЛПФПТЩИ УМХЮБСИ — Й ЬЖЖЕЛФЙЧОПУФШ УПУФБЧМСЕНЩИ РТПЗТБНН.

ч УЧСЪЙ У ЬФЙН ВЙВМЙПФЕЛБ InteLib ДЕМБЕФ НЙОЙНБМШОП ЧПЪНПЦОПЕ ЛПМЙЮЕУФЧП РТЕДРПМПЦЕОЙК ПФОПУЙФЕМШОП ЧЩТБЦЕОЙК, ЛПФПТЩЕ НПЗХФ ВЩФШ УПРПУФБЧМЕОЩ ТЕЖБМ-РЕТЕНЕООПК. рЕТЕНЕООЩЕ ДЕМСФУС ОБ ДЧЕ ЛБФЕЗПТЙЙ — ПДОПЪОБЮОЩЕ Й НОПЗПЪОБЮОЩЕ. ч ВБЪПЧПК ВЙВМЙПФЕЛЕ Л РЕТЧПК ЛБФЕЗПТЙЙ ПФОПУСФУС S- Й T-РЕТЕНЕООЩЕ, ЛП ЧФПТПК — E-РЕТЕНЕООЩЕ. пВТБВПФЛБ РЕТЕНЕООЩИ ЧФПТПК ЛБФЕЗПТЙЙ ПФМЙЮБЕФУС ФЕН, ЮФП Ч УЙФХБГЙЙ, ЛПЗДБ ФБЛБС РЕТЕНЕООБС ЧУФТЕЮБЕФУС Ч ПФЛТЩФПК РПЪЙГЙЙ (ФП ЕУФШ ЪБ ОЕК ОЕ УМЕДХЕФ ОЕРПУТЕДУФЧЕООП ЛПОЕГ ЧЩТБЦЕОЙС ЙМЙ ЪБЛТЩЧБАЭБС УЛПВЛБ), РТПГЕДХТБ УПРПУФБЧМЕОЙС ПТЗБОЙЪХЕФ РЕТЕВПТ ЧБТЙБОФПЧ. лПМЙЮЕУФЧП ЧПЪНПЦОЩИ ЧБТЙБОФПЧ, ЛБЛ Й УБНЙ ЬФЙ ЧБТЙБОФЩ, РПМОПУФША ПРТЕДЕМСЕФУС ЧЙТФХБМШОЩНЙ ЖХОЛГЙСНЙ ЛМБУУБ RfVariable_E (РПФПНЛБ ЛМБУУБ RfVariable, РТЕДУФБЧМСАЭЕЗП E-РЕТЕНЕООЩЕ).

фБЛЙН ПВТБЪПН, РТЙ ОЕПВИПДЙНПУФЙ НПЦОП ПРЙУБФШ ДПРПМОЙФЕМШОЩЕ ЛМБУУЩ ТЕЖБМ-РЕТЕНЕООЩИ. оБРТЙНЕТ, НПЦОП ЧЧЕУФЙ РЕТЕНЕООЩЕ, Ч УППФЧЕФУФЧЙЕ ЛПФПТЩН УФБЧЙФУС МАВБС ГЕРПЮЛБ УЙНЧПМПЧ, ДПРХУФЙНБС Ч ЛБЮЕУФЧЕ ЙНЕОЙ ЙДЕОФЙЖЙЛБФПТБ (Ч ЧЙДЕ НОПЗПЪОБЮОПК ТЕЖБМ-РЕТЕНЕООПК). вПМЕЕ ФПЗП, Ч УМХЮБЕ, ЕУМЙ Ч БОБМЙЪЙТХЕНПН СЪЩЛЕ ЙНЕЕФУС ФТЕВПЧБОЙЕ, ЮФП Ч ЛБЮЕУФЧЕ ЙНЕОЙ ЙДЕОФЙЖЙЛБФПТБ ЧУЕЗДБ ВЕТЕФУС УБНБС ДМЙООБС ЙЪ ДПРХУФЙНЩИ ГЕРПЮЕЛ (Ч ВПМШЫЙОУФЧЕ УПЧТЕНЕООЩИ СЪЩЛПЧ РТПЗТБННЙТПЧБОЙС ЬФП ФБЛ Й ЕУФШ), ФП ЗТБННБФЙЮЕУЛПЕ РПОСФЙЕ » НПЦЕФ ВЩФШ ПРЙУБОП Ч ЧЙДЕ ПДОПЪОБЮОПК РЕТЕНЕООПК (ФП ЕУФШ РЕТЕНЕООПК, ОЕ ДПРХУЛБАЭЕК ЧБТЙБОФОПЗП УПРПУФБЧМЕОЙС), ЮФП, ВЕЪХУМПЧОП, РПЧЩУЙФ ЬЖЖЕЛФЙЧОПУФШ РТПЗТБННЩ Й ХРТПУФЙФ ТЕБМЙЪБГЙА МЕЛУЙЮЕУЛПЗП БОБМЙЪБ.

ч ПРЙУБОЙЙ тЕЖБМБ-5 [12] РПД » СЪЩЛБ РПОЙНБАФУС ХЦЕ ХРПНЙОБЧЫБСУС where-ЛПОУФТХЛГЙС, ЙМЙ ХУМПЧЙЕ , Б ФБЛЦЕ with-ЛПОУФТХЛГЙС, ЙМЙ ВМПЛ .

рТЙ ЙОФЕТРТЕФБГЙЙ where-ЛПОУФТХЛГЙЙ РТПЙЪЧПДЙФУС ЧЩЮЙУМЕОЙЕ ОЕЛПФПТПЗП ТЕЖБМ-ЧЩТБЦЕОЙС Й РПРЩФЛБ УПРПУФБЧМЕОЙС ТЕЪХМШФБФБ У ЪБДБООЩН ПВТБЪГПН, ЛПФПТБС НПЦЕФ ПЛПОЮЙФУС ХУРЕИПН ЙМЙ ОЕХДБЮЕК. чПЪНПЦОП, ЮФП ОЕЛПФПТЩЕ ОЕ УЧСЪБООЩЕ ДП ЧЩРПМОЕОЙС ЛПОУФТХЛГЙЙ РЕТЕНЕООЩЕ РПМХЮБФ ЪОБЮЕОЙС Ч РТПГЕУУЕ ЕЕ ЧЩРПМОЕОЙС. ч УМХЮБЕ ХУРЕИБ РТПЙЪЧПДЙУС ПВЩЮОБС РПДУФБОПЧЛБ РЕТЕНЕООЩИ Ч РТБЧПК ЮБУФЙ РТЕДМПЦЕОЙС. ч УМХЮБЕ ОЕХДБЮЙ РТПЙЪЧПДЙФУС ПФЛБФ ДП ВМЙЦБКЫЕК ФПЮЛЙ ЧЕФЧМЕОЙС, ЕУМЙ ФБЛБС ЕУФШ, ЙМЙ ЖЙЛУЙТХЕФУС ОЕХДБЮБ УПРПУФБЧМЕОЙС ДМС ЧУЕЗП РТЕДМПЦЕОЙС.

With-ЛПОУФТХЛГЙС ЖБЛФЙЮЕУЛЙ ЪБНЕОСЕФ УПВПК РТБЧХА ЮБУФШ. рТЙ ХУРЕЫОПН УПРПУФБЧМЕОЙЙ БТЗХНЕОФБ ЖХОЛГЙЙ У ПВТБЪГПН РТЕДМПЦЕОЙС, УПДЕТЦБЭЕЗП with-ЛПОУФТХЛГЙА, ЧНЕУФП ПВЩЮОПК РПДУФБОПЧЛЙ РТПЙЪЧПДЙФУС ЧЩЮЙУМЕОЙЕ БТЗХНЕОФБ with-ЛПОУФТХЛГЙЙ; ТЕЪХМШФБФ ЧЩЮЙУМЕОЙС РЕТЕДБЕФУС Ч ВЕЪЩНСООХА ТЕЖБМ-ЖХОЛГЙА, ЪБДБООХА ФЕМПН with-ЛПОУФТХЛГЙЙ Ч ЧЙДЕ ПВЩЮОПЗП ВМПЛБ, УПУФПСЭЕЗП ЙЪ ПДОПЗП Й ВПМЕЕ ТЕЖБМ-РТЕДМПЦЕОЙК.

ч ТБУУНБФТЙЧБЕНПК ПВЯЕЛФОП-ПТЙЕОФЙТПЧБООПК НПДЕМЙ тЕЖБМБ ПВЕ ЬФЙ ЛПОУФТХЛГЙЙ ТЕБМЙЪПЧБОЩ ЛБЛ ЮБУФОЩЕ УМХЮБЙ ПВПВЭЕООЩИ ЧПЪНПЦОПУФЕК, ТЕБМЙЪПЧБООЩИ, УППФЧЕФУФЧЕООП, БВУФТБЛФОЩНЙ ЛМБУУБНЙ RfLeftSubclause Й RfRightSubclause.

пДЙО ЙМЙ ОЕУЛПМШЛП ПВЯЕЛФПЧ ЛМБУУБ RfLeftSubclause НПЗХФ ВЩФШ РПНЕЭЕОЩ Ч ЛПОЕГ ПВТБЪГБ, Ф.Е. МЕЧПК ЮБУФЙ ТЕЖБМ-РТЕДМПЦЕОЙС, ЮФП СЧМСЕФУС ПРТБЧДБОЙЕН ОБЪЧБОЙС ЛМБУУБ. лПЗДБ Ч РТПГЕУЕ УПРПУФБЧМЕОЙС ПВОБТХЦЙЧБЕФУС ПВЯЕЛФ ЬФПЗП ЛМБУУБ, УЮЙФБЕФУС, ЮФП ПВТБЪЕГ ЪБЛПОЮЕО (ФП ЕУФШ ПУФБФПЛ УПРПУФБЧМСЕНПЗП ЧЩТБЦЕОЙС ДПМЦЕО ВЩФШ Л ЬФПНХ НПНЕОФХ РХУФ). еУМЙ УПРПУФБЧМЕОЙЕ ВЩМП ХУРЕЫОЩН, РТПЙЪЧПДЙФУС ЧЩЪПЧ НЕФПДБ RfLeftSubclause::Process, ЛПФПТПНХ РЕТЕДБЕФУС ФЕЛХЭЙК ЛПОФЕЛУФ УПРПУФБЧМЕОЙС (УПЧПЛХРОПУФШ УЧСЪЕК НЕЦДХ ТЕЖБМ-РЕТЕНЕООЩНЙ Й ЙИ ЪОБЮЕОЙСНЙ). нЕФПД ЧПЪЧТБЭБЕФ true ДМС ЙОДЙЛБГЙЙ ХУРЕИБ, false — ДМС ЙОДЙЛБГЙЙ ОЕХДБЮЙ.

пВЯЕЛФ ЛМБУУБ RfRightSubclause НПЦЕФ ВЩФШ РПНЕЭЕО Ч ТЕЖБМ-РТЕДМПЦЕОЙЙ ОБ НЕУФП РТБЧПК ЮБУФЙ. ч ЬФПН УМХЮБЕ ЧНЕУФП ПВЩЮОПК РТПГЕДХТЩ РПДУФБОПЧЛЙ ЪОБЮЕОЙК РЕТЕНЕООЩИ РТПЙУИПДЙФ ЧЩЪПЧ НЕФПДБ RfRightSubclause::Process. нЕФПД ЧПЪЧТБЭБЕФ ТЕЖБМ-ЧЩТБЦЕОЙЕ, ЛПФПТПЕ Й ЙУРПМШЪХЕФУС Ч ЛБЮЕУФЧЕ ТЕЪХМШФБФБ ТБВПФЩ ЧУЕК ЖХОЛГЙЙ.

уПВУФЧЕООП ЛПОУФТХЛГЙЙ where Й with ТЕБМЙЪПЧБОЩ Ч ЧЙДЕ ЛМБУУПЧ RfWhereClause Й RfWithClause, ОБУМЕДХЕНЩИ ПФ RfLeftSubclause Й RfRightSubclause УППФЧЕФУФЧЕООП.

уМЕДХЕФ ЪБНЕФЙФШ, ЮФП ПВЩЮОХА РТПГЕДХТХ РПДУФБОПЧЛЙ ЪОБЮЕОЙК РЕТЕНЕООЩИ ВБЪЙУОПЗП тЕЖБМБ ФПЦЕ НПЦОП ТЕБМЙЪПЧБФШ Ч ЧЙДЕ ОБУМЕДОЙЛБ ЛМБУУБ RfRightSubclause. ьФЙН ЧПЪНПЦОПУФЙ ПВПВЭЕООПЗП НЕИБОЙЪНБ, ТБЪХНЕЕФУС, ОЕ ЙУЮЕТРЩЧБАФУС.

чЧЕДЕООЩЕ ПВПВЭЕОЙС РПЪЧПМСАФ УХЭЕУФЧЕООП ТБУЫЙТЙФШ ЙЪПВТБЪЙФЕМШОЩЕ ЧПЪНПЦОПУФЙ ТБУУНБФТЙЧБЕНПК НПДЕМЙ РП УТБЧОЕОЙА У ЙУИПДОЩН СЪЩЛПН тЕЖБМ-5.

тЕБМЙЪБГЙС ЖХОЛГЙПОБМШОПЗП БОБМПЗБ СЪЩЛБ тЕЖБМ Ч ЧЙДЕ ОБДУФТПКЛЙ ОБД ЖХОЛГЙПОБМШОЩН БОБМПЗПН СЪЩЛБ мЙУР МПЗЙЮОП РТЙЧПДЙФ Л НЩУМЙ ПВ ЙУРПМШЪПЧБОЙЙ ХЦЕ ОБТБВПФБООЩИ ДМС МЙУРПЧУЛПК ЮБУФЙ InteLib ВЙВМЙПФЕЮОЩИ ЖХОЛГЙК, УППФЧЕФУФЧХАЭЙИ ЧУФТПЕООЩН ЖХОЛГЙСН СЪЩЛБ мЙУР.

рТЙ ЬФПН УМЕДХЕФ РПНОЙФШ П ТБЪМЙЮЙЙ НЕЦДХ НОПЦЕУФЧПН ЧУЕИ S-ЧЩТБЦЕОЙК Й НОПЦЕУФЧПН S-ЧЩТБЦЕОЙК, ДПРХУФЙНЩИ ЛБЛ РТЕДУФБЧМЕОЙЕ ТЕЖБМ-ЧЩТБЦЕОЙС. лТПНЕ ФПЗП, ОЕПВИПДЙНП ХЮЙФЩЧБФШ ТБЪМЙЮЙЕ УЕНБОФЙЛ ДЧХИ СЪЩЛПЧ. рТПЙММАУФТЙТХЕН ЧПЪОЙЛБАЭХА РТПВМЕНХ ОБ РТЙНЕТЕ. тБУУНПФТЙН ТЕЖБМ-ЧЩТБЦЕОЙЕ ЗДЕ CAR ПВПЪОБЮБЕФ УФБОДБТФОХА мЙУР-ЖХОЛГЙА. мПЗЙЮОП ПЦЙДБФШ, ЮФП ТЕЪХМШФБФПН ЧЩЮЙУМЕОЙС ФБЛПК ЛПОУФТХЛГЙЙ ДПМЦОП УФБФШ ТЕЖБМ-ЧЩТБЦЕОЙЕ 1 10 100 , ЙМЙ, ЙОБЮЕ ЗПЧПТС, S-ЧЩТБЦЕОЙЕ (1 10 100) . пДОБЛП ОЕ ЧУЕ ФБЛ РТПУФП. рЕТЧЩК БЛФЙЧОЩК ЧЩЪПЧ, ЕУМЙ ОЕ РТЙОСФШ УРЕГЙБМШОЩИ НЕТ, ЧЕТОЕФ S-ЧЩТБЦЕОЙЕ 1 , ЧФПТПК — 10 , ФТЕФЙК — 100 . чУЕ ФТЙ, УМЕДХЕФ ПФНЕФЙФШ, ОЕ СЧМСАФУС ДПРХУФЙНЩНЙ Ч ЛБЮЕУФЧЕ ТЕЖБМ-ЧЩТБЦЕОЙС, ЮФП ХЦЕ ПЪОБЮБЕФ ЧПЪОЙЛОПЧЕОЙЕ ПЫЙВПЮОПК УЙФХБГЙЙ. оП ДБЦЕ ЕУМЙ ВЩ ЧУЕ ФТЙ ТЕЪХМШФБФБ УМХЮБКОП ПЛБЪБМЙУШ РТЙОБДМЕЦБЭЙНЙ ДПРХУФЙНПНХ НОПЦЕУФЧХ, — ОБРТЙНЕТ, ЕУМЙ ВЩ ЙУИПДОЩК ЧЩЪПЧ ЧЩЗМСДЕМ ЛБЛ ФП ДБЦЕ Ч ЬФПН УМХЮБЕ РПМХЮЕООЩК ТЕЪХМШФБФ ОЕУЛПМШЛП ПФМЙЮБМУС ВЩ ПФ ФПЗП, ЮЕЗП НЩ ПЦЙДБМЙ ( (1 10 100) ЧНЕУФП ((1)(10)(100)) .

рТЙЮЙОБ ЬФПЗП Ч УЕНБОФЙЮЕУЛПН ТБЪМЙЮЙЙ ЙОФЕТРТЕФБГЙК ДЧХИ СЪЩЛПЧ. ч тЕЖБМЕ, Ч ПФМЙЮЙЕ ПФ мЙУРБ, ТЕЪХМШФБФ ЧЩЮЙУМЕОЙС ЛПОЛБФЕОБГЙЙ ОЕУЛПМШЛЙИ ЧЩТБЦЕОЙК ЕУФШ ЛПОЛБФЕОБГЙС ТЕЪХМШФБФПЧ, ФП ЕУФШ, Ч ФЕТНЙОБИ мЙУРБ, ТЕЪХМШФБФ РТЙНЕОЕОЙС ЖХОЛГЙЙ APPEND Л РПМХЮЕООЩН ТЕЪХМШФБФБН, ФПЗДБ ЛБЛ Ч мЙУРЕ Ч БОБМПЗЙЮОПК УЙФХБГЙЙ ФТБДЙГЙЙ РПДУЛБЪЩЧБАФ ПЦЙДБФШ ЮЕЗП-ФП РПИПЦЕЗП ОБ ТЕЪХМШФБФ ЖХОЛГЙЙ MAP (УРЙУПЛ, РПУФТПЕООЩК ЙЪ ТЕЪХМШФБФПЧ).

рТЕПДПМЕФШ РТПВМЕНХ НПЦОП, ЧЧЕДС ЧПЪНПЦОПУФШ РПНЕЮБФШ ПУПВЩН ПВТБЪПН ФЕ БЛФЙЧОЩЕ (РПУФТПЕООЩЕ У РПНПЭША ЛМБУУБ RfListConstructor) УРЙУЛЙ, ЛПФПТЩЕ ЧЩЪЩЧБАФ МЙУРПЧУЛХА ЖХОЛГЙА. рТЙ ЧЩЮЙУМЕОЙЙ ФБЛПЗП УРЙУЛБ РПМХЮЕООЩК ТЕЪХМШФБФ, РТЕЦДЕ ЮЕН ВЩФШ ЧПЪЧТБЭЕООЩН ЧЩЪЩЧБАЭЕК ЖХОЛГЙЙ, ЙОЛБРУХМЙТХЕФУС Ч УРЙУПЛ ЙЪ ПДОПЗП ЬМЕНЕОФБ. дМС ЬФПЗП Ч ЛМБУУЕ RfListConstructor РТЕДХУНПФТЕО ДПРПМОЙФЕМШОЩК ПРЕТБФПТ || , ЛПФПТЩК ДЕМБЕФ ФП ЦЕ, ЮФП Й ЧЧЕДЕООЩК ТБОЕЕ ПРЕТБФПТ | , ПФМЙЮБСУШ ПФ ОЕЗП ФПМШЛП ЧЩУФБЧМЕОЙЕН УППФЧЕФУФЧХАЭЕЗП РТЙЪОБЛБ Х РПТПЦДБЕНПЗП БЛФЙЧОПЗП УРЙУЛБ.

пРЙУБООБС ЧЩЫЕ ПВЯЕЛФОП-ПТЙЕОФЙТПЧБООБС НПДЕМШ ТЕЖБМ-НБЫЙОЩ Ч УПЮЕФБОЙЙ У ТЕБМЙЪПЧБООПК ТБОЕЕ НПДЕМША БМЗЕВТЩ МЙУРПЧУЛЙИ S-ЧЩТБЦЕОЙК РТЙЧПДЙФ Л ЙДЕЕ УПЪДБОЙС ЗЙВТЙДБ СЪЩЛПЧ мЙУР Й тЕЖБМ.

ч ТБВПФБИ [5,6] ПРЙУБО ФТБОУМСФПТ ХУЕЮЕООПЗП ДЙБМЕЛФБ СЪЩЛБ мЙУР, ОБЪЧБООПЗП InteLib Lisp. фТБОУМСФПТ ЗЕОЕТЙТХЕФ ОБ ЧЩИПДЕ НПДХМШ, ОБРЙУБООЩК ОБ СЪЩЛЕ уЙ++, РТЕДОБЪОБЮЕООЩК ДМС ЙУРПМШЪПЧБОЙС У ВЙВМЙПФЕЛПК InteLib. пФНЕЮБЕФУС, ЮФП ХУФТПКУФЧП ЬФПЗП ФТБОУМСФПТБ ЮТЕЪЧЩЮБКОП РТЙНЙФЙЧОП Ч УЙМХ РПДПВЙС РПМХЮБЕНЩИ ЛПОУФТХЛГЙК уЙ++ Й ЙУИПДОПЗП ЛПДБ ОБ мЙУРЕ.

бОБМПЗЙЮОЩК ФТБОУМСФПТ НПЦЕФ ВЩФШ УПЪДБО ДМС СЪЩЛБ тЕЖБМ (ОБРТЙНЕТ, ДМС ДЙБМЕЛФБ тЕЖБМ-5, ЧУЕ ЧПЪНПЦОПУФЙ ЛПФПТПЗП ЙНЕАФ БДЕЛЧБФОХА НПДЕМШ Ч ВЙВМЙПФЕЛЕ). пЮЕЧЙДОП, РТЙ РПУФТПЕОЙЙ ФБЛПЗП ФТБОУМСФПТБ ОЕПВИПДЙНП РТЕДХУНПФТЕФШ ЧПЪНПЦОПУФШ ЙУРПМШЪПЧБОЙС ПВПВЭЕООЩИ ТЕЖБМ-РЕТЕНЕООЩИ, Б ФБЛЦЕ ПВПВЭЕОЙК ЛПОУФТХЛГЙК with Й where (ЕУФЕУФЧЕООП РТЕДРПМПЦЙФШ, ЮФП УБНЙ ПВПВЭЕОЙС ТЕБМЙЪХАФУС ОБ уЙ++, Й Ч ЛПОУФТХЛГЙСИ тЕЖБМБ ДПМЦЕО ВЩФШ РТЕДХУНПФТЕО ФПМШЛП ОЕЛПФПТЩК ЙОФЕТЖЕКУ Л ФБЛЙН ПВПВЭЕОЙСН). уМЕДХЕФ ПЦЙДБФШ, ЮФП УМПЦОПУФШ РПУФТПЕОЙС ФБЛПЗП ФТБОУМСФПТБ ФБЛЦЕ ВХДЕФ ОЕЧЩУПЛБ, ЮФП РПЪЧПМСЕФ ТБУУНБФТЙЧБФШ ЕЗП ЛБЛ РПВПЮОЩК РТПДХЛФ ТБЪТБВПФЛЙ ВЙВМЙПФЕЛЙ InteLib.

оБЛПОЕГ, ДМС РПУФТПЕОЙС ФТБОУМСФПТБ ДМС ЗЙВТЙДБ мЙУРБ Й тЕЖБМБ ДПУФБФПЮОП ТБЪТБВПФБФШ УЙОФБЛУЙЮЕУЛЙЕ УПЗМБЫЕОЙС. нПЦОП ПЦЙДБФШ, ЮФП РПУФТПЕОЙЕ ФТБОУМСФПТБ У ФБЛПЗП ЗЙВТЙДОПЗП СЪЩЛБ ФБЛЦЕ ОЕ УПУФБЧЙФ РТПВМЕНЩ Й ОЕ ПЛБЦЕФУС ТЕУХТУПЕНЛЙН.

рТЕДМПЦЕООБС Ч УФБФШЕ ПВЯЕЛФОП-ПТЙЕОФЙТПЧБООБС НПДЕМШ ТБУЫЙТЕООПК ТЕЖБМ-НБЫЙОЩ РПЪЧПМСЕФ, ОЕ ЧЩИПДС ЪБ ТБНЛЙ СЪЩЛБ уЙ++ Й ЙУРПМШЪХС, УППФЧЕФУФЧЕООП, УХЭЕУФЧХАЭЙЕ УЙУФЕНЩ РТПЗТБННЙТПЧБОЙС ВЕЪ УРЕГЙБМШОЩИ НПДЙЖЙЛБГЙК, РТЙНЕОСФШ Ч РТПЕЛФБИ ЙЪПВТБЪЙФЕМШОЩЕ РБТБДЙЗНЩ, ОБТБВПФБООЩЕ Ч СЪЩЛЕ тЕЖБМ, Б РТЙ ОЕПВИПДЙНПУФЙ Й ТБУЫЙТСФШ ЧПЪНПЦОПУФЙ ЬФЙИ РБТБДЙЗН.

ч УПЮЕФБОЙЙ У ТБЪТБВПФБООПК ТБОЕЕ НПДЕМША БМЗЕВТЩ S-ЧЩТБЦЕОЙК СЪЩЛБ мЙУР, РТЕДМПЦЕООБС НПДЕМШ РПТПЦДБЕФ УТЕДХ ДМС НХМШФЙРБТБДЙЗНБМШОПЗП РТПЗТБННЙТПЧБОЙС Ч ТБНЛБИ РТПЕЛФПЧ, ПУОПЧОЩН СЪЩЛПН ЛПФПТЩИ СЧМСЕФУС уЙ++.

рПУЛПМШЛХ РТЙНЕОЕОЙЕ РТЕДМПЦЕООЩИ НЕФПДПЧ ОЕ ФТЕВХЕФ ОЙ НПДЙЖЙЛБГЙЙ УХЭЕУФЧХАЭЙИ УЙУФЕН РТПЗТБННЙТПЧБОЙС, ОЙ ЧОЕДТЕОЙС ОПЧЩИ, ВБТШЕТ ЧОЕДТЕОЙС ДМС РТЕДМПЦЕООПК НЕФПДПМПЗЙЙ ПЛБЪЩЧБЕФУС ЮТЕЪЧЩЮБКОП ОЙЪПЛ Й УЧПДЙФУС Л ПУЧПЕОЙА ВЙВМЙПФЕЛЙ ЛМБУУПЧ InteLib, ЙНЕАЭЕК ДПУФБФПЮОП РТПУФХА УФТХЛФХТХ. ьФП РПЪЧПМСЕФ ПЦЙДБФШ, ЮФП РТЕДМПЦЕООЩК НЕФПД НПЦЕФ ОБКФЙ РТЙНЕОЕОЙЕ Ч ЙОДХУФТЙБМШОПН РТПЗТБННЙТПЧБОЙЙ.

1 лБХЖНБО ч.ы. сЪЩЛЙ РТПЗТБННЙТПЧБОЙС. лПОГЕРГЙЙ Й РТЙОГЙРЩ. н.: тБДЙП Й уЧСЪШ, 1993.

2 Kelsey R. at al. Revised report on Algorithmic Language Scheme.

3 уЕТДПВПМШУЛЙК ч.й. сЪЩЛ тежбм Й ЕЗП ЙУРПМШЪПЧБОЙЕ ДМС РТЕПВТБЪПЧБОЙС БМЗЕВТБЙЮЕУЛЙИ ЧЩТБЦЕОЙК. // лЙВЕТОЕФЙЛБ. 1969. N 3. уФТ. 45-51.

4 Steele G. L. Common Lisp the Language, 2nd edition. Digital Press, 1990.

5 Stolyarov A., Bolshakova E., Building Functional Techniques into an Object-oriented System. // Knowledge-Based Software Engineering (proceedings of the 4th JCKBSE, Brno, Czech Republic, 2000), IOS Press, 2000. p.101-106


6 уФПМСТПЧ б. йОФЕЗТБГЙС ЙЪПВТБЪЙФЕМШОЩИ УТЕДУФЧ БМШФЕТОБФЙЧОЩИ СЪЩЛПЧ РТПЗТБННЙТПЧБОЙС Ч РТПЕЛФЩ ОБ C++. нПУЛЧБ, 2001. тХЛПРЙУШ ДЕР. Ч чйойфй тбо

7 Stroustrup B. The C++ Programming Language, 3rd edition. Addison-Wesley. 1997.

8 фХТЮЙО ч.ж. нЕФБСЪЩЛ ДМС ЖПТНБМШОПЗП ПРЙУБОЙС БМЗПТЙФНЙЮЕУЛЙИ СЪЩЛПЧ. // гЙЖТПЧБС ЧЩЮЙУМЙФЕМШОБС ФЕИОЙЛБ Й РТПЗТБННЙТПЧБОЙЕ. н.: уПЧ. ТБДЙП, 1966. уФТ. 116-124

9 фХТЮЙО ч.ж. нЕФББМЗПТЙФНЙЮЕУЛЙК СЪЩЛ. // лЙВЕТОЕФЙЛБ. 1968. N 4. уФТ. 45-54.

10 фХТЮЙО ч.ж. ьЛЧЙЧБМЕОФОЩЕ РТЕПВТБЪПЧБОЙС РТПЗТБНН ОБ тЕЖБМЕ // бЧФПНБФЙЪЙТПЧБООБС УЙУФЕНБ ХРТБЧМЕОЙС УФТПЙФЕМШУФЧПН. н.: гойрйбуу, 1974. уФТ. 36-68.

11 Turchin V.F. The concept of a supercompiler // ACM Transactions on Programming Languages and Systems. 1986. Vol. 8, N 3. Pg. 292-325.

12 Turchin V. REFAL-5, Programming Guide and Reference Manual. New England Publishing Co., Holyoke, 1989.

Язык программирования Рефал Плюс

    Юлия Кугушева 2 лет назад Просмотров:

1 Университет города Переславля им. А. К. Айламазяна Рутен Гурин, Сергей Романенко Язык программирования Рефал Плюс Учебное пособие 2006

2 УДК ББК Г95 Рецензенты: Институт программных систем Российской академии наук д.ф.-м.н., чл.-корр. РАН Сергей Михайлович Абрамов; Институт прикладной математики им. М.В. Келдыша Российской академии наук с.н.с., к.ф.-м.н. Александр Николаевич Андрианов Рутен Гурин, Сергей Романенко Г95 Язык программирования Рефал Плюс. Курс лекций. Учебное пособие для студентов университета города Переславля. Переславль-Залесский: Университет города Переславля им. А. К. Айламазяна, с. Описывается язык программирования Рефал Плюс, предназначенный для обработки символьной информации. Рассматриваются методы программирования на Рефале Плюс, которые иллюстрируются многочисленными примерами программ. Пособие адресовано студентам и преподавателям информатики. УДК ББК c Рутен Гурин, Сергей Романенко, 2006 c Университет города Переславля им. А.К. Айламазяна, 2006 ISBN

3 Оглавление Введение 9 1 Программирование на Рефале Плюс Первый пример Структуры данных Объектные выражения Представление данных в виде объектных выражений Объекты и значения Сборка мусора Вычисление и анализ объектных выражений Результатные выражения Переменные Образцы Функции, определяемые в программе Форматы функций Определения функций Определения функций из одного предложения Локальные переменные Лирико-синтаксическое отступление: тропы, хвосты и источники Локальные переменные (продолжение) Рекурсия Неуспехи и аварии

4 1.5.1 Неуспех при вычислении результатных выражений и троп Перестройки Перехват неуспехов Управление перехватом неуспехов Смысл правых частей Откатные и безоткатные функции Логические условия Проверки и предикаты Ветвления Логические связки Пример: программа дифференцирования Пример: сравнение множеств Использование селекторов прямого доступа Функции, выдающие несколько результатов Сквозной просмотр выражений Быстрая сортировка Итеративные циклы Перебор с возвратом Задача о ферзях Задача о цепочках: Пример: компилятор для простого императивного языка Входной язык компилятора Выходной язык Общая структура компилятора Модули компилятора и их интерфейсы Головной модуль компилятора Сканер Синтаксический анализатор Генератор кода Модуль работы со словарем

5 2 Синтаксис и семантика Рефала Плюс Нотация для записи синтаксиса Естественный метод описания семантики Лексическая структура программы Комментарии Лексемы Ключевые слова Символы-литеры Символы-слова Символы-числа Переменные Нормализация потока лексем Объекты и значения Объектные выражения Синтаксис объектных выражений Статические и динамические символы Символические имена Символические имена выражений Устранение символических имен выражений Значения переменных и среды Результатные выражения Синтаксис Вычисление результатных выражений Примеры Образцы Синтаксис Сопоставление с образцом Примеры Жесткие выражения Синтаксис Сопоставление с жестким выражением Примеры Тропы Синтаксис Вычисление троп

6 Условия Присваивания Поиски Перестройки Огражденные тропы Отрицания условий Заборы Отсечения Тупики Правые части Аварии Перехваты аварий Распутья Выборы Результатные выражения как источники Определения функций Объявления Объявления констант Объявления ящиков, векторов, строк, таблиц и каналов Объявления функций Директивы отладки Контекстные ограничения Устранение избыточных конструкций Ограничения, налагаемые объявлениями функций Ограничения на использование ссылок на функции Ограничения на использование переменных Ограничения на использование отсечений Модули Исполнение программы Библиотека функций Использование библиотечных функций Access: прямой доступ к выражениям

7 3.3 Apply: вызов функций, переданных через параметры Arithm: целочисленная арифметика Bit: Операции с цепочками битов Box: работа с ящиками Class: предикаты для распознавания классов символов Compare: сравнение выражений Convert: преобразования между различными типами данных Dos: связь с операционной системой StdIO: стандартный ввод-вывод String: работа со строками Table: работа с таблицами Vector: работа с векторами Принципы реализации Рефала Плюс Общая схема реализации Виртуальный код Состояние виртуальной машины Некоторые обозначения Метки и адреса Пустая команда Команды управления неуспехами Команды переходов и вызовов функций Команды обработки ошибок Команды построения объектных выражений Команды очистки стека Команды анализа объектных выражений Компиляция Рефал-программ в виртуальный код Абстрактный синтаксис Функции, связанные с форматами Компиляция результатных выражений Генерация ошибок Компиляция троп, хвостов и источников

8 4.3.6 Компиляция троп Компиляция хвостов Компиляция источников Компиляция предложений Компиляция образцов Завершение компиляции образцовых выражений Закрытые с двух сторон элементы образцов Жесткие элементы справа Компиляция образцовых распутий Компиляция определения функции Литература 213 Алфавитный указатель функций 217 8

9 Введение Рефал Плюс представляет собой один из диалектов языка программирования Рефал. Рефал (алгоритмический язык рекурсивных функций) был создан Валентином Федоровичем Турчиным в качестве языка, предназначенного для описания семантики других алгоритмических языков [Тур 1966], [Тур 1971]. Впоследствии, после появления достаточно эффективных реализаций [КРТ 1972], [БзР 1977], [Ром 1987а] Рефал нашел применения в таких областях как компьютерная алгебра, конструирование компиляторов и интерпретаторов, искусственный интеллект и др. Основным типом данных в Рефале являются объектные выражения, которые представляют собой произвольные деревья, изображаемые в линейной записи как последовательности символов и скобок, правильно построенные относительно скобок. Символы представляют собой элементарные объекты (такие как литеры, слова, числа и ссылки на объекты). Основным средством для анализа структуры объектных выражений и для доступа к их компонентам является сопоставление с образцом. Образцы в Рефале могут содержать символы, скобки и переменные. Если объектное выражение имеет структуру, соответствующую образцу, переменные, входящие в образец, получают в качестве значений фрагменты объектного выражения. Значения переменных впоследствии могут использоваться для построения новых объектных выражений. Рефал-программа представляет собой набор определений функций. Каждая функция получает в качестве аргумента неко- 9

10 торое объектное выражение и вырабатывает в качестве результата некоторое объектное выражение. Функции могут произвольным образом вызывать друг друга. Основным средством организации управления в программах является рекурсия, т. е. такая организация вызовов функций, при которой некоторые функции вызывают сами себя (либо непосредственно, либо через другие функции). Рефал Плюс возник в результате обобщения опыта, накопленного при разработке, реализации и использовании Базисного Рефала [БзР 1977], Рефала-2 [КлР 1986], [КлР 1987], [Ром 1987а], Рефала-4 [Ром 1987б], [Ром 1987в], Рефала-5 [Тур 1989], и языков FLAC [Кис 1987] и RL [Ром 1987г], [Ром 1988а], [Ром 1988б]. По сравнению с другими диалектами Рефала, Рефал Плюс обладает следующими особенностями. Более развитая система модульности. Каждый модуль разделен на две части: интерфейс модуля и реализацию модуля. Интерфейс модуля содержит ту часть модуля, которая видна из других модулей, а реализация модуля содержит те части, которые скрыты от других модулей. Интерфейс модуля может содержать любые объявления, что дает возможность экспортировать из модуля не только объявления функций, но и объявления констант, каналов ввода-вывода, ящиков и таблиц. При экспорте функций экспортируются не только их имена, но и описания форматов их аргументов и результатов, что дает возможность проверять корректность их вызовов еще на стадии компиляции. При компиляции модуля используются только интерфейсы других модулей, но не их реализации, что позволяет проводить компиляцию модуля даже в том случае, если еще отсутствуют реализации других модулей. Кроме того, внесение изменений в реализацию модуля не требует перекомпиляции зависящих от него модулей. Таким образом, допускаются любые (в том числе и циклические) связи между модулями. Статические объявления динамических объектов. 10

11 Все объекты, которые могут порождаться динамически, во время исполнения программы (каналы ввода-вывода, ящики, векторы и таблицы) могут объявляться и статически. В этом случае им присваиваются символические имена, которые используются в дальнейшем в тексте программы. Объявления функций Каждая функция в Рефале Плюс может быть объявлена откатной или безоткатной. Если функция откатная, она может выдавать в качестве результата особое значение неуспех. Например, все функции-предикаты выдают в качестве результата либо пустое выражение, либо неуспех. Если же функция безоткатная, она никогда не выдает неуспех. Предыдущие диалекты Рефала позволяли определять только безоткатные функции. Другая особенность Рефала Плюс возможность определять функции, получающие несколько аргументов и выдающие несколько результатов. Количество и типы аргументов функции мы будем называть ее арностью (arity), а количество и типы результатов ее коарностью (co-arity). Арность и коарность функции определяются заданием ее входного и выходного формата. Эти форматы представляют собой образцы, которые содержат символы, скобки и переменные. Входной формат налагает синтаксические ограничения на внешний вид вызовов функции, а выходной формат на контексты, в которых может стоять вызов функции. Если из входного формата удалить символы и скобки, получаем последовательность переменных, описывающих арность функции. Если же то же самое сделать с выходным форматом функции, получаем ее коарность. Явное объявление форматов функций позволяет обнаруживать многие ошибки еще на стадии компиляции и дает возможность уменьшить накладные расходы при исполнении вызовов функций. В предыдущих диалектах Рефала считалось, что каждая функция получает ровно один аргумент и выдает ровно один результат. 11

12 Перехват неуспехов и аварий. Вычисление любой конструкции в Рефале Плюс может завершаться либо успехом, либо неуспехом, либо аварией. Если вычисление закончилось успехом, результатом является некоторое объектное выражение (которое всегда соответствует некоторому заранее ожидаемому формату результата и в реализации может фактически представляться несколькими выражениями). Если вычисление закончилось неуспехом, результатом является сигнал неуспеха и, может быть, некоторая дополнительная информация о месте, в котором он возник. Если вычисление закончилось аварией, результатом является сигнал аварии и сообщение об ошибке некоторое объектное выражение. Рефал Плюс содержит конструкции, которые позволяют перехватывать и анализировать неуспехи и аварии. Ввод-вывод объектных выражений. Рефал Плюс предоставляет набор функций, позволяющих выводить и вводить цепочки литер, а также изображения объектных выражений. При этом происходит автоматическое превращение литер слов и чисел в их изображения и обратно. Работа с ящиками, векторами и таблицами. Рефал Плюс дает возможность работать с динамически создаваемыми объектами: ящиками, векторами, строками и таблицами. Средства работы с ящиками те же, что и в Рефале-2, в то время как векторы, строки и таблицы являются особенностью Рефала Плюс. Каждый ящик представляет собой объект, который может содержать произвольное объектное выражение. Каждый вектор представляет собой объект, который может содержать произвольную конечную последовательность объектных выражений. 12

13 Каждая строка представляет собой объект, который может содержать произвольную конечную последовательность литер. Доступ к ящикам, векторам и строкам производится через символы-ссылки, указывающие на эти объекты. Имеются функции для создания новых ящиков, векторов и строк и для извлечения и изменения их содержимого. Возможно выборочное извлечение и изменение отдельных компонент векторов и строк. Каждая таблица представляет собой объект, который содержит конечный набор ключей, с каждым из которых связано его значение. И ключи, и таблицы являются некоторыми объектными выражениями. Доступ к таблице производится через символыссылки, указывающие на эту таблицу. Имеются функции для создания и копирования таблиц, для получения по ключу его значения и для получения всех ключей, содержащихся в таблице. По существу, каждая таблица представляет собой изображение функции с конечной областью определения. Векторное представление объектных выражений. Реализация Рефала Плюс основана на новом, векторном представлении объектных выражений [АбР 1988], позволяющем свести копирование выражения к копированию пары указателей на его концы. Дешевизна операции копирования позволяет применять функциональный стиль программирования на Рефале, в то время как при использовании предыдущих реализаций приходилось тщательно избегать копирования, что вынуждало, по существу, придерживаться императивного стиля. Освобождение памяти, занятой уже ненужными выражениями, производится с помощью сборки мусора. 13

14 Глава 1 Программирование на Рефале Плюс В данной главе мы даем неформальный обзор основных изобразительных средств языка Рефал Плюс, приводим примеры программ и обсуждаем некоторые приемы программирования на Рефале Плюс. Полное описание Рефала Плюс содержится в главе II ( Синтаксис и семантика Рефала Плюс ), куда и следует обращаться за недостающими тонкостями и подробностями. Если в примерах программ встречаются вызовы неизвестных функций, следует обращаться за их описанием к главе III ( Библиотека функций ) и к разделу Алфавитный указатель функций. 1.1 Первый пример По сложившейся традиции, начнем с рассмотрения простейшей программы на Рефале Плюс: $use StdIO; $func Main = e; Main // Импорт функций ввода-вывода // из модуля StdIO // Объявление формата функции: // на входе — пусто, // на выходе — что угодно. // Определение главной функции 14

; // Печать и перевод строки Эта программа состоит из трех директив. Первая директива $use StdIO; говорит о том, что в программе будут использоваться библиотечные функции ввода-вывода, которые должны быть импортированы из модуля StdIO. Вторая директива описывает формат функции Main: что она может получать на входе, и что она может выдавать в качестве результата. Третья директива является определением функции Main. По соглашению, принятому в Рефале Плюс, работа программы всегда начинается с вызова функции Main. Функция Main всегда имеет пустой аргумент. В данной программе она вызывает библиотечную функцию PrintLn с аргументом «Hello!», в результате чего на стандартное устройство вывода выводится цепочка литер Hello! а вслед за ней литера конец строки, после чего работа программы заканчивается. Литеры // обозначают начало комментария, т. е. все, что следует за ними до конца строки игнорируется. 1.2 Структуры данных Объектные выражения Данные, обрабатываемые программами, написанными на языке Рефал Плюс, являются так называемыми объектными выражениями. Ниже, в качестве примера, приведены 3 объектных выражения «Петр» «Иванович» 33 «года» («Маша» 17) («Клава» 24) («Эльвира» 6) («мой» «дом») «имеет» («большие» («светлые» «окна»)) 15

16 Первое, что бросается в глаза, это использование скобок. Если в этих примерах изменить количество или расположение скобок, то изменится структура и, видимо, подразумеваемый смысл этих выражений. Кроме скобок вышеприведенные выражения содержат символы. Вот примеры символов: «John» «Джон» «джон» «ку-ку» В общем случае объектные выражения состоят из символов и скобок. Всякое объектное выражение это последовательность объектных термов (которая может быть пустой). Объектный терм это либо символ, либо объектное выражение, заключенное в круглые скобки ( и ). Таким образом, всякое объектное выражение это последовательность символов и скобок, в которой скобки правильно расставлены. В памяти компьютера выражения хранятся в виде структуризованных объектов, однако при выполнении операций ввода/вывода (печать, запись в файл или чтение из файла и т. п.) они должны быть представлены в виде линейных последовательностей литер (печатных знаков). Рефал-система обеспечивает ввод и вывод объектных выражений и все необходимые при этом преобразования. При вводе выражений входной поток литер разбивается на лексемы. Каждая лексема изображает символ или скобку. Лексемы отделяются друг от друга пробелами (при этом переход на следующую строку считается эквивалентным пробелу). Если рядом оказываются две скобки или скобка и символ, пробелы между ними могут опускаться. Во всех остальных случаях лексемы обязательно должны быть разделены хотя бы одним пробелом. В текстах Рефал-программ могут появляться в виде констант следующие символы: символы-литеры, символы-слова и символычисла. Символ-литера это печатный знак. Последовательность символов-литер изображается в виде последовательности соответствующих литер, заключенной в апострофы. 16

17 Примеры литер: A a * 2 Цепочка из трех литер A, B и C может быть записана, например, следующими способами (а также многими другими): A B C ABC AB C Символ-слово представляет собой цепочку литер и изображается в виде этой цепочки литер, заключенной в двойные кавычки. Если слово начинается с прописной латинской буквы или подчеркивания, и содержит только латинские буквы, цифры и подчеркивания, то окружающие его двойные кавычки можно опустить. Примеры слов: «Вася» «Вот-Слово» «вот-очень-очень-длинное-слово» X_25m3s «равно?» Символ-число является целым числом. Изображается в виде непустой последовательности десятичных цифр, перед которой может стоять знак + или -. Например: Разрядность целых чисел произвольна Представление данных в виде объектных выражений Объектные выражения особенно удобны для представления символьных (т. е. не чисто числовых) данных. 17

18 Пусть, например, мы хотим выбрать представление в виде объектных выражений для алгебраических формул. Нам нужно уметь представлять константы, переменные и формулы, которые получаются в результате применения бинарной операции к двум более простым формулам. Обозначим через p объектное выражение, которое является представлением формулы p. Тогда мы можем считать, что представлением целых чисел являются соответствующие символы-числа, представлением переменных являются соответствующие символы-слова, а для бинарных операций имеют место соотношения p + q = («плюс» p q ) p q = («минус» p q ) p q = («умн» p q ) p/q = («дел» p q ) p q = («степ» p q ) Таким образом, формула (X + Y 2 ) 512 представляется в виде («минус» («плюс» X («степ» Y 2)) 512) В качестве другого примера рассмотрим представление шахматной позиции в виде объектного выражения. Первым делом нужно обозначить название и цвет каждой фигуры. Например («бел» «Король»), («черн» «пешка»). Затем нужно указать поле каждой фигуры. Например («e» 2), («h» 7). Теперь мы можем представить всю позицию в виде последовательности объектных термов, каждый из которых содержит имя и цвет фигуры, а также ее поле. Например ((«бел» «Король») («g» 5)) ((«черн» «Король») («a» 7)) ((«бел» «Пешка») («c» 6)) ((«бел» «Конь») («g» 1)) ((«черн» «Конь») («a» 8)) 18

Илон Маск рекомендует:  Передача параметров между страницами (location.search)

19 1.2.3 Объекты и значения В самом широком смысле под объектами обычно понимают некоторые сущности, которые существуют во времени, развиваются, но при этом остаются сами собой. Хорошим примером объекта может служить человек, который рождается, растет, развивается и умирает, все же оставаясь, в каком-то смысле, тем же самым человеком. Другой знаменитый пример принадлежит Гераклиту (расцвет творческих сил которого приходится приблизительно на гг. до н. э.). Гераклит учил, что нельзя дважды войти в одну и ту же реку, ибо на входящих в ту же самую реку набегают все новые и новые воды [Гер 500]. Таким образом, река тоже может служить хорошим примером объекта. Под значениями в широком смысле обычно понимают некоторые сущности, которые не меняются, не развиваются и, в этом смысле, находятся вне времени. Неизвестно, существуют ли значения в реальной жизни, но они являются излюбленным предметом изучения в математике. Примером значения, например, может служить число 25. Конечно, значение можно считать частным, вырожденным случаем объекта (а именно, застывшим объектом, не способным к развитию), но мы все же обычно будем называть объектами только такие объекты, которые не являются значениями. Иметь дело с объектами труднее, чем со значениями, ибо они могут изменяться. Поэтому объекты очень часто снабжают именами. Основным свойством имени является то, что оно однозначно связано с объектом (однозначно идентифицирует этот объект). В отличие от самих объектов, имена являются типичными значениями, поскольку они не меняются из-за того, что изменяется сам объект. Например, несмотря на то, что состояние реки Волга непрерывно изменяется, это никак не сказывается на слове Волга. Другим примером (полного) имени могут служить паспортные данные человека: фамилия, имя, отчество, дата и место рождения и т. д. В рамках языка Рефал термины объект и значение имеют 19

20 более специальный смысл. Любое значение в языке Рефал представляет собой некоторое объектное выражение. Любой объект в языке Рефал представляет собой контейнер, который может содержать объектные выражения и другую информацию. Объекты создаются во время компиляции или в процессе работы Рефал-программы. При создании объекта одновременно с ним создается символ-ссылка, который мы будем называть именем объекта или ссылкой на этот объект. Основное свойство имени объекта заключается в том, что оно должно отличаться от всех других символов-ссылок, существующих в момент создания объекта. Благодаря этому между символами-ссылками и объектами существует однозначное соответствие: каждому символу-ссылке соответствует ровно один объект, а равным символам-ссылкам соответствует один и тот же объект. Наглядно взаимосвязь между именем объекта R, объектом и содержимым объекта C можно изобразить следующим образом: R C Рефал Плюс имеет дело с объектами следующих типов. Объекты-функции содержат скомпилированные определения функций. Они создаются во время компиляции программы. Все остальные объекты могут создаваться как статически (т. е. во время компиляции программы), так и динамически (т. е. в процессе исполнения программы). Объекты-ящики предназначены для хранения объектных выражений. Каждый ящик содержит ровно одно объектное выражение. Объекты-таблицы предназначены для хранения конечных множеств упорядоченных пар. Каждая пара содержит два объектных выражения, первое из которых является ключом, а второе значением, связанным с этим ключом. Все ключи в таблице должны быть попарно различны. Таким образом, каждому ключу в таблице однозначно соответствует связанное с ним значение. 20

21 Объекты-каналы дают возможность выполнять операции ввода-вывода. Объекты-векторы предназначены для хранения конечных последовательностей объектных выражений. Объекты-строки предназначены для хранения конечных последовательностей литер Сборка мусора В языке Рефал Плюс имеется возможность порождать объекты во время работы программы, но не предусмотрено никаких специальных средств для явного уничтожения объектов. Таким образом, может случиться так, что в процессе выполнения Рефалпрограммы память будет заполняться все новыми и новыми объектами, хотя многие из них будут уже и не нужны. Конечно, теоретически это не создает никаких проблем, однако, поскольку Рефал-программы исполняются с помощью реальных компьютеров, память которых конечна, во всех реализациях языка Рефал предусмотрен механизм сборки мусора. Сборка мусора автоматически запускается каждый раз, когда исчерпается свободная память. При этом обнаруживаются и удаляются все объекты, которые заведомо не могут повлиять на дальнейшие вычисления, а именно те объекты, до которых невозможно добраться прямо или косвенно, исходя из значений переменных, имеющихся в этот момент. На рисунке 1.1 схематически изображены значения переменных, а также объекты и их содержимое. Белые кружочки изображают некоторые элементы выражений, которые не являются символами-ссылками, черные символы-ссылки. Для удобства изложения все объекты на рисунке пронумерованы. Символыссылки обозначены цифрами. Видно, что по ссылке из значения одной из переменных можно добраться до объекта 1, и из него до объекта 4. По ссылке из значения другой переменной можно непосредственно добраться до объекта 2 и косвенно (через объект 2) до объектов 4, 5, 6, 3. Таким образом, нет способа извлечь информацию из объектов 7 21

22 и 8. Если в этот момент запустить сборку мусора, то объекты 7 и 8 будут уничтожены. Если теперь убрать ссылку на объект 1 из значения переменной, то станет недоступным и объект 1. Если же ссылку на объект 1 оставить, но убрать ссылку на объект 2 из значений переменных, то окажутся ненужными все объекты, кроме 1 и 4. значения переменных Рис. 1.1: Объекты и ссылки 1.3 Вычисление и анализ объектных выражений Результатные выражения Результатные выражения в языке Рефал являются аналогом общеизвестных арифметических выражений. Так, например, арифметическому выражению X Y + 3 в Рефале Плюс соответствует следующее результатное выражение: 3> Угловые скобки обозначают вызов функции. Причем первый символ-слово после левой угловой скобки обозначает имя функции, а все остальное соответствует аргументам функции. Благодаря тому, что аргумент функции всегда явно заключается в угловые функциональные скобки, отпадает необходимость использовать круглые скобки для группировки операций. Например, выражение X (A + B) на Рефале записывается как 22

24 основных операции: конкатенация (сцепление) двух выражений и заключение выражения в скобки. Синтаксис Рефала построен таким образом, чтобы эти операции имели кратчайшие обозначения. А именно, если у нас имеются два результатных выражения Re и Re, то запись Re Re тоже является результатным выражением, которое означает, что надо вычислить Re и Re, а полученные результаты сцепить вместе. Т. е. если результатом вычисления Re и Re являются объектные выражения E и E соответственно, то результатом вычисления Re Re является объектное выражение E E. Если у нас имеется результатное выражение Re, то запись (Re) тоже является результатным выражением, которое означает, что надо вычислить Re, а полученный результат заключить в круглые скобки. Т. е. если результатом вычисления Re является объектное выражение E, то результатом вычисления (Re) является (E). Например, результатом вычисления результатного выражения sx + sy (ez) в среде является объектное выражение (A (B C) D) Переменные Каждая переменная в Рефале Плюс должна начинаться с признака типа переменной. Признак типа указывает на множество допустимых значений переменной и должен быть одной из четырех букв: s, t, v или e. В соответствии с этим все переменные делятся на четыре категории: s-переменные, t-переменные, v-переменные и e-переменные. 24

25 Значениями s-переменных могут быть только символы, значениями t-переменных только объектные термы, значениями v-переменных только непустые объектные выражения. Что касается e-переменных, то их значениями могут быть произвольные объектные выражения. В дальнейшем мы будем говорить, что некоторая переменная является ve-переменной, если она является либо v-переменной, либо e-переменной Образцы В языке Рефал Плюс основным средством анализа объектных выражений являются образцы. Образцы могут содержать символы, круглые скобки и переменные. Например: A B C tx (ey B) Каждый образец изображает множество объектных выражений, которые могут быть получены из него путем замены переменных на произвольные значения, удовлетворяющие их типам. Например, образец A ex изображает множество объектных выражений, которые начинаются с символа A, а образец sx sy множество объектных выражений, состоящих ровно из двух символов. Если одна и та же переменная входит в образец несколько раз, то все ее вхождения должны иметь одно и то же значение. Например, образец tx tx изображает множество выражений, состоящих из двух одинаковых термов. Если нам задано объектное выражение E и образец P, то всегда можно сопоставить E с P и установить, имеет ли E структуру, предписанную образцом P. Если да, то мы говорим, что E успешно сопоставляется с P, в противном случае мы говорим, что результатом сопоставления является неуспех. В результате успешного сопоставления E с P переменные, входящие в P, связываются с соответствующими частями выражения E. Таким образом, результатом сопоставления E с P 25

26 является некоторая среда ρ. Например, если мы сопоставим AAA BBB CCC с образцом ex sy, результатом сопоставления будет среда . Попробуем теперь сопоставить выражение A B C с образцом e1 sx e2. Мы обнаружим, что это можно сделать тремя различными способами, в результате чего получаются три разных среды: Что считать результатом сопоставления в подобных случаях? В Рефале Плюс эта проблема решается следующим образом. Считается, что правильными являются все варианты сопоставления, однако одни варианты предшествуют другим, т. е. имеют приоритет. А именно, пусть ρ 1 и ρ 2 два варианта сопоставления E с P. Рассмотрим все вхождения переменных в P. Если ρ 1 и ρ 2 не совпадают, они приписывают некоторым переменным различные значения. Найдем в P самое первое слева вхождение переменной, которому ρ 1 и ρ 2 приписывают разные значения и сравним длину этих значений. Если значение, приписываемое средой ρ 1, короче, чем значение, приписываемое средой ρ 2, то считается, что ρ 1 предшествует ρ 2, т. е. имеет приоритет перед ρ 2, в противном случае считается, что ρ 2 предшествует ρ 1. Например, сопоставим объектное выражение (A1 A2 A3) (B1 B2) с образцом e1 (ex sa ey) e2. В результате получится следующее множество вариантов сопоставления где варианты сопоставления перечислены в соответствии с их приоритетами, т. е. самый первый вариант находится на первом месте и т. д. 26

27 Описанный выше способ упорядочения вариантов сопоставления называется сопоставлением слева направо. Однако в Рефале Плюс имеется возможность упорядочивать варианты сопоставления и справа налево, при этом упорядочение происходит не по самому левому вхождению переменной, а по самому правому. Чтобы изменить порядок сопоставления, следует приписать к образцу слева ключевое слово $r. Например, если мы сопоставим объектное выражение (A1 A2 A3)(B1 B2) с образцом $r e1 (ex sa ey) e2, множество вариантов сопоставления будет упорядочено следующим образом: 1.4 Функции, определяемые в программе Форматы функций С чисто формальной точки зрения все функции в языке Рефал Плюс имеют ровно один аргумент и всегда выдают ровно один результат. Однако, во многих случаях, мы заранее знаем, какую структуру должны иметь аргумент и результат. Например, функция Add всегда должна получать на входе объектное выражение, состоящее из двух символов, и всегда выдает на выходе объектное выражение, состоящее из одного символа. Ограничения, накладываемые на структуру аргументов и результатов функций, описываются с помощью объявлений функций. Так, например, объявление функции Add имеет вид: $func Add sx sy = sz; В общем случае объявление функции F имеет вид $func F F in = F out ; 27

28 где F in входной формат функции, а F out ее выходной формат. Форматы функции могут содержать символы, круглые скобки и переменные. Индексы переменных никакой информации не несут, используются в качестве комментариев и могут опускаться. Входной и выходной форматы должны быть жесткими, т. е. на одном уровне скобок может находиться не более чем одна veпеременная. Например, формат (e)(e) является жестким, а формат e A e не является. Все аргументы и результаты функции должны иметь структуру, предписанную ее объявлением. Объявление функции должно предшествовать ее первому использованию в каком-либо результатном выражении в программе. При этом, если функция определена в самой программе, ее объявление появляется в тексте программы явно. Если же функция определена в другом модуле, ее объявление должно быть импортировано в программу с помощью директивы $use. Во время компиляции программы производится проверка того, что во всех вызовах функции структура ее аргумента соответствует ее входному формату. Например, результатное выражение > построено правильно. По отношению ко внутреннему вызову функции это очевидно, но для того чтобы проверить корректность наружного вызова, уже требуется привлечь информацию о структуре результата функции Add. А именно, заменяем на выходной формат функции Add, в результате чего получается . Отсюда видно, что аргумент наружного вызова соответствует входному формату функции Add. С другой стороны, если мы напишем в программе результатное выражение 3> оно будет расцениваться компилятором как ошибочное, поскольку аргумент наружного вызова функции Add состоит из трех символов, а не из двух, как предписано ее входным форматом. 28

32 возможность вводить новые переменные для обозначения промежуточных результатов вычислений. А именно, мы можем записать определение функции Sq-Sub1 следующим образом: $func SqSub1 sx = sz; SqSub1 sx = :: sy, ; где :: sy означает, что нужно вычислить и запомнить результат в переменной sy. Затем нужно вычислить . При этом разрешается использовать значение переменной sy. А то, что получится, считается результатом всей правой части предложения Лирико-синтаксическое отступление: тропы, хвосты и источники В этом месте нам придется на время отвлечься от темы локальные переменные и обсудить некоторые особенности синтаксиса Рефала Плюс. Эти особенности связаны не с сутью Рефала Плюс, а с тем, что при его разработке была сделана попытка добиться максимальной краткости при записи программ. Однако, к сожалению, это привело к усложнению системы понятий, связанных с синтаксисом Рефала Плюс. По сути, все конструкции Рефала Плюс, используемые в определениях функций, занимаются либо анализом структуры объектных выражений, либо что-то вычисляют и выдают результат. Для анализа данных служат образцы, а для выработки результатов конструкции, которые называются тропами. Термин тропа был использован для того, чтобы подчеркнуть, что выработка результата это, в общем случае, процесс сложный, который может потребовать выполнения некоторой последовательности шагов: вычисление постепенно, как бы шаг за шагом, продвигается вдоль тропы. А результатное выражение это простейший пример тропы, когда результат получается за один шаг. 32

33 Конструкция = :: sy, ; является более сложным примером тропы, когда вычисление результата выполняется в два этапа. Сначала вычисляется промежуточный результат, а потом он используется при вычислении результатного выражения . При этом, запятая, не обозначает никаких действий. Ее роль чисто синтаксическая. Если ее убрать, то переменная sy прилипнет к следующему за ней результатному выражению = :: sy ; и станет непонятно, где заканчивается часть тропы, ответственная за присваивание, и где начинается выработка результата. В связи с этим, в описании Рефала Плюс приходится использовать два дополнительных синтаксических понятия: хвост и источник. Хвосты и источники это хорошие тропы, обладающие некоторыми полезными синтаксическими свойствами. Хвосты это тропы, которые начинаются с какого-то ключевого слова, благодаря чему они однозначно отделяются от того, что стоит перед ними. Сразу же следует отметить, что ключевые слова в Рефале Плюс могут состоять не только из букв, они могут содержать и другие литеры. Например, тропы = A B C, A B C являются хвостами. (Тонкая разница между = и, для нас пока несущественна, поскольку она проявляется только при обработке неуспехов.) Источники это тропы, которые не содержат запятых на верхнем уровне фигурных скобок. Например: A B C \ < :: sy, ; >33

34 являются источниками. Слово источник было использовано потому, что в конструкции присваивания источник является источником значений для переменных. В дальнейшем, при описании Рефала Плюс, мы будем обозначать тропы через Q, хвосты через R, а источники через S. Если некоторая тропа Q не является хвостом, её (без изменения смысла) всегда можно превратить в хвост, приписав спереди запятую:, Q. Если некоторая тропа Q не является источником, её (без изменения смысла) всегда можно превратить в источник, заключив в фигурные скобки: \ < Q;>Локальные переменные (продолжение) Теперь мы можем вернуться к вопросу о локальных переменных. А именно, присваивание локальным переменным делается с помощью тропы вида S :: He R где S источник, R хвост, а He так называемое жесткое выражение. Жесткое выражение состоит из символов, скобок и переменных и должно удовлетворять следующим ограничениям. Во-первых, He не может содержать два вхождения одной и той же переменной, во-вторых, на каждом уровне скобок может находиться не более одной ve-переменной. Легко видеть, что жесткое выражение He является в то же время и форматным выражением, и во время компиляции программы выполняется проверка, что S заведомо вырабатывает результаты, удовлетворяющие формату He. Тропа S :: He R вычисляется следующим образом. Первым делом вычисляется источник S. Если в результате получается объектное выражение E, то переменные из He связываются с соответствующими частями E, после чего вычисляется хвост R, и полученный результат считается результатом всей конструкции. 34

= будет напечатано три строчки, первая из которых будет содержать литеру A, вторая литеру B, а третья литеру C. Если же в присваивании S :: He R хвост R состоит из одной запятой, его можно опустить, в результате чего получается конструкция S :: He Рекурсия Определение функции может содержать как вызовы библиотечных функций, так и вызовы функций, определяемых в программе. В частности, функция может вызывать и саму себя (либо непосредственно, либо через другие определяемые функции). В этом случае будем говорить, что определение функции является рекурсивным. Необходимость в рекурсивных определениях обычно возникает в тех случаях, когда функция должна быть определена для бесконечного множества аргументов и при этом размер аргумента может быть произвольно большим. 35

36 Рассмотрим, например, следующую задачу. Пусть требуется определить функцию Reverse, которая переворачивает выражение, т. е. переставляет термы аргумента в обратном порядке. А именно, если на вход поступает объектное выражение вида T 1 T 2. T n где T 1, T 2. T n некоторые объектные термы, то на выходе должно получиться объектное выражение T n. T 2 T 1 Если бы длина входного выражения была ограничена, например, если бы мы знали, что n = 1, то можно свести исходную задачу к более простой: 36

Язык рефал

РЕФАЛ-2, РЕФАЛ-5, РЕФАЛ+, РЕФАЛ-0

РЕФАЛ (РЕкурсивных Функций АЛгоритмический)— один из старейших функциональных языков программирования, ориентированный на символьные вычисления: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.

Отличительной чертой языка является использование сопоставления с образцом и переписывания термов как основного способа определения функций.

Основные принципы

Программа на Рефале может состоять из одного или нескольких модулей (файлов), каждый из которых, в свою очередь, состоит из функций.

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

Выражения языка Рефал представляют собой последовательности термов, в качестве которых могут выступать:

  • обыкновенные символы (буквы, цифры ит.д.), которые в зависимости от диалекта требуется или не требуется заключать в апострофы или кавычки
  • символы-метки (идентификаторы, конкретная запись которых варьируется в зависимости от диалекта языка; так, в Рефале-5 идентификатором может служить произвольная последовательность латинских букв и цифр, начинающаяся с буквы)
  • макроцифры— цифровая запись неотрицательных целых чисел, не превышающих предельное значение
  • числа с плавающей точкой
  • Рефал-переменные одного из нескольких предопределённых типов
  • произвольное выражение, заключённое в круглые скобки (в документации по Рефалу такой терм называется выражением в структурных скобках)
  • произвольное выражение, заключённое в «угловые» скобки и означающее вызов функции (такой терм называется активным выражением)

В зависимости от ситуации на выражение могут быть наложены ограничения; так, в образцах запрещено использовать выражения, содержащие угловые скобки, а в поле зрения Рефал-машины не могут присутствовать переменные.

Рефал-переменные используются в образцах и в зависимости от своего типа могут сопоставляться одному символу (то есть любому терму, кроме выражения в структурных скобках), одному терму (произвольному), либо произвольному выражению (то есть последовательности термов произвольной длины). Соответствующие типы переменных называются S-переменными, T-переменными и E-переменными. В диалекте Рефал-2 поддерживались ещё и V-переменные, сопоставляемые произвольному непустому выражению; в современных диалектах такие переменные не поддерживаются.

Семантика языка Рефал описывается в терминах виртуальной машины, называемой «рефал-машина» или «рефал-автомат». Машина имеет поле зрения, в котором может находиться произвольное рефал-выражение, не содержащее рефал-переменных.

Выполнение программы состоит из шагов рефал-автомата, на каждом из которых выполняется применение функции к выражению. Для этого рефал-машина отыскивает в своём поле зрения самое левое из самых внутренних активных выражений; иначе говоря, отыскиваются парные угловые скобки, не содержащие других угловых скобок, а если таких пар имеется несколько, выбирается та из них, которая текстуально в поле зрения находится левее остальных. Первый терм выражения, заключённого в угловые скобки, должен представлять собой символ-метку, служащую именем функции; оставшаяся часть выражения используется как аргумент функции.

Как было сказано выше, среди предложений, составляющих функцию, находится первое такое, образец которого можно сопоставить с аргументом функции; в ходе сопоставления приписываются значения переменным, содержащимся в образце. Затем шаблон, взятый из того же предложения, берётся за основу для формирования результата вычисления функции; попросту говоря, результатом объявляется выражение, полученное из шаблона заменой переменных на их значения. Необходимо отметить, что шаблон может содержать только переменные, имеющиеся в образце; таким образом, все переменные, входящие в шаблон, окажутся при формировании результата заменены на соответствующие выражения, и результат уже содержать переменные не будет. С другой стороны, шаблон вполне может содержать выражения в угловых скобках.

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

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

Пример исполнения

Рассмотрим простейший пример выполнения программы на Рефале. Пусть дана следующая функция:

Эта функция анализирует выражение и возвращает в качестве результата символ-метку True , если выражение является палиндромом, и False в противном случае. Функция имеет имя Palindrom . Поясним, что s.1 — это переменная S-типа, e.1 и e.2 — переменные E-типа. Таким образом, тело функции состоит из четырёх предложений, первое из которых сработает, если аргумент функции представляет собой выражение, начинающееся и заканчивающееся одним и тем же символом; второе будет использоваться, если аргумент состоит ровно из одного символа; третье задействуется для пустого аргумента и, наконец, четвёртое подойдёт для всех остальных случаев.

Отметим, что шаблон в первом предложении содержит активное выражение, представляющее собой рекурсивный вызов функции Palindrom . Это отражает тот факт, что, если первый и последний символы совпали, их можно отбросить и проверить на палиндромичность остаток выражения.

Пусть в поле зрения рефал-автомата оказалось следующее активное выражение:

Тогда выполнение будет состоять из трёх шагов, после которых в поле зрения будут находиться следующие выражения:

На первых двух шагах использовалось первое предложение, на последнем шаге— второе. Поскольку после третьего шага поле зрения больше не содержит угловых скобок, работа рефал-автомата на этом завершается.

История

Первая версия РЕФАЛа была создана в 1966году Валентином Турчиным в качестве метаязыка для описания семантики других языков. Впоследствии, в результате появления достаточно эффективных реализаций на ЭВМ, он стал находить практическое использование в качестве языка программирования. [источникнеуказан655дней]

В настоящее время основными диалектами языка являются РЕФАЛ-2 (1970-е), РЕФАЛ-5 (1985) и РЕФАЛ+ (1990), отличающиеся друг от друга деталями синтаксиса и набором «дополнительных средств», расширяющих первоначальный вариант.

Примеры программ

Следующая программа на диалекте РЕФАЛ-5 обращает и печатает подаваемую на вход строку данных:

Эту же программу можно записать иначе:

Следующая программа на диалекте РЕФАЛ-5 получает на входе строку данных, представляющую собой десятичное представление некоторого натурального числа N, после чего вычисляет и печатает число Фибоначчи с номером N:

Рефал-5λ

Этот раздел представляет собой неформальное введение в Рефал-5λ, учебник, доступный для новичка, даже для новичка в программировании. Более строго и формально язык будет рассмотрен в следующем разделе (справочник).

Термином Базисный Рефал принято называть семантическое подмножество Рефала, в котором предложения функций состоят только из двух частей, переменные могут иметь тип s-, t- или e- (нет, например, спецификаторов РЕФАЛа-2 [7]) и типы символов (symbol) включают в себя только литеральные символы (characters), числа и слова.

Подмножество Базисного Рефала семантическое. Это значит, что конкретная синтаксическая форма рассмотренных конструкций может сильно отличаться в разных диалектах и реализациях (например, синтаксис РЕФАЛа-2 [7] совсем не похож на синтаксис Рефала-5λ), но перечисленные выразительные средства в языке существуют.

Программа Hello, World!

В предыдущей части нам удалось откомпилировать и запустить программу hello.ref , которая распечатала строчку «Hello, World!». Давайте теперь научимся читать и понимать её исходный код.

Внимательные читатели заметили отличия от программы в предыдущей главе: добавились строчки, начинающиеся на /* и заканчивающиеся на */ . Это комментарии — любой текст между /* и */ компилятором игнорируется и используется для пояснения смысла программы читающему её программисту.

В эту программу были добавлены комментарии, просто нумерующие строки (для удобства ссылки на них из текста руководства) и слово /* empty */ , обращающее внимание читателя на то, что в этом месте программы ничего нет. Да, звучит на первый взгляд странно, но вскоре всё станет понятнее.

Комментарии, ограниченные знаками /* и */ , являются многострочными, т.е. */ не обязана находиться в той же строке, что и предшествующая ей /* . Помимо многострочных комментариев также допустимы однострочные — любая строка, начинающаяся со знака (в первой колонке) * , игнорируется компилятором.

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

Но вернёмся к нашей функции.

Любая программа на Рефале-5λ представляет собой набор функций (язык ведь функционального программирования всё-таки). И эта программа не исключение. Здесь определена функция Go . Определение функции записывается как имя функции, за которым следует блок — тело функции, ограниченное фигурными скобками (в строках 1 и 3 соответственно). Имя Go неслучайно: любая программа на Рефале должна содержать единственное определение функции с именем Go либо GO — процесс выполнения программы есть вычисление функции Go (или GO ) с пустым аргументом.

Непонятное $ENTRY перед именем функции будет прояснено в следующих разделах, сейчас нам достаточно знать, что ключевое слово $ENTRY обязано предварять точку входа (entry point) Go или GO в программу.

В строке 2 находится единственное предложение функции Go . Предложение — это правило, определяющее, как построить значение функции на некотором подмножестве её аргументов. Функция в общем случае может состоять из нескольких предложений, каждое из которых завершается знаком ; (точкой с запятой). Точка с запятой в конце последнего предложения может не ставиться.

Любое предложение состоит из двух частей — левой части, образца, описывающей подмножество значений аргумента функции, на котором это предложение применимо, и правой части, результата, описывающей значение функции на этом подмножестве. Левая и правая части разделяются знаком = (равенства).

Примечание. В дальнейшем будет рассматриваться расширенный синтаксис Рефала, в котором синтаксис предложения будет уже сложнее.

В программе hello.ref единственное предложение говорит о том, что оно применимо только для пустого аргумента функции (перед равенством ничего не записано), комментарий /* empty */ подчёркивает этот факт. Правая часть описывает значение функции Go с пустым аргументом как результат вычисления функции Prout , которому в качестве аргумента передаётся последовательность знаков Hello, World! . Вызовы функций на Рефале, в отличие от математической нотации, оформляются при помощи угловых скобок и > (знаков «меньше» и «больше»), при этом имя функции пишется не перед открывающей скобкой, а после неё.

Функция Prout при любом своём аргументе вычисляет «пустоту», однако её выполнение имеет побочный эффект — она распечатывает свой аргумент на экране. Очевидно, ради этого побочного эффекта её и вызывают.

На самом деле, практически все программы на Рефале пишутся ради побочных эффектов. После завершения вычисления функции Go (или GO ), её результат отбрасывается, и программа завершается. Пользователю достаётся лишь то, что было выведено на экран функциями типа Prout , записано в файлы, либо передано «наружу» из процесса вычислений иным путём.


Примечание. Есть исключения из этого правила. Во-первых, это автоматизированные тесты (автотесты) — программы, которые запускают тестируемую функцию, проверяют её результат и завершаются. При успешной проверке программа молча завершается, при неуспешной — аварийно вылетает с ошибкой. Среда запуска тестов умеет различать эти два случая и сообщает пользователю о подобных неуспешных запусках. Другой пример — исследования в области автоматического преобразования и верификации программ, например, при помощи суперкомпиляции. В этом случае пишется какая-нибудь математически интересная функция на Рефале, скармливается инструментальному средству, например, суперкомпилятору РЕФАЛа-5 SCP4 ([1], [2], [3]), после чего изучается результат преобразования или анализа этой функции. Собственно, исследования в области разработки подобных инструментальных средств — это одно из основных применений Рефала на сегодня.

Функция Prout — это одна из функций, входящих в стандартную библиотеку языка, и по умолчанию неявно доступна к использованию в любой программе. В классическом РЕФАЛе-5 она является встроенной, т.е. определённой неявно всегда в любой программе. Рефал-5λ, однако, позволяет писать программы, в которых не используется стандартная библиотека.

Промежуточные выводы — что мы увидели в hello.ref

Давайте подытожим, что мы к этому моменту узнали.

  • В программах можно писать комментарии, которые никак не влияют на выполнение программы и служат лишь для пояснения.
  • Комментарии бывают двух видов: однострочные и многострочные.
  • Однострочный комментарий представляет собой строку, первым символом которой является знак * , а остальные могут быть любыми.
  • Многострочный комментарий может располагаться в любом месте программы, где допустим незначащий пробельный символ. Комментарий начинается знаками /* и заканчивается знаками */ .
  • Программа на Рефале есть набор функций.
  • Выполнение программы начинается с вызова «стартовой» функции Go или GO с пустым аргументом.
  • Перед именем стартовой функции должно располагаться ключевое слово $ENTRY .
  • Функция на Рефале записывается как имя функции, за которым в фигурных скобках следует одно или несколько предложений.
  • Предложение состоит из двух частей: левой части — «образца» и правой части — «результата».
  • Левая часть определяет подмножество значений аргумента, на котором применимо данное предложение.
  • Правая часть определяет, каким способом будет строиться результат вычисления функции на этом подмножестве аргумента.
  • «Пустое значение» записывается пустым местом, обычно в этом месте ставят комментарий /* empty */ или /* пусто */ .
  • Последовательность печатных знаков (characters) записывается в одинарных кавычках: ‘Hello, World!’ .
  • Вызов функции F с некоторым аргументом arg записывается как .

Выполнение программы является вычислением функции Go с пустым аргументом, вызов функции оформляется при помощи угловых скобок, пустое значение записывается пустым местом. Значит, правомерно будет записать, что выполнение программы на Рефале эквивалентно вызову функции или . В первом случае мы между именем функции Go и закрывающей скобкой > мы не написали ничего (приписали вплотную одно к другому). Во втором случае для наглядности воткнули комментарий. Обычно вызов функции с пустым аргументом пишут без комментария внутри.

Другие примеры программ

Программы из нескольких предложений

Прежде чем перейти к рассмотрению других примеров, нужно дать пояснения по синтаксису, не отражённые в листинге hello.ref .

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

Во-вторых, каждый из знаков внутри одинарных кавычек является самостоятельным, следующие записи эквивалентны: ‘Hello’ , ‘Hel’ ‘lo’ , ‘H’ ‘e’ ‘l’ ‘l’ ‘o’ .

В-третьих, именем функции может быть любая последовательность букв, цифр, знаков _ («прочерк») и — («дефис»), начинающаяся с прочерка или буквы. Например, Go , Hello , A-plus-B , _remove_file , ANSWER_42 . Строчные и прописные буквы различаются, т.е. имена hello , Hello и HELLO различные.

Примечание. Классическая реализация РЕФАЛа-5 не поддерживает имена, которые начинаются на прочерк.

Пример 1. Напишем функцию, которая складывает две двоичные цифры.

Левые части предложений можно было записать и слитно, например ’00’ , на работу программы это бы никак не повлияло — они написаны раздельно для удобочитаемости.

Нетрудно понять, что первое предложение применимо, когда аргумент функции — ’00’ , т.е. результатом вызова будет ‘0’ , со вторым и четвёртым предложением тоже всё понятно.

Третье предложение говорит о том, что результат вызова функции точно такой же, как и , от перемены мест слагаемых сумма не меняется. Можно было написать в правой части сразу ‘1’ , вызов функции был добавлен в правую часть ради демонстрации самого вызова.

Областью определения этой функции будут пары символов ’00’ , ’01’ , ’10’ , ’11’ . При попытке вызвать эту функцию с аргументом вне области определения программа аварийно завершится (т.н. ошибка невозможности отождествления, «recognition impossible»).

Пример 2. Напишем функцию, которая вычитает две двоичные цифры.

Здесь всё аналогично, кроме последнего предложения. В правой части четвёртого предложения записан символ минуса, вслед за которым находится вызов функции BinSub . Что это значит? Это значит, что результатом вызова функции будет знак ‘-‘ , за которым следует результат вычисления — ‘1’ . Т.е. результат будет равен ‘-‘ ‘1’ или ‘-1’ .

Пример 3. Напишем функцию, которая проверяет равенство двух двоичных чисел, не больших 2 (т.е. 10 в двоичной записи) и не меньших -1. Будем считать, что оба числа в аргументе функции разделяются знаком ‘=’ .

Да, скучно. Да, длинно. Позже мы увидим, как можно сократить эту запись.

Пример 4. Напишем функцию Go , демонстрирующую коммутативность сложения и некоммутативность вычитания.

Функции BinAdd , BinSub , IsEqual и Go можно положить в один файл (назовём его binmath-1.ref ) и откомпилировать следующей командой:

то получится исполнимый файл binmath-1.exe (или binmath-1 на unix-like), который при запуске напечатает

В этом разделе мы рассмотрели функции, у которых в левых частях предложений записаны различные, но фиксированные значения. И очевидно, областями определения таких функций являются все явно перечисленные значения образцов. Понятно, что для написания нетривиальных программ этого чертовски мало: можно задать только функции с конечной областью определения и для каждого из значений аргумента придётся написать предложение. Это привело к тому, что даже такая простая функция, как IsEqual потребовала целых 16 предложений.

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

У внимательного читателя наверняка возник вопрос: а что будет, если несколько предложений будут иметь одинаковые левые части? Не будет ли это синтаксической ошибкой? Ответ: не будет. Если аргумент функции таков, что становятся применимыми несколько предложений, то приоритет имеет то, которое написано выше. Например, результатом вызова будет ‘1’ , а не ‘3’ :

Первое предложение имеет приоритет над третьим.

Переменные

Выше было сказано, что левая часть определяет подмножество значений аргумента, при котором применимо это предложение. Но пока мы рассмотрели только случаи подмножеств, состоящих из одного единственного элемента.

Рефал позволяет записывать в левых частях выражения (точное определение понятия «выражение» будет дано позже), которые, помимо явно заданных символов, содержат неизвестные произвольные фрагменты — переменные.

Множества значений, которые могут принимать переменные, определяются типом переменной. В Рефале есть три типа переменных: s-, t- и e-переменные. t-переменные мы рассмотрим позже, когда будем изучать структурные скобки.

Значением s-переменной или переменной символа может быть любой одиночный символ (symbol). Значением e-переменной или переменной выражения может быть любой фрагмент аргумента функции, в том числе пустой (не совсем любой, на самом деле, но об этом позже).

Переменная записывается как признак типа ( s , t , e ), за которой следует знак . («точка») и имя переменной — некоторая последовательность букв и цифр. Имя переменной часто называют индексом переменной.

Если в выражении переменная встречается несколько раз, то она называется повторной, все её вхождения должны иметь одинаковое значение.

Рассмотрим некоторые выражения с переменными:

  • s.1 s.2 s.3 — три любых символа, например ‘ABC’ , ‘999’ , ‘@#$’ .
  • s.A s.A s.A — три любых одинаковых, символа, например ‘666’ , ‘www’ .
  • s.Edge s.Middle s.Edge — три любых символа, причём первый и последний должны совпадать. Например: ‘@$@’ , ‘kek’ , ‘^_^’ .
  • s.first e.middle s.last — любое выражение, содержащее как минимум два символа. Например: ‘Hello’ , ’10’ , ‘0_o’ .
  • s.EDGE e.CENTER s.EDGE — любое выражение как минимум из двух символов, начинающееся и заканчивающееся на одинаковый символ. Например: ‘++’ , ‘LOOOL’ , ‘revolver’ .
  • ‘(‘ e.Inner ‘)’ — выражение, начинающееся и заканчивающееся на скобку. Примеры: ‘()’ , ‘()()’ , ‘(ok)’ .
  • e.Key ‘=’ e.Value — выражение, содержащее хотя бы один знак равенства. Например: ‘=’ , ‘x=1’ , ‘-1=10’ , ‘A=B==C=D’ .
  • e.Eq e.Eq — выражение чётной длины, которое можно разбить на две одинаковые половинки: ‘ABCABC’ , ‘8888’ , пустое выражение (да, его тоже можно разбить на два пустых).

Переменные могут встречаться как в левой части предложения, так и в правой. При этом в правой части предложения могут использоваться только те переменные, которые есть в левой.

Теперь мы должны уточнить процесс выполнения функции на Рефале.

  1. Выбирается предложение, из левой части которого можно получить аргумент функции путём замены переменных в ней на некоторые значения. Если таких предложений несколько, выбирается с наименьшим номером. Если такого предложения не нашлось, то программа завершается с ошибкой отождествления (recognition impossible).
  2. Фиксируются значения переменных, при подстановке которых в левую часть выбранного предложения, та обращается в аргумент функции. Если таких наборов значений переменных (подстановок) несколько, то фиксируется та из них, при которой самая левая e-переменная принимает кратчайшее значение, если это не разрешает неоднозначности, то рассматривается следующая e-переменная и т.д. (в следующем разделе мы рассмотрим этот процесс подробнее).
  3. В правой части выбранного предложения заменяются переменные на их значения. После чего вычисляются функции в правой части.

В следующем разделе этот процесс будет рассмотрен более детально и формально.

Пример 5. Теперь, вооружённые новым знанием, мы можем упростить функцию IsEqual :

Видно, что, во-первых, функция сократилась с 16 предложений до двух, во-вторых, её область определения существенно расширилась — она принимает не только пары двоичных чисел, но и вообще любые выражения, содержащие знак ‘=’ .

Первое предложение функции применимо к любым выражениям, которые содержат хотя бы один знак равенства, и при этом их можно разбить так, что часть, предшествующая знаку ‘=’ , будет совпадать со следующей за ней.

Второе предложение применимо к любому аргументу, содержащему знак равенства.

Очевидно, что для аргументов вида ‘ab=ab’ применимы оба предложения, первое, поскольку до и после знака ‘=’ находятся одинаковые выражения, второе, потому что просто содержит знак равенства. Но, как было сказано выше, предшествующие предложения имеют приоритет над последующими, поэтому первое предложение будет обрабатывать только случаи равных «половинок», а второму будут доставаться все остальные (неравные).

Если оба предложения поменять местами, то результатом функции (на своей области определения) всегда будет ‘False’ .

Пример 6. Функция IsPalindrome , проверяющая, является ли аргумент функции палиндромом.

Определение этой функции можно прочитать так. Строка из одного символа является палиндромом. Пустая строка тоже является палиндромом. Строка, которая начинается и заканчивается на один и тот же символ, является палиндромом, если «средняя» часть строки тоже является палиндромом. Любая другая строка палиндромом не является.

Вообще, определения функций на ФЯ часто могут читаться как математические определения.

Пример 7. Напишем функцию сложения двух двоичных чисел произвольной длины. Функции на Рефале принимают один аргумент, а здесь мы хотим передать два. В первом варианте функции сложения мы избежали этого затруднения, передавая в функцию два символа. Теперь нам надо передать два выражения произвольной длины. Каждый из аргументов может состоять только из знаков ‘0’ и ‘1’ , поэтому можно между ними поместить любой символ, кроме нуля и единицы — по нему можно будет понять, где кончается один аргумент и начинается другой. Будем использовать символ ‘+’ для наглядности.

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

Нетрудно заметить, что функция реализует сложение двух двоичных чисел в столбик. Если последние цифры обоих чисел — ‘1’ и ‘1’ , то происходит перенос в следующий разряд — эта дополнительная единица прибавляется к первому аргументу.

Промежуточные выводы

  • В левых и правых частях предложения могут находиться переменные — фрагменты выражений, которые могут заменяться на произвольные значения в соответствии с их типом.
  • S-переменные могут заменяться на любой символ.
  • E-переменные могут заменяться на произвольное выражение.
  • Синтаксис имён переменных: s.varname , e.ab123 , s.123ab .
  • Выполняется то предложение в функции, для левой части которого можно подобрать такую подстановку значений переменных, которая преобразует левую часть в аргумент функции.
  • Та же подстановка производится и в правую часть предложения.

Структурные скобки

Чисто математически изученного подмножества Рефала достаточно для записи любого сколь угодно сложного алгоритма (см. [4, лекция № 6]). Но на практике этого мало: изученные средства позволяют работать только с «плоскими» строками символов, тогда как многие нетривиальные алгоритмы требуют уже иерархически организованных данных.

Что такое иерархия данных? Это возможность работать с некоторым фрагментом данных, как с одним объектом, абстрагируясь от его внутренней сложной структуры. Например, мы можем работать с текстовым документом как с файлом: перемещать его из папки в папку, копировать, стирать, и при этом не заботиться о том, что внутри него может находиться текст, таблицы, картинки и т.д. На определённом уровне иерархии нас это не интересует.

Для того, чтобы в Рефале с выражением работать как с единым объектом, его заключают в круглые скобки, которые называют структурными скобками. Такой объект, его называют скобочный терм, сам может быть частью другого выражения, которое, в свою очередь, тоже может быть заключено в круглые скобки. Так в Рефале строятся иерархические вложенные данные. Символы (symbols), которые мы рассматривали до этого, тоже являются термами. Таким образом, выражение на Рефале состоит из термов, каждый из которых может быть либо символом, либо скобочным термом, который внутри содержит другое выражение на Рефале.

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

Пример 8. Выражение

состоит из 9 термов. Первый терм — скобочный, содержит в себе выражение из трёх термов-символов, следующие три — печатные знаки ‘def’ , следующий — опять скобочный, состоящий из трёх скобочных термов и одного символа, при этом его последний скобочный терм содержит пустое выражение.

В выражении на Рефале скобки должны обязательно образовывать правильную скобочную структуру как в левой, так и в правой части предложений. При этом в правой части предложений круглые и угловые скобки не могут накладываться (overlap) друг на друга.

Уточним наше понимание переменных в свете нового знания.

  • E-переменные могут принимать произвольную последовательность термов, т.е. значением e-переменной может быть только выражение с правильной скобочной структурой.
  • Значением t-переменных (записываются как t.varname ) может быть любой одиночный терм — как символ (symbol), так и выражение в скобках.

Пример 9. Изобразим родословную Пушкина в виде выражения на Рефале. Каждого персонажа родословной мы будем изображать в виде скобочного терма, который содержит имя персонажа и два терма: отец и мать. Причём, если предок известен, он изображается в виде такого же персонажа, если нет — на его месте будет располагаться символ ‘?’ . Таким образом, каждый из персонажей может быть сопоставлен с образцом вида

Собственно, родословная [5, 6]:

Примечание. На самом деле родословная А. С. Пушкина известна гораздо глубже, здесь просто для наглядности были пропущены некоторые предки на разных уровнях иерархии.

Пример 10. Давайте напишем функцию, которая принимает генеалогическое древо и ветвь предка в виде цепочки знаков вида ‘MFFM…’ — где ‘M’ означает мать, ‘F’ — отец и находит соответствующего предка.

Илон Маск рекомендует:  Ctreelistctrl простейший treeview с колонками

Например, ‘F’ — отец, ‘FF’ — дед по отцу, ‘MM’ — бабка по матери, ‘FM’ — бабка по отцу, ‘FMM’ — прабабка по бабке по отцу, пустое выражение — сам персонаж.

Иначе говоря, чтобы по родословной найти какого-то предка по отцу (ветвь начинается с ‘F…’ ), нужно взять родословную отца (поле t.Father ) и поискать предка в ней (отбросив от начала ветви ‘F’ ) — именно это делает первое предложение. Второе предложение аналогично.

Если родословная на некотором этапе неизвестна, то и любой предок будет неизвестен — этот случай обрабатывает третье предложение. Если ветвь пустая (явно указана пустая ветвь или опустошилась за несколько итераций), то корень текущей родословной и есть искомый человек — последнее четвёртое предложение.

Пример 11. Давайте напишем программу, которая распечатывает некоторых предков Пушкина ( pushkin.ref ).

Функция Pushkin состоит из одного предложения — при любом аргументе возвращает константу. Т.е. фактически она и является определением константы. Остальное всё должно быть понятно.

Примечание. Имена предков записаны транслитом — на некоторых операционных системах вывод кириллицы на экран не работает или работает криво. В будущих версиях это будет исправлено.

Для компиляции и запуска программы под Windows введите:

Программа должна распечатать следующее:

Выше мы, когда хотели вызвать функцию с несколькими аргументами, передавали их, разделяя каким-нибудь знаком, который не может встречаться внутри самих аргументов (например, ‘=’ в функции IsEqual или ‘+’ в функции BinAdd ). Более грамотной практикой при передаче нескольких аргументов является их «заворачивание» в скобочные термы. Например, если функция принимает 3 аргумента произвольной длины — обозначим их как e.1 , e.2 , e.3 , — то их можно передать как (e.1) e.2 (e.3) , e.1 (e.2) (e.3) , (e.1) (e.2) e.3 и (e.1) (e.2) (e.3) . Последний вариант, помещение каждого аргумента в скобочный терм, избыточен, но иногда делает программы более понятными. Вообще, если передаётся в функцию N аргументов, то достаточно завернуть в скобки только N−1 аргументов.

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

Функции IsEqual и BinAdd мы можем теперь переписать так:

Другие типы символов: числа

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

Вообще в Рефале символ (symbol) — это объект, который невозможно разложить при помощи образца на более мелкие фрагменты. Помимо символов-литер, в Рефале есть ещё символы-числа и символы-слова. Символы-слова мы рассмотрим в следующем параграфе.

Символ-число или макроцифра (macrodigit) — это число в диапазоне от 0 до 2³²−1, записанное в десятичном виде. Примеры: 1 , 10 , 65536 , 4294967295 (самая большая макроцифра).

Для работы с макроцифрами в Рефале есть встроенные арифметические функции:

  • Add — сложение,
  • Sub — вычитание,
  • Mul — умножение,
  • Div — деление (вычисление частного),
  • Mod — вычисление остатка от деления,
  • Divmod — возвращает и частное, и остаток,
  • Compare — сравнивает два числа,
  • Numb — преобразует цепочку литер в число (в десятичной записи),
  • Symb — преобразует число в цепочку литер (тоже в десятичной записи).


Читателя должно заинтересовать такое странное слово, как «макроцифра». Объясняем: арифметические функции реализуют арифметику произвольной точности (длинную арифметику, arbitrary-precision arithmetic) — работу с числами произвольной длины. И для представления таких чисел используются цепочки макроцифр.

Точно так же, как в обычной десятичной записи, число 1864 означает

в Рефале длинное число, например, 10000000000000000000000 представляется как 542 434162106 2990538752 , что обозначает

т.е. основанием системы счисления является не 10, а 2³². Для записи отрицательных чисел в начале цепочки макроцифр следует поставить литеру ‘-‘ , в начало положительных чисел можно записывать необязательный знак ‘+’ .

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

Функции Add , Sub , Mul , Div , Mod , Divmod и Compare принимают два числа. Если первое число — небольшое положительное (макроцифра), то оно макроцифрой и записывается. Иначе первый аргумент записывается в виде скобочного терма. Второй аргумент пишется вслед за первым.

Функция Divmod возвращает частное в скобках и остаток. Функция Compare возвращает знак разности первого и второго числа, соответственно ‘+’ , ‘0’ или ‘-‘ , когда первое больше, равно или меньше второго.

Функция Numb принимает строку. Если строка начинается с необязательного знака и десятичных цифр, то функция возвращает число, представимое этими цифрами. Иначе (если аргумент не начинается с десятичной записи числа) функция возвращает 0 .

Функция Symb обратна функции Numb — преобразует число в десятичную запись

Пример 12. Некоторые вызовы функций и их результаты рядом:

Пример 13. Функция вычисления факториала. Напомним, что факториал числа N (обозначается N!, читается «эн факториал») — это произведение всех чисел от 0 до N включительно. Т.е. N! = 1×2×…×(N−1)×N. Считается, что 0! = 1.

Можно заметить, что N! = 1×2×…×(N−1)×N = (1×2×…×(N−1))×N = (N−1)!×N. При этом 1! = (1−1)!×1 = 0!×1 = 1×1 = 1. Воспользуемся этим, чтобы написать функцию.

Заметим, что первый аргумент функции Mul мы завернули в скобки, а первый аргумент Sub — нет. Почему? Потому что уже

Т.е. для аргументов, больших 12, факториал уже перестанет влезать в одну макроцифру. У функции Sub первый аргумент всегда влезает в макроцифру, поскольку он изначально задаётся макроцифрой и на каждом шаге рекурсии он только уменьшается. Приведённая выше программа fact.ref напечатает на экране следующее (последняя строка слишком длинная, для удобства чтения разбита на части)

Другие типы символов: слова

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

Например, мы хотим написать функцию, которая читает конфигурационный файл и вызывается таким вот образом:

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

Следовательно, функция нам должна вернуть три разных результата, которые мы должны уметь различить. В первом случае — данные конфигурации. Во втором — признак того, что файла нет. В третьем — сообщение о синтаксической ошибке в файле.

Можно эти случаи просто пронумеровать. В первом случае функция вернёт макроцифру 1 и данные, во втором — только макроцифру 2 и в третьем — число 3 и сообщение об ошибке. Да, результаты функции можно будет различить, но главный недостаток такого решения — числа сами за себя не говорят. Программист будет вынужден помнить, что, например, для этой функции цифра 3 означает синтаксическую ошибку, а 2 — отсутствие файла, и не наоборот. А если таких разных функций много? Придётся учить, что каждое число значит применительно к каждой функции.

Можно возвращать последовательность литер. Например, в первом случае выводить ‘Success’ (e.Configuration) , во втором — ‘File not found’ , в третьем — ‘Syntax error’ (e.ErrorMessage) . Текстовые строки уже говорят сами за себя, понимать программу становится легко. Но у этого решения тоже есть свой недостаток — текстовые строки — выражения произвольной длины, и когда функция возвращает другие данные произвольной длины, например, конфигурацию или сообщение об ошибке, их приходится отделять круглыми скобками. Более того, избыточно передавать пару десятков символов (symbols), когда для различия достаточно одного.

Для различия достаточно одного. Может нам сократить по первой букве? Тогда вместо ‘Success’ (e.Configuration) мы запишем ‘S’ e.Configuration , вместо ‘File not found’ запишем ‘F’ , вместо ‘Syntax error (e.ErrorMessage) запишем ‘S’ e.ErrorMessage . Стоп, стоп, стоп. Чем у нас тогда будет отличаться первый и последний случай? Они оба начинаются на знак ‘S’ , после которого может следовать выражение произвольной длины. Сократить по первой букве не получилось — придётся выбирать какие-то другие буквы. Но тогда всплывёт та же проблема, что и с числами — одиночные буквы плохо сами за себя говорят.

Вот для решения этой проблемы в Рефале существуют символы-слова (символы-идентификаторы, составные символы). Это символы (symbols), сопоставляются с обычной s-переменной, но имеют вид слова без кавычек. Внешний вид идентификатора точно такой же, как у имени функции: он состоит из букв, цифр, прочерков и дефисов, но при этом обязан начинаться с буквы или прочерка. Примеры идентификаторов: Success , FILE_NOT_FOUND , syntax-error , True , False , Error-404-Not-found , o_0 и т.д.

Теперь уже очевидно, что для нашей функции ReadConfig в возвращаемом значении нужно использовать идентификаторы. Например, Success e.Config , FileNotFound и SyntaxError e.Message .

Рефал-5λ, как и классический РЕФАЛ-5, допускает использование произвольных строк символов в качестве идентификаторов. Для этого строку нужно заключить в двойные кавычки: «This is one symbol:-)» . На практике они используются довольно редко, но могут быть полезны, когда хочется использовать в качестве признака-идентификатора комбинацию знаков, которую без кавычек записать нельзя. Например, «*=» , «C++» , «=0?» и т.д. Можно записывать в кавычках слова, которые пишутся и без кавычек тоже — «Success» , «SyntaxError» — они будут идентичны этим же словам без кавычек.

Escape-последовательности

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

Escape-последовательность выглядит как знак \ , за которым следует один или несколько других знаков. Все они вместе образуют одну литеру (если записаны внутри одинарных кавычек), либо один из знаков составного символа. В Рефале-5λ допустимы следующие escape-последовательности:

  • \’ — одинарная кавычка, ‘ ,
  • \» — двойная кавычка, » ,
  • \\ — обратная косая черта, \ ,
  • \n — перевод строки, LF,
  • \r — возврат каретки, CR,
  • \t — знак табуляции,
  • \xHH — символ с кодом HH в шестнадцатеричной записи, например, \x07 — звуковой сигнал, \x0A — перевод строки (то же, что и \n ), поскольку имеет код 10, \x3F — знак вопроса ? ,
  • \ , \> , \( , \) — то же, что и , > , ( , ) — escape-последовательности, поддерживаемые классическим РЕФАЛом-5, поддерживаются и в Рефале-5λ.

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

Пример 13.

  • Запись ‘Abc\ndef\’ghi\\jkl\x6D\x6e’ обозначает последовательность из 17 литер: ‘A’ , ‘b’ , ‘c’ , знак перевода строки, ‘d’ , ‘e’ , ‘f’ , одинарная кавычка, ‘g’ , ‘h’ , ‘i’ , знак обратной косой черты, ‘j’ , ‘k’ , ‘l’ , ‘m’ , ‘n’ (последние два записаны в шестнадцатеричной форме).
  • Запись «Hello, \»World\’!» — это слово, состоящее из 15 знаков. Знак \ перед одинарной кавычкой здесь избыточен, это же слово можно записать как «Hello, \»World’!» или «Hello, \x22World'» .

Абстрактная рефал-машина. Семантика поля зрения

Ранее мы говорили, что функции в правой части предложения после подстановки переменных как-то вычисляются. Теперь пришла пора уточнить, как именно, поскольку без этого невозможно писать эффективные программы и выполнять отладку программ на Рефале-5λ.

Говорят, что программу на Рефале выполняет абстрактная рефал-машина, — воображаемая вычислительная машина, понимающая синтаксис программ на Рефале. У этой машины есть две области памяти: поле программ (program field), хранящее все определения функций программы, и поле зрения (view field), хранящее текущее состояние вычислений. Состояние вычислений описывается в виде активного выражения — выражения языка Рефал, которое содержит скобки активации, но при этом не может содержать переменных.

Рефал-машина выполняет программу по шагам. Каждый шаг — это выполнение следующей последовательности действий.

  1. Рефал-машина находит в поле зрения самую левую пару скобок активации, такой что внутри этого вызова не находится других угловых скобок. Этот участок поля зрения называется первичным активным подвыражением (primary active sub-expression).
  2. Рефал-машина смотрит, что находится справа от левой скобки активации: там должно располагаться имя функции. Если его там нет (язык позволяет написать такую программу), то рефал-машина останавливается с ошибкой «отождествление невозможно» (recognition impossible).
  3. Рефал-машина находит имя функции в поле программ. Функция может быть как написанной на Рефале, так и встроенной. Если функция встроенная, рефал-машина передаёт управление на процедуру в машинном коде, реализующую логику этой функции. Если эта функция написана на Рефале, машина выбирает первое предложение функции.
  4. Если можно подобрать такие значения переменных в левой части текущего предложения, что та обратится в аргумент функции, то выполняется пункт 5. В противном случае выбирается следующее предложение и повторяется пункт 4. Если предложений больше нет, то рефал-машина останавливается с ошибкой «отождествление невозможно».
  5. Найденные значения переменных подставляются в правую часть текущего предложения. Полученное выражение Рефал-машина вставляет в поле зрения на место первичного активного подвыражения.
  6. Если в поле зрения остались скобки активации, то рефал-машина выполняет следующий шаг — возвращается к пункту 1. В противном случае рефал-машина корректно завершается.

Начальным содержимым поля зрения является вызов функции GO с пустым аргументом:

если в программе определена функция GO , либо вызов Go :

если определена функция Go . Если ни той, ни другой функции нет, то программа не запустится.

  1. Классический РЕФАЛ-5 не поддерживает пустые функции, в любой функции должно быть хотя бы одно предложение. Рефал-5λ поддерживает — вызов такой функции приводит к ошибке невозможности отождествления.
  2. Текущая реализация на момент создания программы не может проверить, что функция GO или Go в программе отсутствует. В этом случае будет создана программа, которая при запуске выводит сообщение об ошибке и завершается. Возможно, это будет исправлено в следующих версиях.

Из этого алгоритма можно сделать два важных вывода.

Во-первых, первичным активным подвыражением выбирается самая левая пара скобок активации, не содержащая внутри себя других скобок активации. Из этого следует, что Рефал — аппликативный язык, причём порядок вычисления функций чётко определён: слева-направо. Т.е. если записано несколько вызовов функций в правой части предложения, то они будут вычисляться слева-направо, от самых внутренних к самым внешним. Поэтому мы можем использовать функции с побочным эффектом, (например, Prout ) чётко зная, когда этот побочный эффект будет выполняться.

Во-вторых, из семантики поля зрения непосредственно следует, что Рефал реализует так называемую оптимизацию хвостовой рекурсии.

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

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

Пример 14. Проиллюстрируем это простейшим примером — рассмотрим процесс вычисления функции Fab , заменяющей все литеры ‘a’ на литеры ‘b’ (программа fab-1.ref ):

Начальным содержимым поля зрения будет вызов функции Go :

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

Первичным активным подвыражением здесь будет вызов функции Fab , поскольку он не содержит вложенных скобок активации (вызов Prout содержит внутри себя скобки активации вызова Fab ).

Рефал-машина увидит Fab после и попробует отождествить (match) аргумент ‘abracadabra’ с левой частью первого предложения ‘a’ e.Rest . Отождествление возможно: если вместо e.Rest подставить ‘bracadabra’ , то левая часть превратится в аргумент. Указанную подстановку ( e.Rest → ‘bracadabra’ ) рефал-машина применяет к правой части предложения — получается выражение ‘b’ и заменяет вызов функции на это выражение:

На третьем шаге первичным активным подвыражением опять будет вызов функции Fab . Но левую часть первого предложения отождествить с аргументом невозможно: образец начинается с ‘a’ , но аргумент — с ‘b’ . Выбирается второе предложение. Отождествление возможно: существует подстановка переменных s.Other → ‘b’, e.Rest → ‘racadabra’ . Подстановка применяется к правой части, результат подстановки ( ‘b’ ) подставляется в поле зрения на место первичного активного подвыражения:

Несколько следующих шагов выполняются в том же духе:

На этом этапе рефал-машина выполнит первое предложение функции Fab , подстановка будет интересна тем, что e.Rest получит значение пустого выражения.

Тут тоже рефал-машина будет выполнять функцию Fab , но первое предложение не подходит (невозможно отождествить выражение, которое начинается на ‘a’ , с пустым выражением), второе — тоже (невозможно отождествить выражение, которое начинается на символ с пустым). А вот третье подойдёт — пустая левая часть успешно отождествляется с пустым аргументом. И рефал-машина заменит вызов функции на пустую правую часть третьего предложения:

Теперь уже первичным активным подвыражением будет вызов функции Prout . Рефал-машина заметит, что это встроенная функция и вызовет соответствующую машинную процедуру для вычисления её результата. Машинная процедура напечатает на экране bbrbcbdbbrb и возвратит пустое выражение. На пустое выражение заменится вызов Prout в поле зрения.

Поле зрения станет пустым — рефал-машина корректно остановится.

Хвостовая и нехвостовая рекурсия

При хвостовой рекурсии, как сказано выше, рекурсивный вызов в правой части выполняется последним. Продемонстрируем наглядно, почему это так. Рассмотрим функцию Rec1 , которая осуществляет вызов функции F в правой части и самой себя:

Развитие поля зрения будет выглядеть примерно так:

Видно, что невычисленные вызовы функций нигде не накапливаются. На каждом шаге перед вызовом Rec1 размещается вызов F , который завершается до вызова Rec1 .

Рассмотрим функцию Rec2 , которая незначительно отличается от функции Rec1 :

Здесь наоборот — сначала вызывается Rec2 , потом F . И поле зрения будет развиваться совсем иначе:

Здесь уже накапливаются невычисленные вызовы F , и они накапливаются до тех пор, пока функция Rec2 не перестанет вызывать себя рекурсивно.

Аналогично получается со вложенными вызовами функций. Рекурсия в функции Rec3 хвостовая:

Рекурсия в функции Rec4 не хвостовая:

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

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

Объектные, образцовые, активные и результатные выражения

Прежде чем продолжить изучение Рефала-5λ, необходимо ввести несколько важных определений. Выше мы рассматривали различные типы выражений языка Рефал, которые содержат разные синтаксические конструкции. Теперь пришла пора ввести их строгую классификацию.

  • Объектным выражением (object expression) называется выражение языка Рефал, которое может содержать только символы и круглые скобки. Соответственно, термы, из которых составлено объектное выражение, называются объектными термами (object terms). Аргументом функции может быть только объектное выражение.
  • Активным выражением (active expression) или определённым выражением (ground expression) называется выражение, которое содержит символы, круглые и угловые скобки. Содержимым поля зрения может быть только активное выражение.
  • Образцовым выражением (pattern expression) или образцом (pattern) называется выражение, составленное из символов, структурных скобок и переменных. Левая часть предложения является образцовым выражением.
  • Результатным выражением (result expression) или результатом (result) называется выражение, содержащее символы, круглые и угловые скобки и переменные. Правые части предложений являются результатными выражениями.

Примечание. Также часто используют слово «образец» как синоним «левой части», «результат» — как синоним правой части. Это тоже правильная терминология и по контексту обычно понятно, что имеется ввиду.

Все четыре типа выражений можно изобразить в виде вот такой диаграммы:

Заметим, что объектные и активные выражения существуют только во время выполнения программы — как, соответственно, аргументы функций и содержимое поля зрения (сюда же можно добавить содержимое статических ящиков и копилку, которые будем рассматривать позже). В то время как образцовые и результатные выражения существуют лишь в исходном тексте как левые и правые части предложений. Причиной тому является, очевидно, наличие в них переменных: образцовое выражение есть шаблон, описывающий множество объектных выражений, а результатное — шаблон, по которому строится активное выражение.

Алгоритм сопоставления с образцом и открытые e-переменные

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

Выше принцип сопоставления с образцом был описан в декларативной манере, т.е. было описано, каким требованиям должна удовлетворять подстановка значений переменных в левую часть. Напомним эти требования.

  1. Подстановка переменных в левую часть должна превращать образец в аргумент функции.
  2. Значения, подставляемые вместо переменных, должны соответствовать типам этих переменных. S-, t- и e-переменные могут заменяться только на, соответственно, символы, термы и произвольные выражения.
  3. Если в образце несколько раз встречается переменная с одним и тем же именем, то все её вхождения должны заменяться на одно и то же значение.
  4. Если существует несколько подстановок переменных, соответствующих требованиям 1-3, то выбирается из них та, у которой длина самого левого вхождения e-переменной является кратчайшей. Если это не разрешает неоднозначности, то рассматривается следующая e-переменная и т.д.

Самым интересным требованием тут является последний. Поясним его на примере.

Пример 15. Рассмотрим сопоставление объектного выражения (‘abra’) (‘cadabra’) с образцом (e.L1 s.D e.E1) (e.L2 s.D e.R2) .

Сопоставление возможно, причём можно построить следующие 8 подстановок (пустое выражение будем обозначать как [] ):

Согласно четвёртому пункту будут выбраны те подстановки, у которых самое левое вхождение e-переменной будет кратчайшим. Самая левая e-переменная здесь это e.L1 , кратчайшему её вхождению (пустому выражению) соответствуют первые три подстановки:

Опять неоднозначность. Смотрим на следующую e-переменную. e.R1 во всех трёх случаях имеет одинаковую длину. Смотрим на следующую — e.L2 . Кратчайшей подстановке переменной e.L2 среди этих трёх отвечает первая, где e.L2 → ‘c’ . Таким образом, будет выбрана подстановка

Примечание. Формально, разобранного выше материала достаточно, чтобы писать корректные программы на Рефале. Но мы, тем не менее, рекомендуем дочитать этот параграф до конца. Во-первых, корректные программы — это не всегда эффективные программы, а без понимания механизма сопоставления с образцом эффективные программы писать невозможно. Во-вторых, даётся важное определение понятия открытых переменных, которые часто будут встречаться в последующем изложении.

Но декларативное описание никак не определяет, каким образом будет выбрана подходящая подстановка. И, что ещё хуже, каковы будут временны́е затраты на сопоставление с таким образцом.

Рассмотрим, как в Рефале-5λ осуществляется сопоставление с образцом.

Примечание. В [9, раздел 2.5] описывается алгоритм сопоставления с образцом немножко с другой точки зрения, и, возможно, кому-то он покажется более понятным. При написании руководства я не хотел его дублировать или дословно пересказывать, поэтому дальнейшее изложение построено в терминах трансляции образца в последовательность элементарных команд.


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

Алгоритм порождения императивного кода сопоставления с образцом

Рефал-5λ — это компилятор, который преобразует исходный текст на Рефале в форму, удобную для выполнения машиной — в последовательность интерпретируемых команд, либо в код на C++. В обоих случаях модель вычислений императивная, т.е. описываются не свойства конечного результата, а элементарные шаги, к этому результату приводящие. В данном случае, последовательно выполняя эти шаги, можно вычислить результат сопоставления: найти подстановку значений переменных, удовлетворяющие четырём требованиям выше, либо доказать, что такой подстановки не существует.

Алгоритм, описанный ниже, формирует по заданному образцу последовательность команд сопоставления для некоторого абстрактного исполнителя. Исполнитель рассматривает s- и t-переменные образца как одиночные указатели, e-переменные — как пары указателей, либо указывающих на первый и последний терм выражения, либо одновременно хранящих особое, «нулевое» значение. Помимо переменных, присутствующих в образце, исполнитель пользуется диапазонами — промежуточными рабочими переменными, которые устроены так же, как и e-переменные — в виде пары указателей. Диапазоны мы будем просто нумеровать и обозначать как BN , где N — целое число.

Алгоритм построения при работе будет использовать объекты-указатели, которые будут обозначаться квадратными скобками с индексами: [ N, ] N. Эти указатели могут перемещаться по образцу, перескакивая через его элементы, причём [ N может двигаться только вправо, а ] N — только влево. Два указателя с одинаковым индексом могут аннигилировать — исчезать из образца. Аннигилируют они в двух случаях — когда они непосредственно встречаются, и когда они окружают ещё не сопоставленную e-переменную, такая переменная называется закрытой.

Жёстким элементом называется часть образца, которая имеет известную длину в термах: литеральный символ, любая s- или t-переменная и e-переменная, которая уже получила своё значение, скобочный терм. Жёсткий элемент мы будем обозначать как He .

Входные данные алгоритма: образцовое выражение P .

Выходные данные алгоритма: последовательность команд сопоставления.

Шаг 1. Поместить слева от образца P указатель [ , справа — ] :

Сгенерировать: B0 ← аргумент функции .

Установить переменную NextK ← 1 .

Шаг 2. Если в образце есть указатель [ N, справа от которого есть жёсткий элемент (за исключением скобочного терма), передвинуть указатель за жёсткий элемент:

Сгенерировать: BN → He BN .

Вернуться к шагу 2.

Шаг 3. (Симметричен шагу 2.) Если в образце есть указатель ] N, слева от которого есть жёсткий элемент (за исключением скобочного терма), передвинуть указатель перед жёстким элементом:

Сгенерировать: BN → BN He .

Вернуться к шагу 2.

Шаг 4. Если в образце есть указатель [ N, справа от которого располагается круглая скобка ( , создать пару новых указателей [ K и [ K, где K равно NextK , переместить исходный указатель вправо за соответствующую ) , поместить новые указатели справа от ( и слева от ) соответственно:

Сгенерировать: BN → (BK) BN .

NextK = NextK + 1

Вернуться к шагу 2.

Шаг 5. (Симметричен шагу 4.) Если в образце есть указатель ] N, слева от которого располагается круглая скобка ) , создать пару новых указателей [ K и ] K, где K равно NextK , переместить исходный указатель влево за соответствующую ( , поместить новые указатели справа от ( и слева от ) соответственно

Сгенерировать: BN → BN (BK) .

NextK = NextK + 1

Вернуться к шагу 2.

Шаг 6. Если в образце есть пара указателей, находящихся рядом друг с другом, удалить их (первый случай аннигиляции):

Сгенерировать: BN → [] .

Вернуться к шагу 2.

Шаг 7. Если в образце есть пара указателей, окружающих несвязанную ранее e-переменную, удалить их (второй случай аннигиляции):

Сгенерировать: e.X ← BN .

Повторимся, такая переменная называется закрытой. При выполнении операции BN → e.X переменная получает значение соответствующего диапазона.

Вернуться к шагу 2.

Шаг 8. Найти самый левый указатель [ N, справа от которого располагается несвязанная ранее e-переменная, передвинуть указатель за эту переменную:

Сгенерировать: Loop BN → e.X BN

Здесь формируется уже не одиночная команда сопоставления, а заголовок цикла.

Для каждой пары указателей повторять:

  • Заменить номер N на K, где K — значение переменной NextK .
  • Сгенерировать: BK ← BN .
  • Выполнить: NextK ← NextK + 1 .

Вернуться к шагу 2.

Шаг 9. На данном этапе указатели уже должны закончиться. Завершение работы алгоритма.

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

В случае неудачи управление передаётся на предыдущую команду Loop . Если ранее по тексту нет команды Loop (т.е. если в образце нет открытых e-переменных), то считается, что попытка сопоставления оказалась неудачной.

Команда Loop BN → e.X BN при первом проходе присваивает переменной e.X пустое значение и не меняет BN . При перехвате неудачи сопоставления команда Loop удаляет первый терм из BN и приписывает его в конец e.X — происходит удлинение переменной e.X за счёт BN . Если к тому моменту BN оказался пустым, то операция удлинения оказалась неуспешной — неудача обрабатывается как описано выше.

Стрелки вправо ( ← ) — это присваивания. Они всегда выполняются успешно.

Пример 16. Составим последовательность элементарных команд для образца (e.L1 s.D e.R1) (e.L2 s.D e.R2) .

Инициализируем нулевую пару указателей и переменную NextK :

Генерируем: B0 ← аргумент функции .

Шаги 2 и 3 выполнить не можем. Но можем выполнить шаг 4:

Генерируем: B0 → (B1) B0

Опять не можем выполнить шаги 2 и 3 и можем выполнить шаг 4:

Генерируем: B0 → (B2) B0

Шаги 2, 3, 4 и 5 неприменимы. Выполняем шаг 6 — аннигиляцию пары указателей.

Генерируем: B0 → []

Шаги 2–7 неприменимы. Шаг 8 предписывает передвинуть указатель [ 1 и перенумеровать указатели:

Генерируем: Loop B1 → e.L1 B1

Меняем указатель 1 на 3:

Генерируем: B3 ← B1 .

Меняем указатель 2 на 4:

Генерируем: B4 ← B2 .

Примени́м шаг 2, поскольку s.D — жёсткий элемент.

Генерируем: B3 → s.D B3 . Заметим, что переменная s.D здесь новая.

Шаги 2–6 неприменимы, шаг 7 (аннигиляция указателей вокруг закрытой e-переменной) применим. Выполняем:

Генерируем: e.R1 ← B3 .

Шаги 2–7 недоступны, доступен шаг 8 — цикл удлинения открытой переменной e.L2 . Двигаем указатель и перенумеровываем диапазон:

Генерируем: Loop B4 → e.L2 B4

Меняем указатель 4 на 5:

Генерируем: B5 ← B4 .

Примени́м шаг 2:

Генерируем: B5 → s.D B5 . Переменная s.D здесь повторная, поскольку ранее по тексту она уже отождествлялась.

Аннигилируем указатели вокруг e.R2 (шаг 7):

(e.L1 s.D e.R1) (e.L2 s.D e.R2)

Генерируем: e.R2 ← B5 .

В образце указателей больше не осталось, генерация кода закончена. Получилось:

Выполним сопоставление (‘abra’) (‘cadabra’) : (e.L1 s.D e.R1) (e.L2 s.D e.R2) пользуясь описанным алгоритмом.

Алгоритм успешно отработал. Получили подстановку:

Заметим, ту же самую, что и при декларативном описании.

Пример 17. Будет ли переменная e.X в образце e.X e.Y (e.X) открытой? Построим последовательность команд отождествления.

Шаг 1. Инициализация.

Генерируем: B0 ← аргумент функции .

Окружаем указателями [ , ] образец:

Шаги 2–4 неприменимы. Но можем выполнить шаг 5 (отщепление скобочного терма справа):

Генерируем: B0 → B0 (B1)

Шаги 2–5 неприменимы, примени́м шаг 6 (аннигиляция через закрытую переменную):

Генерируем: e.X ← B1 .

Теперь, внимание, срабатывает шаг 2. Потому что переменная e.X стала повторной, имеет фиксированное значение. Т.е. стала жёстким элементом:

Генерируем: B0 → e.X B0, e.X — повторная

Переменная e.Y закрытая (шаг 6):

Генерируем: e.Y ← B0 .

Указателей не осталось, генерация кода завершена. Получилось:

Переменная e.X не открытая. Она сначала закрытая (в скобках), потом — повторная (в начале).

Простое правило поиска открытых переменных

Чтобы увидеть в образце открытые переменные, можно воспользоваться следующим приёмом. Записываем образец, приписываем в начале и конце знаки @ , подчёркиваем их.


Жёсткими элементами будем считать символы, скобки, s- и t-переменные и повторные e-переменные, одно из вхождений которых уже подчёркнуто.

Затем, пока весь образец не подчёркнут, повторяем:

  • Если подчёркнута одна из круглых скобок, подчёркиваем парную скобку.
  • Если есть неподчёркнутый жёсткий элемент, соседствующий с подчёркнутым текстом, его подчёркиваем.
  • Если есть неподчёркнутая e-переменная, окружённая подчёркнутым текстом, подчёркиваем её — это закрытая переменная.
  • Если есть несколько неподчёркнутых e-переменных, смотрим на самую левую. Эта переменная будет открытой, подчёркиваем её. Всё, что будет подчёркнуто позже, будет сопоставляться в цикле для каждого удлинения этой открытой переменной.

Знаки @ очевидно нужны, чтобы не выделять в особый случай элементы в самом начале и в самом конце образца.

Пример 18. Найдём открытые переменные в образце (e.L1 s.D e.R1) (e.L2 s.D e.R2) .

Открытые переменные — e.L1 и e.L2 .

Пример 19. Найдём открытые переменные в образце e.X e.Y (e.X) :

Открытых переменных нет.

Почему нужно заворачивать аргументы функции в скобки

Вернёмся к примеру с функцией IsEqual . Первоначальный вариант у нас выглядел так:

Во-первых, функция плоха тем, что если e.X или e.Y содержит знак ‘=’ , то она будет работать некорректно. Сравним к примеру ‘a=b=a’ и ‘b’ :

Но, допустим, мы точно знаем, что её аргументы никогда не содержат знака ‘=’ . Запишем императивный код для первого образца:

Операции 4 и 5 будут выполняться последовательно для каждого возможного удлинения открытой переменной e.X . Представьте себе такой вызов:

Переменную e.X придётся удлинить 1000 раз, пока сопоставление в строке 4 не выполнится успешно.

Второй образец также содержит открытую e-переменную и для этого вызова снова будет делать 1000 удлинений e.X .

Если разделять аргументы скобками, то избыточных циклов не возникает.

Код для первого предложения:

Код для второго предложения

Открытых переменных нет.

Можно заметить, что в функции IsEqual одна пара скобок избыточна — аргумент будет правильно разделён на подаргументы, если одну из них стереть:

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

Стоимость различных элементарных операций

Открытые e-переменные — не единственный источник неэффективности. Элементарные операции сопоставления имеют различную стоимость.

Быстро выполняются операции сопоставления с символами, s-переменными, круглыми скобками и новыми t-переменными. Хотелось в этот ряд включить и «сопоставление» с закрытой e-переменной, но она, как мы выяснили, является не сопоставлением, а присваиванием. И она тоже выполняется эффективно.

Медленно выполняются операции сопоставления с повторными e- и t-переменными. Ведь для их сопоставления необходимо проверить равенство их значений, а сами значения могут быть достаточно «тяжёлыми». Допустим, у нас есть функция

Императивный код для первого предложения будет иметь вид

Циклов по открытым переменным нет, в строке 5 имеем элементарную команду отождествления повторной e-переменной.

Пусть функция IsEqual вызывается как

Команда в строке 5 будет сканировать диапазон B2 слева направо. И прежде чем она увидит отличие в 1000-м символе, она убедится в равенстве предыдущих 999 букв ‘a’ .

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

Язык рефал

Дата публикации: 02.07.2001

1
Listing 1. &nbsp>>

Расширенную версию статьи читайте на refal.net/english/xmlref_1.htm

В последние годы стали широко использоваться языки нового типа: языки разметки, такие как HTML и XML. Текст (документ) на таком языке структурирован определенным образом, согласно синтаксису языка, но не является, вообще говоря, описанием алгоритма. Общая черта языков разметки — использование меток ( tag ), что позволяет работать с документом как с древесной структурой. Неалгоритмический характер языков разметки означает, что работа с документом идет согласно алгоритмам, описываемым на другом языке — метаязыке по отношению к языку разметки. Мы будем говорить конкретно об XML , который, по-видимому, используется все шире и приветствуется энтузиастами как чуть ли не провозвестник революции в обмене и обработке информации.

Язык XSL и его расширение XSLT наиболее известен как кандидат на роль метаязыка для XML . Он декларативен. Для его использования в качестве языка программирования необходим интерпретатор. А для его квалифицированного использования надо понимать, как работает интерпретатор. И это далеко не просто.

С точки зрения автора, наилучший выбор для желаемого метаязыка — Рефал [1].

Рефал в сравнении с другими языками

Рефал — функциональный язык, основанный на распознавании по образцу . Это значит, что:

Любые действия в программе представляются как вычисления при вызове некоторой функции.

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

В первые годы после появления Рефала он был единственным языком, сочетавшим эти две черты. В 1980-х годах появилось несколько подобных языков, в частности Haskell и ML . Сравнивая их с Рефалом, мы прежде всего отмечаем, что Рефал является простейшим в этом семействе языков. Одной из целей при создании Рефала было минимизировать список основных понятий, которые пользователь языка должен был понять и запомнить. В частности, переменные в Рефале могут быть только одного из трех фундаментальных типов (см. ниже), и создать новые типы нельзя. Чтобы различать классы значений, можно использовать метки. Так, например, если переменная x принимает значения, описывающие собаку, то она всегда появляется в форме терма ( Sobaka x ), где Sobaka — метка класса. Такой метод не только минимизирует (в определенном смысле) число базисных понятий, но и обладает тем преимуществом, что класс переменной всегда соседствует с самой переменной. Это полезно при обработке выражений и дает возможность легко определять и переопределять классы в динамике.

Наиболее существенное отличие Рефала от всех известных нам функциональных языков — фундаментальный тип данных, используемый для манипулирования символьной информацией. Рефал использует R -выражения, другие языки используют S -выражения, или списки.

Списки были впервые введены в языке Lisp и стали широко использоваться в теории программирования. Список — это слегка ограниченное S -выражение, а S -выражение — это бинарное дерево. Списки языка Lisp , это не совсем те списки, которые мы понимаем интуитивно. Когда мы говорим о списке из трех элементов A, B и C , мы представляем себе выражение вида A-B-C , которое можно считать слева направо или справа налево. Со списками дело обстоит иначе. Их можно читать только слева направо: A ® B ® C . Чтобы достать последний элемент списка, надо достать начальный элемент и пройти весь список. Такая важная структура, как цепочка (строка), по которой можно гулять в двух направлениях, не может быть представлена списками.

В Рефале мы позволяем истинную конкатенацию выражений, которая создает цепочки. Это достигается представлением данных, включающим ссылки и назад, и вперед: A«B«C. Пользователь может воображать данные в компьютере такими, как он видит их на экране или распечатке.

Кроме конкатенаций, Рефал позволяет еще заключение в скобки. Это создает древесные структуры с произвольным числом дочерних узлов. Например, ( A B ( C ) D ) можно интерпретировать как дерево, где корень имеет четыре дочерних узла A, B, ( C ), D ; ( C ) имеет одного потомка С, а A, B, C, D потомков не имеют: это листья.

Синтаксис Рефала чрезвычайно прост. R -выражение определяется следующим образом:

Символ — это элемент структуры, который не может быть разложен на части: лист древесной структуры. Примеры символов: отдельный знак ‘a’, целое число 25, символическое имя quantity .

Терм — это или символ, или выражение в скобках.

Выражение — это цепочка термов, возможно пустая.

Соответственно есть три типа переменных: символьная переменная, имеющая префикс s , например s. 1 или s.tag ; переменная терма с префиксом t , например t.x — переменное выражение; префикс e , например e. 5 , e.x. 1 .

Следует отметить, что скобки в Рефале не являются символами: это лишь специальные знаки, создающие древесную структуру. Для вызова функций используются угловые скобки. Вызов функции F с аргументом Arg записывается в виде F Arg >.

Чтобы показать, как строятся предложения и программы, определим на Рефале функцию Palindrom как предикат, дающий ответ на вопрос, является ли данная строка палиндромом (то есть читается одинаково слева направо и справа налево):

В определении четыре предложения. В первом предложении образец аргумента имеет вид s .1 e . x s .1; если словами: аргумент кончается на ту же букву, что и начинается. В этом случае предикат применяется к внутренней части строки e . x . Заметим, что образец в первом предложении не может быть выражен в языке, основанном на списках. В таком языке аргумент должен быть сперва обращен, а затем его надо сравнить с исходным аргументом. Ясно, что такой алгоритм менее эффективен, чем наш.

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

Отображение XML в R-выражения

Для выделения подструктуры язык XML использует два маркера: tag …> в начале и в конце подструктуры. Здесь tag — цепочка литер, называемая меткой. Многоточие означает, что там может быть расположена некая дополнительная информация. Подструктуры могут конкатенировать и вкладываться.

Тот, кто программирует на Рефале, немедленно узнаёт (и приветствует!) привычную структуру R -выражения, где tag …> играет роль левой, а tag > — правой скобки. Чтобы обрабатывать XML-текст на Рефале, мы прежде всего конвертируем его в R -выражение. Будем называть такое преобразование рефализацией . Эта простая однопроходная процедура, по существу, является синтаксическим разбором (парсированием), ибо R -выражение уже не линейная цепочка, а дерево. Детали этого входного преобразования могут варьироваться в зависимости от предпочтений программиста. Общий принцип таков: выделяя семантически значимые подструктуры, заключаем их в скобки.

В данной работе мы использовали следующие правила преобразований (опуская детали):

превращается в Рефал-терм.

где квадратные скобки указывают, что их содержимое еще подлежит преобразованию. Метки, как tag >, превращаются в R -символы, начинающиеся с заглавной буквы. Цепочки литер заключаются в кавычки.

Список свойств в XML — это цепочка свойств, каждое из которых имеет вид:

где property-name — это символическое имя, а property-value — цепочка литер. В Рефале данное свойство превращается в

В XML цепочка литер входит как есть, без кавычек. В Рефал-выражениях мы заключаем их в кавычки.

В качестве примера возьмем следующий текст в XML , заимствованный из [2] с небольшим упрощением. (см. Listing 1)

Преобразование XML в HTML

Одно из главных приложений преобразования XML -документов, это преобразование XML -документа в HTML -файл для вывода на экран или на печать. В частности, язык XSL возник как средство для решения этой задачи. Мы продолжим наш пример такого преобразования (см. [2]) и покажем, как задача решается на Рефале. Первая часть дела — рефализация XML-документа — уже сделана ( Listing 2). Listing 3 — желаемый результат преобразования, Listing 4 — Рефал-программа, которая его осуществляет.

Рефал-программа устроена просто. На левой стороне предложения — образцы входного XML -документа, на правой стороне — соответствующие им фрагменты создаваемого выходного HTML -документа. В начале процесса аргументом функции Xh , выполняющим преобразования, является R -терм, представляющий весь ввод. Представляя его в виде образца, мы разбиваем его на меньшие части (значения переменных образца), к которым рекурсивно применяется функция Xh . Это процесс, обратный к построению сложных образцов из простых согласно синтаксису рефализированных XML -документов.

Основной синтаксический элемент языка XML представляется R -термом вида ((A *) ?) , где A — метка, * — возможный список свойств, а знак вопроса указывает, что в это место может быть встроена другая подструктура. Термы могут конкатенироваться и вкладываться.

Эти схемы дают представление о том, чего надо ожидать в левых частях предложения.

Рассмотрим первое предложение программы. Метка Recipe относится ко всему документу. По законам языка HTML , документ должен открываться маркером HTML > и закрываться маркером HTML >. Что и сделано в программе.

В левой части второго предложения мы видим не один образец терма, а два. Причина здесь в том, что значение переменной e.name используется не только в выходе от своего терма Name (мы обозначаем термы именем используемой метки, набранным курсивом), но и в выходе от следующего терма Description. Простейший способ решить эту проблему — соединить эти два терма и сразу получить значения обеих переменных e.name и e.descr.

Терм Ingredients печатает « Ingredients » и создает HTML -таблицу, начинающуюся с маркера TABLE …>. За ним следует заголовок таблицы, затем преобразование функцией Xh всего, что осталось (он дается переменной e.on ), и, наконец, закрывающий маркер TABLE >.

Илон Маск рекомендует:  Что такое код ldap_errno

К этому моменту в аргументе функции Xh осталось четыре терма Ingredient, представляющих четыре ряда таблицы. В левой части четвертого предложения отщепляется один такой терм со свободными переменными e.qty, e.unit и e.item. В правой части конструируется соответствующий ряд значений в формате таблицы HTML . Это предложение применяется рекурсивно, отщепляя терм за термом. Когда отщеплять больше нечего, работает последнее предложение, и процесс завершается. Подчеркнем, что программа работает без изменений при любом числе рядов в таблице.

Последняя деталь. От программы требуется, чтобы пользователь мог указать в XML -документе, что тот или иной Ingredient ( Item ) является необязательным. Это должно указываться тем, что в терме Item содержится свойство Optional =”1″, то есть Optional (‘1’) после рефализации. В HTML -файле это должно проявиться приписыванием к имени Ingredient свойства ‘( optional )’.

Мы удовлетворяем это требование ввода в поле свойств терма Item в левой части переменной e.option . Эта переменная зафиксирует, есть ли там свойство или же там пусто. Теперь осталось только приписать в правой части к имени e.item терма Ingredient . Функция Option решает, будет ли это ‘ (optional) ’, или нет.

Утверждается, что Рефал — наиболее подходящий из известных автору языков для обработки документов в формате XML , так как он обладает следующей уникальной комбинацией черт.

Рефал — функциональный язык. Программа на Рефале определяет алгоритм, а выглядит как декларация отношения между элементами ввода и вывода.

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

В отличие от других известных автору функциональных языков, Рефал базируется на R -выражениях (а не S -выражениях) для создания структур данных. Базовая структура данных языка XML является, по существу, частным случаем R -выражений. Этот выбор структур создателями XML , по-видимому, не случаен. R -выражения не только удобны, они привычны каждому, кто изучал алгебру в школе.

Рефал имеет очень короткий список основных понятий и чрезвычайно простой синтаксис. Его легко выучить.

Рефал универсален как язык для обработки информации. Он может использоваться как единственный язык программирования при работе с символьными данными в широком спектре проблем — от простейших подстановок до сложнейших систем искусственного интеллекта.

Я благодарю Андрея Климова, Аркадия Климова и Андрея Чеповского за обсуждение этой работы.

Язык рефал

РЕФАЛ-ТЕХНОЛОГИЯ АНАЛИЗА И ТРАНСЛЯЦИИ

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

легко проектируются синтаксические анализаторы и трансляторы

с одного языка на другой. Однако для практического программиро-

вания нормальные алгоритмы не обладают достаточными вырази-

— не определены переменные типа “символ”;

— не определены строчные переменные;

— не определены имена переменных и идентификаторы;


— нормальные алгоритмы неэффективны, так как на каждом

шагу требуют просмотра всего поля зрения, а не ее активной части;

— отсутствует операция присвоения;

— отсутствуют операторы ввода-вывода и обращения к файлам.

Эти недостатки преодолены в языке практического программирования РЕФАЛ, созданного в России в 1962 году (см. в [18]).

Язык Рефал является эффективным орудием разработки систем анализа программ и их трансляции, а также удобен в качестве метаязыка для макропрограммирования. Язык Рефал существует в нескольких полных вариантах и в урезанном виде (для преподавания).

Опишем специальный учебный язык Мини-Рефал,

используемый в Московском институте электроники и математики.

АЛГОРИТМИЧЕСКИЙ ЯЗЫК МИНИ-РЕФАЛ
Это язык алгоритмов, представленных в виде упорядоченных наборов обобщенных подстановок (процедур Рефала) со средствами локализации этих подстановок, обогащенный средствами генерации новых подстановок и средствами обмена. Алгоритмы Маркова являются простыми базовыми конструкциями Рефала.

Обычно пользуются Рефал-интерпретатором, который условно

называют Р е ф а л — м а ш и н о й.

Работа Рефал-машины состоит в последовательных преобразованиях символьной строки, занесенной в п о л е з р е н и я

Рефал-машины. Для локализации просмотров на Рефале предусматривается выделение текущей а к т и в н о й о б л а с т и с помощью специальных символов “конкретизации” (будем считать, что они обозначаются квадратными скобками) . Эти символы активизируют выполнение Рефал-преобразования. На каждом шагу работы машины в поле зрения обрабатывается только содержимое самых левых самых внутренних квадратных скобок.
П р и м е р . Cодержимое поля зрения: [Q[Pab]abc[d]].

Сначала обрабатывается цепочка Pab, причем символ может P

играть роль процедуры обработки ab. Образуется новая скобочная структура, и на каждом шагу рассматривается содержание только самых внутренних скобок. Затем выполняется процедура d, а потом над образовавшейся цепочкой выполняется процедура Q.

В полном языке РЕФАЛ, описанном в литературе (см. [18]), предусмотре-ны свободные переменные трех типов: символьные, термы и строки. Термом на Рефале называется либо символ, либо выражение в круглых скобках. Все свободные переменные имеют цифровые номера от 0 до 9. Пусть # означает символ, & означает терм, а @ означает строку. Тогда, например, запись #1@2&3 означает цепочку, состоящую из одного отдельного символа (#1) , одной строки неопределенной длины (@2) и одного терма (&3) . Процедуры Рефала записываются в виде формул (подстановок), состоящих из левой части, разделителя и правой части. Свободные переменные могут входить как в левую часть процедуры, так и в правую. Они получают значение в левой части процедуры и переносят его в правую часть.

Работа Рефал-машины разбивается на шаги. На каждом шагу сверху

вниз просматривается список процедур и отыскивается первая

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

подстановка а#1b ® c применима к слову eakbbee, получается ecbee

подстановка a@1b ® @1 применима к слову aaxbz, получается axcz

подстановка a#1@1® #1a применима к слову abaaa, получается ba

Основные возможности языка Мини-Рефал
Мини-Рефал обеспечивает

— поиск подходящей процедуры слева направо в поле зрения;

— загрузку и использование свободных переменных

символьного и строчного типа;

— выполнение подстановок в цепочках, содержащих свободные

— возможность подгружать Рефал-процедуры из других файлов;

— генерацию новых Pефал-процедур;

— вывод промежуточных результатов на экран;

— ввод промежуточных данных с клавиатуры;

— возможность ввода-вывода в файлы;

— вызов загрузочных модулей (.exe) .
Базовые понятия языка мини-Рефал

п о л е з р е н и я, где хранится обрабатываемая цепочка;

а к т и в н а я о б л а с т ь (в квадратных скобках);

P е ф а л — п р о ц е д у р ы (обобщенные подстановки),

содержащие левую и правую часть с разделителем

с и м в о л ы в поле зрения совпадают с символами ASCII;

у п р а в л я ю щ и е с и м в о л ы Refal-транслятора:

Их коды в шестнадцатеричной системе счисления больше b0

(графические символы); эти символы зарезервированы и не могут служить

объектами обработки. Все остальные символы ASCII доступны для обработки и называются о б ъ е к т н ы м и.
Рефал-программа
Программа на Рефале состоит из множества предложений, представляющих Рефал-процедуры. В Мини-Рефале каждая процедура расположена на отдельной строке. Синтаксис процедуры:

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

Левая часть определяет два режима подстановок. В ней записывается либо о т к р ы т а я строка, либо з а к р ы т а я строка. Открытая строка вызывает на каждом шагу просмотр всей цепочки, записанной в поле зрения и поиск подходящей подцепочки, которая допускает синтаксическое отождествление. Этот режим задействован в нормальных алгоритмах. Например, нормальный алгоритм ab ® cde эквивалентен

Но на Рефале возможны также обобщенные подстановки, например,

@1 и т.д., содержащие свободные переменные.

В режиме открытых строк выполняется просмотр всего поля зрения до

обнаружения первой подходящей подцепочки.

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

Обязателен баланс скобок в левой и правой частях процедур.

Обязателен также баланс квадратных скобок в поле зрения.
П р и м е р ы

1. Рефал-процедура ab

cde перерабатывает содержимое поля зрения

[xaby] в xcdey, а z[xaby]z[s] в zxcdeyz[s]

2. Рефал-процедура [ab]

cde неприменима к [xaby] и к z[xaby]z[s], но перерабатывает z[ab]z в zcdez

Символы @ и # использованы правильно, если после них следует цифра (0 . 9), которая однозначно идентифицирует переменную – символ или строку в пределах одного предложения. Дополнительно допустимо употребление после символа # буквы; в этом случае эта свободная

переменная означает символ из некоторого класса символов, который должен быть определен в Рефал-программе отдельной процедурой. Класс символов, который может определять программист, задается Рефал-процедурой в формате
[ ]=
Например, Рефал-процедура [i]=IJKLMN определяет свободную переменную типа i, которая может принимать значения IJKLNM. Процедура a#ib

c#ie применима к слову aMb и превращает его в cMe.
П р и м е р ы определения классов:

[z]=-+/* — определяет класс арифметических

действий с идентификатором z.

[ ]=0123456789 — означает определение класса цифр

c идентификатором , см.выше

При синтаксическом отождествлении свободные переменные получают значения в левой части процедуры (при первом вхождении), сохраняют их в случае повторения (с тем же номером) и переносят их в правую часть. Свободные переменные строчного типа загружаются до первого символа – ограничителя справа. Поэтому всякая свободная переменная типа «строка»

д о л ж н а б ы т ь о г р а н и ч е н а с п р а в а конкретным символом:

(1) либо объектным символом,

(2) либо свободной переменной, которая

уже получила конкретное значение,

(3) либо управляющей скобкой,

(4) либо цепочкой свободных переменных типа «символ»

c конкретным символом справа.

Таким образом, свободные строки просматриваются слева направо

ОДИН PАЗ до известного (к этому времени) конкретного ограничителя справа. В комбинации @1a@2@1 строка @2 заполняется вплоть до обнаружения того конкретного символа, которым начинается уже присво-енное ранее значение строки @1. В абстрактном выражении после каждой свободной переменной строчного типа должен встретиться хотя бы один ограничитель до следующей свободной переменной (во избежание неопре-деленности).

Рефал-машина работает следующим образом. На каждом шагу

ищется самая левая самая внутренняя пара квадратных скобок, и область

внутри этой скобки активизируется, то есть, поступает в регистр интерпретатора для подбора процедуры. Затем Рефал-процедуры просматриваются сверху вниз до первой подходящей процедуры.

В случае, если процедуры нет, то СТОП и вывод (всего) поля зрения .

Особенности оформления процедур

Невостребованные справа свободные переменные допускаются и

игнорируются, а не определенные слева, но используемые справа свободные

переменные представляют синтаксическую ошибку.

Все различные свободные переменные в каждой процедуре

должны иметь разные номера, иначе – ошибка.

Пустая левая часть команды интерпретатором допускается,

но следует соблюдать внимательность в таком нестандартном случае, так как правая часть будет записываться в поле зрения непосредственно перед самой левой внутренней скобкой [.

Пустая правая часть в команде означает стирание.

В поле зрения допускаются все символы, но трудности по написанию команд, связанных с управляющими символами возлагаются на программиста.

Простые и сложные символы

Рефал предоставляет возможность пользоваться так называемыми «сложными символами», мнемоника которых задается программистом. Эти символы оформляются как слово в угловых скобках.

Например, комбинация рассматривается транслятором как единый неделимый символ.

Транслятор определяет все такие символы один раз вначале и кодирует их графическими символами ASCII.

Допускается определение класса, идентификатором которого будет являться такой «сложный символ».

Пример: процедура [ ]=012345678


Динамическое добавление новой процедуры. Удаление существующей
Мини-Рефал позволяет создавать новые процедуры в процессе работы Рефал-программы . Такой процесс можно назвать динамическим преобразо-ванием или “самопреобразованием” программы. Новые процедуры записы-ваются либо в начало, либо в конец списка процедур. Также допускается удаление уже существующей процедуры в процессе прохождения программы.

С и н т а к с и с д и н а м и ч е с к о г о п р е о б р а з о в а н и я

При возникновении в активной части строки комбинаций

[Uа: … ] содержимое между двоеточием : и скобкой ]

добавляется в начало списка Рефал-процедур;

[Uz: ] содержимое между двоеточием : и скобкой ]

добавляется в начало списка Рефал-процедур;

[Ud: ] содержимое между двоеточием : и скобкой ]

сравнивается с левыми частями (до символа

существующих на данном этапе работы Рефал-машины,

и при совпадении данная процедура удаляется из списка процедур.

Возникает необходимость введения копий служебных символов,

которые резервируются, но только внутри команды U.

Предусмотренные копии управляющих символов :

Вне зависимости от результата выполнения команд динамического

самопреобразования содержимое этих команд удаляется из активной части строки.
П р и м е р ы.

Вызов процедуры [Ua:=cS1de]

порождает новую Рефал-процедуру [a#1b]

c#1de, после чего содержимое

квадратных скобок удаляется.

Выполнение процедуры [Ua:=5] создает Рефал-процедуру [n]

что равносильно присвоению значения 5 переменной n.

В языке мини-Рефал допустима подгрузка Рефал-процедур из

других файлов с помощью команды:
include .
Эта команда записывается с первой позиции.

П р и м е р . Фрагмент программы 1 на Pефале в файле miem.ref:

Фрагмент программы 2 на Рефале

Интернет-технология, Теория управления, [спецкурс]

При запуске этой программы на место первой строки загружается текст

Рефал-программа из файла с именем miem.ref . Далее Рефал-машина обрабатывает расширенный текст в обычном режиме. В этом примере обращение [предметы] вызывает список предметов.

Ввод – вывод на Рефале
В Pефале определены команды стандартного ввода-вывода на стадии

выполнения программы с форматами

При возникновении в активной зоне фразы комбинации [ ] программа останавливается и ждет ввода строки с клавиатуры

( до ) , помещая эту строку на место вызова.

При возникновении в активной части фразы комбинации: [ : … ]

содержимое между знаками : и ] выводится на экран, а затем Рефал-машина работает обычным образом.
Порядок работы интерпретатора («Рефал-машины»)
1. Загрузка поля зрения.

2. Выделение активной области.

3. Поиск подходящей Рефал-процедуры.

4. Загрузка свободных переменных.

5. Подстановка правой части процедуры вместо левой.

6. Возврат на п.1 .

Рефал-интерпретатор языка мини-Рефал предлагается в виде

.exe файла и работает под управлением операционной системы DOS. Этот файл в упакованном виде можно считать в Интернете из сайта [18] в разделе

mini-Refal. Программа на Рефале должна быть записана в стандартный файл prog.ref в том же разделе, что и refal.exe. Обрабатываемая фраза в поле зрения заносится в стандартный файл in.ref в том же разделе.

Рефал-интерпретатор формирует файл out.ref , в который заносится результат выполнения Рефал-программы.

Программирование на Pефале (примеры)
1. Предикат равенства.

[Addh=ddh], [Addh=add], [Aa=aaaaaa], [A1=1]

Файл out.ref: (1) ddh equals ddh., (2) No!, (2) No!, (1) 1 equals 1.
2. Пpоцедуpа S чтения последнего символа перед точкой

3. Рекурсивный алгоритм распознавания арифметических

Здесь B играет роль названия рекурсивной процедуры

Входное слово должно быть заключено в ограничители

4. Присвоение переменной #1 значения @2 путем порождения

[Assign x=abcd]We have: [x]+[x]+[x] We expect: abcd+abcd+abcd

We have: abcd+abcd+abcd We expect: abcd+abcd+abcd
5. Распознавание симметричных слов (процедура MP)

: загружаем слово: @1][@1]

: Пpавильное слово, товаpищи!]

Вход: baabbcbbaab. Выход: OK
6. Рекурсивный вызов (R) произвольной процедуры #1

(вызов процедуры во всех вхождениях)

//здесь буква N выдается процедурой #1 если она неприменима

Применение Рефала в задачах трансляции
Техника преобразования символьных строк на Рефале позволяет упростить процесс разработки синтаксических анализаторов и трансляторов.

Заметим, во-первых, что незаключительные команды конечного автомата по синтаксису и выполнению совпадают текстуально с нормальными алгритмами и Рефал-процедурами. Заключительную команду конечного автомата

следует заменить на подстановку

нормального алгоритма или на Рефал-процедуру

Работу МП-автомата также легко выполнить на Рефале.

Заметим, во-первых, что конфигурации МП-автомата, находящегося в состоянии Si, можно записывать в виде строк вида

Тогда команды МП-автомата во всех допустимых форматах сводятся к подстановкам, которые выполняет нормальный алгоритм или Рефал-машина. Начальная конфигурация должная иметь вид S1

и для нормальных алгоритмов и для алгоритмов на Рефале.

Заключительная команда МП-автомата

записывается в виде #S2# ® · в нормальном алгоритме

Синтаксически управляемая транслирующая машина допускает

достаточно простое программирование на Рефале. Действительно, синтаксический анализ старшинства операторов выполняется на

МП-автомате и программируется, как описано выше. Операционные знаки могут быть объединены в один класс, например, [s]=+*/^() и вписаны в Рефал-процедуру свертки с трансляцией. Пусть начальное присвоение [N]

0 задает начальное значение номера генерируемых переменных. Генерацию нового имени операнда можно описать процедурой

[Ua:=[ N]] [N]
где есть Рефал-процедура инкрементации. Тогда свертка и трансляция двухместных операций может быть записана в виде Рефал-процедуры:

O(var[ N]); #s, @1, @2, var[N],

где #s представляет класс допустимых двухместных операций.

Пример программирования транслирующей машины на Рефале
НА ВХОДЕ

— таблица старшинства операторов;

— размеченная входная фраза с ограничителями ● слева и справа.

Размеченные операнды имеют вид O( );

— Рефал процедура инкрементации: для присвоения на единицу

большего значения N.

МП-АНАЛИЗАТОР СТАРШИНСТВА ОПЕРАТОРОВ

Записывается в виде нормального алгоритма со свободными переменными.

Состояния МП-автомата Si можно кодировать парами символов или составными Рефал-символами

#1S2 // перенос первого символа в стек;

#1O(@3)#2S2 // две команды переноса для #1 #2.

На выходную ленту транслирующей машины последовательно записываются

команды условной двух- или трехадресной машины.

Для одноместных операций

O(var[incN][N])S2; #1, @1, var[N]

// Здесь после точки с запятой записана генерируемая команда условной

// двухадресной машины. Код операции – символ #1

Для двухместных операций


O(var[incN][N])S2; #2, @1, @3, var[N]

// Здесь после точки с запятой записана команда условной

// трехадресной машины с кодом операции #2

У п р а ж н е н и я
1. Разработайте синтаксически управляемый Рефал-транслятор для грамматики старшинства операций
@ ® #A#

B ® B*O | O
Порядок выполнения работы:
1/ составьте таблицу старшинства операций;
2/ напишите текст МП-анализатора старшинства операций на Рефале;
3/ запустите Рефал-машину и добейтесь безошибочного анализа;
4/ опишите Рефал-процедуру генерации команды условной

5/ создайте на Рефале транслятор с языка, порождаемого указанной

грамматикой, и добейтесь его правильной работы;

6/ запишите протокол работы транслирующей машины для фразы
# O+O*O+O#.

2. Разработайте на Рефале АТ-машину для языка, заданного атрибутной

Язык Рефал

Название языка происходит от «РЕкурсивных Функции АЛгоригми-ческий язык». Нас будут также интересовать соображения, которые привели к построению этого языка — эти соображения имеют на наш взгляд весьма общий характер и полезны для лучшего понимания причин возникновения продукционного подхода в программировании.

Разработчики языка Рефал делят алгоритмические языки на две группы. Первую группу образуют языки, которые называются языки операторного, или процедурного типа. Элементарными единицами программы являются здесь операторы, т.е. приказы, выполнение которых сводится к четко оп­ределенному изменению четко определенной части памяти машины. Ти­пичным представителем этой группы является язык машины Поста. Сюда же относятся машинные языки конретных ЭВМ, а также массовые языки программирования типа Фортран, Алгол, ПЛ/1.

Языки второй группы называются языками сентенциального, или дек­ларативного типа (sentence — высказывание, предложение). Программа на таком языке представляется в виде набора предложений (соотношений, правил, формул), которые машина, понимающая данный язык, умеет каким-то образом применять к обрабатываемой информации. Простей­шим примером сентенциального языка, созданного с теоретическими це­лями является язык нормальных алгоритмов Маркова.

Можно указать прообразы указанных типов алгоритмических языков в естественных языках. Для операторных языков это повелительное накло­нение (императив, приказание), для сентенциалышх — изъявительное нак­лонение (описание, повествование). Обращаясь к естественному языку, нетрудно заметить, что «изъявительное наклонение является несравненно более распространенным и образует, в сущности, основу языка, в то время как повелительное наклонение предстает в виде некоторой специальной модификации». Таким образом, можно сделать вывод о том, что «относительный вес изъявительного наклонения является мерой развитос­ти языка».

Язык РЕФАЛ является сентенциальным в своей основе, а вся информа­ция в этом языке представляется в виде правил конкретизации. Каждое правило записывается в виде предложения, которое представляет собой продукцию с определенными синтаксисом и семантикой. Предложения в Рефал-программе отделяются друг от друга знаком § (параграф).

Каждое правило конкретизации определяет раскрытие смысла некото­рого понятия через более элементарные. Операцию конкретизации можно также определить как переход от имени к значению. Введем два знака:

k и ^, которые будем называть конкретизационными скобками, и кото­рые будут содержать объект, подлежащий конкретизации. Так, если х — некоторая переменная, то kx^. (конкретизация х) будет изображать значе­ние этой величины. Другой пример: объект k28 +7^ при правильном опре­делении операции сложения рано или поздно будет заменен на объект 35.

Выполнение конкретизации — переход от имени к значению — объявляется основной и, по существу, единственной операцией в языке Рефал. Эту опера­цию будет выполнять Рефал-машина (имеется в виду машина на логи­ческом уровне, имитируемая соответствующим транслятором на уни­версальной ЭВМ; возможно, разумеется, и построение реальной «физи­ческой» Рефал-машины).

Поскольку правило конкретизации есть указание для замены одного объекта (слова в некотором алфавите) на другой, предложения языка Рефал должны состоять из левой части (заменяемый объект) и правой части (объект, заменяющий левую часть). Для разделения правой и левой части мы будем использовать знак стрелки «à».

Пример 3.5. Предложение, выражающее тот факт, что значение переменной Х есть 137, записывается в виде

Между знаком § и первым знаком k можно вставлять последовательность знаков, которая будет служить номером предложения, или комментарием к нему, например:

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

Пусть программа машины состоит из единственного предложения (ф. 27), а в поле зрения находится выражение kX^. Тогда за один шаг машина заме­нит содержимое поле зрения на 137, после чего она остановится, т. к. знаков конкретизации больше нет, и следовательно, делать ей больше нечего.

Так как Рефал-программа содержит, вообще говоря, набор (последова­тельность) предложений, может оказаться, что для выполнения данной кон­кретизации пригодно не одно, а несколько предложений. Например, в поле памяти, кроме (ф. 27), может находиться еще предложение

Неоднозначность, которая отсюда может возникнуть, устраняется так же, как это принято в нормальных алгоритмах Маркова (читатель, видимо, уже заметил, что Рефал-машина следует идеологии этих алгоритмов): машина просматривает предложения в том порядке, в котором они рас­положены в Рефал-программе, и применяет первое из них, которое окажет­ся подходящим.

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

Пример. Пусть Рефал-программа имеет вид

а поле зрения содержит выражение

На первом шаге замене подлежит подвыражение kX^ — получим в поле зрения kl37 + kY^^. Теперь в первую очередь конкретизируется kY^ — получим в результате применения третьего предложения k137 +2^ и на последнем шаге получим 139, не содержащее символов k. (Разумеется для реального сложения используются соответствующие встроенные функции, а этот пример — лишь простейшая иллюстрация принципов рабо­ты машины [21]).

Чтобы иметь возможность представлять обобщенные предложения, ис­пользуются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В простейшем случае переменные записы­ваются в виде указателя типа (е, t, s) и индекса; например, е1, e2 пере­менные, пробегающие в качестве значений выражения. Выражением в язы­ке Рефал называется последовательность знаков, правильно построенная в соответствеии с синтаксисом языка Рефал. Терм языка Рефал — это либо символ, либо выражение в круглых или конкретизационных скобках. Выражения строятся из термов.

Пример. Предположим, требуется написать программу, кото­рая выполняет раскрытие скобок в алгебраических выражениях, построен­ных из букв с помощью скобок, знаков сложения «+» и умножения»*». Рассмотрим процесс написания такой программы. Если некоторое выра­жение е имеет вид е1 + e1, где е1, e1 выражения, то для раскрытия ско­бок надо: раскрыть скобки в e1, раскрыть скобки в е2, полученные резуль­таты сложить. Эту мысль в компактном, но в то же время и наглядном ви­де выражает предложение:

Если же выражение е имеет вид e1 * e2, то, вообще говоря, необходимо учитывать две возможности:

— хотя бы один из сомножителей есть сумма (например, е = (А + В) *С),

— ни одно из выражений е1 или е2 не представимо в виде суммы (на­пример, е = (А * В) * (С * Л)).

В первом случае надо описать законы дистрибутивности:

Во втором случае по аналогии со сложением имеем

Наконец, осталось выразить возможность «снятия внешних скобок» и условие «терминальности» символов, что определяют предложения:

(буквы не подлежат конкретизации).

Приведенные семь предложений § 2.1 — § 2.7 решают задачу. Рассмот­рим как эта программа обрабатывает выражение

Последовательно получим в результате работы программы (для удобства слева указываем номер правила, которое непосредственно привело к дан­ному выражению):

§2.3 kA *C^ +kB*C^ + k(A+B)*D^,

§2.3 kA *C^ + kB*C^ + kA *D^ + kB*D^.

Далее ограничимся рассмотрением первого слагаемого:

После аналогичной обработки остальных слагаемых получим искомое выражение

Если на вход поступит выражение

то получим последовательно:

Обратите внимание, что если расположить правило § 2.5 перед правила­ми § 2.2 и § 2.3, то придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.

Пролог

Данную главу нельзя рассматривать как учебник по языку Пролог, а только как краткий «ликбез», служащий для иллюстрации принципов продукционного программирования, описанных выше.

РЕФАЛ

РЕФАЛ

зависит от реализации

РЕФАЛ-2, РЕФАЛ-5, РЕФАЛ+, РЕФАЛ-0

РЕФАЛ (РЕкурсивных Функций АЛгоритмический) — один из старейших функциональных языков программирования, ориентированный на символьные вычисления: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.

Отличительной чертой языка является использование сопоставления с образцом и переписывания термов как основного способа определения функций.

Содержание

Основные принципы

Программа на Рефале может состоять из одного или нескольких модулей (файлов), каждый из которых, в свою очередь, состоит из функций.

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

Выражения языка Рефал представляют собой последовательности термов, в качестве которых могут выступать:

  • обыкновенные символы (буквы, цифры и т. д.), которые в зависимости от диалекта требуется или не требуется заключать в апострофы или кавычки
  • символы-метки (идентификаторы, конкретная запись которых варьируется в зависимости от диалекта языка; так, в Рефале-5 идентификатором может служить произвольная последовательность латинских букв и цифр, начинающаяся с буквы)
  • макроцифры — цифровая запись неотрицательных целых чисел, не превышающих предельное значение
  • числа с плавающей точкой
  • Рефал-переменные одного из нескольких предопределённых типов
  • произвольное выражение, заключённое в круглые скобки (в документации по Рефалу такой терм называется выражением в структурных скобках)
  • произвольное выражение, заключённое в «угловые» скобки и означающее вызов функции (такой терм называется активным выражением)

В зависимости от ситуации на выражение могут быть наложены ограничения; так, в образцах запрещено использовать выражения, содержащие угловые скобки, а в поле зрения Рефал-машины не могут присутствовать переменные.

Рефал-переменные используются в образцах и в зависимости от своего типа могут сопоставляться одному символу (то есть любому терму, кроме выражения в структурных скобках), одному терму (произвольному), либо произвольному выражению (то есть последовательности термов произвольной длины). Соответствующие типы переменных называются S-переменными, T-переменными и E-переменными. В диалекте Рефал-2 поддерживались ещё и V-переменные, сопоставляемые произвольному непустому выражению; в современных диалектах такие переменные не поддерживаются.

Семантика языка Рефал описывается в терминах виртуальной машины, называемой «рефал-машина» или «рефал-автомат». Машина имеет поле зрения, в котором может находиться произвольное рефал-выражение, не содержащее рефал-переменных.

Выполнение программы состоит из шагов рефал-автомата, на каждом из которых выполняется применение функции к выражению. Для этого рефал-машина отыскивает в своём поле зрения самое левое из самых внутренних активных выражений; иначе говоря, отыскиваются парные угловые скобки, не содержащие других угловых скобок, а если таких пар имеется несколько, выбирается та из них, которая текстуально в поле зрения находится левее остальных. Первый терм выражения, заключённого в угловые скобки, должен представлять собой символ-метку, служащую именем функции; оставшаяся часть выражения используется как аргумент функции.

Как было сказано выше, среди предложений, составляющих функцию, находится первое такое, образец которого можно сопоставить с аргументом функции; в ходе сопоставления приписываются значения переменным, содержащимся в образце. Затем шаблон, взятый из того же предложения, берётся за основу для формирования результата вычисления функции; попросту говоря, результатом объявляется выражение, полученное из шаблона заменой переменных на их значения. Необходимо отметить, что шаблон может содержать только переменные, имеющиеся в образце; таким образом, все переменные, входящие в шаблон, окажутся при формировании результата заменены на соответствующие выражения, и результат уже содержать переменные не будет. С другой стороны, шаблон вполне может содержать выражения в угловых скобках.

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

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

Пример исполнения

Рассмотрим простейший пример выполнения программы на Рефале. Пусть дана следующая функция:

Эта функция анализирует выражение и возвращает в качестве результата символ-метку True , если выражение является палиндромом, и False в противном случае. Функция имеет имя Palindrom . Поясним, что s.1 — это переменная S-типа, e.1 и e.2 — переменные E-типа. Таким образом, тело функции состоит из четырёх предложений, первое из которых сработает, если аргумент функции представляет собой выражение, начинающееся и заканчивающееся одним и тем же символом; второе будет использоваться, если аргумент состоит ровно из одного символа; третье задействуется для пустого аргумента и, наконец, четвёртое подойдёт для всех остальных случаев.

Отметим, что шаблон в первом предложении содержит активное выражение, представляющее собой рекурсивный вызов функции Palindrom . Это отражает тот факт, что, если первый и последний символы совпали, их можно отбросить и проверить на палиндромичность остаток выражения.

Пусть в поле зрения рефал-автомата оказалось следующее активное выражение:

Тогда выполнение будет состоять из трёх шагов, после которых в поле зрения будут находиться следующие выражения:

На первых двух шагах использовалось первое предложение, на последнем шаге — второе. Поскольку после третьего шага поле зрения больше не содержит угловых скобок, работа рефал-автомата на этом завершается.

История

Первая версия РЕФАЛа была создана в 1966 году Валентином Турчиным в качестве метаязыка для описания семантики других языков. Впоследствии, в результате появления достаточно эффективных реализаций на ЭВМ, он стал находить практическое использование в качестве языка программирования. К:Википедия:Статьи без источников (тип: не указан) [источник не указан 1606 дней]

В настоящее время основными диалектами языка являются РЕФАЛ-2 (1970-е), РЕФАЛ-5 (1985) и РЕФАЛ+ (1990), отличающиеся друг от друга деталями синтаксиса и набором «дополнительных средств», расширяющих первоначальный вариант.

Примеры программ

Следующая программа на диалекте РЕФАЛ-5 обращает и печатает подаваемую на вход строку данных:

Эту же программу можно записать иначе:

Следующая программа на диалекте РЕФАЛ-5 получает на входе строку данных, представляющую собой десятичное представление некоторого натурального числа N, после чего вычисляет и печатает число Фибоначчи с номером N:

Напишите отзыв о статье «РЕФАЛ»

Литература

  • Турчин В. Ф. Алгоритмический язык рекурсивных функций (РЕФАЛ). — М.: ИПМ АН СССР, 1968.
  • Романенко С. А., Турчин В. Ф. РЕФАЛ-компилятор // Труды 2-й Всесоюзной конференции по программированию. — Новосибирск: ВЦ СО АН, 1970.
  • Романенко С. А. Реализация Рефала-2. — М.: ИПМ АН СССР, 1987.
  • Смирнов В.К. [library.keldysh.ru/preprint.asp? >(рус.) // Препринты ИПМ им.М.В.Келдыша. — 2003. — № 99 . — С. 1-21 .
  • Гурин Р.Ф., Романенко С.А. Язык программирования Рефал Плюс. — Переславль: Университет города Переславля, 2006. — 13 с. — ISBN 5-901795-08-3.

Ссылки

  • [www.refal.net/ Сайт Рефал-сообщества]
  • [www.refal.ru/ Содружество «РЕФАЛ/Суперкомпиляция»]
  • [wiki.botik.ru/Refaldevel/ wiki-сайт, посвящённый развитию языка]
  • [ulm.uni.udm.ru/

soft/wiki/doku.php? >

Семантика:
Тип исполнения:
Появился в:
  • Ассемблер
  • BASIC
  • C
  • C++
  • C#
  • COBOL
  • Fortran
  • Java
  • JavaScript (JS)
  • Lisp
  • Pascal
  • Perl
  • PHP
  • Python
  • Ruby
  • Smalltalk
  • Visual Basic .NET (VB.NET)

Отрывок, характеризующий РЕФАЛ

– Подать письмо, просьбу его величеству, – сказал Николай с дрожанием голоса.
– Просьба – к дежурному, пожалуйте сюда (ему указали на дверь внизу). Только не примут.
Услыхав этот равнодушный голос, Ростов испугался того, что он делал; мысль встретить всякую минуту государя так соблазнительна и оттого так страшна была для него, что он готов был бежать, но камер фурьер, встретивший его, отворил ему дверь в дежурную и Ростов вошел.
Невысокий полный человек лет 30, в белых панталонах, ботфортах и в одной, видно только что надетой, батистовой рубашке, стоял в этой комнате; камердинер застегивал ему сзади шитые шелком прекрасные новые помочи, которые почему то заметил Ростов. Человек этот разговаривал с кем то бывшим в другой комнате.
– Bien faite et la beaute du diable, [Хорошо сложена и красота молодости,] – говорил этот человек и увидав Ростова перестал говорить и нахмурился.
– Что вам угодно? Просьба?…
– Qu’est ce que c’est? [Что это?] – спросил кто то из другой комнаты.
– Encore un petitionnaire, [Еще один проситель,] – отвечал человек в помочах.
– Скажите ему, что после. Сейчас выйдет, надо ехать.
– После, после, завтра. Поздно…
Ростов повернулся и хотел выйти, но человек в помочах остановил его.
– От кого? Вы кто?
– От майора Денисова, – отвечал Ростов.
– Вы кто? офицер?
– Поручик, граф Ростов.
– Какая смелость! По команде подайте. А сами идите, идите… – И он стал надевать подаваемый камердинером мундир.
Ростов вышел опять в сени и заметил, что на крыльце было уже много офицеров и генералов в полной парадной форме, мимо которых ему надо было пройти.
Проклиная свою смелость, замирая от мысли, что всякую минуту он может встретить государя и при нем быть осрамлен и выслан под арест, понимая вполне всю неприличность своего поступка и раскаиваясь в нем, Ростов, опустив глаза, пробирался вон из дома, окруженного толпой блестящей свиты, когда чей то знакомый голос окликнул его и чья то рука остановила его.
– Вы, батюшка, что тут делаете во фраке? – спросил его басистый голос.
Это был кавалерийский генерал, в эту кампанию заслуживший особенную милость государя, бывший начальник дивизии, в которой служил Ростов.
Ростов испуганно начал оправдываться, но увидав добродушно шутливое лицо генерала, отойдя к стороне, взволнованным голосом передал ему всё дело, прося заступиться за известного генералу Денисова. Генерал выслушав Ростова серьезно покачал головой.
– Жалко, жалко молодца; давай письмо.
Едва Ростов успел передать письмо и рассказать всё дело Денисова, как с лестницы застучали быстрые шаги со шпорами и генерал, отойдя от него, подвинулся к крыльцу. Господа свиты государя сбежали с лестницы и пошли к лошадям. Берейтор Эне, тот самый, который был в Аустерлице, подвел лошадь государя, и на лестнице послышался легкий скрип шагов, которые сейчас узнал Ростов. Забыв опасность быть узнанным, Ростов подвинулся с несколькими любопытными из жителей к самому крыльцу и опять, после двух лет, он увидал те же обожаемые им черты, то же лицо, тот же взгляд, ту же походку, то же соединение величия и кротости… И чувство восторга и любви к государю с прежнею силою воскресло в душе Ростова. Государь в Преображенском мундире, в белых лосинах и высоких ботфортах, с звездой, которую не знал Ростов (это была legion d’honneur) [звезда почетного легиона] вышел на крыльцо, держа шляпу под рукой и надевая перчатку. Он остановился, оглядываясь и всё освещая вокруг себя своим взглядом. Кое кому из генералов он сказал несколько слов. Он узнал тоже бывшего начальника дивизии Ростова, улыбнулся ему и подозвал его к себе.
Вся свита отступила, и Ростов видел, как генерал этот что то довольно долго говорил государю.
Государь сказал ему несколько слов и сделал шаг, чтобы подойти к лошади. Опять толпа свиты и толпа улицы, в которой был Ростов, придвинулись к государю. Остановившись у лошади и взявшись рукою за седло, государь обратился к кавалерийскому генералу и сказал громко, очевидно с желанием, чтобы все слышали его.
– Не могу, генерал, и потому не могу, что закон сильнее меня, – сказал государь и занес ногу в стремя. Генерал почтительно наклонил голову, государь сел и поехал галопом по улице. Ростов, не помня себя от восторга, с толпою побежал за ним.

На площади куда поехал государь, стояли лицом к лицу справа батальон преображенцев, слева батальон французской гвардии в медвежьих шапках.
В то время как государь подъезжал к одному флангу баталионов, сделавших на караул, к противоположному флангу подскакивала другая толпа всадников и впереди их Ростов узнал Наполеона. Это не мог быть никто другой. Он ехал галопом в маленькой шляпе, с Андреевской лентой через плечо, в раскрытом над белым камзолом синем мундире, на необыкновенно породистой арабской серой лошади, на малиновом, золотом шитом, чепраке. Подъехав к Александру, он приподнял шляпу и при этом движении кавалерийский глаз Ростова не мог не заметить, что Наполеон дурно и не твердо сидел на лошади. Батальоны закричали: Ура и Vive l’Empereur! [Да здравствует Император!] Наполеон что то сказал Александру. Оба императора слезли с лошадей и взяли друг друга за руки. На лице Наполеона была неприятно притворная улыбка. Александр с ласковым выражением что то говорил ему.
Ростов не спуская глаз, несмотря на топтание лошадьми французских жандармов, осаживавших толпу, следил за каждым движением императора Александра и Бонапарте. Его, как неожиданность, поразило то, что Александр держал себя как равный с Бонапарте, и что Бонапарте совершенно свободно, как будто эта близость с государем естественна и привычна ему, как равный, обращался с русским царем.
Александр и Наполеон с длинным хвостом свиты подошли к правому флангу Преображенского батальона, прямо на толпу, которая стояла тут. Толпа очутилась неожиданно так близко к императорам, что Ростову, стоявшему в передних рядах ее, стало страшно, как бы его не узнали.
– Sire, je vous demande la permission de donner la legion d’honneur au plus brave de vos soldats, [Государь, я прошу у вас позволенья дать орден Почетного легиона храбрейшему из ваших солдат,] – сказал резкий, точный голос, договаривающий каждую букву. Это говорил малый ростом Бонапарте, снизу прямо глядя в глаза Александру. Александр внимательно слушал то, что ему говорили, и наклонив голову, приятно улыбнулся.
– A celui qui s’est le plus vaillament conduit dans cette derieniere guerre, [Тому, кто храбрее всех показал себя во время войны,] – прибавил Наполеон, отчеканивая каждый слог, с возмутительным для Ростова спокойствием и уверенностью оглядывая ряды русских, вытянувшихся перед ним солдат, всё держащих на караул и неподвижно глядящих в лицо своего императора.
– Votre majeste me permettra t elle de demander l’avis du colonel? [Ваше Величество позволит ли мне спросить мнение полковника?] – сказал Александр и сделал несколько поспешных шагов к князю Козловскому, командиру батальона. Бонапарте стал между тем снимать перчатку с белой, маленькой руки и разорвав ее, бросил. Адъютант, сзади торопливо бросившись вперед, поднял ее.
– Кому дать? – не громко, по русски спросил император Александр у Козловского.
– Кому прикажете, ваше величество? – Государь недовольно поморщился и, оглянувшись, сказал:
– Да ведь надобно же отвечать ему.
Козловский с решительным видом оглянулся на ряды и в этом взгляде захватил и Ростова.
«Уж не меня ли?» подумал Ростов.
– Лазарев! – нахмурившись прокомандовал полковник; и первый по ранжиру солдат, Лазарев, бойко вышел вперед.
– Куда же ты? Тут стой! – зашептали голоса на Лазарева, не знавшего куда ему итти. Лазарев остановился, испуганно покосившись на полковника, и лицо его дрогнуло, как это бывает с солдатами, вызываемыми перед фронт.
Наполеон чуть поворотил голову назад и отвел назад свою маленькую пухлую ручку, как будто желая взять что то. Лица его свиты, догадавшись в ту же секунду в чем дело, засуетились, зашептались, передавая что то один другому, и паж, тот самый, которого вчера видел Ростов у Бориса, выбежал вперед и почтительно наклонившись над протянутой рукой и не заставив ее дожидаться ни одной секунды, вложил в нее орден на красной ленте. Наполеон, не глядя, сжал два пальца. Орден очутился между ними. Наполеон подошел к Лазареву, который, выкатывая глаза, упорно продолжал смотреть только на своего государя, и оглянулся на императора Александра, показывая этим, что то, что он делал теперь, он делал для своего союзника. Маленькая белая рука с орденом дотронулась до пуговицы солдата Лазарева. Как будто Наполеон знал, что для того, чтобы навсегда этот солдат был счастлив, награжден и отличен от всех в мире, нужно было только, чтобы его, Наполеонова рука, удостоила дотронуться до груди солдата. Наполеон только прило жил крест к груди Лазарева и, пустив руку, обратился к Александру, как будто он знал, что крест должен прилипнуть к груди Лазарева. Крест действительно прилип.
Русские и французские услужливые руки, мгновенно подхватив крест, прицепили его к мундиру. Лазарев мрачно взглянул на маленького человечка, с белыми руками, который что то сделал над ним, и продолжая неподвижно держать на караул, опять прямо стал глядеть в глаза Александру, как будто он спрашивал Александра: всё ли еще ему стоять, или не прикажут ли ему пройтись теперь, или может быть еще что нибудь сделать? Но ему ничего не приказывали, и он довольно долго оставался в этом неподвижном состоянии.
Государи сели верхами и уехали. Преображенцы, расстроивая ряды, перемешались с французскими гвардейцами и сели за столы, приготовленные для них.
Лазарев сидел на почетном месте; его обнимали, поздравляли и жали ему руки русские и французские офицеры. Толпы офицеров и народа подходили, чтобы только посмотреть на Лазарева. Гул говора русского французского и хохота стоял на площади вокруг столов. Два офицера с раскрасневшимися лицами, веселые и счастливые прошли мимо Ростова.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL