Think Stitch
PRINCIPIA  最近の更新


Undo/Redo の話

なんらかのデータを編集するためのユーザインターフェイスを持つアプリケーションプログラムで Undo/Redo を実現する1つの方法について書きたいと思います。 方法自体は一般的なものですが、ある条件を要求するので、残念ながらいつでも適用できるというわけにはいかないと思います。 いつでも適用できるようになるといいな、とは思っていますけど。 その条件とは何かというと、ユーザの操作に対応する遷移を、純粋に関数型で書くということです。

遷移を関数型で書く利点

SyncStitch のモデルは CSP に基づいた状態遷移モデルですから、全体としては関数型プログラムではありません(微妙なところですけど)。 しかし遷移において、状態変数やプロセスパラメータの値を計算する部分は純粋な関数型として記述します。 変数に格納されているデータ構造を副作用によって改変することはありません(できません)。 SyncStitch 自身も、ユーザインターフェイスの部分は 99% 関数型で書かれています(残りが何か気になりますか?。気にならないですか、すみません。誰もが自分と同じことに興味を持つわけではありませんね。数字はおおざっぱな話です)。

遷移における計算を純粋な関数型で計算すると、Undo/Redo の実現が簡単になります。 さらっと「簡単になります」なんていいましたけど、この違いは劇的です。

ポインタで複雑に連結された共有部分を持つようなデータ構造を扱うプログラムで Undo/Redo を実装したことがある人ならば、そのたいへんさをご存知でしょう。 時には共有構造を考慮した上で深いコピーを作ったり、差分を求めたり、逆演算を定義してみたりと面倒なこと(楽しいこと?)この上ありません。 デザインパターンを使った方法があるそうですから、私がよい方法を知らないだけかもしれませんが。

これに対して関数型の場合は簡単です。単に前の状態をそのまま保存しておけばよいのですから。 保存した後で新しい状態に遷移する操作を行っても、保存した状態には影響がありません。 それなりにメモリは消費しますが、それを気にする時代でもありませんし、たいていは共有構造がありますから、そのまま大きさに比例するというわけでもありません。

念のためいっておくと、副作用がある場合でも深いコピーを作成すれば全保存できます。 しかし深いコピーのコードを作るのは結構大変です。 永続化の操作が用意されていれば使うだけですけど、それでも実行に時間がかかります。 さらに以前のデータと部分を共有することはできません。 関数型の場合、保存するといってもコピーは発生しませんから、ここでも違いは劇的です。

Undo パスの2つの流儀

では具体的に Undo/Redo のモデルを作ってみることにします。

状態には A, B, C, ... があるとして、各状態 X に遷移する操作を op.X とします。 A, B, C, ... はそれぞれ複雑なデータ構造を持つ状態です。 操作は遷移前状態から遷移後状態への関数ですから、ほんとはもっとたくさんあるわけですけど、最終的に状態 X に至ることになる操作をまとめて op.X と表しているわけです。

例として、初期状態 A から順に操作を行った状態遷移を以下に示します。 状態 E までいったところで undo を2回実行して状態 C まで戻り、そこで操作 op.F を実行して状態 F になったところです。

状態 C まで戻ったところでは、redo を2回実行することができます。 操作 op.X を実行しない限り、undo と redo で過去の状態を行き来できます。

状態 C で操作 op.F を実行したとき、undo できる状態の列を何にするかで2つの流儀があるように思います。 1つは、A -> B -> C -> F と来たと見なして、右にある D, E を捨ててしまう流儀です。 もう1つは、一度経由した状態にすべて戻れるように、過去のパスを A -> B -> C -> D -> E -> D -> C -> F と見なす流儀です。 それぞれについてモデルを作ってみます。

Redo 部分を捨てる場合

操作 op.X と undo, redo を実行できるプロセス Q を作ります。 このプロセスはエディタのような編集プログラムを抽象的に表したものです。 プロセスは3つのパラメータを持ちます。

プロセスは次のようになります。

