Editing Combinatory logic (section)

=== Examples of combinators ===

The simplest example of a combinator is '''I''', the identity combinator, defined by

:('''I''' ''x'') = ''x''

for all terms ''x''.  Another simple combinator is '''K''', which manufactures constant functions:  ('''K''' ''x'') is the function which, for any argument, returns ''x'', so we say

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

for all terms ''x'' and ''y''.  Or, following the convention for multiple application,

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

A third combinator is '''S''', which is a generalized version of application:

:('''S''' ''x y z'') = (''x z'' (''y z''))

'''S''' applies ''x'' to ''y'' after first substituting ''z'' into
each of them. Or put another way, ''x'' is applied to ''y'' inside the environment ''z''.

Given '''S''' and '''K''', '''I''' itself is unnecessary, since it can be built from the other two:

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

for any term ''x''.  Note that although (('''S K K''')
''x'') = ('''I''' ''x'') for any ''x'', ('''S K K''')
itself is not equal to '''I'''.  We say the terms are [[extensional equality|extensionally equal]].  Extensional equality captures the mathematical notion of the equality of functions: that two functions are ''equal'' if they always produce the same results for the same arguments.  In contrast, the terms themselves, together with the reduction of primitive combinators, capture the notion of ''intensional equality'' of functions: that two functions are ''equal'' only if they have identical implementations [[up to]] the expansion of primitive combinators.  There are many ways to implement an identity function; ('''S K K''') and '''I''' are among these ways.  ('''S K S''') is yet another. We will use the word ''equivalent'' to indicate extensional equality, reserving ''equal'' for identical combinatorial terms.

A more interesting combinator is the [[fixed point combinator]] or '''Y''' combinator, which can be used to implement [[recursion]].