На этом шаге мы рассмотрим общие теоретические положения этого метода.

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

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

    Рассмотрение метода необходимо начать с метаязыка, который используется для описания типов данных. Данный метаязык включает в себя две операции - декартово произведение и размеченное объединение, а также несколько служебных слов для описания различных аспектов проектируемых типов данных. Служебные слова приводятся по мере рассмотрения упомянутых операций.

    1. Декартово произведение. Декартово произведение определяется стандартным для математики образом.

    Если C₁, C₂, ...,C_n - это типы, а C - это тип, состоящий из множества кортежей вида

   (c1,c2, ...,cn), c ∈ Ci, i=1,2,...,n,

   C=C1 × C2 × ... × Cn.

    Таким образом, операция декартова произведения строит гиперпространство на заданных множествах значений (типах). Каждая точка такого гиперпространства определяется набором координат, соответствующих значениям определённого типа, из которых состоит само декартово произведение.

    В методике синтаксически ориентированного конструирования к самому декартову произведению прилагается два типа операций (функций). Это конструктор (обозначается как "constructor") и множество селекторов (обозначается как "selectors").

    Функция-конструктор конструирует тип, являющийся декартовым произведением. Каждая функция-селектор выбирает из значения созданного типа соответствующее назначению селектора значение базового типа, из которых состоит декартово произведение.

    Запись наличия конструктора и селекторов у типа C при помощи математических формул выглядит следующим образом:

   c=constructor C,
   s1, s2, ..., sn = selectors C.

    Понятно, что конструктор - это функция, имеющая тип

   c: C1 × C2 × ... × Cn → C

   c: C1 → (C2 → ... → (Cn → C)...).

    Таким образом, смысл конструктора полностью определяется следующей формулой:

    ∀ci ∈ Ci, i=1,2,...,n: c c1 ... cn = <c1, c2, ..., cn>.

    Каждый селектор si, i=1,...,n, имеет тип s_i:C → C_i. Все селекторы связаны с конструктором важнейшей взаимосвязью:

    ∀x∈C: constructor C (s1 x)...(sn x)=x,

   si (constructor C c1...cn)=ci.

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

    2. Размеченное объединение. Размеченное объединение, так же как и декартово произведение в данном случае, является обычным объединением множеств (типы - это, по сути, множества), дополненным двумя наборами функций.

    Если C₁, C₂,..., C_n - это некоторые типы, а C - это тип, состоящий из объединения типов C₁, C₂,..., C_n, при условии выполнения "размеченности", то C называется размеченным объединением типов C₁, C₂,..., C_n.

    Обозначается этот факт как

   C=C1 + C2+ ... + Cn.

    Условие размеченности обозначает, что если из C взять какой-нибудь элемент c_i, то однозначно определяется базовый тип этого элемента C_i.

    Размеченность типа C определяется при помощи набора предикатов P₁, P₂, ..., P_n таких, что

    ∀(x∈C) (x ∈ Ci → Pi(x)&(∀j ≠ i)¬Pj(x)).

    Размеченное объединение гарантирует наличие таких предикатов.

    Этот факт указывается записью

   P1, ..., Pn = predicates C.

    Присутствие предикатов по сути позволяет всем значениям из типа C не терять своей идентичности и "помнить" о своём первоначальном типе C_i. Тем самым достигается то, что тип C как бы остаётся разделённым на части. Каждая часть - это исходный тип.

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

   N1, N2, ..., Nn = parts C.

    Каждая такая функция в применении ко всему множеству значений типа C возвращает только множество значений соответствующего ей типа C_i.

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

   constructor, selectors, predicates, parts.

    Со следующего шага мы начнем рассматривать бинарные деревья поиска.

Предыдущий шаг Содержание Следующий шаг