gcc/testsuite/go.test/test/peano.go

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