SK/SKI/BCKW Combinator Calculus

Most of the information you can find online about SK/SKI/BCKW combinator calculus is fragmentary, intended for a specific, usually academic, purpose, or just hard to find.

To remedy this, at least for me, I will be putting as much stuff I can find here, with links to sources if I have them.

Consider the SK calculus expressions under each section to be using different "namespaces". In other words, the symbols (barring S, K, I, B, C, K, and W) defined in one section don't carry over into other sections unless specified. For example, under "Birds", T represents a Thrush, but under "Logic" it represents True.

If you want to try simplifying some expressions, you can use any number of interpreters, though they usually expect it in a specific form, not necessarily the one used here. You can also use my one, which is fast and probably not innaccurate.

Extra Reading and Sources

Introduction

In SK calculus, everything is a function, which for these purposeses, is a thing represented by a letter or symbol that can be 'applied' to other functions.

The application of "x" to "y" is written as "xy". An application between two functions is also a function and can be applied to other functions. The application of the application of "x" to "y" to "z" is written as "xyz". Because applications are also functions, you can apply functions to applications, which is different from applying applications to functions. The application of the function "x" to the application of "y" to "z" is written as "x(yz)".

On top of this, the application of a specific function can be defined to be equivalent to some other combination of applying functions. For example, say you define "Fxy" as equivalent to "y", than you can simplify other expressions containing "F". "F(Fab)(Fc)e" becomes simply "e" and the rest follows from there.

This is similar to lambda calculas, except in lambda calculas functions need to be defined first. In SK calculus (and friends), at least two functions must be defined beforehand by context (S, and K, for example), and all other functions are defined as combinations of them.

The following functions are, for historical reasons, considered "standard".

Because B, C, W, and I can be defined (relatively) easily in terms of S and K, they are sometimes left out of a base definition, though still useful.

Arithmetic

Everything in SK calculus is a function, so numbers must be too. A traditional way of representing numbers as functions is using Church numerals, where the representation of a number N is a function that applies it's first argument to it's second N times. In SK calculus, it is easy to define a successor function "+" that increments a number given to it, and then the numbers 1 and 0. From there, all other numbers can be defined.

A predecessor function "-" (for decrementing numbers) can also be defined, although it is somewhat slow and large.

Adding numbers is easy, use b+a, where a and b are the numbers you want to add, and "+" is the successor function. Subtraction is done the same way but with minus instead of the plus. Another easy operation, counter-intuitively, is exponentation. "a to the power of b" is written as ba. Multiplication takes the form b(a+)0, where the result is "a multiplied by b".

In summary:

Division is weird but I derived a division operator (with the help of the birds and lambda calculus). "a divided by b" is "/ba":

It works using recursion and stuff. Bear in mind that it is very slow for "large" numbers (15 for example).

Logic (and lists)

Boolean logic can be expressed using ifelse-like statements, meaning that True is a function that returns the first of it's two arguments, and False returns the second.

The basic AND, OR, and NOT operators can be created just by using True and False. "a AND b" can be rephrased as "if a is True, than b, otherwise False". Likewise "a OR b" can be rephrased as "if a is True, than True, otherwise b". Finally, "NOT a" can be rephrased as "if a is True, than False, otherwise True".

Other commonly used operators can also be formed using these three.

Lists can be created with a join function "," that applies the third argument to the first two, allowing either of them to be retrieved. Using this join function, a list of five values a, b, c, d, and e can be written ,a(,b(,c(,d(,eK)))). Because True returns it's first argument and False returns it's second argument, they can be given to a list to return the corresponding sides of the join.

Birds

Sourced from: Combinator Birds.