summaryrefslogtreecommitdiffstats
path: root/test/bench/garbage/peano.go
diff options
context:
space:
mode:
Diffstat (limited to 'test/bench/garbage/peano.go')
-rw-r--r--test/bench/garbage/peano.go121
1 files changed, 121 insertions, 0 deletions
diff --git a/test/bench/garbage/peano.go b/test/bench/garbage/peano.go
new file mode 100644
index 0000000..6c7e523
--- /dev/null
+++ b/test/bench/garbage/peano.go
@@ -0,0 +1,121 @@
+// run
+
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+ "fmt"
+ "runtime"
+ "time"
+)
+
+type Number struct {
+ next *Number
+}
+
+// -------------------------------------
+// Peano primitives
+
+func zero() *Number { return nil }
+
+func is_zero(x *Number) bool { return x == nil }
+
+func add1(x *Number) *Number {
+ e := new(Number)
+ e.next = x
+ return e
+}
+
+func sub1(x *Number) *Number { return x.next }
+
+func add(x, y *Number) *Number {
+ if is_zero(y) {
+ return x
+ }
+
+ return add(add1(x), sub1(y))
+}
+
+func mul(x, y *Number) *Number {
+ if is_zero(x) || is_zero(y) {
+ return zero()
+ }
+
+ return add(mul(x, sub1(y)), x)
+}
+
+func fact(n *Number) *Number {
+ if is_zero(n) {
+ return add1(zero())
+ }
+
+ return mul(fact(sub1(n)), n)
+}
+
+// -------------------------------------
+// Helpers to generate/count Peano integers
+
+func gen(n int) *Number {
+ if n > 0 {
+ return add1(gen(n - 1))
+ }
+
+ return zero()
+}
+
+func count(x *Number) int {
+ if is_zero(x) {
+ return 0
+ }
+
+ return count(sub1(x)) + 1
+}
+
+func check(x *Number, expected int) {
+ var c = count(x)
+ if c != expected {
+ panic(fmt.Sprintf("error: found %d; expected %d", c, expected))
+ }
+}
+
+// -------------------------------------
+// Test basic functionality
+
+func verify() {
+ check(zero(), 0)
+ check(add1(zero()), 1)
+ check(gen(10), 10)
+
+ check(add(gen(3), zero()), 3)
+ check(add(zero(), gen(4)), 4)
+ check(add(gen(3), gen(4)), 7)
+
+ check(mul(zero(), zero()), 0)
+ check(mul(gen(3), zero()), 0)
+ check(mul(zero(), gen(4)), 0)
+ check(mul(gen(3), add1(zero())), 3)
+ check(mul(add1(zero()), gen(4)), 4)
+ check(mul(gen(3), gen(4)), 12)
+
+ check(fact(zero()), 1)
+ check(fact(add1(zero())), 1)
+ check(fact(gen(5)), 120)
+}
+
+// -------------------------------------
+// Factorial
+
+func main() {
+ t0 := time.Now()
+ verify()
+ for i := 0; i <= 9; i++ {
+ print(i, "! = ", count(fact(gen(i))), "\n")
+ }
+ runtime.GC()
+ t1 := time.Now()
+
+ gcstats("BenchmarkPeano", 1, t1.Sub(t0))
+}