Python and Viv · Recursion
Tower of Hanoi
What to notice
- Both sides return the list of moves instead of appending to a global list. In Viv that is the only way: a function cannot grow a global array, because
moves = append(moves, x)inside adefmakesmovesa local. return []gives an empty list; Viv learns that it holds strings from theappendof an f-string, andmoves + hanoi(...)joins two lists of strings as Python's+does.f"disk {n}"needs:din Viv to print1rather than1.0.2 ** MAX_DISKS - 1is2 ^ MAX_DISKS - 1; power binds tighter than minus in both.
Python hanoi.py · 24 lines
Viv hanoi.viv · 31 lines
py2viv refuses hanoi.py
1 move n disks from one peg to another
4def hanoi(n, source, target, spare):
5 if n == 0:
6 return []
7 moves = hanoi(n - 1, source, spare, target)
8 moves.append(f"disk {n}: {source} -> {target}")
9 return moves + hanoi(n - 1, spare, target, source)
2def hanoi(n, source, target, spare) {
3 if n == 0 {
4 return []
5 }
6 moves = hanoi(n - 1, source, spare, target)
7 moves = append(moves, f"disk {n:d}: {source} -> {target}")
8 return moves + hanoi(n - 1, spare, target, source)
9}
py2viv refuses this program:
hanoi.py:6:16: not numeric Python: an empty list (lifted by R17)
return []
^^
py2viv grows a list only as `lst = []` then `lst.append(x)`; otherwise allocate the final size with np.zeros(n) and fill it.
hanoi.py:8:5: not numeric Python: list.append (lifted by R17)
moves.append(f"disk {n}: {source} -> {target}")
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
py2viv changes a list (append, pop, insert, extend, remove, clear, reverse, sort) only when nothing else can hold it: bound only to new lists (`[]`, a list literal, a comprehension, list(...), sorted(...)) and read nowhere an alias could be taken (a second name, an argument, a container, a nested def); otherwise allocate the final size with np.zeros(n) and write by index.
hanoi.py:13:10: not numeric Python: iterating over a value of unknown type
for m in hanoi(DISKS, "A", "C", "B"):
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Loop over `range(len(a))` and index.
3 constructs outside the numeric subset (tools/py2viv/SUBSET.md) 2 three disks, every move
12DISKS = 3
13for m in hanoi(DISKS, "A", "C", "B"):
14 print(m)
12DISKS = 3
13for m in hanoi(DISKS, "A", "C", "B") {
14 print(m)
15}
(refused)
3 the count doubles with each disk
17MAX_DISKS = 10
18EVERY = 3
19for n in range(1, MAX_DISKS + 1, EVERY):
20 count = len(hanoi(n, "A", "C", "B"))
21 print(f"{n:2d} disks: {count:4d} moves")
18MAX_DISKS = 10
19EVERY = 3
20for n from 1 to MAX_DISKS + 1 by EVERY {
21 count = len(hanoi(n, "A", "C", "B"))
22 print(f"{n:2d} disks: {count:4d} moves")
23}
(refused)
4 checks
24assert len(hanoi(MAX_DISKS, "A", "C", "B")) == 2 ** MAX_DISKS - 1
26test "2^n - 1 moves" {
27 assert_true(len(hanoi(MAX_DISKS, "A", "C", "B")) == 2 ^ MAX_DISKS - 1)
28}
(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 hanoi.py
disk 1: A -> Cdisk 2: A -> Bdisk 1: C -> Bdisk 3: A -> Cdisk 1: B -> Adisk 2: B -> Cdisk 1: A -> C1 disks: 1 moves4 disks: 15 moves7 disks: 127 moves10 disks: 1023 moves
$ viv run hanoi.viv
disk 1: A -> Cdisk 2: A -> Bdisk 1: C -> Bdisk 3: A -> Cdisk 1: B -> Adisk 2: B -> Cdisk 1: A -> C1 disks: 1 moves4 disks: 15 moves7 disks: 127 moves10 disks: 1023 movesPASS 2^n - 1 moves