commit ← (⎕ns'') ##.UndoRedo ⍝ Derive undo/redo function.
commit var ... ⍝ commit application state.
'≠' commit var ... ⍝ commit if different (avoid duplicates)
'!' commit _ ⍝ initialize undo/redo stacks.
var ... ← '<' commit var ... ⍝ undo (rewind) application state.
var ... ← '>' commit var ... ⍝ redo (wind) application state.
undo/redo ← '⊃' commit null ⍝ most recent undo/redo items or null (Kai)
'↑' commit size ⍝ truncate undo stack.
sizes ← '?' commit _ ⍝ query undo/redo stack lengths.
UndoRedo is an operator, used to derive a function for saving and restoring the
state of an application. We can use it to implement "Undo" and "Redo" commands.
One way to provide undo/redo is for each command that changes the state of the
application, to stack an equal and opposite inverse command. Each _Insert_ would
store a _Delete_ and each _Delete_ would store the corresponding _Insert_. This
is the technique used by the Dyalog editor.
A simpler way is to stack the complete state of the application at each "commit"
point. Because of the way Dyalog shares arrays, this method does not use as much
workspace as one might expect. All unchanged parts of the state, are _shared_ at
_every_ level in the undo stack. A commit called after only a small modification
of the state uses little workspace - see the example below.
The state of a typical application might be represented by the values of a (pot-
entially large) number of variables: V1, V2, ..., which need to be restored in
order to roll back to a prior state. In this case, the derived "commit" function
would be called as follows:
'!' commit 0 ⍝ initialize undo/redo stacks.
commit V1 V2 ... ⍝ commit application state.
... ⍝ application changes its state.
commit V1 V2 ... ⍝ commit application state.
(V1 V2 ...) ← '<' commit V1 V2 ... ⍝ undo .. ..
(V1 V2 ...) ← '>' commit V1 V2 ... ⍝ redo .. ..
(
When the number of values defining the application state is large, it may be
tidier to define a pair of "getstate" and "setstate" functions.
getstate←{ setstate←{
props←... ⎕wg... props V1 V2 ...←⍵
V1←a b c _←... ⎕ws do ... ⍝ see →do←
V2←i j k a b c∘←V1
... i j k∘←V2
Vn←x y z ...
props V1 V2 ... x y z∘←Vn
} }
Then:
commit getstate 0 ⍝ regular commit
setstate '<'commit getstate 0 ⍝ undo
Note that the gathering and dispersal of values using local names does not
increase the amount of workspace used by the undo/redo stacks.
As getstate and setstate (by definition) deal with state, implementing them
in a functional paradigm, such as D, is necessarily awkward. They may be
better coded as tradfns. In this case, getstate would be niladic.
)
Note that committing a value _discards_ the redo stack. In other words, redo is
available only immediately after one or more undos. This is a feature of most
Undo/Redo implementations.
The "query guard" '?' could be used in a GUI application to set the Active prop-
erty of the Undo and Redo buttons or menu items:
mbar.(redo undo).Active ← ×'?'commit 0 ⍝ [In]Activate redo / undo.
Note that both the query and initialise commands: '?' and '!' ignore their right
arguments.
Thanks to Kai Jaeger for improvements to this operator.
Technical notes:
UndoRedo binds a namespace to contain the undo/redo stacks that persist between
calls on the derived function (commit). See the notes for the →memo← operator
for a description. See also, Ray Cannon's article "Ghost Variables" Vector 18.3:
http://www.vector.org.uk/archive/v183/hack183.htm
There may be a way to avoid the code duplication in the undo and redo cases by
parameterizing the sense of the reversal.
An alternative, perhaps slightly less elegant implementation, might use fixed
length _vectors_ to represent the undo and redo stacks. The advantage of this
approach would be the ease of controlling a "maximum history depth", which
could be specified as a right argument at initialization time:
UndoRedoV←{ ⍝ Derive undo/redo fn (vector history).
⍺←⊢ ⍝ default: commit values.
psh←{(⊂⍺),⍵} ⍝ push ⍺ to vector ⍵.
pop←{(⊃⍵)(1↓⍵)} ⍝ pop top vector item.
1≡⍺ 1:⍺⍺{ ⍝ monadic commit: push new hist record.
size←⍺.(max⌊1+⍴undo) ⍝ max size of undo vector.
⍺.undo←size↑⍵ psh ⍺.undo ⍝ push new undo record.
⍺.redo←⍬ ⍝ discard redo history.
}⍵
'!'≡⍺:⍺⍺.(redo undo max←⍬ ⍬ ⍵) ⍝ initialize history vectors.
'?'≡⍺:,↑⍴¨⍺⍺.(redo undo) ⍝ query history vectors.
'<'≡⍺:⍺⍺{ ⍝ undo:
0=⍴⍺.undo:⍵ ⍝ no more undo: state unchanged.
⍺.redo←⍵ psh ⍺.redo ⍝ push current state on redo vector.
⊃last ⍺.undo←pop ⍺.undo ⍝ pop last state.
}⍵
'>'≡⍺:⍺⍺{ ⍝ redo:
0=⍴⍺.redo:⍵ ⍝ no more redo: state unchanged.
⍺.undo←⍵ psh ⍺.undo ⍝ push current state on undo vector.
⊃next ⍺.redo←pop ⍺.redo ⍝ pop last state.
}⍵
'↑'≡⍺:⍺⍺{ ⍝ resize undo vector.
⍺.max←⍵ ⍝ set new undo vector size limit.
⍺.(undo←(⍵⌊⍴undo)↑undo) ⍝ truncate undo vector.
⍺.redo←⍬ ⍝ remove redo records.
}⍵
}
Then:
commitV ← (⎕ns'') UndoRedoV ⍝ derive commitV function.
'!'commitV 10 ⍝ initialise, setting history size.
commitV ... ⍝ commit transactions ...
'↑'commitV 4 ⍝ change history vector size.
Example:
commit←(⎕ns'')UndoRedo ⍝ derive a commit function.
'!'commit 0 ⍝ initialise history stack.
'?'commit 0 ⍝ both stacks empty.
0 0
A B C D←'now' 'is' 'the' 'time' ⍝ initial application state.
commit A B C D ⍝ commit application state.
A B ← 'then' 'was' ⍝ change state,
commit A B C D ⍝ commit changes.
A C ← 'that' 'a' ⍝ change state,
commit A B C D ⍝ commit changes.
B D ← 'took' 'while' ⍝ change state,
⎕←A B C D ⍝ show current state.
that took a while
'?'commit 0 ⍝ undo stack has 3 items.
0 3
⎕←A B C D←'<'commit A B C D ⍝ undo last change,
that was a time
'?'commit 0 ⍝ redo stack has 1 item.
1 2
⎕←A B C D←'<'commit A B C D ⍝ undo previous change,
then was the time
⎕←A B C D←'<'commit A B C D ⍝ and change before that.
now is the time
⎕←A B C D←'>'commit A B C D ⍝ Redo last undo.
then was the time
⎕←A B C D←'>'commit A B C D ⍝ Redo previous undo.
that was a time
⎕←A B C D←'>'commit A B C D ⍝ Redo undo before that.
that took a while
'?'commit 0 ⍝ redo stack emtpy.
0 3
⎕←A B C D←'<'commit A B C D ⍝ Undo last Redo.
that was a time
⎕←A B C D←'<'commit A B C D ⍝ Undo previous redo.
then was the time
⎕←A B C D←'<'commit A B C D ⍝ Undo redo before that.
now is the time
⍝ The following example shows that the space overhead of history is small.
a b c d e f g h i j←{1e6?1e6}¨⍳10 ⍝ ten large variables.
'!'commit '(right arg ignored)' ⍝ reinitialise history.
commit a b c d e f g h i j ⍝ commit large variables.
wa←⎕wa ⋄ commit a b c d e f g h i j ⋄ wa-⎕wa ⍝ committing unchanged vars,
96
wa←⎕wa ⋄ commit a b c d e f g h i j ⋄ wa-⎕wa ⍝ consumes little workspace.
80
wa←⎕wa ⋄ commit a b c d e f g h i j ⋄ wa-⎕wa ⍝ consumes little workspace.
80
⍝ ...
See also: memo list
Back to: contents
Back to: Workspaces