Categorical combinators

What is an algorithm?

The algorithm is the most essential concept in computer science. There are two typical definitions of it:

  1. An algorithm is a finite sequence of instructions.

    This is the mainstream definition.
    Making this definition formal, we arrive to the Turing-machine (an abstract computer) which is the theoretical base of the so-called imperative programming languages.

  2. An algorithm is a computable function.

    Making this definition formal, we arrive to the Lambda-calculus (the calculus of substitutions) which is the theoretical base of the so-called functional programming languages.

I chose B because its formalisation is less ad-hoc. The Turing-machine has separate memory and control logic. The Lambda-calculus is independent of computer architectures; in fact it was invented before electrical computers.

There are alternatives to Lambda-calculus in formalizing computable functions. One alternative is Combinatory logic. Combinatory logic builds up functions with elementary building blocks called combinators. I chose Combinatory logic because by choosing specific combinators one can tailor the system for specific tasks like creating interactive algorithms. This is more complicated in Lambda-calculus.

For a concrete set of elementary combinators I chose Categorical combinators because I found it the most intuitive and pragmatic set of combinators.

So, in this blog post an algorithm is a structure built up with elementary combinators. Let’s see what does it mean.

Introduction to Categorical combinators

Predefined combinators

Predefined combinators are be built-up with elementary combinators but for didactic reasons their definition is not shown.

First we introduce the rotateRight combinator, which rotates a diagram clockwise by 90°. (The definition of diagrams is not important at this point. They will be used only in examples.)

Examples of applying rotateRight on concrete diagrams:

The algorithm which is built-up with only one rotateRight combinator is visualised as follows:

╔═════════════╗
║ rotateRight ║
╚═════════════╝

Vertical composition

Vertical composition – or just composition – is an elementary combinator with two holes in it:

╔═══════════════╗
║╔═════════════╗║
║║   <hole₁>   ║║
║╚═════════════╝║
║╔═════════════╗║
║║   <hole₂>   ║║
║╚═════════════╝║
║ v-composition ║
╚═══════════════╝

Simplified visualisation:

╔═══════════╗
║  <hole₁>  ║
╠═══════════╣
║  <hole₂>  ║
╚═══════════╝

The holes can be filled in with algorithms. Vertical composition connects the two algorithms by feeding the output of the algorithm in hole₁ into the input of the algorithm in hole₂. (Type systems can ensure that one can only fill in algorithms for which this output-to-input feeding is possible.)

For example, composing rotateRight with itself reflects a diagram through its origin:

╔═════════════╗
║ rotateRight ║
╠═════════════╣
║ rotateRight ║
╚═════════════╝

Function composition is associative which means that the order of composition does not matter:

            ╔═══════╗     ╔═══════╗
╔═════╗     ║╔═════╗║     ║   f   ║
║  f  ║     ║║  f  ║║     ╠═══════╣
╠═════╣     ║╠═════╣║     ║╔═════╗║   
║  g  ║  =  ║║  g  ║║  =  ║║  g  ║║
╠═════╣     ║╚═════╝║     ║╠═════╣║
║  h  ║     ╠═══════╣     ║║  h  ║║
╚═════╝     ║   h   ║     ║╚═════╝║
            ╚═══════╝     ╚═══════╝

For example:

╔═════════════╗
║ rotateRight ║     ╔═══════════════╗     ╔═══════════════╗
╠═════════════╣     ║ reflectOrigin ║     ║  rotateRight  ║
║ rotateRight ║  =  ╠═══════════════╣  =  ╠═══════════════╣
╠═════════════╣     ║  rotateRight  ║     ║ reflectOrigin ║
║ rotateRight ║     ╚═══════════════╝     ╚═══════════════╝
╚═════════════╝

Another example for composition is the Fahrenheit-to-Celsius conversion algorithm:

╔════╗
║-32 ║
╠════╣
║ /5 ║
╠════╣
║ *9 ║
╚════╝
0 -17.7777
100 37.7777

Here (-32) is a predefined combinator which subtracts 32 from any number, (/5) is a predefined combinator which divides any number by 5, and (*9) is a predefined combinator which multiplies any number by 9.

Bidirectional algorithms

The algorithms shown so far are bidirectional which means that one can provide the output to get the input.

For example, the Fahrenheit-to-Celsius conversion algorithm can be used to convert Celsius values to Fahrenheit values too.

Identity combinator

The elementary combinator id gives back its input unchanged.

╔════╗
║ id ║
╚════╝

The identity combinator can be eliminated from composition:

╔════╗     ╔════╗
║ id ║     ║ f  ║     ╔════╗
╠════╣  =  ╠════╣  =  ║ f  ║
║ f  ║     ║ id ║     ╚════╝
╚════╝     ╚════╝

Horizontal composition

Horizontal composition is an elementary combinator with two holes:

╔═══════════════╗
║╔═════════════╗║
║║   <hole₁>   ║║
║╚═════════════╝║
║╔═════════════╗║
║║   <hole₂>   ║║
║╚═════════════╝║
║ h-composition ║
╚═══════════════╝

