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 type Number *Number
  13
  14 // -------------------------------------
  15 // Peano primitives
  16
  17 func zero() *Number {
  18         return nil
  19 }
  20
  21 func is_zero(x *Number) bool {
  22         return x == nil
  23 }
  24
  25 func add1(x *Number) *Number {
  26         e := new(Number)
  27         *e = x
  28         return e
  29 }
  30
  31 func sub1(x *Number) *Number {
  32         return *x
  33 }
  34
  35 func add(x, y *Number) *Number {
  36         if is_zero(y) {
  37                 return x
  38         }
  39
  40         return add(add1(x), sub1(y))
  41 }
  42
  43 func mul(x, y *Number) *Number {
  44         if is_zero(x) || is_zero(y) {
  45                 return zero()
  46         }
  47
  48         return add(mul(x, sub1(y)), x)
  49 }
  50
  51 func fact(n *Number) *Number {
  52         if is_zero(n) {
  53                 return add1(zero())
  54         }
  55
  56         return mul(fact(sub1(n)), n)
  57 }
  58
  59 // -------------------------------------
  60 // Helpers to generate/count Peano integers
  61
  62 func gen(n int) *Number {
  63         if n > 0 {
  64                 return add1(gen(n - 1))
  65         }
  66
  67         return zero()
  68 }
  69
  70 func count(x *Number) int {
  71         if is_zero(x) {
  72                 return 0
  73         }
  74
  75         return count(sub1(x)) + 1
  76 }
  77
  78 func check(x *Number, expected int) {
  79         var c = count(x)
  80         if c != expected {
  81                 print("error: found ", c, "; expected ", expected, "\n")
  82                 panic("fail")
  83         }
  84 }
  85
  86 // -------------------------------------
  87 // Test basic functionality
  88
  89 func init() {
  90         check(zero(), 0)
  91         check(add1(zero()), 1)
  92         check(gen(10), 10)
  93
  94         check(add(gen(3), zero()), 3)
  95         check(add(zero(), gen(4)), 4)
  96         check(add(gen(3), gen(4)), 7)
  97
  98         check(mul(zero(), zero()), 0)
  99         check(mul(gen(3), zero()), 0)
 100         check(mul(zero(), gen(4)), 0)
 101         check(mul(gen(3), add1(zero())), 3)
 102         check(mul(add1(zero()), gen(4)), 4)
 103         check(mul(gen(3), gen(4)), 12)
 104
 105         check(fact(zero()), 1)
 106         check(fact(add1(zero())), 1)
 107         check(fact(gen(5)), 120)
 108 }
 109
 110 // -------------------------------------
 111 // Factorial
 112
 113 var results = [...]int{
 114         1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
 115         39916800, 479001600,
 116 }
 117
 118 func main() {
 119         for i := 0; i <= 9; i++ {
 120                 if f := count(fact(gen(i))); f != results[i] {
 121                         println("FAIL:", i, "!:", f, "!=", results[i])
 122                         panic(0)
 123                 }
 124         }
 125 }