21 Inheritance case study: “undo”in an interactive system udesixmple weneed thatth desigers of amost any interactive system:how to provide a way to undo commands. The discussion will show how inheritance and dynamic binding yield a simple, regular and general solution to an apparently intricate and many-faceted problem;and it will teach us a few general lessons about the issues and principles of object-oriented design. 21.1 PERSEVERARE DIABOLICUM To err is human,it is said,but to foul things up for good takes a computer (aided,one should add,by humans).The faster and more powerful our interactive systems become, the easier it becomes to make them perform actions that we do not really want.This is why we all wish for a way to erase the recent past;not the "big red button"of computer jokes, but a Big Green Button that we can push to pretend that we did not do something that we did but wish we did not. Undoing for fun and profit In an interactive system,the equivalent of the Big Green Button is an Undo operation, which the system's designer has provided for the benefit of any user who,at some stage in a session,wants to cancel the effect of the last executed command. The primary aim of an undo mechanism is to allow users to recover from potentially damaging input mistakes.It is all too easy to type the wrong character or click on"OK" instead of"Cancel".But a good undo facility goes further.It frees users from having to concentrate nervously on every key they type and button they click.Beyond this,it encourages a "What if...?"style of interaction in which users try out various sorts of input,knowing that they can back up easily if the result is not what they expect. Every good interactive system should provide such a mechanism.When present,it tends to be one of the most frequently used operations.(For that reason,the makers ofthe computer on my desk have wisely provided an Undo key on the keyboard,although it is neither green nor particularly big.It is only effective,of course,for those regrettably few software applications whose authors took notice of it.)
21 Inheritance case study: “undo” in an interactive system For our second design example we examine a need that confronts the designers of almost any interactive system: how to provide a way to undo commands. The discussion will show how inheritance and dynamic binding yield a simple, regular and general solution to an apparently intricate and many-faceted problem; and it will teach us a few general lessons about the issues and principles of object-oriented design. 21.1 PERSEVERARE DIABOLICUM To err is human, it is said, but to foul things up for good takes a computer (aided, one should add, by humans). The faster and more powerful our interactive systems become, the easier it becomes to make them perform actions that we do not really want. This is why we all wish for a way to erase the recent past; not the “big red button” of computer jokes, but a Big Green Button that we can push to pretend that we did not do something that we did but wish we did not. Undoing for fun and profit In an interactive system, the equivalent of the Big Green Button is an Undo operation, which the system’s designer has provided for the benefit of any user who, at some stage in a session, wants to cancel the effect of the last executed command. The primary aim of an undo mechanism is to allow users to recover from potentially damaging input mistakes. It is all too easy to type the wrong character or click on “OK” instead of “Cancel”. But a good undo facility goes further. It frees users from having to concentrate nervously on every key they type and button they click. Beyond this, it encourages a “What if… ?” style of interaction in which users try out various sorts of input, knowing that they can back up easily if the result is not what they expect. Every good interactive system should provide such a mechanism. When present, it tends to be one of the most frequently used operations. (For that reason, the makers of the computer on my desk have wisely provided an Undo key on the keyboard, although it is neither green nor particularly big. It is only effective, of course, for those regrettably few software applications whose authors took notice of it.)
696 INHERITANCE CASE STUDY:"UNDO"IN AN INTERACTIVE SYSTEM $21.I Multi-level undo and redo Offering an undo mechanism is better than not offering one,but it is not enough.Most systems that provide Undo limit themselves to one level:you can only cancel the effect of the last command.If you never make two mistakes in a row,this is enough.But if you ever go off in the wrong direction,and wish you could go back several steps,you are in trouble. (Anyone having used Microsoft Word,the Unix Vi editor or FrameMaker,in the releases available at the time this book was published,will know exactly what I mean. There is really no excuse for the restriction to one level of undoing.Once you have set up the undoing machinery,going from one-level to multi-level undo is a simple matter, as we will see in this chapter.And,please (this is a potential customer speaking)do not, like so many application authors,limit the number of commands that can be undone to a ridiculously small value;if you must limit it at all,let the user choose his own limit (through a "preferences"setting that will apply to all future sessions)and set default to at least 20.The overhead is small if you apply the techniques below,and is well justified. With multi-level undo,you will also need a Redo operation for users who get carried away and undo too much.With one-level undo no special Redo is required;the universally applied convention is that an Undo immediately following an Undo cancels it,so that Redo and Undo are the same operation.But this cannot work if you can go back more than one step.So we will have to treat Redo as a separate operation. Practical issues Although undo-redo can be retrofitted with reasonable effort into a well-written O-O system,it is best,if you plan to support this facility,to make it part of the design from the start-if only because the solution encourages a certain form ofsoftware architecture(the use of command classes)which,although beneficial in other respects,does not necessarily come to mind if you do not need undoing. To make the undo-redo mechanism practical you will have to deal with a few practical concerns. First you must include the facility in the user interface.For a start,we may just assume that the set of operations available to users is enriched with two new requests: Undo (obtained for example by typing control-U,although following the Macintosh convention control-Z seems to have become the standard on PC tools)and Redo (for example control-R).Undo cancels the effect of the last command not yet undone;Redo re-executes the last undone command not yet redone.You will have to define some convention for dealing with attempts to undo more than what has been done (or more than what is remembered),or to redo more than what has been undone:ignore the request,or bring up a warning message. This is only a first shot at user interface support for undo-redo.At the end of this chapter we will see that a nicer,more visual interface is possible
696 INHERITANCE CASE STUDY: “UNDO” IN AN INTERACTIVE SYSTEM §21.1 Multi-level undo and redo Offering an undo mechanism is better than not offering one, but it is not enough. Most systems that provide Undo limit themselves to one level: you can only cancel the effect of the last command. If you never make two mistakes in a row, this is enough. But if you ever go off in the wrong direction, and wish you could go back several steps, you are in trouble. (Anyone having used Microsoft Word, the Unix Vi editor or FrameMaker, in the releases available at the time this book was published, will know exactly what I mean.) There is really no excuse for the restriction to one level of undoing. Once you have set up the undoing machinery, going from one-level to multi-level undo is a simple matter, as we will see in this chapter. And, please (this is a potential customer speaking) do not, like so many application authors, limit the number of commands that can be undone to a ridiculously small value; if you must limit it at all, let the user choose his own limit (through a “preferences” setting that will apply to all future sessions) and set default to at least 20. The overhead is small if you apply the techniques below, and is well justified. With multi-level undo, you will also need a Redo operation for users who get carried away and undo too much. With one-level undo no special Redo is required; the universally applied convention is that an Undo immediately following an Undo cancels it, so that Redo and Undo are the same operation. But this cannot work if you can go back more than one step. So we will have to treat Redo as a separate operation. Practical issues Although undo-redo can be retrofitted with reasonable effort into a well-written O-O system, it is best, if you plan to support this facility, to make it part of the design from the start — if only because the solution encourages a certain form of software architecture (the use of command classes) which, although beneficial in other respects, does not necessarily come to mind if you do not need undoing. To make the undo-redo mechanism practical you will have to deal with a few practical concerns. First you must include the facility in the user interface. For a start, we may just assume that the set of operations available to users is enriched with two new requests: Undo (obtained for example by typing control-U, although following the Macintosh convention control-Z seems to have become the standard on PC tools) and Redo (for example control-R). Undo cancels the effect of the last command not yet undone; Redo re-executes the last undone command not yet redone. You will have to define some convention for dealing with attempts to undo more than what has been done (or more than what is remembered), or to redo more than what has been undone: ignore the request, or bring up a warning message. This is only a first shot at user interface support for undo-redo. At the end of this chapter we will see that a nicer, more visual interface is possible
$21.1 PERSEVERARE DIABOLICUM 697 Second,not all commands are undoable.In some cases this is an impossibility of fact,as in the command "fire the missiles"(notwithstanding the televised comment of a then-in-office US president,who thought one could command a U-turn)or,less ominously,"print the page".In other cases,a command is theoretically undoable but the overhead is not worth the trouble;text editors typically do not let you undo the effect of a Save command,which writes the current document state into a file.The implementation of undoing will need to take into account such non-undoable commands,making this status clear in the user interface.Be sure to restrict non-undoable commands to cases for which this property is easily justifiable in user terms. As a counter-example,a document processing tool which I frequently use tells its user, once in a while,that in the current state of the document the command just requested is not undoable,with no other visible justification than the whim of the program.At least it says so in advance-in most cases. Interestingly,this warning is ina sense a lie:you can undo the effect if you want,although not through Undo but through "Revert to last saved version of the document".This observation yields a user interface rule:if there remains any case for which you feel justified to make a command non-undoable,do not follow the document processing system's example by just displaying a warning of the form"This command will not be undoable"and giving the choice between Continue anyway and Cancel.Give users three possibilities:save document,then execute command;execute without saving; cancel. Finally,it may be tempting to offer,besides Undo and Redo,the more general "Undo,Skip and Redo"scheme,allowing users,after one or more Undo operations,to skip some of the commands before triggering Redo.The user interface shown at the end of this chapter could support this extension,but it raises a conceptual problem:after you skip some commands,the next one may not make sense any more.As a trivial example assume a text editor session,with a text containing just one line,and a user who executes the two commands (1)Add a line at the end (2)Remove the second line Exercise E21.4. Our user undoes both,then wants to skip(1)and redo(2).Unfortunately at this stage page 716. (2)is meaningless:there is no second line.This is less a problem in the user interface (you could somehow indicate to the user that the command is impossible)than in the implementation:the command Remove the second line was applicable to the object structure obtained as a result of(1),but applying it to the object structure that exists prior to (1)may be impossible (that is to say,cause a crash or other unpleasant results). Solutions are certainly possible,but they may not be worth the trouble. Requirements on the solution The undo-redo mechanism that we set out to provide should satisfy the following properties. UI.The mechanism should be applicable to a wide class of interactive applications, regardless of the application domain
§21.1 PERSEVERARE DIABOLICUM 697 Second, not all commands are undoable. In some cases this is an impossibility of fact, as in the command “fire the missiles” (notwithstanding the televised comment of a then-in-office US president, who thought one could command a U-turn) or, less ominously, “print the page”. In other cases, a command is theoretically undoable but the overhead is not worth the trouble; text editors typically do not let you undo the effect of a Save command, which writes the current document state into a file. The implementation of undoing will need to take into account such non-undoable commands, making this status clear in the user interface. Be sure to restrict non-undoable commands to cases for which this property is easily justifiable in user terms. As a counter-example, a document processing tool which I frequently use tells its user, once in a while, that in the current state of the document the command just requested is not undoable, with no other visible justification than the whim of the program. At least it says so in advance — in most cases. Interestingly, this warning is in a sense a lie: you can undo the effect if you want, although not through Undo but through “Revert to last saved version of the document”. This observation yields a user interface rule: if there remains any case for which you feel justified to make a command non-undoable, do not follow the document processing system’s example by just displaying a warning of the form “This command will not be undoable” and giving the choice between Continue anyway and Cancel. Give users three possibilities: save document, then execute command; execute without saving; cancel. Finally, it may be tempting to offer, besides Undo and Redo, the more general “Undo, Skip and Redo” scheme, allowing users, after one or more Undo operations, to skip some of the commands before triggering Redo. The user interface shown at the end of this chapter could support this extension, but it raises a conceptual problem: after you skip some commands, the next one may not make sense any more. As a trivial example assume a text editor session, with a text containing just one line, and a user who executes the two commands (1) Add a line at the end. (2) Remove the second line. Our user undoes both, then wants to skip (1) and redo (2). Unfortunately at this stage (2) is meaningless: there is no second line. This is less a problem in the user interface (you could somehow indicate to the user that the command is impossible) than in the implementation: the command Remove the second line was applicable to the object structure obtained as a result of (1), but applying it to the object structure that exists prior to (1) may be impossible (that is to say, cause a crash or other unpleasant results). Solutions are certainly possible, but they may not be worth the trouble. Requirements on the solution The undo-redo mechanism that we set out to provide should satisfy the following properties. U1 • The mechanism should be applicable to a wide class of interactive applications, regardless of the application domain. Exercise E21.4, page 716
698 INHERITANCE CASE STUDY:"UNDO"IN AN INTERACTIVE SYSTEM $21.I U2.The mechanism should not require redesign for each new command. U3.It should make reasonable use of storage. U4.It should be applicable to both one-level and arbitrary-level Undo. The first requirement follows from the observation that there is nothing application- specific about undoing and redoing.To facilitate the discussion,we will use as example a kind of tool familiar to everyone:a text editor (such as Notepad or Vi),which enables its users to enter texts and to perform such commands as INSERT LINE,DELETE LINE, GLOBAL REPLACEMENT (of a word by another)and so on.But this is only an example and none of the concepts discussed below is specific to text editors. The second requirement excludes treating Undo and Redo as just any other command in the interactive system.Were Undo a command,it would need a structure of the form if"Last command was INSERT LINE"then "Undo the effect of INSERT LINE" elseif "Last command was DELETE LINE"then “Undo the effect of DELETE LINE” etc. We know how bad such structures,the opposite of what the Single Choice principle See"Single directs us to use,are for extendibility.They have to be changed every time you add a Choice”,page61. command;furthermore,the code in each branch will mirror the code for the corresponding command (the first branch,for example,has to know a lot about what INSERT LINE does),pointing to a flawed design. The third requirement directs us to be sparing in our use of storage.Supporting undo- redo will clearly force us to store some information for every Undo;for example when we execute a DELETE LINE,we will not be able to undo it later unless we put aside somewhere,before executing the command,a copy of the line being deleted and a record of its position in the text.But we should store only what is logically necessary. The immediate effect of this third requirement is to exclude an obvious solution: On STORABLE see saving the whole system state-the entire object structure-before every command “Deep storage:.afirst execution;then Undo would just restore the saved image.This would work but is terribly view ofpersistence" wasteful of space.Too bad,since the solution would be trivial to write:just use the page 250. STORABLE facilities for storing and retrieving an entire object structure in a single blow. But we must look for something a little more sophisticated. The final requirement,supporting an arbitrary depth of undoing,has already been discussed.It will tum out to be easier to consider a one-level mechanism first,and then to generalize it to multi-level. These requirements complete the presentation of the problem.It may be a good idea, as usual,to spend a little time looking for a solution on your own before proceeding with the rest of this chapter
698 INHERITANCE CASE STUDY: “UNDO” IN AN INTERACTIVE SYSTEM §21.1 U2 • The mechanism should not require redesign for each new command. U3 • It should make reasonable use of storage. U4 • It should be applicable to both one-level and arbitrary-level Undo. The first requirement follows from the observation that there is nothing applicationspecific about undoing and redoing. To facilitate the discussion, we will use as example a kind of tool familiar to everyone: a text editor (such as Notepad or Vi), which enables its users to enter texts and to perform such commands as INSERT_LINE, DELETE_LINE, GLOBAL_REPLACEMENT (of a word by another) and so on. But this is only an example and none of the concepts discussed below is specific to text editors. The second requirement excludes treating Undo and Redo as just any other command in the interactive system. Were Undo a command, it would need a structure of the form if “Last command was INSERT_LINE” then “Undo the effect of INSERT_LINE” elseif “Last command was DELETE_LINE” then “Undo the effect of DELETE_LINE” etc. We know how bad such structures, the opposite of what the Single Choice principle directs us to use, are for extendibility. They have to be changed every time you add a command; furthermore, the code in each branch will mirror the code for the corresponding command (the first branch, for example, has to know a lot about what INSERT_LINE does), pointing to a flawed design. The third requirement directs us to be sparing in our use of storage. Supporting undoredo will clearly force us to store some information for every Undo; for example when we execute a DELETE_LINE, we will not be able to undo it later unless we put aside somewhere, before executing the command, a copy of the line being deleted and a record of its position in the text. But we should store only what is logically necessary. The immediate effect of this third requirement is to exclude an obvious solution: saving the whole system state — the entire object structure — before every command execution; then Undo would just restore the saved image. This would work but is terribly wasteful of space. Too bad, since the solution would be trivial to write: just use the STORABLE facilities for storing and retrieving an entire object structure in a single blow. But we must look for something a little more sophisticated. The final requirement, supporting an arbitrary depth of undoing, has already been discussed. It will turn out to be easier to consider a one-level mechanism first, and then to generalize it to multi-level. These requirements complete the presentation of the problem. It may be a good idea, as usual, to spend a little time looking for a solution on your own before proceeding with the rest of this chapter. See “Single Choice”, page 61. On STORABLE see “Deep storage: a first view of persistence”, page 250
$21.2 FINDING THE ABSTRACTIONS 699 21.2 FINDING THE ABSTRACTIONS The key step in an object-oriented solution is the search for the right abstraction.Here the fundamental notion is staring us in the eyes. Command as a class The problem is characterized by a fundamental data abstraction:COMMAND, representing any editor operation other than Undo and Redo.Execution is only one of the features that may be applied to a command:the command might be stored,tested-or undone.So we need a class of the provisional form deferred class COMMAND feature execute is deferred end undo is deferred end end COMMAND describes the abstract notion of command and so must remain deferred. Actual command types are represented by effective descendants of this class,such as class LINE DELETION inherit COMMAND feature deleted line index:INTEGER deleted line:STRING set deleted line index (n:INTEGER)is -Set to n the number of next line to be deleted. do deleted line index:=n end execute is --Delete line. do "Delete line number deleted line index" "Record text of deleted line in deleted line" end undo is --Restore last deleted line. do "Put back deleted line at position deleted line index" end end And similarly for each command class
§21.2 FINDING THE ABSTRACTIONS 699 21.2 FINDING THE ABSTRACTIONS The key step in an object-oriented solution is the search for the right abstraction. Here the fundamental notion is staring us in the eyes. Command as a class The problem is characterized by a fundamental data abstraction: COMMAND, representing any editor operation other than Undo and Redo. Execution is only one of the features that may be applied to a command: the command might be stored, tested — or undone. So we need a class of the provisional form deferred class COMMAND feature execute is deferred end undo is deferred end end COMMAND describes the abstract notion of command and so must remain deferred. Actual command types are represented by effective descendants of this class, such as class LINE_DELETION inherit COMMAND feature deleted_line_index: INTEGER deleted_line: STRING set_deleted_line_index (n: INTEGER) is -- Set to n the number of next line to be deleted. do deleted_line_index := n end execute is -- Delete line. do “Delete line number deleted_line_index” “Record text of deleted line in deleted_line” end undo is -- Restore last deleted line. do “Put back deleted_line at position deleted_line_index” end end And similarly for each command class
700 INHERITANCE CASE STUDY:"UNDO"IN AN INTERACTIVE SYSTEM $21.2 What do such classes represent?An instance of LINE DELETION,as illustrated below,is a little object that carries with it all the information associated with an execution of the command:the line being deleted (deleted line,a string)and its index in the text (deleted line index,an integer).This is the information needed to undo the command should this be required later on,or to redo it deleted line index 45 A command "Some text" object deleted line The exact attributes-such as deleted line and deleted line index here -will See“Requirements differ for each command class,but they should always be sufficient to support the local on the solution”", variants of execute and undo.Such objects,conceptually describing the difference page 697. between the states that precede and follow the application of a command,will enable us to satisfy requirement U3 of the earlier list-storing only what is strictly necessary. The inheritance structure of command classes may look like this: execute* Command undo* COMMAND class hierarchy LINE LINE STRING INSERTION DELETION REPLACE The graph shown is flat (all proper descendants of COMMAND at the same level), but nothing precludes adding more structure by grouping command types into intermediate categories;this will be justified if such categories make sense as abstract data types,that is to say,have specific features. When defining a notion,it is always important to indicate what it does not cover. Here the concept of command does not include Undo and Redo;for example it would not make sense to undo an Undo(except in the sense of doing a Redo).For this reason the discussion uses the term operation for Undo and Redo,reserving command for operations which can be undone and redone,such as line insertion.There is no need for a class covering the notion of operation,since non-command operations such as Undo have only one relevant feature,their ability to be executed. This is a good example of the limitations of simplistic approaches to "find the objects", “The nous and the such as the famous "Underline the nouns"idea studied in a later chapter.In the verbs",page 720. specification of the problem,the nouns command and operation are equally important; but one gives a fundamental class,the other does not give a class at all.Only the abstract data type perspective-studying abstractions in terms of the applicable operations and their properties-can help us find the classes of our object-oriented systems
700 INHERITANCE CASE STUDY: “UNDO” IN AN INTERACTIVE SYSTEM §21.2 What do such classes represent? An instance of LINE_DELETION, as illustrated below, is a little object that carries with it all the information associated with an execution of the command: the line being deleted (deleted_line, a string) and its index in the text (deleted_line_index, an integer). This is the information needed to undo the command should this be required later on, or to redo it. The exact attributes — such as deleted_line and deleted_line_index here — will differ for each command class, but they should always be sufficient to support the local variants of execute and undo. Such objects, conceptually describing the difference between the states that precede and follow the application of a command, will enable us to satisfy requirement U3 of the earlier list — storing only what is strictly necessary. The inheritance structure of command classes may look like this: The graph shown is flat (all proper descendants of COMMAND at the same level), but nothing precludes adding more structure by grouping command types into intermediate categories; this will be justified if such categories make sense as abstract data types, that is to say, have specific features. When defining a notion, it is always important to indicate what it does not cover. Here the concept of command does not include Undo and Redo; for example it would not make sense to undo an Undo (except in the sense of doing a Redo). For this reason the discussion uses the term operation for Undo and Redo, reserving command for operations which can be undone and redone, such as line insertion. There is no need for a class covering the notion of operation, since non-command operations such as Undo have only one relevant feature, their ability to be executed. This is a good example of the limitations of simplistic approaches to “find the objects”, such as the famous “Underline the nouns” idea studied in a later chapter. In the specification of the problem, the nouns command and operation are equally important; but one gives a fundamental class, the other does not give a class at all. Only the abstract data type perspective — studying abstractions in terms of the applicable operations and their properties — can help us find the classes of our object-oriented systems. "Some text" deleted_line_index deleted_line 45 A command object See “Requirements on the solution”, page 697. Command class hierarchy * LINE_ … execute* undo* INSERTION LINE_ DELETION COMMAND STRING_ REPLACE “The nouns and the verbs”, page 720
$21.2 FINDING THE ABSTRACTIONS 701 The basic interactive step To get started we will see how to support one-level undo.The generalization to multi-level undo-redo will come next. In any interactive system,there must be somewhere,in a module in charge of the communication with users,a passage of the form basic interactive step is --Decode and execute one user request. do "Find out what the user wants us to do next" “Doit(if possible)” end In a traditionally structured system,such as editor,these operations will be executed as part of a loop,the program's"basic loop": from start until quit has been requested and confirmed loop basic interactive step end whereas more sophisticated systems may use an event-driven scheme,in which the loop is external to the system proper (being managed by the underlying graphical environment).But in all cases there is a need for something like basic interactive step. In light of the abstractions just identified,we can reformulate the body of the procedure as "Get latest user request" "Decode request" if "Request is a normal command (not Undo)"then "Determine the corresponding command in our system" "Execute that command" elseif“Request is Undo”then if“There is a command to be undone”then Undo last command'” elseif"There is a command to be redone"then “Redo last command'" end else "Report erroneous request" end
§21.2 FINDING THE ABSTRACTIONS 701 The basic interactive step To get started we will see how to support one-level undo. The generalization to multi-level undo-redo will come next. In any interactive system, there must be somewhere, in a module in charge of the communication with users, a passage of the form basic_interactive_step is -- Decode and execute one user request. do “Find out what the user wants us to do next” “Do it (if possible)” end In a traditionally structured system, such as editor, these operations will be executed as part of a loop, the program’s “basic loop”: from start until quit_has_been_requested_and_confirmed loop basic_interactive_step end whereas more sophisticated systems may use an event-driven scheme, in which the loop is external to the system proper (being managed by the underlying graphical environment). But in all cases there is a need for something like basic_interactive_step. In light of the abstractions just identified, we can reformulate the body of the procedure as “Get latest user request” “Decode request” if “Request is a normal command (not Undo)” then “Determine the corresponding command in our system” “Execute that command” elseif “Request is Undo” then if “There is a command to be undone” then “Undo last command” elseif “There is a command to be redone” then “Redo last command” end else “Report erroneous request” end
702 INHERITANCE CASE STUDY:"UNDO"IN AN INTERACTIVE SYSTEM $21.2 This implements the convention suggested earlier that Undo applied just after Undo means Redo.A request to Undo or Redo is ignored if there is nothing to undo or redo.In a simple text editor with a keyboard interface,"Decode request"would analyze the user input,looking for such codes as control-I (for insert line),control-D (for delete line)and so on.With graphical interfaces you have to determine what input the user has entered, such as a choice in a menu,a button clicked in a menu,a key pressed. Remembering the last command With the notion of command object we can be more specific about the operations performed by basic interactive step.We will use an attribute requested:COMMAND --Command requested by interactive user representing the latest command that we have to execute,undo or redo.This enables us to refine the preceding scheme of basic interactive step into: "Get and decode latest user request" if“Request is normal command(not Undo)”then "Create appropriate command object and attach it to requested" --requested is created as an instance of some -descendant of COMMAND,such as LINE DELETION --(This instruction is detailed below.) Dynamic requested.execute;undoing mode :False Binding elseif "request is Undo"and requested /Void then if undoing mode then "This is a Redo;details left to the reader" else equested.undo undoing mode:=True end else "Erroneous request:output warning,or do nothing" end The boolean entity undoing mode determines whether the last operation was an Undo.In Exercise E21.2. this case an immediately following Undo request would mean a Redo,although the page 716. straightforward details have been left to the reader;we will see the full details of Redo implementation in the more interesting case of a multi-level mechanism. The information stored before each command execution is an instance of some See“Requirements descendant of COMMAND such as LINE DELET/ON.This means that,as announced,the on the solution”, solution satisfies the property labeled U3 in the list ofrequirements:what we store for each page 697. command is the difference between the new state and the previous one,not the full state
702 INHERITANCE CASE STUDY: “UNDO” IN AN INTERACTIVE SYSTEM §21.2 This implements the convention suggested earlier that Undo applied just after Undo means Redo. A request to Undo or Redo is ignored if there is nothing to undo or redo. In a simple text editor with a keyboard interface, “Decode request” would analyze the user input, looking for such codes as control-I (for insert line), control-D (for delete line) and so on. With graphical interfaces you have to determine what input the user has entered, such as a choice in a menu, a button clicked in a menu, a key pressed. Remembering the last command With the notion of command object we can be more specific about the operations performed by basic_interactive_step. We will use an attribute requested: COMMAND -- Command requested by interactive user representing the latest command that we have to execute, undo or redo. This enables us to refine the preceding scheme of basic_interactive_step into: “Get and decode latest user request” if “Request is normal command (not Undo)” then “Create appropriate command object and attach it to requested ” -- requested is created as an instance of some -- descendant of COMMAND, such as LINE_DELETION -- (This instruction is detailed below.) ; undoing_mode := False elseif “request is Undo” and requested /= Void then if undoing_mode then “This is a Redo; details left to the reader” else ; undoing_mode := True end else “Erroneous request: output warning, or do nothing” end The boolean entity undoing_mode determines whether the last operation was an Undo. In this case an immediately following Undo request would mean a Redo, although the straightforward details have been left to the reader; we will see the full details of Redo implementation in the more interesting case of a multi-level mechanism. The information stored before each command execution is an instance of some descendant of COMMAND such as LINE_DELETION. This means that, as announced, the solution satisfies the property labeled U3 in the list of requirements: what we store for each command is the difference between the new state and the previous one, not the full state. requested ● execute Dynamic Binding requested ● undo Exercise E21.2, page 716. See “Requirements on the solution”, page 697
$21.2 FINDING THE ABSTRACTIONS 703 The key to this solution-and its refinements in the rest of this chapter-is polymorphism and dynamic binding.Attribute requested is polymorphic:declared of type COMMAND,it will become attached to objects of one of its effective descendant types such as LINE INSERTION.The calls requested.execute and requested.undo only make sense because of dynamic binding:the feature they trigger must be the version redefined for the corresponding command class,executing or undoing a LINE INSERTION,a LINE DELETION or a command of any other type as determined by the object to which requested happens to be attached at the time of the call. The system's actions No part of the structure seen so far is application-specific.The actual operations of the application,based on its specific object structures -for example the structures representing the current text in a text editor-are elsewhere;how do we make the connection? The answer relies on the execute and undo procedures of the command classes, which must call application-specific features.For example procedure execute of class LINE DELETION must have access to the editor-specific classes to call features that will yield the text of the current line,give its position in the text,and remove it. As a result there is a clear separation between the user interaction parts of a system, largely application-independent,and the application-specific parts,closer to the model of each application's conceptual model-be it text processing,CAD-CAM or anything else. The first component,especially when generalized to a history mechanism as explained next,will be widely reusable between various application domains. How to create a command object After decoding a request,the system must create the corresponding command object.The instruction appeared abstractly as "Create appropriate command object and attach it to requested";we may express it more precisely,using creation instructions,as if"Request is LINE INSERTION"then LINE INSERTION requested.make (input text,cursor_index) elseif"Request is LINE DELETION"then LINE DELETION requested.make (current line,line index) elseif "Polymorphic cre- This uses the SOME TYPE x...form of the creation instruction,which creates an ation”page479. object of type SOME TYPE and attaches it to x;remember that SOME TYPE must conform to the type declared for x,as is the case here since requested is of type COMMAND and all the command classes are descendants of COMMAND. If each command type uses a unique integer or character code,a slightly simpler form relies on an inspect:
§21.2 FINDING THE ABSTRACTIONS 703 The key to this solution — and its refinements in the rest of this chapter — is polymorphism and dynamic binding. Attribute requested is polymorphic: declared of type COMMAND, it will become attached to objects of one of its effective descendant types such as LINE_INSERTION. The calls requested ● execute and requested ● undo only make sense because of dynamic binding: the feature they trigger must be the version redefined for the corresponding command class, executing or undoing a LINE_INSERTION, a LINE_DELETION or a command of any other type as determined by the object to which requested happens to be attached at the time of the call. The system’s actions No part of the structure seen so far is application-specific. The actual operations of the application, based on its specific object structures — for example the structures representing the current text in a text editor — are elsewhere; how do we make the connection? The answer relies on the execute and undo procedures of the command classes, which must call application-specific features. For example procedure execute of class LINE_DELETION must have access to the editor-specific classes to call features that will yield the text of the current line, give its position in the text, and remove it. As a result there is a clear separation between the user interaction parts of a system, largely application-independent, and the application-specific parts, closer to the model of each application’s conceptual model — be it text processing, CAD-CAM or anything else. The first component, especially when generalized to a history mechanism as explained next, will be widely reusable between various application domains. How to create a command object After decoding a request, the system must create the corresponding command object. The instruction appeared abstractly as “Create appropriate command object and attach it to requested”; we may express it more precisely, using creation instructions, as if “Request is LINE INSERTION” then ! LINE_INSERTION ! requested ● make (input_text, cursor_index) elseif “Request is LINE DELETION” then ! LINE_DELETION ! requested ● make (current_line, line_index) elseif … This uses the ! SOME_TYPE ! x … form of the creation instruction, which creates an object of type SOME_TYPE and attaches it to x; remember that SOME_TYPE must conform to the type declared for x, as is the case here since requested is of type COMMAND and all the command classes are descendants of COMMAND. If each command type uses a unique integer or character code, a slightly simpler form relies on an inspect: “Polymorphic creation”, page 479
704 INHERITANCE CASE STUDY:"UNDO"IN AN INTERACTIVE SYSTEM $21.3 inspect request code when Line insertion then !LINE INSERTION requested.make (input_text,cursor_position) etc Both forms are multiple-branch choices,but they do not violate the Single Choice “Single Choice", principle:as was pointed out in the discussion of that principle,if a system provides a page 61. number ofalternatives some part ofit must know the complete list of alternatives.The above extract,in either variant,is that point of single choice.What the principle precludes is spreading out such knowledge over many modules.Here,no other part of the system needs access to the list of commands;every command class deals with just one kind of command. It is in fact possible to obtain a more elegant structure and get rid of the multi-branch “Precomputing choice totally;we will see this at the end of presentation. command objects”, page 708. 21.3 MULTI-LEVEL UNDO-REDO Supporting an arbitrary depth of undoing,with the attendant redoing,is a straightforward extension of the preceding scheme. The history list What has constrained us to a single level of undoing was the use of just one object,the last created instance of COMMAND available through requested,as the only record of previously executed commands. In fact we create as many objects as the user executes commands.But because the See chapter 9 on software only has one command object reference,requested,al ways attached to the last garbage collection command,every command object becomes unreachable as soon as the user executes a new command.It is part of the elegance and simplicity of a good O-O environment that we do not need to worry about such older command objects:the garbage collector will take care of reclaiming the memory they occupy.It would be a mistake to try to reclaim the command objects ourselves,since they may all be of different shapes and sizes. To provide more depth of undoing we need to replace the single command requested by a list of recently executed commands,the history list: history:SOME LIST [COMMAND] SOME LIST is not a real class name;in true object-oriented,abstract data type style we will examine what features and properties we need from SOME LIST and draw the conclusion as to what list class (from the Base library)we can use.The principal operations we need are straightforward and well known from previous discussions: put to insert an element at the end (the only place where we will need insertions).By convention,put will position the list cursor on the element just inserted. empty to find out whether the list is empty
704 INHERITANCE CASE STUDY: “UNDO” IN AN INTERACTIVE SYSTEM §21.3 inspect request_code when Line_insertion then ! LINE_INSERTION ! requested ● make (input_text, cursor_ position) etc. Both forms are multiple-branch choices, but they do not violate the Single Choice principle: as was pointed out in the discussion of that principle, if a system provides a number of alternatives some part of it must know the complete list of alternatives. The above extract, in either variant, is that point of single choice. What the principle precludes is spreading out such knowledge over many modules. Here, no other part of the system needs access to the list of commands; every command class deals with just one kind of command. It is in fact possible to obtain a more elegant structure and get rid of the multi-branch choice totally; we will see this at the end of presentation. 21.3 MULTI-LEVEL UNDO-REDO Supporting an arbitrary depth of undoing, with the attendant redoing, is a straightforward extension of the preceding scheme. The history list What has constrained us to a single level of undoing was the use of just one object, the last created instance of COMMAND available through requested, as the only record of previously executed commands. In fact we create as many objects as the user executes commands. But because the software only has one command object reference, requested, always attached to the last command, every command object becomes unreachable as soon as the user executes a new command. It is part of the elegance and simplicity of a good O-O environment that we do not need to worry about such older command objects: the garbage collector will take care of reclaiming the memory they occupy. It would be a mistake to try to reclaim the command objects ourselves, since they may all be of different shapes and sizes. To provide more depth of undoing we need to replace the single command requested by a list of recently executed commands, the history list: history: SOME_LIST [COMMAND] SOME_LIST is not a real class name; in true object-oriented, abstract data type style we will examine what features and properties we need from SOME_LIST and draw the conclusion as to what list class (from the Base library) we can use. The principal operations we need are straightforward and well known from previous discussions: • put to insert an element at the end (the only place where we will need insertions). By convention, put will position the list cursor on the element just inserted. • empty to find out whether the list is empty. “Single Choice”, page 61. “Precomputing command objects”, page 708. See chapter 9 on garbage collection