Simplified visualisation:

╔═════════╦═════════╗
║ <hole₁> ║ <hole₂> ║
╚═════════╩═════════╝

Horizontal composition operates on pairs of values. The algorithms in the holes are executed in parallel.

Example:

╔════╦════╗
║ +3 ║ *2 ║
╚════╩════╝
(4, 5) (7, 10)
(0, 0) (3, 0)

Example for using horizontal and vertical composition in the same algorithm:

╔══════════════════╗
║       dup        ║
╠════╦═════════════╣
║ id ║ rotateRight ║
╠════╩═════════════╣
║     overlay      ║
╚══════════════════╝

dup is an elementary combinator which takes a value and returns a pair of the duplicated value. overlay is a predefined combinator which takes a pair of diagrams and returns a diagram which is made by overlaying the second diagram on the first one.

Wires

A better visualisation of dup and id is to draw wires in their boxes:

╔════════╤═════════╗
║  ╭─────┴──╮  dup ║
╠══╪═╦══════╧══════╣
║id│ ║ rotateRight ║
╠══╧═╩═════════════╣
║     overlay      ║
╚══════════════════╝

A clearer presentation of the same algorithm:

         ╷
   ╭─────┴──╮
   │ ╔══════╧══════╗
   │ ║ rotateRight ║
╔══╧═╩═════════════╣
║     overlay      ║
╚══════════════════╝

Boxes can completely be separated by wires:

                                  ╷                        ╷
         ╷                  ╭─────┴──╮               ╭─────┴──╮
   ╭─────┴──╮               │ ╔══════╧══════╗        │ ╔══════╧══════╗
   │ ╔══════╧══════╗        │ ║ rotateRight ║        │ ║ rotateRight ║
   │ ║ rotateRight ║  =     │ ╠═════════════╣  =     │ ╚══════╤══════╝
╔══╧═╩═════════════╣        │ ║      id     ║        │        │
║     overlay      ║     ╔══╧═╩═════════════╣     ╔══╧════════╧══════╗
╚══════════════════╝     ║     overlay      ║     ║     overlay      ║
                         ╚══════════════════╝     ╚══════════════════╝

We may draw wires instead of the following elementary combinators (the detailed discussion is omitted for brevity):

name example how the wire looks like typically
id 33 vertical bar
assoc ((12, 5), 7)(12, (5, 7)) diagonal bars
swap (3, 4)(4, 3) crossing diagonal bars
first _ first (*2): (4, 3)(8, 3) wires by-passing blocks
dup 8(8, 8) fork
fst (6, 2)6 dead end

There are algorithms to convert freely drawn wires to these combinators. Similar wires will result in identical algorithms which is ensured by the associativity of composition and several laws for id, assoc, swap, first, dup and fst.

Variables

Although ‘variable’ is not a basic concept for Categorical combinators, it can be introduced to simplify complex wires.

Wires can be named:

         ╷
   ╭─────a──╮
   │ ╔══════╧══════╗
   │ ║ rotateRight ║
╔══╧═╩═════════════╣
║     overlay      ║
╚══════════════════╝

Named wires can be hidden:

         a
         
     ╔══════a══════╗
     ║ rotateRight ║
╔══a═╩═════════════╣
║     overlay      ║
╚══════════════════╝

A good visualization tool can mix combinators, wires and variables.

Textual representation

One can use also a textual representation of combinators.

First name anonymous horizontal sides:

     ╔══════a══════╗
     ║ rotateRight ║
╔══a═╩══════b══════╣
║     overlay      ║
╚════════c═════════╝

Then convert boxes to rows:

b <- rotateRight -< a
c <- overlay -< (a, b)

This syntax is the arrow syntax in Haskell. (Unfortunately I could not use the Haskell arrow syntax in the editor implementation because the Haskell arrow notation is desugared to pure functions boxed into combinators instead of the elementary combinators id, assoc, swap, dup etc.)

Other elementary combinators

The remaining elementary combinators not discussed here are related with conditional execution and higher-order algorithms (where algorithms may travel in wires). It’s cool that these features can be turned on and off by allowing or disallowing the corresponding elementary combinators. One can also reduce the power of these features by wrapping the corresponding elementary combinators into less general combinators.

Effectful combinators

Although Categorical combinators are computationally universal, we can add effectful combinators to Categorical combinators. The effectful combinators may simplify the implementation of a whole class of algorithms.

Local state with delay

delay is an elementary combinator which simplifies the implementation of algorithms with local state.

delay has a local state. When delay is given a value, it gives back its local state and replaces its local state with the given value.

For example, suppose that the initial local state of delay is 0:

╔═══════╗
║ delay ║0
╚═══════╝

Examples of sending values through this combinator one after each-other:

5 0
3 5
42 3
3 42

For purists it may be disturbing that the result for input 3 is not always the same. Can we call delay a function? No, we can’t. delay is not a function, it is an algorithm with local state.

