Реализация сетевой модели вычислений с аксиоматической и рекурсивной формами задания функций и предикатов (бакалаврская работа)

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙУНИВЕРСИТЕТ«МЭИ»Институт Автоматики и вычислительной техникиКафедра Прикладной математикиВЫПУСКНАЯ РАБОТАбакалавра Прикладной математики и информатикипо направлению «Прикладная математика и информатика» (010500)Тема:«Реализациясетевоймоделивычисленийсаксиоматической и рекурсивной формами задания функций ипредикатов»СтудентАфанасьев С.ЕА-13-08фамилия, и. огруппа,подписьНаучныйруководительПрофессорд.т.нФальк В.Н.должностьзваниеФамилия, и.о. подпись«Работа допущена к защите»Зав. кафедройЕремеев А.П.датаФамилия, и.о.Дата_____________Москва2012 г.подпись1ВведениеТеория направленных отношений, разработанная Фальком В.Н.

иКутеповымВ.П., являетсяуниверсальнойтеоретическоймоделью,позволяющей в естественной форме описывать и вычислять рекурсивнозаданные объекты некоторой предметной области. На базе теориинаправленныхотношенийфункционально-логическогобыла разработана одна из реализацийязыка программирования FLOGOL (Functionand LOGic Oriented Language), обладающая возможностью в компактнойсхемнойформезадаватьопределения конструктивных объектоввтерминах направленных отношений.Цель работы:Создание системы функционально-логического программирования(СФЛП), основанной на формализме направленных отношений (НО) иобладающей развитыми интерфейсными средствами построения и отладкипрограмм.Основные задачи:— исследование языка FLOGOL и формальное описание егосемантики;— разработка основных принципов и метода компиляции FLOGOLзапросов;— разработка специальной технологии ввода программ исоответствующих интерфейсных средств;21.

Теоретическая часть1.1. Основные понятияВосновенаправленноготеориинаправленныхотношения (НО).отношенийРазличаютдвалежитвидапонятиенаправленныхотношений – бестиповые и типизированные.,Направленным отношением типаназывается график соответствия из , на носителе. Пара | |, |вD| называетсяарностью этого НО.Подкласс НО на носителе D,обозначается.Типилитипа(арности < | |, |,арностьНО| >)при необходимостиуказываются в виде правого верхнего индекса.Здесь D – множество всевозможных кортежей элементов множества Dдлины ϑ. Иными словами, направленное отношение R арности < n , n’’ >на носителе D (точнее, его график) есть множество упорядоченных пар′ ′′вида < d1′...dn′' , d1′′...dn′′'' > , где все di , di ∈ D .

Кортеж d1′...dn′' назовем входным, акортеж d1′′...dn′′'' – выходным для соответствующего элемента d -отношения R .Кортеж нулевой длины (пустой кортеж) обозначается λ , а в случаях егоиспользования в выражениях там, где это не приводит к недоразумениям, онпредставляется непосредственно пустым словом.В случае если в качестве Dвыбирается односортный носитель(универсум), то тип любого НО на D вполне определяется его арностью. Вязыке программирования FLOGOL в качестве носителя выбран односортныйноситель, поэтому язык можно считать нетипизированным.

Однаковследствиетого,чтомногосортныйносительможетбытьлегкопромоделирован с использованием односортного носителя, введение в языкпользовательских типов данных затруднений не вызывает.3НОназывается обратным для НО∀ ∀,∈ ≈, если,∈НО могут обладать некоторыми фундаментальными свойствами, вопределенном смысле не зависящими от выбора носителя.

К такимсвойствам относятся функциональность и тотальность.НО арности∀,на∈→∃называется тотальным, если∈&#,∈ $НО R называется функциональным, если∀ ∀ ′∀ ′′,∈ &,∈→= ′′Этими свойствами могут обладать как само НО, так и братное ему НО.Свойства функциональности и тотальности, определенные для обратногоотношения, будем называть свойствами обратной функциональности итотальности.Свойства функциональности и тотальности играют значительную рольв процедурах редукции, использующихся в базовой модели вычислениянаправленныхотношенийиввычислительнойподсистемеданнойреализации языка.1.2. Языки и схемы направленных отношенийВ основу построения данной реализации языка FLOGOL положеноопределенное понятиеязыкасхемНО.Длязаданияязыкасхемнеобходимо определение области интерпретации, символов элементарныхконстант и переменных, связок и операторов.

Связки используются дляобозначения результатовпримененияоперацийкомпозицииНОнаобласти интерпретации.Область интерпретации задается уточнением носителя. Бинарнымиоперациями,являютсярассматриваемымипоследовательнаявтеориикомпозиция,направленыхпараллельнаяотношений,композиция,4конкатенация, условная композиция, эквализация (унификация), операцииобъединения и пересечения типизированных НО.НОПоследовательная композиция∙обозначается через'':∙Если∙и' –и'≅{'НО арности,|∃,,, ∈& ,,,– НО арностейи∈,'}соответственно, то, ′′ .

Операция последовательной композицииассоциативна.иПараллельная композиция НОопределяетсяграфиковЕслито#'какираздельное'обозначаетсядекартовопроизведение|&#'икомпонентов':#'и'≅{','– НО арности+ ′' , – НО арности,∈,и', '', ∈'}соответственно,'+ ′′' . Операция параллельнойкомпозиции ассоциативна.Объединение НОи'обозначается черезкак теоретико-множественное объединения НО∪и''и определяется, гдеи'соответствующие графики. Объединение накладывает требование равенстваарности НО, причем результат объединения имеет ту же арность. Операцияобъединения ассоциативна и коммутативна.Пересечение НО R и R ' обозначается через R ∩ R ' и определяетсякак теоретико-множественное пересечениеНО Rи R ' как графиков.Пересечение накладывает требование равенства арности НО, причемрезультат пересечения имеет ту же самую арность.

