Денотационная семантика

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

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

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

• 1 Историческое развитие
  • 1.1 Значения рекурсивных программ
  • 1.2 Денотационная семантика недетерминированных программ
  • 1.3 Денотационная семантика параллелизма
  • 1.4 Денотационная семантика состояния
  • 1.5 Обозначения типов данных
  • 1.6 Денотационная семантика для программ ограниченной сложности
  • 1.7 Денотационная семантика последовательности
  • 1.8 Денотационная семантика как перевод из источника в источник
• 2 Абстракция
• 3 Композиционность
• 4 Семантика в сравнении с реализацией
• 5 Связь с другими областями информатики
• 6 Ссылки
• 7 Дополнительная литература
• 8 Внешние ссылки

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

Денотационная семантика имеет был разработан для современных языков программирования, которые используют такие возможности, как concurrency и исключения, например, Concurrent ML, CSP и Haskell. Семантика этих языков является композиционной, поскольку значение фразы зависит от значений ее подфраз. Например, значение аппликативного выражения f (E1, E2) определяется в терминах семантики его подфраз f, E1 и E2. В современном языке программирования E1 и E2 могут оцениваться одновременно, и выполнение одного из них может повлиять на другой, взаимодействуя через общие объекты, что приводит к определению их значений в терминах друг друга. Кроме того, E1 или E2 могут вызвать исключение, которое может прервать выполнение другого. В следующих разделах описываются частные случаи семантики этих современных языков программирования.

Значения рекурсивных программ

Денотационная семантика приписывается программной фразе как функции от среды (хранящей текущие значения ее свободных переменных) до ее обозначения. Например, фраза n * mсоздает обозначение, если предоставляется в среде, которая имеет привязку для двух своих свободных переменных: nи m. Если в среде nимеет значение 3, а mимеет значение 5, то обозначение равно 15.

Функция может быть представлена ​​как набор упорядоченные пары аргумента и соответствующих значений результата. Например, набор {(0,1), (4,3)} обозначает функцию с результатом 1 для аргумента 0, результатом 3 для аргумента 4 и неопределенным в противном случае.

Проблема, которая должна быть решена, состоит в том, чтобы предоставить значения для рекурсивных программ, которые определены в терминах самих себя, например, определение функции factorial как

int factorial (int n) { если (n == 0), то верните 1; иначе вернуть n * факториал (n-1); }

Решение состоит в том, чтобы придать значения приближенным значениям. Факториальная функция - это общая функция от ℕ до ℕ (определенная везде в своей области), но мы моделируем ее как частичную функцию. Вначале мы начинаем с пустой функции (пустой набор). Затем мы добавляем упорядоченную пару (0,1) к функции, чтобы получить другую частичную функцию, которая лучше аппроксимирует факториальную функцию. После этого мы добавляем еще одну упорядоченную пару (1,1), чтобы создать еще лучшее приближение.

Поучительно представить эту цепочку итераций для "частичной факториальной функции" F как F, F, F,... где F означает F, примененный n раз.

• F ({ }) - полностью неопределенная частичная функция, представленная как набор {};
• F ({}) - это частичная функция, представленная как набор {(0,1)}: она определена в 0, чтобы быть 1 и не определено в другом месте;
• F ({}) - это частичная функция, представленная как набор {(0,1), (1,1), (2,2), (3,6), (4,24)}: он определен для аргументов 0,1,2,3,4.

Этот итерационный процесс строит последовательность частичных функций от ℕ до ℕ. Частичные функции образуют частичный порядок с полной цепочкой с использованием ⊆ в качестве порядка. Кроме того, этот итерационный процесс лучших приближений факториальной функции формирует расширяющее (также называемое прогрессивным) отображение, потому что каждое $F\; i\; \le \; F\; i\; +\; 1\; \{\backslash \; displaystyle\; F\; ^\; \{i\}\; \backslash \; leq\; F\; ^\; \{i\; +\; 1\}\; \}$с использованием ⊆ в качестве порядка. Таким образом, согласно теореме о неподвижной точке (в частности, теореме Бурбаки – Витта ), существует фиксированная точка для этого итерационного процесса.

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

$⨆\; i\; \in \; NF\; i\; (\{\}).\; \{\backslash \; displaystyle\; \backslash \; bigsqcup\; \_\; \{i\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}\; F\; ^\; \{i\}\; (\backslash \; \{\backslash \}).\}$

Здесь символ «⊔» означает (из направленных множеств ), что означает «наименьшая верхняя граница». Направленное соединение - это, по сути, соединение направленных наборов.

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

Концепция областей власти была разработана для придания денотационной семантики недетерминированным последовательным программам. Написав P для конструктора степенной области, область P (D) является областью недетерминированных вычислений типа, обозначенного D.

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

Денотационная семантика параллелизма

Многие исследователи утверждали, что теоретико-предметные модели, приведенные выше, не подходят для более общего случая параллельных вычислений. По этой причине были представлены различные новые модели. В начале 1980-х люди начали использовать стиль денотационной семантики, чтобы дать семантику для параллельных языков. Примеры включают работу Уилла Клингера с моделью актера ; Работа Глинна Винскеля со структурами событий и сетями Петри ; и работа Francez, Hoare, Lehmann и de Roever (1979) по семантике трассировки для CSP. Все эти направления исследований остаются в стадии исследования (см., Например, различные денотационные модели для CSP).

Недавно Винскель и другие предложили категорию профункторов в качестве предметной теории для параллелизма.

Денотационная семантика состояния

Состояние (например, куча) и простые императивные функции могут быть напрямую смоделированы в денотационной семантике, описанной выше. Все учебники ниже содержат подробности. Ключевая идея - рассматривать команду как частичную функцию в некоторой области состояний. Значение «x: = 3» - это функция, которая переводит состояние в состояние с 3, присвоенным x. Оператор последовательности «;» обозначается композицией функций. Затем используются конструкции с фиксированной точкой для придания семантики конструкциям цикла, например «while».

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

