Что составляет денотационную семантику?

45

В другом потоке Андрей Бауэр определил денотационную семантику как:

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

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

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

Поскольку в настоящее время большинство (все?) Формальных семантик имеют тенденцию быть структурными, является ли это обязательным определением?

Итак, мой вопрос: что такое денотационная семантика?

Охад Каммар
источник
4
Значение может быть дано во многих формах: предварительные условия, работа абстрактной машины, математическая сущность, игровая стратегия. Во всех современных подходах эти значения даны как функция значения частей.
Охад Каммар
1
Вопрос о существовании положил начало изучению теории области. Он вытекает из денотационного подхода, но не определяет его (например, рассматриваемый язык может даже не иметь функциональных пространств). Что касается модульности, как я уже говорил выше, в основном, каждый современный подход к семантике обладает композиционностью в подходящем смысле. [DD]D
Охад Каммар
10
Хорошо, пожалуйста, прекратите распространять ложное мнение, что инициировала или мотивировала теорию предметной области, потому что это не так. Дана Скотт хотела, чтобы теория предметной области была математической теорией, подходящей для типизированного -calculus. Тот факт, что он также дал модель нетипизированного -calculus, был случайностью . Я знаю, он сказал мне об этом. λ λ[DD]=D λλ
Андрей Бауэр
2
Спасибо за исправление. Я имел в виду, что в своей неопубликованной «Теоретической альтернативе типа ISWIM» он призвал отказаться от поиска и начал искать модели для типизированных -calculus. В процессе он обнаружил решение для вышеуказанного уравнения области. Таким образом, вопрос о том, не -наличие , который постулировал быть положительным (но оказался отрицательным), следовательно , привело к доменам инициированных теории домена. Я здесь тоже не прав? λ D [ D D ] D[DD]=DλD[DD]D
Охад Каммар
1
Не уверен, что это помогает, но то, как я вижу «текущую» работу денотационной семантики, это «компиляция языка в какую-то категорию» - действительно, вы могли бы написать семантику в терминах известных математических объектов, не настаивая на структуре категории, но это Достоверная характеристика конкретных примеров, с которыми я столкнулся.
Гаше

Ответы:

30

Различие, которое я лично делаю между денотационной и операционной семантикой, выглядит примерно так:

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

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

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

Марк Хаманн
источник
Хороший пример разницы между алгоритмическим и математическим подходом - это трактовка нетерминации. Обозначение цикла является нижним, но из-за проблемы остановки неразрешимо, является ли обозначение произвольной программы нижним. В семантике малых шагов вы можете наблюдать шаги сокращения, но теория не имеет «нижнего» значения. Неразрешимость и нетерминация переходят в метатеорию: неразрешимо то, заканчивается ли последовательность редукции. Точно так же в семантике большого шага неразрешимо, есть ли деривация.
Blaisorblade
23

Если бы я угадал, что скажет Дана Скотт, он, вероятно, сказал бы, что денотационная семантика является композиционной (подобно тому, что я утверждал) и что смысл программы должен быть подлинным математическим объектом, а не какой-либо синтаксической или формалистической сущностью. Конечно, такой взгляд требует дифференциации между формальным манипулированием синтаксисом и «истинной» математикой. Это обязательно нематематическое различие.

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

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

Андрей Бауэр
источник
3
Время от времени мне говорят, что переходные системы не так математичны, как домены, решетки или порядки. Я нахожу это представление сбивающим с толку. Все можно выразить в теории множеств ZFC.
Мартин Бергер
1
Рассмотрение того, насколько точно данная семантика может моделировать вычислительное явление, является более интересным подходом, и он действительно решающим образом зависит от выбранного понятия наблюдения. Одним из ключевых преимуществ операционной семантики (например, теории процессов) является именно то, что естественные понятия наблюдения гораздо легче определить по сравнению с теоретико-порядковой семантикой.
Мартин Бергер
3
@Marc: Я согласен с вами, что операционные методы не моделируют вычисления как функцию. Но я не понимаю, почему это делает теоретико-порядковые подходы «более математическими». Математика под влиянием физики, такая как дифференциальные уравнения, моделирует оценки определенных систем во времени. Подход ввода-вывода сам по себе использует элементарную временную структуру, а именно то, что вывод недоступен до ввода.
Мартин Бергер
2
@Martin: математики часто жалуются, что то, что делают физики, тоже не настоящая математика. ;-) Физика - это просто более комфортная наука на данный момент. TCS - все еще относительно новый ребенок на блоке. Я думаю, что TCS не следует беспокоиться о том, чтобы сделать людей в другой дисциплине (независимо от того, насколько нам лично это нравится) счастливыми; у нас есть свои собственные моджо на ходу (как физики).
Марк Хаманн
2
@Marc: произвольный мусор может быть выражен в ZFC, так что это не тот критерий, на который можно положиться. Семантика, в которой «функции» в языке программирования интерпретируются как функции в математическом смысле, имеет как минимум два преимущества. Во-первых, это хорошо согласуется с тем, как люди думают о функциях в языке программирования. Во-вторых, функции - это знакомые математические объекты, поэтому существует множество механизмов, которые можно использовать. Конечно, переходные системы тоже имеют свое применение.
Андрей Бауэр
19

