combinatory logic

(redirected from Combinators)

combinatory logic

A system for reducing the operational notation of logic, mathematics or a functional language to a sequence of modifications to the input data structure. First introduced in the 1920's by Schoenfinkel. Re-introduced independently by Haskell Curry in the late 1920's (who quickly learned of Schoenfinkel's work after he had the idea). Curry is really responsible for most of the development, at least up until work with Feys in 1958.

See combinator.
This article is provided by FOLDOC - Free Online Dictionary of Computing (
The following article is from The Great Soviet Encyclopedia (1979). It might be outdated or ideologically biased.

Combinatory Logic


a branch of mathematical logic that studies combinators and their properties. The function and the operation of applying a function to an argument are the fundamental concepts in combinatory logic. Members of a certain class of operations on functions that is closed with respect to application are called combinators. The concept of “combinatorily defined function” as formulated using the terms of combinatory logic was one of the first methods of refining the concept of algorithm. The foundations of combinatory logic were worked out by the Soviet mathematician M. I. Sheinfinkel’ (Schönfinkel; 1924). Most of its results belong to the American logician H. Curry. Combinatory logic finds extensive application in the theory of programming languages.


Ianovskaia, S. A. “Logika kombinatornaia.” In the book Filosofskaia entsiklopediia, vol. 3. Moscow, 1964.
Schönfinkel, M. “Über die Bausteine der mathematischen Logik.” Mathematische Annalen, 1924, vol. 92.
Curry, H. B., and R. Feys. Combinatory Logic. Amsterdam, 1958.
Curry, H. B. “Recent Advances in Combinatory Logic.” Bulletin de la Société mathématique de Belgique, 1968, vol. 20, no. 3.
The Great Soviet Encyclopedia, 3rd Edition (1970-1979). © 2010 The Gale Group, Inc. All rights reserved.
References in periodicals archive ?
Using C++14 standard we made small implementations of lambda calculus, such as combinators, conditionals, booleans and numbers.
Schonfinkel (1889-1942) that introduced logical combinators (e.g.
Lexicalized grammars then use a small set of language-independent rules called combinators to combine lexical categories to produce a parse of the sequence of tokens into a complete sentence.
Instead parsing is viewed as a search defined by the category chosen for each terminal symbol and the set of combinators used to combine categories to build the parse.
Using example domain specific language case studies, the volume covers topics such as understanding internal DSL implementation patterns, DSL design in Ruby, Groovy and Clojure, DSL with Scala, external DSL artifacts, and designing external DSLs using Scala parser combinators. Chapters include detailed code examples and illustrations.
Additional Key Words and Phrases: Abstract machines, compilers, combinators, functional programming, program transformation
The last language An consists of functional expressions that can be seen as assembly code (essentially, combinators with explicit sequencing and calls).
We design a system with six Basic Combinators and prove that it is powerful enough to embed the full asynchronous [Pi]-calculus, including replication.
Additional Key Words and Phrases: Functional completeness, Quine-Bernays combinators
In fact, Migicovsky used his InPulse watch to present and pitch during <a href="">Y Combinator's demo day</a>&nbsp;a few weeks ago.