# 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.

• The `(-32)` predefined combinator adds 32 to any number if it is applied in the reverse direction.
• Composition of `f` and `g` applied in the reverse direction feeds inputs of `g` as outputs of `f`.

## 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` `3``3` 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.

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) ↦ (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:

• resurrect a halted execution
• generate a random number
• log events

# 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 between the holes are ping-ponged until one hole gives it up.
• Holes can give up ping-ponging by sending an empty value to the other hole.
• The values emitted on the other sides during ping-ponging are collected and concatenated. These will be the two outputs.

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:

• Lists with list concatenation and the empty list.
• Perturbations with perturbation composition and the identity perturbation.