3 ms·

The key realization for me was that in lambda calculus, "A function can’t call itself by name, so we will have to find an alternative way." The rest is smart a

by Rygian 2y ago

The key realization for me was that in lambda calculus, "A function can’t call itself by name, so we will have to find an alternative way." The rest is smart acrobatics.

bmacho 2y ago
A 'function' can't call itself (by name or by any other method), but since 'functions' can call each other, and can make each other to call each other, recursion is mostly trivial. You try it, then you'll get a working recursion one way or another. (Lambda calculus don't operate on functions, but on expressions/lambda terms.)
Joker_vD 2y ago
let odd'(n, odd, even) = if n == 0 then False else even(n-1, odd, even) let even'(n, odd, even) = if n == 0 then True else odd(n-1, odd, even) let odd(n) = odd'(n, odd', even') let even(n) = even'(n, odd', even') Look ma, no hands! Well, actually, it is explicit closure-conversion done by hand so... anyhow, there are more straightforward and performant ways to get recursion in practice.
- marvinborner 2y ago
  In lambda calculus, you could use a variadic fixed point combinator to solve such recurrence relations elegantly
  - Joker_vD 2y ago
    But you don't need to solve these, they're solved already: these four definitions are non-recursive. Yet when evaluated, they will exhibit properly recursive behaviour. The only reason to use Y combinator in practice is when you for some reason don't want to keep manually passing the function to itself like "func fact(self, n) { return (n < 1) ? 1 : n * self(self, n-1) }; print(fact(fact, 5))" — maybe because it's tedious and error-prone, — and don't have a sufficiently ergonomic term-rewrite system at hand that would do this for you.
    - marvinborner 2y ago
      Yes, I realize that. However, the alternative using a variadic fixed point combinator looks slightly cleaner and would (optimally) reduce to the same term. For example, using a list-based vfix: even' _ odd n = if n == 0 then True else (odd (n - 1))) odd' even _ n = if n == 0 then False else (even (n - 1)) even = head $ vfix [even', odd'] odd = tail $ vfix [even', odd'] Here, the functions don't need to be passed explicitly to the "recursive" calls. I prefer this a lot, it makes my lambda functions much more readable.

by Rygian 2y ago

The key realization for me was that in lambda calculus, "A function can’t call itself by name, so we will have to find an alternative way." The rest is smart acrobatics.

bmacho 2y ago

A 'function' can't call itself (by name or by any other method), but since 'functions' can call each other, and can make each other to call each other, recursion is mostly trivial. You try it, then you'll get a working recursion one way or another. (Lambda calculus don't operate on functions, but on expressions/lambda terms.)

Joker_vD 2y ago

let odd'(n, odd, even) = if n == 0 then False else even(n-1, odd, even) let even'(n, odd, even) = if n == 0 then True else odd(n-1, odd, even) let odd(n) = odd'(n, odd', even') let even(n) = even'(n, odd', even') Look ma, no hands! Well, actually, it is explicit closure-conversion done by hand so... anyhow, there are more straightforward and performant ways to get recursion in practice.

marvinborner 2y ago
In lambda calculus, you could use a variadic fixed point combinator to solve such recurrence relations elegantly
- Joker_vD 2y ago
  But you don't need to solve these, they're solved already: these four definitions are non-recursive. Yet when evaluated, they will exhibit properly recursive behaviour. The only reason to use Y combinator in practice is when you for some reason don't want to keep manually passing the function to itself like "func fact(self, n) { return (n < 1) ? 1 : n * self(self, n-1) }; print(fact(fact, 5))" — maybe because it's tedious and error-prone, — and don't have a sufficiently ergonomic term-rewrite system at hand that would do this for you.
  - marvinborner 2y ago
    Yes, I realize that. However, the alternative using a variadic fixed point combinator looks slightly cleaner and would (optimally) reduce to the same term. For example, using a list-based vfix: even' _ odd n = if n == 0 then True else (odd (n - 1))) odd' even _ n = if n == 0 then False else (even (n - 1)) even = head $ vfix [even', odd'] odd = tail $ vfix [even', odd'] Here, the functions don't need to be passed explicitly to the "recursive" calls. I prefer this a lot, it makes my lambda functions much more readable.