Consider this lambda expression:
(lambda (x) (sqrt x)).
This function simply calls
sqrt on its argument and
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
directly. We say that this function and the
function are extensionally equal. We can replace this
lambda expression with a literal reference to the
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
(lambda (x) ((compute-f) x)). We can
η-reduce this to
(compute-f), but this makes a
subtle difference. When wrapped with the
(compute-f) is evaluated just before it is
x. In fact, we won't
(compute-f) unless we invoke the result of the
lambda expression somewhere. However, once
(compute-f) is evaluated at the point
the original lambda was evaluated, which can be quite a bit
When a function
foo calls another
bar as a subproblem, an
implicit continuation is passed
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
barreturns, we'll finish running the code in
fooand further continue by invoking the continuation supplied to
foo makes a tail call to
foo is just returning what
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
bar, we can just pass along the continuation that was passed to
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
eval took two continuations and I could
achieve tail recursion by η-reducing one of them.
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)
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.
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.
Post a Comment