Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 46
Текст из файла (страница 46)
Булевы значения. Булевы значения моделируются как )ь-выражения следующим образом. Истина (ьгце. Т) определяетсякак; Лх.Лу х.(Понятьэтавыражениестанетлегче, если мы установим, что означает Истина: из пары значений следует выбрать первое. Это показано на примере, который мы рассмотрим позже.) ))оль (Ра)эе. Р) определяется как: Лх.
Лу.у. (Из пары значений следует выбрать второе.) Используя определения этих объектов, мы получаем, что следующие свойства истинны: «т Р)0) Р, то есть «Т Р)О) = «Лх Лу.х Р)0) = (Лу Р 0) Р; «Р Р)0)=т О. то ест. « Р Р)0) ~ «Лх Лу.у Р)0) ~ (Лу у О) =т О. Имея определения для констант Т и Р, можно определить следующие логические функции: ног (логическое отриццние) алз (коньюнкцил) ог (дизьюнкция) 164 Глава 4. Моделирование свойств языка Теперь нам предстоит показать, что наша интерпретация булевых значений согласуется с правилами логики прсдикатов. Например, применение функции пег к т (истина) должно дать Г (ложь), и наоборот.
Действительно, (пот Т) - (Лх.((х Г)Т)Т) =х ((Т Г)Т) ~ Г; (пот Г) (Лх.((х Г)Т)Г) ~ ((Г Г)Т) =х Т. Можно показать аналогичным образом, что определенные нами функции и и или также обладают всеми необходимыми свойствами данных логических операций. Целые числа. Используя определенные нами булсвы функции, можно перейти к определению целых чисел: 0 ЛГ.Лс.с ) - Л(.Лс.((с) 2 = Лг Лс.(((гс)) 3 = Л(.)с.(Г(Т(тс))) Здесь с соответствует нулевому элементу, а Т вЂ” это функция, последовательно добавляющая к с единицу, С помон(ью этих определений можно определить обычныс арифметические операции: целое число И записывается посредством Л-выражения как (И а), то есть Лс, (а.,(а с)...).
Применяя редукцию к ((И а)Ь), мы получаем (а..(а Ь)...). Рассмотрим Х-выражение ((М а)((И а)Ы), применив константу ((И а)Ы к Л-выражению (М а). Подстановка ((И а)Ы вместо с в (М а) дает (а..(а Ь)..), при тсм теперь уже в этом списке присутствует (М+И) символов а. Таким образом, мы только что показали, что Х-выражения можно скла((ыватги (М+И) - Ла.)Щ(М в)((И а)Ы) Иначе говоря, мы определили операцию + как + = ЛМ,ЛМ,Лв.ЛЬ.((М в)((И З)Ь)) Аналогичным образом можно показать, что Уиноиение (М х И) - Ла.(М(И а)) Возведение в степен~ (М') = (И М) Продолжая в том жс духе, мы можем определить все вычислимые математические функции. Однако давайте применим эти идеи к семантике языков программирования.
Моделирование языков программирования Используя полученные сведения о Л-выражениях, можно пойти дальшс и применить Л-выражения к моделированию типов данных; после этого мы можем сделать следующий шаг и получить модель, включающую также и семантику языков программирования.
Когда к Х-выражению применяется операция редукции, оно сводится либо к некоторым константам, либо к другим Л-выражсниявт. Таким образом, все Л-вьтражсния являются решениями следующего функционального уравнения; Х-выражение - константа+ (Л-выражение =о Л-выражение). Нс углубляясь в детали дснотационной семантики, мы просто констатируем, что тип данных — это решение такого уравнения. Заметим, однако, что между этой формальной моделью типа данных и определениями типов в языке Мг. имеется 4,2. Семантика языка 165 прямое соответствие. А именно список целых чисел (конструктор йу)т зб) определяется в МВ следующим образом: вататуре Ну1~вт = чаг от тпг ) 1твгтбея ОГ тпг * Ну1твг; Здесь используются конструкторы чаг и 1тзбт бее, по свосму назначению аналогичные )с-выражениям.
С помощью этой концепции мы можем определить модель деттотационной сематттиики простого языка программирования. Эта модель является разновидностью операционной семантики, поскольку мы прослеживаем выполнение каждого типа операторов, чтобы определить его воздействие на интерпретатор более высокого уровня. Однако в отличие от традиционных интерпретаторов, которые описаны в главе 2, мы рассматриваем программу как некоторую функцию аналогично ранней трактовке ) -ттсчисления, Каждый оператор языка — это функция, и мы моделируем выполнен не последовательных операторов, определяя, какой вид должна иметь композиция функций для двух операторов.
Для каждого типа операторов (5йпб) можно написать уравнение определения типа данных: 5габ = Г!О х Гхр) Областв операторов присваивания Ы 5ггб х 5гпц ) Областв послелователвностей Ы Гхр х 5гяг х 5свг) Область условных операторов Ы Гир х 5СФС) Областв итераций Как в случае с любым интерпретатором, нам необходимо представлять себе его виртуальный компьютер, В данном случае мы предполагаем, что каждый идентификатор ссылается па определенную область памяти.
В этом простом примере мы не используем замещение имен, передачу параметров и указатели. Следовательно, каждому идентификатору соответствует некая область памяти, в которой содержится значение этого идентификатора. Иначе говоря, мы можем моделировать нашу концепцию памяти функцией, которая для каждого идентификатора возвращает его значение. Такую функцию мы будем называть лалтлтью. Итак, память для программы — это функция, сопоставляющая каждой ее области (или идентификатору) соответствующее значение. Тогда результат выполнения оператора можно представить как некоторую модификацию памяти, Мы имеем новую функцию (аналогичную предыдущей), которая теперь сопоставляет каждому идентификатору некое значение, которое может совпадать или не совпадать с предыдущим, Таким образом, выполнение оператора мы рассматриваем как суперпозицию двух функций: функции, ттредставляютгтей память, и функции, которая описывает выполнение данного оператора.
Мы расс магри наем память как отображение идентификаторов на область значений, хранящихся в памяти, и записываем это с помощью сигнатуры вида т0 — а ча1це, где тб — это множество идентификаторов данного языка, а ча1це — множество их значений, Мы называем это сосвтояниеяв программы. При определении семантики языка программирования нам следует представить три основные функции. 1. Необходимо описать семантику л)тогралсны. В данном случае синтаксис программы определяет функцию, которая, вообще говоря, сопоставляет неко- 1бб Глава 4.
Моделирование свойств языка торому числу какое-то иное число. Другими словами, мы ищем функцию Н с сигнатурой н . ргор -х Епож -+ поп) 2. Необходимо описать оператор языка, Каждый оператор отображает данное состояние в другое, то есть С : втжс -х Евгасе -я всасе) Эта запись означает, что каждый синтаксический оператор вглтг представляет собой функцию, сопоставляющую одному состоянию всасе программы другое состояние в гасе.
Следовательно, каждый конкретный оператор берет данное состояние программы (то есть отображение из области идентификаторов на область их значений) и производит новое отображение идентификаторов на их значения, являющееся результатом действия всех предылущих операторов, включая и тот, о котором идет речь. 3. Функция С, описывающая действие оператора, зависит от значений различных выражений, поэтому нам необходимо понимать процесс вычисления выражений в рассматриваемом языке.
Любое выражение — это набор синтаксических единиц, в том числе идентификаторов, каждому из которых сопоставлено некое значение в соответствующей области памяти. Таким образом, для данного выражения сопоставление набора входящих в него идентификаторов и других синтаксических единиц с набором значений этих идентификаторов позволяет получить значение этого выражения. Тогда для вычисления выражений мы получаем следующую сигнатуру: Е : ехр -+ Еэгаге -х еча1) В качестве простого примера рассмотрим вычисление выражения ехр, представляющего собой сложение двух величин а+Ь, Тогда функция Е для вычисления выражения такова: ЕЕаяЫ; вваве — я еча1.
применение этой функции к состоянию в дает функцию ЕЕа ° Ысв) - атв) + щв) Обычно пишется не Е( а+Ы, а Е((а+Ь) ), то есть синтаксические аргументы помещаются не в круглые скобки, а в фигурные. Теперь мы можем моделировать области для нашего языка программирования: агаве = тл -х ча1не состояния програнны 10 илентифинаторы ча1ое = еча1 зна~ения еча) - пож + Ьао1 значения выражений пож целые числа Ьоо1 булевы значения ехр выражения всжс операторы Для того чтобы определить язык, нужно определить функцию типа в Еа Ее а втасе для каждого типа синтаксических операторов. Для удобочитаемости мы используем ) -подобттуто конструкцию 1ег (аналогичную конструкции 1ет в языке МЕ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
