Re: Observer pattern limitations

Leslie Sanford wrote:
"David Barrett-Lennard" wrote:
Frans Bouma wrote:

<snip>

I think people should take a step back and drop the whole 'pattern'
approach until they've figured out which problems they want to solve
in the first place. Too many developers design their software by
connecting patterns with patterns like lego blocks, but that's not
what they're all about.

I agree with that as well.

Well, I may be beating a dead horse at this point. But I was thinking
about David's X, Y, Z example in his original post as it applies to a
domain I'm interested in, sound synthesis for musical application (I've
talked a little about this elsethread), and wanted to share my thoughts
and hopefully get some feedback. I'm hoping that even though the example
I'm using is of personal interest, I can use it to shine light on some
problems whose solutions may have larger applicability.

Hardware synthesizers have been popular for decades, and as computers
have become more powerful, modeling hardware synthesizers in software
has become popular as well, just look at VST. The first thing that
strikes you when you look at the old analog synthesizers is how modular
many of them were. They were made up of components that could be plugged
into each other in countless ways. So when you begin thinking about
modeling synthesizers in software, it's natural to think in terms of
modeling components individually. It's also desirable to give them the
same pluggable interfaces.

This is good, but there is a problem: You're modeling an analog domain
in a digital one. Why is this a problem?

If you take the output of one hardware component, split it, and send one
branch to the input of a component and the other branch to the input of
another component, you can assume that the output of the original
component will arrive simultaneously at the input of both components
(actually, I'm not knowledgeable enough in physics to say this with
absolute certainty, but at least from a practical standpoint, it is
true).

-------------->

+---+
| B |-->
+---+
+---+ out |in
| A |-------+
+---+ |in
+---+
| C |-->
+---+

If you model the components in software as objects, the same cannot be
said. The output becomes descreet with the component sending its output
to the two input components in turn, one right after the other via an
Observer notification or direct communication or whatever.

In some situations this isn't a problem, but in other situations it is.
Certainly if you want to design a general framework for creating and
configuring synthesizer components, you have to find some way to make
your discreet signals behave more like continuous ones.

Here is an example that can cause a problem:

---------------->

+---+out
| B |--+
+---+ |
+---+ out |in | in+---+out
| A |-------+ +---| D |---->
+---+ |in | +---+
+---+ |
| C |--+
+---+out

Let's run through how this works:

A generates a signal, and it passes this signal along to B and C
synchronously. Let's say that B gets notified first. B receives the
signal and does whatever processing it needs on it and sends the
modified signal on to D. In turn, D does its thing and sends the results
to its output. The problem is that C has not gotten a chance to
contribute its part. It's only after D has finished that A finally gets
back control and can notify C. C then processes the signal and sends it
to D... So the output from D doesn't reflect the intent of the
algorithm.

This illustrates the problem of treating the signal discreetly, and it
is similiar to David's X, Y, Z problem, IMO.

So how can this be solved?

I described one way elsethread, and that is to treat each component as a
simple state machine. Each component knows how many components have been
connected to it. It doesn't process the signal until its received the
output from all of the components connected to its input. Once that
happens it fires and resets itself for the next sample. The protocol
here would have to be strict and well thought out. The signals from the
components could not arrive in an arbitrary way, e.g. you wouldn't want
one component sending out a signal twice in a row before all of the
other components have sent out their signals.

This is the "data flow" approach. There are generic data flow engines
around that do exactly what you say here. Some provide a GUI that lets
you insert components that contain input and output nodes, and the user
wires them up just like you're building an electronic circuit. This
approach is very natural in signal processing domains, such as sound or
image processing. WiT is an example of such a product for image
processing.

Attempts to make it work like a full-fledged programming language
haven't worked well. After using WiT for a while, I decided it was a
rather unproductive approach if you want to do anything complex.


Another possible way of solving this problem is to use David's approach.
When the output from D is retrieved, D in turn retrieves the output from
B and C. B and C retrieve the output from A. We have to make sure that
when B and C retrieve the output from A, A only performs its calculation
once instead of twice. So before the output of D is retrieved, the
components are marked as dirty. The dirtiness can be propagated through
the components as they change, or, as I was thinking, a seperate
algorithm could mark them instead, depends on the situation. At any
rate, when A performs its calculation in response to B or C, it marks
itself as clean. That way, when it is accessed a second time, it doesn't
perform the calculation again. B and C do their thing and pass it back
to D which then outputs its result.

Both approaches solve the same problem, IMO, and that is to turn
descreet events into continuous ones. Or another way of thinking about
it, it's as if we have an algorithm, and we're making sure that each
step of the algorithm completes before the next step is begun. We run
into a problem, as I see it, when the partial results of a step in an
algorithm are acted upon by the next step prematurely.


The approach I have described corresponds to an emphasis on the
functional programming perspective. I have spoken to Kazakov about
this.

