website | twitter

Thursday, September 08, 2005


To tell the truth, I haven't cared about UNDO in my work at all. Although I am really interested in brand new feature and fancy demonstration of computer programming, but I never have been concerned real user's experience. Ah, but the time seems to be coming to do about UNDO.

From the stand point of developer, I'm really taking care of undo. Programmer's undo is revision control systems. I love to use Monticello to manage my private project in Squeak, and Subversion for other stuff. I couldn't do anymore unless such system. So I realize that one interesting issue here is why undo system is implemented in various way?!

In minimal scale, we can use just undo key in your editor. Each application has its own undo policy. But the undo buffer is removed when the editor is shutdown. Revision control helps the situation. Besides, sometimes we use more file oriented backup system. So far, my company did differential backup for whole PCs at office into file server (I made the script in Perl). In any case, the goals are same, we want to back some point in history of our computing activity. Are there any core concept in?

Let's talk about other angle of undo. Sometimes undo is implemented as command pattern. Look, we have already have another commands in our etoys system, a tile, so we can imagine if undo buffer is made in etoys tiles. If so, one can learn how tile script is written looking undo history. This is basically same as macro recording (actually, I have learned emacs lisp to record/read macro scripts so far). To achieve such feature, all operation including painting a form and editing a text should be recorded as commands (as HyperTalk has all commands for menu / editor operation).

If all operation is recorded into undo buffer, we can see the undo buffer is document itself. That is an interesting side-effect. Instead of saving document data, we can save a sequence of command. The benefit of it would have a power of generalization. Documents, undo, playback, etc. are formed same way of commands.

To proceed this concept, you can see two different documents as two snapshot from same revision tree. Because certainly, a document is written from empty document. We could see any document of same application derives one root. Hence, any document of Squeak space is regard as different version of one big revision tree described in commands.

I know the idea is based on too simplification. I didn't care any performance issue neither space nor time. But it is important to start where the simple enough point.


  1. Some things to think about for Croquet:

    What is the granularity of change? Is it uniform across a system, or do different applications have different granularity?

    Conceptually, there's a message history that can be recorded. By definition, the current state can be reproduced by starting with any committed state and then replaying the messages since then.

    In general, we only care about messages from one tea party to another, where the source and destination are on different hosts. For example, messages from your avatar to the party or from my avatar to the party, are the ones that actually correspond to "external input". But even some of these message are pretty fine-grained (e.g., pointerMove:). Brie has a "gesture" model, where there is distinction between operations that a user thinks of as a single gesture.

    For some applications, it may be handy for a user to specify certain points of time to be of interest. I don't like to make users think about explicitly saving their work, but in those systems that do force users to explicitly "save" or "publish", this forms a natural granularity that the user has actively dicided as the states worth noting.

    In general, a message or gesture is not reversable: not every action has an "inverse" action that will undo it. So the only general mechanism for going backwards through time (e.g., with a scroller) is to save the entire state whenever something of interest changes. (A plausible optimization is to not constantly be saving things during normal use, but wait until someone decides they need to go backwards. At that time, we can start with the most recent convenient checkpoint and replay the messages, with saves of state after each change.)

    What about interactions between objects? Suppose we treat a whole tea party as a unit as described above, where for example, messages from an "outside" party are the the things defining our history for replay. Now, suppose you are replaying the history of a space. Can you be in the space? You're a different tea party! What about the messages that are sent to get the timeline slider to move? One model for this is the "3d portal" or "God's eye view". It's a model of a space, looking from outside. You could be in a place, holding a small 3d model of some place, and simultaneously sliding a timeline back and forth that controls the tea time shown by the 3d model. Then, at some point, you could decide to jump into that model and branch the timeline to create an alternative future from the point that the timeline was at when you jumped in.

    But what about messages from the party controlled by the 3d model, outward to the party that you are now in? Those messages, if replayed, would effect your own past!

    And what about having multiple tea parties in a scene? For example, an object in a space could be a proxy to another tea party. I think this is a generalization of the question of what happens to the avatars of folks who were in a place being replayed.

  2. Thanks Howard!

    I looked the Brie demo at NICT with Julian. I was impressed the idea of using TeaMessage for playback mechanism.

    Actually my idea note was for etoys (finally it becomes Tweak base), current etoys has just poor ability for undoing, so we (etoys' developers) had discussed what kind of undoing mechanism is needed for etoys at Glendale last week. So I was surprised that you had already made replaying demo in Croquet. New generation of etoys needs proper way of undo/redo/playback and even network sharing, there are a lot of similar issues of Croquet.

    But I am just starting now, and there are many difficult issue for me, "gesture" model is a good suggestion that certainly I need it. If we have to care about network collaboration ??????????

    First of all, I'm going to study the undo model of Emacs. It has same aspects than we expected in etoys in many ways, it has infinity undoing, besides you can undo even after you executes user script written in elisp. I'd like to know how Emacs could undo smoothly unless saving vast size of state.

    - Takashi

  3. This comment has been removed by a blog administrator.

  4. I implemented undo once in a moderately complex virtual-human design system. (PeoplePutty)

    We basically created a recordable state object for every undo-capable module, and then recorded all the state objects. The trick was making the state object both complete and small.

    I was never really happy with the results, partially because of regular poor performance, but also because of the just design difficulties arising from having a complex system with several different parts and categories of undo.

    hats off to you for tackling this !

  5. This comment has been removed by a blog administrator.

  6. This comment has been removed by a blog administrator.

  7. This comment has been removed by a blog administrator.

  8. This comment has been removed by a blog administrator.

  9. This comment has been removed by a blog administrator.

  10. Hi there,
    I have stumbled across your blog while searching for info on squeak. I am a final year student working on my hons project which happens to be to develop etoys. Could you direct me to any website/literature that may help me on my way?? I would really appreciate it. Thanks kel

  11. This comment has been removed by a blog administrator.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 Unported License.