Язык РЕФАЛ: дополнительные виды памяти

Дополнительные виды памяти

Поскольку язык нормальных алгоритмов Маркова является вычислительно полным (можно реализовать любой алгоритм), то и Рефал обладает этим свойством. Однако вышеуказанными средствами Рефала не всегда можно достаточно просто описать любой алгоритм. В случае необходимости (временно запомнить промежуточные результаты, а потом их использовать выборочно для продолжения вычислений) мы можем пока использовать только накопление этих результатов в структурных выражениях, а необходимый при этом постоянный анализ таких выражений ведет к неэффективным алгоритмическим конструкциям. Поэтому с целью повысить эффективность разработки алгоритмов введены к обычным видам памяти ( поле памяти, в котором находятся описание рефал-функций, и поле зрения, в котором находится преобразуемое выражение) дополнительные виды памяти.

Рекурсивные вычисления и функция порождения процесса

Функции Рефала могут быть рекурсивными, т. е. обращаться сами к себе, как мы это видели на примерах предыдущего раздела. Но эти примеры не были связаны с запоминанием в памяти промежуточных вычислений рекурсии. Так, например, при вычислении функции n! происходит рекурсивный спуск от значения аргумента n к значению n-1 с запоминанием значения n к тому моменту, когда будет вычислено значение (n-1)! и надо будет умножить это значение на запомненное n. Такой рекурсивный спуск требует, чтобы рефал-машина имела не одно поле зрения (память) для выполнения процесса вычислений, а много таких полей зрения для порожденных процессов, которые могли бы выполнять вычисления в своей памяти, т. е. в своих полях зрения.

Вызов функции apply имеет другой синтаксис, чем вызов обычной рефал-функции:

<apply /Рефал-функция/ аргументРефал-функции>

Здесь полужирные уголковые скобки являются обязательными синтаксическими единицами в отличие от обычных уголковых скобок, служащих для описания синтаксиса. При вызове apply порождается новое поле зрения и в него помещается терм

k/Рефал-функция/ аргументРефал-функции.

Происходит попытка вычисления этого терма, и результат этого вычисления возвращается в то поле зрения, из которого была вызвана функция apply.

Поле того как результат замены сформирован, дополнительное поле зрения, созданное в результате обращения к apply, уничтожается. При рекурсивном обращении к apply образуется стек полей зрения.

В качестве примера мы рассмотрим создание функции вычисления факториала n!.

FACT     START
         ENTRY    Factorial
         EXTRN    prout, card, numb, symb, mul, first, apply
Factorial  =  k/fact/ k/numb/ k/prout/'n: '. k/card/...

fact  /0/   =  k/pr/ '!=1'
       E1   =  k/pr/ k/symb/E1.'!=' k/symb/ k/f0/ E1...
           
f0     E1   =  <apply /f/ E1>

f     /1/   =  /1/
       E1   =  k/mul/ (E1) k/f0/ k/m1/ E1...
           
pr          =
       E1   =  k/pr1/ k/first/ /80/ E1..
           
pr1 (E1)E2  =  k/prout/ E1. k/pr/ E2.
    '*'E1   =  k/prout/ E1.
	   
END

В этой программе функция Factorial вводит цепочку цифр данного, преобразует к символу-числу и вызывает функцию fact, которая вычисляет значение факториала от аргумента и готовит полученное значение к выводу на экран.

Функция fact для вычислений вызывает функцию f0, которая при помощи функции apply порождает процесс вычисления функции f. Эта функция накапливает произведение аргумента на значение факториала от аргумента, уменьшенного на 1, для чего снова вызывает функцию f0 с этим уменьшенным значением аргумента. Функция f0 снова порождает процесс вычисления f с новым значением аргумента и так делается до тех пор, пока значение аргумента не станет равно 1.

В этом случае будет происходить завершение вычисления функции f в обратном порядке вызванных процессов. Память завершающихся процессов будет удаляться, а значение, вычисленное в каждом процессе, будет передаваться в вызвавший процесс до тех пор, пока не закончится вычисление функции f0 в первом вызванном процессе.

Функция fact вызовет после вычислений преобразование результата к цепочке символов и вызов функции pr для вывода на экран результата.

Здесь следует обратить внимание на то, что полученная цепочка символов может не уместиться в одной строке экрана. Поэтому функция pr отщепляет от цепочки 80 символов при помощи функции first и передает на печать функцию pr1, которая печатает отщепленную часть и возвращает остаток функции pr для следующего отщепления. Так происходит до тех пор, пока вся цепочка символов не будет выведена.

