This page is a work in progress. Here be dragons.

Combinators are higher-order functions in concatenative languages.

Combinators as data flow

Most languages use named variables for storing values, and routing them where they need to be. When a value needs to be used in more than one place, or passed through several steps of computation, a name gives you a way to refer to it again without losing track of it.

Concatenative languages, on the other hand, allow the programmer to express more complex dataflow schemes using combinators, removing the need for naming values in many cases. For example, bi fans a single value out to two quotations, bi@ runs two values through the same quotation, and keep calls a quotation preserving the value it consumes.

Combinators as control flow

Languages like Factor and Growl use combinators for expressing control flow and looping. For example, in Growl, there is no if construct built into the language, nor branching opcodes in its virtual machine.

A combinator like if is simply constructed from the primitives ?, which selects between two values based on a flag, and call, which calls a quotation in the stack.

Looping can be achieved by using tail-recursion, such as the definition of list/each in Growl’s standard library:

def list/each {
  if: over nil =
    [2drop]
    [
      [[head] dip call] 2keep
      [tail] dip list/each
    ];
}

Writing combinators

When writing combinators you should try to keep the stack clean when calling the quotation, which can be done using the retain stack or preserving combinators such as dip and keep. For example, the times combinator in Growl moves its state to the retain stack before calling the provided quotation:

def times {
  if: over 0 =
    [2drop]
    [swap over >r >r call r> 1 - r> times];
}

This allows the quotation to access the stack cleanly, which is important for keeping track of state across iterations. For example, we can write a word to get the nth Fibonacci number using times by leaving the seed numbers in the stack:

def fib {
  0 1 dig [dup [+] dip swap] times drop
}