１２月２５日火曜日、晴れ

Abstract data type というご大層な名前がついているこの技法が、僕はとても好きだ。 C++ や Java などのオブジェクト指向言語では「インターフェース」が相当する。

つまり「型」があって、これに対するひとそろいの操作がある、というもの。

C 言語でもこれは表現できる。構造体の名前だけを見せて、ポインター越しに操作する関数をいくつか公開するというもの。僕が大好きな例は stdio.h に定義されている FILE オブジェクトだ。

利用者からは実装の詳細が見えないので、操作──メッセージを介してオブジェクトを少しずつ変化させていくことになる。結果、モジュール同士はインターフェースでのみ繋がることになって、お互いの中身がどう変わろうと（まるきり別の実装に置き換わったとしても）構わないという、高い保守性が得られることになる。それっぽく「疎結合」と呼ばれるものだ。

ただ現実には、疎結合が守られたコードなんて皆無といっていい。最初から独立性が高く、それでいて必要十分な操作が可能なインターフェースを括りだすことは難しい。
インターフェースを介してオブジェクトを操作するという理想は切羽詰まった現場では変更速度を落とす足枷となる。結果、抽象化の壁は無残に突き崩され、実装の詳細がズブズブに密結合した悪夢のスパゲッティが世に供されることになる。

＊　＊　＊

もとい。

いまだに、ちまちま数独のテンプレート的解法を実装するための準備をしていて、そこでリスト（という名前の配列）データ抽象を作成した。

こんなの。

#pragma once
#include <stdbool.h>

struct list;

struct list *list_make(void *const *objects, unsigned elems);

struct list *list_append(const struct list *list, void *object);

unsigned list_length(const struct list *list);

void *list_value(const struct list *list, unsigned index);

void *list_reduce(const struct list *list, void *initial, void *(*f)(void *context, void *aggregate, void *value), void *context);

struct list *list_map(const struct list *list, void *(*f)(void *context, void *value), void *context);

struct list *list_filter(const struct list *list, bool (*f)(void *context, void *value), void *context);

そしてこのリスト操作を使って、例の４万６６５６通りのテンプレートを生成するメイン処理がこちら。

/**
 * Input a template (list of numbers), returns its possible templates (list of list).
 */
static void *generate(void *context, void *list);

int main()
{
   GC_INIT();
   struct list *templates = generate(NULL, list_make(NULL, 0));
   printf("%u\n", list_length(templates));
   return 0;
}

static struct list *candidates(struct list *list);
static struct list *prune(struct list *lists);
static struct list *concat(struct list *lists);
void *generate(void *context, void *list)
{
   if (list_length(list) == 9)
   {
       return list_make(&list, 1);
   }
   else
   {
       struct list *nexts = candidates(list);
       struct list *filtered = prune(nexts);
       struct list *lists = list_map(filtered, generate, context);
       return concat(lists);
   }
}

Boehm GC を使ってみるという目的も兼ねていたので、メモリーを使い回すバックトラック法でなく、富豪的深さ優先探索実装になった。（関数型言語に親しんでいればお馴染み、 map reduce による実装）

バックトラック法なら、出力はそのまま標準出力に流すところで、深さ優先探索実装ではリストのリストを生成し、再帰呼び出しの呼び出し元でリストのリストを平らに並べ直す、という手間をとっている。
リストのリストを使う理由は、関数の型合わせのため。

バックトラック法なら candidates 呼び出しで候補すべてをひとまとめに生成したりはせず、候補を一つずつ生成してはそれが制約に従っているかチェックして、さらにその先を探して……というように深く深く潜っていく。
生成されるテンプレートの順序は同じになるのだけれど、途中計算の状況をメモリーにどれだけ蓄えられるかの違いでコードの流れは随分違ったものになっていく。

＊　＊　＊

たしかにそういうことだ。
そう確認できる抽象度の高い数式で「意味」を与え、そこから等式変形でおなじ意味を持つ式に並べなおし書き換えていき、最終的に望む速度と占有記憶域を満たすプログラムを得る。

そういったプログラムの生成ができたら、それこそがプロの仕事と言えるんだろうな──そんな夢を見る。