Я согласен с тем, что отождествление денотационной семантики А. А. Бауэром с композиционностью (в « Книгах по семантике языка программирования» ) не очень хорошо характеризует то, что традиционно подразумевалось под денотационной семантикой, поскольку явно операционная семантика, а также логика программы (семантика аксиоматики) являются композиционными. ,

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

  1. Раньше было сложно рассуждать об операционной семантике.

  2. Раньше было трудно дать аксиомантическую семантику нетривиальным языкам.

Я бы сказал, что обе проблемы были в значительной степени улучшены, (1) например, с помощью методов, основанных на бисимилировании, исходя из теории процессов (которые можно рассматривать как специфическую форму операционной семантики), или, например, Питтс работает над операционной семантикой и программой эквивалентность, и (2) развитием, например, логики разделения или логики Хоара, полученной в виде типизированных версий логики Хеннеси-Милнера посредством встраивания языка программирования в типизированные -calculi.π

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

Мартин Бергер
источник
1
Если вспомнить мой последний пост, «денотационная семантика» должна сказать: «смысл этой нотации таков». «Оперативная» семантика и «аксиоматическая» семантика не являются семантическими определениями такого рода. Вводить их в заблуждение обманчиво. Отметим также, что то, что называется «оперативным подходом», является подходом к рассуждению о программах. Это не операционная семантика. Операционный подход и аксиоматический подход могут заменить инженерные приложения денотационной семантики. Но они не становятся денотационной семантикой.
Удай Редди
@Uday. Я не уверен, что это действительно существенная разница. Например, если я даю семантику языка композиционным переводом в -calculus, я назначаю каждой -программе процесс. То, что делает этот процесс, дается только оперативно. С логикой программы у вас часто есть характерные формулы (вычислимый синтаксис программы с индуктивной формой), которые фиксируют все поведение программы в паре формул. Как это не говорит "смысл этого обозначения таков"? π LLπL
Мартин Бергер
1
@Мартин. Почему назначение процессов композиционным способом не является денотационным. Может быть, если вы убедите всех нас, что процессы - это основополагающая теория, такая же, как теория множеств, и не следует спрашивать ее семантику. Я сочувствую мнению, что может существовать основополагающий язык, который моделирует вычисления с состоянием. Возможно, исчисление процесса какой-либо формы когда-нибудь будет принято за такое основание. Но я не думаю, что мы там еще.
Uday Reddy
1
@MartinBerger Это единственный, который я когда-либо узнал, но мне трудно сразу дать хорошую ссылку. Например, «Наконец, без тегов, частично оцененный» ( citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.99.9287 ) использует « сложение », «композиционный» и «примитивно-рекурсивный» во вступлении в качестве очевидных синонимов. (но это не обсуждается в статье, это воспринимается как должное). Viceversa, может показаться, что это философский вопрос, если верить Википедии здесь: en.wikipedia.org/wiki/Principle_of_compositionality#Critiques
Blaisorblade
1
@Blaisorblade Когда я был аспирантом, я общался с денотационными семантиками, потому что я должен был работать над денотационной семантикой. Я всегда спрашивал их, что такое денотационная семантика, могут ли они дать мне абстрактное определение, но я получил только уклончивые или расплывчатые ответы типа «денотационная семантика - математическая семантика», см. Также объяснение А. Бауэра. Я не думаю, что концепция четко определена. Я также не понимаю, почему требование, например, примитивной рекурсии, достаточно ограничивает, потому что сила примитивной рекурсии зависит от того, что еще доступно: (продолжение)
Мартин Бергер
16

Я доволен ответом Адрея, но я бы хотел продолжить.

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

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

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

Однако композиционные семантические определения с годами теряют свою остроту. Робин Милнер и Энди Питтс разработали ряд методов « оперативного мышления », которые работают исключительно над синтаксисом, но используют операционную семантику там, где это необходимо для разговора о поведении. Эти методы оперативного мышления являются низкотехнологичными. Нет фантазии математики. Нет бесконечных объектов. Мы можем научить их магистрантам, и каждый может их использовать. Поэтому многие люди задаются вопросом, зачем вообще нужна денотационная семантика. (Мартин Бергер, вероятно, находится в этом лагере.)

