А   Б  В  Г  Д  Е  Є  Ж  З  І  Ї  Й  К  Л  М  Н  О  П  Р  С  Т  У  Ф  Х  Ц  Ч  Ш  Щ  Ю  Я 


Операційна семантика

Операційна семантика, що задається функцією переходів, еквівалентна семантиці підстановок р-редукції і б-редукції в лямбда-численні.

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

Чи визначає операційна семантика відповідь на запит А.

Доведіть, що операційна семантика Прологу узгоджується з семантикою К-систем: якщо операційна семантика дозволяє обчислити для запиту а. ТАК чи НІ, то в К-системі, відповідної даної Пролог-програму (заперечення замінено на в), слово а істинно, якщо відповідь ТАК, і помилково, якщо відповідь НІ.

Отже, розглянемо операційну семантику продукцій. Для однаковості викладу вважатимемо, що всі зразки в продукціях - процедурні.

Якщо прологовскіе програми мають операційну семантику, програми на Дейталоге - чисто декларативні, при інтерпретації програм на Пролозі використовується низхідна схема, заснована на резолюцію-ної стратегії, пошуку спочатку вглиб і бектрекінге Для конструювання дерев докази. Базова схема інтерпретації Дейталога - висхідна.
 Використання системи понять з вбудованою операційною семантикою дозволяє формувати посилки машинно реалізованого логічного висновку, що породжує потрібні дані, а це значно збагачує можливості системи. Подальше збагачення повинно бути пов'язане з розробкою механізму оперування з розмитими об'єктами.

По-перше, такий підхід дозволяє легко задайать операційну семантику мов програмування, що оперує з такими поняттями, як стан управління і стан обчислювального середовища.

Реалізуючи проміжний код, інтерпретатор, крім того, забезпечує його операційну семантику.

Доведіть, що операційна семантика Прологу узгоджується з семантикою К-систем: якщо операційна семантика дозволяє обчислити для запиту а. ТАК чи НІ, то в К-системі, відповідної даної Пролог-програму (заперечення замінено на в), слово а істинно, якщо відповідь ТАК, і помилково, якщо відповідь НІ.

Основне досягнення дослідження ван Емдена і Ковальського полягає в отриманні елегантних доказів еквівалентності операційної семантики, теоретико-модельної семантики і семантики нерухомої точки для логічних програм на мові хорновскіх диз'юнктів. Ці семантики еквівалентні в тому сенсі, що вони визначають одні і ті ж денотат для предикатних символів. Еквівалентність перших двох семантик виходить завдяки теоремі Геделя про повноту логіки предикатів першого порядку, що зв'язує доказовою з общезначимостью. еквівалентність другий і третій семантик встановлюється за допомогою докази того, що Ifp (Т) є найменша ербрановская модель Р і що Р p (t) тоді і тільки тоді, коли предикат p (t) є істинним в цій моделі.

Однак тут розглядається проблема зовнішнього по відношенню до мережі процесів недетермінізма і немає строгого визначення операційної семантики. У[71]показано, що недетермінізм процесів може призводити до втрати властивості безперервності обчислень, коли вже непридатна теорема про найменшу нерухому точку або аналогічна їй теорема Кнастера-Тарського. Збереження при цьому властивості монотонності процесів не дає конструктивного прийому для відшукання найменшою нерухомою точки обчислень.

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

Застосувавши правило 1 до висновку факту А - БЕЗДІТНИЙ, отримаємо в якості присипання заперечення факту А - МАЄ ДІТЕЙ. Операційна семантика заперечення в мові Пролог розуміється так[20]: Щоб вивести посипання не а, слід перевірити, що факт а невивода. З огляду на це ми починаємо виводити факт А - МАЄ]ДІТЕЙ. Це твердження виводиться за допомогою правила 2 з факту 3 Звідси випливає, що посилка не А - МАЄ ДІТЕЙ невиведені, значить, невивода і факт А - БЕЗДІТНИЙ - на наш запит систем) відповість НІ.

 Як зазначалося вище, денотаціонная семантика (зовнішнє опис) визначається в поняттях повідомлень, а операційна (внутрішнє опис) - в поняттях подій. На основі операційної семантики формулюються вимоги до реалізації композиції процесів: для того щоб композиція була однозначною, досить, щоб переходи процесів були взаємно транзитивними. Якщо композиція однозначних процесів неперервна, то її денотаціонная семантика - це семантика найменшою нерухомою точки. властивість безперервності процесів обчислень забезпечує існування конструктивного прийому знаходження нерухомої точки програм[41]як найменшої верхньої межі Итг на закінченому частковому порядку з вхідних і вихідних повідомлень. Монотонність функції F на закінченому частковому порядку також забезпечує існування найменшої нерухомої точки, проте не дає деякого конструктивного прийому для її знаходження. Тарского, які вивчали проблему стосовно до ґрат, а не до закінченому часткового порядку. Тому іноді відповідну семантику називають семантикою Тарского.

