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.

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {52},
     number = {2},
     year = {2018},
     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
PB  - mathdoc
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
%I mathdoc
%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