Combinatory logic
Conversion of a lambda term to an equivalent combinatorial term

For example, we will convert the lambda term λx. λy.(y x) to a combinatorial term:

If we apply this combinatorial term to any two terms x and y (by feeding them in a queue-like fashion into the combinator 'from the right'), it reduces as follows:

The combinatory representation, (S (K (S I)) (S (K K) I)) is much longer than the representation as a lambda term, λx. λy.(y x). This is typical. In general, the T construction may expand a lambda term of length n to a combinatorial term of length Θ (n).
detectable_content:number_placeholders[4], length_constraints:number_words[464]