Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What are combinators?

I'm looking for:

  • a practical explanation
  • examples of how they are used
  • examples of how combinators improve the quality/generality of code

I'm not looking for:

  • explanations of combinators that don't help me get work done (such as the Y-combinator)
share|improve this question

3 Answers 3

up vote 13 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
This addresses the second bullet point of my question. Thanks for the example! –  Matt Fenwick Nov 2 '11 at 18:06
    
This post has some good links but doesn't actually answer the question directly. Answers should be complete on their own, and use links as references if necessary. –  Aaronaught Nov 3 '11 at 0:06

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.

share|improve this answer
    
@MattFenwick, a need to drop in a simple embedded interpreter often arises where you will never expect it. E.g., in my case it was a language I had to design in order to extend a communication protocol. Simple IPC was not enough, so the protocol had to be executable. –  SK-logic Nov 3 '11 at 13:31
    
@MattFenwick, as for your question: you can try writing some code in APL or J. Combinators are essential there, so you'll get an idea of how to apply them properly. Also, reading on point-free style may help: en.wikipedia.org/wiki/Tacit_programming –  SK-logic Nov 3 '11 at 13:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.