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