Идиомы программирования на Рефале
Понятие идиомы в языке программирования
Есть ли в Си++ цикл со счётчиком? А цикл foreach? Если смотреть узко, то нет. Строго говоря, в Си++, как и в Си, только три цикла (конструкции, порождаемые условными инструкциями и goto, рассматривать не будем), а именно while, for и do-while. Первые два из них являются циклами с предусловием, последний — с постусловием. Такая конструкция, как цикл со счётчиком, в синтаксисе отсутствует, в отличие, скажем, от Паскаля и Бейсика. Однако один из циклов с предусловием обладает одним интересным свойством: цикл for позволяет помимо самого условия задавать инициализатор и "модификатор" каждой итерации:
for( инициализатор ; условие ; модификатор ) тело_цикла
Этим часто пользуются. Eсли нужно выполнить тело цикла, параметризованное последовательными целочисленными индексами, пишут что-то вроде этого:
//Листинг 1
for( int i = 0; i < 100; ++i )
{
a[i] = i * i;
}Очевидно, данный цикл выполняет тело цикла с последовательными значениями, т.е. в целом эквивалентен следующему циклу на Паскале:
for i := 0 to 99 do begin a[i] := i * i; end
Конструкции типа показанной в листинге 1, очень распространены и узнаются опытными программистами на Си с первого взгляда, в отличие от цикла, показанного на листинге 2, который делает то же самое, что и листинг 1.
//Листинг 2 for( int i = -1; ++i < 100; a[i] = i * i );
Общепринятые конструкции, выражающие распространённые понятия, непосредственно отсутствующие в языке программирования, называются идиомами этого языка программирования. Например, листинг 1 является идиомой цикла со счётчиком в си-подобных языках программирования.
Библиотека языка Си++ предоставляет пользователю набор различных по реализации, но одинаковых по интерфейсу шаблонных классов-контейнеров: вектора, списки, очереди, множества, отображения. Соответственно, при использовании контейнеров существует потребность перебора элементов контейнеров. Можно было бы вводить для каждого контейнера свою идиому для перебора, однако унифицированный интерфейс библиотеки позволяет использовать стандартную идиому для обхода контейнеров (листинг 3).
//Листинг 3
typedef .... MyContainer;
void printall(MyContainer& c)
{
for(MyContainer::iterator p = c.begin(); p != c.end(); ++p)
{
std::cout << *c;
}
}Таким образом, эта идиома (а именно, перебор при помощи итератора ContainerName::iterator начиная с obj.begin() и до obj.end()) позволяет эмулировать цикл foreach, присутствующий в синтаксисе многих других языков программирования (в частности, в Visual Basic и C#).
Поэтому на вопрос, заданный в начале статьи, можно ответить так: "Си++ поддерживает цикл со счётчиком и цикл foreach, но только идиоматически".
Другими примерами идиом, кроме цикла со счётчиком и имитации цикла foreach, может служить способ организации исходного кода с заголовочными файлами (имитирует модули с экспортом и импортом, которые непосредственно представлены в синтаксисе языка
Отсюда можно сделать вывод, что использование идиомы в языке программирования фактически означает расширение языка программирования некоей высокоуровневой инструкцией, которой нет непосредственно в языке. Как правило, в более низкоуровневых языках при помощи идиом выражаются те понятия, которые непосредственно существуют в высокоуровневых. Так например, функции map и filter в Scheme можно рассматривать как идиомы, ненужные в тех языках, где есть list comprehension.
Владение идиомами позволяет программисту быстрее писать программы, не тратя время на продумывание и написание типичного кода (типа листингов 1 и 3). Кроме того, такой код проще читать и понимать (если конечно код писал программист, владеющий идиомами), а также отлаживать, т.к. поведение идиом хорошо известно и не требует лишней отладки. Также опечатки в известных конструкциях, т.е. отход от общепринятого кода, бросается в глаза и свидетельствует о возможной ошибке.
Идиомы программирования на подмножестве базисного Рефала
В этом разделе будет рассмотрено сам подмножество и идиомы программирования на нём. Выбор подмножества базисного Рефала обусловлен двумя причинами:1. Подмножество базисного Рефала поддерживается всеми диалектами Рефала, поэтому рекомендации ниже можно будет воплотить везде. Правда, не везде в них есть необходимоть.
2. Я разрабатываю самокомпиляторы Модульного и Простого Рефалов, которые как раз поддерживают именно это подмножество (хотя Простой Рефал уже поддерживает вложенные функции — весьма мощное и выразительное средство, которое не только облегчает использование нижеперечисленных идиом, но и порождает ряд новых).
Для изложения будет использоваться синтаксис Рефала 5, который обладает достаточной выразительностью (по сравнению с Рефалом 2) и понятен большинству программистов на Рефале. При демонстрации идиом, связанных с указателями на функции и функциями высших порядков будут использоваться диалекты Модульного и Простого Рефала.
Для краткости в дальнейшем будем отождествлять понятия подмножества базисного Рефала и Рефал. Если будет иметься в виду конкретный диалект Рефала или особенности, не входящие в подмножество, это будет оговорено особо.
Специфические идиомы подмножества
Общие замечания о подмножестве базисного Рефала
Подробное описание подмножества, а также определения применяемых ниже терминов приведены в приложении к статье, поэтому читателям, не программировавшим ранее на Рефале, рекомендуется изучить это описание. В дальнейшем будет предполагаться, что читатель уже знаком с языком программирования Рефал и уже умеет писать и запускать на нём программы.Кратко можно сказать, что программа представляет собой набор функций, каждая из которых представляет собой набор предложений — пар образец = результат. Функция принимает единственный аргумент, представляющий собой объектное выражение (определение разных видов выражений см. в приложении). Аргумент сопоставляется по очереди с каждым образцом до тех пор, пока не будет достигнуто успешное сопоставление. В случае успешного сопоставления управление передаётся результату, выполнение которого приводит к замене скобок вызова функции в поле зрения (определения скобок вызова функции — скобок конкретизации и поля зрения см. в приложении). Т.е. выразительные средства языка оказываются крайне бедными: нет ни ветвлений по условию (кроме ветвлений по пассивному аргументу (а активным он быть и не может)), ни циклов, ни функций с несколькими аргументами, ни инкапсуляции (все данные в программе представляют собой объектные выражения, которые можно проанализировать любым образцом, скрыть внутреннюю структуру данных невозможно).
А так как полезных высокоуровневых средств непосредственно в языке нет, их приходится эмулировать вручную — сам программист рано или поздно разработает набор идиом для своей повседневной работы. В данной статье я расскажу о тех приёмах, которыми я пользуюсь при программировании на Простом и Модульном Рефалах. Часть их я узнал из различных руководств по программированию на Рефале (в частности, из руководства Турчина по Рефалу 5), часть я разработал самостоятельно. Если идиома основана не на моих идеях, я обязательно укажу авторство. Кроме того, будут приведены примеры кода на более развитых диалектах, демонстрирующие, как высокоуровневые средства делают ненужными соответствующие идиомы.
Общие идиомы подмножества
В этом разделе будут приведены идиомы, которые ограничиваются только подмножеством, описанным в приложении. В последующих разделах подмножество будет расширено это подмножество указателями на функции и вложенными функциями, т.е. средствами, существующими Модульном и Простом Рефалах.Форматы функций
Источник идиомы — руководство Турчина по Рефалу 5 BAD TAG: litno: ref5man, ["http://refal.net/chap3r5.html#3.2. ФОРМАТЫ ФУНКЦИЙ" отсюда].Одним из ограничений подмножества базисного Рефала является унарность функций — каждая функция принимает на входе только один аргумент и возвращает только одно значение, в то время как часто возникает необходимость передать в функцию несколько значений. Кроме того, функция может возвращать несколько связанных по смыслу значений. Во многих распространённых императивных языках программирования функции могут принимать несколько аргументов, но при этом возвращают только одно значение. Для возврата нескольких значений семантика языка предусматривает передачу параметров по указателю или ссылке, позволяя тем самым присвоить из вызываемой функции новое значение передаваемым параметрам. Передача по ссылке в базисном Рефале невозможна, т.к. требует наличия операции присваивания, которой в семантике языка места не нашлось.
Решение этой проблемы даёт введение соглашений о вызовах функций, также известных как форматы функций. Форматом аргумента называется способ построения из нескольких логически разных аргументов функции одного объектного выражения, в котором однозначно выделяется каждая часть, соответствующая самостоятельному аргументу. Аналогично, форматом результата называется способ формирования возвращаемого значения функции (т.е. пассивного объектного выражения, которое образуется на месте скобки активации данной функции после выполнения необходимого числа шагов Рефал-машины) в виде объектного выражения, содержащего однозначно выделяемые фрагменты, соответствующие различным возвращаемым значениям (если угодно, выходным параметрам).
Как правило (входные и выходные) параметры-термы (в том числе и атомы) попадают в формат как есть, если же нужно передать в функцию или получить из функции N объектных выражений переменной длины, то как правило (N - 1) из них заворачивают в круглые скобки, а последнее (или первое) передают как есть. Если при таком способе формирования форматов заменить отдельные параметры на соответствующие переменные — атомы, термы и выражения на, соответственно, s-, t- и e-переменные, то полученный образец не будет содержать открытых e-переменных, а значит, будет распознаваться за постоянное время — за постоянное время будут выделяться отдельные подаргументы внутри аргумента функции.
Таким образом, формат функции — это лишь соглашение о том, каким образом вызывается функция и какое возвращаемое значение от неё ожидать. Для документирования формата я предпочитаю использовать комментарии, показанные на листинге 4.
// Листинг 4
/*
<Fact s.N> == s.N!
*/
Fact { ... }
/*
<Parse (s.Token e.Value)*>
== t.ErrorList t.SyntaxTree
*/
Parse { ... }
/*
<Zip (t.ElemA*) (t.ElemB*)>
== (t.ElemA t.ElemB)*
*/
Zip { ... }
/*
<Repeat s.Num e.Expr>
== e.Expr e.Expr ... e.Expr
Выражение e.Expr повторяется s.Num раз.
*/
Repeat { ... }
/*
<Map s.Func t.Elem*>
== e.Res*
где <s.Func t.Elem> == e.Res
*/
Map { ... }
/*
<GetFileSize e.FileName>
== Size s.Size
== Directory
== FileNotFound
*/В данных комментариях отдельные элементы формата (атомы, термы, выражения) показаны как переменные соответствующих типов. Для выражений, представляющих собой цепочки однородных элементов (термов или иногда подвыражений), показана повторяемая часть, после которой следует знак *. Формат аргумента функции для наглядности иллюстрируется как вид скобки конкретизации, т.е. внутри угловых скобок с именем функции. Формат результата начинается с двойного знака равенства ==. Однократный знак равенства означает замену вызова функции на результат за один шаг рефал-машины, поэтому двойной знак равенства означает достижение пассивного результата за более чем один шаг.
А теперь, чтобы не оставалось сомнений, вкратце рассмотрим форматы функций, представленные на листинге 4. Функция Fact принимает один атом (как не трудно догадаться, число) и один атом возвращает, а именно, факториал аргумента. Функция Parse получает на входе лексическую свёртку — последовательность скобочных термов вида (s.Token e.Value), где s.Token представляет собой тип токена: число, имя, знак пунктуации, а e.Value — связанное с ним значение, а возвращает список обнаруженных синтаксических ошибок и построенное синтаксическое дерево. Функция Zip принимает две цепочки термов и сворачивает их в одну. Что делает функция, в случае если цепочки t.ElemA* и t.ElemB* окажутся разной длины, в формате не описано, скорее всего лишние термы будут отброшены. Функция Repeat принимает число повторений и выражение, которое нужно размножить, возвращает размноженное выражение. Функция Map принимает первым термом функцию и цепочку термов для преобразования, возвращает цепочку преобразованных термов. Формат функции-преобразователя в комментарии показан в той же манере. В функции GetFileSize мы сталкиваемся с ещё нерассмотренным случаем — с несколькими форматами возвращаемых значений. В таких случаях выходные форматы следует делать ортогональными, но при этом достаточно схожими. Для этого достаточно разные выходные форматы начинать с различных атомов-имён, помечающих разный результат функции (например, корректное или ошибочное завершение).
Под ортогональными форматами здесь и далее будем понимать форматы, пересечение множеств объектных выражений, соответствующим этим форматам, пустое. Самый простой способ сделать форматы ортогональными — это начинать их с разных атомов-имён, как это сделано с функцией GetFileSize.
Комментарии с форматом функции рекомендуется писать либо перед entry-функцией, либо перед функцией, решающей довольно крупную подзадачу, либо перед функцией, имеющей нетривиальный формат, либо перед функцией, которая вызывается несколько раз в пределах одного модуля и все точки её вызова находятся на достаточно большом расстоянии от места её определения. Автор этой статьи написал программу, которая умеет сканировать файлы исходного текста в поисках комментариев определённого вида и записи содержимого этих комментариев в (указанный в командной строке) текстовый файл. Эти комментарии представляют собой комментарии в стиле Си, начинающиеся с последовательности /**. В таких комментариях автор статьи предпочитает записывать комментарии к entry-функциям, чтобы затем просматривая текстовик с интерфейсами, сразу узнавать формат, не лазая по исходным текстам.
Как это часто бывает с идиомами, введение более высокоуровневых средств в язык позволяет если не отказаться, то хотя бы упроситить использование идиомы. Так например, в диалекте Рефал Плюс имеется поддержка форматов функций со стороны компилятора — для каждой функции необходимо задать её формат, для чего введён специальный синтаксис объявлений функций. Компилятор проверяет соответствие функции заданному формату: соответствие образцов формату на входе, соответствие завершающего результатного выражения (т.к. предложение может содержать несколько образцов и результатов — т.н. действий) формату на выходе, а также корректность вызовов функций, образующих результатные выражения. На листинге 5 приведён пример функции быстрой сортировки с двумя вспомогательными функциями и явным описанием форматов каждой из них.
/* Листинг 5 */
$func QSort eS = eQ;
$func Split sX eS = (eS1) (eS2) (eS3);
$func Split-Aux sX (eS1) (eS2) (eS3) eS = (eS1)(eS2)(eS3);
QSort
eS =
{
eS : /* пусто */ = ;
eS : t = eS;
eS : sX e =
<Split sX eS> :: (eS1)(eS2)(eS3),
<QSort eS1> eS2 <QSort eS3>;
};
Split
sX eS =
<Split-Aux sX ()()() eS>;
Split-Aux
sX (eS1)(eS2)(eS3) eS =
eS :
{
/* пусто */ = (eS1)(eS2)(eS3);
sY eRest =
{
<"<" (sY)(sX)>
= <Split-Aux sX (eS1 sY)(eS2)(eS3) eRest>;
<">" (sY)(sX)>
= <Split-Aux sX (eS1)(eS2)(eS3 sY) eRest>;
/* sX == sY */
= <Split-Aux sX (eS1)(eS2 sY)(eS3) eRest>;
};
};Имитация неуспешного выполнения
Данная идиома является частным случаем предыдущей идиомы, однако поскольку я часто пользуюсь этим приёмом, позволю себе рассказать о нём отдельно.Бывают такие случаи, когда функция в результате работы может либо возвратить некоторое значение, либо возвратить не может. Можно привести следующие примеры:
1.Операция поиска по ключу в некотором ассоциативном массиве может либо найти значение, либо не найти, если такого нет.
2. Операция добавления нового имени в таблицу символов может либо завершиться успешно, если такое имя ранее отсутствовало в таблице символов, либо неудачно, если таблица уже содержит такое имя.
3. Операция синтаксического анализа может либо распознать без ошибок, либо при разборе могут встретиться ошибки.
4. Операция загрузки данных из файла может завершиться либо успешно (данные загружены без ошибок), либо неудачно (файл не найден, нет прав на чтение, файл в неправильном формате).
Этот список можно продолжать и дальше, но основная идея уже и так понятна. Необходимо для функции обеспечить два ортогональных выходных формата: для представления успешного и неудачного завершения операции. Можно в случае невозможности выполнения информации возвращать пустое выражение, но этот вариант может быть не ортогонален, т.к. пустой результат может быть и вполне корректным результатом (например, при поиске в ассоциативном массиве, отображающем любое объектное выражение на любое объектное выражение). Можно корректный результат заворачивать в структурные скобки, а в случае неуспеха — возвращать пустое выражение. Такие форматы уже ортогональны, но не выразительны, т.к. структурные скобки ничего не говорят об успешности (т.е. фактически представляют собой как костыль).
Воспользуемся наиболее простым способом "ортогонализации": будем начинать разные результаты с разных атомов-имён — успешный возврат с Success, неуспешный — c Fails. Таким образом, формат неуспешной (Failable) функции можно описать так, как показано на листинге 6 (а).
// Листинг 6 (а) /* <Foobar некоторый-аргумент> == постоянная-часть Success успешный-результат == постоянная-часть Fails необязательный-признак-ошибки */ // Листинг 6 (б) // Реальный пример формата функции парсера командной строки /* <Parse t.ErrorList t.FnCmdLineDescription e.ArgList> == t.ErrorList Success t.Collected == t.ErrorList Fails */
Здесь некоторый-аргумент — это аргумент функции, постоянная-часть — та часть выходного формата, которая присутствует в выходном формате, успешный-результат — результат, который выводится в случае успешного выполнения операции, необязательный-признак-ошибки — дополнительная информация, описывающая почему именно не удалась операция, часто может отсутствовать.
На листинге 6 (б) приведён пример формата функции из компилятора Модульного Рефала. Структура данных t.ErrorList — это абстрактный тип данных (см. ниже), содержащий в себе список обнаруженных ошибок (лексических, синтаксических, семантических...) с местоположением самих ошибок. Этот список передаётся из функции в функцию, каждая из которых туда может добавить новую информацию. t.FnCmdLineDescription — структура данных, описывающая обработку командной строки, содержит в себе имена допустимых опций, их особенности (наличие у опции параметра или группы параметров) и функции их обработки, e.ArgList — это список аргументов командной строки. Функция при успешном завершении возвращает структуру данных t.Collected, которая фактически представляет собой абстрактное синтаксическое дерево для данной командной строки и для данного метода обработки, в случае неудачного завершения нет необходимости возвращать какую-либо дополнительную информацию о том, почему не удался разбор, т.к. клиентскому коду, использующему эту функцию, не интересна эта причина, а сами описания ошибок уже находятся в t.ErrorList.
Передача параметра t.ErrorList сквозь каждую функцию обусловлена недостатками реализации рантайма — необходимостью копирования переменных. При использовании реализаций, имеющих векторный или векторно-списковый способ представления объектных выражений, копирование было бы эффективно и необходимости в передаче из функции в функцию t.ErrorList не было бы. Кроме того, если бы на момент написания этого кода была бы поддержка вложенных функций, можно было бы упрятать список ошибок в монаду State (см. ниже) и не использовать его явно.
Высокоуровневое средство, которое имитирует эта монада — это использование откатных функций, имеющихся в большинстве развитых диалектов Рефала: в Рефале Плюс, в Рефале 6 и Рефале 7. Однако, в случае использования неуспехов нет возможности возвращать вместе с неуспехом какую-либо постоянную-часть, например, список обнаруженных ошибок. Любители Хаскеля в этой идиоме, скорее всего, уже увидели монаду Maybe, которая как раз и применяется с этой целью: вернуть либо корректное значение, либо признак "Значения нет". Возврат Success соответствует конструктору Just x, возврат Fails соответствует конструктору Nothing монады Maybe. Кроме того, в Рефале с вложенными функциями (Рефал 7 или Простой Рефал, в перспективе и Модульный Рефал) можно реализовать монады Error, Continuation или IO, которые позволили бы использовать механизм исключений для генерации исключительных ситуаций как альтернативу возврату Fails (про монады см. ниже).
Ассоциативные списки и поиск по открытым e-переменным
Для этой идиомы трудно указать конкретный источник, т.к. идиома достаточно проста и её в руководствах редко объясняют подробно, она как правило приводится как нечто, само собой разумеющееся.Основными типом данных Рефала является объектное выражение, представляющие собой цепочки термов. Термами могут быть либо подвыражения, заключённые в структурные скобки, либо атомы того или иного подтипа. Данный набор средств, не смотря на всю его кажущуюся бедность, является очень гибким и позволяет реализовывать аналоги таких конструкций других языков как записи, включая записи с вариантами, а также удобно описывать деревья различного вида и сложности. В данном разделе будет рассмотрена идиома, позволяющая выражать такой тип данных, как отображение (в смысле, структура данных). Отображение позволяет сопоставить одному значению — ключу (key) другое значение — значение (value). Ключи как правило (но не всегда) уникальны для данного отображения. Для этого типа данных определены операции поиска значения по ключу, обновления значения, связанного с данным ключом, добавление новой пары ключ-значение, удаления значения, связанного с данным ключом. В большинстве языков программирования такой тип данных присутствует как встроенный или библиотечный и называется ассоциативным массивом (иногда хеш-таблицей, но хеш-таблица — это один из способов реализации ассоциативного массива).
Отображение можно реализовать различными способами. Рассмотрим некоторые.
1. Ассоциативный список представляет собой последовательность пар (ключ, значение). Поиск нужной пары осуществляется путём последовательного перебора пар до тех пор, пока не будет обнаружен требуемый ключ или не будет достигнут конец последовательности. Сама последовательность может реализовываться в императивных языкак как массив или односвязанный список, в функциональных языках, поддерживающих списки, как список пар, в Рефале как объектное выражение. Формат каждого терма такой последовательности должен позволять однозначно выделить как ключ, так и значение. Примеры таких форматов: ((e.Key) e.Value), (e.Key s.Value), (s.Key e.Value). Время доступа по ключу при данной реализации — как правило O(N), где N — количество пар.
Если запросы обладают определённой степенью локальности, то можно использовать самонастраивающийся список. Принцип действия следующий. При доступе (не важно, по чтению или по записи) по некоторому ключу соответствующая пара перемещается в начало последовательности, поэтому если данные обладают локальностью, наиболее "популярные" за недавнее время пары будут находиться в начале, и, следовательно, доступ к ним будет осуществляться быстрее.
2. Дерево. На самом деле существует много разных видов деревьев, например АВЛ-деревья, красно-чёрные деревья, 2-3-деревья, сильно ветвящиеся деревья. Общей их чертой является то, что при правильной реализации доступ по ключу в дереве осуществляется за время O(log N). Дерево на Рефале реализовать сравнительно не сложно, т.к. сама структура объектных выражений древовидная — за счёт того, что сами термы могут содержать в себе другие выражения. Самое простое дерево, без каких-либо оптимизаций, может быть описано форматом на листинге 7. Здесь термы t.Tree-Left и t.Tree-Right имеют тот же формат t.Tree. Предполагается, что ключи элементов, описанных в дереве t.Tree-Left меньше (по какому-либо способу упорядочивания) ключа e.Key текущего узла, аналогично t.Tree-Right содержит значения с ключами, большими текущего ключа.
// Листинг 7. Описание дерева. /* t.Tree ::= Empty | ((e.Key) e.Value t.Tree-Left t.Tree-Right) */
Поиск по такому дереву осуществляется по следующей схеме:
1) Если t.Tree == Empty, то поиск завершился неудачей.
2) В противном случае, если ключ e.Key имеет интересующее нас значение, то данный узел является искомым.
3) Если значение e.Key больше искомого значения, осуществляем рекурсивный поиск в поддереве t.Tree-Left.
4) Если значение e.Key меньше искомого значения, осуществляем рекурсивный поиск в поддереве t.Tree-Right.
3. Сортированный массив — это массив пар вида (ключ, значение), элементы которого отсортированы по возрастанию. Поиск пары по ключу осуществляется алгоритмом двоичного поиска за время O(log N), но операции вставки и удаления могут потребовать перемещения всех элементов массива. Таким образом время при поиске и обновлении значения по ключу происходит за время O(log N), вставка и удаление осуществляются за время O(N). Операции вставки и удаления для сортированного массива выполняются гораздо медленнее, чем для дерева, однако, как правило, двоичный поиск внутри массива выполняется быстрее (с меньшим коэффициентом перед log N), чем операции поиска внутри дерева, поэтому если объём данных измеряется редко (например, если данные добавляются в отображение только на этапе инициализации), то предпочтительнее использовать сортированный массив.
4. Хеш-таблица. Данный метод основан на использовании хеш-функции — функции, отображающей ключи на целые числа таким образом, чтобы для двух разных ключей вероятность получения одинаковых чисел была минимальной. Результат применения хеш-функции к некоторому ключу называется хешем данного ключа. Сама хеш-таблица представляет собой массив ассоциативных списков. При доступе к хеш-таблице по некоторому значению ключа сначала вычисляется хеш ключа, который затем выступает индексом массива. В дальнейшем поиск осуществляется внутри ассоциативного списка, находящегося по данному индексу. При правильно подобранном размере массива время доступа к элементу равно O(1), т.е. фактически не зависит от размера таблицы.
В отличие от ассоциативного списка и дерева, сортированный массив и хеш-таблица требуют эффективной операции индексирования для доступа к элементу (т.е. для чтения и для записи), что предоставляют не все реализации Рефала (как правило, вектор предоставляется как быблиотечный абстрактный тип данных).
Любой (или почти любой, если у нас нет вектора) из вышеперечисленных способов представления отображения можно оформить как АТД, однако, как мы покажем ниже, без этого вполне можно обойтись. Как известно, сложные алгоритмы с хорошими асимптотическими оценками оказываются эффективнее простых алгоритмов только при больших значениях N. Поэтому если пар в отображении немного, то можно воспользоваться и простым ассоциативным списком, используя нижеприведённую идиому.
Вспомним, как работает образец с открытыми e-переменными. Если мы имеем образец вида e.Begin образец-терма e.End, где образец-терма — это образец, с которым может сопоставиться только один терм (образец в скобках, атом, t- или s-переменная), то в процессе сопоставления объектного выражения с этим образцом образец-терма будет последовательно сопоставляться с каждым термом аргумента до тех пор, пока сопоставление не удастся или пока не завершится выражение. Если же в качестве образца-терма выбрать формат элемента ассоциативного списка с фиксированным ключом, то будет выбран элемент, представляющий собой пару (ключ, значение) с требуемым ключом или же сопоставление не удастся. Таким образом, если для поиска в дереве понадобится выполнить ряд шагов рефал-машины, то поиск в ассоциативном списке мы можем осуществлять с помощью одного образца. Функции на листинге 8 демонстрируют основные приёмы использования этой идиомы.
// Листинг 8. Приёмы работы с ассоциативными списками.
/*
В этом примере e.AssocList ::= (e.Key (e.Value))*.
Кроме того, в примере предполагается,
что повторения в ассоциативном списке отсутствуют.
*/
/*
Функция, осуществляющая поиск элемента с заданным ключом.
<Lookup (e.Key) e.AssocList>
== Success e.Value
== Fails
*/
Lookup {
(e.Key) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
Success e.Value;
(e.Key) e.AssocList = Fails;
}
/*
Функция, осуществляющая обновление ассоциативного списка.
Если элемент с данным ключом отсутствует, то он добавляется в список.
<Update (e.Key) (e.Value) e.AssocList>
== e.AssocList
*/
Update {
(e.Key) (e.NewValue) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
e.AssocList-B (e.Key (e.NewValue)) e.AssocList-E;
(e.Key) (e.NewValue) e.AssocList =
e.AssocList (e.Key (e.NewValue));
}
/*
Функция, добавляющая новый элемент.
Если элемент уже существует, возвращается ошибка.
<Insert (e.Key) (e.Value) e.AssocList>
== Success e.AssocList
== Fails
*/
Insert {
(e.Key) (e.Value) e.AssocList-B (e.Key (e.OtherValue)) e.AssocList-E =
Fails;
(e.Key) (e.Value) e.AssocList =
Success e.AssocList (e.Key (e.Value));
}
/*
Функция, осуществляющая удаление элемента.
Если элемент уже существует, возвращается ошибка.
<Delete (e.Key) e.AssocList>
== Success e.AssocList
== Fails
*/
Delete {
(e.Key) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
Success e.AssocList-B e.AssocList-E;
(e.Key) e.AssocList =
Fails;
}
/*
Функция, осуществляющая "очистку" ассоциативного списка
от элемента с данным ключом.
После завершения данной функции в ассоциативном списке не будет
пары с требуемым ключом.
<Clear (e.Key) e.AssocList> == e.AssocList
*/
Clear {
(e.Key) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
e.AssocList-B e.AssocList-E;
(e.Key) e.AssocList = e.AssocList;
}Здесь нужно дать несколько пояснений.
1. Этот пример только демонстрирует применение идиом, он не представляет собой абстрактный тип данных, который следует включать в библиотеку. Каждая из этих функций только демонстрирует способы обращения с ассоциативными списками.
2. Для обозначения частей ассоциативного списка, не содержащих ключа, я использую имя переменной с суффиксами -B и -E (очевидно, от слов begin и end).
3. В реализациях Рефала, использующих списковое представление поля зрения, копирование переменных обходится дорого, а в примерах кода функций Lookup, Insert и Delete в случае неудачи весь список уничтожается. Поэтому при вызове этих функций нужно на всякий случай создавать копию списка, что может оказаться неэффективным. Функции, сохраняющие список, представлены на листинге 9. Функциям был добавлен суффикс -T от слова transparent, т.к. они возвращают неизменным один из своих параметров из соображений эффективности.
// Листинг 9. Функции, сохраняющие список.
/*
Функция, осуществляющая поиск элемента с заданным ключом.
<Lookup-T (e.Key) e.AssocList>
== Success e.Value (e.AssocList)
== Fails e.AssocList
*/
Lookup-T {
(e.Key) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
Success e.Value
(e.AssocList-B (e.Key (e.Value)) e.AssocList-E);
(e.Key) e.AssocList = Fails e.AssocList;
}
/*
Функция, добавляющая новый элемент.
Если элемент уже существует, возвращается ошибка.
<Insert-T (e.Key) (e.Value) e.AssocList>
== Success e.AssocList
== Fails e.AssocList
*/
Insert-T {
(e.Key) (e.Value) e.AssocList-B (e.Key (e.OtherValue)) e.AssocList-E =
Fails e.AssocList-B (e.Key (e.OtherValue)) e.AssocList-E;
(e.Key) (e.Value) e.AssocList =
Success e.AssocList (e.Key (e.Value));
}
/*
Функция, осуществляющая удаление элемента.
Если элемент уже существует, возвращается ошибка.
<Delete-T (e.Key) e.AssocList>
== Success e.AssocList
== Fails e.AssocList
*/
Delete-T {
(e.Key) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
Success e.AssocList-B e.AssocList-E;
(e.Key) e.AssocList =
Fails e.AssocList;
}4. В рассмотренном примере операции над списком сохраняют относительный порядок элементов: части e.AssocList-B и e.AssocList-E в результатной части объединяются в том же порядке, новые элементы добавляются в конец, при обновлении списка новый терм вставляется в то место, где был старый. В тех случаях, когда сохранения порядка не требуется, можно использовать самонастраивающиеся списки, как показано на листинге 10.
// Листинг 10.
// Для наглядности приведены не все функции.
/*
Функция, осуществляющая поиск элемента с заданным ключом.
<Lookup-T (e.Key) e.AssocList>
== Success e.Value (e.AssocList)
== Fails e.AssocList
*/
Lookup {
(e.Key) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
Success e.Value
((e.Key (e.Value)) e.AssocList-B e.AssocList-E);
(e.Key) e.AssocList = Fails e.AssocList;
}
/*
Функция, осуществляющая обновление ассоциативного списка.
Если элемент с данным ключом отсутствует, то он добавляется в список.
<Update (e.Key) (e.Value) e.AssocList>
== e.AssocList
*/
Update {
(e.Key) (e.NewValue) e.AssocList-B (e.Key (e.Value)) e.AssocList-E =
(e.Key (e.NewValue)) e.AssocList-B e.AssocList-E;
(e.Key) (e.NewValue) e.AssocList =
(e.Key (e.NewValue)) e.AssocList;
}Преимущества по компактности записи кода эта идиома даёт только в подмножестве Базисного Рефала, т.к. в более продвинутых реализациях с действиями (Рефал 6, 7, Плюс) или хотя бы с условиями и блоками (Рефал 5) можно, не создавая россыпи промежуточных функций, использовать библиотечные ассоциативные массивы, представляющие собой АТД и реализованные, скажем, как деревья или хеш-таблицы.
Абстрактные типы данных
Абстрактные типы данных (АТД) — это не идиома конкретного языка программирования, а общий метод управления сложностью программ и повышения гибкости архитектуры. Применительно к Рефалу описание идиомы можно найти в том же учебнике Турчина BAD TAG: litno: ref5man, ["http://www.refal.ru/chap3r5.html#3.2. ФОРМАТЫ ФУНКЦИЙ" здесь]. Глубокое рассмотрение абстрактных типов данных (правда, применительно не к Рефалу, а к Схеме) можно найти в книге BAD TAG: litno: SICP.Единственный тип данных Рефала — это объектное выражение. Основные операции, производимые над ним — анализ (от греческого analysis — "разложение, расчленение") выражения путём сопоставления с образцом, синтез (от греческого synthesis — "совмещение, помещение вместе) нового выражения из переменных, констант и результатов выполнения функций в результатной части выражения, а также операции над встроенными в язык типами данных (числа, символы, имена) при помощи библиотечных функций (арифметика, преобразование символ <–> код символа и др.).