Припустимо дан запит А. Відповідно до операційної семантикою заперечення для виведення цієї посилки необхідно знову почати виводити факт А - робота інтерпретатора зациклюється на необмеженій застосуванні одного і того ж правила. Зрозуміло, можна зареєструвати це зациклення і вважати, що факт А невивода за допомогою даного правила, а на запит А. Але це буде означати, що ні А виводиться, а значить А має місце. Ми, таким чином, отримали протиріччя з логічної семантикою цього правила - прийняття будь-якого варіанту (А виводиться, А невиведені) призводить до протилежного твердженням. Іншими словами, цьому правилу взагалі не вдається приписати ніякого сенсу, якщо вважати, що факт А обов'язково або виводимо, або невивода.

Другий розглянутий нами підхід до підвищення ефективності виконання функціональних програм використовує абстрактну інтерпретацію для управління шляхом виконання програми без модифікації її визначення. Механізм такого управління формалізується анотуванням програми, що специфікує її операційну семантику більш точно, ніж це може бути зроблено при визначенні тільки семантики для мови в цілому. Наприклад, ми вже стикалися в декількох випадках з семантикою енергійного і ледачого обчислень в функціональних мовах, в яких параметри завжди беруться за значенням і за потребою відповідно. Однак немає причини, чому б не зробити деякі застосування функції енергійними і їхні аргументи будуть братися за значенням, а інші - ледачими і їхні аргументи будуть братися за потребою. Потрібно лише однобітових анотація для кожного параметра визначення функції, яка вказує, яка семантика повинна бути для кожного компилируемого застосування функції. Правда, практичне завдання полягає насамперед у здійсненні правильного вибору.

Робота SECD-машини була визначена в напівформальному вигляді в термінах станів і функції переходів, яка визначає однокрокові переходи з одного стану в інший. З /- машина забезпечує коректну реалізацію Л, необхідно математично визначити операційну семантику і довести, що вона еквівалентна загальноприйнятою (денотаціонной) семантиці Л, визначеної в термінах Р - і б-ре-продукції. Спочатку ми дамо формальне визначення складових частин SfCD-машини, а потім визначимо для неї операційну функцію обчислення Eval. при застосуванні до вираження А ця функція повертає значення, обчислене для цього виразу SECD-машиною. Доказ є простим, але має безліч деталей, і докази двох лем віднесені в кінець цього розділу.

Припустимо, ми маємо деякий мову програмування, частиною визначення властивостей якого є денотаціонная семантика. Ми хочемо на цій мові писати коректні програми, виконання яких описується операційної семантикою мови. При цьому виникає проблема, що відноситься до числа фундаментальних в теоретичному програмуванні.

Для суворого рішення цих питань, а також інших, таких як питання про зберігають сенс оптимізацію, розглянутих в ч III даної книги, кожна мова програмування повинна бути забезпечений математичної семантикою. Функціональні мови програмування внаслідок міцного теоретичного фундаменту добре підходять для цього Мають місце кілька альтернативних підходів до формальної семантиці Операційна семантика наказує, як обчислюються вирази в термінах переходів між станами, визначеним. Кінець послідовності переходів представляє деяку повністю редуцированную величину Інший підхід, який був використаний для опису семантики імперативних мов, є аксіоматичним. У цьому випадку кожному типу синтаксичного оператора відповідає аксіома Маючи набір припущень, що представляють стан виконання програми в точці безпосередньо перед виконуваних оператором, набір припущень в точці безпосередньо після його виконання може бути виведений з аксіоми, пов'язаної з цим оператором. Однак, оскільки в декларативною програмою ие існує природного поняття точка програми (якщо її послідовність обчислень не представлена ясно), аксіоматичний підхід важко застосувати для функціональних мов.