The idea is to partition all state into independents versus dependents.
A dependent is a value that is conceptually the result of a *pure*
calculation on its inputs. The inputs can be independents, or other
dependents. In order for the calculated values to be well defined, it
is important that there are no cycles in the dependency graph. ie it
forms a DAG.

Saying that a dependent is the result of a pure calculation on its
inputs means there is a pure functional dependency, all the way back to
the independents. This can be expressed in code using "pure" functions
that have no side effects. This makes it very easy to reason about the
code - as is commonly discussed with functional programming languages.

It also allows for an important type of optimisation (called
sub-expression optimisation). Consider the expression

int x = foo(7) + foo(7) * foo(7);

If the compiler knows that foo() has no side effects, it is able to
only call it once, and instead do this...

int temp = foo(7);
int x = temp + temp * temp;

This optimisation relates to the idea of caching the results of
calculations in the dependency graph itself.

The whole point of keeping the calculated results for any length of
time is to allow a dependent to be *reused* - ie as an input to another
dependent.


Now I spoke about a separation between the independents and dependents.
Consider the following C++ class

class Demo
{
public:
Demo() : x(0), yIsDirty(true) {}

void setx(int newx)
{
x = newx;
yIsDirty = true;
}

int gety() const
{
if (yIsDirty) { y = x*x; yIsDirty = false; }
return y;
}

private:
int x;
mutable int y;
mutable bool yIsDirty;
};

This class contains an independent called x and a dependent called y.
A boolean is used to indicate whether y is stale (or dirty). Note the
use of the C++ 'mutable' keyword. This indicates that y is not part of
the "logical state" of the class. That makes it permissible to assign
it within the gety() method which has the 'const' qualifier.

As an ADT, the above Demo class is *indistinguishable* from this.

class Demo2
{
public:
Demo2() : x(0) {}
void setx(int newx) { x = newx; }
int gety() const { return x*x; }
private:
int x;
};

When I talk about the "formalism of OO", I'm talking about the
mathematical precision of statements like the one above. This more
than anything brings us closer to a formal basis for reasoning about
our OO software. This is where I accuse (even ridicule) the OO
community for lacking formalism.

Now this was a rather simple example of a dependency. More generally
we may have many independents and dependents spread around in lots of
different objects. The observer pattern is the standard way to ensure
that the dependents are automatically recalculated. However, as
described in the GoF book, it doesn't stipulate what you can and can't
do in a notification message. In particular it doesn't suggest that
you aren't allowed to synchronously recalculate the dependent (ie
observer) that was notified. It is not so much a matter of saying that
the observer pattern is flawed, it is more a case of saying that (as
described) it is particularly dangerous for the unwary.

I claim that a provably correct approach for general dependency graphs
is to simply propagate dirtiness eagerly through the dependency graph
whenever an independent is changed. This avoids the problems of dirty
reads, infinite recurses in the notifications, and the performance cost
of repeated eager recalculation of dependents.

It also allows for the pure functional dependency perspective to be
used, which is great because it makes it easy to reason about the code.
There is a sense in which the program is mathematically equivalent to
an abstract machine where there are no dependent variables at all, no
dirty flags and no state change notifications. This is an extremely
powerful theoretical tool.

On this basis, I deduce some important things. For example, I deduce
that only the independents should generally persist on disk, because
only they relate to the logical state. Therefore I deduce that the
ideology of orthogonal persistence is fundamentally flawed! The
dependency graph itself (ie the edges) should only form transiently,
and as a result of a small number of dependent nodes that are directly
associated with the "observable outputs" of the program - such as the
display.

Anyway IMO this whole way of thinking forms a useful basis for
reasoning about your signal processing application above.

Cheers,
David Barrett-Lennard

.

Relevant Pages

  • Re: DIY electronic interlocking suggestions?
    ... It would be fun to create the interlocking in electronics, ... sequence although the individual turnouts will only switch if there is no ... turnouts and signals should be dependent on signal aspects only, ... If you made turnouts dependent on other turnouts, ...
    (uk.rec.models.rail)
  • Re: How Do I Determine if a Specific Process Exists?
    ... > This is very much OS dependent. ... privilegies to send signals to unrelated processes. ... Sender/From address is bogus. ...
    (comp.unix.programmer)
  • Re: How Do I Determine if a Specific Process Exists?
    ... > This is very much OS dependent. ... privilegies to send signals to unrelated processes. ... Sender/From address is bogus. ...
    (comp.unix.questions)
  • Re: Calculation time
    ... calculation, and if the result doesn't change, all its dependent cells ... So to decrease the calculation time it is better to split the formula's up ... dependent upon cells that change. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Name - relative reference doesnt calculate
    ... dependent cells are changed. ... calculation behaviour seems to depend ... (Excel doesn't calculate automatically, ...
    (microsoft.public.excel.worksheet.functions)