Source file test/peano.go

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

View as plain text