Geodesic
On interpretation of typed and untyped functional programs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 52 (2018) no. 2, pp. 119-133 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{UZERU_2018_52_2_a6,
     author = {S. A. Nigiyan},
     title = {On interpretation of typed and untyped functional programs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {119--133},
     year = {2018},
     volume = {52},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2018_52_2_a6/}
}
TY  - JOUR
AU  - S. A. Nigiyan
TI  - On interpretation of typed and untyped functional programs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2018
SP  - 119
EP  - 133
VL  - 52
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZERU_2018_52_2_a6/
LA  - en
ID  - UZERU_2018_52_2_a6
ER  - 
%0 Journal Article
%A S. A. Nigiyan
%T On interpretation of typed and untyped functional programs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2018
%P 119-133
%V 52
%N 2
%U http://geodesic.mathdoc.fr/item/UZERU_2018_52_2_a6/
%G en
%F UZERU_2018_52_2_a6
S. A. Nigiyan. On interpretation of typed and untyped functional programs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 52 (2018) no. 2, pp. 119-133. http://geodesic.mathdoc.fr/item/UZERU_2018_52_2_a6/

[1] S. A. Nigiyan, “Functional Languages”, Programming and Computer Software, 17:5 (1992), 290–297

[2] S. A. Nigiyan, “On Interpretation of Functional Programming Languages”, Programming and Computer Software, 19:2 (1993), 71–78 | MR | Zbl

[3] S. A. Nigiyan, “On Non-classical Theory of Computability”, Proceedings of the YSU. Physical and Mathematical Sciences, 2015, no. 1, 52–60 | Zbl

[4] S. A. Nigiyan, “On $\lambda$-Definability of Arithmetical Functions with Indeterminate Values of Arguments”, Proceedings of the YSU. Physical and Mathematical Sciences, 2016, no. 2, 39–47 | Zbl

[5] S. A. Nigiyan, T. V. Khondkaryan, “On Translation of Typed Functional Programs into Untyped Functional Programs”, Proceedings of the YSU. Physical and Mathematical Sciences, 51:2 (2017), 177–186

[6] S. A. Nigiyan, T. V. Khondkaryan, “On Canonical Notion of $\delta$-Reduction and on Translation of Typed $\lambda$-Terms into Untyped $\lambda$-Terms”, Proceedings of the YSU. Physical and Mathematical Sciences, 51:1 (2017), 46–52 | Zbl

[7] H. Barendregt, The Lambda Calculus. Its Syntax and Semantics, North-Holland Publishing Company, 1981 | MR | Zbl

[8] S. A. Nigiyan, S. A. Avetisyan, “Semantics of Untyped Functional Programs”, Programming and Computer Software, 28:3 (2002), 119–126 | DOI | MR | Zbl

[9] L. E. Budaghyan Formalizing the Notion of $\delta$-Reduction in Monotonic Models of Typed $\lambda$-Calculus, Algebra, Geometry Their Applications, 1 (2002), 48–57 | MR

[10] R. Yu. Hakopian, “On Procedural Semantics of Strong Typed Functional Programs”, Proceedings of YSU, 2008, no. 3, 59–69 (in Russian)

[11] Z. Manna, Mathematical Theory of Computation, McGraw-Hill Book Company, 1974 | MR | Zbl

[12] G. G. Hrachyan, “On Basic Semantics of Untyped Functional Programs”, Programming and Computer Software, 35:3 (2009), 121–135 | DOI | MR | Zbl