1// run
2
3// Copyright 2009 The Go Authors. All rights reserved.
4// Use of this source code is governed by a BSD-style
5// license that can be found in the LICENSE file.
6
7// Test that heavy recursion works. Simple torture test for
8// segmented stacks: do math in unary by recursion.
9
10package main
11
12import "runtime"
13
14type Number *Number
15
16// -------------------------------------
17// Peano primitives
18
19func zero() *Number {
20	return nil
21}
22
23func is_zero(x *Number) bool {
24	return x == nil
25}
26
27func add1(x *Number) *Number {
28	e := new(Number)
29	*e = x
30	return e
31}
32
33func sub1(x *Number) *Number {
34	return *x
35}
36
37func add(x, y *Number) *Number {
38	if is_zero(y) {
39		return x
40	}
41
42	return add(add1(x), sub1(y))
43}
44
45func mul(x, y *Number) *Number {
46	if is_zero(x) || is_zero(y) {
47		return zero()
48	}
49
50	return add(mul(x, sub1(y)), x)
51}
52
53func fact(n *Number) *Number {
54	if is_zero(n) {
55		return add1(zero())
56	}
57
58	return mul(fact(sub1(n)), n)
59}
60
61// -------------------------------------
62// Helpers to generate/count Peano integers
63
64func gen(n int) *Number {
65	if n > 0 {
66		return add1(gen(n - 1))
67	}
68
69	return zero()
70}
71
72func count(x *Number) int {
73	if is_zero(x) {
74		return 0
75	}
76
77	return count(sub1(x)) + 1
78}
79
80func check(x *Number, expected int) {
81	var c = count(x)
82	if c != expected {
83		print("error: found ", c, "; expected ", expected, "\n")
84		panic("fail")
85	}
86}
87
88// -------------------------------------
89// Test basic functionality
90
91func init() {
92	check(zero(), 0)
93	check(add1(zero()), 1)
94	check(gen(10), 10)
95
96	check(add(gen(3), zero()), 3)
97	check(add(zero(), gen(4)), 4)
98	check(add(gen(3), gen(4)), 7)
99
100	check(mul(zero(), zero()), 0)
101	check(mul(gen(3), zero()), 0)
102	check(mul(zero(), gen(4)), 0)
103	check(mul(gen(3), add1(zero())), 3)
104	check(mul(add1(zero()), gen(4)), 4)
105	check(mul(gen(3), gen(4)), 12)
106
107	check(fact(zero()), 1)
108	check(fact(add1(zero())), 1)
109	check(fact(gen(5)), 120)
110}
111
112// -------------------------------------
113// Factorial
114
115var results = [...]int{
116	1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
117	39916800, 479001600,
118}
119
120func main() {
121	max := 9
122	if runtime.GOARCH == "wasm" {
123		max = 7 // stack size is limited
124	}
125	for i := 0; i <= max; i++ {
126		if f := count(fact(gen(i))); f != results[i] {
127			println("FAIL:", i, "!:", f, "!=", results[i])
128			panic(0)
129		}
130	}
131}
132