SLIPS(ID:1271/sli007)Applicative language based on Lambda-Calculus, working by Wadsworth-style call-by-need, and featuring a novel two-directional interpretive algorithm Related languages
References: Extract: Introduction Introduction The LAMBDA-Calculus possesses several features of programming languages. For example, bound variables in the LAMBDA-Calculus correspond to formal parameters in a procedure; and the type-free aspect corresponds to the fact that for a machine a program and its data are the same, namely, a sequence of bits. Turing showed that inspite of its very simple syntax, the LAMBDA-Calculus is strong enough to describe all mechanically computable functions. Therefore, the LAMBDA-Calculus can be viewed as a programming language in which the primitive instructions are renaming (the ALPHA-renaming) and reduction (the BETA-reduction) rules. A computation in this programming language consists of the application of a sequence of such primitive instructions. The computation is said to be complete when there is no way of renaming bound variables such that further reduction rules can be applied. The BETA-reduction rule is the basic evaluation rule of the LAMBDA-Calculus and corresponds essentially to substitution of an actual parameter for all instances of a bound variable in the body of the LAMBDA-expression. The LAMBDA-Calculus is insensitive to the order in which instructions are executed (substitutions are performed). The two common orders of evaluation of a LAMBDA-expression are (i) normal order (or call-by-name) and (ii) applicative order (or call-by-value). But, inspite of all its features of a programming language, the LAMBDA-Calculus is not a very convenient notation for writing actual programs. However, it is not difficult to add "syntactic sugar" to it and develop a practical programming language based on the LAMBDA-Calculus. In this paper we present a Small language for Instruction Purposes (SLIPS), which is a "sugared" version of the LAMBDA-Calculus notation, and, although it does not introduce new ways of creating functions, this "sugaring" does increase the palatability of the language for practical programming purposes. SLIPS is applicative (and so is the LAMBDA-Calculus) and retains the lexical binding of the LAMBDA-Calculus. We first introduce the language SLIPS and then present a call-by-need reduction algorithm, called the SLIPS interpreter, for the same. Both call-by-value and call-by-name mechanisms of function invocation perform extra evaluations and, thus, are not efficient. With call-by-value, arguments are always evaluated before a function is applied. This implies that (possibly non-terminating) evaluations are performed on arguments that are not actually used in the function body. On the other hand, call-by-name re-evaluates the same argument several times if the formal parameter bound to it has many occurences in the function body. The call-by-need reduction method suggested by Wadsworth seems satisfactory and eliminates the drawbacks of both call-by-value and call-by-name (at least in purely applicative languages). It consists of evaluating the arguments the first time they are needed in the evaluation of the function body, storing these values and then using them everytime thereafter. This means that an argument is evaluated at most once, its evaluation being delayed until first needed. The interpreter has been implemented in PASCAL. Extract: Concluding Remarks Concluding Remarks We presented an applicative language, SLIPS, based on the LAMBDA-Calculus. The latter was used as a metalanguage to describe the various operations in the former. We also gave a call-by-need reduction algorithm for our language. As for the performance of our algorithm, we note that call-by-need is still a nonoptimal computation rule although it improves both call-by-name and call-by-value. In fact, in the term ((LAMBDA f(PLUS (f l)(f 2)))(LAMBDA x(PLUS x(PLUS 3 4)))) the redex (PLUS 3 4) is reduced twice. Apparently this problem is inherent to call-by-need algorithms. But it seems that this is not a real source of inefficiency in practice. Our reduction algorithm is re-entrant which means that the initial representation of an expression is never modified. This allows sharing of subexpressions and eliminates copying. The SLIPS interpreter would give correct results on correct inputs. Its behaviour on wrong inputs cannot be predicted. This interpreter can also be used to reduce pure LAMBDA-expressions. in Computer Languages 11(1) view details |