I've been thinking about a Common Lisp feature recently, and I haven't been
able to figure out how to implement it well. That is the ability to
transfer control to a point that is lexically apparent but may be elsewhere
on the stack. E.g.
(block b
(mapc #'(lambda (x) (if (match x winner) (return-from b x)))
list))
I don't have any problem with figuring out how to get this to work
correctly; my problem is how to trap the misuses, like:
(block b
#'(lambda () (return-from b 1)))
followed by a call of the closure. Lucid, at least, correctly catches this
bug. I can think of two implementations for doing so, neither of which I'm
fond of:
1. Scan closures when placing them out of scope and invalidate their
control transfers.
2. Associate a unique tag with each block and invalidate the tag on return
from the block.
(1) is expensive. (2) is cheap but requires consing, which seems counter
to the whole point of giving control transfers dynamic extent. (The unique
tag could start out being a fixnum, eliminating consing for the first
couple of billion occurrences, but eventually you'd have to either cons
bignums or wrap around, risking tag duplication.)
Is there any method I'm missing, something that's both cheap and cons-free?
What do most implementations do?
Jonathan Amsterdam
In article <·················@kix.ai.mit.edu> ···@ai.mit.edu (Jonathan Amsterdam) writes:
>2. Associate a unique tag with each block and invalidate the tag on return
> from the block.
>
>(2) is cheap but requires consing, which seems counter
>to the whole point of giving control transfers dynamic extent.
I think I'd go with (2). I don't think the whole point of making exit
points dynamic extent was to save on consing, at least not to this extent.
It's to save the need to cons a representation of the entire control state.
> (The unique
>tag could start out being a fixnum, eliminating consing for the first
>couple of billion occurrences, but eventually you'd have to either cons
>bignums or wrap around, risking tag duplication.)
The tag only has to be unique for a particular exit point. So they won't
have to increment as often as if there was a single, global ID generator.
If you're worried about using generic arithmetic for this, you could simply
have a two-fixnum tag field, and roll your own double-precision integer
arithmetic routine using fixnum arithmetic. Given typical fixnum sizes,
this should be enough to re-enter a block every microsecond for several to
several thousand years.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar