index , prev , next

e2000.ref

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...

index , prev , next