Geodesic
On transformations of untyped functional programs and their procedural semantics
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2011), pp. 36-43.

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

In this paper the notion of transformation of untyped functional programs that preserves the main semantics of programs is presented. A transformation, representing programs by two equations, such that procedural semantics of programs that use interpretation algorithms based on substitution and normal form reduction remain the same, is introduced. It is proved also that there is no transformation, which represents programs with one equation, such that the procedural semantics of programs remain unchanged for all interpretation algorithms that are based on two operations: a substitution and a one-step $\beta$-reduction.
Keywords: procedural semantics, interpretation algorithms.
Mots-clés : term, equation 
@article{UZERU_2011_1_a6,
     author = {G. A. Ghazaryan},
     title = {On transformations of untyped functional programs and their procedural semantics},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {36--43},
     publisher = {mathdoc},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2011_1_a6/}
}
TY  - JOUR
AU  - G. A. Ghazaryan
TI  - On transformations of untyped functional programs and their procedural semantics
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2011
SP  - 36
EP  - 43
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2011_1_a6/
LA  - en
ID  - UZERU_2011_1_a6
ER  - 
%0 Journal Article
%A G. A. Ghazaryan
%T On transformations of untyped functional programs and their procedural semantics
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2011
%P 36-43
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2011_1_a6/
%G en
%F UZERU_2011_1_a6
G. A. Ghazaryan. On transformations of untyped functional programs and their procedural semantics. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2011), pp. 36-43. http://geodesic.mathdoc.fr/item/UZERU_2011_1_a6/

[1] H.P. Barendregt, The Lambda Calculus: Its Syntax and Semantics, North-Holland Pub. Comp., Amsterdam, New York, Oxford, 1981 | MR | Zbl

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