Summary

Turner's S-K Reduction Machine is described.  This innovative proposal
for computer organization seems to offer a way of implementing graph
reduction architectures with reasonable efficiency using "off-the-shelf"
components.  The heart of the proposal is the technique for compiling
HLL function definitions into a kind of "applicative machine language"
based on Curry's "combinators".

In order to motivate and appreciate the ideas of Turner and Curry, we
first give a general overview of the "reduction" approach to computation
focusing on the common features of reduction languages such as FP and
FEL.  We describe the theoretical advantages offered by reduction, as
well as the practical problems which seem to make it unworkable.  Then
we show how the Turner/Curry approach eliminates those problems one
by one.

The compiler algorithm is explained using ALFL (a variant of FEL) as
a source language.  Then we discuss Turner's straightforward design
of a machine to execute the machine code.

Finally, we discuss some possible improvements to the HLL, the compiler,
the machine language, and the hardware.  This includes both recent work
and a few suggested directions for future research.



Sample ALFL Programs

-- ALFL is a language developed at Yale.  It is a hybrid of
-- FEL (Keller, Utah) and SASL (Turner, England).
-- The syntax is mostly self-explanatory.  "==" is used for
-- definitions.  "b->e1,e2" is if_then_else.  "^" is the
-- list constructor "fby".  Instead of the usual infix colon,
-- we represent application by an infix space!  This notation,
-- borrowed from SASL, has some important consequences which
-- will be explained in the lecture.

discr1 a b c == b*b - 4*a*c;

discr2 [a,b,c] == b*b - 4*a*c;

-- discr1 and discr2 are two slightly different functions with
-- the same purpose.  discr1 expects three arguments (one 
-- after the other - more about this later.)  On the other hand,
-- discr2 expects a single argument which must be a three
-- element list.  [a,b,c] is merely a syntacticly sugared
-- version of (a^(b^(c^nil))).  (discr1 2 5 2) evaluates to 9
-- as does (discr2 [2,5,2]).  The choice between the two styles
-- of function definition is basicly a matter of taste.  But
-- be careful not to mix illegally: (discr1 [2,5,2]) is an error.

fib n == n < 2  -> 1,
                   fib (n-1)  +  fib (n-2) ;

fastfib n == {
    RESULT select n fibseq;
    select k (x^s) == {
        j == k-1;
        RESULT  j = 0  -> x,
                          select j s ;
     };
    fibseq == 1 ^ (addstr fibseq (0 ^ fibseq));
    addstr (x1^s1) (x2^s2) == (x1+x2) ^ (addstr s1 s2);
 };

-- Both fib and fastfib give the same results, but fastfib
-- is a more efficient program because it uses the linear
-- dynamic programming algorithm rather than the exponential
-- divide-and-conquer algorithm.  The infinite list fibseq
-- (1 ^ 1 ^ 2 ^ 3 ^ 5 ... ) is not a problem because we are
-- using lazy evaluation.

summ1 s == {
    RESULT  s = nil  ->  0,
                         head s  +  summ1 (tail s) ;
    head (x^y) == x;
    tail (x^y) == y;
 };

-- summ1 does a summation of the elements of a list.  Actually,
-- it was unnecessary to include local definitions of head and
-- tail.  These functions would be globally available primitives.

summ2 nil == 0;
summ2 (x^y) == x + summ2 y ;

-- summ2 does the same thing as summ1.  The choice between these
-- two forms of function definition is again a matter of taste.
-- This idea of "pattern directed invocation" is becoming very
-- popular and appears in many new languages, eg. Prolog and CSP.


Bibliography

1. Turner, D.A., A New Implementation Technique for Applicative
Languages,  Software Practice and Experience 9,31-49 (1979).
     The paper upon which this report is based.  Highly recommended
     that you at least skim this paper before my presentation.  Very
     well written, considering the complexity of the subject matter.
     Available in Sears, or borrow my copy.

2. Burge, W.H., Recursive Programming Techniques, Addison-Wesley 1975.
     The book which gave Turner his first acquaintance with Curry's
     combinators.  Heavy going, but there are probably a few more
     nuggets of inspiration buried in this book that could be mined
     by a careful and imaginative reader.  In Sears.

3. Curry, H.B. and Feys R., Combinatory Logic Vol. I, North Holland 1958
     The standard text on combinators, and on mathematical logic and
     language generally.  One measure of the importance of this work is
     the fact that most of the truly innovative papers in computer 
     languages, from McCarthy to Backus, have included this work in the
     references for no apparent reason.  Curry's writing has a dry,
     pedantic, but somehow sparkling flavor.  Reading Curry is an
     acquired taste, but one which I highly recommend to my fellow
     maniacs who are interested in the foundations of mathematics
     (ie. the stuff that is even more basic than set theory.)

4. Hudak, P. and Krantz, D., A Combinator-based Compiler for a
Functional Language, 1983 POPL Conference Proceedings, pp 122-132.
     My source for ALFL and correction of a bug in Turner's compiler.
     Contains a recent bibliography on other work with combinators 
     since Turner.  Otherwise undistinguished.  Borrow my copy.

5. Treleaven et al., Data Driven and Demand Driven Computer Architecture,
ACM Computing Surveys 14-1 (1982).
     Excellent survey paper which everyone in the course has probably
     already read.  Combinator freaks will want to re-read section 6,
     especially 6.6 and 6.7.  Incidentally, other good survey papers
     by Treleaven appear in the 1981, 1982, and 1983 Architecture
     Conference Proceedings.  These Proceedings contain many other
     interesting papers.  Borrow from various people in the dept.

6. Turner, D.A., On the Semantic Elegance of Applicative Languages,
Proceedings Conference on Functional Programming Languages and
Computer Architecture 1981.
     A case study in problem solving and algorithm design.  Worth a 
     look.  This volume also contains a paper by Backus on the 
     motivation behind FP, and lots of other good stuff.  Someone
     borrowed my copy of this Proceedings and never returned it.
     The only other known copy on this campus belongs to a female
     faculty member.

7. Cohen, J., Garbage Collection of Linked Data Structures, ACM
Computing Surveys 13-3 (1981).
     A good survey paper on algorithms and hardware for handling
     the weak link in Turner's machine.  If you are really interested
     in this area, be sure to look up Cohen's references to Baker.

8. VanderHeyde et al., /u/hunt/amps/fe , VAX
     A collection of FEL programs.  If you still need to be convinced
     that applicative languages work for problems other than computing
     factorials, take a glance at these.