@ cdf2d0cb24bc5f0af81926cf5d0b2a709fd84abc | 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"},
})
}