Тепер розглянемо питання про те, як може бути визначена денотаціонная семантика обчислень в моделі обміну використовуються для обчислення шуканих результатів. Операційна семантика, однак, встановлюється, в основному, інтерпретатором, тому сама Пролог-програма є переважно дескриптивної і описує те, що необхідно обчислити, а не як це зробити.

Робота машини описується в термінах переходів з одного стану в інший. Переходи ми визначимо за допомогою функції переходів з одного стану в інший в наступному розділі. Ця функція може бути використана для формального визначення операційної семантики реалізації і дана для випадку аплікативного порядку обчислень.

Описавши проміжний код, ми потім пояснюємо, як він може бути механічно обчислений на комп'ютері. Наш перший метод реалізації заснований на інтерпретаторі для проміжного коду. Побічно забезпечуючи реалізацію вихідного мови, цей інтерпретатор дає нам також операційну семантику проміжного мови, яка описує мову, специфікуючи як обчислюється кожна мовна конструкція. Ми побачимо, що існує безліч досить тонких питань, особливо коли намагаємося реалізувати різні порядки обчислень. Альтернативою механізму інтерпретації є визначення абстрактної машини для обчислення виразів проміжного коду, заснованої на деякій правильно визначеної обчислювальної моделі, і в гл. SECD-машину, - яка обчислює вирази, записані в лямбда-нотації.

Глава складається з трьох основних розділів. Розділ 9.1 вводить тип даних мови Норі для подання абстрактних синтаксичних дерев проміжного коду, а в розд. Ми завершуємо цю главу загальним обговоренням проблем, пов'язаних з використанням інтерпретатора для визначення операційної семантики мови.

Вона заснована на категоріальної комбінаторної логікою. Абстрактна машина для комбінаторної редукції цього типу, звана категоріальної абстрактної машиною (КАМ), заснована на міцному математичному фундаменті, що сприяє досить високою ступеня оптимізації. Цікаво, що її робота описується в термінах переходів між станами, що дуже нагадує операційну семантику SECD-машини.

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

Натомість тут ми розглянемо семантику деяких характерних особливостей типових функціональних мов, таких як Норі, показавши, наприклад, як ми можемо розрізняти редукцію аіплікатівного і нормального порядку. Зауважимо, однак, що передачі параметрів по імені і по необхідності дають однакове значення для кожного виразу, оскільки кожна реалізує редукцію нормального порядку. Ці два правила обчислень є тому семантично ідентичними з точки зору денотаціонной семантики, але відрізняються з точки зору операційної семантики. Ми починаємо з розгляду Х - обчислення, оскільки всі функціональні мови математично еквівалентні йому і його семантика забезпечує відносно просте введення в предмет нашого обговорення.

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

Схема програми з пам'яттю, що також називається а л о г о л о п о д о б н о і, або про п е-р а т о р н о і, схемою, задається у вигляді кінцевого орієнтованого графа переходів, що має зазвичай одну вхідну і одну вихідну вершини, вершини з однієї (перетворювачі) і двома (розпізнавачі) вихідними дугами. За допомогою символів сигнатури і рахункового безлічі символів змінних і констант звичайним чином будується безліч функціональних і предикатних термів. Кожному розпізнавачів зіставляється недо-рий предикатний терм, а перетворювача - оператор присвоєння, що має вид г /: т, де у - символ змінної, а т - функціональний терм. Кінцева сукупність всіх змінних в схемі утворює її пам'ять. Інтерпретація на додаток до конкретизації базових операцій наказує кожноїзмінної область її зміни, а кожної константі - її значення. Для програм з пам'яттю найбільш звичайна т.зв. операційна семантика, що складається з алгоритму виконання програми на заданому стані пам'яті. Програма виконується при русі по графу переходів. При попаданні на распознаватель обчислюється предикатний терм і відбувається перехід по дузі, що відповідає значенню предиката. При попаданні на перетворювач з оператором у: т: обчислюється значення т і присвоюється змінної у.

