Теория предметной области

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

Мотивация и интуиция

Основной мотивацией исследования доменов, которое было начато Даной Скотт в конце 1960-х годов, был поиск денотационной семантики лямбда -исчисления . В этом формализме рассматриваются «функции», определяемые определенными терминами языка. Чисто синтаксически можно перейти от простых функций к функциям, которые принимают другие функции в качестве входных аргументов. Используя снова только синтаксические преобразования, доступные в этом формализме, можно получить так называемые комбинаторы с фиксированной точкой (наиболее известным из которых является Y-комбинатор ); они по определению обладают тем свойством, что f ( Y ( f )) = Y ( f ) для всех функций f .

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

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

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

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

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

Руководство по формальным определениям

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

Ориентированные множества как сходящиеся спецификации

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

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

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

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

Из основной идеи частично определенных результатов как представления неполного знания вытекает еще одно желательное свойство: существование наименьшего элемента . Такой элемент моделирует состояние отсутствия информации — место, где начинается большинство вычислений. Его также можно рассматривать как результат вычислений, который вообще не возвращает никакого результата.

Вычисления и домены

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

При работе с dcpos также может потребоваться, чтобы вычисления были совместимы с формированием пределов направленного набора. Формально это означает, что для некоторой функции f образ f ( D ) направленного множества D (т. е. множества образов каждого элемента из D ) снова направлен и имеет в качестве наименьшей верхней границы образ наименьшего граница D. верхняя Можно также сказать, что f сохраняет направленные супремумы . Также обратите внимание, что при рассмотрении направленных наборов из двух элементов такая функция также должна быть монотонной. Эти свойства порождают понятие непрерывной по Скотту функции. Поскольку это часто не является двусмысленным, можно также говорить о непрерывных функциях .

Аппроксимация и конечность

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

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

Отношение намного ниже

Более сложный подход приводит к определению так называемого порядка аппроксимации , который более убедительно также называется отношением «путь ниже» . Элемент x находится намного ниже элемента y , если для каждого направленного множества D с супремумом такого, что

y\sqsubseteq \sup D

,

существует некоторый элемент d в D такой, что

x\sqsubseteq d

.

Тогда также говорят, что x приближает y , и пишут

x\ll y

.

Это подразумевает, что

x\sqsubseteq y

,

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

\{0\},\{0,1\},\{0,1,2\},\ldots

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

Однако то, что находится намного ниже какого-либо элемента, является относительным понятием и мало что говорит об этом элементе. Например, хотелось бы охарактеризовать конечные множества теоретико-порядковым способом, но даже бесконечные множества могут быть намного ниже какого-либо другого множества. Особым свойством этих конечных элементов x является то, что они находятся намного ниже самих себя, т.е.

x\ll x

.

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

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

Базы доменов

Предыдущие мысли поднимают еще один вопрос: можно ли гарантировать, что все элементы предметной области могут быть получены как предел гораздо более простых элементов? Это весьма актуально на практике, поскольку мы не можем вычислять бесконечные объекты, но все же можем надеяться аппроксимировать их сколь угодно близко.

В более общем плане мы хотели бы ограничиться определенным подмножеством элементов, достаточным для получения всех остальных элементов как наименьших верхних границ. определяют Следовательно, базу ЧУУ P как подмножество B в P , такое, что для каждого x в P множество элементов в B , которые находятся намного ниже x, содержит направленное множество с супремумом x . ЧУ-множество P является непрерывным ЧУ-множеством, если оно имеет некоторую базу. Тем более, что P сам по себе является базой в этой ситуации. Во многих приложениях в качестве основного объекта исследования ограничиваются непрерывным (d)cpos.

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

Однако в некоторых случаях база ЧУМ счетна . В этом случае говорят о ω-непрерывном ч.у.м. Соответственно, если счетная база целиком состоит из конечных элементов, мы получаем порядок, который является ω-алгебраическим .

Особые типы доменов

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

Можно получить ряд других интересных специальных классов упорядоченных структур, которые могли бы подойти в качестве «доменов». Мы уже упоминали непрерывные ЧУП и алгебраические ЧУП. Более специальными версиями обоих являются непрерывный и алгебраический cpos . Добавляя еще дополнительные свойства полноты, мы получаем непрерывные решетки и алгебраические решетки , которые представляют собой просто полные решетки с соответствующими свойствами. В алгебраическом случае обнаруживаются более широкие классы ЧУМ, которые все еще заслуживают изучения: исторически области Скотта были первыми структурами, изучаемыми в теории предметных областей. Еще более широкие классы доменов составляют SFP-домены , L-домены и биконечные домены .

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

Важные результаты

ЧУ-множество D является dcpo тогда и только тогда, когда каждая цепь в D имеет верхнюю грань. (Направление «если» опирается на аксиому выбора .)

Если f — непрерывная функция в области D , то она имеет наименьшую неподвижную точку, заданную как наименьшую верхнюю границу всех конечных итераций f на наименьшем элементе ⊥:

\operatorname {fix} (f)=\bigsqcup _{n\in \mathbb {N} }f^{n}(\bot )

.

Это теорема Клини о неподвижной точке . $\sqcup$ символ — направленное соединение .

Обобщения

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

См. также

Дальнейшее чтение

Г. Гирц; К.Х. Хофманн; К. Кеймель; Джей Ди Лоусон; М. Мислов; Д.С. Скотт (2003). «Непрерывные решетки и области» . Энциклопедия математики и ее приложений . Том. 93. Издательство Кембриджского университета. ISBN 0-521-80338-1 .
Самсон Абрамский , Ахим Юнг (1994). «Теория предметной области» (PDF) . У С. Абрамского; ДМ Габбай ; TSE Майбаум (ред.). Справочник по логике в информатике . Том. III. Издательство Оксфордского университета. стр. 1–168. ISBN 0-19-853762-Х . Проверено 13 октября 2007 г.
Алекс Симпсон (2001–2002). «Часть III: Топологические пространства с вычислительной точки зрения». Математические структуры для семантики . Архивировано из оригинала 27 апреля 2005 г. Проверено 13 октября 2007 г.
Д.С. Скотт (1975). «Типы данных как решетки». Труды Международного летнего института и коллоквиума по логике, Киль, в конспектах лекций по математике . 499 . Спрингер-Верлаг: 579–651.
Карл А. Гюнтер (1992). Семантика языков программирования . МТИ Пресс. ISBN 9780262570954 .
Б. А. Дэйви; Х.А. Пристли (2002). Введение в решетки и порядок (2-е изд.). Издательство Кембриджского университета. ISBN 0-521-78451-4 .
Карл Хьюитт; Генри Бейкер (август 1977 г.). «Акторы и непрерывные функционалы» (PDF) . Материалы рабочей конференции ИФИП по формальному описанию концепций программирования . Архивировано (PDF) из оригинала 12 апреля 2019 г.
В. Столтенберг-Хансен; И. Линдстрем; Э. Р. Гриффор (1994). Математическая теория областей . Издательство Кембриджского университета. ISBN 0-521-38344-7 .

Внешние ссылки

Введение в теорию предметной области , Грэм Хаттон, Ноттингемский университет.