Observer Pattern
I've often mentioned the idea of changing application programming so more responsibility is offloaded to "The System" (or "The Framework") for managing invalidation. What I'm suggesting isn't quite as pathological as "Completely recompute the layout of every page in Microsoft Word on each keystroke". But I do think that programmers could express their code in such a way that looks a lot more like doing the entire computation, and lets the computer figure out how to manage the incremental updates in a "perfect" way.
Central to achieving this is the ability to monitor the observations that are made of your document as the code is generating pieces of the display. When I mention this, people frequently mention the Observer Pattern. The observer pattern is a good general concept for programmers to think about. Sometimes it's better to not just look at a piece of data and then walking away from it, but rather establish a relationship between the observer and the observed. When a change happens, a notification ("signal" or "callback") is sent to the observer.
The specifics of what I was imagining was that your document's data structure would be built on an API set up with many different entry points. Each entry point into examining the data structure would correspond to a different kind of observation.
As for example, let's think about getting the parent of a TreeNode. One API formulation might look like:
class TreeNode
{
...
TreeNode* GetParentMaybeNull(); // root node returns null for parent
...
};
We could also imagine breaking that API up into more observations. We could break this unified routine into separate accessors for testing whether a TreeNode has a parent, and getting the parent of a TreeNode:
class TreeNode
{
...
bool HasParent();
TreeNode* GetParent(); // asserts if no parent
...
};
At first glance, this looks to be equivalent...and more likely to cause problems. But if you are working within the observer pattern, imagine each API call as an observation that might generate a callback if the observed value changes. If all the observer wanted to know was whether or not a TreeNode has a parent, then a call to HasParent() means there would be no need to have a callback when a node's parent changes, so long as it still has a parent!
(You can of course implement GetParentMaybeNull() as HasParent() ? GetParent() : null...but you would be guiding users of the API away from the habit of asking what the parent is when they only wanted to know whether there was a parent.)
The API can be widened further, of course. If a program has a repeated pattern of testing to see if a TreeNode has a particular node as a parent, we might imagine another API entry point:
class TreeNode
{
...
bool ParentIsNode(TreeNode* node);
...
}
This would be yet another opportunity for minimizing the number of callback notifications. For example, if the answer was false, we'll only need to notify the observer if this node's parent changes to become the precise node in question.
Now imagine that we are trying to keep track of a block of observations of a tree made by a piece of running code. Let's say we have the following list:
A.HasParent() => True
B.HasParent() => True
B.ParentIsNode(A) => False
A.GetParent() => C
If any one of the observed properties changes, the observer wants to be signaled (without needing to know which specific piece of observed information changed). One implementation would be to keep this entire list (or some equivalent of it). Then we could scan through it on each update to the data structure to see if we needed to send a notification. That would cost us a lot of storage space and time, but provide the minimum number of signals to the observer.
Yet certain observers don't mind sometimes getting notifications when the information hasn't actually changed ("false positives"), as long as they never run the chance of skipping a genuine update ("false negatives"). If our observer takes this form, we could prune the list down to something more basic:
Property of A observed
Property of B observed
Going this route causes us to lose some of the benefits of having the programmer express their observations at a fine-grained level. But the notification system has the power to trade off between these extremes. For instance, it could keep track of those observers who take a long time to respond to notifications...and keep a more fine-grained list of their observations, to minimize how frequently they get updated. On the other hand, an observer who makes many observations but runs quickly could move to a more compressed format that might notify them more often than technically necessary.
I had a theory about using this approach with a flexible general-purpose data structure (like XML, for example). My idea was that it would be feasible on today's machines to write a full-fledged application (the likes of Microsoft Word or Excel) in such a way that the programmer never had to think about reacting to specific changes in the data, but just let the system take care of it. This can be achieved by breaking the display code into several observers, and re-generating an observer if one one of the pieces of information that it looked at changes.
For example, in PixelCAD, it is possible to make an icon out of several layers which are composed together...which have rendering effects that are expensive derived computations. Yet each layer is somewhat independent of the others. So it's possible for the display code to observe how many layers there are without delving into the pixel content...and generate a new and independent observer object for each layer. The layers then observe each pixel, so they become dependent on any changes.
It's straightforward to see how this makes the layers independent, and maybe it seems like it would be easy enough to structure a program in this domain which would react appropriately. But now imagine that one of the special effects for a layer just so happens to visit specific pixels in the layer above or below it. The nice thing is that without adding any special handling code to the program, the invalidation would just work. If the programmer was trying to explicitly manage the display incrementality of layers, it would involve some foresight when adding this new special effect. Otherwise, it wouldn't be possible to get a correct incremental display, due to the assumption that the display of each layer was independent of the underlying data used to produce other layers.
This is a major piece of the work I was trying to do. When I talk about it, I tend to get into details...like the precise choices of whether HasParent is a separate entry point or not. Or perhaps I'll talk about how the node ID's are hashed together in a clever way to provide very compact storage of the observation list with very few "false positives". I go into those details because these particular choices seem to be what make typical applications built on these premises work surprisingly well on today's machines. The methodology isn't all that terribly novel, it is just something people don't think would generate usable programs--especially not programs that can do fancy tricks like background spell-checking.
Central to achieving this is the ability to monitor the observations that are made of your document as the code is generating pieces of the display. When I mention this, people frequently mention the Observer Pattern. The observer pattern is a good general concept for programmers to think about. Sometimes it's better to not just look at a piece of data and then walking away from it, but rather establish a relationship between the observer and the observed. When a change happens, a notification ("signal" or "callback") is sent to the observer.
The specifics of what I was imagining was that your document's data structure would be built on an API set up with many different entry points. Each entry point into examining the data structure would correspond to a different kind of observation.
As for example, let's think about getting the parent of a TreeNode. One API formulation might look like:
class TreeNode
{
...
TreeNode* GetParentMaybeNull(); // root node returns null for parent
...
};
We could also imagine breaking that API up into more observations. We could break this unified routine into separate accessors for testing whether a TreeNode has a parent, and getting the parent of a TreeNode:
class TreeNode
{
...
bool HasParent();
TreeNode* GetParent(); // asserts if no parent
...
};
At first glance, this looks to be equivalent...and more likely to cause problems. But if you are working within the observer pattern, imagine each API call as an observation that might generate a callback if the observed value changes. If all the observer wanted to know was whether or not a TreeNode has a parent, then a call to HasParent() means there would be no need to have a callback when a node's parent changes, so long as it still has a parent!
(You can of course implement GetParentMaybeNull() as HasParent() ? GetParent() : null...but you would be guiding users of the API away from the habit of asking what the parent is when they only wanted to know whether there was a parent.)
The API can be widened further, of course. If a program has a repeated pattern of testing to see if a TreeNode has a particular node as a parent, we might imagine another API entry point:
class TreeNode
{
...
bool ParentIsNode(TreeNode* node);
...
}
This would be yet another opportunity for minimizing the number of callback notifications. For example, if the answer was false, we'll only need to notify the observer if this node's parent changes to become the precise node in question.
Now imagine that we are trying to keep track of a block of observations of a tree made by a piece of running code. Let's say we have the following list:
A.HasParent() => True
B.HasParent() => True
B.ParentIsNode(A) => False
A.GetParent() => C
If any one of the observed properties changes, the observer wants to be signaled (without needing to know which specific piece of observed information changed). One implementation would be to keep this entire list (or some equivalent of it). Then we could scan through it on each update to the data structure to see if we needed to send a notification. That would cost us a lot of storage space and time, but provide the minimum number of signals to the observer.
Yet certain observers don't mind sometimes getting notifications when the information hasn't actually changed ("false positives"), as long as they never run the chance of skipping a genuine update ("false negatives"). If our observer takes this form, we could prune the list down to something more basic:
Property of A observed
Property of B observed
Going this route causes us to lose some of the benefits of having the programmer express their observations at a fine-grained level. But the notification system has the power to trade off between these extremes. For instance, it could keep track of those observers who take a long time to respond to notifications...and keep a more fine-grained list of their observations, to minimize how frequently they get updated. On the other hand, an observer who makes many observations but runs quickly could move to a more compressed format that might notify them more often than technically necessary.
I had a theory about using this approach with a flexible general-purpose data structure (like XML, for example). My idea was that it would be feasible on today's machines to write a full-fledged application (the likes of Microsoft Word or Excel) in such a way that the programmer never had to think about reacting to specific changes in the data, but just let the system take care of it. This can be achieved by breaking the display code into several observers, and re-generating an observer if one one of the pieces of information that it looked at changes.
For example, in PixelCAD, it is possible to make an icon out of several layers which are composed together...which have rendering effects that are expensive derived computations. Yet each layer is somewhat independent of the others. So it's possible for the display code to observe how many layers there are without delving into the pixel content...and generate a new and independent observer object for each layer. The layers then observe each pixel, so they become dependent on any changes.
It's straightforward to see how this makes the layers independent, and maybe it seems like it would be easy enough to structure a program in this domain which would react appropriately. But now imagine that one of the special effects for a layer just so happens to visit specific pixels in the layer above or below it. The nice thing is that without adding any special handling code to the program, the invalidation would just work. If the programmer was trying to explicitly manage the display incrementality of layers, it would involve some foresight when adding this new special effect. Otherwise, it wouldn't be possible to get a correct incremental display, due to the assumption that the display of each layer was independent of the underlying data used to produce other layers.
This is a major piece of the work I was trying to do. When I talk about it, I tend to get into details...like the precise choices of whether HasParent is a separate entry point or not. Or perhaps I'll talk about how the node ID's are hashed together in a clever way to provide very compact storage of the observation list with very few "false positives". I go into those details because these particular choices seem to be what make typical applications built on these premises work surprisingly well on today's machines. The methodology isn't all that terribly novel, it is just something people don't think would generate usable programs--especially not programs that can do fancy tricks like background spell-checking.