blob: f4c59d1e1a2c64b36fe9674704c085846fa01ce7 [file] [log] [blame]
 // \$G \$F.go && \$L \$F.\$A && ./\$A.out // Copyright 2009 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package main type Number *Number // ------------------------------------- // Peano primitives func zero() *Number { return nil } func is_zero(x *Number) bool { return x == nil } func add1(x *Number) *Number { e := new(Number) *e = x return e } func sub1(x *Number) *Number { return *x } func add(x, y *Number) *Number { if is_zero(y) { return x } return add(add1(x), sub1(y)) } func mul(x, y *Number) *Number { if is_zero(x) || is_zero(y) { return zero() } return add(mul(x, sub1(y)), x) } func fact(n *Number) *Number { if is_zero(n) { return add1(zero()) } return mul(fact(sub1(n)), n) } // ------------------------------------- // Helpers to generate/count Peano integers func gen(n int) *Number { if n > 0 { return add1(gen(n - 1)) } return zero() } func count(x *Number) int { if is_zero(x) { return 0 } return count(sub1(x)) + 1 } func check(x *Number, expected int) { var c = count(x) if c != expected { print("error: found ", c, "; expected ", expected, "\n") panic("fail") } } // ------------------------------------- // Test basic functionality func init() { check(zero(), 0) check(add1(zero()), 1) check(gen(10), 10) check(add(gen(3), zero()), 3) check(add(zero(), gen(4)), 4) check(add(gen(3), gen(4)), 7) check(mul(zero(), zero()), 0) check(mul(gen(3), zero()), 0) check(mul(zero(), gen(4)), 0) check(mul(gen(3), add1(zero())), 3) check(mul(add1(zero()), gen(4)), 4) check(mul(gen(3), gen(4)), 12) check(fact(zero()), 1) check(fact(add1(zero())), 1) check(fact(gen(5)), 120) } // ------------------------------------- // Factorial func main() { for i := 0; i <= 9; i++ { print(i, "! = ", count(fact(gen(i))), "\n") } }