[cells-devel] Pentagon of Death [was Re: Vancouver Lisp Users Group meeting for October 2008 - The Nature of Order]

[Kenny]

puchacz wrote:
> On Oct 4, 11:03 pm, Kenny <kentil... at gmail.com> wrote:
> 
>>Patrick May wrote:
>>
>>>Kenny <kentil... at gmail.com> writes:
>>
>>>>Patrick May wrote:
>>
>>>>>Kenny <kentil... at gmail.com> writes:
>>
>>>>>>I wonder if Flash can keep up with compiled JS. You don't mind the
>>>>>>Flash requirement? I realize it is ubiquitous enough, but still.
>>
>>>>>    It loads relatively slowly, but once it's loaded it's as fast
>>>>>as a desktop app (not surprisingly).  I selected it despite the
>>>>>Flash requirement because it provided a nice grid control and the
>>>>>chart displays I needed.
>>
>>>>JS frameworks don't have those?
>>
>>>     Some have one, some have the others, some have some other bits I
>>>wanted to use.  TIBCO's GI was actually my first choice, but there was
>>>a bug in Safari that prevented me from using it.
>>
>>I was just going to say one big win would be insulation from browser
>>variability.
>>
>>
>>
>>
>>>>Or was it more like you had zero reason to avoid Flash (and maybe
>>>>already knew it) so there was no reason to hassle with less polished
>>>>tools? I suppose you also had the means to acquire the tools.
>>
>>>     Actually, I felt rather dirty using Flash.  And not in that good,
>>>tingly way.
>>
>>:)
>>
>>
>>
>>
>>>     Aside from the chart widgets, the tools are free (as in beer).
>>
>>What's your IDE, Eclipse?
>>
>>
>>
>>
>>>[ . . . ]
>>
>>>>No Cells? Are you mad? For a GUI? Celtk and Cells-Gtk (and soon
>>>>Xello) will show you how to drive an existing framework with Cells.
>>
>>>     This application is a trading system.  If Cells is fast enough,
>>>it might be a good choice for the backend.  Can I get a response in 10
>>>milliseconds when an order book changes?
>>
>>10ms is an eternity! I know, I have a feel for that having done
>>RoboCells in which we handled realtime inputs spaced at 100ms.
>>
>>Otherwise, not sure what you are asking. Naturally a very interesting
>>question is how long does the functional computation take. But I will
>>presume that is in order and what you are asking is if Cells is a pig.
>>No. (see "RoboCells"). In fact, Cells helps a bit by magically
>>discerning exactly what needs to be updated when X changes. I tried to
>>tell the walking dead at ECLM 2008 that Cells is a library about change.
>>  Practically, this means one has complete control over change,
>>including the aforementioned optimization of changing only those things
>>that need to change, but also being able to surgically control "oh, I do
>>not need to update /that/ every 10ms, I can do it every other unless of
>>courese Y changes by 42%". Stuff like that.
>>
>>Well, if js/html/css get on my nerves I'll take a look at Fex/MXML. Thx
>>for the lead.
>>
>>kt
> 
> 
> Hi,
> 
> Is Cells able to handle updates in a "diamond scenario"?
> 
> "a": external input
> "b": driven from "a"
> "c": driven from "a"
> "d": driven from "b" and "c"
> 
> As "d" is driven indirectly from a single input "a", and processing of
> "b" and "c" may take different time, it is important to wait with
> updating of "d" until both "b" and "c" is finished. Otherwise, "d" may
> publish its value twice, and the first value would be totally
> incorrect, like a huge spike in the series.


PWUAHAHAHAHAHHAHAA! I thought I invented that. Philip Eby gave it a more 
dramatic name when I explained it to him while justifying the Cells 
mechanism -- the Pentagon of Death, I think it was. Why Pentagon aka 5?

I settled on a tougher case in which, eg, d did not depend directly on 
c, but did so indirectly thru an intermediary depencency c2 which 
depended on c.  Why does this matter? If a changes c needs to be 
recalculated, period, no question. But C might recompute and come up 
with the same value, say if A changes from 3 to 6 and C is (mod A 3). In 
that case we cannot know C2 is obsolete until C runs, and this defeats 
some algorithms (assuming we have a rule that says "never calculate 
unecessarily").

I also made it nastier in that...well, it gets complicated, but Cells 
tracks dynamic dependencies, not lexical, so I cannot just inspect the 
dependency graph as it stands -- the change to 'a' might make 'd' go 
after 'c2' for the first time ever in 'd's life.

Philip struggled mightily to find a better way than the Cells algorithm, 
but in the end the Pentagon of Death beat every alternative.

Thx for the heads up on the prior art.

cheers,ken