Summary: Thoughts on implementing Scheme in C 
Author Message
 Summary: Thoughts on implementing Scheme in C

Since Shriram asked me to do so, I am going to summarize my thoughts
on C as the implementation language for Scheme.

Note that this summary tries to accurately reflect my own beliefs.  I
will also try to explain the reasons why I hold these beliefs.  Nobody
should in any way feel offended if I criticize her favorite
implementation method.  This is not personal criticism, and for every
point that I am going to make here, there may very well be another
aspect to consider that counters my evaluation.

Also do not forget that this is just a usenet article and not a
scientific paper.  Since most if not all of these things are
well-known, anyone interested in finding out more, better, more
detailed information on it should consult the scientific literature.

Best regards,
Matthias Blume

=============================================================================

Why I think that C is not the ideal implementation language for Scheme
----------------------------------------------------------------------
                                                     by Matthias Blume
                                                    Tokyo, Nov 9, 2000

0. Outline
----------

There are 5 sections (excluding this outline).

Section 1 specifies the problem domain by making precise what
languages I am going to talk about.

Section 2. gives a brief overview of Scheme features that are
potentially troublespots for an implementation -- together with a
short summary of how these features tend to be implemented.

Section 3. lists specific problems with the C language that I see or
that I have personally encountered when implementing Scheme in C.

Section 4. briefly talks about specific problems with "Baker's
method".

Finally, section 5. has some general (and concluding) thoughts on
source-to-source translation.

1. Scope of this discussion
---------------------------

1.1. The C language

By "C" I will refer to what I consider "portable" C.  Portable C in
this sense is the language by that name described and mandated by
standardization bodies such as ANSI or ISO.  In particular, this
excludes all language constructs whose semantics are "undefined" or
"implementation-dependent".

This is a rather strict requirement.  It also excludes constructs that
"work on every platform I tried", or "are going to work on any
'reasonable' implementation", or "work on gcc, and I never use
anything but gcc" and such.

(Needless to say, I also strongly dislike the use of #if-voodoo in C
source code when it is used to deal with implemenatation-specific
behavior.)

1.2. The Scheme language

