Prolog で破壊代入っぽい操作を実現する方法

# モチベーション

Prolog でちょっと複雑なプログラムを書こうとすると、引数に受け渡しする変数を並べるのも、リファクタリングで引数を増やしたり減らしたり順序を入れ替えたりするのも大変です。

Prolog の変数には単一化によって値を設定することができますが、一度値を設定すると、バックトラックでなかったことにする以外、書き換える方法はありません。

破壊代入ができるプログラミング言語を使い慣れているせいもあって、変数に破壊代入できればこう書けるのに、とか述語間で任意の値を受け渡しできる破壊代入可能な構造体なりキーバリューストア（KVS）なりを使いたい、とか思うこともしばしばです。

Prolog で素直に KVS を実装してみると、以下のような感じで引数には設定前の KVS、設定後の KVS のペアが必要になります:

```prolog:kvs0.pl
% create(-KVS)
%    KVS を作成する
create(kvs([])).

% put((+KVS_before)-(-KVS_after), +Key, +Value)
%    KVS に Key-Value を登録する。既にあれば上書きする。
put(kvs(Kvs0)-kvs(Kvs1), Key, Value) :-
    nonvar(Kvs0)
    -> ( select(Key-_, Kvs0, Kvs2) -> append(Kvs2, [Key-Value], Kvs1)
       ; append(Kvs0, [Key-Value], Kvs1)).

% remove((+KVS_before)-(-KVS_after), +Key)
%    KVS から Key を削除する。
remove(kvs(Kvs0)-kvs(Kvs1), Key) :-
    nonvar(Kvs0) -> select(Key-_, Kvs0, Kvs1).

% get(+KVS, +Key, -Value)
%    KVS から Key に対応する値 Value を取得する。
get(kvs(Kvs), Key, Value) :-
    nonvar(Kvs) -> member(Key-Value, Kvs).
```

これを利用するプログラムはこんな感じです:

```prolog
:- initialization(consult('kvs0.pl')).

test :-
    create(   X0),    % KVS を作成する（初期状態は X0）
    assign1(  X0-X1), % X[key] に値 1 を設定する（設定結果は X1）
    increment(X1-X2), % X[key] の値を +1 する（+1 した結果は X2）
    increment(X2-X3), % X[key] の値を +1 する（+1 した結果は X3）
    increment(X3-X4), % X[key] の値を +1 する（+1 した結果は X4）
    increment(X4-X5), % X[key] の値を +1 する（+1 した結果は X5）
    result(   X5).    % X[key] の値を表示する
assign1(X1-X2) :-
    write(assign: x(key) = 1), nl,
    put(X1-X2, key, 1).
increment(X1-X2) :-
    get(X1, key, V),
    write(increment: x(key) = V + 1), nl,
    V1 is V + 1,
    put(X1-X2, key, V1).
result(X) :-
    get(X, key, V),
    write(result: x(key) = V), nl.
```

「設定前 - 設定後」をずらずらと採番しながら引数に書いているので、とても煩わしいものになります。書くときに煩わしいだけでなく、リファクタリングも大変です。
例えば、上記の `increment/1` の呼び出しを増やしたり減らしたりするだけでも面倒です。

以下のように書けるならばもっとすっきりします:

```prolog
:- initialization(consult('kvs.pl')).

test :-
    create(   X),  % KVS を作成する
    assign1(  X),  % X[key] に値 1 を設定する
    increment(X),  % X[key] の値を +1 する
    increment(X),  % X[key] の値を +1 する
    increment(X),  % X[key] の値を +1 する
    increment(X),  % X[key] の値を +1 する
    result(   X).  % X[key] の値を表示する
assign1(X) :-
    write(assign: x(key) = 1), nl,
    put(X, key, 1).
increment(X) :-
    get(X, key, V),
    write(increment: x(key) = V + 1), nl,
    V1 is V + 1,
    put(X, key, V1).
result(X) :-
    get(X, key, V),
    write(result: x(key) = V), nl.
```

しかし、これだと `X` に破壊代入しているように見えます。
単一化操作しかない Prolog でこのような記述は可能でしょうか。

# 未完成リストの利用

Prolog の変数は単一化される前の未実現変数を受け渡すことができます。
リストを構成する変数も

`[a,b,c|_]`

のように末尾を未実現のままにしておくことができます。
末尾は未実現なので、更にあとから

`[a,b,c,d,e|_]`

のように伸長していくことが可能です。

このような未完成リスト (incomplete list) 上へ、Key-Value の設定、削除履歴を追加としていって、最も後ろにある当該キーの値を検索して値を返せるようにすれば、破壊代入しているかのような見た目の KVS を実現できます:

```prolog:kvs.pl
:- module(kvs, [create/1, put/3, remove/2, get/3]).

%% create(-KVS)
% Key-Value-Store を作成する（未完成リストを作成する）
create(kvs(_)).

%% put(?KVS, +Key, +Value)
% KVS に Key-Value を登録する（未完成リスト末尾に編集履歴を追加する）
put(kvs(Kvs), Key, Value) :-
    append_to_last(Kvs, Key-put(Value)).

%% remove(?KVS, +Key)
% KVS から Key を削除する（未完成リスト末尾に編集履歴を追加する）
remove(kvs(Kvs), Key) :-
    append_to_last(Kvs, Key-remove).

%% get(?KVS, +Key, -Value)
% KVS から Key に対応する値を Value に取得する
% （未完成リスト上の編集履歴を辿っていって、最後の編集内容を返す）。
% なければ fail。
get(kvs(Kvs), Key, Value) :-
    find_last_entry(Kvs, Key-V) -> V = put(Value).

% 未完成リスト構造を保ったまま、末尾に Entry を追加する。
append_to_last([X|Xs], Entry) :-
    ( var(X) -> X = Entry
    ; append_to_last(Xs, Entry) ).
% 未完成リスト上の Key を検索し、最終要素の値あるいは none を返す。
find_last_entry(Kvs, Key-Value) :-
    find_last_entry(Kvs, Key-Value, none).
find_last_entry(Kvs, Key-Value, LastValue) :-
    ( var(Kvs) -> Value = LastValue
    ; Kvs = [K-V|Kvs2] ->
      ( K == Key -> find_last_entry(Kvs2, Key-Value, V)
      ; find_last_entry(Kvs2, Key-Value, LastValue) )).
```

Key-Value 追加・更新の度に、未完成リストの末尾に `[Key-put(Value)|_]` を追加していきます。削除の場合には `[Key-remove|_]` を追加します。
登録した値を取得する際には、最も末尾に近い当該 Key の要素を探します。

例として、

`create(X), put(X, key, 1), put(X, key, 2), remove(X, key), put(X, key, 3)`

のような操作をした場合には、

'X = kvs([key-put(1), key-put(2), key-remove, key-put(3)|_])'

のように未完成リスト上に履歴が登録されていきます。
この状態で `get(X, key, Value)` を実行すると、未完成リスト上の最後のエントリ `key-put(3)` をもとに `Value=3` を返します。

更新の度にリストが伸びていき検索コストも増大するため、何万回もループを繰り返して更新を繰り返すような用途には向きません。

# まとめ

未完成リストを使うと、Prolog でも破壊代入しているかのようにみせかけることができます。