|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 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.
Received: 14.11.2017 Accepted: 25.01.2018
Citation:
S. A. Nigiyan, “On interpretation of typed and untyped functional programs”, Proceedings of the YSU, Physical and Mathematical Sciences, 52:2 (2018), 119–133
Linking options:
https://www.mathnet.ru/eng/uzeru467 https://www.mathnet.ru/eng/uzeru/v52/i2/p119
|
Statistics & downloads: |
Abstract page: | 131 | Full-text PDF : | 28 | References: | 14 |
|