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