What are combinators?
I'm looking for:
I'm not looking for:
From a practical viewpoint combinators are kind of programming constructs that allow you to put together pieces of logic in interesting and often advanced manners. Typically using them depends on the possibility of being able to pack executable code into objects, often called (for historical reasons) lambda functions or lambda expressions, but your mileage can vary.
A simple example of a (useful) combinator is one that takes two lambda functions without parameters, and creates a new one that runs them in sequence. The actual combinator looks in generic pseudocode like this:
func in_sequence(first, second):
lambda ():
first()
second()
The crucial thing that makes this a combinator is the anonymous function (lambda function) on the second line; when you call
a = in_sequence(f, g)
the resulting object a is not the result of running first f() and then g(), but it is an object that you can call later to execute f() and g() in sequence:
a() // a is a callable object, i.e. a function without parameters
You can similarly then have a combinator that runs two code blocks in parallel:
func in_parallel(first, second):
lambda ():
t1 = start_thread(first)
t2 = start_thread(second)
wait(t1)
wait(t2)
And then again,
a = in_parallel(f, g)
a()
The cool thing is that 'in_parallel' and 'in_sequence' are both combinators with the same type / signature, i.e. they both take two parameterless function objects and return a new one. You can actually then write things like
a = in_sequence(in_parallel(f, g), in_parallel(h, i))
and it works as expected.
Basically so combinators allow you to construct your program's control flow (among other things) in a procedural and flexible fashion. For example, if you use in_parallel(..) combinator to run parallelism in your program, you can add debugging related to that to the implementation of the in_parallel combinator itself. Later, if you suspect that your program has parallelism-related bug, you can actually just reimplement in_parallel:
in_parallel(first, second):
in_sequence(first, second)
and with one stroke, all the parallel sections have been converted into sequential ones!
Combinators are very useful when used right.
The Y combinator, however, is not needed in real life. It is a combinator that allows you to create self-recursive functions, and you can create them easily in any modern language without the Y combinator.
It is wrong to brand Y-combinator as something that won't "help to get the work done". I've found it very useful in a number of occasions. The most obvious case is when you have to quickly bootstrap some embedded interpreted language. If you provide a minimal set of primitives, namely sequence, select, call, const and a closure allocation, it is already sufficient for building up a complete, arbitrary complex language. No special support for recursion is needed - it can be added via a fixed point combinator. Otherwise you'll need much more complicated primitives.
Another obvious case for combinators is obfuscation. A code translated into the SKI calculus is practically unreadable. If you really have to obfuscate an implementation of an algorithm, consider using combinators, here is an example.
And, of course, combinators are an important tool for implementing functional languages. The easiest approach (as in the example above) is via SKI or equivalent calculus. Supercombinators are used in some other implementations. This book talks about it in depth.
This is a joke, but a joke worth a very careful reading, since many arcane programming techniques and theories are covered there.
Digging around a bit, I found a StackOverflow question, Good explanation of “Combinators” (For non mathematicians) that's a close cousin of this question. One of the answers pointed to Reginald Braithwaite's blog, Homoiconic, which links to several useful examples of combinators in code (e.g. the K combinator, implemented by Ruby's Object#tap method - read the page for examples of why it's useful).
The Wikipedia page on Combinatory Logic describes combinators more globally.
Preface: All the other answers here seem to be defining "combinators" as "higher-order functions". The definition I use in this answer is very different, and I think more useful than a synonym for "higher-order functions" (although the specific names "combinator" and "pure" are awful names for this definition I use herein).
Combinators are functions whose bodies do not reference any values defined somewhere outside that same function body. Put another way: combinators' inputs can only be parameters. If the function uses any variable made available in an enclosing/parent function's definition (sometimes called "parent scopes", or the "context" attached to a closure), or via some other mechanism by which functions can access external values (such as some "global" or "static" variables), then it's not a combinator.
function f(){
let contextual = 6
// Neither "pure" nor a combinator.
// Any other function that reads from `contextual` will act
// differently depending upon whether or not this function happens
// to have been executed beforehand.
function notAPureFunction(a, b){
contextual = 15
return a - b
}
// A "pure" function, but not a combinator.
// This function needs a variable named "contextual" to be
// present in the current scope in order to run correctly. If you
// move this function outside of `f`'s body, it may even find some
// *other* variable which happened to be named "contextual" and
// read its value!
function notACombinator(a, b){
return contextual + a * b
}
// Both a "pure" function and a combinator.
// This function doesn't need to be defined inside `f` at all!
// If, later, it turns out you want this function's functionality
// to be re-used elsewhere, you can move this function definition
// without modifying its body whatsoever.
function combinator(a, b){
return a + b / 2
}
}
This gives combinators a property distinct from all other functions: the context in which they were defined cannot influence their behaviour. If a function is a combinator, that means you can cut and paste its definition anywhere in your code and know, certainly, that it will do the same thing given the same inputs.
Compare this with "pure" functions in "functional programming": because they don't modify (only read from) any value defined outside the function, the context in which pure functions execute cannot influence their behaviour.
Combinators are a subset of pure functions. Not only can they not modify values "outside" the function; they can't even read outside values. They're immune to the context of their execution and their definition.
The practical value of this is similarly comparable to the practical value of pure functions: you gain resilience/robustness to changes in your codebase. Combinators are even more modular, and thus even more testable than pure functions. Also, by virtue of the fact that the parameters describe all a combinators' inputs, discerning the behaviour of combinators is more explicit and simpler compared to other functions.
Returning to the subject of definitions/terminology: from a programming perspective it might be useful to abandon "combinator" entirely and instead name the "no non-local references" property "acontextual" or "local-only", and to name the "all parameters and the return value are functions" property "exclusively higher-order" or "meta-". The properties are orthogonal to each other, so it'd be useful for each to have their own name, which we could compose together so that what is currently called a "combinator" by many might instead be called an "acontextual metafunction".