In a similar way, by "Scheme" I will refer to the language described
in and mandated by documents such as RnRS (let's say for n >= 4) or
the IEEE Scheme standard.  I will consider an implementation of Scheme
to be a "Quality Implementation" if it is efficient and as complete as
possible with respect to these standards.

Critical features include: lexical scope, first-class functions,
call-by-value, proper tail-recursiveness, fully general
call-with-current-continuation ("call/cc"), dynamic type system.  Any
implementation that does not have the above properties is not
considered here.

Highly desirable features include: the full numeric tower (bignums,
rationals, reals, complex), safety ("no core dumps"), the
"safe-for-space" property (generalization of "tail-recursiveness" to
all data).

2. Possible implementation method(s)
------------------------------------

2.1. Lexical scope and first-class functions

In a C-like language with a sufficiently rich type system for data
structures and with function pointers, but with no nested functions
(e.g., C), or no pointers to nested functions (e.g., Modula-2), one
can always simulate lexically scoped, first-class functions by
performing a "closure conversion".

Closure conversion turns all lambda-expressions into fully closed
lambda expressions; previously "free" variables will be passed as
additional explicit arguments, first-class functions are a function
pointer together with a record of values for all free variables of
that function (the "closure").

Data structures representing closures must be heap-allocated (in the
general case).

There is a choice between using "linked" or "flat" closures (or a
combination of both techniques).  Ordinary linked closures (= SICP's
"environment model") are not safe-for-space but they avoid copying, so
they may contain mutable state.  Flat closures are safe for space but
incur copying of certain program variables -- which requires these
variables to be immmutable.  (Many Scheme compilers -- beginning with
Kranz' Orbit, I believe -- perform a simple initial transformation
that turns all Scheme variables into immutable variables by
introducing explicit ref cells for those that are subject to "set!".)

Conclusion: Lexical scope and first-class functions can be implemented
adequately; techniques vary.

2.2. Call-by-value

This is easy since C is also cbv.

2.3. Tail-recursiveness

Informally speaking, "proper tail-recursiveness" requires that a
function call in tail position does not grow the stack.  An infinite
recursion through tail calls that does not consume memory in any other
way should run in constant space.

This is somewhat tricky to do in C since a straightforward mapping
from Scheme functions to C functions will not have the desired effect
because C compilers typically do not implement tail-call optimization.

However, there many possible techniques to simulate the effect, some
of which are:

  - {*filter*}olines:  If f calls g and g wants to tail-call h, it will
    return (to f), in such a way that f will be prompted to call h on
    g's behalf.  An open issue here is how to portably represent the
    "pending" function call so that f can call h without knowing the
    type of h. (Discussed later.)
    Ordinary function calls (i.e., those that are not in tail
    position) are carried out as (mostly) ordinary C function calls.
    However, the caller must implement the {*filter*}oline for use by
    the callee for the case that the callee performs a tail-call.

  - Baker's "Cheney on the MTA" (CotMTA) technique:  The whole program is
    CPS-converted (see below) so that _all_ calls are tail-calls.
    On the C side, each such call is carried out anyway, thereby growing
    the stack.  At certain points during execution, the stack is forced
    to be completely unwound, throwing away all control information --
    which isn't necessary anyway because no function ever returns.
    This method has the other nice property that the C stack can
    double as a generational GC's allocation area.
    Unwinding of the stack (after doing a minor GC) can be done either
    via longjump, or -- in languages that do not have longjump -- by
    simply returning.

  - explicit stack management:
    CPS-converted code essentially already manages its own control
    stack.  The use of the C stack by CotMTA is more or less
    incidental and by no means necessary.  The CPS-converted code
    could also use a global {*filter*}oline to avoid growing any C stack.
    This requires that all data will be allocated on the heap from
    the beginning.
    The "CPS-conversion+global {*filter*}oline" method was already used by
    the very first Scheme compiler (Steele's "Rabbit" -- where the
    target was not C but Lisp).

    It is also possible to manage a stack explicitly without doing
    a CPS-conversion.  This typically involves some kind of
    non-recursive interpreter that operates on some representation
    of the Scheme program (AST, bytecode, ...).
    (In some sense every "native" implementation is in this category:
    the non-recursive interpreter is the CPU, the intermediate
    representation is the machine program.)

2.4. Call-with-current-continuation

The call/cc operation involves accessing the program's full control
state and preserving this state in such a way that it can be
reinstated at arbitrary later times.

In ordinary C code, the C stack represent's the program's control
state.  Since accessing the C stack in the required way (copying,
storing away) is not portable, call/cc would be extremely difficult if
not impossible to implement portably as long as arbitrary C code is
involved.

However, upon inspection of the methods for implementing
tail-recursiveness above (section 2.3.), we find that all of them
except for the first represent control information explicitly.  Thus,
with these techniques, implementing call/cc is not very difficult.

(Notice that CPS-converted code does no longer contain any invocations
of call/cc and continuations are represented explicitly as ordinary
closures.)

2.5. Dynamic type system

Implementing Scheme's dynamic type system typically requires that all
data structures be annotated with their run-time type, i.e., that this
type be represented explicitly in some way.  Moreover, since objects
of arbitrary types can be passed in any variable and as argument to
any function, there must be a uniform ("boxed") representation for all
data.

For complex data structures that are stored in the heap one can either
store a descriptor along with the actual data, or one can allocate
these structures in separate memory regions so that the type becomes
implicitly known by knowing the address of the object.  Such Scheme
objects are uniformely represented by their heap pointer.

For certain simple values such as small integers, one most certainly
(for efficiency reasons) would want to represent them as immediate
values and not heap-allocate boxes for them.  However, to be able to
tell that they are values and not pointers to heap objects, there must
be some kind of type tagging _within_ the value's immediate
representation.  There are various bit-fiddling tricks that one can
play to achieve this effect; all these tricks depend in some way on
the underlying machine architecture.

2.6. Numeric tower

The numeric tower can be seen as just a special case of Scheme's
dynamic type ...

read more »



Mon, 28 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C

+---------------
| ...I am going to summarize my thoughts on C as the implementation
| language for Scheme.
+---------------

After only a quick reading, IMHO it's a useful contribution. A few random
comments and/or questions (again, based on only a brief reading)...

+---------------
| Since most if not all of these things are well-known, anyone interested
| in finding out more, better, more detailed information on it should
| consult the scientific literature.
+---------------

The one article that *immediately* came to mind was David Gudeman's
"Representing Type Information in Dynamically Typed Languages"
<URL:ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/typeinfo.ps.gz>,
which covers a wealth of representational issues.

+---------------
| Ordinary linked closures (= SICP's "environment model") are not
| safe-for-space...
+---------------

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.

I certainly see that you *can* write space-unsafe tail-call code using
closures, e.g., write CPS code in Scheme and pass a "new" closure that
always captures some portion of the current environment (and thus captures
the *entire* environment, since it's linked), but that's equally true
of tail-call code that conses data onto a list that it passes explicitly.
Both are extending a data structure (albeit the environment is an implicit
one) per call. However, AFAICT not *all* tail-call sequences -- even
quasi-infinite ones (such as, say, finite-state machines implemented
as a tail-call per state transtition) -- need involve such growth.
So what am I missing?

+---------------
| 2.3. Tail-recursiveness
| Informally speaking, "proper tail-recursiveness" requires that a
| function call in tail position does not grow the stack.  An infinite
| recursion through tail calls that does not consume memory in any other
| way should run in constant space.
+---------------

Minor quibble: I suspect we Schemers (and Lispers) tend to confuse
other people when we say "proper tail-recursiveness", because those
not deeply familiar with the concept assume there's no "recursion"
going on in some cases when "proper tail-recursion" is indeed still
required (e.g., quasi-infinite sequences of freshly-created closures
which tail-call freshly-created closures which tail-call... yet with
no closure ever calling "itself", even indirectly).

Also, many people who are not Scheme implementers come away with the
false belief that optimizing a self-tail-call ("immediate" recursion)
into a simple loop [such as GCC does] is somehow "all you really need"
for proper tail-recursiveness. (It isn't, as you of course know.)

To completely side-step this confusion, I personally now prefer to use
only the term "proper tail-call optimization", which, as R5RS says in
sect. 3.5, "supports an unbounded number of active tail calls". [And I
think it's unfortunate that R5RS didn't shift to using the term "proper
tail-call optimization", since that's really what they're talking about.]

The relevance to your article is that getting self-tail-recursion right
in C (by most C people's notion of "right") isn't even *close* to being
good enough for full Scheme...

+---------------
| 2.5. Dynamic type system
| ... [since] arbitrary types can be passed in any variable and
| as argument to any function, there must be a uniform ("boxed")
| representation for all data.
+---------------

Minor quibbles:

1. Some people reserve the term "boxed" to imply "heap-allocated",
   so to avoid this ambiguity Gudeman refers to data being "wrapped"
   with the type information, which may or may not (depending on the
   type) also require heap space (a "box").

2. While your statement is of course true, some readers may not
   immediately understand that in a "uniform representation" not all
   types need be wrapped in the same way -- decoding the type can be
   based on a possibly-complex decision tree. Only the entire representation
   *algorithm* need be "uniform" within a given implementation. Again,
   Gudeman's paper is a great reference for the tradeoffs between "flat"
   and "multilevel-decoded" wrappings.

+---------------
| For certain simple values such as small integers, one most certainly
| (for efficiency reasons) would want to represent them as immediate
| values and not heap-allocate boxes for them.
+---------------

Aha! Here you yourself clearly separate "wrapping" from "boxing".
(So I probably *wasn't* being too picky...?)

+---------------
| However, to be able to tell that they are values and not pointers
| to heap objects, there must be some kind of type tagging _within_
| the value's immediate representation.  There are various bit-fiddling
| tricks that one can play to achieve this effect; all these tricks
| depend in some way on the underlying machine architecture.
+---------------

While this is probably true, there *are*, I believe, "portable" (in
the sense of your initial requirement) ways in ANSI or ISO C to access
the required machine-dependencies in the local environment. In some
cases this may require defining the generic "Scheme" data type to be
a union and/or a structure (or a union of structures, etc.).

I believe it *is* a C requirement that "malloc()" return a block of
storage which is aligned to the most stringent requirements of any
basic C type on the underlying machine architecture, and, on current
machines at least, almost always requires at least a few low-order
bits of the addresses of all malloc'd objects will be zeroes.

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?]

+---------------
| 2.6.1. Efficient small integers
+------- [lots of good stuff elided] --------

One cute technique you didn't mention is the one used by SIOD Scheme,
which boxes *everything* ("everything's a pointer"), but which quite
nicely optimizes small integers by preallocating a bunch of them at
startup (configurable, but the range -100 to +1000 is not unreasonable),
and having all arithmetic operators check their results against that range,
returning a preallocated one where possible instead of consing up a new one.

This can also *significantly* speed up checking for known small values
by using an "eq?" (pointer) test for specific values instead of unwrapping
(or in this case, unboxing) the value and comparing with native arithmetic.

+---------------
| In a language where the compiler knows at compile-time that a number
| is a small integer, the typical operation requires just one single
| machine instruction.
+---------------

If SIOD-style small-integer preallocation is done at compile time,
an "eq?" test might even be possible in a C "switch()". (...albeit
the casts you'd have to use would be pretty ugly, since "switch()"
only supports integral types IIRC.)

+---------------
| 3.2. Efficient representation of runtime types
| As long as the "descriptor word" technique is being used, things are
| not difficult.  But as I explained earlier, for efficiency one would
| like to represent certain values as immediate values (small integers,
| perhaps booleans, nil, characters, ...).
+---------------

The SIOD-style preallocation trick works for these types, too.
And by preallocating all the values for a type (say, characters)
in a single array, one can use simple C pointer arithmetic --
*without* ugly casts -- to perform things like "char->integer"
or "integer->char".

+---------------
| As far as Scheme and mutability is concerned, one might argue that
| data structures in Scheme aren't immutable.
+---------------

Well, an implementation is *allowed* (though not required!) to make
certain data immutable. See R5RS "3.4 Storage model":

        In many systems it is desirable for constants (i.e. the values
        of literal expressions) to reside in read-only-memory. To express
        this, it is convenient to imagine that every object that denotes
        locations is associated with a flag telling whether that object
        is mutable or immutable. In such systems literal constants and
        the strings returned by symbol->string are immutable objects,
        while all objects created by the other procedures listed in this
        report are mutable. It is an error to attempt to store a new value
        into a location that is denoted by an immutable object.

+---------------
| There is one data structure that can be (and by most Scheme compilers
| will be forced to be) immutable: the closure.
+---------------

Though note that closures contain their environments, and portions
of those captured environments *can* be mutable! The only thing that
helps one out of this thorny question is that there are no mutation
operators defined on closures themselves! [In fact, AFAICT the *only*
mutable things required by R5RS (again, "3.4 Storage model") are variables
(which aren't "objects" per se, so the notion of "mutation" itself is
a bit weird -- what is mutated is the location the variable is bound to)
and "objects such as pairs, vectors, and strings" (indeed, *only* pairs,
vectors, and strings are defined with any mutation operators).

-Rob

-----

Network Engineering             http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.          Phone: 650-933-1673
1600 Amphitheatre Pkwy.         PP-ASEL-IA
Mountain View, CA  94043



Tue, 29 Apr 2003 13:31:11 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:

>I believe it *is* a C requirement that "malloc()" return a block of
>storage which is aligned to the most stringent requirements of any
>basic C type on the underlying machine architecture,

This is true.

Quote:
>and, on current machines at least,

      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This is the problem. Matthias is talking about what the ANSI C
standard guarantees. It is not true that the C standard:

Quote:
>almost always requires at least a few low-order
>bits of the addresses of all malloc'd objects will be zeroes.

Of course it is true for most practical C implementations.
But you can go over to comp.lang.c and have interesting discussions
about arcane architectures for which it is *not* true.

Typically, the arcane architecture discussed is some C->Lisp
compiler, in which all basic types, including void*, have
a size of 1. (Everything is just represented as 1 Lisp value...)

Quote:
>And by preallocating all the values for a type (say, characters)
>in a single array, one can use simple C pointer arithmetic --
>*without* ugly casts -- to perform things like "char->integer"
>or "integer->char".

Not according to ANSI C. Only pointer comparisons where both
pointers lay in the same array are guaranteed to produce
meaningful results.

Not so very long ago, we had the segmented "real mode" 8086
architecture, in which a pointer comparison typically only
compared the 16 least significant bits. Since arrays were
guaranteed not to cross segment boundaries, this was (and is)
in accordance to ANSI C.

There are still millions of these machines in use. They are still
used today in embedded systems. Hardly obscure...

Anyway, if you want an ANSI C language lawyer, you should
go over to comp.lang.c, and ask *them* if all the assumptions
Scheme implementations typically make are warranted.

When you are feeling {*filter*}, that is.

Greetings, Stephan

--
ir. Stephan H.M.J. Houben
tel. +31-40-2474358 / +31-40-2743497



Tue, 29 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C
+---------------

| >And by preallocating all the values for a type (say, characters)
| >in a single array, one can use simple C pointer arithmetic --
| >*without* ugly casts -- to perform things like "char->integer"
| >or "integer->char".
|
| Not according to ANSI C. Only pointer comparisons where both
| pointers lay in the same array are guaranteed to produce
| meaningful results.
+---------------

Uh... Did you even *read* the text you were objecting to?!?
I *said*, "by preallocating all the values for a type (say,
characters) IN A SINGLE ARRAY"!!  A "single array" is surely
the "same array" as itself, no?

-Rob

-----

Network Engineering             http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.          Phone: 650-933-1673
1600 Amphitheatre Pkwy.         PP-ASEL-IA
Mountain View, CA  94043



Tue, 29 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:

>+---------------

>| >And by preallocating all the values for a type (say, characters)
>| >in a single array, one can use simple C pointer arithmetic --
>| >*without* ugly casts -- to perform things like "char->integer"
>| >or "integer->char".
>|
>| Not according to ANSI C. Only pointer comparisons where both
>| pointers lay in the same array are guaranteed to produce
>| meaningful results.
>+---------------

>Uh... Did you even *read* the text you were objecting to?!?

Yes, I did. Thank you very much for your trust.

Quote:
>I *said*, "by preallocating all the values for a type (say,
>characters) IN A SINGLE ARRAY"!!  

No need to scream.

You can put the char's in a single array, but that still
doesn't allow you to find out whether something is a char
in the first place. And without that, char->integer cannot
be implemented safely, and char? cannot be implemented at all.

Quote:
>A "single array" is surely
>the "same array" as itself, no?

You said: a single array for _all the values of a type_.

Stephan
--
ir. Stephan H.M.J. Houben
tel. +31-40-2474358 / +31-40-2743497



Tue, 29 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C
+---------------
| You can put the char's in a single array, but that still
| doesn't allow you to find out whether something is a char
| in the first place. And without that, char->integer cannot
| be implemented safely, and char? cannot be implemented at all.
+---------------

Not true! "Char?" *can* be implemented in a totally portable
ANSI C way, just not very efficiently:   ;-}  ;-}

        SCHEME is_char(SCHEME x) {
          extern SCHEME standard_chars[];
          int i;
          for (i = 0; i < NUM_CHARS; ++i)
            if (EQ(x, &standard_chars[i]))
              return SCHEME_TRUE;
          return SCHEME_FALSE;
        }

And then you can put the non-portable version of the code that depends
on pointer compare working outside array bounds under a machine-dependent
feature test, and use fast code like:

        SCHEME is_char(SCHEME x) {
          extern SCHEME standard_chars[];
          if ((addr_t)x >= (addr_t)&standard_chars[0] &&
              (addr_t)x < (addr_t)&standard_chars[NUM_CHARS])
            return SCHEME_TRUE;
          return SCHEME_FALSE;
        }

+---------------
| >A "single array" is surely the "same array" as itself, no?
|
| You said: a single array for _all the values of a type_.
+---------------

Yes, characters are a type, so one array for all characters.
What's odd about that?

Note that the original context was *only* SIOD-style *preallocated*
types such as chars or booleans (or sub-types, such as small integers),
not for general heap-allocated types.

-Rob

-----

Network Engineering             http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.          Phone: 650-933-1673
1600 Amphitheatre Pkwy.         PP-ASEL-IA
Mountain View, CA  94043



Tue, 29 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:
> I believe it *is* a C requirement that "malloc()" return a block of
> storage which is aligned to the most stringent requirements of any
> basic C type on the underlying machine architecture, and, on current
> machines at least, almost always requires at least a few low-order
> bits of the addresses of all malloc'd objects will be zeroes.
> ...

Well, that is true much of the time, but certainly doesn't derive from
ANSI C.  ANSI C is specifically constructed to make the representation
of pointers opaque.  I'm not aware of any way to write pointer tag code
(low bits or otherwise) that wouldn't depend on knowledge of the
particular representation used by the compiler in use.  The only
standard way to define such tag bits is within a single allocation
object, which ANSI C limits in size to 65535 bytes.  In standard C++
though, the size limit is lifted and size_t is big enough so that you
could allocate a heap as a single object and thus rely on pointer
arithmetic to get the tag bits.  It would then be simple to have a
switch that allowed dynamic heap expansion (mallocing more than once) on
"friendly" implementations (a probably correct setting for such a switch
could be deduced from appropriate diagnostic code).

jim
------------------------------------------------------------
James P. White             Netscape DevEdge Champion for IFC
IFC Exchange  -  Insanely great Java  -  http://www.ifcx.org



Tue, 29 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:

>+---------------
>| Ordinary linked closures (= SICP's "environment model") are not
>| safe-for-space...
>+---------------

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

(let ([a ...] [b ...] [c ...])
  (define (foo ...) ; accesses a and b
     ...)
  ...)

With linked closures, "foo"'s closure would contain a link to the
enclosing environment ("a", "b" and "c"). So the value of "c" would
be retained. With flat closures, "foo"'s closure would only contain
the values of "a" and "b" (or boxes of these values, in case they
are assigned). "c"'s value could be recovered by the garbage
collector.

Quote:
>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.

felix



Tue, 29 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:


> +---------------
> | You can put the char's in a single array, but that still
> | doesn't allow you to find out whether something is a char
> | in the first place. And without that, char->integer cannot
> | be implemented safely, and char? cannot be implemented at all.
> +---------------

> Not true! "Char?" *can* be implemented in a totally portable
> ANSI C way, just not very efficiently:   ;-}  ;-}

>    SCHEME is_char(SCHEME x) {
>      extern SCHEME standard_chars[];
>      int i;
>      for (i = 0; i < NUM_CHARS; ++i)
>        if (EQ(x, &standard_chars[i]))
>          return SCHEME_TRUE;
>      return SCHEME_FALSE;
>    }

> And then you can put the non-portable version of the code that depends
> on pointer compare working outside array bounds under a machine-dependent
> feature test, and use fast code like:

>    SCHEME is_char(SCHEME x) {
>      extern SCHEME standard_chars[];
>      if ((addr_t)x >= (addr_t)&standard_chars[0] &&
>          (addr_t)x < (addr_t)&standard_chars[NUM_CHARS])
>        return SCHEME_TRUE;
>      return SCHEME_FALSE;
>    }

To put an end to this: Rob is right, even without resorting to the
abomination above.  Notice that the pre-allocated array of "things"
(small ints, chars, bools, ...) still contains descriptor words for
those "things".  So you first fetch through the pointer and test the
descriptor, and when you find the right one you _know_ that you have a
pointer to the right array, so you can do a pointer comparison.

I knew about this trick -- as you can tell from the fact that I used
it in VSCM.  I just decided not to talk about it because it would have
made the long article even longer - and for little gain.  The problem
with this technique when comparing it to the bit-fiddling technique
(which is not portable) is that it loses ot modern machines that have
high memory latency.  The bit-fiddling type test can be done
completely in registers while the portable method using pre-allocated
arrays and descriptor words involves at least one fetch from memory.

Besides, I found that while the trick speeds things up tremenously
(compared with all-numbers-are-heap-allocate), it still sucks as soon
as you start leaving the pre-allocated range.

Best regards,
Matthias

--

Kyoto University, Research Institute for Mathematical Sciences
(remove those spam-preventing underscores from mail address)



Wed, 30 Apr 2003 01:13:43 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:


> >+---------------
> >| Ordinary linked closures (= SICP's "environment model") are not
> >| safe-for-space...
> >+---------------

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

That's right.  I was perhaps being a bit obscure with my original claim.

Both linked and flat closures can get tail-call optimization right.  By
"safe-for-space" I was referring to a stronger notion, in particular to
Appel's definition, where variables that are no longer "live" (for an
axiomatically defined notion of what's "live") must not hold on to
heap-allocated memory.

Now, it is actually possible to make the axioms so weak that even linked
closures are "safe-for-space", but Appel's axioms are stronger.

Matthias

--

Kyoto University, Research Institute for Mathematical Sciences
(remove those spam-preventing underscores from mail address)



Wed, 30 Apr 2003 10:26:24 GMT  
 Summary: Thoughts on implementing Scheme in C
+---------------
| >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

-----

Network Engineering             http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.          Phone: 650-933-1673
1600 Amphitheatre Pkwy.         PP-ASEL-IA
Mountain View, CA  94043



Wed, 30 Apr 2003 12:31:08 GMT  
 Summary: Thoughts on implementing Scheme in C

{stuff deleted}

Quote:
> 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"...

The notion of "space safety" that Matthias is using is the notion of space
safety defined by Andrew Appel, in his book Compiling with
Continuation. Andrew's notion of space safety is pretty "standard" within
the academic community.

  http://ncstrl.cs.princeton.edu/expand.php3?id=TR-454-94

Has lots of details about safe or space closure conversion.

The "safe for space complexity" rule is simply:

  Any local variable binding  must be unreachable after its last use
  within its scope.

Andrew's book has a more formal definition. One can argue about whether the
definition is useful or not, but under this definition link closures are not
"safe for space".



Wed, 30 Apr 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C
Matthias, 3 dumb questions:

1) What about implementing purely functional programming in C?
i.e. Scheme without assignment (setq, setcar, etc).

2) I've thought about CPS but only for functional programming (which
Felleisen stresses can be understood mathematically in his
Lambda-value Calculus).  So I was confused by the idea that (which
Shriram mentioned a while back) that you need closures to implement
CPS.  I think of closures as in the assignment end of Scheme.

