Войти
Теория предметной области - это раздел математики, изучающий специальные виды частично упорядоченных множеств (пункты), обычно называемые доменами . Следовательно, теорию предметной области можно рассматривать как раздел теории порядка. Эта область имеет основные приложения в информатике, где она используется для определения денотационной семантики, особенно для языков функционального программирования. Теория предметной области формализует интуитивные идеи приближения и конвергенции в очень общем виде и тесно связана с топологией.
Основная мотивация для изучения доменов, инициированная Даной Скотт в конце 1960-х был поиск денотационной семантики для лямбда-исчисления. В этом формализме рассматриваются «функции», определяемые определенными терминами языка. С чисто синтаксической точки зрения можно перейти от простых функций к функциям, которые принимают другие функции в качестве входных аргументов. Снова используя только синтаксические преобразования, доступные в этом формализме, можно получить так называемые комбинаторы с фиксированной точкой (наиболее известным из которых является комбинатор Y ); они, по определению, имеют свойство f (Y (f)) = Y (f) для всех функций f.
Чтобы сформулировать такую денотационную семантику, можно сначала попытаться построить модель лямбда-исчисления, в которой настоящая (общая) функция связана с каждым лямбда-термином. Такая модель формализует связь между лямбда-исчислением как чисто синтаксической системой и лямбда-исчислением как системой записи для управления конкретными математическими функциями. Комбинаторное исчисление является такой моделью. Однако элементы комбинаторного исчисления - это функции от функций к функциям; для того, чтобы элементы модели лямбда-исчисления имели произвольную область и диапазон, они не могли быть истинными функциями, только частичные функции.
Скотт обошел эту трудность, формализовав понятие «частичного» или «неполная» информация для представления вычислений, которые еще не вернули результат. Это было смоделировано путем рассмотрения для каждой области вычислений (например, натуральных чисел) дополнительного элемента, который представляет неопределенный вывод, то есть «результат» вычисления, которое никогда не заканчивается. Кроме того, область вычислений оснащена отношением упорядочения, в котором "неопределенный результат" - это наименьший элемент.
. Важным шагом для поиска модели лямбда-исчисления является рассмотрение только этих функций (на такой частично упорядоченный набор), которые гарантированно имеют наименьших фиксированных точек. Набор этих функций вместе с соответствующим порядком снова является «областью» в смысле теории. Но ограничение на подмножество всех доступных функций имеет еще одно большое преимущество: можно получить домены, которые содержат свои собственные функциональные пространства, т.е. можно получить функции, которые можно применять к себе.
Помимо этих желаемых свойств, теория предметной области также допускает привлекательную интуитивную интерпретацию. Как упоминалось выше, области вычислений всегда частично упорядочены. Этот порядок представляет собой иерархию информации или знаний. Чем выше элемент в порядке, тем он более конкретный и содержит больше информации. Нижние элементы представляют собой неполные знания или промежуточные результаты.
Вычисление затем моделируется путем многократного применения монотонных функций к элементам домена для уточнения результата. Достижение фиксированной точки эквивалентно завершению расчета. Домены обеспечивают превосходную настройку для этих идей, поскольку можно гарантировать существование неподвижных точек монотонных функций и, при дополнительных ограничениях, их можно аппроксимировать снизу.
В этом разделе будут представлены основные концепции и определения теории предметной области. Вышеупомянутая интуиция областей, являющихся упорядочениями информации, будет подчеркнута для мотивации математической формализации теории. Точные формальные определения можно найти в специальных статьях для каждого понятия. Список общих теоретико-порядковых определений, которые также включают теоретико-предметные понятия, можно найти в глоссарии теории порядка. Тем не менее, наиболее важные концепции теории предметной области будут введены ниже.
Как упоминалось ранее, теория предметной области имеет дело с частично упорядоченными наборами для моделирования области вычислений. Цель состоит в том, чтобы интерпретировать элементы такого порядка как части информации или (частичные) результаты вычислений, где элементы, расположенные выше по порядку, расширяют информацию элементов ниже них согласованным образом. Из этой простой интуиции уже ясно, что домены часто не имеют наибольшего элемента, так как это означало бы, что существует элемент, который содержит информацию обо всех других элементах - довольно неинтересная ситуация.
Концепция, которая играет важную роль в теории, - это концепция направленного подмножества домена; Направленное подмножество - это непустое подмножество порядка, в котором любые два элемента имеют верхнюю границу, которая является элементом этого подмножества. С точки зрения нашей интуиции относительно доменов это означает, что любые две части информации в пределах направленного подмножества последовательно расширяются каким-либо другим элементом в подмножестве. Следовательно, мы можем рассматривать направленные подмножества как согласованные спецификации, то есть как наборы частичных результатов, в которых нет двух противоречащих друг другу элементов. Эту интерпретацию можно сравнить с понятием сходящейся последовательности в analysis, где каждый элемент более конкретен, чем предыдущий. Действительно, в теории метрических пространств последовательности играют роль, во многих аспектах аналогичную роли направленных множеств в теории предметной области.
Теперь, как и в случае с последовательностями, нас интересует предел направленного множества. В соответствии с тем, что было сказано выше, это будет элемент, который представляет собой наиболее общую часть информации, которая расширяет информацию всех элементов направленного набора, то есть уникальный элемент, который содержит точно ту информацию, которая присутствовала в направленном наборе, и ничего более. В формализации теории порядка это просто наименьшая верхняя граница направленного множества. Как и в случае пределов последовательностей, точные верхние границы направленных множеств не всегда существуют.
Естественно, особый интерес вызывают те области вычислений, в которых сходятся все согласованные спецификации, то есть в порядках, в которых все направленные множества имеют наименьшую верхнюю границу. Это свойство определяет класс направленных-полных частичных заказов или для краткости dcpo . В самом деле, большинство соображений теории предметной области действительно рассматривают только заказы, которые по крайней мере направлены полными.
Из основной идеи частично определенных результатов как представления неполных знаний выводится еще одно желаемое свойство: наличие наименьшего элемента. Такой элемент моделирует состояние отсутствия информации - место, где начинается большинство вычислений. Его также можно рассматривать как результат вычисления, которое вообще не возвращает никакого результата.
Теперь, когда у нас есть некоторые базовые формальные описания того, какой должна быть область вычислений, мы можем перейти к самим вычислениям. Ясно, что это должны быть функции, принимающие входные данные из некоторой вычислительной области и возвращающие выходные данные в некоторой (возможно, другой) области. Однако можно было бы также ожидать, что вывод функции будет содержать больше информации, когда информационное содержание ввода будет увеличиваться. Формально это означает, что мы хотим, чтобы функция была монотонной.
При работе с dcpos, можно также захотеть, чтобы вычисления были совместимы с формированием пределы направленного набора. Формально это означает, что для некоторой функции f изображение f (D) направленного множества D (т. Е. Множество изображений каждого элемента D) снова направлено и имеет в качестве наименьшей верхней границы изображение наименьшего верхняя граница D. Можно также сказать, что f сохраняет направленную супрему. Также обратите внимание, что при рассмотрении направленных наборов из двух элементов такая функция также должна быть монотонной. Эти свойства дают начало понятию функции скоттовско-непрерывной. Поскольку это часто не является неоднозначным, можно также говорить о непрерывных функциях.
Теория предметной области - это чисто качественный подход к моделированию структуры информационных состояний. Можно сказать, что что-то содержит больше информации, но количество дополнительной информации не уточняется. Тем не менее, есть некоторые ситуации, в которых хочется говорить об элементах, которые в некотором смысле намного проще (или гораздо более неполны), чем данное состояние информации. Например, при естественном упорядочении включения подмножеств на некотором powerset любой бесконечный элемент (то есть набор) гораздо более «информативен», чем любое из его конечных подмножеств.
Если кто-то хочет смоделировать такую взаимосвязь, можно сначала рассмотреть индуцированный строгий порядок < of a domain with order ≤. However, while this is a useful notion in the case of total orders, it does not tell us much in the case of partially ordered sets. Considering again inclusion-orders of sets, a set is already strictly smaller than another, possibly infinite, set if it contains just one less element. One would, however, hardly agree that this captures the notion of being "much simpler".
Более сложный подход приводит к определению так называемый порядок аппроксимации, который, скорее, также называется отношением «путь ниже» . Элемент x находится намного ниже элемента y, если для каждого направленного множества D с супремумом, такого что
,существует некоторый элемент d в D такой, что
.Затем говорят, что x приближает y, и записывают
.Это означает, что
,, поскольку направлен набор одиночных элементов {y}. Например, при упорядочении множеств бесконечное множество намного выше любого из своих конечных подмножеств. С другой стороны, рассмотрим направленное множество (фактически, цепочку ) конечных множеств
Так как верхняя грань этой цепочки - это множество всех натуральных чисел N, это показывает, что никакое бесконечное множество не может быть ниже N.
. Однако нахождение намного ниже некоторого элемента является относительным понятием и мало что раскрывает о самом элементе. Например, кто-то хотел бы охарактеризовать конечные множества теоретико-порядковым способом, но даже бесконечные множества могут быть намного ниже некоторого другого множества. Особым свойством этих конечных элементов x является то, что они находятся намного ниже самих себя, т.е.
.Элемент с этим свойством также называется компактный. Тем не менее, такие элементы не обязательно должны быть «конечными» или «компактными» в любом другом математическом использовании этих терминов. Тем не менее, эти обозначения мотивированы определенными параллелями с соответствующими понятиями в теории множеств и топологии. Компактные элементы области обладают важным специальным свойством, заключающимся в том, что они не могут быть получены как предел ориентированного множества, в котором они еще не встречались.
Многие другие важные результаты, касающиеся отношения «путь ниже», подтверждают утверждение, что это определение подходит для отражения многих важных аспектов предметной области.
Предыдущие мысли поднимают другой вопрос: можно ли гарантировать, что все элементы домена могут быть получены как предел гораздо более простых элементов? Это весьма актуально на практике, поскольку мы не можем вычислять бесконечные объекты, но мы все же можем надеяться приблизить их произвольно близко.
В более общем плане мы хотели бы ограничиться определенным подмножеством элементов как достаточным для получения всех других элементов как минимальных верхних границ. Следовательно, каждый определяет base чугуна P как подмножество B в P, так что для каждого x в P набор элементов в B, которые находятся намного ниже x, содержит ориентированный набор с супремумом Икс. Позиционирование P является непрерывным множеством, если оно имеет некоторую базу. Тем более, что P является базой в этой ситуации. Во многих приложениях основным объектом исследования является непрерывный (d) cpos.
Наконец, еще более сильное ограничение на частично упорядоченное множество дается, требуя существования базы из конечных элементов. Такой набор называется алгебраическим. С точки зрения денотационной семантики алгебраические позы особенно хорошо работают, поскольку они позволяют аппроксимировать все элементы, даже если они ограничиваются конечными. Как отмечалось ранее, не каждый конечный элемент является «конечным» в классическом смысле, и вполне может быть, что конечные элементы составляют несчетное множество.
Однако в некоторых случаях базой для позиционного набора является счетный. В этом случае говорят о ω-непрерывном ч.у. Соответственно, если счетная база состоит полностью из конечных элементов, мы получаем порядок, который является ω-алгебраическим .
Простой частный случай области известен как элементарный или плоский домен . Он состоит из набора несравнимых элементов, таких как целые числа, а также одного «нижнего» элемента, который считается меньшим, чем все остальные элементы.
Можно получить ряд других интересных специальных классов упорядоченных структур, которые можно было бы использовать в качестве «доменов». Мы уже упоминали непрерывные множества и алгебраические множества. Более специальные версии обоих - это непрерывный и алгебраический cpos. Добавляя еще свойства полноты, мы получаем непрерывные решетки и алгебраические решетки, которые являются всего лишь полными решетками с соответствующими свойствами. Для алгебраического случая можно найти более широкие классы посетов, которые все еще стоит изучить: исторически домены Скотта были первыми структурами, которые были изучены в теории доменов. Еще более широкие классы доменов составляют, и.
Все эти классы порядков могут быть отнесены к различным категориям dcpos с использованием функций, которые являются монотонными, непрерывными по Скотту или даже более специализированными как морфизмы. Наконец, обратите внимание, что сам термин «домен» не является точным и поэтому используется как сокращение только в том случае, если формальное определение было дано ранее или когда детали не имеют значения.
Позиционирование D является DCPO тогда и только тогда, когда каждая цепочка в D имеет супремум. (Направление 'if' основывается на аксиоме выбора .)
Если f - непрерывная функция в области D, то она имеет наименьшую фиксированную точку, заданную как наименьшую верхнюю границу всех конечных итераций f на наименьшем элементе ⊥:
.Это теорема Клини о неподвижной точке. Символ 
| journal =()