test/peano.go

   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
  10 package main
  11
  12 import "runtime"
  13
  14 type Number *Number
  15
  16 // -------------------------------------
  17 // Peano primitives
  18
  19 func zero() *Number {
  20         return nil
  21 }
  22
  23 func is_zero(x *Number) bool {
  24         return x == nil
  25 }
  26
  27 func add1(x *Number) *Number {
  28         e := new(Number)
  29         *e = x
  30         return e
  31 }
  32
  33 func sub1(x *Number) *Number {
  34         return *x
  35 }
  36
  37 func add(x, y *Number) *Number {
  38         if is_zero(y) {
  39                 return x
  40         }
  41
  42         return add(add1(x), sub1(y))
  43 }
  44
  45 func 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
  53 func 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
  64 func gen(n int) *Number {
  65         if n > 0 {
  66                 return add1(gen(n - 1))
  67         }
  68
  69         return zero()
  70 }
  71
  72 func count(x *Number) int {
  73         if is_zero(x) {
  74                 return 0
  75         }
  76
  77         return count(sub1(x)) + 1
  78 }
  79
  80 func 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
  91 func 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
 115 var results = [...]int{
 116         1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
 117         39916800, 479001600,
 118 }
 119
 120 func 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 }