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