Стековая память Рефала

Рефал позволяет использовать память, называемую копилкой . Она предоставляет возможность организовать любое количество стеков и запоминать информацию из поля зрения в том или ином стеке, а также извлекать эту информацию из стека в поле зрения.

Содержимое копилки перед началом работы рефал-программы всегда пусто, а в процессе работы рефал-программы имеет следующий вид:

('<ИмяСтека1>=<Выраж1>'). . . ('<ИмяСтекаN>=<ВыражN>'),

где <ИмяСтека1> ... <ИмяСтекаN> - произвольные имена стеков (необязательно различные), а выражения <Выраж1>...<ВыражN> - произвольные рефал-выражения, записанные в эти стеки. При записи в стек записываемое выражение добавляется вместе с именем стека в копилку слева.

Первичная функция brот bury - закопать. '<ИмяСтека>=<Выраж>' добавляет в копилку слева выражение аргумента и возвращает пустое выражение. Например, в результате выполнения

k/br/ 'X=A'. k/br/ 'X=B'.

в копилку слева добавится выражение ('X=B')('X=A'), т. е. образуется стек с именем X (если его ранее не было в копилке ) и в него добавится сначала символ 'A', а затем - символ 'B'.

Первичная функция dgот dig out - выкопать. '<ИмяСтека>' ищет в копилке слева структурное выражение ('<ИмяСтека>=<Выраж>') с именем стека <ИмяСтека>, удаляет его из копилки (т. е. из стека с этим именем) и возвращает выражение <Выраж> ; в поле зрения. Если в копилке не найдется имени стека, то будет возвращено пустое выражение. Например, пусть копилка имеет вид:

('X=A')('Y=B')('Y=C').

Тогда после выполнения

k/dg/ 'Y'.

копилка примет вид:

('X=A')('Y=C'),

а функция возвратит значение 'B'.

Первичная функция cpот copy - скопировать. <ИмяСтека> возвращает то же, что и функция dg. но не удаляет ничего из копилки ( копилка не изменяется). Например, после выполнения

k/dg/ 'Y'.

для результатов предыдущего примера копилка не изменится, а функция возвратит значение 'C'.

Первичная функция rpот replace - заменить. '<ИмяСтека>=<Выраж>', так же как и функция br, добавляет в копилку слева структурное выражение с аргументом, но удаляет перед этим последнюю (самую левую) запись с именем стека в копилке, если она там была. Возвращает пустое выражение. Например, пусть копилка имеет вид:

('X=A')('Y=B')('Y=C').

Тогда после выполнения

k/rp/ 'Y=C'.

копилка примет вид: ('X=A')('Y=C')('Y=C').

Первичная функция dgallот dig out all - выкопать все. возвращает в поле зрения все выражение копилки и очищает копилку полностью. Например, пусть копилка имеет вид:

('X=A')('Y=B')('Y=C').

Тогда после выполнения

k/dgall/ .

в поле зрения вернется ее выражение ('X=A')('Y=B')('Y=C') и копилка очистится.

В качестве примера мы рассмотрим сортировку массива положительных целых чисел методом вставки. Используются 2 стека: Y, в котором формируется отсортированная в возрастающем порядке последовательность, и X, который является вспомогательным: в нем содержится начало уже отсортированной последовательности в обратном порядке.

Каждое вводимое число z сравнивается с числом, находящимся в вершине стека Y, и если оно меньше, то идет поиск его места в стеке X, а если оно не меньше, то числа из Y переписываются в X до тех пор, пока z не станет меньше, чем в вершине Y (или Y не станет пустым), после чего оно записывается в Y.

При поиске места z в X оно сравнивается с числом, находящимся в вершине X, и если оно меньше, то числа из X переписываются в Y до тех пор, пока z не станет не меньше, чем в вершине X - тогда оно записывается в X.

При вводе нуля (признак окончания ввода) остаток в X переписывается в Y, а затем извлекается из стека Y для вывода через пробел на экран.

SORT    START
        ENTRY    Sort
        EXTRN    prout, card, numb, symb, sub, first, br, dg, cp
			 
*                    ввод 1-го числа в стек Y
Sort    =        k/n1/ k/br/'Y=' k/numb/
                          k/prout/'Последовательность чисел: '. k/card/....
										 
*                  ввод очередного числа z
n1    E1    =  k/n2/ k/br/'Z=' k/numb/ k/card/... k/cp/'Z'..

*                   z=0? X–>Y : z–y
n2  /0/     =  k/t1/ k/cp/'X'..
    S(N)1   =  k/n3/ k/sub/ (S1) k/cp/'Y'...
	   
