is a derivation. Assuming a sequence is a valid derivation to begin with, it can be extended using these rules. All derivations of length 1 are valid derivations. Recursive parameter passing and quoting quotes q and ignores i forms a binary tree that parameters can flow from root to branches and be read by identityFunc=((SK)K) or read a quoted lambda q using Kq. SKI expressions Self-application and recursion SII is an expression that takes an argument and applies that argument to itself: SIIα = Iα(Iα) = αα This is known as U combinator. One interesting property of it is that its self-application is irreducible: SII(SII) = I(SII)(I(SII)) = SII(I(SII)) = SII(SII) Another thing is that it allows one to write a function that applies one thing to the self application of another thing: (S(Kα)(SII))β = Kαβ(SIIβ) = α(Iβ(Iβ)) = α(ββ) This function can be used to achieve recursion. If β is the function that applies α to the self application of something else, β = S(Kα)(SII) then the self-application of this β is the fixed point of that α: SIIβ = ββ = α(ββ) = α(α(ββ)) = If α expresses a "computational step" computed by αρν for some ρ and ν, that assumes ρν' expresses "the rest of the computation" (for some ν' that α will "compute" from ν), then its fixed point ββ expresses the whole recursive computation, since using the same function ββ for the "rest of computation" call (with ββν = α(ββ)ν) is the very definition of recursion: ρν' = ββν' = α(ββ)ν' = ... . α will have to employ some kind of conditional to stop at some "base case" and not make the recursive call then, to avoid divergence. This can be formalized, with β = Hα = S(Kα)(SII) = S(KS)Kα(SII) = S(S(KS)K)(K(SII)) α as Yα = SIIβ = SII(Hα) = S(K(SII))H α = S(K(SII))(S(S(KS)K)(K(SII))) α which gives us one possible encoding of the Y combinator. The reversal expression S(K(SI))K reverses the following two terms: S(K(SI))Kαβ → K(SI)α(Kα)β → SI(Kα)β → Iβ(Kαβ) → Iβα → βα Boolean logic SKI combinator calculus can also implement Boolean logic in the form of an if-then-else structure. An if-then-else structure consists of a Boolean expression that is either true (T) or false (F) and two arguments, such that: Txy = x and Fxy = y The key is in defining the two Boolean expressions. The first works just like