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: "b1 b2 b3 ... bn" -> "(PB1(PB2(PB3...(PBn(KK))...)))" or 'AAPB1AAPB2AAPB3...AAPBnAKK'. Here P="S(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K))))(KK)" [stack], and Bi="K" if bi=0 and Bi="SK" if bi=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 "(PB1(PB2(PB3...(PBn(KK))...)))", then we treat "b1b2b3...bn" as bit output of the program, otherwise output is broken, where again if Bi="K" then bi=0 and if Bi="SK" then bi=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: