Combinators & combinatory logic

Combinatory Logic

Combinatory logic was invented by Moses Shönfinkel in 1920. The work was published in 1924 in a paper entitled On the building blocks of mathematical logic. Schönfinkel showed how the use of bound variables in logic could be dispensed with. The use of "curried" higher order functions makes possible the reduction of logic to a language consisting of one constructor (the application of a function to an argument) and three primitive constants U, C (now usually called K) and S.

The Mathematical Foundations of Joy by Manfred von Thun

Joy is a functional programming language which is not based on the application of functions to arguments but on the composition of functions. This paper describes the theoretical basis of the language. The denotation of Joy programs maps a syntactic monoid of program concatenation to a semantic monoid of function composition. Instead of lambda abstraction Joy uses program quotation, and higher order functions can be simulated by first order functions which dequote quoted programs.
[See also Atomic Programs of Joy, The Algebra of Joy & Recursion Theory and Joy ]

GUM: a portable parallel implementation of Haskell by K Hammond, JS Mattson Jr, AS Partridge, SL Peyton Jones & PW Trinder

GUM is a portable, parallel implementation of the Haskell functional language which has been publicly released with version 0.26 of the Glasgow Haskell Compiler (GHC). GUM is message-based, and portability is facilitated by using the PVM communications-harness available on most multi-processors, including shared-memory and distributed-memory machines. For example GUM is available by FTP for a Sun SPARCserver multiprocessor and for a network of Sun SPARC workstations.

Lazy Evaluation by Alex Aiken

Turner's paper on lazy evaluation had a profound effect on functional programming. All implementations of lazy functional languages are based directly or indirectly on his implementation ideas. In addition, laziness is not just an implementation trick; it also provides a new software structuring device. One can write programs that generate and use infinite data structures, for example. Provided only a finite portion of those data structures are ever demanded during execution, the program will still terminate. The basic idea is to compile to combinators, which are variable-free functions.

Comparing the Performance of KiR and C on the Multiple Stack Architecture Fast by Claus Aßmann

This paper describes some experiences with the processor architecture Fast which is tailored to the needs of executing untyped functional languages. The architecture is similar to those of conventional RISC processors, though some features have been added and others have been slightly modified. In order to support a fast subroutine call mechanism and efficient parameter passing, our architecture uses a system of four stacks, of which two are easily interchangeable. It also supports runtime type-checking by means of operand tags which are validated during instruction execution. Fast is a 40-bit RISC processor architecture with register-to-register, load/store, call and conditional branch instructions that allow for an efficient implementation of functional (or function-based) languages.

Combinator Graph Reduction: A Congruence and its Applications by David Lester

The G-machine is an efficient implementation of lazy functional languages developed by Augustsson and Johnsson. This thesis may be read as a formal mathematical proof that the G-machine is correct with respect to a denotational semantic specification of a simple language. It also has more general implications. A simple lazy functional language is defined both denotationally and operationally; both are defined to handle erroneous results. The operational semantics models combinator graph reduction, and is based on reduction to weak head normal form. The two semantic definitions are shown to be congruent.

An Investigation into Architectures for a Parallel Packet Reduction Machine by Mark Irvine Greenberg

The Flagship project is a collaborative academic and industrial venture, which aims to produce a complete parallel computer system capable of supporting declarative languages efficiently. A packet-based reduction model of computation has been specifically developed for parallel execution and to support the features of declarative languages. The research described in this thesis examines the machine structures and the organisation needed for efficient packet reduction. Two main areas are covered, the architecture of the reduction processor, and the network to interconnect the processors.

T-Ruby: A tool for handling Ruby expressions

[Uses combinators to define VLSI circuits]

Linear Logic and Permutation Stacks--The Forth Shall Be First by Henry G. Baker

Girard's linear logic can be used to model programming languages in which each bound variable name has exactly one "occurrence"--i.e., no variable can have implicit "fan-out"; multiple uses require explicit duplication. Among other nice properties, "linear" languages need no garbage collector, yet have no dangling reference problems. We show a natural equivalence between a "linear" programming language and a stack machine in which the top items can undergo arbitrary permutations. Such permutation stack machines can be considered combinator abstractions of Moore's Forth programming language.

An Architecture for Combinator Graph Reduction (TIGRE) by Philip J Koopman, Jr

The results of cache-simulation experiments with an abstract machine for reducing combinator graphs are presented. The abstract machine, called TIGRE, exhibits reduction rates that, for similar kinds of combinator graphs on similar kinds of hardware, compare favorably with previously reported techniques. Furthermore, TIGRE maps easily and efficiently onto standard computer architectures, particularly those that allow a restricted form of self-modifying code. This provides some indication that the conventional "stored program" organization of computer systems is not necessarily an inappropriate one for functional programming language implementations.

MaRS: a combinator reduction multiprocessor (in French)

PACE: Parallel Associative Combinator Evaluation

The PACE project is investigating a radically new approach to the construction of an extensible, distributed memory multi-processor architecture. The basic replicable node is a purpose-designed processor, in which dataflow architectural principles are applied directly to a fine-grained graph reduction computational model. This approach not only removes interpretive overheads normally associated with graph reduction models, but also gives rise to a no-cost multi-tasking capability which results in better scalability properties. The processor also incorporates hardware support for management tasks: diffusion scheduling by means of an automatic locally-determined dynamic load control system, autonomous communications and independent concurrent garbage collection.
[See PACE: A prototype design, Internal Report (Jan 95) & PACE: A multiprocessor architecture dedicated to graph reduction].

ACM Transactions on Programming Languages and Systems Volume 14 (1992)

Cache behavior of combinator graph reduction Philip J., J r. Koopman, Peter Lee and Daniel P. Siewiorek Pages 265-297 (See Phil Koopman's Stack Computers bib at CS.CMU

(E.g. S/K/I Combinators in Forth, A fresh look at combinator graph reduction, and Phil's perennial favourite, stack machines in general).

Incoming material

ADVISORY: Email to these sites is filtered. Unsolicited email may be automajically re-directed to the relevant postmaster.