ON TRANSFORMATIONS OF UNTYPED FUNCTIONAL PROGRAMS AND THEIR PROCEDURAL SEMANTICS

Abstract

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 algo-rithms that are based on two operations: a substitution and a one-step β-reduction.