reduction languages for reduction machines
This paper describes a particular realization of a Lambda-Red language as a machine language. Parts of it resemble the Lambda Calculus or a transposed form of it. A constructor syntax is employed such that a linearized preorder representation of the syntax tree is the information structure on which the machine operates. Instances of reduction rules are recognized by combinations of constructors and atoms. Reduction rules with 1, 2 and 3 constructors and/or atoms have been described.A recursive control structure forms the essential part of the implementation. There is a one to one correspondence between constructor syntax and control structure rather than a simulation of recursive structure by von Neumann type instruction sequencing. Thus the system is easily expandable by new constructors and atoms. Execution, that is the application of reduction rules, is subsumed under editing. Emphasis has been on the following pragmatic concepts: locality of action, directness, and security. There are no error messages, errors appear as irreducible expressions. There is no "RUN" instruction, instead the number of reductions to be performed is specified. Whatever happens - it is restricted to subexpressions. The user has the security that all his actions are limited and predictable.The machine language resembles a higher level programming language, but it is "variable-free": expressions are named, not boxes which contain expressions. There seems to be a concept of late binding. However, this is not made a matter of principle, but a matter of degree. Between a general statement of a problem and the result are many intermediate representations - all in the same language - corresponding to various degrees of binding parameters. The user has complete freedom in the choice of variable names. There is a specially developped protection system which avoids confusion of variables.The efficiency of the system is limited by the rate characters can be processed which is essentially determined by the control store cycletime. Measurements will be performed as soon as a simulation of the system is available. Three other important subjects, namely arithmetic, the definition of constants, and source sink input-output will be reported later.
reduction language paper lambda calculus representation tree informal structure rules recursion control implementation simulation instruction sequence systems applications edit pragmatics concept locality action direct secure errors message express user predict programming language variability binding general completeness protection efficiency character measurement definition input