gcc/testsuite/go.test/test/garbage/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 import (
  10         "fmt"
  11         "runtime"
  12         "time"
  13 )
  14
  15
  16 type Number struct {
  17         next *Number
  18 }
  19
  20
  21 // -------------------------------------
  22 // Peano primitives
  23
  24 func zero() *Number { return nil }
  25
  26
  27 func is_zero(x *Number) bool { return x == nil }
  28
  29
  30 func add1(x *Number) *Number {
  31         e := new(Number)
  32         e.next = x
  33         return e
  34 }
  35
  36
  37 func sub1(x *Number) *Number { return x.next }
  38
  39
  40 func add(x, y *Number) *Number {
  41         if is_zero(y) {
  42                 return x
  43         }
  44
  45         return add(add1(x), sub1(y))
  46 }
  47
  48
  49 func mul(x, y *Number) *Number {
  50         if is_zero(x) || is_zero(y) {
  51                 return zero()
  52         }
  53
  54         return add(mul(x, sub1(y)), x)
  55 }
  56
  57
  58 func fact(n *Number) *Number {
  59         if is_zero(n) {
  60                 return add1(zero())
  61         }
  62
  63         return mul(fact(sub1(n)), n)
  64 }
  65
  66
  67 // -------------------------------------
  68 // Helpers to generate/count Peano integers
  69
  70 func gen(n int) *Number {
  71         if n > 0 {
  72                 return add1(gen(n - 1))
  73         }
  74
  75         return zero()
  76 }
  77
  78
  79 func count(x *Number) int {
  80         if is_zero(x) {
  81                 return 0
  82         }
  83
  84         return count(sub1(x)) + 1
  85 }
  86
  87
  88 func check(x *Number, expected int) {
  89         var c = count(x)
  90         if c != expected {
  91                 panic(fmt.Sprintf("error: found %d; expected %d", c, expected))
  92         }
  93 }
  94
  95
  96 // -------------------------------------
  97 // Test basic functionality
  98
  99 func verify() {
 100         check(zero(), 0)
 101         check(add1(zero()), 1)
 102         check(gen(10), 10)
 103
 104         check(add(gen(3), zero()), 3)
 105         check(add(zero(), gen(4)), 4)
 106         check(add(gen(3), gen(4)), 7)
 107
 108         check(mul(zero(), zero()), 0)
 109         check(mul(gen(3), zero()), 0)
 110         check(mul(zero(), gen(4)), 0)
 111         check(mul(gen(3), add1(zero())), 3)
 112         check(mul(add1(zero()), gen(4)), 4)
 113         check(mul(gen(3), gen(4)), 12)
 114
 115         check(fact(zero()), 1)
 116         check(fact(add1(zero())), 1)
 117         check(fact(gen(5)), 120)
 118 }
 119
 120
 121 // -------------------------------------
 122 // Factorial
 123
 124
 125 func main() {
 126         st := &runtime.MemStats
 127         t0 := time.Nanoseconds()
 128         verify()
 129         for i := 0; i <= 9; i++ {
 130                 print(i, "! = ", count(fact(gen(i))), "\n")
 131         }
 132         runtime.GC()
 133         t1 := time.Nanoseconds()
 134
 135         fmt.Printf("garbage.BenchmarkPeano 1 %d ns/op\n", t1-t0)
 136         fmt.Printf("garbage.BenchmarkPeanoPause %d %d ns/op\n", st.NumGC, int64(st.PauseNs)/int64(st.NumGC))
 137 }