Editing Combinatory logic (section)

==== 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:

:''T''[''λx''.''λy''.(''y'' ''x'')]
::        = ''T''{{!(}}''λx''.''T''{{!(}}''λy''.(''y'' ''x''){{))!}} (by 5)
::        = ''T''[''λx''.('''S''' ''T''[''λy''.''y''] ''T''[''λy''.''x''])] (by 6)
::        = ''T''[''λx''.('''S I'''       ''T''[''λy''.''x''])] (by 4)
::        = ''T''[''λx''.('''S I'''       ('''K''' ''T''[''x'']))] (by 3)
::        = ''T''[''λx''.('''S I'''       ('''K''' ''x''))] (by 1)
::        = ('''S''' ''T''[''λx''.('''S I''')] ''T''[''λx''.('''K''' ''x'')]) (by 6)
::        = ('''S''' ('''K''' ('''S I'''))   ''T''[''λx''.('''K''' ''x'')]) (by 3)
::        = ('''S''' ('''K''' ('''S I'''))   ('''S''' ''T''[''λx''.'''K'''] ''T''[''λx''.''x''])) (by 6)
::        = ('''S''' ('''K''' ('''S I'''))   ('''S''' ('''K K''') ''T''[''λx''.''x''])) (by 3)
::        = ('''S''' ('''K''' ('''S I'''))   ('''S''' ('''K K''') '''I''')) (by 4)

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:

:          ('''S''' ('''K''' ('''S''' '''I''')) ('''S''' ('''K''' '''K''') '''I''') x y)
::        = ('''K''' ('''S''' '''I''') x  ('''S''' ('''K''' '''K''')   '''I''' x) y)
::        = ('''S''' '''I''' ('''S''' ('''K''' '''K''')   '''I''' x) y)
::        = ('''I''' y ('''S''' ('''K''' '''K''')   '''I''' x y))
::        = (y ('''S''' ('''K''' '''K''')   '''I''' x y))
::        = (y ('''K''' '''K''' x ('''I''' x) y))
::        = (y ('''K''' ('''I''' x) y))
::        = (y ('''I''' x))
::        = (y x)

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''[&nbsp;] construction may expand a lambda term of length ''n'' to a combinatorial term of length [[Big O notation|Θ]](''n''<sup>3</sup>).{{sfn|Lachowski |2018}}