Однак якщо ми неправильно розуміємо цю мову, то не зможемо правильно зрозуміти семантику визначається мови. Все це відноситься не тільки до семантиці виклику функцій. Кожна з конструкцій визначається мови з необхідністю реалізується в термінах конструкцій визначає мови, так що якщо ми недостатньо добре розуміємо ці конструкції, то не зможемо повністю зрозуміти семантику визначається мови. Саме з цієї причини семантика мови програмування часто виражається в неопераційна вигляді. Ідея полягає в тому, щоб відмовитися від визначення мови в термінах іншої мови і виражати семантику мови в термінах точних математичних понять, що особливо підходить для функціональних мов. Це веде нас від операційної семантики в сферу денотаціонной семантики, яка визначає мову, явно встановлюючи математичну величину для кожної мовної конструкції, причому ця величина належить добре специфікованої області визначення. Щоб дати читачеві деяке базове уявлення про предмет, в додатку В ми коротко описуємо, що таке денотаціонная семантика.

Часто кластерні методи використовуються в поєднанні з мовами специфікації, інваріантними щодо технічної реалізації функцій архітектури. Так, в[73]в якості мови специфікації використовується UNITY, який спочатку розроблявся як засіб і метод специфікації паралельних обчислень. Ця мова поєднує в собі можливості нотації і формальної верифікації програм. Мова дозволяє описати синхронне і асинхронне взаємодія процесів без їх попереднього планування і призначення на ресурси. Таким чином підтримується функціональний стиль специфікації і можливість аналізу конкретних реалізацій компонентів архітектури в широкому діапазоні - від програм до замовний апаратури. Близьким до розглянутого в[73]є метод об'єктно-орієнтованих функціональних специфікацій[159], В якому використовуються теоретика-множинні нотації архітектури. Стан системи представляється об'єктами, які реалізуються як функції мови СП-К Навмисний відхід від операційної семантики в специфікаціях забезпечує гнучкість в реалізації архітектурних рішень.

Вивчення семантики мови програмування в своїй основі пов'язане з приписуванням значень компонентів програм. У загальному випадку значення кожної такої компоненти визначається як її контекстом в даній програмі, так і деяким фіксованим способом її означивания за допомогою цієї програми. Це питання передбачає, що є відповідність, частково обумовлений безліччю процедур Р, між предикативними символами і деякими іншими об'єктами, які є їхніми значеннями. Що ж можна використовувати в якості таких об'єктів. Для обчислювальної семантики очевидним вибором є ефективно обчислюваності відносини. Вони розробили три різних види семантики, в кожному з яких в якості денотата предикатного символу визначається деякий обчислюваності відношення, і встановили співвідношення між ними. Якщо розглядати спростування як обчислення і помітити, що для породження цих обчислень є такі системи виведення, як резолюція, то термін операційна семантика стає виправданим. Це визначення операційної семантики аналогічно традиційному способу завдання семантик звичайних мов програмування - а саме, за допомогою визначення механізму виконання (як правило, на деякій абстрактній машині) і пояснення потім значення програми, виходячи з того, що обчислюється в результаті застосування до програми даного механізму.

Вивчення семантики мови програмування в своїй основі пов'язане з приписуванням значень компонентів програм. У загальному випадку значення кожної такої компоненти визначається як її контекстом в даній програмі, так і деяким фіксованим способом її означивания за допомогою цієї програми. Це питання передбачає, що є відповідність, частково обумовлений безліччю процедур Р, між предикативними символами і деякими іншими об'єктами, які є їхніми значеннями. Що ж можна використовувати в якості таких об'єктів. Для обчислювальної семантики очевидним вибором є ефективно обчислюваності відносини. Вони розробили три різних види семантики, в кожному з яких в якості денотата предикатного символу визначається деякий обчислюваності відношення, і встановили співвідношення між ними. Якщо розглядати спростування як обчислення і помітити, що для породження цих обчислень є такі системи виведення, як резолюція, то термін операційна семантика стає виправданим. Це визначення операційної семантики аналогічно традиційному способу завдання семантик звичайних мов програмування - а саме, за допомогою визначення механізму виконання (як правило, на деякій абстрактній машині) і пояснення потім значення програми, виходячи з того, що обчислюється в результаті застосування до програми даного механізму.