Saturday, August 20, 2011

cmd hiccup and data dependency

Editing a control that invalidates the entire piece, say affects the amount of randomness in the start times of every note, winds up locking up the app for almost 2 seconds.  That shouldn't happen.  The performance should be forced in the background, and it should wait a second or so before starting anyway so that subsequent keystrokes can kill the rederive before it starts.  So I did the only thing I could think of and put in prints with timing info to find where the hiccup is.  This is in the IO loop, so that's possible.  Then I do the binary search thing, edit, compile, check, etc.  I'm compiling because seems like a hassle to set up a test right now that reproduces the entire cycle but maybe I should have.

Turns out I'm checking for damage to in the resulting performance, and that field is marked strict along with the others, so even though the edit damage is accumulated independently of the performance results in that data structure, the strictness annotations force it all.  I think?  In any case, removing the !s causes the delay to disappear from that spot and reappear later on.  Now it's the *next* msg that hangs, in this case the key up from the key that invalidated the score.  That doesn't make any sense, a key up should be cheap.

More prints and binary search.  And now the trail leads into pure code.  The lag shows up on forcing the result of the second cmd.  So clearly cmds are doing something to make the eventual status depend on something inside the state which in turn is depending on some non-lazy part of the performance.  How am I supposed to know what any of those things in the chain are?  Forcing a particular value can result in an unknown amount of computation, and you can't tell from looking at the value what it is and who created it.

It's at times like these that I'm ambivalent about the value of laziness.

You also can't constrain the dependency links statically, they arise implicitly through data dependence.  Actually there are ways, but I understand them only poorly.  For example, if you accumulate a list by passing from function to function but only appending, even getting the head will force the entire computation because there's no static proof that you didn't prepend an element somewhere.  But if you accumulate the list in a such a way that it's impossible to prepend an element, say by not passing the head to subsequent functions, or using a Writer where the mappend is an append, the dependency is broken.  By encoding the accumulation pattern into the structure of the computation you not only get better laziness but also a clearer expresion of how a value will be accumulated.  I did the same thing when instead of collecting results by passing the accumulating value around in a StateT, I put the value into Monoid, passed mempty to subcomputations, and merged their results back into the StateT.  I feel like this was an important insight, but it came late, and I've never seen it discussed specifically.

Monads are another way to statically constrain data dependency.  I feel like there should be a more organized way to think about this, or at least a set of guidelines and "design patterns" based around controlling data dependency.  It's important, right?  Especially in functional programming...  in imperative programming every single line has an explicit dependence on the previous line which does make things clear but solves the problem only in the sense that amputation simplifies health care.

Since reduction of data dependency not only allows laziness but also allows parallelism, there must be a fair weight of research bearing down on the problem.  It's hopeful for the future of laziness I suppose.  Perhaps future generations will have more principled controlled ways to use it.

Back to the cmd hiccup, I'm now thinking that if the data dependency is so delicate and hard to find, what I really need a stronger wall so that cmd code cannot, just by looking at something, depend on score derivation, with the necessary exception of playing.  Relying on laziness in a "large scale" way is too error-prone without some constraints.  I suppose this is analogous to the problem of lazy IO and its solution via the constraints monads can provide.

But it's not just playing... there are a fair number of ways cmds want to use the deriver output.  Maybe it's not so bad as it seems.  The only thing that can incur a dependence on the performance is the result of the performance itself.  Hardcode lookup_performance to return Nothing and the problem is gone.  And that's the key to it all.  I've noticed this reaction to problems in pure code.  My first reaction is disillusionment and dismay, that the problem is intractable and I'll never make progress if I don't even know what steps to take.  But after that passes and I apply some higher level reasoning to the problem, it turns out to not be as intractable as I imagined.  Debugging functional code requires a greater ability to step away from the minutia and think through the problem more abstractly.

After much tracing of things that call things that call things, it becomes apparent.  A while back I added a nifty feature where instruments can bring cmds into scope.  Initially it's so drum-like instruments can bind keys to special event creation, but there are probably other uses as well.  So you have to know the current instrument in scope.  But you can't tell that just by looking at track title, since the instrument may be inherited from the environment.  In fact, a given block may have different instruments when called from different places.  So I had a bright idea and added another feature where the deriver output includes the values of the environment at each track.  Well, the environment depends on, guess what, the results of derivation.  And it's not very lazy.

