Re: Observer pattern limitations

On 12 Jul 2006 03:01:48 -0700, David Barrett-Lennard wrote:

Dmitry A. Kazakov wrote:

These are independent issues. You refer to a notification propagation. Time
stamping is for state reconstruction. Surely you could use it to
reconstruct state of "dirtiness", if you wanted.

Ok. I have seen designs use a "change count" which is essentially
a logical time stamp.

Yes, though sequence numbers are incoherent. On the other side time stamps
require a more elaborated infrastructure, especially in distributed
systems.

As for graph closures, I don't think it is a good idea to evaluate them
each time, if you have a deep graph.

Huh? Are you talking about transitive closure of the graph?

Dependencies are transitive, so a container of observers is an observer.

You can't always avoid the need for caching, and the need to know when
caches are dirty. Furthermore, some problems have complex dependency
graphs that can't be abstracted away.

I pack them in a tightly coupled object like a record variable above. That
would cut all dependencies.

I have been building software for the last few years that allows the
end user to assemble complex persistent components like leggo, and use
formulae in various ways to wire them up in interesting ways. In that
domain I have to deal with complex dependency graphs that form at run
time and can't be abstracted away.

Interestingly, but this is what I am doing too. I have a persistency layer
for AI objects (classifiers, features, training sets etc).

But this is rather a simple case, therefore it works as Lego. It is easy
because:

1. The is no circular dependencies
2. It is synchronous (you store/restore all involved objects at once)
3. It is immutable, the action of storing does not change the object.

It is an empiric principle, however maybe it could be supported by
analogies in set theory. My observation is whenever you try to make objects
which, for example, delete themselves, you end up with a mess. Same with
detaching. You want to be "functional" using "forall x in X P(x)" pattern,
and at the same time you break it by changing the quantifier (the set X)
from P. It is fundamentally inconsistent, so the mess.

I now look at the problem of cache management across the program from a
global, graph theoretic perspective, because a local view as suggested
by the observer pattern doesn't seem to work well in practice.

This reminds me of the problem of detecting garbage which is (often)
nicely handled by a global tracing GC, whereas local approaches such as
reference counting are difficult and painful to get right, and often at
odds with writing reusable components. I agree that "real time"
issues remain a problem with graph theoretic approaches.

No, as with observer, GC does not solve this problem. The perspective must
be not "graph theoretic." I should be *just* theoretic. The problem is that
you don't have formally specified the requirements on what we call cache,
notification, dependency etc. Once you had, you would quickly discover that
the requirements are contradictory. Then the actual work begins: to remove
contradictions from there.

If notification only propagates dirtiness eagerly through the
dependency graph then we eliminate all the problems I have discussed.
This includes the question of when to update the dependency graph
topology - because that happens in a separate phase when caches are
lazily evaluated.

You just have separated event and reaction (which are united in the
observer pattern). This solves some problems by bringing others. For
example, you might lose events. Sometimes it is acceptable (for state
variables), sometimes it is not (control variables).

However, I'm comparing it to the idea of only propagating dirtiness
during state change notifications. That eliminates the problem
completely.

It brings other problems, because events and reactions become decoupled.

Handle = smart pointer.

No, that won't solve the problem when you have pre-written components
in a third party library and you need to add the objects that represent
the "wiring". What deletes the wiring?

GC. You have a handle to it. When the last handle goes out of scope, that
kills the wire. The thing that creates a wire is responsible to hold its
handle by itself or to pass it to a container serving as the scope. In my
component library weak references are collected objects.

Either subjects need to store strong references to the observers, or
else observers need a special notification for when the subject is
being destroyed. Neither of these approaches is done in typical
implementations of the observer pattern.

No, you mix things here. When objects can be observers, then there is no
need in any wiring you tell B: "take x from A." When they are not, then the
wire is the observer which tells B: "here is an x (from A), enjoy." In any
case the observer is a weak reference that gets a notification upon
finalization of A. This notification does not kill it directly. That's the
principle of "non-self-subject."

Race condition is in c. When notification about a arrives before one of b,
c thinks that b's cache is OK, which is wrong. Note that even when c does
not cache anything, there is always some hidden cache present. When c reads
a, somebody else might be busy with changing a or b. You must lock
something, somewhere to kill transition processes.

This is a multi-threading issue. I was only addressing the problem of
cache management for a single thread.

No. In all scenarios the problem persist. Asynchronous propagation of
events and notification merely means that the order of execution of
reactions to the events might be wrong. In general, threading is irrelevant
to the problem. A separation of events and reactions makes possible a
brute-force synchronization: all events - all reactions - all events ..
This enforces some order, but it does not guaranty that it is the required
order. But for all, it is very ugly and very slow.

I think I have more of a functional programming perspective on this
than you. I try to promote the idea that the order of calculation is
driven naturally by functional dependencies. This is a powerful
approach to help write code that is both correct and very efficient.

Hmm, that's the observer pattern is all about: triggering things =
determining the order.

I'm talking about examples like "c := a.get() + b.get()". The
act of executing that code causes a and b to be calculated *before* c
is calculated. Lazy evaluation is great for solving most order of
calculation problems.

It allows enforcing order on operands, but that does not solve problem when
get() has side effects. You will also have aliasing problem and one of
ordering operands of "+".

Note also that when there is no side effects, there is also no need to have
it lazy. Marshal values of a and b to c, that's it. Lazy can be great for
dealing with side-effects, but it does not eliminate the ordering problem.
It is a tool.

The problem space has to be analysed to find a solution of the *narrower*
problem.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
.

Relevant Pages

  • Re: Observer pattern limitations
    ... dependency graph may depend on thousands of inputs, ... complete recurse of the graph is needed just to tell whether it is ... You refer to a notification propagation. ... and an observer decides that it wants to synchronously detach. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... dependency graph may depend on thousands of inputs, ... complete recurse of the graph is needed just to tell whether it is ... You refer to a notification propagation. ... and an observer decides that it wants to synchronously detach. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... You refer to a notification propagation. ... so a container of observers is an observer. ... some problems have complex dependency ... Therefore the dependency graph has no need to persist. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... objects to need to cache the results of calculations. ... problems that exist whether Observer is used or not. ... What those other objects do in response to that notification is part of ... a different problem solution in the context where Observer is used. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... objects to need to cache the results of calculations. ... problems that exist whether Observer is used or not. ... a different problem solution in the context where Observer is used. ... Observer may be useful to provide the notification. ...
    (comp.object)