next up previous contents
Next: Example of Step by Up: Using the Y Combinator Previous: Introduction   Contents
New book on A++ and the Lambda Calculus available!

Steps to Eliminate Implicit Recursion

  1. recursive function to calculate the factorial including illegal implicit recursion:

    FAC = lambda n.(IF (= n 0) 1 (* n (FAC (- n 1))))

  2. locating illegal implicit recursion:

    FAC = lambda n.(... FAC ...)

  3. eliminating illegal implicit recursion:

    FAC = (lambda fac. lambda n.( ... fac ...) FAC)

  4. simplified representation:

    FAC = (M FAC)

    where:

    M = lambda fac. lambda n.(... fac ...)

    The recursion is eliminated by enclosing the recursive function in a lambda abstraction, that receives the function to be invoked recursively as an argument.

  5. Using definition 12 and the result in step 4 fixed point is identified as a fixed point of M.

    Therefore we can write:

    FAC = (Y M)

  6. The function to calculate the factorial can now be rewritten as:

    FAC = (Y lambda fac. lambda n.(... fac ...))

  7. To compute the factorial of n the following expression has to be evaluated:

    (( Y lambda fac. lambda n.(... fac ...)) n)


Georg Loczewski 2003-08-07
Impressum und Datenschutz