Операция пересеченияассоциативна и коммутативна.5Операция эквализации (унификации). Эквализация d -отношений R1 иR2 определяется как декартово произведение первых компонентов графиковпри равных вторых компонентах:R1∇R2 ≅ {< α1α 2 , β >|< α1 , β >∈ R1 & < α2 , β >∈ R2 }.< n1 , n > иЭквализация определена только для операндов арностей< n2 , n > . Результат операции будет иметь арность < n1 + n2 , n > .Условная композиция d -отношений R1 и R2 обозначается знаком →и представляет собой проекцию R2 по первому компоненту графика наобласть определения d -отношения R1 :R1 → R2 ≅ {< α , β >|< α , β >∈ R2 & ∃β ' (< α , β ' >∈ R1 )}.Арности операндов условной композиции должны быть< n,n1 >и< n,n2 > , соответственно.

Результат композиции, очевидно, имеет арностьвторого операнда.< n ,n >Операция итерации. Итерация d -отношения Rобозначается {R}и определяется так:{ R} ≅U R (k )k ≥0( 0)n, где R ≅ {< α ,α >| α ∈ D } (тождественное d -отношение(1 )( i +1)≅ R (i ) • Rарности < n, n > ), R ≅ R и RОчевидно, что итерация {R} d -отношения R является наименьшимрешением уравнения x = R( 0)∪ R • x , т.е.{ R} = { x = R (0) ∪ R • x} .Результатприменения< n, n >, n ≥ 0 , что и ее операнд.итерациибудетиметьтужеарность6< n ,n >Операция повторения. Повторение d -отношения Rобозначается[R ] и определяется так:[R] ≅ U R (k ) = R • { R}k ≥1.Результат применения операции повторения будет иметь ту же арность< n, n >, n ≥ 0 , что и ее операнд.Реализация языка функционально-логическогоFLOGOL опираетсянаформализмпрограммированиянаправленногоотношения,чтопозволяет в естественной форме выражать основные семантическиеобъекты, используемые при формулировке задач искусственного интеллекта.К таким объектам относятся предикаты, функции, конструкторы,кортежи и др.

Программа на языке FLOGOL представляется в виде базыданных определений НО, одно из которых выделено в качестве запроса кбазе[1].Вычислениезапросапроизводитсянаосновесетевогопредставления направленных отношений.1.3. Комбинаторные d -отношения.d -отношениеназывается комбинаторным, если оно являетсяRфиксированной точкойдля любой перестановкиξна носителеD:ξ (R) = R для любого всюду определенного на D взаимно-однозначногоотображенияξ .

Класс комбинаторныхd -отношений на носителеDобозначим R к , полагая, что сам носитель ясен из контекста (фактически насинтересует только его мощность).Пустое множество задает пустое комбинаторное d -отношение.Среди простых комбинаторныхследующие d -отношения:d -отношенийособо выделим71) тождественные < n, n > -арные, n ≥ 0 , d -отношенияα ∈ D n } . Очевидно, чтоn• R <n ',n"> = R = R •последовательной композиции d -отношений:0≅2)≅ {<, >} .< n′, n′′ > -арные3) пустыеn′n";– правая и левая единица операции# R = R = R#параллельной композиции:≅ {< α ,α >|– правая и левая единица операцииn'0n;d -отношения,n′, n′′ ≥ 0, обозначаются∅n′′ .

n′ ∅n′′ – правые и левые единицы для операции объединения d -отношений:n'∅n" ∪ R<n′,n′′> = R = R∪n′ ∅n′′ ;< n′, n′′ > -арные4) универсальныеn′обозначаютсяn′′n′n′′.d-отношения, n′, n′′ ≥ 0,– правые и левые единицы для операциипересечения d -отношений:n′n′′∩ R < n′,n′′> = R = R ∩ n′n′′Выделим в множестве простых комбинаторныхследующее подмножество элементарных d -отношений:R кпэ ≅ {,,,где <>≅{<, >},≅ {< α , >| α ∈ D}≅ {<,α >| α ∈ D} ,≅ {< αα ,α >| α ∈ D} ,,,,},d -отношений8≅ {< α ,αα >| α ∈ D} ,≅ {< α , β >| α ∈ D & β ∈ D & α ≠ β } ,≅ {< α 'α ",α "α ' >| α '∈ D & α "∈ D} .Пусть n ≥ 0 . Определим сначала тождественное < n, n > -арное d 0nотношениеn +1≅: a), b)n≅#≅, где•.nd -Отношения≅ {< α , >| α ∈ D n }nи≅ {<, α >| α ∈ D n }определимтак:00=n +1=≅,n′′#< n′, n′′ >Универсальноеn′n +1nn′n′′≅ {< α ′,α ′′ >| α '∈ D & α ′′ ∈ D }n≅,#-арноеопределяется так:.-отношениеdn′n′′n′≅•n′′.Остальные константы:n≅ {< α ,αα >| α ∈ D n } ,n≅ {< αα ,α >| α ∈ D n } ,n≅ {< α , β >| α ∈ D n & β ∈ D n & α ≠ β } ,n'n"≅ {< α ′α ′′,α ′′α ′ >| α ′ ∈ D n′ & α ′′ ∈ D n′′ }могут быть определены следующим образом:0n1)1n′′+102)=n≅ (1≅0n′′≅nn′′,)•(#n +1,n′+1≅(≅ (n′#1n′′) • ( n′n′′#),n′′#n#);)•(n#n1#),903)04)≅n +1,≅ ∅ ,n +1n≅(≅n#n#1n∪)•(#n#),n#.1.4.