DTL. Часть третья
Множества
Описание конкретных элементов уже позволяет, конечно, описывать ряд цепочек, но выразительности этих конструкций определённо не хватает. С их помощью можно явно перечислить некоторые цепочки, но возникает необходимость описывать наборы цепочек одним шаблоном.
Очень часто при описании предикатов для цепочек необходимо указать не наличие в цепочке какого-то конкретного элемента, а элемента из некоторого множества. Одновременно с этим очень часто условия на разные символы в разных цепочках оказываются одинаковыми, и в этом случае также удобно объявить множество цепочек, для которых истинно некоторое условие.
:= ∝ <=>A(x)= x∈ ∝, ( 11 )
где - имя множества в угловых скобках,
∝ - определение множества в виде шаблона,
A(x) - предикат, определяемый множеством.
Итак, множество представляет собой полноценный аналог предиката. По сути дела, оно задаёт предикат принадлежности к себе (т. е. предикат истинен только для элементов данного множества). В то же время, любой предикат порождает множество, в которое входят те цепочки, для которых он истинен. Имя множества указывается в угловых скобках. В определении множества оно указывается в левой части определения, далее следует знак «:=» и после него формируется шаблон-предикат, определяющий множество. После этого множество можно указывать в качестве элемента шаблонной цепочки.
Пример описания цепочек из двух одинаковых подцепочек с помощью множеств.
:= abcd
:=
⇒ := abcdabcd
Итак,
(∝) ≡ Def(A, P), P(∝), ( 12 )
где Def(X,Y) :="Y является определением X\" (т. е. в файле существует строка : = Y)"
Как и предикаты Пролога, множества могут быть параметризованы. Параметры при вставке множества могут унифицироваться как в строке шаблона, содержащей множество, так и в его определении.
Параметры перечисляются через запятую и указываются в имени множества. В шаблонной строке параметры указываются так же, как и переменные, в квадратных скобках. Если параметр унифицируется с элементом входной цепочки, он указывается без дополнительных знаков. Если его надо унифицировать с чем-то ещё, параметр указывается с символом равенства, а после параметра записывается элемент, с которыми происходит унификация.
≔ [Value=]0|1|2|3|4|5|6|7|8|9
≔
≔ [L = l * 10][Val = DVal * l + NVal]
Определения множеств записываются отдельными строками наряду со строками правил преобразования. Интерпретатор отличит определения от правил по наличию в них конструкции «:=».
Метасимволы
Зачастую бывает удобно описывать повторяющиеся конструкции символов с помощью некоторой сокращённой записи. Для таких целей используются метасимволы, записываемые после элемента, к которому они применяются. Вот примеры таких метасимволов и тех строк, которые будут вместо них подставлены интерпретатором:
X? ≡ |X (элемент встречается 0 или 1 раз) ( 13 )
X:(a, b) ≡ [n ≥ a][n ≤ b] (элемент встречается от a до b раз) ( 14 )
Один из параметров a или b (вместе с запятой) можно опускать. В данной версии интерпретатора эта языковая возможность не реализована.
X* ≡ (элемент встречается любое число раз подряд (включая 0)), ( 15 )
X+ ≡ [n≥1] (элемент встречается любое число раз подряд),
где
≔
:= [Y][k = k1 + 1]
Функции
Некоторую последовательность операций удобно определить как функцию, которую можно будет легко вызывать внутри шаблонов. В отличие от множеств, основное требование для вызова функции - полная определённость всех параметров в момент обращения к ней. Функция может вернуть любое значение (не обязательно истину или ложь).
Вот пример функции, суммирующей входную последовательность цифр:
sum ≔ => 0
sum ≔ [X=]x[Y=]α[Z = X + @(sum,Y) ] => [Z]
Функция определяется при помощи строки, содержащей её имя, знак определения («:=»), далее - список входных данных, знак преобразования (=>) и, наконец, список выходных данных. Список входных данных теоретически может быть пустым.
Аналогичным образом вычисляется длина цепочки:
length ≔ => 0
length ≔ x[A=]α[L = @(length,α) ][R = L + 1] => [R]
Вызов функции, как вы уже заметили, начинается с «собачки». Далее через запятую указываются имя функции и её аргументы (это сделано для упрощения анализатора, да).
Фактически вызов функции приводит к запуску внутреннего преобразователя, работающего по собственным правилам. Результат внутреннего преобразователя используется для дальнейшей работы внешнего.
Определять функцию можно произвольное число раз. При этом каждое определение может содержать свой шаблон для описания работы функции.
Существуют предопределённые функции, которые не нужно описывать. Эти функции позволяют конструировать новые элементы, а также делать многое другое.
Списки
Со списками мы уже сталкивались - при разговоре о множествах и функциях. Для того чтобы определить список шаблонов, нужно записать эти шаблоны через запятую. При этом входные данные, удовлетворяющие такому шаблону, должны представлять собой набор из того же числа элементов, что и список, причём каждый элемент набора должен удовлетворять соответствующему шаблону. Операция похожа на конкатенацию, но определённые отличия есть.
(A_1, …, A_n)(∝) ≡ ∝ = (β_1, …, β_n), A_i (β_i ), i = 1 … n ( 16 )
Дополнительные конструкции языка
В связи с производственной необходимостью в язык были добавлены следующие шаблоны:
1) ^ - обозначает начало строки, не ассоциируясь при этом ни с каким конкретным элементом входной цепочки;
2) $ - обозначает конец строки (действует аналогично).
Продолжение следует.
Описание конкретных элементов уже позволяет, конечно, описывать ряд цепочек, но выразительности этих конструкций определённо не хватает. С их помощью можно явно перечислить некоторые цепочки, но возникает необходимость описывать наборы цепочек одним шаблоном.
Очень часто при описании предикатов для цепочек необходимо указать не наличие в цепочке какого-то конкретного элемента, а элемента из некоторого множества. Одновременно с этим очень часто условия на разные символы в разных цепочках оказываются одинаковыми, и в этом случае также удобно объявить множество цепочек, для которых истинно некоторое условие.
:= ∝ <=>A(x)= x∈ ∝, ( 11 )
где - имя множества в угловых скобках,
∝ - определение множества в виде шаблона,
A(x) - предикат, определяемый множеством.
Итак, множество представляет собой полноценный аналог предиката. По сути дела, оно задаёт предикат принадлежности к себе (т. е. предикат истинен только для элементов данного множества). В то же время, любой предикат порождает множество, в которое входят те цепочки, для которых он истинен. Имя множества указывается в угловых скобках. В определении множества оно указывается в левой части определения, далее следует знак «:=» и после него формируется шаблон-предикат, определяющий множество. После этого множество можно указывать в качестве элемента шаблонной цепочки.
Пример описания цепочек из двух одинаковых подцепочек с помощью множеств.
:= abcd
:=
⇒ := abcdabcd
Итак,
(∝) ≡ Def(A, P), P(∝), ( 12 )
где Def(X,Y) :="Y является определением X\" (т. е. в файле существует строка : = Y)"
Как и предикаты Пролога, множества могут быть параметризованы. Параметры при вставке множества могут унифицироваться как в строке шаблона, содержащей множество, так и в его определении.
Параметры перечисляются через запятую и указываются в имени множества. В шаблонной строке параметры указываются так же, как и переменные, в квадратных скобках. Если параметр унифицируется с элементом входной цепочки, он указывается без дополнительных знаков. Если его надо унифицировать с чем-то ещё, параметр указывается с символом равенства, а после параметра записывается элемент, с которыми происходит унификация.
≔ [Value=]0|1|2|3|4|5|6|7|8|9
≔
≔ [L = l * 10][Val = DVal * l + NVal]
Определения множеств записываются отдельными строками наряду со строками правил преобразования. Интерпретатор отличит определения от правил по наличию в них конструкции «:=».
Метасимволы
Зачастую бывает удобно описывать повторяющиеся конструкции символов с помощью некоторой сокращённой записи. Для таких целей используются метасимволы, записываемые после элемента, к которому они применяются. Вот примеры таких метасимволов и тех строк, которые будут вместо них подставлены интерпретатором:
X? ≡ |X (элемент встречается 0 или 1 раз) ( 13 )
X:(a, b) ≡ [n ≥ a][n ≤ b] (элемент встречается от a до b раз) ( 14 )
Один из параметров a или b (вместе с запятой) можно опускать. В данной версии интерпретатора эта языковая возможность не реализована.
X* ≡ (элемент встречается любое число раз подряд (включая 0)), ( 15 )
X+ ≡ [n≥1] (элемент встречается любое число раз подряд),
где
≔
:= [Y][k = k1 + 1]
Функции
Некоторую последовательность операций удобно определить как функцию, которую можно будет легко вызывать внутри шаблонов. В отличие от множеств, основное требование для вызова функции - полная определённость всех параметров в момент обращения к ней. Функция может вернуть любое значение (не обязательно истину или ложь).
Вот пример функции, суммирующей входную последовательность цифр:
sum ≔ => 0
sum ≔ [X=]x[Y=]α[Z = X + @(sum,Y) ] => [Z]
Функция определяется при помощи строки, содержащей её имя, знак определения («:=»), далее - список входных данных, знак преобразования (=>) и, наконец, список выходных данных. Список входных данных теоретически может быть пустым.
Аналогичным образом вычисляется длина цепочки:
length ≔ => 0
length ≔ x[A=]α[L = @(length,α) ][R = L + 1] => [R]
Вызов функции, как вы уже заметили, начинается с «собачки». Далее через запятую указываются имя функции и её аргументы (это сделано для упрощения анализатора, да).
Фактически вызов функции приводит к запуску внутреннего преобразователя, работающего по собственным правилам. Результат внутреннего преобразователя используется для дальнейшей работы внешнего.
Определять функцию можно произвольное число раз. При этом каждое определение может содержать свой шаблон для описания работы функции.
Существуют предопределённые функции, которые не нужно описывать. Эти функции позволяют конструировать новые элементы, а также делать многое другое.
Списки
Со списками мы уже сталкивались - при разговоре о множествах и функциях. Для того чтобы определить список шаблонов, нужно записать эти шаблоны через запятую. При этом входные данные, удовлетворяющие такому шаблону, должны представлять собой набор из того же числа элементов, что и список, причём каждый элемент набора должен удовлетворять соответствующему шаблону. Операция похожа на конкатенацию, но определённые отличия есть.
(A_1, …, A_n)(∝) ≡ ∝ = (β_1, …, β_n), A_i (β_i ), i = 1 … n ( 16 )
Дополнительные конструкции языка
В связи с производственной необходимостью в язык были добавлены следующие шаблоны:
1) ^ - обозначает начало строки, не ассоциируясь при этом ни с каким конкретным элементом входной цепочки;
2) $ - обозначает конец строки (действует аналогично).
Продолжение следует.