Recursion

Just as normal lambda calculus, bruijn does not support typical recursion.

If you want to recursively call a function (or imitate for/while loops), you need to use fixed-point combinators like y from std/Combinator.

Fixed-point combinators have the fascinating property of inducing recursive behaviour in programming languages without support for recursion.

Say we want a function g to be able to call itself. With the y combinator the following equivalence is obtained:

  (y g)
⤳ [[1 (0 0)] [1 (0 0)]] g
⤳ [g (0 0)] [g (0 0)]
⤳ g ([g (0 0)] [g (0 0)])
≡ g (y g)

With this equivalence, g is able to call itself since its outer argument is the initial function again.

Example for using y to find the factorial of 3:

# here, `1` is the induced outer argument `(y g)`
# `0` is the accumulator (the argument of `factorial`)
g [[=?0 (+1) (0 ⋅ (1 --0))]]

factorial y g ⧗ Number → Number

:test ((factorial (+3)) =? (+6)) (true)

In the wild it might look like this:

# 3 abstractions => two arguments
# 2 is recursive call
# 1 is accumulator (+0)
# 0 is argument (list)
length z [[[rec]]] (+0) ⧗ (List a) → Number
    rec 0 [[[case-inc]]] case-end
        case-inc 5 ++4 1
        case-end 1

Read list data structure for more information. Also read coding style for other style suggestions.

Mutual recurrence relations

For solving mutual recurrence relations, you can use the variadic fixed-point combinator y* from std/List. This combinator produces all the fixed points of given functions as an iterable list.

Example even?/odd? implementation using y*:

# the odd? recursive call will be the second argument (1)
g [[[=?0 true (1 --0)]]]

# the even? recursive call will be the first argument (2)
h [[[=?0 false (2 --0)]]]

even? head (y* (g : {}h)) ⧗ Number → Boolean

odd? tail (y* (g : {}h)) ⧗ Number → Boolean

Read more about this in the blog post Variadic fixed-point combinators.