
Proceedings of the YSU, Physics & Mathematics, 2018, Volume 52, Issue 2, Pages 119–133
(Mi uzeru467)




Informatics
On interpretation of typed and untyped functional programs
S. A. Nigiyan^{} ^{} Chair of Programming and Information Technologies YSU, Armenia
Abstract:
In this paper the interpretation algorithms for typed and untyped functional programs are considered. Typed functional programs use variables of any order and constants of order $\leq 1$, where constants of order $1$ are strongly computable, monotonic functions with indeterminate values of arguments. The basic semantics of the typed functional program is a function with indeterminate values of arguments, which is the main component of its least solution. The interpretation algorithms of typed functional programs are based on substitutions, $\beta$reduction and canonical $\delta$reduction. The basic semantics of the untyped functional program is the untyped $\lambda$term, which is defined by means of the fixed point combinator. The interpretation algorithms of untyped functional programs are based on substitutions and $\beta$reduction. Interpretation algorithms are examined for completeness and comparability. It is investigated how the “behavior” of the interpretation algorithm changes after translation of typed functional program into untyped functional program.
Keywords:
typed functional program, untyped functional program, basic semantics, interpretation algorithm, completeness, comparability, translation.
Full text:
PDF file (202 kB)
References:
PDF file
HTML file
Document Type:
Article
MSC: 68N18 Received: 14.11.2017
Language: English
Citation:
S. A. Nigiyan, “On interpretation of typed and untyped functional programs”, Proceedings of the YSU, Physics & Mathematics, 52:2 (2018), 119–133
Citation in format AMSBIB
\Bibitem{Nig18}
\by S.~A.~Nigiyan
\paper On interpretation of typed and untyped functional programs
\jour Proceedings of the YSU, Physics {\&} Mathematics
\yr 2018
\vol 52
\issue 2
\pages 119133
\mathnet{http://mi.mathnet.ru/uzeru467}
Linking options:
http://mi.mathnet.ru/eng/uzeru467 http://mi.mathnet.ru/eng/uzeru/v52/i2/p119
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  14  Full text:  8  References:  2 