*                  z<y?
n3  '–'E1   =  k/nx/ k/cp/'X'..
    E1      =  k/ny/ k/cp/'Y'..
	  
*                  X=0? z->X : z–x
nx          =  k/n1/ k/br/'X=' k/dg/'Z'...
    S(N)1   =  k/n4/ k/sub/ (k/cp/'Z'.) S1..

*                       z<x? X->Y : Z->X
n4   '–'E1       =  k/br/'Y=' k/dg/'X'.. k/nx/ k/cp/'X'..
     E1          =  k/n1/ k/br/'X' k/dg'Z'...
	   
*                       Y=0? Z->Y : z–y
ny               =  k/n1/ k/br/'Y=' k/dg/'Z'...
     S(N)1       =  k/n5/ k/sub/ (k/cp/'Z'.) S1..
		
*                       z<y? Z->Y : Y->X
n5   '–'E1       =  k/br/'Y=' k/dg/'Z'.. k/n1/ k/cp/'X'..
     E1          =  k/br/'X' k/dg'Y'.. k/ny/ k/cp/'Y'..
		
*                       X=0? –>вывод Y : X–>Y
t1               =  k/m2/ () k/cp/'Y'..
     E1          =  k/t1/ k/br/'Y' k/dg/'X'..k/cp/'X'..
		 
*                       Y=0? –>печать (E) : –>вывод Y
m2  (E1)         =  k/pr/ E1.
    (E1)S(N)2    =  k/m2/ (E1' 'k/symb/S2.) k/dg/'Y'..
		
*                  выделение 80 символов для печати
pr          =
     E1     =  k/pr1/ k/first/ /80/ E1..
		 
*                  печать выделенного или остатка
pr1 (E1)E2  =  k/prout/ E1. k/pr/ E2.
    '*' E1  =  k/prout/ E1.
		 
END

Обменная статическая и динамическая память Рефала

Рефал-выражения являются способом представления древовидных структур, которые в основном и используются при синтаксическом анализе конструкций какого-либо языка. Но в некоторых случаях необходимо представлять структуры, которые не обязательно являются древовидными. Таковы, например, сложные динамические структуры, основанные на цепных списках: очереди, деки, поисковые списки, графы, разреженные матрицы. И хотя любые структуры можно представлять в виде набора некоторого количества деревьев, это не всегда удобно.

Средством Рефала, дающим возможность обрабатывать произвольные динамические структуры, является обменная память , называемая также ящиками. Каждый ящик содержит произвольное рефал-выражение ( содержимое ящика ), которое может изменяться в процессе работы программы. Каждому ящику однозначно соответствует своя обменная функция - функция, с помощью которой можно получить доступ к содержимому ящика. Имя обменной функции совпадает с именем ящика.

Работа обменной функции осуществляется термом

<имя обменной функции>/ <рефал-выражение>.

В результате вызова такой функции содержимое ящика помещается в поле зрения, а в ящик записывается указанное рефал-выражение (происходит обмен информацией между полем зрения и ящиком ).

Все ящики делятся на статические и динамические. Статические ящики описываются директивой SWAP:

<пробел> SWAP <пробел> <имя ящика 1>, ... ,<имя ящика N>

и не могут уничтожаться во время работы. Например, в следующем фрагменте программы

SWAP    X,Y
swxy         = k/X/'A'. k/Y/ 'B'. k/sw/ /X/ /Y/.
sw    Sx Sy  = k Sx k Sy k Sx...

при вызове функции

k/swxy/.

в ящики X и Y сначала будут занесены символы 'A' и 'B' соответственно, а затем в результате выполнения терма

k/sw/ /X/ /Y/.

содержимое ящиков поменяется местами.

Динамические ящики порождаются в процессе работы программы первичной функцией new. В результате выполнения терма

k/new/ <рефал-выражение>.

создается новый ящик, в него помещается рефал-выражение аргумента и возвращается символ-ссылка, которая является именем новой обменной функции. Символ-ссылка играет роль указателя, т. е. имеет значение адреса памяти, и ее нельзя употреблять в программе в виде констант (но можно напечатать при отладке программы). Например, описанный выше пример со статическими ящиками мы могли бы заменить на аналогичный с динамическими ящиками:

EXTRN     new
swrr           = k/sw/ k/new/'A'/. k/new/ 'B'..
sw     Sx Sy   = k Sx k Sy k Sx...

