12.Области на Скот.Примери.

Всеки който е изучавал език за програмиране се е сблъсквал с неясното описание на някои оъ по-сложните конструкции с размиване м/у описанието в документацията и реалното поведение на програмите.Често това води до трудни за откриване грешки и загуба на часове в в изучаване на поведението на програмите с помоща на многократни експеременти.Проблемът за точното разбиране на даден език стои дори по остро пред авторите на самите компилатори.Важността на проблема за прецизното описание на синтаксиса и семантиката на един език за програмиране е осъзната отдавна и има многобройни опити за неговото решаване.В настоящия момент можем да считаме че въпросът с синтаксиса е напълно решен.Описанието се дава с помоща на формална граматика, синтактични диаграми или подобен формален метод. Нещо повече в резултат от развитието на формалните методи се намериха и ефикасни алгоритми за проверка на синтактична коректност.Не така стои въпросът със семантиката на езиците за програмиране.И до ден днешен най-разпространения метод на задаване на семантика на език за програмиране е операционният.Основното в този метод е че всяка конструкция в езика се определя посредством поведението на абстрактен компютър.Говори се за клетки, стекове и пр.Прецизното описание на езиците за програмиране в тези термини е напълно възможно но когато се достигне до по-сложни елементи на езика като например дефиниция посредством рекурсия сложността става толкова голяма че прецизността обикновенно се изоставя и трябва да се задоволим с примери.Друг недостатък е че програмите са доста тромави реално приложими само в сравнително прости случай.Друг подход към определянето на семантиката на езиците за програмиране е денотационния метод.Основната идея на този метод е че всяка конструкция в езика за програмиране може да се определи като минимална неподвижна точка на непрекъснато изображение в определен вид частияно наредени множ. наречени области на Скот.Самите неподвижни точки се определят с помоща на конструкция.Нека А е множ. и } е бинарна релация в А. Казваме че } е частична наредба в А ако при всеки избор на алементите a,b,c на А са в сила следните условия:

1)а }а;

2)а }b^b }aa=b;

3)a }b^b }ca }c.

Област на Скот наричаме всяка тройка (А, } , ) където А е произволно непразно множ., } е частична наредба в А, е най-малкият елемент на А,т.е. "а(аА }а), и всяка монотонно растяща редица a₀ } a₁ }... } a_к }...от елементите на А има точна горна граница,която ще означяваме с U a_{к .} Трпйката F_n =( F_n, } , €) където F_n е множ. от n-местните частични ф-ции в множ. на естествените числа, } е дефинирана като релация продължение , а € е никъде неопределена ф-ция.Този пример може тривиално да се обобщи като вместо частична ф-ция в N разгледаме частични ф-ции в произволно множ. Подобен по дух пример е и съвкупността на всички подмнож. на дадено множ. като най-малък еелемент. Друг важен за програмирането пример е т,нар. плоска област на Скот.Нека А₀ е произволно множ. Избираме елемент , които не принадлежи на А₀ и дефинираме релацията } в/у множ. А= А₀ U{ } като положим х } у точно тогава когато х= или х=у. Да покажем че (А, }, ) е област на Скот. От дефиницията на наредба веднага следва че е най-малкият елемент на А. Нека х₀ }х₁}... } х_n }... е монотонно растяща редица от елементи на А. Отново по дефиниции