Python and Viv · Recursion
Fibonacci with a memo
What to notice
- The memo is a dict in Python and a
map()in Viv;n in memois the same in both. A function stores into the global map without any declaration, because a map is a handle. - Viv has no
globalstatement, and a function cannot assign a global number: an assignment makes the name local for the whole body, and reading it first is refused with a note. The Viv side counts calls in a one-element array,calls = [0], and a function writes into it withcalls[0] += 1. fib(78)is 8944394323791464, below 2^53, so the double holds it exactly. Pastfib(78)the Viv values would be rounded; Python's ints would not.print(... fib_counted(SMALL), "after", calls ...)in Python evaluates the call before readingcalls. The Viv side stores the result first, which makes the order plain.
Python fib_memo.py · 39 lines
Viv fib_memo.viv · 49 lines
py2viv refuses fib_memo.py
1 plain recursion
4def fib(n):
5 if n < 2:
6 return n
7 return fib(n - 1) + fib(n - 2)
2def fib(n) {
3 if n < 2 {
4 return n
5 }
6 return fib(n - 1) + fib(n - 2)
7}
py2viv refuses this program:
fib_memo.py:26:5: not numeric Python: `global calls` rebinding a module-level name
calls += 1
^^^^^^^^^^
Keep the value in a one-element array and write `calls[0] = ...`, as the ports do.
1 construct outside the numeric subset (tools/py2viv/SUBSET.md) 2 remembered in a dict
10memo = {}
11
12def fib_memo(n):
13 if n < 2:
14 return n
15 if n in memo:
16 return memo[n]
17 v = fib_memo(n - 1) + fib_memo(n - 2)
18 memo[n] = v
19 return v
10memo = map()
11
12def fib_memo(n) {
13 if n < 2 {
14 return n
15 }
16 if n in memo {
17 return memo[n]
18 }
19 v = fib_memo(n - 1) + fib_memo(n - 2)
20 memo[n] = v
21 return v
22}
(refused)
3 count the calls
22calls = 0
23
24def fib_counted(n):
25 global calls
26 calls += 1
27 if n < 2:
28 return n
29 return fib_counted(n - 1) + fib_counted(n - 2)
30
31SMALL = 20
32print("fib(20) =", fib_counted(SMALL), "after", calls, "calls")
25calls = [0]
26
27def fib_counted(n) {
28 calls[0] += 1
29 if n < 2 {
30 return n
31 }
32 return fib_counted(n - 1) + fib_counted(n - 2)
33}
34
35SMALL = 20
36f20 = fib_counted(SMALL)
37print("fib(20) =", f20, "after", calls[0], "calls")
(refused)
4 large n with the memo
35BIG = 78
36print(f"fib(78) = {fib_memo(BIG):d}, memo holds {len(memo)} values")
40BIG = 78
41print(f"fib(78) = {fib_memo(BIG):d}, memo holds {len(memo):d} values")
(refused)
5 checks
39assert fib(SMALL) == fib_memo(SMALL)
44test "memo agrees" {
45 assert_true(fib(SMALL) == fib_memo(SMALL))
46}
(refused)
What they print
identical — the two programs print the same text.
Dimmed lines are left out of the comparison. Each Viv test block prints one PASS line; the Python checks the same facts with assert, which prints nothing.
$ python3 fib_memo.py
fib(20) = 6765 after 21891 callsfib(78) = 8944394323791464, memo holds 77 values
$ viv run fib_memo.viv
fib(20) = 6765 after 21891 callsfib(78) = 8944394323791464, memo holds 77 valuesPASS memo agrees