oster@dewey.soe.berkeley.edu (David Phillip Oster) (05/31/87)
In article <863@apple.UUCP> lsr@apple.UUCP (Larry Rosenstein) writes: >>The combined pair present us with a new virtual document, or view, >>that contains ... > >The same idea is useful in implementing Undo. > >For example, consider selecting all the shapes in a MacDraw document and >changing their shades to white. To save the old state of the document would >require storage proportional to the size of the document, which would be >unacceptable. I know that this is how MacApp does it, but frankly I've never understood why: 1.) A filter implementation of undo seems bad from a human factors point of view: One of the advantages of a personal computer over a terminal connected to a time sharing system is that the personal computer owner can expect a consistant response time from his system. The studies I see say that even if your personal system is slower than the average response of a time-sharing system, you will tend to be more satisfied with the personal system because you have a good feel for how long things are going to take. Now, a filter undo system throw this all away. When you issue a command, the time it takes to complete is equal to the time it takes the CPU to compute the filter for this command (a constant, just like before we had undo) and the time it takes the cpu to do _the previous command_ which it only pretended to do when you issued it. So, a filter undo system throws away one of the great user-interface advantages of a pesonal computer: consistant time behavior. 2.) A filter implementation of undo seems no better from a storage usage point of view: Let's take a common, but tougher case than the one Larry used: suppose, in a text editor you do a complex pattern-matching search-and-replace command that scans an entire large document, doing its thing, and as a side effect changing the length of every single line so that the whole document gets its line-breaks re-computed. Next the user uses the scroll bar to move a long way in the document. A filter undo system is either going to have to do a hell of a lot of computation (and generate a lot of intermediate transient data structures) or it will avoid the computation by, in effect, pre-doing it and caching a lot of data structure. either way, the space could easily be as large as an extra copy of the portion of the document that changed. 3.) A filter implementation of undo seems bad from a programming complexity point of view. A filter implementation of undo requires that you write, for each command that mutates the data structure, a routine that does the real work, and also a routine that pretends to have done the work. These two routines are very different from each other: one is concerned with changing a data structure, the other with spoofing data structure accessors into believing that the structure has changed. The alternative is to actually do the operation, and change the data structure, but to execute a preamble that saves away enough information that an inverse-function can be applied to change the data structure back if the user says to. You need to write the mutator function, the preamble function, and the inverse-mutator function. I use this scheme in my programs. One of the nifty things about this scheme is that the mutator function is often identical to the inverse-mutator function. (Copy-to-clipboard, rename-file, change-color, change-size, and change-font are a few operations that have this self-inverse property.) Suppose Macintosh programs had not only <command>-Z (UnDo) but also <command>-M (Undo more) i.e. run this document editor session backwards in time, one editor step at a time. Let's think about what this would mean for the implementation of the program: Another advantage of the actually-do-it school of undo is that if I ever decide to implement more undo than just undo-the-last-operation, all I need do is manage a list of those records that my preambles made for me. Just takes some space. On the the other side, the filter-scheme of undo means I'd have to keep layering filters between the real data and what the user sees. Each filter takes compute power each time it is used (imagine scrolling through a document that had to percolate the data through 10 layers of active filter before you could see the result of your scroll command.) Obviously, I don't understand some of the philosophical details of the filter-school of undo very well. Obviously you guys at Apple have put a lot of thought into how to implement undo. Please tell me some of the thinking behind your decision. --- David Phillip Oster -- "The goal of Computer Science is to Arpa: oster@dewey.soe.berkeley.edu -- build something that will last at Uucp: ucbvax!dewey.soe!oster -- least until we've finished building it."
lsr@apple.UUCP (Larry Rosenstein) (06/01/87)
In article <19205@ucbvax.BERKELEY.EDU> oster@dewey.soe.berkeley.edu.UUCP (David Phillip Oster) writes: > >I know that this is how MacApp does it, but frankly I've never understood >why: MacApp only provides a framework for implementing Undo; it does not require that you use a filtering approach. Most commands are implemented by saving the necessary document state and restoring it if Undo is chosen. As you said, there are disadvantages to the filtering approach. It does mean that the NEXT command could take longer depending on whether the previous command needs to be committed. >2.) A filter implementation of undo seems no better from a storage >usage point of view: > Let's take a common, but tougher case than the one Larry used: >suppose, in a text editor you do a complex pattern-matching >search-and-replace command that scans an entire large document, doing In this case, there is no good way of implementing Undo. If you look at existing applications, you will see that most of them punt and make the operation non-Undoable. If you have a lot of memory or disk space and the amt. of text is small, then saving the entire document would be the easiest approach. Implementing a filter might be difficult, because you couldn't record the changes in a very compact form, and couldn't apply them very efficiently. One thing you should not do is prevent the user from making the change simply because there is not enough memory, disk space, etc. You should fall back to making the operation non-Undoable. The other thing you should not do is make the operation non-Undoable without getting permission from the user first. Changing the font of some text or the color of an object is different. The storage space required by the filter is much less, also it takes less processing time to apply the filter. >3.) A filter implementation of undo seems bad from a programming >complexity point of view. > A filter implementation of undo requires that you write, for each >command that mutates the data structure, a routine that does the real >work, and also a routine that pretends to have done the work. These This is not a problem. Normally you would implement a set of access routines that the rest of the program uses to access the data structures. These access routines would hide the existence of filters from the rest of the application. In MacApp, the data is stored in a Document object, and normally you implement methods of the Document to access the data. In addition, undoable commands are implemented using Command objects, so the knowledge about doing, undoing, and committing the command (ie, whether there is a filter and how to apply it) is isolated in one place. >structure back if the user says to. You need to write the mutator >function, the preamble function, and the inverse-mutator function. I >use this scheme in my programs. One of the nifty things about this >scheme is that the mutator function is often identical to the >inverse-mutator function. (Copy-to-clipboard, rename-file, Unfortunately, this is not always the case. Stretching an object can't be undone this way without losing information, because of rounding in the arithmetic. (This is especially true if the stretch factor is large.) > Another advantage of the actually-do-it school of undo is that if I >ever decide to implement more undo than just undo-the-last-operation, >all I need do is manage a list of those records that my preambles >made for me. Just takes some space. On the the other side, the >filter-scheme of undo means I'd have to keep layering filters between >the real data and what the user sees. Each filter takes compute power >each time it is used (imagine scrolling through a document that had to >percolate the data through 10 layers of active filter before you could >see the result of your scroll command.) Everything you said in your message (including the paragraph above) is absolutely true. The key words above are "just some space". The purpose of filtered Undo is to save memory space by using processing time. On the Macintosh, memory space is generally more limited than processing time, therefore filtering is a viable way of implementing Undo. On a machine with virtual memory or large hard disks, then filtering is not as useful. It is true that filtering is more difficult to implement than just saving the document state. It is also a technique that programmers might not think of at first (which is why I mentioned it in the first place). I'm not saying that filtering should be used for all operations (or even all operations within a single program). There are cases, however, where creating the filter and applying it doesn't take an excessive amount of processing power, compared to the amount of memory you would have to use to save the entire state. For those cases, filtering can be a good alternative. Thanks for the good comments! -- Larry Rosenstein Object Specialist Apple Computer AppleLink: Rosenstein1 UUCP: {sun, voder, nsc, mtxinu, dual}!apple!lsr CSNET: lsr@Apple.com