Python and Viv · Recursion
Quicksort in place
What to notice
- A list passed to a Python function and an array passed to a Viv function are both shared:
partitionswaps elements of the caller's array in either language. a[i], a[j] = a[j], a[i]swaps two elements in both.- A Viv function with no
returngives back 0, which the caller ignores;quicksortneeds no return statement. for j in range(lo, hi)isfor j from lo to hi.- The generator in
all(... for k in ...)becomes a loop of assertions inside the test.
Python quicksort.py · 27 lines
Viv quicksort.viv · 37 lines
py2viv translated from quicksort.py
What py2viv adds before the program
(nothing)
(nothing)
15 lines: a header and the guard functions its translation calls
1###
2Translated from quicksort.py by py2viv 0.2.0 (numeric Python -> Viv).
3Python source sha256: 2f1726d1a8d02da31e2c639938759d9c92135eb6f483da40ee7eb977a1eacef4
4Each print(...) is one print(...) line; fmt(x) writes a float as Python's repr does.
5A `raise`, a failed assert and every guard `stop` with Python's exception line.
6###
7
8#| An int result, as Python's int: a -0.0 becomes 0 (an int has no sign on zero), and the run
9#| stops at 2^53, past which a double no longer holds every integer (Python's int does).
10def py_int(x) {
11 if abs(x) >= 9007199254740992 {
12 stop("py2viv: an integer reached 2^53; Python's int is exact there and a double is not")
13 }
14 return x + 0.0
15}
1 partition around the last element
4def partition(a, lo, hi):
5 pivot = a[hi]
6 i = lo
7 for j in range(lo, hi):
8 if a[j] < pivot:
9 a[i], a[j] = a[j], a[i]
10 i += 1
11 a[i], a[hi] = a[hi], a[i]
12 return i
2def partition(a, lo, hi) {
3 pivot = a[hi]
4 i = lo
5 for j from lo to hi {
6 if a[j] < pivot {
7 a[i], a[j] = a[j], a[i]
8 i += 1
9 }
10 }
11 a[i], a[hi] = a[hi], a[i]
12 return i
13}
20def partition(a: Arr, lo, hi) {
21 pivot = a[hi]
22 i = lo
23 for j from lo to hi {
24 if a[j] < pivot {
25 a[i], a[j] = a[j], a[i]
26 i = py_int(i + 1)
27 }
28 }
29 a[i], a[hi] = a[hi], a[i]
30 return i
31}
2 sort the two sides
15def quicksort(a, lo, hi):
16 if lo < hi:
17 p = partition(a, lo, hi)
18 quicksort(a, lo, p - 1)
19 quicksort(a, p + 1, hi)
16def quicksort(a, lo, hi) {
17 if lo < hi {
18 p = partition(a, lo, hi)
19 quicksort(a, lo, p - 1)
20 quicksort(a, p + 1, hi)
21 }
22}
33def quicksort(a: Arr, lo, hi) {
34 if lo < hi {
35 p = partition(a, lo, hi)
36 quicksort(a, lo, py_int(p - 1))
37 quicksort(a, py_int(p + 1), hi)
38 }
39}
3 sort a list in place
22data = [3.5, -1.0, 7.25, 0.0, 2.0, 7.25, -8.5, 4.0]
23quicksort(data, 0, len(data) - 1)
24print(data)
25data = [3.5, -1.0, 7.25, 0.0, 2.0, 7.25, -8.5, 4.0]
26quicksort(data, 0, len(data) - 1)
27print(fmt(data))
41data = [3.5, -1.0, 7.25, 0.0, 2.0, 7.25, -8.5, 4.0]
42quicksort(data, 0, len(data) - 1)
43print(fmt(data))
4 checks
27assert all(data[k] <= data[k + 1] for k in range(len(data) - 1))
30test "ascending" {
31 for k to len(data) - 1 {
32 assert_true(data[k] <= data[k + 1])
33 }
34}
45py_all1 = true
46for py_k2 to len(data) - 1 {
47 if not (data[py_k2] <= data[py_int(py_k2 + 1)]) {
48 py_all1 = false
49 break
50 }
51}
52if not py_all1 {
53 stop("AssertionError")
54}
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 quicksort.py
[-8.5, -1.0, 0.0, 2.0, 3.5, 4.0, 7.25, 7.25]
$ viv run quicksort.viv
[-8.5, -1.0, 0.0, 2.0, 3.5, 4.0, 7.25, 7.25]PASS ascending
$ viv run quicksort.py (py2viv’s translation)
The translation prints exactly what the Python prints.
[-8.5, -1.0, 0.0, 2.0, 3.5, 4.0, 7.25, 7.25]