Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!rutgers!ames!ucbcad!ucbvax!dewey.soe.berkeley.edu!oster From: oster@dewey.soe.berkeley.edu (David Phillip Oster) Newsgroups: comp.sys.mac Subject: Re: Filtering as a way of implementing undo Message-ID: <19205@ucbvax.BERKELEY.EDU> Date: Sun, 31-May-87 07:20:27 EDT Article-I.D.: ucbvax.19205 Posted: Sun May 31 07:20:27 1987 Date-Received: Tue, 2-Jun-87 01:39:10 EDT References: <8705130929.AA17766@cogsci.berkeley.edu> Sender: usenet@ucbvax.BERKELEY.EDU Reply-To: oster@dewey.soe.berkeley.edu.UUCP (David Phillip Oster) Organization: School of Education, UC-Berkeley Lines: 90 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 -Z (UnDo) but also -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."