Monday, April 19, 2021

η-conversion and tail recursion

Consider this lambda expression: (lambda (x) (sqrt x)). This function simply calls sqrt on its argument and returns whatever sqrt returns. There is no argument you could provide to this function that would cause it to return a different result than you would get from calling sqrt directly. We say that this function and the sqrt function are extensionally equal. We can replace this lambda expression with a literal reference to the sqrt function without changing the value produced by our code.

You can go the other way, too. If you find a literal reference to a function, you can replace it with a lambda expression that calls the function. This is η-conversion. η-reduction is removing an unnecessary lambda wrapper, η-expansion is introducting one.

η-conversion comes with caveats. First, it only works on functions. If I have a string "foo", and I attempt to η-expand this into (lambda (x) ("foo" x)), I get nonsense. Second, a reduction strategy that incorporates η-reduction can be weaker than one that does not. Consider this expression: (lambda (x) ((compute-f) x)). We can η-reduce this to (compute-f), but this makes a subtle difference. When wrapped with the lambda, (compute-f) is evaluated just before it is applied to x. In fact, we won't call (compute-f) unless we invoke the result of the lambda expression somewhere. However, once η-reduced, (compute-f) is evaluated at the point the original lambda was evaluated, which can be quite a bit earlier.

When a function foo calls another function bar as a subproblem, an implicit continuation is passed to bar. bar invokes this continuation on the return value that it computes. We can characterize this continuation like this:

kbar = (lambda (return-value)
         (kfoo (finish-foo return-value)))
this just says that when bar returns, we'll finish running the code in foo and further continue by invoking the continuation supplied to foo.

If foo makes a tail call to bar, then foo is just returning what bar computes. There is no computation for foo to finish, so the continuation is just

kbar = (lambda (return-value)
         (kfoo return-value))
But this η-reduces to just kfoo, so we don't have to allocate a new trivial continuation when foo tail calls bar, we can just pass along the continuation that was passed to foo.

Tail recursion is equivalent to η-reducing the implicit continuations to functions where possible. A Scheme aficionado might prefer to say avoiding η-expanding where unnecessary.

This is a mathematical curiosity, but does it have practical significance? If you're programming in continuation passing style, you should be careful to η-reduce (or avoid η-expanding) your code.

Years ago I was writing an interpreter for the REBOL language. I was getting frustrated trying to make it tail recursive. I kept finding places in the interpreter where the REBOL source code was making a tail call, but the interpreter itself wasn't, so the stack would grow without bound. I decided to investigate the problem by rewriting the interpreter in continuation passing style and seeing why I couldn't η-convert the tail calls. Once in CPS, I could see that eval took two continuations and I could achieve tail recursion by η-reducing one of them.


Anonymous said...

It's funny, in Gambit if you compile

(map - l)

then it will unroll the implicit recursion in map to some extent, but each call to - will be an intermodule call to the system library routine ##-, but if you eta-expand to

(map (lambda (x) (- x)) l)

then each call to the eta-expanded - will be inlined to

(if (fixnum? x) (let ((res (fx-? x))) (if res res (##- x)))
(if (flonum? x) (fl- x)
(##- x)))

and the code will run much faster in the common case when the elements of l are fixnums or flonums.

Perhaps the Gambit compiler should do this eta-expansion automatically for functions arguments to map.

John Cowan said...

1) Eta-expansion only works reliably in the ordinary lambda calculus, whereas Scheme uses the eager variant, which means it only sometimes works, as you show above.

2) If map is supposed to special-case some functional arguments, it has to detect them. You can use eq? for this in R5RS, and eqv? in R7RS (which allows eq? to return #f on two procedure objects), but in R6RS it can't be done at all: the value of both eq? and eqv? on two procedures is a boolean, but the spec doesn't say which.

This is done so that car (e.g.) can be inlined in operator position while it remains a reference to a function in operand position. Inlining can be done portably in any R6RS or syntax-case system by writing a macro, because a macro keyword in operand position matches a syntax-case rule of the form _. this works because an identifier is a valid top-level pattern.

3) Your Rebol interpreter apparently re-created what the original ITS Scheme interpreter described in R0RS does.