government / eval / tail_test.go

@ 69e3ad85cc0f4df2aca759df28acafb505578821 | history


package eval

import (
	"runtime/debug"
	"testing"
)

// The first case loops a million times, the rest 100,000. Without proper
// tail calls every iteration would add several Go frames; at either depth
// that is far past the 16 MB stack limit set here (non-tail recursion
// overflows it at 100,000), and the test binary would die with a stack
// overflow.
func TestTailCalls(t *testing.T) {
	defer debug.SetMaxStack(debug.SetMaxStack(16 << 20))

	runEvalCases(t, []evalCase{
		{"(define count (lambda (n) (if (== n 0) 'done (count (- n 1))))) (count 1000000)", "done"},

		// Tail position in the true branch, and in a nested if.
		{"(define count (lambda (n) (if (!= n 0) (count (- n 1)) 'done))) (count 100000)", "done"},
		{"(define count (lambda (n) (if (== n 0) 'done (if (< n 0) 'neg (count (- n 1)))))) (count 100000)", "done"},

		// The last operand of and/or.
		{"(define count (lambda (n) (or (== n 0) (count (- n 1))))) (count 100000)", "T"},
		{"(define count (lambda (n) (and (> n -1) (if (== n 0) 'done (count (- n 1)))))) (count 100000)", "done"},

		// The last form of a body, after defines and other expressions.
		{"(define count (lambda (n) (define m (- n 1)) n (if (== n 0) 'done (count m)))) (count 100000)", "done"},

		// An accumulator turns a computation into a loop.
		{`(define sum (lambda (n acc) (if (== n 0) acc (sum (- n 1) (+ acc n)))))
		  (sum 100000 0)`, "5000050000"},
		{`(define fact-iter (lambda (n acc) (if (== n 0) acc (fact-iter (- n 1) (* n acc)))))
		  (fact-iter 20 1)`, "2432902008176640000"},

		// A tail call to a different function, passed in as an argument.
		{`(define bounce (lambda (f n) (if (== n 0) 'done (f f (- n 1)))))
		  (bounce bounce 100000)`, "done"},

		// Building a long list with an accumulator, then measuring it.
		{`(define build (lambda (n acc) (if (== n 0) acc (build (- n 1) (cons n acc)))))
		  (define len (lambda (l acc) (if (== l ()) acc (len (cdr l) (+ acc 1)))))
		  (len (build 100000 ()) 0)`, "100000"},
	})
}

// Recursion that is not in tail position still nests, but moderate depths
// work. The pending (+ 1 ...) at each level is real work the program needs
// the stack for.
func TestNonTailRecursion(t *testing.T) {
	runEvalCases(t, []evalCase{
		{`(define len (lambda (l) (if (== l ()) 0 (+ 1 (len (cdr l))))))
		  (define build (lambda (n acc) (if (== n 0) acc (build (- n 1) (cons n acc)))))
		  (len (build 10000 ()))`, "10000"},
	})
}