So the options seem to be:
  1. Abandon the idea of per-instrument cmds.  I don't think I want to do this, input flexibility is too valuable.
  2. Abandon the idea of getting the instrument from the derivation, go back to parsing the track title or something.  I don't like this much because I don't want cmds to have a separate way of understanding the score than the deriver.  This is analogous to an IDE that uses an ad-hoc parser and analysis to come to possibly different conclusions than the compiler.  Of course some of that is unavoidable, e.g. incomplete expressions, but I'd like to minimize it.  So then the other way to go is reduce the expressiveness of the language so that the ad-hoc analysis is easy.  I don't think I really need arbitrary expressions being able to set the instrument.  But this generality also makes the language simpler, it's simpler that instrument is just a dynamic binding like any other.  Is there some way I can design a language which is both constrained enough to make textual analysis require minimal context, but also general and simple and not a SQL-ish mess of ad-hoc syntax and lack of abstraction?  I feel like the two goals are in conflict, and it would take someone smarter than me to resolve them simultaneously.
  3. Try to avoid fetching track cmds unless I need them.  For example, if track cmds can declare they are never interested in a key up, I can skip all the work of figuring out what they are.  I don't think this works because firstly that just puts off the work until a key comes along that does apply, and secondly because the scope of interest is only going to expand as there are more cmds and more complicated ones.  In fact, track cmds already want a key up if they want to emit a MIDI NoteOff for it.  And it's complicated.  Cmd dispatch doesn't need to get any more complicated than it already is.
  4. Make derivation lazy enough that looking up the istrument of a track derives very little.  Technically this should be possible and is appealing because the lazier I can make derivation the better.  Maybe I can tweak the mappend for the TrackEnviron such that it doesn't force more than necessary.  I think this is a good idea in general, but it still seems fragile.  Depend on something else, or depend on too much, and I'm back to debugging a hiccup.
  5. Delay the replacement of the performance until it's been forced enough to not cause a delay.  This would keep anyone from touching the new performance until it's "safe" to do so.  I think I can do this by only replacing the last performance when the new one has had several important fields forced.  This means the evaluation thread has to actually ship the performance back to the responder thread at some point rather than replacing it synchronously and relying on laziness, but I already have a path to communicate evaluation status, so this shouldn't add undue complexity.
I think #5 is the winner.  But I should try #4 and include TrackEnviron in the laziness tests.

#5 took about 20m to implement, about a 10th of the time it took to figure out.  It means that I lose the nice behaviour where a play will immediately start forcing the derivation even if the evaluator is still waiting to see if there will be more input.  Now play will simply start the old version.  You have to wait for the evaluator's cooldown second to hear the new version.  Fortunately a bit of the UI changes color to indicate when that's happening, but it's a bit annoying.  But the big win is that the UI interaction is now gloriously lag-free.  I would need some further hackery and thread communication if I want play to cancel the cooldown and tell the evaluator to get a move on.  #5 cancelled out some of the nice effects of laziness; the implicit thread communication provided by the runtime where whoever gets to the lazy thunk first triggers its evaluation was nice.  It made play work just how I wanted with no additional work.  But like so many implicit things it's so powerful its dangerous.  How do you control it without losing the benefits?

On a whim a while back I watched "The Thin Red Line" on netflix.  The music has a series of duets, which for some reason remind me of Shaker music, with parallel fifths and fourths, harmony yielding suddenly to unison.  Then there are long melodies in a lilting French kind of style.  Some parts are stronger than others, but at its best it achieves a kind of sparse melancholy that is free from the film in the way so many things in that film are free of each other.

It's so hard to see how what I'm doing, the insufficient laziness causing hangs, incorrect redraws and fussy little bugs from typos, it's hard to see how it relates to what I really want to do.  Sometimes listening to music is not inspiring but dispiriting.

Isn't it arrogant, or at least stubborn of me to insist on doing everything my own way?  Getting stuck in toolsmithing is a classic trap.  And how do I know in advance if the tools are usable?  Ideally you are using the tools as you're developing them and I'm doing that a little, but in music it's much harder to work with incomplete tools.  You have to get an instrument into a more or less playable state before you can begin to make judgements of its musicality.  And software is such a slow way to build an instrument.

No comments:

Post a Comment