Лично у меня нет проблем с наличием множества инструментов в моем ящике для инструментов. Методы денотации могут быть лучше для одних задач, а методики для других. Исследователи, которые разрабатывают теорию, могут быть лучше настроены на тот или иной подход. Довольно часто мы можем выработать идеи в одном подходе и перенести эти идеи в другой подход. (Многие работы Энди Питтса такого рода. Реляционная параметрическость была разработана в денотационной обстановке, но он может понять, как переформулировать это как оперативное рассуждение. Когда я смотрю на это, я говорю: «Ух, я бы никогда думал, что это было бы возможно. "Логика разделения также идет по этому пути. Стив Брукс предоставил 60-страничное доказательство надежности для параллельной логики разделения с использованием денотационной семантики.

Операционные подходы также блестяще выигрывают, когда языки программирования становятся очень причудливыми со всеми видами зацикленных типов высшего порядка. Мы можем не знать, как математически моделировать такие вещи. Или стандартные математические модели могут оказаться несовместимыми в условиях цикличности. (Например, см. «Полиморфизм не является теоретико-множественным» Рейнольдса.) Операционные подходы, которые работают исключительно по синтаксису, могут аккуратно обойти все эти математические проблемы.

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

Итак, пусть будет здоровая конкуренция между денотационным, операционным и реализуемым подходами. Там нет никакого вреда.

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

Удай Редди
источник
Одним из конструктивных подходов к решению этой проблемы может быть поиск переводов между различными подходами.
Мартин Бергер
1
Обратите внимание, что у меня нет проблем с обычной денотационной семантикой как инструментом в наборе инструментов. Я просто нахожу неявные или явные предположения, что они как-то лучше проблематичны и не имеют последовательного обоснования.
Мартин Бергер
Я бы выставил тома «Алголоподобные языки» ( eecs.qmul.ac.uk/~ohearn/Algol/algol.html ), отредактированные Питером О'Хирном и Бобом Теннентом, как образец хорошей практики. Они включают в себя статьи о «традиционной денотационной семантике» (Strachey, Reynolds, Tennent, Meyer et al), а также «нетрадиционной» денотационной семантике (mine, Abramsky & McCusker, Brookes) и операционных подходах (Andy Pitts, Felleisen). Кстати, две работы Рейнольдса в томах («Логика спецификаций» и «Синтаксический контроль помех») были «аксиоматичными», когда они были написаны!
Удай Редди
1
Что касается здоровой конкуренции, одна из ключевых проблем заключается в том, что существует так много подходов, формализмов, исследователей и статей, что трудно идти в ногу с развитием. Как исследовательское сообщество, возможно, стоило бы приложить постоянные усилия для синтеза и унификации существующих подходов.
Мартин Бергер
2
@MartinBerger, отправной точкой, о которой я знаю, является статья Патрика Кузо «Конструктивное проектирование иерархии семантики», в которой показано, что очень широкий диапазон семантических моделей, включая переходные системы, аксиоматическую семантику, денотационные модели, может быть связан с помощью дополнений, следовательно рассматривается как разные абстракции.
Виджай Д
12

[Еще один ответ. Вероятно, не круто накапливать несколько ответов. Но, эй, это глубокая проблема.]

Я сказал, что согласен с ответом Андрея, но, похоже, я не совсем согласен. Есть разница.

Я сказал, что денотационная семантика должна сказать «смысл этой нотации таков». Я имел в виду, что обозначениям должны присваиваться значения, которые представляют собой некоторую форму концептуальных объектов, а не некоторые другие обозначения. Напротив, Андрей также требовал, перефразируя Скотта, что значения должны быть «математическими» объектами. Я не верю, что математический бит необходим.

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

С другой стороны, мы действительно еще не знаем, как говорить о физических процессах абстрактно. Таким образом, мы могли бы действительно использовать некоторое математическое описание процессов, чтобы сформулировать наши идеи. Но эти математические описания были бы просто «описаниями». Они не являются значениями. Реальные значения - это просто физические процессы, которые мы представляем концептуально.

В своей речи о присуждении награды SIGPLAN (которая скоро должна появиться на YouTube) Хоар сказал, что ACP использует «алгебраический подход», CSP использует «денотационный подход», а CCS использует «операционный подход» для описания процессов. Мы с Охадом сидели вместе на сессии, мы смотрели друг на друга и говорили: «Это действительно интересно». Итак, здесь много концептуального пространства, которое изучается. Я думаю, что многие последующие работы Скотта, посвященные системам соседства, информационным системам и т. Д., Действительно были попыткой объяснить функции как «процессы» некоторой формы. Геометрия взаимодействия Жирара и семантика поздних игр также являются попытками объяснить функции как процессы. Я бы сказал, что разработка основательной теории процессов могла бы стать большим вкладом, который информатика могла бы внести в математику XXI века. Я бы не принял убеждение, что у математики есть все ответы, и мы должны попытаться свести вычислительные явления к математическим понятиям, чтобы понять их.

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

Удай Редди
источник
10

[Надеюсь, это мой последний ответ на этот вопрос!]

Первоначальный вопрос Охада был о том, чем денотационная семантика отличается от структурной операционной семантики. Он думал, что они оба были композиционными. На самом деле, это не соответствует действительности. Структурная операционная семантика дана как последовательность шагов. Каждый шаг выражается композиционно (и Плоткин замечательно делает открытие, что это возможно!), Но все поведение не определяется композиционно. Вот что говорит Плоткин в своем вступлении к статье SOS [выделение добавлено]:

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

Тот факт, что каждый шаг выражается композиционно, не означает, что все поведение выражается композиционно.

Есть хорошая статья Карла Гюнтера под названием « Формы семантической спецификации» , в которой сравниваются и сравниваются различные методы определения семантики. Большая часть этого материала также воспроизведена в первой главе его текста «Семантика языков программирования». Это надо надеяться прояснить картину.

Еще одно слово об «операционной семантике». В первые дни термин «оперативный» использовался для обозначения любого семантического определения, которое ссылалось на подробные этапы оценки. И денотационные семантики, и сторонники аксиоматики смотрели свысока на «операционную» семантику, считая ее низкоуровневой и ориентированной на машины. Я думаю, что это было действительно основано на их убеждении, что описания более высокого уровня были возможны. Эти убеждения были разрушены, как только они рассмотрели параллелизм. Процессы де Баккера и Цукера и денотационная семантика параллелизма имеют следующие интересные отрывки:

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

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

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

Несмотря на все это, операционное понятие процесса все еще весьма отличается от денотационного понятия процесса, последнее из которого было разработано как де Баккером, так и Хоаром и их командами. И я думаю, что есть много загадочного и прекрасного в концепции денотационного процесса, которую еще предстоит понять.

Удай Редди
источник
Извините, что не ответил на запрос чата. Я очень занят в течение следующих двух недель. Спасибо, что написали это! Это первый технический ответ на странице, которую я понимаю.
Виджай Д
Я мог бы воспользоваться этой возможностью, чтобы подключить наш выпускник средней школы по теоретической информатике, который предназначен для решения всех этих проблем. Он открыт для всех аспирантов из любой точки мира.
Удай Редди
9

Этот дополнительный ответ призван усилить мысль о том, что денотационные семантические модели предназначены для «объяснения» вычислительных явлений. Я приведу ряд примеров из семантики императивных языков программирования (также называемых «алголоподобными» языками).

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

Рейнольдс сказал, что он не моделирует стековую дисциплину локальных переменных. Когда вводится локальная область, ее переменные распределяются, и они освобождаются при выходе из области. По сути, это вопрос "в каком смысле локальные переменные локальны?" Как семантика захватывает местность? Чтобы объяснить это, он изобрел модель категории функторов. (См. Рейнольдс: Сущность Алгола и Теннента: Семантика языков программирования).

Теннент хотел смоделировать принципы аргументации, сформулированные в Спецификационной логике Рейнольдса (расширение логики Хоара для процедур более высокого порядка). Логика имеет такие идеи, как выражения, подобные выражениям (только для чтения), невмешательство между командами и вычислениями, подобными выражениям, и некоторые принципы обоснования абстракции данных. Он усовершенствовал модель категории Рейнольдса, чтобы найти новую. Это называется моделью «SASL», также описанной в книге Теннента.

Мейер и Зибер, а также О'Хирн и Теннент отметили, что ни одна из этих моделей все еще полностью не отражала локальность локальных переменных. Когда две реализации абстрактного типа данных или класса различаются по своим локальным переменным, но манипулируют ими способами, которые имеют одинаковое поведение при взгляде извне, они являются наблюдательно эквивалентными. Денотационная семантика должна приравнивать их. Чтобы смоделировать это, О'Хирн и Теннент добавили реляционную параметричность к варианту модели категории функторов Рейнольдса.

Когда я одновременно посмотрел на проблему, я не поверил в подход категории функторов. Я также подумал, что это слишком технически, и считал, что должна быть более простая модель. Это заставило меня изобрести модель «Глобальное состояние считается ненужным», которая скорее похожа на модель трассировок CSP, но для языка более высокого порядка. В качестве дополнительного бонуса эта модель также уловила необратимость изменения состояния, чего не было в более ранних моделях.

Моя модель работала только для хорошо себя ведущего подъязыка Алгол, называемого Синтаксический Контроль Интерференции . Абрамский и МакКускер расширили мою модель, используя идеи семантики игр, чтобы она могла работать на полный Алгол. Таким образом, их модель объясняет те же явления, что и моя, но для более крупного языка.

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

[Все работы, о которых я упоминал, можно найти в томах «Алголоподобные языки»: ссылка и ссылка ]

Удай Редди
источник