## 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.