Combinatory logic is a variant of lambda calculus that does not have bound variables. SKI combinator calculus is a combinatory logic, a reduced version of untyped lambda calculus. While it is impractical for real world use, it is an extremely simple Turing complete language. Lambda calculus can be translated into SKI calculus as binary trees. Combinatory logic eliminates free variables. A combinator is a higher-order function that uses only function application to define a result.
(E₁E₂)application of combinatory terms
It requires only two primitive functions:
K x y = xconstance function
S x y z = x z (y z)substitution function
but commonly there is a third primitive function for convenience.
I x = xidentity function
I is the same as
Identify without the primitive identity function.
((S K K) x) = (S K K x) = (K x (K x)) = x
(K (K a b) (K a)) = (K (a) (K a)) = a
(K a) = (K a)
Boolean logic. True is
T and returns the first argument.
Txy = Kxy = x
F and returns the second argument.
SKxy = Ky(xy) = y
There is a
cons function to create LISP style cons lists. The
mkExpression function creates an associative array with a
variable and a
value which is a single character.
Remove all white space because there may be multiple white spaces between parentheses and single character primitives and variables. Then prepend everything with a white space to be able to split everything into an array and use
fold to create a cons binary tree.
Recursively build a cons binary tree from an array.
reduce a tree until
reduce does not make any changes to the tree.
convert on a subtree if the node has a primitive on the left hand side.
leftDepth matches the number of arguments that a primitive takes and a primitive exists at that left side depth, perform a reduction.
Count the number of
cars in a tree.