A lambda-calculus model of programming languages—II. Jumps and procedures

The correspondence between programming languages and the lambda-calculus presented in Part I of the paper is extended here to include iteration statements, jumps, and procedures. Programs containing loops are represented by lambda-expressionswhose components are specified recursively by means of systems of simultaneous conversion relations. The representation of call-by-name and side-effects in a program is accomplished without any resort to the concepts of memory and address by making use of a number of variables in addition to those declared by the programs; with the aid of these additional variables, the parameter linkage operations can be simulated by pure substitution. The applicability of the model to the problems of proving program correctness and equivalence is demonstrated by means of examples.     

Optimization of very high level languages—II. Deducing relationships of inclusion and membership

SETL is a set-theoretically oriented language of very high level whose reportoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples useable as mappings. This two-part paper studies the optimization problems associated with such a language. The first issue studied is that of copy optimization, i.e. the discovery of cases in which changes to a compound data object can be made “differentially” without recopying the whole of the object. The second part of the paper sets forth techniques for the automatic discovery of relationships of inclusion and membership on which automatic data-structure choice may be based. The methods used extend known techniques of data-flow analysis and of logical program analysis.     

Handin — a system for helping with the teaching of programming

A system has been implemented that enables students on a programming course to hand in programs for assessment without the need for printed listings to be generated. The system test runs all submitted programs using standard sets of data, and then facilitates the marking of these programs by the staff teaching the course. The implementation of this system is described, and the experience gained from using it is discussed.