Re: Observer pattern limitations


Dmitry A. Kazakov wrote:
On 10 Jul 2006 07:24:12 -0700, David Barrett-Lennard wrote:

Dmitry A. Kazakov wrote:
On 10 Jul 2006 02:31:26 -0700, David Barrett-Lennard wrote:

PROBLEM 1: Infinite recursion in notifications.

A simpler approach (which is also asynchronous) is for notification
handlers to simply mark their caches as dirty. The cache is
automatically recalculated when it is next requested.

The general approach for replicas is time stamping. Unfortunately it does
not help you in reconstruction of a coherent system state. You'll also need
a history window. But even this does not give you an ability to reconstruct
the state for any given time point. Also it becomes a nightmare for
bidirectional connections.

Time stamping can be quite inefficient. For example a dependent in the
dependency graph may depend (indirectly) on thousands of inputs, and a
complete recurse of the graph is needed just to tell whether it is
dirty (ie to perform all the time stamp comparisons). Within a
process, propagation of dirtiness through a dependency graph seems a
better choice.


IMO, the lesson to learn: go higher-level, use ADTs with behaviors
*specific* to the problem. There is no general solution at low level.

You'll need to elaborate please!


PROBLEM 2: Dirty reads.

Use protected objects. Behavior should be encapsulated in a protected
action on it. Note that "read" is not yet a behavior, it is a low-level
operation. Low-level tend to be dirty.

No amount of encapsulation will help. If an object privately caches a
value and doesn't know that it is dirty then it will supply clients
with incorrect results in its public API.

See above. You don't have a cached value, that was probably a wrong design
decision. Try larger objects.

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.


PROBLEM 3: Observer attaches or detaches during a notification

It is racing condition, when allowed to happen asynchronously.

No I'm talking about a single thread that is in the process of
iterating through the observers of a subject in order to notify them,
and an observer decides that it wants to synchronously detach (say).
The problem doesn't exist if the detach is performed asynchronously.

The rule of thumb for good OO design is that objects aren't subjects of
their own. So I would say that objects detaching themselves is a bad
design. However, technically it is no problem.

Please elaborate.


The problem is that while a subject is notifying one of the observers,
an observer decides to attach or detach to/from the subject. This may
cause a crash depending on the data structure used by the subject to
store the observers.

This is not a problem, it is a bug. List and its iterators are objects. So
it is legal to modify the list while iterating it.

Double linked lists (std::list) will work, std::vector or std::deque
will not.

No. It is no matter how the list is implemented. If the contract reads:
iterators stay valid upon list modification, then, well, it is the
contract.

....which is the case for std::list, but not for std::vector and
std::deque.


The very idea to change the list of observers while notifying them is
horrible to me. For example, does it matter whether the new observers
being attached also receive the notification?

Yes it does. In my implementation of persistent objects the weak reference
notification callback passes a set of objects, into which you can place new
objects. They will be notified as well. The set is held by the caller.

Sounds messy to me :)


One hack I've seen to solve this problem is to use a "one shot
observer". Another is to make a copy of the list of observers before
issuing the notifications.

There are many solutions. For example, observers can be limited to wait for
exactly one event at a time.

All are horrible hacks in my opinion :)

That depends on the problem you face. For example, the limitation above
allows rate monotonic analysis. If you had a real-time system, that could
be paramount to you. There always are pros and contras.

PROBLEM 4: Memory management problems

There seems to only be one general solution (that I can think of). A
subject needs to hold strong references on its observers.

Well, usually it is a weak reference observer->subject. Clearly each weak
reference is a strong one in the backward direction. But implementations
don't care about it, because finalization of an observer finalizes the
reference with it. So there is nothing to care about.

Your typical C++ implementation of the observer pattern won't be able
to solve the memory management problem in the example I gave.

It does (and it is not C++, though it were also possible in C++ albeit
through much more sweat and tears). It uses handles.

I don't see how. Please elaborate

With GC if you want to connect two objects using a third one you have to
decide who refers to whom. But typically in a GUI there is a fourth
container object which will hold all three, like Gtk.Box. Anyway, it is not
publisher-subscriber problem specific.


PROBLEM 5: Nested contract attachments

Huh, a container of observers is itself an observer. Or dually, a set of
events is an event.

I have no idea how that relates to the problem.

You have to do a closure of all publisher-subscriber relations. Its result
will be a new observation relation. In general, observations are not
composable. Consider:

c ::= a + b

Let a and b change synchronously, then asynchronous notification
propagation would produce rubbish in c due to race condition.

I don't know what you mean. If a,b both change and they both mark c
as dirty, then later when c is requested it is recalculated and will
simply use the new values of a,b, and therefore give the correct
result. Where is the race condition?

Another
typical example is evaluation of a differential in a data-flow machine:

diff (x) ::= delta (x) / delta (T)

The operator delta computes x(n)-x(n-1). Because the variable T (clock)
changes always, the result of this formula is a constant 0 with 100% CPU
load and sudden spikes when x changes. The problem is in composition of the
events:

changed(x) <+> changed(T) = either changed(x) or changed(T) // wrong
changed(x) <+> changed(T) = changed(x) // correct, in this special case

A newsgroup is a good place to quickly get some opinions.

May I ask a personal question? How long are you reading newsgroups? (:-))

On and off for years. I tend to avoid them for long periods because
they can seem like such a time waster!


The existing literature on lazy evaluation, one-way constraints etc,
seem to more directly solve the problem of cache recalculation. The
observer pattern appears rather flawed for a general solution.

Well, lazy evaluation is an interesting thing, but it has a lot of problems
of its own. Upward closures don't look natural. What about response times
and error handling?

Basically, the reason why you'd like to postpone something must be clear.
For example, if you have a race condition at hand, you might want to wait
until completion of a transition. The problem though is to detect the
condition. Laziness alone is not enough for this. It is just a mechanism of
postponing, it is not a mechanism of detection or preventing.

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.

I'm not sure to what extent we have a basis for comparison because you
seem to be interested in a fully asynchronous and perhaps distributed
system, whereas I'm talking specifically about a single process and
avoiding multi-threading issues.

In that setting there is nothing simpler that the idea to eagerly
propagate dirtiness through the dependency graph, and avoid all the
problems I have discussed in this thread. To me, the only quandary is
to somehow avoid unnecessary work when intermediate nodes end up having
the same value after recalculation. In the problems I have dealt with
this happens more often than not.

This way of thinking seems simple and elegant.

Cheers,
David Barrett-Lennard

.

Relevant Pages

  • Re: Observer pattern limitations
    ... Use asynchronous notification services. ... handlers to simply mark their caches as dirty. ... iterating through the observers of a subject in order to notify them, ... usually it is a weak reference observer->subject. ...
    (comp.object)
  • Re: Observer pattern limitations
    ... A simpler approach is for notification ... handlers to simply mark their caches as dirty. ... iterating through the observers of a subject in order to notify them, ... usually it is a weak reference observer->subject. ...
    (comp.object)
  • Re: repaint method and design question
    ... that the Observable class is not under any restriction regarding how it deals with notification. ... Observers that an Observable may change the order and thread. ... method ends with repaint(). ... invokeLater() and invokeAndWaitaddress synchronization issues related specifically to those methods. ...
    (comp.lang.java.programmer)
  • Re: does NSNotificationCenter block?
    ... the following call to post a notification to the main thread in my GUI ... "A notification center delivers notifications to observers ... Tom "Tom" Harrington ...
    (comp.sys.mac.programmer.help)