Side-note about purity

Algorithms with local state are impure in the sense that they may not give the same output given the same input.

The pure-impure distinction is very important but the world of algorithms is not that black-and-white. There are even more impure algorithms whose effects cannot be reversed, and there are algorithms which have better properties than just being pure: bidirectional, linear, first-order.

One should be aware about these distinctions when making general statements about algorithms. Categorical combinators makes the classification easy by enumerating the combinators used in an algorithm. Type systems – for example, type classes in Haskell – can track the presence of different combinators for us. This is similar to tracking side effects with monads but simpler than that.

Example for composing delay with other combinators:

╔═══════╤═════════╗
║  ╭────╯  ╭────╮ ║
║  │ ╔═════╧═╗  │ ║
║  │ ║ delay ║0 │ ║
║╔═╧═╩═══════╣  │ ║
║║     +     ║  │ ║
║╚══════╤════╝  │ ║
║       ├───────╯ ║
║       │      sum║
╚═══════╧═════════╝
       
5 5
3 8
42 50
3 53

Here (+) is a predefined combinator which adds its two inputs together.

For replacing the wires with combinators in sum we need the so called feedback combinator too:

╔═══════╤════════╗
║    ╭──╯ ╭────╮ ║
║╔═══╧════╧═══╗│ ║
║║   <hole>   ║│ ║
║╚═══╤════╤═══╝│ ║
║    ╰──╮ ╰────╯ ║
║       │feedback║
╚═══════╧════════╝

Halting the execution with halt

halt is an elementary combinator which halts the execution of an algorithm:

╔══════╗
║ halt ║
╚══════╝

In this blog post halt is hidden inside predefined combinators like (/) which divides two numbers. (/) halts the execution if the second number is zero:

╔═══════╗
║   /   ║
╚═══════╝
(4, 5) 0.8
(2, 0) <halt>
(2, 1) 2

The behaviour of algorithms containing both halt and delay is determined by the behaviour of the elementary combinators, but the semantics of elementary combinators should take both effects into account.

halt is useful if we want to allow a user input (like hitting the delete key at the end of a text) but we want no response to it.

Other effectful combinators

With other effectful combinators not discussed here one can:

Different type of bidirectional combinators

Bidirectional combinators can be visualised as follows:

   ▴
   ▾               ▾  ▴
╔══╧══╗          ╔═╧══╧═╗
║     ║    or    ║      ║
╚══╤══╝          ╚═╤══╤═╝
   ▴               ▾  ▴
   ▾

As effectful combinators, bidirectional combinators may simplify the implementation of a whole class of algorithms.

In case of simple bidirectional combinators, each input results an output on the other side.
Examples:

  10                                              28
   ▾                                              ▴
╔══x══╗       ╔══x══╗            ╔══x══╗       ╔══x══╗
║y=x+2║   ↝   ║y=x+2║            ║y=x+2║   ↝   ║y=x+2║
╚══y══╝       ╚══y══╝            ╚══y══╝       ╚══y══╝
                 ▾                  ▴
                 12                30

In case of concurrently bidirecional combinators, each input results in outputs on both sides. An example is the following stateful perturbation transforming combinator which compensates too big perturbations by sending back corrections:

 (-10)              (+4)
   ▾                 ▴
╔══x══╗x=6        ╔══x══╗x=0
║0<y<x║y=2   ↝    ║0<y<x║y=0
╚══y══╝           ╚══y══╝
                     ▾
                    (-2)

Algorithms using bidirectional connections are well-defined if the elementary combinators are well-defined. Here we discuss the semantics of composition only.

In case of simple bidirectional combinators, the semantics of composition is rather simple. Each input goes sequentially through the two holes to the other side, in the right order:

   ▾   ▴
╔══╪═══╪══╗
║╔═╧═══╧═╗║
║║       ║║
║╚═╤═══╤═╝║
║  │   ▴  ║
║  ▾   │  ║
║╔═╧═══╧═╗║
║║       ║║
║╚═╤═══╤═╝║
╚══╪═══╪══╝
   ▾   ▴

In case of concurrently bidirectional combinators, the semantics of composition is more sophisticated:

   ▾         ▴
╔══╪═════════╪══╗
║  │ ╭▸──────┤  ║
║  │ │ ...   │  ║
║╔═╧═╧═══════╧═╗║
║║             ║║
║╚═╤═╤═════╤═╤═╝║
║  │ ▴     │ ▴  ║
║  │ │ ... │ │  ║
║  ▾ │     ▾ │  ║
║╔═╧═╧═════╧═╧═╗║
║║             ║║
║╚═╤═══════╤═╤═╝║
║  │   ... │ │  ║
║  ├──────◂╯ │  ║
╚══╪═════════╪══╝
   ▾         ▴

The values on the wires should have a monoid structure which means that they need to have a composition operation and an empty/identity value. Typical monoids for wires:

Further reading

Conclusion

 

Back to the main page