Re: Nested context properties -- an implementation sketch
Am Sunday 14 August 2011, 17:31:11 schrieb David Kastrup: a) a revert will only cancel the last _matching_ override, and the match includes the complete specified property path, _and_ the prospective use of \once. \revert will not cancel \once\override and vice versa. b) At the end of a timestep, all \once\override are reverted. All non-\once overrides remain in effect and on the stack as if none of the \once\override had ever happened. That makes sense. Isn't this how it should have worked so far, too? I have no clear view about \set yet. It would seem to me that \unset should be equivalent to \revert, and \set should be equivalent to \revert+\override. This is a change of existing semantics and will likely require changes to some Lilypond scores. Which cases exactly do change? BTW, about \once\revert: Urs Liska's tutorial brought up a nice use of it. \voiceOne [notes...] \once \revert Stem #'direction [...] I.e. \voiceOne sets the direction of several grobs. If there is one note where you want one of the grobs return to the default setting, \once\revert is the best solution. Otherwise one would have to look up the default value in the IR, explicitlly override it and hope that the default will never change in the future (because then this will break completely). Cheers, Reinhold -- -- Reinhold Kainhofer, Vienna University of Technology, Austria email: reinh...@kainhofer.com, http://reinhold.kainhofer.com/ * Financial and Actuarial Mathematics, TU Wien, http://www.fam.tuwien.ac.at/ * Edition Kainhofer Music Publishing, http://www.edition-kainhofer.com/ * LilyPond music typesetting software, http://www.lilypond.org/ ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
Once again i'm reviving an old thread, but since i was involved in discussions with David before i disappeared, i'd like to give my feedback on this. 2011/8/14 David Kastrup d...@gnu.org: there are the proposed semantics. At least for the latter, I would want to get some sort of feedback. The semantics can be summarized as follows: a) a revert will only cancel the last _matching_ override, and the match includes the complete specified property path, _and_ the prospective use of \once. \revert will not cancel \once\override and vice versa. b) At the end of a timestep, all \once\override are reverted. All non-\once overrides remain in effect and on the stack as if none of the \once\override had ever happened. 2011/8/14 David Kastrup d...@gnu.org: There are likely two contentious changes. The first is related to nested properties: namely that the pairing of override/revert of a property x should be independent from override/revert of a nested property x.y. However, if overrides and reverts of x and x.y are not acting as if they were issued independently, and if overrides and reverts of x and x.z are not acting as if issued independently, then it gets quite hard to let overrides and reverts of x.y and x.z act as if they were issued independently. And that would make working with nested properties less straightforward in my opinion. The second is that \once\override will not mix with \override\revert. Currently \once\override ... \override will have the second \override active just for the current timestep, and revert to the previous value afterwards. \override ... \once \override ... \revert \revert will at first revert both overrides, but reinstate the state after the first override at the end of the timestep. If I understand the code correctly. LGTM. (sorry that i don't have anything more constructive to say) thanks for your work, David! Janek ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
Trevor Daniels t.dani...@treda.co.uk writes: David Kastrup wrote Sunday, August 14, 2011 8:11 PM Trevor Daniels t.dani...@treda.co.uk writes: I think we need to clarify a few things first. You wrote I have no clear view about \set yet. It would seem to me that \unset should be equivalent to \revert, and \set should be equivalent to \revert+\override. As we are contemplating a major change anyway, I'd prefer an equivalence in operation of \override, \once \override and \revert with \set, \once \set and \unset. Or is this infeasible? A sequence of \set \set \set would lead to stack buildup. That seems contrary to the spirit of the command name. On the other hand, a sequence of \set \unset will, under my proposal which is pretty much the current semantics, cancel a previous override, while a sequence \override \set \set \set \revert will be neutral, all-in-all. Now I am confused. Are you saying that \set will operate on grob properties rather than or in addition to operating on context properties? That would be a major change! I am talking about context properties exclusively. grob properties are basically just copies of context properties at a certain point of time (the initial, immutable grob properties at least, and the mutable being per-grob only anyway and not subject to context scoping), and thus are not concerned with all the scoping mess as far as I can tell, nor with overrides and reverts and once. They just take a snapshot of the context property when created, and work from there. As far as I understand. Which may not be all that far since I get my knowledge from hearsay and from analyzing the code bottom-up (and not having reached the top yet). -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
David Kastrup d...@gnu.org 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 ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
Well David, I should not want to let you implement this in the current form without any feedback from the developer list. [...] :-) Unfortunately, I have nothing useful to say. Werner ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
Werner LEMBERG w...@gnu.org writes: Well David, I should not want to let you implement this in the current form without any feedback from the developer list. [...] :-) Unfortunately, I have nothing useful to say. Well, there is the code (obviously bound to be streamlined before implementation) and there are the proposed semantics. At least for the latter, I would want to get some sort of feedback. The semantics can be summarized as follows: a) a revert will only cancel the last _matching_ override, and the match includes the complete specified property path, _and_ the prospective use of \once. \revert will not cancel \once\override and vice versa. b) At the end of a timestep, all \once\override are reverted. All non-\once overrides remain in effect and on the stack as if none of the \once\override had ever happened. I have no clear view about \set yet. It would seem to me that \unset should be equivalent to \revert, and \set should be equivalent to \revert+\override. I am pretty sure that any less strict 1:1 matching of reverts and overrides will cause surprises to users that are really hard to track down and explain. This is a change of existing semantics and will likely require changes to some Lilypond scores. I should be quite surprised if such changes would not make the intent of the writer easier to follow and maintain, but they would be changes nevertheless. Once I rewrite the property code in C, getting negative feedback about the semantics afterwards will be a major pain. So I made a toy implementation (it is already suffering from too much premature optimization for a toy, but is still more or less readable) in Scheme. The version in C will be less readable, but deliver the same results. The Scheme version was likely overkill to do, but whether or not somebody actually looks at it, it helped for focussing on the needed data structures. So from those not interested in the code (long as it works(TM)), I'd be at least interested in hearing whether they would be ok with _what_ I propose it should be doing, never mind _how_ it does it. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
On Sun, Aug 14, 2011 at 05:31:11PM +0200, David Kastrup wrote: Werner LEMBERG w...@gnu.org writes: Unfortunately, I have nothing useful to say. Well, there is the code (obviously bound to be streamlined before implementation) and there are the proposed semantics. At least for the latter, I would want to get some sort of feedback. I agree. :( The semantics can be summarized as follows: Those look fine to me. Once I rewrite the property code in C, getting negative feedback about the semantics afterwards will be a major pain. So I made a toy implementation (it is already suffering from too much premature optimization for a toy, but is still more or less readable) in Scheme. If you really want to poke the hornet's nest, and if the scheme implementation can be used for any arbitrary lilypond file (i.e. just by adding an \include new-overrides.ly to the top), then we could ask on the lilypond-user mailing list. Since we'll be having a release candidate as soon as Mike fixes his python 2.4 problem in output-distance.py, I'd ask you to wait until 2.16 is out before pushing this change. That's the only real feedback I can give, sorry. Cheers, - Graham ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
Graham Percival gra...@percival-music.ca writes: On Sun, Aug 14, 2011 at 05:31:11PM +0200, David Kastrup wrote: Werner LEMBERG w...@gnu.org writes: Unfortunately, I have nothing useful to say. Well, there is the code (obviously bound to be streamlined before implementation) and there are the proposed semantics. At least for the latter, I would want to get some sort of feedback. I agree. :( The semantics can be summarized as follows: Those look fine to me. There are likely two contentious changes. The first is related to nested properties: namely that the pairing of override/revert of a property x should be independent from override/revert of a nested property x.y. However, if overrides and reverts of x and x.y are not acting as if they were issued independently, and if overrides and reverts of x and x.z are not acting as if issued independently, then it gets quite hard to let overrides and reverts of x.y and x.z act as if they were issued independently. And that would make working with nested properties less straightforward in my opinion. The second is that \once\override will not mix with \override\revert. Currently \once\override ... \override will have the second \override active just for the current timestep, and revert to the previous value afterwards. \override ... \once \override ... \revert \revert will at first revert both overrides, but reinstate the state after the first override at the end of the timestep. If I understand the code correctly. I prefer to have behavior corresponding to simple well-defined rules rather than implementation artifacts. Even if it means that the implementation is harder to write. Once I rewrite the property code in C, getting negative feedback about the semantics afterwards will be a major pain. So I made a toy implementation (it is already suffering from too much premature optimization for a toy, but is still more or less readable) in Scheme. If you really want to poke the hornet's nest, and if the scheme implementation can be used for any arbitrary lilypond file (i.e. just by adding an \include new-overrides.ly to the top), then we could ask on the lilypond-user mailing list. Since a number of other Context internals in addition to the grob property list manipulators themselves are written in C++, such a replacement is unfortunately not feasible to do without recompilation as far as I can see. Since we'll be having a release candidate as soon as Mike fixes his python 2.4 problem in output-distance.py, I'd ask you to wait until 2.16 is out before pushing this change. That's the only real feedback I can give, sorry. I'll not likely be that fast, anyway. On the other hand, once the stuff works for me, it seems reasonable to get it out for massive testing. So it seems a bit awkward that we don't have a release branch separate from master. Since the change of semantics would not be limited to nested properties, it does not make sense to rush this in under the pretense of it being a mere bug fix, however. It is more like fixing a design flaw. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
Trevor Daniels t.dani...@treda.co.uk writes: David I think we need to clarify a few things first. You wrote The semantics can be summarized as follows: a) a revert will only cancel the last _matching_ override, and the match includes the complete specified property path, _and_ the prospective use of \once. \revert will not cancel \once\override and vice versa. b) At the end of a timestep, all \once\override are reverted. All non-\once overrides remain in effect and on the stack as if none of the \once\override had ever happened. Will the order of \override and \once \overide within the same timestep for the same property matter, or does the \once \override always take precedence within its timestep? The order matters with regard to which override determines the active state of a property (always the last override). It does not matter for matching reverts to overrides. I'm not clear about stacking. Will \override be equivalent to push and \revert to pop, with the top value left on the stack being effective? Or is there no stack? There is a stack, and the last active override determines the value. If an override is just for a subproperty, it determines the value just for that subproperty (and its respective subsubproperties). The exact matching is done for matching reverts (which may for that reason happen below the stack top) to overrides, not for reading out properties. I have no clear view about \set yet. It would seem to me that \unset should be equivalent to \revert, and \set should be equivalent to \revert+\override. As we are contemplating a major change anyway, I'd prefer an equivalence in operation of \override, \once \override and \revert with \set, \once \set and \unset. Or is this infeasible? A sequence of \set \set \set would lead to stack buildup. That seems contrary to the spirit of the command name. On the other hand, a sequence of \set \unset will, under my proposal which is pretty much the current semantics, cancel a previous override, while a sequence \override \set \set \set \revert will be neutral, all-in-all. I don't particularly like all the semantics, but they are reasonably comprehensible and useful. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Nested context properties -- an implementation sketch
David Kastrup wrote Sunday, August 14, 2011 8:11 PM Trevor Daniels t.dani...@treda.co.uk writes: I think we need to clarify a few things first. You wrote I have no clear view about \set yet. It would seem to me that \unset should be equivalent to \revert, and \set should be equivalent to \revert+\override. As we are contemplating a major change anyway, I'd prefer an equivalence in operation of \override, \once \override and \revert with \set, \once \set and \unset. Or is this infeasible? A sequence of \set \set \set would lead to stack buildup. That seems contrary to the spirit of the command name. On the other hand, a sequence of \set \unset will, under my proposal which is pretty much the current semantics, cancel a previous override, while a sequence \override \set \set \set \revert will be neutral, all-in-all. Now I am confused. Are you saying that \set will operate on grob properties rather than or in addition to operating on context properties? That would be a major change! Trevor - No virus found in this message. Checked by AVG - www.avg.com Version: 10.0.1392 / Virus Database: 1520/3833 - Release Date: 08/14/11 ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Nested context properties -- an implementation sketch
Ok, so I have been trying to get a hold on the nested context property thing. The main issue is getting a grip of how to update stuff on removal. With regard to nested context properties, an update further down in the nested property alist can have repercussions further up if some parts of the lower hierarchies have been used in setting up a nested context property alist further up in the hierarchy. There are basically two approaches I see possible for dealing with this: a) when removing a higher-level property further down in the stack, replace its conses, possibly consulted further up, with copies of the next property lower down in the stack. But if I have set a property 'x with a value ((y . ((z . 4, then the property handler has no business overwriting the internals of my property just because he copied them for filling in the blanks when setting a nested property (x y c). b) update stuff further up the stack. I've implemented this as Scheme for experimenting with, probably with bugs remaining. Other key elements: A revert will _only_ match an override with the _same_ signature, the signature consisting of the state of the \once flag as well as the full property path. This makes sure that unexpected pairings of reverts with overrides will be kept to a minimum. \once\override will _not_ register the old value of the setting. Instead, every not-yet cancelled \once will get cancelled at the end of the time step. 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. ;; Plan: context contains, in contrast to the current Lilypond ;; implementation, an additional source list for context overrides ;; corresponding to the cache list member by member. The source list ;; stops with the last override in the context and does not continue ;; into parenting contexts. ;; ;; In this file, this list is titled source and the actual override ;; list is titled cache. source is not really the most accurate ;; description since it merely contains _additional_ data. ;; ;; Structure of context (only changed destructively). ;; car - parenting context or #f ;; cadr - source ;; cddr - list head for contexts as currently existing: ;; caddr - cache, the property list for this context including ;; parents ;; cdddr - tail. The cache is only valid if the cache of the ;; parent is valid and eq to this context's tail. ;; ;; 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. ;; ;; The cache is never changed destructively, instead new copies are ;; created for changes. Any parts of the cache that are eq to some ;; part of the structure at an arbitrary different point of time, are ;; for this reason unchanged. (use-modules (ice-9 optargs) (srfi srfi-1) (srfi srfi-2)) (use-modules (ice-9 debug)) (define* (make-context #:optional parent) (cons parent (cons '() (cons '() (if parent (caddr parent) '()) (define (updatecache source oldcache newcache) updatecache should be called with (fold-right updatecache cachetail oldcachelist sourcelist) cachetail contains the new tail for the cache which has lost sync with the previous cache. (let loop ((depth (cdr source)) (oldcache oldcache) (newcache newcache)) (if (zero? depth) ;; entry is the original data entry in this list without copied ;; material so we just cons it up and continue. (cons oldcache newcache) ;; Now we may need to update a nested property override. This ;; is tricky. The property (car oldcache)'s nested property ;; list (cdr oldcache) starts with an override in the first ;; position (cadr oldcache) followed by the top level ;; original nested list (cddr oldcache). If the original for ;; the copied nested list has remained eq, the whole entry can ;; stay the way it is. If we had a sibling override, we need ;; not copy the whole depth of the recursion but only up to ;; the level where the chain is again intact. So we can solve ;; this problem in a recursive manner. Don't even dream of ;; using ly:assoc-get here: strict eq is vital for getting ;; this right.