2. Пример программы на языке рефал
Символьные преобразования, производимые в рефале, во многом похожи на те алгебраические преобразования, к которым мы все хорошо привыкли.
Например, вычисление выражения (в традиционной, нерефальской записи)
cos( cos( cos( cos ( 1 ))))
распадается на последовательность шагов
cos ( cos ( cos ( cos ( 1 ) ) ) ) = cos ( cos (cos ( 0.540302 ) ) ) = cos ( cos ( 0.857530 ) ) =
= cos ( 0.654290 ) = 0.793480.
Усложним последний пример так: пусть имеется выражение
cos ( cos ( cos ( tg ( 1 ) ) ) )
и определение функции tg
tg (x) = sin (x) / cos (x)
Тогда вычисление выражения распадается на шаги
cos ( cos ( cos ( tg ( 1 ) ) ) ) = cos ( cos ( cos ( sin ( 1 ) / cos ( 1 ) ) ) ) =
= cos (cos (cos ( 0.841471 / cos ( 1 ) ) ) ) =cos ( cos ( cos ( 0.841471 / 0.540302 ) ) ) =
= cos ( cos ( cos ( 1.55741 ) ) ) = cos ( cos ( 0.0133861 ) ) = cos ( 0.99991 ) = 0.540378.
Последний пример во многом показателен для рефала. Имеется выражение, которое надо вычислить, имеется определение функции tg, зависящей от переменной, обозначенной через х. При вычислении переменная х принимает значение 1, выражение tg ( 1 ) заменяется внутри всего выражения на sin ( 1 ) / cos ( 1 ).
Рассмотрим теперь пример программы на языке рефал, которая делает следующее:
- программа вводит одну строку символов, - разбивает ее на слова, - переставляет в обратном порядке буквы в каждом слове, - полученное печатает
Текст этой программы изображен на рис.1 и приведен в example1.ref.
Сделаем некоторые пояснения. Строка
$EXTRN CARD , PROUT ;
описывает внешние (стандартные) функции.
Строки, начинающиеся с символа звездочка, являются коментариями и на работу программы не влияют.
---------------------------------------------------------------------------------------------------------------------
Рис.1. Пример программы на рефале.
* Программа вводит одну строку символов,
* разбивает ее на слова,
* переставляет в обратном порядке буквы в каждом слове,
* полученное печатает
$EXTRN CARD , PROUT ;
$ENTRY Go {
= <Prout <Word <Card >>>;
}
Word {
e.1 ' ' e.2 = <Inverse e.1> ' ' <Word e.2>;
e.1 = <Inverse e.1>;
}
Inverse {
s.a e.1 = <Inverse e.1> s.a;
= ;
}
-------------------------------------------------------------------------------------------------------------------
Строка
$ENTRY Go
показывает, что входной точкой данной программы является функция Go .
Программа состоит из трех функций : Go , Word , Inverse.
Описание функции заключается в фигурные скобки. Описание функции состоит из нескольких предложений, каждое из которых заканчивается символом ";" (точка с запятой).
Описание функции Go состоит из одного предложения, описания функций Word , Inverse - из двух предложений.
Каждое предложение имеет левую и правую части, которые отделяются друг от друга знаком "=". Левая часть предложения описывает аргумент функции, правая - значение функции.
Разберем подробно, как работает эта программа.
Работа любой рефал-программы состоит из последовательности шагов. На каждом шаге происходит некоторое преобразование выражения, находящегося в поле зрения . Преобразование осуществляется в соответствии с описаниями функций, приведенными в программе.
Функции в поле зрения и в программе записываются при помощи знаков "<" и ">". Например, выражение
cos (cos (cos (cos ( 1 ))))
на рефале можно записать так
<COS <COS <COS <COS '1'>>>>
Каждому знаку "<" соответствует свой знак ">", который ограничивает область действия функции. Имена функций задаются составными символами-метками, следующими сразу за знаком "<".
Шаг 1. На первом шаге поле зрения всегда имеет вид
<D >
где D - имя некоторой входной точки. В данном примере начальное поле зрения имеет вид
<Go >
Другими словами, требуется применить функцию Go к пустому выражению.
В левой части предложения для функции Go (перед знаком "=") стоит как раз пустое выражение.
Поэтому на первом шаге работы программы выражение
<Go >
заменяется на правую часть описания функции Go, т.е. на выражение
<Prout <Word <Card >>>
Вспомним аналогичную замену tg ( 1 ) на sin ( 1 ) / cos ( 1 ).
Ha этом первый шаг заканчивается, рефал-машина переходит ко второму шагу.
Шаг 2. Поле зрения имеет вид
<Prout <Word <Card >>>
Ясно, что на втором шаге возможно вычисление лишь функции CARD. Эта функция описана в программе как внешняя и является стандартной функцией рефала.
В результате работы функции CARD выражение
<CARD >
заменяется на символы очередной введенной строки.
Предположим, что мы ввели шесть символов '123 45'
Тогда, после выполнения замены на втором шаге, в поле зрения получится выражение
<Prout <Word '123 45' >>
Шаг 3. На этом шаге возможно вычисление функции Word. Левая часть первого предложения описания функции Word имеет вид
e.1 ' ' e.2
Рефал-машина пытается придать переменным e.1 и e.2 такие значения, чтобы выражение
e.1 ' ' e.2
совпало с аргументом функции Word :
'123 45'
Будут использованы следующие значения переменных
e.1 -> '123' e.2-> '45'
(более подробно алгоритм присваивания значений переменным изложен в п.3).
Правая часть описания функции Word имеет вид
<Inverse e.1> ' ' <Word e.2>
Итак, после выполнения третьего шага поле зрения будет иметь вид
<Prout <Inverse '123' > ' ' <Word '45' > >
Шаг 4. На этом шаге происходит вычисление функции Inverse. Описание функции Inverse состоит из двух предложений. На данном шаге можно применить первое предложение при таких значениях переменных:
s.a -> '1' e.1 -> '23'
B результате выражение
<Inverse '123'>
заменится на выражение
<Inverse '23' > '1'
После шага 4 поле зрения имеет вид
<Prout <Inverse '23'> '1 ' <Word '45'> >
Шаг 5. Вычисление функции Inverse:
s.a -> '2' e.1 -> '3'
Поле зрения после замены имеет вид:
<Prout <Inverse '3'> '21 ' <Word '45'> >
Шаг 6. Вычисление функции <Inverse '3' >
s.a -> '3' e.1 -> Empty (пустое выражение)
Поле зрения после замены имеет вид:
<Prout <Inverse > '321 ' <Word '45'> >
Шаг 7. На этом шаге первое предложение функции Inverse применить нельзя, поэтому рефал-машина пытается применить второе предложение, которое описывает как раз случай пустого аргумента функции Inverse. Результатом применения функции Inverse к пустому выражению является пустое выражение.
Значит, после шага 7, поле зрения имеет вид
<Prout '321 ' <Word '45'> >
Шаг 8. Вычисление функции Word, первое предложение применить нельзя, так как в аргументе нет пробела, поэтому рефал-машина пытается применить второе прдложение функции Word:
e.1 -> '45'
Поле зрения после замены имеет вид:
<Prout '321 ' <Inverse '45'> >
Шаг 9. Вычисление функции Inverse:
s.a -> '4' e.1 -> '5'
Поле зрения после замены имеет вид:
<Prout '321 ' <Inverse '5'> '4' >
Шаг 10. Вычисление функции Inverse:
s.a -> '5' e.1 -> Empty
Поле зрения после замены имеет вид:
<Prout '321 ' <Inverse > '54' >
Шаг 10. Вычисление функции Inverse:
s.a -> '5' e.1 -> Empty
Поле зрения после замены имеет вид:
<Prout '321 ' <Inverse > '54' >
Шаг 11. Вычисление функции Inverse, как на шаге 7 применяется второе предложение:
Поле зрения после замены имеет вид:
<Prout '321 54' >
Шаг 12. Вычисляется функция PROUT, которая описана как внешняя функция. Функция PROUT печатает выражение, к которому она применяется, результатом замены является пустое выражение.
Итак, программа напечатает
321 54
после чего поле зрения будет иметь вид пустого выражения.
Итак, поле зрения не содержит функций, которые надо вычислять, поэтому рефал-машина останавливается в нормальном состоянии.
ЗАДАЧА. Что напечатает программа , если были введены символы :
'123 45'
'123 45 '
' '
ЗАДАЧА. Какие правильные арифметические выражения переходят в правильные при работе программы example1.ref ?