Clean up code for sorting grob-properties.

WAS: Automatically sort alist grob-properties in IR.

David's logic has convinced me to retract the alist-sorting of the previous patch.  What remains is just a minor cleanup of the sorting code, which is hopefully now easier to understand.

http://code.google.com/p/lilypond/issues/detail?id=3932

[dak, 2014-05-28 00:00:59]

https://codereview.appspot.com/102760044/diff/1/scm/document-backend.scm
File scm/document-backend.scm (right):

https://codereview.appspot.com/102760044/diff/1/scm/document-backend.scm#newc...
scm/document-backend.scm:22: (apply eq? #t (map pair? x))))
(apply eq? #t (map pair? x)) is horribly contorted and subject to limitations in
argument list length.  Use (every pair? x) which has the advantage of
short-circuit evaluation.

Also, it seems like a stretch to assume that every list with pair members will
tolerate sorting.  You do not even restrict this to lists with symbols in the
car, and explicitly sort lists with non-symbols.

That seems like a bad idea.

https://codereview.appspot.com/102760044/diff/1/scm/lily-sort.scm
File scm/lily-sort.scm (right):

https://codereview.appspot.com/102760044/diff/1/scm/lily-sort.scm#newcode112
scm/lily-sort.scm:112: ((and (number? (car a)) (number? (car b)))
Can you point to any "alists" where the keys are numbers?  This seems rather
fishy to me.

[Mark Polesky, 2014-05-28 06:07:28]

https://codereview.appspot.com/102760044/diff/1/scm/document-backend.scm
File scm/document-backend.scm (right):

https://codereview.appspot.com/102760044/diff/1/scm/document-backend.scm#newc...
scm/document-backend.scm:22: (apply eq? #t (map pair? x))))
On 2014/05/28 00:00:58, dak wrote:
> (apply eq? #t (map pair? x)) is horribly contorted and subject
> to limitations in argument list length.  Use (every pair? x)
> which has the advantage of short-circuit evaluation.

Ah, that's the procedure I was looking for, thanks!  Sorry, I didn't know about
that one.

> Also, it seems like a stretch to assume that every list with
> pair members will tolerate sorting.

Do you mean that 
1) the order of keys in some alists may be significant?
or
2) my code might trigger a scheme error during sorting?

Regarding #1, I *am* assuming that key-order is irrelevant, but if that's
misguided, let me know.  Regarding #2, I thought my definition of `ly:alist<?'
covered that with the `else' clause:

(else
  (ly:string<? (object->string (car a))
               (object->string (car b))))

> You do not even restrict this to lists with symbols in the car
> and explicitly sort lists with non-symbols.
> That seems like a bad idea.

Not trying to be annoying (really), but why?

https://codereview.appspot.com/102760044/diff/1/scm/lily-sort.scm
File scm/lily-sort.scm (right):

https://codereview.appspot.com/102760044/diff/1/scm/lily-sort.scm#newcode112
scm/lily-sort.scm:112: ((and (number? (car a)) (number? (car b)))
On 2014/05/28 00:00:58, dak wrote:
> Can you point to any "alists" where the keys are numbers?  This seems rather
> fishy to me.

Accidental.glyph-name-alist:
'((0 . accidentals.natural)
  (-1/2 . accidentals.flat)
  (1/2 . accidentals.sharp)
  (1 . accidentals.doublesharp)
  (-1 . accidentals.flatflat)
  (3/4 . accidentals.sharp.slashslash.stemstemstem)
  (1/4 . accidentals.sharp.slashslash.stem)
  (-1/4 . accidentals.mirroredflat)
  (-3/4 . accidentals.mirroredflat.flat))

Finally, for what it's worth, here's the list of all alist grob-properties:
http://www.markpolesky.com/norobots/alist-grob-properties.txt

Thanks.
- Mark

[dak, 2014-05-28 07:37:48]

On 2014/05/28 06:07:28, Mark Polesky wrote:
> https://codereview.appspot.com/102760044/diff/1/scm/document-backend.scm
> File scm/document-backend.scm (right):
> 
>
https://codereview.appspot.com/102760044/diff/1/scm/document-backend.scm#newc...
> scm/document-backend.scm:22: (apply eq? #t (map pair? x))))
> On 2014/05/28 00:00:58, dak wrote:
> > (apply eq? #t (map pair? x)) is horribly contorted and subject
> > to limitations in argument list length.  Use (every pair? x)
> > which has the advantage of short-circuit evaluation.
> 
> Ah, that's the procedure I was looking for, thanks!  Sorry, I didn't know
about
> that one.
> 
> > Also, it seems like a stretch to assume that every list with
> > pair members will tolerate sorting.
> 
> Do you mean that 
> 1) the order of keys in some alists may be significant?

An alist is not an opaque data structure.  It is a list structure that is *used*
as an alist.  There are list structures that are not intended to be an alist
which perfectly well meet the definition of an alist.  For example,
'((lambda (a b c) (+ a (- b c))) (+ 3 4) (- 1 2) (/ 4 5))
is an alist with keys lambda, +, -, / and values ((a b c) (+ a (- b c))), (3 4),
(1 2) and (4 5), but you'll likely rather regard it as a quoted expression
evaluating to 26/5.

What you may be considering an alist is not necessarily one.

> > You do not even restrict this to lists with symbols in the car
> > and explicitly sort lists with non-symbols.
> > That seems like a bad idea.
> 
> Not trying to be annoying (really), but why?
> 
> https://codereview.appspot.com/102760044/diff/1/scm/lily-sort.scm
> File scm/lily-sort.scm (right):
> 
> https://codereview.appspot.com/102760044/diff/1/scm/lily-sort.scm#newcode112
> scm/lily-sort.scm:112: ((and (number? (car a)) (number? (car b)))
> On 2014/05/28 00:00:58, dak wrote:
> > Can you point to any "alists" where the keys are numbers?  This seems rather
> > fishy to me.
> 
> Accidental.glyph-name-alist:
> '((0 . accidentals.natural)
>   (-1/2 . accidentals.flat)
>   (1/2 . accidentals.sharp)
>   (1 . accidentals.doublesharp)
>   (-1 . accidentals.flatflat)
>   (3/4 . accidentals.sharp.slashslash.stemstemstem)
>   (1/4 . accidentals.sharp.slashslash.stem)
>   (-1/4 . accidentals.mirroredflat)
>   (-3/4 . accidentals.mirroredflat.flat))

This one is a good counterexample for a different reason.  You _are_ aware that
access to an alist element takes execution time proportional to its position in
the list?  There is a reason this kind of alist is sorted with the most
frequently accessed elements placed at the front.  So we don't want a different
order in execution, and if you try following the actions of the code while
looking at the IR (it's called "internals" for a reason), you'll get puzzled.

> Finally, for what it's worth, here's the list of all alist grob-properties:
> http://www.markpolesky.com/norobots/alist-grob-properties.txt

Containing MetronomeMark.round-up-exceptions which is not an alist.  More
seriously, when any properties are added later on that happen to match your
alist? test by accident, they'll get sorted, leading to quite confusing entries.

Also when debugging, it will be _totally_ confusing if the data does not
correspond with the actual content.  If you consider alphabetic sorting
important for whatever reason for some properties and the performance
characteristics of the use case don't speak against it, it makes more sense to
sort the actual definitions rather than make a diverging representation of the
properties in the IR.

[Mark Polesky, 2014-05-28 21:32:53]

David's logic has convinced me to retract the alist-sorting of the previous
patch.  What remains is just a minor cleanup of the sorting code, which is
hopefully now easier to understand.

Please review the new patch.

Thanks.
- Mark

[dak, 2014-05-28 21:46:55]

https://codereview.appspot.com/102760044/diff/90001/scm/document-backend.scm
File scm/document-backend.scm (right):

https://codereview.appspot.com/102760044/diff/90001/scm/document-backend.scm#...
scm/document-backend.scm:37: (set! all-grob-descriptions
Doing an assoc-set! here is inefficient inside of the loop.  Instead of
(for-each
   (lambda (grob-description)
      ...
      (set! all-grob-descriptions (assoc-set! ...

one should use
(set! all-grob-descriptions
  (map!
     (lambda (grob-description)
        ;replacement for grob description)
     all-grob-descriptions))

Changing the list when doing the iteration is not well-defined anyway.

[Mark Polesky, 2014-05-28 22:01:20]

On 2014/05/28 21:46:55, dak wrote:
> Doing an assoc-set! here is inefficient inside of the loop.  Instead of
> (for-each
>    (lambda (grob-description)
>       ...
>       (set! all-grob-descriptions (assoc-set! ...
> 
> one should use
> (set! all-grob-descriptions
>   (map!
>      (lambda (grob-description)
>         ;replacement for grob description)
>      all-grob-descriptions))

Like this?

[dak, 2014-05-29 06:01:42]

On 2014/05/28 22:01:20, Mark Polesky wrote:
> On 2014/05/28 21:46:55, dak wrote:
> > Doing an assoc-set! here is inefficient inside of the loop.  Instead of
> > (for-each
> >    (lambda (grob-description)
> >       ...
> >       (set! all-grob-descriptions (assoc-set! ...
> > 
> > one should use
> > (set! all-grob-descriptions
> >   (map!
> >      (lambda (grob-description)
> >         ;replacement for grob description)
> >      all-grob-descriptions))
> 
> Like this?

Yup, looks good.  Of course, it wasn't your fault in the first place, but it
would be strange not to use an opportunity for cleaning this up.  Actually
thinking about it, map! isn't the hottest idea since it modifies a constant in
the code (undefined behavior, might be flagged at one point of time).  But so do
all of the assoc-set! calls: this would have to be rewritten as a whole, and
while this is not done, one might as well use map! here.