Теперь при вызове функции swrr будут выполнены 2 вызова функции new, в результате которых образуются 2 ящика, например, с именами /%0321514/ и /%0674236/. В эти ящики будут записаны символы 'A' и 'B' соответственно, а затем при вызове функции sw их содержимое поменяется местами.

Обращаться напрямую к динамическому ящику мы не можем, но можем запомнить символ-ссылку и вызывать обменную функцию для нее. Если динамической памяти не хватит, то система запустит программу сборки мусора. Эта программа исследует, есть ли ссылки на тот или иной динамический ящик в поле зрения или других статических и динамических ящиках. Если такой ссылки нет, то соответствующий ящик удаляется (память освобождается). Это снимает с программиста заботу о чистке памяти.

Имеются 5 первичных функций, которые удобнее по сравнению с прямым использованием обменной функции.

Функция gtr (взять по ссылке)

k/gtr/ <ссылка>.        ,

где ссылка - это имя статического (симовол-метка) или динамического (символ-ссылка) ящика, извлекает и возвращает содержимое ящика.

Функция rdr (прочитать по ссылке)

k/rdr/ <ссылка>.

копирует в поле зрения содержимое ящика.

Функция ptr (положить по ссылке)

k/ptr/ <ссылка> <рефал-выражение>.

добавляет в ящик справа рефал-выражение аргумента и возвращает пустое выражение.

Функция wtr (записать по ссылке)

k/wtr/ <ссылка> <рефал-выражение>.

заменяет в ящике содержимое на рефал-выражение аргумента и возвращает пустое выражение.

Функция swr (Обменять по ссылке)

k/swr/ <ссылка> <рефал-выражение>.

делает обмен между содержимым ящика и полем зрения (в поле зрения выдается содержимое ящика, а в ящик записывается рефал-выражение аргумента).

Рассмотрим пример работы с поисковым списком. Элементы списка будут располагаться в динамических ящиках. Структура каждого элемента:

<ссылка следующего ящика> (<ключ>) <данные>

Последний элемент в цепочке динамических ящиков имеет пустую ссылку следующего ящика, а на первый элемент ссылается статический ящик, который определяет голову списка. Функции Init, In, Find, Out производят

Следующая программа выводит меню действий:

0. Завершить программу.
1. Инициализировать список.
2. Добавить элемент списка.
3. Найти данные по ключу.
4. Удалить элемент по ключу.
Введите пункт меню.

и осуществляет эти действия.

LIST     START
         ENTRY      Init, In, Find, Out, List
         EXTRN      prout, card, numb, symb,
*                     ключ, данные, указатели головы списка и
*                     элементов текущего, предыдущего и след.
         SWAP       key, data, pl, cur, pred, next
         
*                     начальный вывод меню и выбор действия
List     =          k/menu/. k/act/ k/pnkt/..

*                      вывод меню
menu     =          k/prout/ '0. Завершить программу.'.
                    k/prout/ '1. Инициализировать список.'.
                    k/prout/ '2. Добавить элемент списка.'.
                    k/prout/ '3. Найти данные по ключу.'.
                    k/prout/ '4. Удалить элемент по ключу.'.
                   k/prout/ ' Выберите пункт меню.'.
							 
*                    выбор пункта меню
pnkt            =  k/numb/ k/card/..

*                    выбор действия
act             =
         /0/    =
         /1/    =  k/Init/. k/menu/. k/act/ k/pnkt/..
         /2/    =  k/In/. k/menu/. k/act/ k/pnkt/..
         /3/    =  k/inkey/. k/Find/. k/prd/. k/menu/. k/act/ k/pnkt/..
         /4/    =  k/inkey/. k/Out/. k/prd/. k/menu/. k/act/ k/pnkt/..
         E1     =
		  
*                     ввод ключа
inkey    E1     =  k/key/ k/numb/ k/prout/'Ключ: '. k/card/...

*                     ввод данных
indat    E1     =  k/data/ k/prout/'данные: '. k/card/..

*                     инициализация списка
Init     E1     =  k/pl/.

*                     добавление элемента
In       E1     =  k/pl/ k/new/ k/gtr/ /pl/. (k/rdr/ /key/ k/inkey/..)
                                                                   k/rdr/ /data/ k/indat/....

*                     поиск по ключу: опред. тек.эл. cur
Find            =  k/wtr/ /pred/. k/wtr/ /cur/ k/rdr/ /pl/..
                                                                    k/f1/ k/rdr/ /cur/..

*                     нет текущего? не найден : анализ текущего
f1              =   k/data/ 'Не найден'.
      S(R)c     =   k/f2/ k/rdr/ k/rdr/ /cur/...

