Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Ֆունկցիոնալ ծրագրերի հիմնական սեմանտիկայի մասին

Հրաչյան, Գուրգեն Գագիկի (2009) Ֆունկցիոնալ ծրագրերի հիմնական սեմանտիկայի մասին. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (282Kb) | Preview

    Abstract

    В диссертационной работе рассматриваются бестиповые и строго типизированные функциональные программы. Бестиповые функциональные программы представляют собой системы уравнений с отделяющимися переменными в бестиповом X -исчислении. Основная (детонационная) семантика таких программ определяется как терм в бестиповом X -исчислении, использующий некоторый комбинатор неподвижной точки. Обычно используется комбинатор неподвижной точки Y (парадоксальный комбинатор Карри). Существует множество технологий интерпретации бестиповых функциональных языков программирования. Например, Eval/Apply-интерпретатор, SECD машина, метод, основанный на редукции графов, метод CPS преобразований. Исследование соотношения процедурных семантик используемых методов и основной семантики является одной из актуальных и важных проблем теории функционального программирования. Перечисленные методы, а также многие другие, эквивалентны, так называемым, алгоритмам интерпретации. В работе процедурные семантики алгоритмов интерпретации сравниваются с основной семантикой, определяемой с помощью комбинатора неподвижной точки Y. Возникает естественный вопрос: верны ли эти результаты для произвольного комбинатора неподвижной точки? Таким образом, важным является рассматриваемый в диссертационной работе вопрос об инвариантности основной семантики относительно комбинатора неподвижной точки, а также вопрос о том, как ведут себя основные семантики, определяемые разными комбинаторами неподвижной точки, при конкретных редукционных стратегиях. В диссертационной работе исследуется также наименьшее решение строго типизированных функциональных программ (систем уравнений с отделяющимися переменными в монотонных моделях типового X -исчисления), главная компонента которого является основной семантикой программы. В работе2, доказывается, что компоненты порядков < 2 наименьшего решения такой системы уравнений достигаются при ординале о (ординал, соответствующий натуральному ряду). В диссертационной работе исследуется вопрос о том, при каких ординалах достигаются компоненты порядков > 3. 1. Ապացուցվում է առանց տիպերի ֆունկցիոնալ ծրագրերի հիմնական սեմանտիկայի ինվարիանտության մասին թեորեմը, ըստ որի, կամայական երկու տարբեր անշարժ կետի կոմբինատորների միջոցով սահմանված հիմնական սեմանտիկաները համարժեք են այն իմաստով, որ եթե դրանք կիրառվում են նույն տվյալներին, ապա ստացվում է միևնույն արդյունքը: Այս թեորեմից հետևում է, որ Y (Կարրիի պարադոքսալ կոմբինատոր) անշարժ կետի կոմբինատորի համար մինչ այժմ ստացված արդյունքները ճիշտ են կամայական անշարժ կետի կոմբինատորի համար: Ապացուցվում է, որ չնայած այս համարժեքությանը, տարբեր անշարժ կետի կոմբինատորների, մասնավորապես Y (Կարրիի պարադոքսալ կոմբինատոր) և 0 (Թյուրինգի կոմբինատոր) անշարժ կետի կոմբինատորների միջոցով սահմանված հիմնական սեմանտիկաները, ոչ միշտ են ի-հավասար: Ապացուցվում է նաև, որ այսպես կոչված, ակտիվ ռեդուկցիոն ստրատեգիաները (որոշակի բնական պայմանին բավարարող) և, այսպես կոչված, կատարելագործված ակտիվ ռեդուկցիոն ստրատեգրիաները օգտագործելու դեպքում տարբեր անշարժ կետի կոմբինատորներով սահմանված հիմնական սեմանտիկաները ոչ միշտ են իրենց նույն կերպ պահում: Այսինքն, մի դեպքում ռեդուկցիան ավարտվում է արդյունքով, իսկ մյուս դեպքում այն շարունակվում է անվերջ: Որոշվում է ա]ն օրդինալը (2 ճշտությամբ), որի դեպքում սաացվում է մոնոաոն արտապատկերման փոքրագու]ն անշարժ կետը: Գնահատվում են ա]ն օրդինալները, որոնց դեպքում ստացվում են խիստ տիպիզացված ֆունկցիոնալ ծրագրերի փոքրագու]ն լուծման >3 կարգի կոմպոնենտները:

    Item Type: Thesis (PhD)
    Additional Information: Ֆունկցիոնալ ծրագրերի հիմնական սեմանտիկայի մասին: On Basic Semantics of Functional Programs.
    Uncontrolled Keywords: Հրաչյան Գուրգեն Գագիկի, Hrachyan Gurgen G.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 15 Mar 2017 12:50
    Last Modified: 15 Mar 2017 13:56
    URI: http://etd.asj-oa.am/id/eprint/4273

    Actions (login required)

    View Item