В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 49

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 49)

в ПОЛИЗЕ из результатов перевода выделенных компонент. Когда действия этих

сортов переплетены некоторым нерегулярным способом, то планировать,

понимать, выполнять и проверять сложно. Чтобы уменьшить сложность, полезно

выделить две ключевых абстракции (два понятия): анализ исходной структуры и

синтез результирующей структуры, и предложить знаковую систему для их

взаимосвязанной конкретизации в рамках единой программы.

Тут уместно вспомнить язык нормальных алгоритмов Маркова (для

единообразия назовем этот язык моделью Маркова).

Охарактеризуем эту модель с точки зрения нашей концептуальной схемы.

Базис: единственный скалярный тип данных - литера; единственная

базисная операция - поиск-подстановка; единственная структура данных -

строка (текст); единственная структура операций - цикл по подстановкам.

Развитие: явных средств нет. Только моделированием.

Дальнейший анализ модели можно предложить в качестве упражнения.

В модели Маркова анализ структуры встроен в исполнитель и управляется

левой частью подстановки. Синтез структуры отделен от анализа - он

управляется правой частью подстановки. Исполнитель распознает тривиальную

структуру (слово), указанную слева, и заменяет ее столь же тривиальной

структурой (словом), указанной справа.

С точки зрения нашей задачи модель Маркова недостаточно развита. Дело в

том, что вид распознаваемых структур слишком тривиален. Хотелось бы

приблизить средства описания вида структур, например, к БНФ. Шаги в нужном

направлении сделаны в языке, созданном В.Ф.Турчиным в ИПМ АН СССР в 1966-68

гг. и названном им "Рефал" (рекурсивных функций алгоритмический язык). В

основу Рефала положены три модификации модели Маркова.

13.3.2. Модификации модели Маркова (введение в Рефал)

Изложим модель языка Рефал, особенно интересного с точки зрения нашей

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

средство для эффективного определения других языков (другими словами, как

базовый ЯП).

Первая модификация состоит в том, что в качестве (по-прежнему

единственной) базисной структуры данных вместо произвольной строки (слова)

используется "выражение" - строка, сбалансированная по скобкам.

Вторая модификация касается подстановки. Ее левая часть должна быть

так называемым функциональным термом с возможными переменными. Правая часть

должна быть выражением, в котором можно использовать переменные из левой

части подстановки (и только их).

Третья модификация касается поиска применимой подстановки. В отличие от

модели Маркова, где заранее не фиксируется заменяемая часть обрабатываемого

слова, в Рефале заменяемая часть обрабатываемого выражения фиксируется

перед поиском применимой подстановки - это всегда так называемый ведущий

функциональный терм.

Применимой считается подстановка с минимальным номером, левая часть

которой согласуется с ведущим термом. Иными словами, применима такая

подстановка, в левой части которой указан общий вид структуры (образец),

частным случаем которой оказался ведущий терм.

Займемся теперь каждой из модификаций подробнее. Нам нужно уточнить

смысл слов "выражение", "ведущий функциональный терм", "переменная" и

"согласуется". Рассматриваемую модель ЯП назовем моделью Маркова-Турчина

(моделью МТ).

Строение выражений; поле зрения. Выделено три типа скобок - символьные