(define-process (Q c us rs)
  (alt
    (? op (s)
       (Q s (cons c us) '()))
    (if (null? us)
        STOP
        (! undo
           (Q (car us) (cdr us) (cons c rs))))
    (if (null? rs)
        STOP
        (! redo
           (Q (car rs) (cons c us) (cdr rs))))))

抽象モデルというのは見通しがよくてわかりやすくていいですね。 しかもこのまま動きますから。計算木はつぎのようになります。

操作 op.F を実行した後の us は (C B A), rs は空になっています。

Redo 部分にも戻れるようにする場合

次に、Redo 部分にも戻れるようなモデルを考えます。 状態 C まで戻ってきた時点では us = (B A), rs = (D E) です(上のパスの 8 行目を見てください)。 ここで操作 op.F を実行したら us = (C D E D C B A) となって欲しいわけです。 このうち、末尾にある元の us = (B A) を除いた部分は C を rs = (D E) に加えた (C D E) を折り返したような形になっています。 最初の状態遷移図を見れば、折り返しになることは明らかでしょう。 この折り返しを計算する関数 mirror を定義しておきます。

(define (mirror x)
  (cond ((null? x) '())
        ((null? (cdr x)) x)
        (else
         (cons (car x)
               (append (mirror (cdr x))
                       (list (car x)))))))

再帰の部分は、以下の図を見るとわかると思います。

プロセスは次のようになります。 操作 op.X 時の us の計算部分が変わっただけです。

(define-process (Q2 c us rs)
  (alt
    (? op (s)
       (Q2 s (append (mirror (cons c rs)) us) '()))
    (if (null? us)
        STOP
        (! undo
           (Q2 (car us) (cdr us) (cons c rs))))
    (if (null? rs)
        STOP
        (! redo
           (Q2 (car rs) (cons c us) (cdr rs))))))

計算木は次のようになります。環境ウィンドウを見るとわかるように、期待通りの us になりました。

変更されたかどうかの判断

エディタのような編集を行うプログラムで考えなければならない要素に、データが変更されたかどうかの判断があります。 データをファイルに保存したら変更なしの状態になります。 操作をすれば変更された状態になります。 データを保存する場合やプログラムの終了時に、変更の判断が必要になります。

原理的には、変更なしとみなす状態を保存しておけば、現在の状態と比較することで変更されたかどうか判断することができます。 しかし一般にデータは複雑な構造を持っていますから、データのコピーを2つ与えられたときに、それらが同じであるかどうかを判断するのはコストがかかります。 これは関数型であるかどうかには関わりません。 変更状態を常に表示する場合や、バックグラウンドで自動保存をする場合を考えると、判断は瞬時にできるほうが望ましいでしょう。

そこで次のような妥協案を考えます。 操作を行って状態が変更されたら、新しい状態に対応する識別子を発行します。 識別子は同一性の判定ができるもので、生成と同一性判断コストが安ければどのようなものでもかまいません。 単にインクリメントしていく整数(シーケンサ)でもいいですし、Lisp/Scheme であれば cons や gensym でもよいでしょう。 この識別子を状態とともに記憶することで、変更されているかどうかを判断することにします。 (お使いのエディタがどうなっているか、きっとご存知でしょう。)

このためにプロセスパラメータを3つ追加します。 ここでは整数を識別子として使うことにします。

現在の状態を変更なしとするイベント clear(保存に対応する)を追加します。 プロセスは次のようになります。 undo バッファ、redo バッファともに、状態 c と識別子 i のペアを保存するようにします。

(define-process (Q3 c i m g us rs)
  (alt
    (? op (s)
      (Q3 s g m (+ g 1)
          (append (mirror (cons (cons c i) rs))
                  us)
          '()))
    (if (null? us)
        STOP
        (! undo
           (Q3 (caar us) (cdar us) m g
               (cdr us) (cons (cons c i) rs))))
    (if (null? rs)
        STOP
        (! redo
           (Q3 (caar rs) (cdar rs) m g
               (cons (cons c i) us) (cdr rs))))
    (! clear
       (Q3 c i i g us rs))))

操作の一例を示します。 初期状態では i = m = 0 ですから、変更はありません。 操作 op.B を行うと m = 1 となり i != m ですから変更ありです。 D までいったところで保存、つまり clear を実行します。 すると m = i = 3 となり、変更なしになります。 その後、undo, redo どちらの方向に進んでも、状態 D のところで i = m となることがわかります。

この方法が近似に過ぎないことは、状態 F からさらに操作 op.D を行うとわかります。 保存した状態と同じ状態 D にいるにもかかわらず i != m となっています。 それでも応用によっては有効な方法だと思います。

2013/09/23
© 2013,2014,2015 PRINCIPIA Limited