Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 45
Текст из файла (страница 45)
Правило Атрибут <пес!агат)оп>: = <Оес1><аес!агагтоп> Оес1 зет(сес1ага11опг) - бес) паве!пес)) кеес! за 1!бес!а пат ! опт ) Оес1 зет!Оес1агаттоп) = Оес1 папе!Оес1) Оес1 паве!пес!) - х оес! папе!Оес!) = у Оес1 папеИес)) = г <Еес1агат1оп> ; = <Оес1> <Оес1>::= ттео!вге х <Оес1> :.= ттео!аге у <Оес1>:.= цео!его г Синтезированный атрибут бес! зе1, связанный с нетерминальным символом <!)ее!агат! оп>, всегда содержит множество имен, объявленных в данной программе. Этот атрибут можно передавать вниз по дереву через унаследованный атрибут и использовать при генерации кода для введенных данных. Бели в грамматике имеются только синтезированные атрибуты (как в приведенном выше примере), то компилятор может вычислить их в момент генерации 160 Глава 4.
Моделирование свойств языка ! Р 2 ! 1 4.2. Семантика языка 161 дерева синтаксического разбора на соответствуюшем этапе трансляции. Так работают системы, подобные г'АСС. Каждый раз, когда г'АСС определяет, какое применить правило (продукцию) НФБ-грамматики, выполняется подпрограмма (например, атрибутивная функция), которая дополняет дерево синтаксического разбора семантической информацией. 4.2.2. Денотационная семантика Денотационная семантика — это формальная аппликативная модель для описания семантики языков программирования. Прежде чем обсуждать денотационную семантику, введем понятие Х-исчисления, которое представляет собой более простую функциональную модель, разработанную еще в 30-е гг. как способ объяснения математических вычислений.
На основе Х-исчисления могут быть построены более сложные структуры, включая концепцию типов данных и семантику языков программирования. Далее в этой главе (в разделе 4.2.3) мы опишем язык МЕ как пример функционального языка, основанного на некоторой функциональной разновидности денотационной семантики. Л-исчисление Возможно, самой первой моделью семантики языка программирования было Л-исчисление, предложенное в 30-х гг. А.
Черчем в качестве теоретической модели вычислений, сопоставимой с машиной Тьюринга (см. раздел 4тй3). Оказалось, что Л-исчисление хорошо моделирует вызов функций в языках программирования, хотя его появление опередило самые первые компьютеры на несколько лет, а язътки программирования — на пятнадцать. Фактически семантика обращения к функциям в языках АЕООЕ и ЫБР унаследована от Х-исчисления; механизм подстановки в Х-исчислении является прямым отображением определенного в языке А1.ООЕ механизма передачи параметра по имени (см.
раздел 9,3), Скотт 198] расширил эту модель, превратив ее в общую теорию типов данных, которая сегодня известна под названием денптационнай семантики. Система обозначений, принятая в денотационной семантике, оказала влияние на разработку теории типов данных в языке МЕ.
Полное описание Л-исчислеттия и денотационной семантики не входит в задачу авторов этой книги; тем не менее мы хотели бы представить краткий обзор этих концепций и показать их связь с разработкой языков программирования. Л-выражения определяются рекурсивно при помощи следующих правил: !. Если х является именем переменной, то х является Л-выражением. 2. Если й является Х-выражением, то Лх.
М является Х-выражением. 3. Если Г и д являются Х-выражепиями, то (ГА) — также Х-выражение. Здесь à — это оператор, а гт — операнд. Х-выражения можно определить и при помощи контекстно-свободной грамматики; Л выражение -в идентифинатар ! Лилентифинатор.Л выражение ) (Л выражение Л выражение) Далее приведены примеры Х-выражений, сгенерированных этой грамматикой: 162 Главав.
Моделирование свойств языка х >х х Лх.у Лх.(ху> (Лх (хх)Лх.(хх)> Лх.Лу.х Переменные могут быть связанными или свободными. Интуитивно понятно, что связанная переменная — это локально объявленная переменная, а свободная переменная не имеет никакого объявления. Переменная х в Л-выражении х является свободной переменной. Если х в М является свободной, то в Лх. М она связана.
Переменная х является свободной в (Г А), если она свободна в Г или в А. Имя любой связанной переменной можно поменять так же, как имена параметров функций. Так, Л-выражение Лх.х эквивалентно Лу у, Л-выражение Лх.Лх.х эквивалентно Лх. Лу у, поскольку переменная х связана с самым правым Лх. Неформально можно сказать, что связанные переменные являются параметрами функции, описываемой Л-выражением; свободные же переменные являются глобальными.
Эта аналогия показывает, что Л-выражение просто ап проке ими рует концепцию процедур и подпрограмм для большинства алгоритмических языков типа Рааса), С, РОКТКАХ или А()а Операции над Х-выражениями Для Л-выражений определена только одна операция — операция )авду(охни. Если (Р А) — Л-выражение и Р = Лх. М, то во всех случаях, где в М встречается свободная переменная х, вместо нее можно подставить Л Записывается это следующим образом: (Лх. М А) ~ М'. Эта операция аналогична подстановке фактического параметра вместо формального параметра в вызове функции.
Ниже приведены некоторые примеры редукции в Л-выражениях: (Лх х у) ~У (Лх.(ху) у) =~ (>у) (Лх.(ху) Лх.х) =~ (Лх.х у) Ф у (Лх,(хх> Лх.(хх>) =~ гхх.(хх> Лх.(хх>) Заметим, что операция редукции не обязательно приводит к упрощению Л-выражения; четвертый пример иллюстрирует ситуацию, в которой редукция не завершается — иными словами, выражение пе редуцируется. Исследование этих примеров приводит нас к формулировке свойсгнва Черна-Россвра (>Соззег): если две различные редукции Л-выражения завершаются, то они являются членами одного класса значений, Иначе говоря, если для Л-выражения М имеются две редукции М =а Р иМ =а О,тосуществуетединственноеЛ-выраженией,такоечтоР ~ Ки 0 =а Р.
Выражение Р называется нормальной формой для класса значений, представителем которого является М. Передача параметров в Л-выражениях. Существует два стандартных подхода к редукции любого Л-выражения: 1) сначала редуцировать самый внутренний левый член; 2) сначала редуцировать самый внешний левый член. Например,вЛ-выражении(Лу (уу) (Лх (хх) а)) самыйвнешнийчлен — этовсе выражение, а самый внутренний — (Лх. (хх) а>. Здесь возможны две последовательности редукций.
+ Сначала редуцируется самый внешний член: (Лу (уу)(хх (хх>а» ~ ((Лх (хх) а>(Лх (хх> а)) =~ ((аа>(аа)> + Сначала редуцируется самый внутренний член; (Лу.(ух>(Лх.(хх>а» =~ ((Лу.(уу)(аа)> =~ ((аа)(аа)> 4.2. Семантика языка 163 Хотя ответы совпадают, редукция происходит по-разному: в первом случае функция (Лх. (хх) а) подставляется вместо параметра у и для каждогоэкземпляра у вычисляется значение этой функции. Такая редукция аналогична механизму вызова параметра по имени, описанному в разделе 9.3, Во втором случае сначала вычисляется значение константы (аа), которое затем подставляется вместо переменной у. Такая редукция представляет механизм вызова параметра по значению. Если имеется нормальная форма, то редукция, произведенная по первому способу (то есть аналогичная вызову по имени), сведется к этой форме; хотя, как было показано ранее, ни один из способов редукции не гарантирует ее завершение.
Вызов по имени — форма отложенного вычисления (см. раздел В.2.2), поэтому требуется вычислить только выражения, используемые в окончательном решении. При вызове по значению, напротив, вычисляются значения всех аргументов, даже если онн в итоге не будут использованы (например, в случае, если выражение не редуцируется). Приведенные выше редукции можно использовать для создания простых примеров выражений, которые редуцируются при испалъзовании первого способа (вызов по имени) и не редуцируются при использовании второго способа (вызов по значению).
Единственное, чта для этого нужно, — сконструировать нередуцируемое Л-выражение как аргумент, ссылки на который отсутствуют. Мы уже знаем, что выражение (Лх. (хх) Лх. (хх) ) не редуцируется, а на параметр у в выражении Лу.г, очевидно, отсутствуют ссылки. Следовательно, для выражения (Лу.г рах.(хх)Лх.(хх))) при исполъзонании редукции первого типа (вызон по имени) легко получить нормальную форму, которой является г; но если вы примените вызов по значению, то это выражение окажется нередуцируемым. = Лх. «хР)т): - Лх.) у.((ху)Р) = Лх.Лу.
« хТ)у) Моделирование математики при помощи Р),-выражений Л-исчисление изначально было создано как логическая модель нычислений. Можно использовать )ь-вгиражения для моделирования арифметики как мы ее понимаем. Сначала при помощи Л-выражеттий моделируется исчисление предикатов; затем на основе построенного исчисления предикатов можно моделировать целые числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
