Simple lambda-calculus model of programming languages

UNCLASSIFIED ABSTRACT We present a simple correspondence between a large subset of ALGOL 60 language and lambda-calculus. With the aid of this correspondence, a program can be translated into a single lambda-expression. In general, the representation of a program is specified by means of a system of simultaneous conversion relations among the representations of the program constituents. High-level programming language features are treated directly, not in terms of the representations of machine-level operations. The model includes input-output in such a way that when the representation of a (convergent) program is applied to the input item representations , the resulting combination reduces to a tuple of the representations of the output items. This model does not introduce any imperative notions into the calculus; the descriptive programming constructs, such as expressions, and the imperative ones, such as assignments and jumps, are translated alike into pure lambda-expressions. The applicability of the model to the problems of proving program equivalence and correctness is illustrated by means of simple examples.