Subject: Re: Summary: Thoughts on implementing Scheme in C
From: (Rob Warnock)
Date: 11 Nov 2000 04:31:08 GMT
Newsgroups: comp.lang.scheme
Message-ID: <8uii2c$e9m7t$>
felix <> wrote:
| Rob Warnock wrote:
| >This is not obvious to me -- could you say more?  Since the environment
| >of the current closure is abandoned when making a tail call, I fail to
| >see the necessity of space-unsafety in the simple linked model.
| This problem is not so much related to tail-calls, it has something to do
| with the set of free variables: Linked closures keep a pointer to the
| complete lexically superior environment, even to variables that are not
| used by the current closure. When using flat closures, a closure *only*
| contains the variables that it really needs.

Yes, I understand all that, and I certainly grant that the simple
environment model is "space inefficient" compared to the "flat" model.
But you said, or at least implied, that the simple linked environment
model was (paraphrased) "space unsafe with respect to tail calls", not
merely "space inefficient". To me something isn't "space unsafe" unless
a (quasi-)infinite tail-call chain causes the retained (not-collected)
space to grow without limit.

So I still don't see what would make the simple linked model "unsafe"...

| >One such bit is enough to distinguish (say) fixnums from boxed/heap;
| >two is enough for fixnums, other-immediate (#t, #f, chars, etc.),
| >boxed, and "broken heart" (for copying GCs); three [a common case]
| >is a *wealth* of riches!! [CMUCL uses 3 bits, doesn't it?]
| The "broken heart" (isn't it a lovely term?) is only needed for boxed
| values: some special header-value is enough. No need for a tag bit.

Well, that depends on your heap format. I agree that if the smallest
possible heap object is two pointers (or bigger), the "broken heart"
can be any old distinguished pointer-sized value, with the following
pointer word containing the "forwarding" address of the relocated object.
But if, in some hypothetical implementation, it is possible to have
one-word "singleton" heap objects, then you might not *have* any place
to put the forwarding pointer.

Consider, for example, an implementation in which the first word
of a heap object is not a type word full of bits and/or subfields
(length, type, subtype, whatever), but instead is a full pointer to
the "type object" of the heap object's type (which might be the case
if you have a builtin object system, say). In such cases, one might
define a class with no slots per se, only object identity (and perhaps
parent class methods). In that case, (make-foo) or (make-instance <foo>)
might allocate only one word of heap, containing a pointer to the
<foo> (sub)class type object. In such cases, it is useful to have
a broken heart that is *also* a forwarding pointer.


Rob Warnock, 31-2-510
Network Engineering
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043