ON TRANSFORMATIONS OF UNTYPED FUNCTIONAL PROGRAMS AND THEIR PROCEDURAL SEMANTICS

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Submitted: 2025-02-22; Published: 2025-02-22

This work is licensed under Creative Commons Attribution–NonCommercial International License (CC BY-NC 4.0).

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.