blob: 89e71c8602b7dc6bf42069ebd5e1f7c21f96df14 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
# 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`{.bruijn} from
[`std/Combinator`](/std/Combinator.bruijn.html).
Fixed-point combinators have the fascinating property of inducing
recursive behaviour in programming languages without support for
recursion.
Say we want a function `g`{.bruijn} to be able to call itself. With the
`y`{.bruijn} 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`{.bruijn} is able to call itself since its
outer argument is the initial function again.
Example for using `y`{.bruijn} to find the factorial of 2:
``` bruijn
# 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:
``` bruijn
# 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](data-structures.md#lists-stdlist) for more
information. Also read [coding style](style.md) for other style
suggestions.
## Mutual recurrence relations
For solving mutual recurrence relations, you can use the *variadic
fixed-point combinator* `y*`{.bruijn} from
[`std/List`](/std/List.bruijn.html). This combinator produces all the
fixed points of a function as an iterable [list](data-structures.md).
Example `even?`{.bruijn}/`odd?`{.bruijn} implementation using
`y*`{.bruijn}:
``` bruijn
# 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](https://text.marvinborner.de/2023-06-18-15.html).
|
