抽象データ型と期待された動作の担保

抽象データ型はコード的にはインターフェースのみを持ち具体的な処理は実装する人間にまかされます。

インターフェースに表れないそのデータ型が満たすべき仕様を担保するために、抽象データ型自体がそれを検査するテストを提供すれば良いのではないのかなと思ったので、メモしておきます。

スタックをつくる

例はおなじみのスタックです。コードは Rust 勉強中なので Rust です。

スタックはだいたい以下のような操作が可能です。

trait Stack {
    type Item;

    fn push(&mut self, v: Self::Item);
    fn pop(&mut self) -> Option<Self::Item>;
    fn top(&self) -> Option<&Self::Item>;
}

スタックを実装

今回は Vec を型 T を扱うスタックとして実装しています。

impl<T> Stack for Vec<T> {
    type Item = T;

    fn push(&mut self, v: Self::Item) {
        self.push(v)
    }

    fn pop(&mut self) -> Option<Self::Item> {
        self.pop()
    }

    fn top(&self) -> Option<&Self::Item> {
        self.last()
    }
}

いい加減なスタックを実装

ところで、スタックを知らない人がただ「実装」することも可能です。

struct NoStack<T: Default>(T);

impl<T> Stack for NoStack<T> {
    type Item = T;

    fn push(&mut self, v: Self::Item) {}

    fn pop(&mut self) -> Option<Self::Item> {
        None
    }

    fn top(&self) -> Option<&Self::Item> {
        Some(&self.0)
    }
}

これはコード上ではただしく実装されているのでコンパイルが通ります。

一方、スタックとして期待された動作はしません。

どのように期待された動作を担保するか

そこで、期待された動作をするか確認するテストも同時に提供すればどうかしら?と思ったのが今回のメモの発端です。

期待された動作をするか確認するテストを用意する

期待された動作を満たすためのテストがあれば、ある日異なるスタックを実装して使うことにしても、あらためてスタックの動作を保証する具体的なテストを書かずにすみます。

#[cfg(test)]
struct StackTester;

#[cfg(test)]
impl StackTester {
    fn test(mut stack: impl Stack<Item = usize>) {
        stack.push(1);
        stack.push(2);
        stack.push(3);

        assert_eq!(stack.pop().unwrap(), 3);
        assert_eq!(stack.pop().unwrap(), 2);
        assert_eq!(stack.top().unwrap(), &1);
        assert_eq!(stack.pop().unwrap(), 1);
        assert!(stack.pop().is_none());
        assert!(stack.top().is_none());
    }
}

Vec のスタックは期待された動作をするので通ります。

#[test]
fn test_my_stack() {
    StackTester::test(vec![]);
}

いっぽう、いい加減な方はいい加減な動作をするので通りません。

#[test]
fn test_no_stack() {
    StackTester::test(NoStack(Default::default())); // thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/stack.rs:17:20
}

公理 (AXIOMS) というらしい

期待された動作を定義して実装を確実にする手法はすでに確立されていてもおかしくないな、と思ったので軽くぐぐろうとしたところ、言葉自体がわからなかったので言葉を調べたところで力尽きました。

期待された動作、つまり「その抽象データ型が必ず満たす条件」は「公理 (AXIOMS)」といい、形式的な記述方法もあるみたいです。(参考: 「オブジェクト指向入門 第6章 抽象データ型」を読んだ - $shibayu36->blog;。プログラミング言語によらない抽象データ型の仕様の記述について触れられています)

まとめ

実装の柔軟な変更を考えると、この公理を満たしているかどうか (変更においては満たしつづけられているかどうか) の担保は実装者など実装サイドに任せるのではなく、その公理を定めた側からできると安全性が増しそうです。

柔軟な実装の変更と言えばマイクロサービスが思い浮かびますが、これも公理を満たすかどうかは外部から担保できないと、なかなか変更できなさそうですね。