Re: Nested context properties -- an implementation sketch

[David Kastrup]

David Kastrup <address@hidden> writes:

> I don't think that anything close to a sensible implementation can be
> significantly simpler or significantly more efficient.  There are some
> things that may be nicer to do in C, and some shortcuts that may be
> taken.  But as a functional sketch, this should more or less be what it
> takes.
>
> I don't think we can get this much cheaper.

> ;; Structure of source: a list exactly as long as the list reaching
> ;; from cache inclusively to tail exclusively, and associated 1:1 with
> ;; the respective list elements.  Each element of source has the
> ;; following parts:
> ;;   car   ->  records whether this property was entered with \once or
> ;;             not.
> ;;   cdr   ->  length of nested property path.  After this many cdar
> ;;             calls on the property alist, you reach the set value of
> ;;             the nested property.  All other content of the property
> ;;             alist entry is taken from other alist entries.

Well David,

I should not want to let you implement this in the current form without
any feedback from the developer list.  When you try converting your
approach into C code, you'll likely notice a few problems where
performance might be suboptimal.

The one thing to note is that fold-right is an inefficient function to
use, and because of the guile implementation, greatly more so if you use
it with more than a single list.  It is still O(n), but with a factor of
ugliness that warrants some polishing up, the simplest polish-up
possibly just consisting in hard-coding the case for 2 lists instead of
using general code.

But that still results in complex code and a recursion filling up the
stack before actually starting any work working the stack down to empty
again.

So let us see what you are using fold-right for.  Its main purpose
appears to be for updating a context's personal part of the property
list in reverse, back to front.  And it is only in this context that you
are actually using "source".  So basically, there seems to be little
incentive not to keep source in reversed form in the first place.

The second point of interest is seeing what you are using source for.

One thing "source" is used for is keeping score of "once".  We need that
in order to clear all "\once\override" commands at the end of a time
step.  And we need it in order to check whether a "[\once]\revert"
applies to some property or not.  But if you make this list sparse (as
in storing only the elements with once being #t), it should work just
fine.  How to find out you are processing a given list element of the
alist?  Well, we are consing the top level alist entries ourselves, so
their identity is established by eq if we don't change the entries.  You
need to check, however, whether keeping the eq-identity of an entry is
feasible when it partly consists of copied sibling properties from
somewhere else, and those need to be adapted because of new
override/reverts.

The other thing "source" keeps track of is the depth of nesting of each
override.  Making this sparse might not help all that much with regard
to efficiency: when we need to consult it, we already are in the process
of consing up a new spine, so we are already O(n).

The question is how to keep a balance between making the code reasonably
efficient as well as understandable, and thus, maintainable.  While
probably not all too many people are comfortable with that code area in
the current state, dealing with nested properties is going to make the
situation worse, and that should be kept in check as well as possible.

Perhaps you'd want some more opinions.

-- 
David Kastrup