(открывающая ` и закрывающая ' кавычки), структурные (обычные круглые

скобки) и функциональные (мы будем использовать фигурные скобки "{" и "}"

).

Выражением называется всякая последовательность литер, сбалансированная

по всем трем типам скобок; термом - выражение в скобках либо совсем без

скобок; символом - отдельная литера либо последовательность литер в

символьных скобках.

Например,

(a+b) - выражение - структурный терм;

{a+b (c `АЛЬФА')} - выражение - функциональный терм;

`АЛЬФА' - символ, терм, выражение;

}ab{ - не выражение.

По существу, выражение - это линейное представление дерева - структура

этого вида часто используются в программировании именно потому, что наглядно

воплощает идею иерархии, частичного порядка, пошаговой (последовательной)

декомпозиции.

Дерево - это ориентированный граф (орграф) без циклов, в котором

выделена вершина, называемая корнем дерева, и в каждую вершину, кроме корня,

входит ровно одна дуга, причем из корня доступны все вершины. В дереве легко

вводятся уровни иерархии (по длине пути из корня).

Так, выражение {a+b(c `АЛЬФА' )} может быть представлено деревом вида

{ } 0-й уровень

/ \

a + b ( ) 1-й уровень

/ \

c ` ' 2-й уровень

/ \

А Л Ь Ф А 3-й уровень

Ведущим (функциональным) термом называется самый левый функциональный

терм, не содержащий других функциональных термов. В примерах ведущие термы

выделены.

(a+b{c+d}); { АЛЬФА (a*b)}{cd}x10

(100 DO 3 {I={1}(,3)}).

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

МТ-исполнителя (МТ-машины). В этом поле помещается обрабатываемый объект,

который может быть только выражением. В качестве очередной заменяемой части

всегда выбирается ведущий терм. Если такового нет, то считается, что делать

исполнителю нечего, и он останавливается.

Выражение, оставшееся в поле зрения, считается результатом выполнения

программы, находящейся в поле определений исполнителя.

[В авторской терминологии это поле называется "поле памяти". Так

говорить нам неудобно. В модели Н и программа, и данные находились в памяти.

Естественно считать, что поле зрения МТ-машины - также часть памяти. Термин

"поле определений" лучше отражает суть дела.]

Поле определений; МТ-предложения. [Мы изучаем модели ЯП. Поэтому будем

позволять себе "вариации на тему" рассматриваемого языка-прототипа, когда

такие вариации упрощают рассмотрение. Например, говоря о МТ-предложениях, мы

не будем строго следовать их авторской трактовке.]

В модели Маркова средства описания правил анализа и синтеза бедны -

можно лишь явно выписывать заменяемое и заменяющее подслова (левую и правую

части марковской формулы соответственно).

Основная идея обобщения марковской формулы состоит в том, чтобы за счет

введения локальных переменных наглядно изображать одной (обобщенной)

формулой сразу целый класс подстановок (применимых к функциональным термам

определенной структуры).

Ключевыми понятиями при этом служат интерпретация переменных и

согласование (терма с обобщенной подстановкой при определенной интерпретации

ее переменных).

Интерпретация переменных - это функция типа I:N->V, где N - множество

обозначений переменных, V - множество их допустимых значений.

[Интерпретация напоминает состояние в модели Н. Только вместо адресов -

обозначения переменных. Это по сути одно и то же. Но называем мы их по-

разному, так как они играют разные роли. Состояние в модели Н - глобальный

объект, сохраняющийся между последовательными операциями, а интерпретация в

модели МТ - локальный объект, действующий внутри операции подстановки.]

При конкретной интерпретации переменных обобщенная подстановка (в

Рефале ее называют предложением или Рефал-предложением) изображает

конкретную марковскую формулу подстановки.

Например, предложение

{10 e 00 s 1} -> s 101 e

где е и s - (локальные) переменные, при интерпретации

i1={e->00, s->11}

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

интерпретацию) изображает марковскую формулу

{100000111}-->1110100 ,

а при интерпретации

i2={e->ABC,s->D}

- марковскую формулу

{10ABC00D1}-->D101ABC.

Соответственно левая часть предложения изображает левую часть

марковской формулы, а правая часть предложения - правую часть формулы.

Согласование - это тройка (t,i,s), где t - ведущий терм, s -

предложение и i - интерпретация, при которой левая часть s изображает t.

Итак, за счет различных интерпретаций переменных одна обобщенная

марковская подстановка (предложение) способна изображать целый класс

марковских подстановок (что и требовалось).

Однако этот класс не должен быть слишком широким. Ведь каждое

предложение должно быть приспособлено для (наглядного) изображения вполне

определенного содержательного преобразования поля зрения. Поэтому следует

принять меры к тому, чтобы ,во-первых, изображаемые подстановки не

нарушали структуру поля зрения и, во-вторых, чтобы можно было управлять

допустимыми значениями переменных (другими словами, управлять их типом).

Наконец, в-третьих, необходимо установить такие правила согласования

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

что правила согласования должны обеспечивать единственность подразумеваемой

программистом согласующей интерпретации (при фиксированном поле зрения).

Первое и второе достигается за счет ограничений на класс допустимых

интерпретаций, третье - за счет ограничений на класс допустимых

согласований.

Допустимые интерпретации должны удовлетворять двум условиям:

значения переменных, а также обе части изображаемой подстановки должны

быть выражениями (так что МТ-преобразования не выводят за класс выражений);

значение переменной должно соответствовать спецификатору, который

указывается непосредственно после обозначения переменной и отделяеется

двоеточием ":".

[Понятие спецификатора связано с еще одним (в некотором смысле

ортогональным) направлением обобщения марковской формулы подстановки. Это

направление мы оставим открытым и будем использовать пока только очень

простые спецификаторы. Именно, в качестве спецификатора можно написать

"символ" или "терм" (это значит, что значениями переменной могут быть только

символы (только термы)) или в круглых скобках можно явно перечислить

допустимые значения переменной.

Например, s:символ - переменная, значениями которой могут быть только

символы, t:терм - только термы, s:(+I-) - значениями s могут быть только

литеры "+" или "-". ]

Ограничения на согласования состоят в том, что допустимыми считаются

только так называемые ориентированные согласования. Они бывают левыми или

правыми.

Определим левое (левоориентированное) согласование. Правое определяется

по симметричным правилам.

Будем называть переменную y1 в функциональном терме левой для

переменной y2, если самое левое вхождение y1 расположено левее самого левого

вхождения переменной y2.

Будем говорить, что согласование (t,i',s) короче согласования (t,i,s),

если в t найдется переменная y1, для которой i'(y1) короче i(y1), причем для

любой переменной z, левой для y1 в терме t, i'(z) совпадает с i(z).

Согласование (t,i,s) называется левым, если оно самое короткое из

возможных согласований t и s.

Таким образом, основная идея левого согласования - левые переменные при

поиске согласующей интерпретации удлиняются в последнюю очередь.

По умолчанию предполагается, что допустимы только левые согласования.

Допустимость только правых согласований указывается буквой R после

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

Например, предложение

{e1+e2}-->{e1}{e2}+

согласуется с термом {a+b+c+d} интерпретацией

{e1-->a, e2-->b+c+d}

и изображает формулу подстановки

{a+b+c+d} --> {a}{b+c+d}+ ,

а предложение

{e1+e2}R --> {e1}{e2}+

согласуется с тем же термом интерпретацией

{e1-->a+b+c, e2-->d}

и изображает формулу подстановки

{a+b+c+d} -> {a+b+c}{d}+.

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

переменные от постоянных частей предложения. Если есть опасность спутать

переменную и постоянную, то постоянную будем выделять.

Характеристики

Список файлов книги