How to implement recursion with the Y combinator in GNU R using the recursive addition as an example. Originates from this blog post: https://www.matthiaspreu.com/posts/lambda-calculus-recursion/.

y-combinator.R

# Part of a blog post about lambda calculus on my website:
# https://www.matthiaspreu.com/posts/lambda-calculus-recursion/

# Y combinator based on the expression:
#
# Y = λf.(λx.f(xx))(λx.f(xx))
Y <- function(f) {
  fxx <- function(x) { f((x)(x)) } 
    
  (fxx)(fxx)
}

# Abstracted addition function expecting
# the real addition function as a parameter.
# Based on the expression:
#
# λ ADD xy.Z y x SUCC((ADD x (PRED y)))
add_generator <- function(add) {
  function(x,y) {
    if (y == 0) {
      x
    } else {
      add(x,y-1) + 1
    }
  }
}

# Extract our real addition function as the fixed 
# point of add_generator.
add <- function(x,y) { Y(add_generator)(x,y) }

# Example application
print(add(2,2))