Схема универсальной функции для языка РЕФАЛ-5
, аспирант кафедры информатики СПбГУ, *****@***cc
Аннотация
В данной статье предлагается схема реализации универсальной функции для языка программирования РЕФАЛ-5.
Введение
Универсальная функция, по аналогии с универсальной машиной Тьюринга — функция, которая может заменить собой любую функцию. Получив на вход код функции и входные данные (аргументы функции), она вычисляет ответ, который вычислила бы по входным данным функция, чья программа была дана на вход. Такая универсальная функция свойственна интерпретируемым языкам, таким как PHP, Perl, JavaScript и другие, и как правило называется eval (от англ. evaluate — выполнять). Язык РЕФАЛ-5[1] не является интерпретируемым языком в чистом виде, так как код программы компилируется в код РЕФАЛ-машины и потом выполняется этой машиной, но это не значит, что для него невозможно реализовать такую функцию.
Универсальная функция позволит выполнять динамически генерируемый код, в частности — введенный пользователем, так же универсальная функция позволяет реализовать динамическую загрузку РЕФАЛ-модулей. Кроме своего прямого предназначения — исполнения пользовательского кода, данная функция позволит реализовать такие конструкции, как замыкание, функции высших порядков и анонимные функции, которые, к сожалению не реализованы в наиболее распространенных диалектах языка РЕФАЛ: РЕФАЛ-5 и РЕФАЛ+.
Замыкание — это подпрограмма (процедура или функция), которая использует переменные объявленные вне этой функции, не являющиеся глобальными и не являющихся ее аргументами. Как правило — это функция, которая определена внутри другой функции и использует ее локальные переменные. Стандартными средствами языка РЕФАЛ-5 легко реализовать такую конструкцию невозможно.
Функция высшего порядка — функция, которая принимает в качестве аргумента другую функцию или же возвращает функцию. Этот механизм был реализован в диалекте языка РЕФАЛ, который его авторы назвали РЕФАЛ-7[2]; так же частично данный функционал можно реализовать с помощью Метафункции Mu[3].
Анонимная функция, так же иногда называемая лямбда функцией — функция, которая объявляется в месте использования и не имеет идентификатора, по которому может быть вызвана традиционным способом. Такая функция либо используется на месте либо ссылка на нее присваивается переменной и в дальнейшем вызов этой функции происходит через эту переменную. Создание такой конструкции стандартными средствами языка РЕФАЛ-5 так же сложно.
Реализация
Выбор способа реализации
Есть 2 способа реализовать универсальную функцию: как встроенную функцию РЕФАЛ-машины или же средствами самого языка.
Реализация как встроенная функция РЕФАЛ-машины имеет ряд плюсов:
1. Скорость выполнения — функции выполняемые универсальной функцией будут выполняться почти с такой же скоростью, как если бы это были обычные функции, плюс возможно кешировать такие функции, то есть при повторном вызове не компилировать код заново, а выполнять уже скомпилированный.
2. Простота реализации — РЕФАЛ-машине нужно будет лишь запустить компилятор для переданного кода и поместить функцию в область видимости с каким-нибудь уникальным именем.
Однако есть и минусы:
1. Возможно возникновение проблем с лицензией при изменении оригинального компилятора и РЕФАЛ-машины для языка РЕФАЛ-5.
2. После изменения получится не язык РЕФАЛ-5, а язык РЕФАЛ-5 с дополнениями, который не будет полностью совместим с остальными РЕФАЛ-5 машинами, как следствие для выполнения программ, написанных с использованием дополнений, будет необходимо использовать измененную РЕФАЛ-машину.
Если реализовать универсальную функцию средствами языка РЕФАЛ-5, то плюсом будет то, что программа, использующая данную функцию будет работать на всех РЕФАЛ-машинах языка РЕФАЛ-5. Минусы, по сравнению с реализацией функции внутри РЕФАЛ-машины, следующие:
1. Низкая скорость выполнения — универсальная функция будет вынуждена самостоятельно разбирать переданный код и выполнять его, таким образом будет необходимо реализовать интерпретатор РЕФАЛа.
2. Сложность реализации — будет необходимо реализовать разбор переданного кода и его выполнения, то есть полностью реализовать интерпретатор языка РЕФАЛ-5 на РЕФАЛе, что является трудоемкой задачей.
Не смотря на минусы, был решено реализовать универсальную функцию средствами языка РЕФАЛ-5, так как такой способ позволяет использовать стандартную РЕФАЛ-5 машину.
Разбор кода функции
Для упрощения разбора переданного универсальной функции кода будем считать, что этот код написан на базисном РЕФАЛЕ, то есть в коде отсутствуют условия и вложенные блоки. При необходимости данный функционал можно будет добавить позже. С учетом описанных ограничений переданный код будет выглядеть следующим образом:
{
<Образец_1> = <Действия_1>;
…
<Образец_n> = <Действия_n>;
}
Таким образом:
· Весь код заключен в фигурные скобки.
· Каждое предложение содержит образец и действия, отделенные от образца символом «=», все предложение заканчивается символом «;». Однако стоит учесть, что как образец, так и действия, могут содержать литералы, которые в себе содержат эти символы («=» и «;»).
Для упрощения дальнейшего разбора кода, переданный код преобразуется в поток лексем. Полученный поток лексем разбивается на отдельные предложения (по лексеме «;»), после чего каждое предложение по лексеме «=» разбивается на образец и действия
Выполнение полученного кода
После того, как переданный код разобран необходимо его выполнить. Для этого универсальная функция просматривает образец предложения, в котором могут быть литералы, РЕФАЛ-слова, структурные скобки и переменные. Значения переменных необходимо будет где-то хранить, для этого можно использовать стек, так как программа на языке РЕФАЛ-5 является однопоточной, то можно быть уверенным, что во время выполнения универсальной функции никто не изменит его содержимое. В зависимости от встреченного в образце элемента действия функции могут быть следующими:
1 Встретился литерал или РЕФАЛ-слово — проверяется, совпадает-ли он с литералом (РЕФАЛ-словом) в переданном аргументе, если нет, то просмотр образца прерывается.
2 Встретилась переменная — здесь действия зависят от того, связана-ли переменная и от ее типа:
2.1) Переменная связана — проверить, если значение переменной совпадает с начальными символами аргумента, то продолжать дальше, если нет, то прервать просмотр.
2.2) Переменная не связана — для t и s переменной записать в нее следующий терм или символ соответственно, для e переменной необходимо начать внутренний цикл, который поочередно помещает в эту переменную 0, 1, 2, … и так далее символов, пока весь просмотр образца не завершится успехом или не будут исчерпаны все варианты.
3 Встретились структурные скобки — проверить наличие структурных скобок в аргументе, при их наличии внутри скобок произвести просмотр и сопоставление образца, при отсутствии — прервать просмотр.
4 Обнаружен конец образца — если при этом в аргументе остались символы, то сопоставление завершено не удачно, если не осталось, то сопоставление завершилось удачей.
Если просмотр по вышеописанным правилам заканчивается удачей, то выполняются соответствующие ему действия, если же нет, то функция переходит к следующему образцу, если все образцы просмотрены, то функция завершается неудачей и вызывает ошибку.
При выполнении действий, соответствующих совпавшему образцу для вызова функций используется метафункция Mu.
Заключение
В статье показано как средствами РЕФАЛ-5 реализовать универсальную функцию, способную выполнить переданный ей код на базисном РЕФАЛе.
Литература
1. , , Косовский программирование. Турбо Пролог и Рефал-5 на персональных компьютерах. - СПб.: Издательство СПбУ, 1992.
2. , - Язык Refal с функциями высшего порядка. http://*****/science/refal. pdf [дата просмотра: 02.04.2013].
3. - РЕФАЛ-5. Руководство по программированию и справочник. http:///rf5_frm. htm [дата просмотра: 02.04.2013]