Обозначения типов данных

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

datatype list = Cons of nat * list | Пусто

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

Другой пример: тип обозначений нетипизированного лямбда-исчисления - это

тип данных D = D из (D → D)

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

Полиморфные типы данных - это типы данных, которые определяются с помощью параметра. Например, тип α lists определяется

типом данных α list = Cons of α * α list | Пустой

Списки натуральных чисел, таким образом, относятся к типу nat list, а списки строк - к списку строк.

Некоторые исследователи разработали теоретико-предметные модели полиморфизма. Другие исследователи также смоделировали параметрический полиморфизм в рамках теорий конструктивных множеств. Подробности можно найти в перечисленных ниже учебниках.

Недавняя область исследований включала денотационную семантику для языков программирования на основе объектов и классов.

Денотационная семантика для программ ограниченной сложности

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

Денотационная семантика последовательности

Проблема полной абстракции для языка последовательного программирования PCF долгое время была большим открытым вопросом в денотационной семантике. Проблема с PCF в том, что это очень последовательный язык. Например, в PCF невозможно определить функцию parallel- или. Именно по этой причине подход с использованием доменов, представленный выше, дает денотационную семантику, которая не является полностью абстрактной.

Этот открытый вопрос был решен в основном в 1990-х годах с развитием семантики игры, а также с помощью методов, включающих логические отношения. Подробнее см. Страницу в PCF.

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

Часто бывает полезно перевести один язык программирования на другой. Например, язык параллельного программирования может быть переведен в исчисление процессов ; язык программирования высокого уровня может быть переведен в байт-код. (Действительно, обычную денотационную семантику можно рассматривать как интерпретацию языков программирования на внутренний язык категории доменов.)

В этом контексте понятия денотационной семантики, такие как полная абстракция, помогает решить проблемы безопасности.

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

1. Синтаксическая независимость : обозначения программ не должны включать синтаксис исходного языка.
2. Адекватность (или надежность) : все наблюдаемые отличные программы имеют разные обозначения;
3. Полная абстракция : Все эквивалентные с точки зрения наблюдения программы имеют одинаковые обозначения.

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

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

1. Конструктивизм : Конструктивизм связан с тем, можно ли показать, что элементы предметной области существуют конструктивными методами..
2. Независимость денотационной и операционной семантики : денотационная семантика должна быть формализована с использованием математических структур, которые не зависят от операционной семантики языка программирования; Однако основные концепции могут быть тесно связаны. См. Раздел Композиционность ниже.
3. Полная полнота или определимость : каждый морфизм семантической модели должен быть обозначением программы.

Важным аспектом денотационной семантики языков программирования является композиционность, с помощью которой обозначение программы строится из обозначений ее частей. Например, рассмотрим выражение «7 + 4». Композиционность в данном случае должна обеспечивать значение «7 + 4» в терминах значений «7», «4» и «+».

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

1. Мы начинаем с описания значения типов нашего языка: значение каждого типа должно быть областью. Обозначим через τ〛 область, обозначающую тип τ. Например, значение типа natдолжно быть областью натуральных чисел: 〚nat〛 = ℕ ⊥.
2. Из значения типов мы получаем значение для типизации контекстов. Положим 〚x 1:τ1,..., x n:τn〛 = 〚τ 1 〛 ×... × 〚τ n 〛. Например, 〚x: nat, y: nat>〛 = ℕ ⊥×ℕ⊥. В качестве особого случая значение пустого контекста типизации без переменных - это домен с одним элементом, обозначенным 1.
3. Наконец, мы должны придать значение каждому фрагменту программы-при-типе- контекст. Предположим, что P - фрагмент программы типа σ, в контексте ввода Γ, который часто пишется как Γ⊢P: σ. Тогда смысл этой программы-в-контексте-типизации должен быть непрерывной функцией 〚Γ⊢P: σ〛: 〚Γ〛 → 〚σ〛. Например, 〚⊢7: nat〛: 1 → ℕ ⊥ - это постоянная функция «7», а 〚x: nat, y: nat⊢x + y: nat〛: ℕ ⊥×ℕ⊥→ℕ⊥- это функция, которая складывает два числа.

Теперь значение составного выражения (7 + 4) определяется составляя три функции 〚⊢7: nat〛: 1 → ℕ ⊥, 〚⊢4: nat〛: 1 → ℕ ⊥ и 〚x: nat, y: nat⊢x + y: nat〛: ℕ ⊥×ℕ⊥→ℕ⊥.

Фактически, это общая схема для композиционная денотационная семантика. Здесь нет ничего конкретного о доменах и непрерывных функциях. Вместо этого можно работать с другой категорией. Например, в семантике игр категория игр включает игры как объекты, а стратегии как морфизмы: мы можем интерпретировать типы как игры, а программы как стратегии. Для простого языка без общей рекурсии мы можем обойтись категорией наборов и функций . Для языка с побочными эффектами мы можем работать в категории Kleisli для монады. Для языка с состоянием мы можем работать в категории функторов . Милнер выступал за моделирование местоположения и взаимодействия, работая в категории с интерфейсами как объектами и биграфами как морфизмами.

Согласно Дана Скотт (1980):

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

Согласно Клингеру (1981):

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

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

Учебники

Примечания к лекциям

Другие ссылки

В Wikibook Haskell есть страница по теме: Денотационная семантика

• Денотационная семантика. Обзор книги Ллойда Эллисона
• Шрейнер, Вольфганг (1995). «Структура языков программирования I: денотационная семантика». Примечания к курсу.