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