Implementing SASL using Categorical Multi-Combinators

machines INTRODUCTION Functional programs consist of definitions of functions and other objects. The execution of a program in a functional language consists of the evaluation of an expression, and we can see this as proceeding by successive rewriting of an expression until it takes printable (or normal) form. (A normal form is one that cannot be rewritten further.) For example, if we say fac n = n * fac(n-1) , n¿0 (1) = 1 , otherwise then fac 2 is rewritten thus 0038-0644/90/000000-00$05.00 Received 28 September 1987 c fl1990 by John Wiley & Sons, Ltd. Revised 18 May 1988 and 24 April 1990 2 R.D.LINS AND S.J.THOMPSON fac 2 ) 2 fac (2 \Gamma 1) (2) ) 2 fac 1 ) 2 (1 fac (1 \Gamma 1)) ) 2 (1 fac 0) ) 2 (1 1) ) 2 1 ) 2 The definition (1) is used in the first line of (2) where we have to substitute the actual value 2 for the variable n - this process of parameter passing forms the major overhead in rewriting implementations of functional languages. The method of compi..