6. Стандартные функции
Стандартными функциями называются такие функции, которыми можно пользоваться, не определяя их в рефал-программах. Достаточно описать их в предложениях $EXTRN (да и то не обязательно).
С двумя стандартными функциями CARD, PROUT мы уже познакомились в п.2.
Имеются следующие стандартные функции:
- ввод карт и печать,
- арифметические функции,
- операции с копилкой,
- функции лексического анализа,
- файловый ввод/вывод.
В настоящем пособии мы познакомимся лишь с первыми тремя типами стандартных функций. Полный список стандартных функций рефала-5 приведен в приложении 1.
Будем использовать следующее соглашение: объектные выражения в форматах обращений к функциям обозначаем через е.Expr , e.N1 , e.N2 , e.File-name , s.D и т.д.
Если аргумент функции не соответствует формату обращения к функции, то происходит остановка "отождествление невозможно".
Ввод карт
Формат обращения к функции
<CARD >
Результатом вычисления является введенная строка .
Еще раз подчеркнем, что ни структурных скобок, ни составных символов в поле зрения с помощью функции CARD получить нельзя.
Вывод результата
Печать результатов работы рефал-программы можно осуществлять при помощи функции PRINT.
Формат обращения к функции:
<PRINT e.Expr>
где е.Expr - объектное выражение, которое нужно напечатать.
В результате выполнения функции PRINT выражение е.Expr печатается с новой строки. Если выражение е.Expr не помещается на одной строке, то оно продолжается на следующих строчках.
Результат замены - выражение е.Expr .
Простые символы "(", ")" и структурные скобки при выводе не различаются..
Формат обращения к функции PROUT
<PROUT e.Expr>
Результат замены - пустое выражение. Выражение е.Expr выводится в том же виде, как для функции PRINT.
Операции с копилкой
Кроме поля зрения, в рефал-машине имеется еще одно выражение, которое называется копилкой.
Копилкой удобно пользоваться, когда некоторое выражение требуется в различных частях программы, а передавать это выражение через поле зрения неудобно.
Каждое запомненное в копилке выражение имеет свое имя. Запись выражений в копилку и чтение их оттуда осуществляется по именам выражений. Более того, под одним именем можно записать несколько значений по очереди, а затем по очереди их читать.
Копилка имеет вид:
(е.a '=' е.1) (е.b '=' е.2) ...
где е.a , е.b,... - имена закопанных выражений, е.1, е.2,... - значения, которые закопаны под именами е.a, е.b,... соответственно.
Опишем 4 стандартные функции работы с копилкой:
BR -закопать (BURY),
DG -выкопать (DIG),
CP -скопировать (COPY),
RP -заменить (REPLACE).
B R - закопать.
Формат обращения
<BR e.N ' =' e.0 >
где e.N - произвольное выражение, не содержащее символа "=" на внешнем уровне скобочной структуры, е.0 - произвольное выражение.Копилка е.К преобразуется так:
е.К -> ( e.N' =' e.0 ) e.K
т.е. терм ( e.N '=' e.0 ) добавляется к копилке слева.
Результатом вычисления будет пустое выражение.
D G - выкопать.
Формат обращения
<DG e.N >
где e.N - произвольное выражение.
Функция DG просматривает копилку слева направо в поисках терма ( e.N ' =' e.0) и, если его находит, удаляет его из копилки и выдает е.0 в качестве результата замены.
При этом копилка меняется так:
е.1 ( e.N '=' e.0 ) e.2 -> e.1 e.2
Если же терм не найден, то результатом замены будет пустое выражение, копилка не изменяется.
Отметим, что если в копилке несколько выражений закопаны под одним именем, то при первом обращении к функции DG выкапывается выражение, закопанное последним, при втором - предпоследним и т.д.
С Р - скопировать.
Формат обращения
<СР e.N.>
где e.N - произвольное выражение.
Функция СР работает аналогично функции DG, отличие заключается в том, что найденный терм (e.N '=' e.0.) из копилки не удаляется, а в поле зрения формируется копия выражения e.0.
Отметим, что функция СР работает медленнее функции DG, так как нужно формировать копии выражений. Функции BR и DG работают очень быстро, поскольку выражение е.0 фактически не переписывается из поля зрения в копилку или обратно, изменяются лишь адреса, которые связывают выражения друг с другом.
R P - заменить.
Формат обращения
<RP e.N '=' e.0 >
где e.N, e.0, - те же, что и для функции BR.
Функция RP добавляет в копилку новое выражение и выбрасывает выражение, закопанное под именем e.N в последний раз (если такое выражение есть).
Результат замены - пустое выражение.
Копилка изменяется так:
е.1 (e.N '=' e.P) e.2 -> e.1 (e.N '=' e.0) e.2
З А Д А Ч А. Можно ли функцию RP описать на рефале следующими предложениями?
RP { e.1 '=' e.2 = <DEL <DG e.1>> <BR e.1 '=' e.2 > ; }
DEL { е.1 = ; }
АРИФМЕТИЧЕСКИЕ ФУНКЦИИ.
Стандартные функции ADD, SUB, MUL, DIV , DIVMOD, MOD предназначены для работы с целыми числами, записанными с помощью макроцифр (см.п.1).
ADD - сложение,
SUB - вычитание,
MUL - умножение,
DIV - деление , DIVMOD - деление с остатком , MOD - получение остатка.
Целое число - это непустая последовательность макроцифр, перед которой может стоять знак. Знак - это простой символ "+" или "-". Если знак отсутствует, то подразумевается "+".
Такое представление числа является записью в системе счисления по основанию 2^N , где N - количество двоичных разрядов, отводимых под одну макроцифру. Для рефала-5 N=32.
Например, четыре символа '-' 1 12 3 изображают число -(1 х 2^64 + 12 х 2^32 + 3)
Обращение к функциям ADD, SUB, MUL, DIV, DIVMOD, MOD имеет вид
<D (e.M) e.N>
где D - имя одной из функций, е.М, e.N - целые числа.
Результат вычисления функций ADD, SUB, MUL, DIVMOD, MOD - целое число, являющееся суммой, разностью, произведением, частным или остатком от деления целых чисел е.М и e.N.
Если результат положителен, то знак "+" не ставится, левые нули опускаются. Нулевой результат выдается в виде одной макроцифры 0.
Пример. Функция, вычисляющая факториал неотрицательного числа
Fact {
0 = 1;
е1 = <MUL (e1) <Fact <SUB (e1) 1> >> ;
}
Напишите "по шагам" вычисление рабочего выражения <Fact 4 > . Обратите внимание на порядок вычислений умножений.
Функция DIV выдает результат в виде
(e.Q) e.R
где e.Q - частное, e.R - остаток.
Частное и остаток выдаются без левых нулей и без знака "+" перед положительными числами.
Деление на нуль приводит к остановке "отождествление невозможно".
Деление с остатком производится так: делятся два числа, без учета знаков, а затем частному и остатку приписываются знаки так, чтобы выполнялось соотношение:
е.М = e.Q х e.N + e.R
Например,
<DIVMOD ( 5 ) 3 -> ( 1 ) 2 <DIVMOD ( 5 ) '-' 3 -> ( '-' 1 ) 2 <DIVMOD ( '-' 5 ) 3 -> ( '-' 1 ) '-' 2 <DIVMOD ( '-' 5 ) '-' 3 -> ( 1 ) '-' 2
Пример. Приведем описание функции Nod, вычисляющей наибольший общий делитель двух чисел по алгоритму Евклида.Формат обращения <Nod (e.1) e.2 >
Nod {
(e.1) 0 = e.1;
(e.1) e.2 = <Nod (e.2) <Mod (e.1) e.2> >;
}
Задача. Написать работу "по шагам" функции Nod для каких-либо небольших целых чисел.
Задача. Известная теорема из алгебры (см., например, [4], 1.8.3) утверждает, что наибольший общий делитель d двух чисел а и b всегда выражается в виде
d = u х a + v х b
для некоторых целых чисел u, v.
Числа u, v можно определить, используя соотношения, которые возникают при работе алгоритма Евклида.
Написать функцию, которая для данных целых чисел а, b вычисляет числа u, v.
ПРЕОБРАЗОВАНИЕ ЦИФР В МАКРОЦИФРУ - NUMB.
Bce исходные данные поступают в поле зрения в виде цепочек простых символов. Поэтому числовые данные - последовательности цифр - надо преобразовать в последовательность макроцифр. Для этого служит стандартная функция NUMB.
Формат обращения:
<NUMB e.D >
где e.D - последовательность цифр, перед которой может быть символ "+" или "-". Число представляется в десятичной системе счисления и должно быть меньше 2^32.Результатом вычисления является одна макроцифра, перед которой стоит знак "-", если исходное число было отрицательным.
Для перевода произвольной последовательности цифр без знака в последовательность макроцифр можно воспользоваться функцией CVB, которая приведена в программе e2000.ref.
ПРЕОБРАЗОВАНИЕ МАКРОЦИФР В ЦИФРЫ - SYMB.
Результаты надо печатать в виде последовательности цифр, поэтому существует стандартная функция SYMB, которая превращает одну макроцифру в последовательность десятичных цифр.
Формат обращения:
<SYMB e.N >
где e.N - одна макроцифра.
Результатом вычисления будет число e.N, записанное в десятичной системе счисления в виде последовательности простых символов.
Для перевода произвольной последовательности макроцифр без знака в последовательность десятичных цифр можно воспользоваться функцией CVD, которая приведена в программе e2000.ref.
Пример.Основным преимуществом арифметики языка рефал является неограниченность обрабатываемых чисел. Рассмотрим пример использования арифметики рефала.
Вычислить число е = 2.71828... с точностью до 2000 знаков после запятой.
Для вычисления числа е используем ряд
e = 1 + 1 + 1 / 2! + 1 / 3! + 1 / 4! + ...
Для решения задачи достаточно взять первые 1000 слагаемых ряда.
Будем вычислять частичные суммы ряда в виде дробей
Обозначим требуюмую функцию через Е2000. Решение приведено в программе e2000.ref.
Обращение к функции <Е2000 >
Результат замены - число е с точностью до 2000 знаков.
Сделаем пояснения.
Функция Е2000 делает вспомогательный шаг и подготавливает структуру поля зрения для вычислений: первый символ - макроцифра обозначает номер шага n+1 при вычислении частичной суммы ряда.
Функция Е2001 осуществляет вычисление а , n!, 10^n при n = 1,2,...,1000.
Первое предложение проверяет окончание цикла.
Функция CVD переводит полученные макроцифры в последовательность из 2000 десятичных цифр, а функция Е2003 ставит после первого символа десятичную точку (в числе е точка стоит после первой цифры).
Задача. Написать функцию Е вычисления числа е с заданным (произвольным) количеством знаков.
Формат обращения:
<Е e.N>
где e.N - макроцифра, указывающая точность вычислений.
Задача. Написать функцию вычисления числа pi = 3.14...