Path: utzoo!mnetor!uunet!husc6!rutgers!ucla-cs!zen!ucbvax!CSD16.NYU.EDU!ericson
From: ericson@CSD16.NYU.EDU (Lars Ericson)
Newsgroups: comp.lang.scheme
Subject: Optimizing tail-recursive operations using jumps
Message-ID: <8801022048.AA17960@csd16.nyu.edu>
Date: 2 Jan 88 20:48:48 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 30

Consider the following calling pattern:

;0 Calling /' with arguments (<f <f 1>> <f <f <f -2<pp Y>>>>)
; 1 Calling // with arguments (<f <f 1>> <f <f <f -2<pp Y>>>>)
;  2 Calling /' with arguments (<f 1> <f <f -2<pp Y>>>)
;   3 Calling // with arguments (<f 1> <f <f -2<pp Y>>>)
;    4 Calling /' with arguments (1 <f -2<pp Y>>)
;     5 Calling // with arguments (<f 1> <f -2<pp Y>>)
;     5 Returned from // with values ((<f 1>) / (<f -2<pp Y>>))
;    4 Returned from /' with values ((<f 1>) / (<f -2<pp Y>>))
;   3 Returned from // with values ((<f 1>) / (<f -2<pp Y>>))
;  2 Returned from /' with values ((<f 1>) / (<f -2<pp Y>>))
; 1 Returned from // with values ((<f 1>) / (<f -2<pp Y>>))
;0 Returned from /' with values ((<f 1>) / (<f -2<pp Y>>))

/' is a procedure and // is an operation.  Both are compiled, one calls
the other.  It is apparent that every call is tail-recursive, since the
results on the way "back up" are unmodified.

Why not use continuations somehow to have a "REWRITE-CALL", similar to
a plain old JUMP, which passes arguments to a subprocedure, overwriting
the argument space on the stack for the calling procedure, such that
when the subprocedure returns, it returns to the caller of the caller?
Like DEFINE-INTEGRABLE, REWRITE-CALL would be an optimization that the
user applies intentionally when it is clear that the call is tail-recursive.

This seems like it would be pretty easy to implement, both for interpreted
and compiled code, in terms of continuations.

-- Lars Ericson