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

Տիպիզացված ֆունկցիոնալ ծրագրերի իրականացման մասին

Գրիգորյան, Դավիթ Անդրանիկի (2019) Տիպիզացված ֆունկցիոնալ ծրագրերի իրականացման մասին. PhD thesis, ԵՊՀ.

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

Download (491Kb) | Preview

    Abstract

    Աշխատանքը նվիրված է ֆունկցիոնալ ծրագրավորման հիմունքներին։ Հետազոտման առարկա են հանդիսանում տիպիզացված ֆունկցիոնալ ծրագրերը, իսկ հիմնական դիտարկվող խնդիրը՝ ծրագրի կողմից որոշվող ֆունկցիայի հաշվարկման ֆունդամենտալ խնդիրն է: Տիպիզացված ֆունկցիոնալ ծրագրի հիմնական սեմանտիկան հանդիսանում է արգումենտների անորոշ արժեքներով ֆունկցիա, որը նրա փոքրագույն լուծման գլխավոր կոմպոնենտն է 1։ Ծրագրի կողմից որոշվող ֆունկցիայի հաշվարկը՝ կոնկրետ մուտքային տվյալների դեպքում, իրականացնում է ինտերպրետացիայի ալգորիթմը։ Եթե որոշվող ֆունկցիայի արժեքը անորոշ է, ապա ինտերպրետացիայի ալգորիթմը կամ կանգ է առնում անորոշ արժեքով, կամ աշխատում է անվերջ։ Հետազոտվել են այդպիսի ծրագրերի հաշվարկմանկանոններ, որոնք օգտագործում են տեղադրում և թերմերի պարզեցում, կապված ներդրված ֆունկցիաների հետ (δ-ռեդուկցիա), սակայն δ-ռեդուկցիայի գաղափարը չի եղել ֆորմալիզացված։ δ-ռեդուկցիայի գաղափարն առաջին անգամ ֆորմալիզացվել է 1,2 աշխատանքներում։ Ներմուծվել և հետազոտվել է, այսպես կոչված, բնական δ-ռեդուկցիայի գաղափարը, գտնվել է անհրաժեշտ և բավարար պայման, որին պետք է բավարարի բնական δ-ռեդուկցիայի գաղափարը, որպեսզի ցանկացած տիպիզացված λ-թերմի ᵦδ-նորմալ ձևը լինի միակը 2։ Работа посвящена проблемам функционального программирования. Объектом исследования являются типизированные функциональные программы, а основной рассматриваемой проблемой-задача вычисления, определяемой программой функции. Типизированная функциональная программа представляет собой систему уравнений (с отделяющимися переменными) в монотонной модели типового λ-исчисления. Каждое уравнение программы имеет вид F = £, где F - переменная, t - типизированный λ-терм, тип которого совпадает с типом переменной F. Рассматриваемые нами типизированные функциональные программы используют переменные любых порядков и константы порядок которых <1, где константы порядка 1 являются строго вычислимыми, монотонными функциями с неопределенными значениями аргументов. Основной семантикой типизированной функциональной программы является функция с неопределенными значениями аргументов, которая представляет собой главную компоненту ее наименьшего решения. Вычисление определяемой программой функции для конкретных входных данных, осуществляет алгоритм интерпретации. Алгоритмы интерпретации, основанные на подстановке правых частей уравнений программы вместо некоторых свободных вхождений переменных, одношаговой δ-редукции и одношаговой δ-редукции являются непротиворечивыми в том смысле, что, если алгоритм останавливается, то вычисленное им значение совпадает со значением определяемой программой функции. Если значение определяемой функции является неопределенным, то алгоритм интерпретации либо останавливается с неопределенным значением, либо функционирует бесконечно. Понятие δ -редукции является классическим понятием и является одним и тем же при любой интерпретации языка, понятие же δ-редукции зависит от множества встроенных функций и от конкретной реализации функционального языка программирования. The thesis is devoted to the problems of functional programming. The object of the research is typed functional programs, and the main problem under consideration is the fundamental task of computation of the function determined by the program. A typed functional program is a system of equations (with separable variables) in a monotonic model of typed λ -calculus. Each program equation has the form F = t, where F is a variable, t is a typed λ -term, the type of which coincides with the type of the variable F. We consider that typed functional programs use variables of any order and constants of order <1, where constants of order 1 are strong computable, monotonic functions with undefined values of arguments. The main semantic of a typed functional program is a function with undefined values of arguments, which is the main component of the least solution. The computation of a function, determined by a program, for specific input data is performed by an interpretation algorithm. The Interpretation algorithms that based on substitution of the right parts of the program equations instead of some free occurrences of variables, one-step ᵦδ - reduction and one-step δ-reduction, are consistent in the sense that if the algorithm stops, then the value it calculates coincides with the value of the function determined by the program. If the value of the function being determined is undefined, then the interpretation algorithm either stops with an undefined value or functions infinitely. The notion of ᵦδ - reduction is a classical notion and is the same for any interpretation of a language. The notion of δ-reduction depends on a set of built-in functions and on the specific implementation of a functional programming language.

    Item Type: Thesis (PhD)
    Additional Information: О реализации типизированных функциональных программ. On interpreters of typed functional programs.
    Uncontrolled Keywords: Григорян Давит Андраникович, Grigoryan Davit A.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 26 Aug 2019 13:22
    Last Modified: 26 Aug 2019 13:23
    URI: http://etd.asj-oa.am/id/eprint/10633

    Actions (login required)

    View Item