*                         анализ текущего
f2  S(R)n(S(N)k)Ed   =   k/wrt/ /next/ Sn. k/data/ Ed. k/f3/ Sk.

*                     сравнение ключей k–key
f3    S(N)k      =   k/f4/ k/sub/ (Sk) k/rdr/ /key/...

*                    k=key? найден : следующий
f4    /0/        =
      E1         =  k/pred/ k/cur/ k/next/... k/f1/ k/rdr/ /cur/..

*                    вывод результата из данных
prd   E1         =  k/prout/ k/rdr/ /data/..

*                    удаление: есть ли ключ?
Out   E1         =  k/Find/. k/o1/ k/rdr/ /cur/..

*                    удаление: есть ли предыдущий?
o1               =  k/data/ 'Не найден'.
      Vc         =  k/o2/ k/rdr/ /pred/..

*                    удаление: есть ли предыдущий?
o2               =  k/pl/ k/rdr/ /next/.. k/data/ 'Удален'.
      Vp         =  k/o3/ k/rdr/ k/rdr/ /pred/...

*                    удаление: изменение предыдущего
o3   S(R)cEd     =  k/wtr/ /pred/ k/rdr/ /next/. Ed. k/data/ 'Удален'.

              END

Отметим, что в случае, когда в статическом ящике A находится ссылка на другой динамический ящик %B, к которой мы непосредственно не можем обратиться, то для получения данных последнего ящика нужно дважды вызвать данные:

k/rdr/ k/rdr/ /A/..

В результате первого вызова функции rdr в поле зрения появится ссылка на динамический ящик (как содержимое ящика A ), а в результате второго вызова этой функции в поле зрения будет возвращено содержимое динамического ящика. Это и используется в вышеприведенной программе. Прокомментируем некоторые сложные функции этой программы.

Добавление элемента определяется функцией In. Ее выполнение начинается с получения ссылки в ящике головы списка pl (для первого вводимого элемента списка эта ссылка пустая и означает конец списка, а для последующих данных, определяемых динамическими ящиками, она уже не пустая), которая является первой частью тройки добавляемого элемента. Затем осуществляется ввод ключа нового элемента и определение этого значения в структурных скобках и, наконец, ввод данных этого элемента и определение этого значения в качестве последней части тройки элемента. После этого эти данные записываются в новый динамически определяемый элемент, а ссылка на него записывается в ящик головы списка.

Поиск элемента по ключу определяется функцией Find и вспомогательными функциями f1, f2, f3, f4. Действия функции Find начинаются с записи в ящик pred предыдущего элемента пустой ссылки и с записи в ящик cur текущего элемента ссылки на первый элемент списка, находящейся в ящике pl головы списка. Затем для текущего элемента списка вызывается функция f1, которая в случае неуспешности поиска (ссылка на текущий элемент пустая) записывает в ящик data отыскиваемых данных фразу 'Не найден'. В случае же непустой ссылки на текущий элемент f1 вызывает функцию f2, передавая ей на анализ этот элемент. Функция f2 анализирует данные текущего элемента, разбивая его на ссылку на следующий элемент (записывается в ящик next ), ключ и данные (записываются в ящик data данных). Затем она отправляет этот ключ функции f3 (для сравнения с поисковым ключом в ящике key ), которая готовит разность ключей и отправляет ее для решения функции f4. Эта функция при равенстве ключей (разность ключей равна 0) заканчивает вычисления поиска (в ящике data уже находятся искомые данные), а в ином случае сначала изменяет ссылку текущего элемента на следующий элемент, а ссылку предыдущего элемента - на прежний текущий элемент, и затем вызывает функцию f1 для нового текущего элемента.

Удаление элемента по ключу осуществляется функцией Out и вспомогательными функциями o1, o2, o3. Действия начинаются с поиска Find элемента по ключу и передачи текущего определенного элемента функции o1 для анализа. Функция o1 при пустой ссылке текущего элемента записывает в ящик data неуспешность поиска, а в ином случае передает эту ссылку функции o2 для подготовки удаления элемента из списка. Функция o2 в случае пустой ссылки предыдущего элемента изменяет ссылку в головном указателе pl на ссылку на следующий элемент (и этим ликвидирует текущий элемент списка), а в случае непустой ссылки предыдущего элемента передает функции f3 эту ссылку для удаления текущего элемента списка. Функция f3 записывает в ящик pred предыдущего элемента ссылку на следующий элемент, сохраняя остальные данные предыдущего элемента. Этим также заканчивается удаление текущего элемента.

Упражнения