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