Python and Viv · Recursion
Merge sort
What to notice
- The algorithm is line for line the same.
out.append(x)isout = append(out, x)andout.extend(a[i:])isout = extend(out, a[i:]). i = j = 0has no Viv form; the Viv side writes two assignments.- Slices
xs[:mid]andxs[mid:]are copies in both (Python lists copy on slicing; Viv arrays always do), so the sort never changesdata. - The test compares arrays with
all(a == b), since==between two arrays is elementwise in Viv;sorted(data)becomescopythensort.
Python merge_sort.py · 32 lines
Viv merge_sort.viv · 44 lines
py2viv refuses merge_sort.py
1 merge two sorted lists
4def merge(a, b):
5 out = []
6 i = j = 0
7 while i < len(a) and j < len(b):
8 if a[i] <= b[j]:
9 out.append(a[i])
10 i += 1
11 else:
12 out.append(b[j])
13 j += 1
14 out.extend(a[i:])
15 out.extend(b[j:])
16 return out
2def merge(a, b) {
3 out = []
4 i = 0
5 j = 0
6 while i < len(a) and j < len(b) {
7 if a[i] <= b[j] {
8 out = append(out, a[i])
9 i += 1
10 }
11 else {
12 out = append(out, b[j])
13 j += 1
14 }
15 }
16 out = extend(out, a[i:])
17 out = extend(out, b[j:])
18 return out
19}
py2viv refuses this program:
merge_sort.py:32:19: not numeric Python: an empty list (lifted by R17)
assert merge_sort([]) == []
^^
py2viv grows a list only as `lst = []` then `lst.append(x)`; otherwise allocate the final size with np.zeros(n) and fill it.
1 construct outside the numeric subset (tools/py2viv/SUBSET.md) 2 split, sort each half, merge
19def merge_sort(xs):
20 if len(xs) <= 1:
21 return xs
22 mid = len(xs) // 2
23 return merge(merge_sort(xs[:mid]), merge_sort(xs[mid:]))
22def merge_sort(xs) {
23 if len(xs) <= 1 {
24 return xs
25 }
26 mid = len(xs) // 2
27 return merge(merge_sort(xs[:mid]), merge_sort(xs[mid:]))
28}
(refused)
3 run it
26data = [38, 27, 43, 3, 9, 82, 10, 3, 55, -4]
27print(merge_sort(data))
28print(data)
31data = [38, 27, 43, 3, 9, 82, 10, 3, 55, -4]
32print(merge_sort(data))
33print(data)
(refused)
4 checks
31assert merge_sort(data) == sorted(data)
32assert merge_sort([]) == []
36test "merge sort" {
37 expect = copy(data)
38 sort(expect)
39 assert_true(all(merge_sort(data) == expect))
40 assert_true(len(merge_sort([])) == 0)
41}
(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 merge_sort.py
[-4, 3, 3, 9, 10, 27, 38, 43, 55, 82][38, 27, 43, 3, 9, 82, 10, 3, 55, -4]
$ viv run merge_sort.viv
[-4, 3, 3, 9, 10, 27, 38, 43, 55, 82][38, 27, 43, 3, 9, 82, 10, 3, 55, -4]PASS merge sort