SKI Combinator Calculus in JavaScript

2017-07-06
note combinator calculus

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.

Combinatory terms

  • x variable
  • P primitive function
  • (Eā‚Eā‚‚) application of combinatory terms

Primitive Combinators

It requires only two primitive functions:

  • K x y = x constance function
  • S x y z = x z (y z) substitution function

but commonly there is a third primitive function for convenience.

  • I x = x identity function

I is the same as SKK.

Examples

Identify without the primitive identity function.

((S K K) x)
    = (S K K x)
    = (K x (K x))
    = x

Constant function.

(K (K a b) (K a))
    = (K (a) (K a))
    = a

Limited reduction.

(K a)
    = (K a)

Boolean logic. True is T and returns the first argument.

Txy = Kxy = x

False is F and returns the second argument.

SKxy = Ky(xy) = y

JavaScript Implementation

There is a cons function to create LISP style cons lists. The mkExpression function creates an associative array with a type, primitive or variable and a value which is a single character.

stringToTree

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.

fold

Recursively build a cons binary tree from an array.

fixedPoint

Recursively reduce a tree until reduce does not make any changes to the tree.

reduce

Perform convert on a subtree if the node has a primitive on the left hand side.

convert

If the leftDepth matches the number of arguments that a primitive takes and a primitive exists at that left side depth, perform a reduction.

leftDepth

Count the number of cars in a tree.

References