Combinatory logic language. This language described in John Tromp's paper "Kolmogorov Complexity in Combinatory Logic" is based on K and S combinators encoded into bits. There are 2 representations of data: stack and tree. In tree representation the data is a tree with nodes A and leaves K and S, where A is application of left branch to right branch. For example, 'AAKSAKS' means A[ A[K,S], A[K,S] ]. In stack representation the data is a sequence of K, S, or R, where R is a reference to another sequence. For example, "SKS(SKK)" means 2 stacks: "SKSR" and "SKK", and R refers to the second stack. More examples:

Tree | Stack |
---|---|

'ASK' | "SK" |

'AASKK' | "SKK" |

'AAASKKAASKS' | "SKK(SKS)" |

Evaluation is being done by the following 2 rules:

Tree | Stack |
---|---|

'AAKXY' -> 'X' | "KXY" -> "X" |

'AAASXYZ' -> 'AAXZAYZ' | "SXYZ" -> "XZ(YZ)" |

The evaluation can be done for any subtree in tree representation, or for any stack from the left side in stack representation.

The characters of the language are bits. Every program consists of
2 parts: code and input. The code is self-delimited and presented
as "tree" string where A is 1, S is 00, and K is 01.
Examples: 'ASK' is 10001, 'AASKK' is 11000101. The input is a string
of any bits which is converted to a form (data representation)
in the following way:
"b_{1} b_{2} b_{3} ... b_{n}"
->
"(PB_{1}(PB_{2}(PB_{3}...(PB_{n}(KK))...)))" or
'AAPB_{1}AAPB_{2}AAPB_{3}...AAPB_{n}AKK'.
Here P="S(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K))))(KK)" [stack],
and B_{i}="K" if b_{i}=0 and
B_{i}="SK" if b_{i}=1.
If we denote code as C and input as S then the whole form
ready to evaluate is 'ACS'. After evaluation, if the output is
in the form of list
"(PB_{1}(PB_{2}(PB_{3}...(PB_{n}(KK))...)))",
then we treat "b_{1}b_{2}b_{3}...b_{n}" as
bit output of the program, otherwise output is broken, where again
if B_{i}="K" then b_{i}=0 and
if B_{i}="SK" then b_{i}=1.

For example, the program 11000101101 is: C=11000101, S=101, C='AASKK'="SKK", S='AAPASKAAPKAAPASKAKK'="P(SK)(PK(P(SK)(KK)))"

C++ interpreters to the language:

- mcli.cpp tree interpreter, inputs binary string
- mclp.cpp stack interpreter (faster then tree interpreter), inputs ks-string
- b2ks.cpp binary to ks-string converter