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

Առանց տիպերի ֆունկցիոնալ ծրագրերի ձևափոխությունների և նրանց պրոցեդուրային սեմանտիկաների մասին

Ղազարյան , Գոռ Արամի (2011) Առանց տիպերի ֆունկցիոնալ ծրագրերի ձևափոխությունների և նրանց պրոցեդուրային սեմանտիկաների մասին. PhD thesis, ԵՊՀ.

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

Download (228Kb) | Preview

    Abstract

    Այս աշխատանքը վերաբերում է ֆունկցիոնալ ծրագրավորման խնդիրներին: Հետազոտության առարկան առանց տիպերի ֆունկցիոնալ ծրագրերն են, որոնք սահմանվում են որպես անջատվող փոփոխականներով հավասարումների համակարգեր առանց տիպերի λ-հաշվում1,2: Ֆունկցիոնալ ծրագրերի անշարժ կետի սեմանտիկան (հիմնական սեմանտիկան) սահմանվում է անշարժ կետի Y կոմբինատորի միջոցով 3,4: Հիմնականում ֆունկցիոնալ ծրագրերի ինտերպրետատորները հիմնվում են երկու տեսակի գործողությունների վրա` տեղադրություն և միաքայլ β-ռեդուկցիա: Ապացուցված է, որ պրոցեդուրային սեմանտիկաները, հիմնված այդպիսի ինտերպրետացիայի ալգորիթմների վրա, անհակասելի են: Երբ պրոցեդուրային սեմանտիկաները, հիմնված այդ ինտերպրետացիայի ալգորիթմների վրա, համընկնում են ծրագրերի հիմնական սեմանտիկայի հետ, այդ դեպքում նշված պրոցեդուրային սեմանտիկաները համարվում են լրիվ, իսկ հակառակ դեպքում` ոչ լրիվ: Երկու ֆունկցիոնալ ծրագրեր համարվում են համարժեք, եթե նրանց հիմնական սեմանտիկաները համընկնում են: Հաճախ օպտիմիզացման նպատակների համար անհրաժեշտ է լինում ծրագիրը ձևափոխել, այսինքն` ներկայացնել այն մեկ այլ համարժեք ծրագրով: Ակնհայտ է, որ, օգտվելով ծրագրերի հիմնական սեմանտիկայից, կամայական ծրագիր կարելի է ձևափոխել մեկ հավասարումից կազմված ծրագրի: Բնականաբար հարց է առաջանում, թե արդյոք կարելի է ցանկացած ծրագիր ձևափոխել մեկ հավասարումից կազմված ծրագրի այնպես, որ պահպանվեն բոլոր պրոցեդուրային սեմանտիկաները: Диссертационная работа посвящена проблемам функционального программирования. Объектом исследования является бестиповая функциональная программа, которая представляет собой систему уравнений (с отделяющимися переменными) в бестиповом λ-исчислении. Семантика неподвижной точки (основная семантика) бестиповой функциональной программы определяется с помощью комбинатора неподвижной точки Y. Процедурные семантики бестиповых функциональных программ основаны на алгоритмах интерпретации, использующих два вида операции: подстановку и одношаговую β-редукцию. Известно, что процедурные семантики, основанные на таких алгоритмах интерпретации являются непротиворечивыми. Если процедурная семантика совпадает с основной семантикой программ, то она называется полной, в противном случае – не полной. Представляет интерес исследование этой проблемы в классе программ состоящих из одного уравнения. В цельях оптимизации, часто бывает необходимо преобразовывать программу, т.е. представлять ее другой, эквивалентной ей программой. Очевидно, что можно преобразовать произвольную программу в эквивалентную ей программу, состоящую из одного уравнения. Соответсвенно возникает вопрос: возможно ли преобразовать произволную программу в программу состоящую из одного уравнения, которая бы сохраняла все основные процедурные семантики. The thesis is devoted to the problems of functional programming. The main object of the research is the untyped functional program, which is defined as а system of equations (with separated variables) in the untyped λ-calculus. The fixed-point semantics (main semantics) of the untyped functional program is defined by the fixed-point combinator Y. The procedural semantics of untyped functional programs are based on interpretation algorithms that use two types of operations: substitution and one-step β-reduction. It is known that procedural semantics based on such interpretation algorithms are consistent. If procedural semantics match with the main semantics of the programs, then these procedural semantics are called complete, and in the opposite case, these procedural semantics are called incomplete. Often for optimization purposes, it is necessary to transform the program, i.e. to represent a program by another equivalent program. It is evident that any program can be transformed to an equivalent program composed of one equation. Consequently, a question arises: whether it is possible to transform any program to a program composed of one equation, which preserves the main procedural semantics.

    Item Type: Thesis (PhD)
    Additional Information: О преобразованиях бестиповых функциональных программ и их процедурных семантиках. On transformations of untyped functional programs and their procedural semantics.
    Uncontrolled Keywords: Казарян Гор Арамович, Ghazaryan Gor A.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Thesis Dissertations
    Date Deposited: 01 Dec 2015 13:16
    Last Modified: 16 Mar 2017 13:47
    URI: http://etd.asj-oa.am/id/eprint/79

    Actions (login required)

    View Item