М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
 Скачать 0.92 Mb.
|
1.3.Функции и предложенияКаждая функция языка Рефал имеет только один аргумент, однако такое ограничение числа аргументов рефал-функций не снижает выразительной и вычислительной мощности языка. Действительно, аргументом функции является объектное выражение – последовательность из нескольких термов, которые могут рассматриваться как последовательные аргументы функции. Обращение к рефал-функции имеет вид функционального терма, причём имя функции стоит внутри функциональных скобок: <имя_функции выражение> Определение рефал-функции состоит из нескольких предложений вида выражение-образец = выражение записываемых последовательно друг за другом по строкам. Каждое предложение включает левую часть (выражение-образец) и правую часть (рефал-выражение общего вида) и описывает правило преобразования и замены: выражение-образец характеризует заменяемое выражение, выражение в правой части определяет результат его замены. Подчеркнём, что в левой части предложения не могут встречаться обращения к функциям. При определении функции, в начале её первого предложения, перед его левой частью записывается имя функции, которое отделяется от последующего выражения-образца одним или несколькими пробелами. Остальные предложения функции не нуждаются в именовании, но их запись на строке должна начинаться хотя бы с одного пробела. Приведём пример функции, описываемой двумя предложениями. В нашем примере функции первое предложение описывает нужное преобразование цепочки символов (замену в ней знака +), а второе соответствует случаю, когда знак + в цепочке символов отсутствует, и она остаётся прежней. * Функция ChangeFirstPlus заменяет в цепочке символов * знак сложения (если он есть) на знак вычитания, * например, 'A+B' будет преобразовано в 'A-B', * а 'XY+Z85' – в 'XY-Z85' ChangeFirstPlus e1 '+' e2 = e1 '-' e2 e1 = e1 Порядок записи предложений в рефал-функции существенен, поскольку каждое предложение может быть применено только тогда, когда не применимы все предыдущие предложения. Выражения-образцы в левой части предложений обычно содержат рефал-переменные. Эти переменные локальны, областью их действия является только то предложение функции, в котором они употребляются. Для нашего примера функции ChangeFirstPlus это означает, что значение переменной e1 при использовании первого предложения может быть отлично от значения этой же переменной при использовании второго предложения. Переменные получают свои значения при проверке применимости предложения, и эти значения используются для выполнения описанной в этом предложении замены. Тем самым, в правой части предложения могут быть использованы только те переменные, которые были использованы в левой части. В общем случае может быть несколько вхождений одной и той же переменной как в левую, так и в правую часть предложения, например: s1 e2 s1 e3 = s1 s1 e2 e3 Все вхождения одной и той же переменной (т.е. переменной с конкретным индексом) в левую и правую часть предложения должны иметь одинаковый признак типа. Тем самым недопустимы предложения вида s1 e1 = e1 или s1 e2 = e1. Приведём пример ещё одной рефал-функции: * Функция ChangeAllPlus заменяет в цепочке символов * все знаки сложения на знаки вычитания, например, * 'A+B+C' будет преобразовано в 'A-B-C' ChangeAllPlus e1 '+' e2 = e1 = e1 В отличие от функции ChangeFirstPlus, функция ChangeAllPlus рекурсивна: в правой части первого предложения стоит обращение к ней самой, рекурсия реализует последовательную, циклическую замену знаков сложения. Этот процесс заканчивается, когда в обрабатываемой цепочке символов не останется знаков +, и применяется второе предложение функции. Использование рекурсии является одной из основных особенностей программирования на языке Рефал. 1.4.Абстрактная Рефал-машинаПрограмма на Рефале представляет собой несколько взаимосвязанных рефал-функций. Выполнение рефал-программы (её операционная семантика) описывается в терминах абстрактной рефал-машины, роль которой на практике играет рефал-интерпретатор. Рефал-машина имеет два запоминающих устройства: поле зрения, в котором содержится обрабатываемое рабочее выражение, поле памяти, в котором хранится рефал-программа. Перед началом работы рефал-машины в поле зрения заносится исходное символьное выражение, точнее, некоторый функциональный терм – обращение к функции, аргументом которой является это исходное выражение, например: Работа рефал-машины разбивается на шаги, на каждом из которых применяется одно рефал-предложение, в результате чего некоторое выражение в поле зрения заменяется на другое. Таким образом, выражение, находящееся в поле зрения, последовательно, по шагам преобразуется. В ходе преобразований в поле зрения может содержаться сколь угодно много функциональных термов, в том числе – вложенных один в другой. По окончании работы в поле зрения должно остаться объектное выражение (выражение без переменных и функциональных термов), рассматриваемое как результат вычислений. Опишем более подробно шаг работы рефал-машины, он включает следующие этапы: Поиск в поле зрения заменяемого выражения – ведущего функционального терма. Ведущим функциональным термом является самый левый функциональный терм, не содержащий внутри себя других функциональных термов. Он представляет собой обращение к некоторой функции: Поиск в поле памяти применимого предложения функции f. Для этого в группе предложений, определяющих функцию f, последовательным перебором, начиная с первого предложения, ищется такое предложение El = Er, левую часть El которого можно синтаксически отождествить с аргументом Еt функционального обращения --------------------------------------------------------------------------------------------- Говорят, что имеет место синтаксическое отождествление выражения-образца El с объектным выражением Et, если переменным из выражения-образца El можно задать такие допустимые значения (согласно их типу), что при подстановке в El этих значений вместо соответствующих переменных получается выражение, в точности совпадающее c объектным выражением Et. --------------------------------------------------------------------------------------------- Если возможно синтаксическое отождествление El c Et, то соответствующее предложение функции f считается применимым. Это предложение вместе с найденными в процессе синтаксического отождествления значениями переменных передаётся на следующий этап. Применение найденного предложения функции f. При этом в поле зрения производится замена найденного на этапе I ведущего функционального терма По окончании этапа III рефал-машина вновь переходит к этапу I и все описанные этапы повторяются, но уже с изменённым содержимым поля зрения. Возможны два случая останова рефал-машины – нормальный и аварийный. Нормальный останов происходит в случае, когда на этапе I в поле зрения нет функциональных термов (функциональных обращений). Рефал-машина сообщает, что вычисление окончено и останавливается, результатом её работы считается выражение, оставшееся в поле зрения. Аварийный останов рефал-машины происходит тогда, когда для найденного на этапе I ведущего функционального терма на этапе II не обнаружено ни одного применимого предложения. В этом случае рефал-машина останавливается с сообщением «отождествление невозможно». Такой останов означает, что либо программа на Рефале, либо исходные данные для неё были заданы неверно. Отметим, что аварийный останов рефал-машины может произойти и в том случае, когда исчерпана память, отводимая под поле зрения, обычно это происходит в результате зацикливания рекурсивных рефал-программ. Рассмотрим примеры работы рефал-машины. Пусть в поле памяти рефал-машины содержится рассмотренное выше описание функции ChangeFirstPlus, а в поле зрения помещено выражение Пусть теперь в поле памяти кроме определения функции ChangeFirstPlus содержатся определения двух функций: Num1 = '731' Num2 = '+1230' В обоих определениях по одному предложению, в левой части каждого предложения – пустое выражение. Пусть в поле зрения рефал-машины помещено выражение Тогда на первом шаге работы рефал-машины ведущим будет терм Теперь ведущим становится терм Это выражение содержит только один функциональный терм, поэтому на следующем шаге применяется первое предложение функции ChangeFirstPlus при e1 ↔ '731', e2 ↔ '1230'. В поле зрения остаётся выражение '731-1230', которое уже не содержит функциональных скобок. Поэтому на четвёртом шаге рефал-машина остановится с результатом '731-1230' в поле зрения. |