Almost, but not quite: C++ STL in LilyPond

[David Kastrup]

Hi,

I am currently digging back and forth regarding implementation of our
Smobs (Scheme objects) and garbage collection and STL, and I think I am
converging on the realisation that we'll have to end up duplicating
those parts of STL that we are using.

One reason is that we want to get rid of finalisers particularly in
connection with the Boehm GC.  Finalisers are called when garbage is
collected, the collection of garbage is typically indicative of the
expected lifetime of our objects (there are a few that might be
unambiguously dead before), and thus it will cause C++ destructors to be
called.  And those trigger, among other things, the deallocation of
memory resources, but we'd rather want the deallocation to be determined
by Scheme mechanisms and not have any resources in need of destruction
other than falling into oblivion.

Another point is the lack of reflection we have for getting a
description of STL nodes (like list nodes) for the sake of knowing which
elements may be allocated in what manner where.  It is conceivable that
Guile-2 will work tolerably just with the hand-waving knowledge "this
node may or may not contain pointers to other nodes somewhere" which
essentially is the information STL allocators can rely on but having to
rely on it does not seem like a good idea with regard to keeping things
well-collected.

I've tried to come up with a clever callback scheme where the first use
of a structure causes fake nodes to be created with a "Pointer" type
that actually calls back with its address to its caller that then
constructs a layout of SCM elements within its governed class.  However,
I have found no way to make this "parallel construction" where I could
then swap out this specific "Pointer" behavior for regular SCM.  Which
means that pointer/SCM juggling within the STL framework would always
involve some check (empty call or boolean variable) of whether we are
still in initialisation phase.  Not good.

The third reason is that STL allocators just have no knowledge about use
patterns and need to be able to allocate single SCM elements and
multiple SCM elements at request and keep track of them.  That is
particularly problematic since SCM allocations are principally
per-element and any multiple allocation needs to run through vectors and
similar.

And of course we'd want to make good use of what we have for generating
hash values etc in Scheme already.

So that means that I am going to reimplement some STL containers with
equal semantics (and hopefully also matching the "Container" definitions
so that at least container adaptors from the STL can make use of them)
and with more introspection into the Scheme-typical manners of
allocation and semantics.

In practical terms this means for other developers to avoid using or
introducing STL structures into Smobs.  Obviously, arrays and vectors
will have to get reimplemented in course of my plan, so there is no
point in avoiding them.  With regard to maps, ordered and unordered sets
and similar stuff, the strategy would be to vastly prefer any solution
that can be implemented in terms of Scheme functions.

To make this less painful, it is suggested that things like Scheme_hash
get reimplemented in a manner closely following the STL API so that we
can actually program in a C++ style (and encourage other contributors to
do so) without thinking too much.

I'd like to come up with an allocator/container programming model
comparatively similar to the STL one so that one could mostly steal the
implementations and "just" add the required Scheme awareness while
removing of destruction/deallocation tracking.

Using the actual code with trickery around it would be, of course, a lot
nicer.  But after a lot of deliberation and researching implementation
strategies, I am skeptical that making and keeping it work would be
robust and dependable (and efficient) enough to make this a really good
idea.

-- 
David Kastrup