3) You wrote

   The common idiom [for variable-length object ...]  is (as far as I
   know) not actually strictly legal (notwithstanding the fact that
   some compilers -- notably gcc -- explicitly support this), and all
   others that I know implicitly tolerate it, doing "The Right Thing".
   But the above idiom is (or, I should say, "would be") very useful
   for implementing things such as Scheme strings or vectors.

So what about the larger question of implementing Scheme in gcc?  (I
expect you'll say that variable-length objects is just one of many
implemention pitfalls.)  

--
Bill
<http://www.math.nwu.edu/~richter>



Thu, 01 May 2003 03:00:00 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:

> +---------------
> | Ordinary linked closures (= SICP's "environment model") are not
> | safe-for-space...
> +---------------

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

As I explained in another article, I was referring to Appel's notion
of "safe-for-space" here -- which is stronger than the requirement of
proper tail-call optimization.

Quote:
> Well, an implementation is *allowed* (though not required!) to make
> certain data immutable. See R5RS "3.4 Storage model":

>    In many systems it is desirable for constants (i.e. the values
>    of literal expressions) to reside in read-only-memory. To express
>    this, it is convenient to imagine that every object that denotes
>    locations is associated with a flag telling whether that object
>    is mutable or immutable. In such systems literal constants and
>    the strings returned by symbol->string are immutable objects,
>    while all objects created by the other procedures listed in this
>    report are mutable. It is an error to attempt to store a new value
>    into a location that is denoted by an immutable object.

Sure.  This makes my point all the more relevant.

Quote:
> +---------------
> | There is one data structure that can be (and by most Scheme compilers
> | will be forced to be) immutable: the closure.
> +---------------

> Though note that closures contain their environments, and portions
> of those captured environments *can* be mutable!

Not in standard Scheme.  If you view the environment as a mapping from
names to _locations_ (i.e., NOT the values stored in those locations),
then even a set! of a variable will not modify the environment
(because the mapping does not change).

This is like having an (immutable) record of (mutable) ref cells in
ML: you can store into the ref cells, but you can't mutate the
record.  This pretty accurately describes how mutable variables and
(flat) closures are often implemented by Scheme compilers.

Matthias

--

Kyoto University, Research Institute for Mathematical Sciences
(remove those spam-preventing underscores from mail address)



Sat, 03 May 2003 10:46:43 GMT  
 Summary: Thoughts on implementing Scheme in C

Quote:

>> +---------------
>> | There is one data structure that can be (and by most Scheme compilers
>> | will be forced to be) immutable: the closure.
>> +---------------

>> Though note that closures contain their environments, and portions
>> of those captured environments *can* be mutable!

>Not in standard Scheme.  If you view the environment as a mapping from
>names to _locations_ (i.e., NOT the values stored in those locations),
>then even a set! of a variable will not modify the environment
>(because the mapping does not change).

>This is like having an (immutable) record of (mutable) ref cells in
>ML: you can store into the ref cells, but you can't mutate the
>record.  This pretty accurately describes how mutable variables and
>(flat) closures are often implemented by Scheme compilers.

I think this is a bit too strong: I could imagine that just the same
number of Schemes (or the majority?) use mutable environments.
I wouldn't take the flat-closure/ref cell-implementation strategy for
granted (even if I personally find it more attractive).
Furthermore "standard" Scheme doesn't imply any implementation
technique: the "mapping of names to locations" is a totally
abstract term. So the Scheme standard has nothing to do with
this discussion.

felix



Sat, 03 May 2003 03:00:00 GMT  
 
 [ 90 post ]  Go to page: [1] [2] [3] [4] [5] [6] [7]

 Relevant Pages 

1. Implementing Scheme in Scheme

2. Implementing Scheme in Scheme

3. Some thoughts on implementing GUI testing/automation interfaces

4. Summary. Interpreters are faster than I thought

5. please unscribe dinh@cs.ucla.edu from the scheme mailing list

6. Wanted: references on using Scheme for Intro CS courses

7. More thoughts inspired by the Logo and Scheme discussion

8. to CS: or not to CS: in F-PC assembler

9. Scheme implemented on top of Forth

10. Scheme implemented in forth or RPL

11. Anyone implemented Dylan in Scheme?

12. implementing scheme

 

 
Powered by phpBB® Forum Software