連結リストのみのLISP処理系実装について考察した

限りなくポエムに近い技術記事です．
【2021-07-22修正】
コンスセル構造の記述例をSchemeからPrologに，配列構造の記述例をClojureからPythonに変更しました．Clojureの連結リストは配列構造じゃないよ…．

前書き

筆者は趣味と実益を兼ね，いろんな仕様やプログラミング言語で最小構成のLISP評価器（いわゆる純LISP）を実装して遊んでいます（記事1，記事2，記事3，記事4）．

このうち，直近で試した評価器をJSONで定義してみた際に，JSONの配列構造による定義のしやすさから，LISPならではのコンスセルの実装は行わず，連結リストのみを用いた方式にしました．この結果，リスト操作のプリミティブ関数であるconsとcdrがScheme/Common Lispなどの主流LISP仕様と大きく異なることとなりました．また，それに伴い，それまでは名前環境（シンボルテーブル）を連想リストで実現していたのを，属性リストに変更しました．コンスセル，連結リスト，連想リスト，属性リストについてはこちらの記事を御参照下さい（ただし，属性リストについては，Common Lispにおける記号割当に基づく実際の利用方法を中心に述べています）．

LISPなのにコンスセルがないなんて…とも思ったのですが，実装に用いるプログラミング言語，特に，Python/Ruby/JavaScriptなどの主要スクリプト言語では，それ自身を含む任意の型を要素とする配列が連結リストとして利用できることから，評価器本体はもちろん（他サイト記事参照），S式入出力処理の実装もだいぶ楽になります．コンスセルはリスト構造の基本パーツであると同時に，いわゆる辞書型やハッシュテーブル，連想配列の要素に相当するペア構造も兼ねるのですが，これを，属性リスト，すなわち，キーと値が交互に並ぶ連結リストの方式に置き換えても，利用面はもちろん，セル消費・操作コストもそれほど違いがありませんでした．データ構成だけでペア構造と判断できないのが最大の難点でしょうか．

リスト構造と配列構造

両者の違いについては，単純に値が並んでいる場合の内部構造を見ればすぐにわかります．

プログラミングにおいては，いずれも『リスト』と呼び，角括弧とカンマ区切りで表現しているものの，前者を採用しているPrologと，後者を採用しているPythonでの扱いの違いに現れます．次は，Prologのペア構造によるリスト構造の例です．リスト構造となる場合は括弧と縦棒が省略されてカンマ区切りとなり，リストのネストとは異なる構造となります．

SWI-Prolog8.0.2

?- X = [a, b, c].
X = [a, b, c].

?- [A | B] = [a, b, c].
A = a,
B = [b, c].

?- X = [a | [b | [c | []]]].
X = [a, b, c].

?- X = [a, [b, [c, []]]].
X = [a, [b, [c, []]]].

?- X = [a | []].
X = [a].

?- X = [a, []].
X = [a, []].

次は，Pythonのリストを扱っている例です．あくまで配列であり，角括弧とカンマ区切りによる表現がそのまま内部構造となります．

Python3.7.3

>>> ['a', 'b', 'c']
['a', 'b', 'c']
>>> ['a', 'b', 'c'][0]
'a'
>>> ['a', 'b', 'c'][1:]
['b', 'c']
>>> ['a', 'b', 'c'][2:]
['c']
>>> ['a', ['b', ['c', []]]]
['a', ['b', ['c', []]]]

Pythonのリスト操作は，あくまで配列構造に対する添字操作となります．いわゆるスライス操作で連結リストと同様の『先頭から順番にたどっていく』ことも可能ですが，『最後から順番にたどっていく』ことも同様に可能です．

Python3.7.3

>>> ['a','b','c'][-1]
'c'
>>> ['a','b','c'][:-1]
['a', 'b']
>>> ['a','b','c'][:-2]
['a']

本来の連結リスト構造をもつPrologでは，『最後からたどる』ことは原則としてできません．リスト全体の構造を把握した上で要素を取り出すのが基本です．

SWI-Prolog8.0.2

?- [X, Y, Z] = [a, b, c].
X = a,
Y = b,
Z = c.

?- [_, _, X] = [a, b, c].
X = c.

?- [_|[_|[X|_]]] = [a, b, c].
X = c.

コンスセル構造を用いる最大の利点は，構造そのものよりも，syntax sugarとしての省略表現かもしれません．これは元祖コンスセル構造のLISP系言語で用いられるS式で如実に現れます．内部的にはコンスセル構造のみを使用しているにも関わらず，プログラムコードにおけるデータ構造の構築・参照では空白区切りの連結リストとして利用可能です．

Chibi-Scheme0.9.1

> (quote (a b c))
(a b c)
> (quote (a . (b . (c . ()))))
(a b c)
> (quote ((a . 1) (b . 2) (c . 3)))
((a . 1) (b . 2) (c . 3))
> (quote ((a . 1) . ((b . 2) . ((c . 3) . ()))))
((a . 1) (b . 2) (c . 3))
> (car (quote ((a . 1) (b . 2) (c . 3))))
(a . 1)
> (car (cdr (quote ((a . 1) (b . 2) (c . 3)))))
(b . 2)
> (car (car (cdr (quote ((a . 1) (b . 2) (c . 3))))))
b
> (cdr (car (cdr (quote ((a . 1) (b . 2) (c . 3))))))
2

連想リストと属性リスト

ここまで見ると，少なくともデータ構造の操作コストや，ポインタを格納するセルの数については，配列の方が圧倒的に少なく済みます．ですが，コンスセルまたは配列のみでキーと値のセットを扱う場合はどうなるでしょうか？次の図は，上から順に，コンスセル構造による連想リスト，コンスセル構造による属性リスト，配列構造による属性リストの内部構造を示したものです．

この場合でも，連想リストよりも属性リスト，コンスセル構造よりも配列構造の方がやはり消費セル数が少なくなります．ここで，キー検索によってペア構造を取り出すプログラムを考えてみます．

連想リスト／コンスセル構造（Prolog）

myasso(_, [], false) :- !.
myasso(K, [[K|V]|_], [K|V]) :- !.
myasso(K, [_|V], R) :- myasso(K, V, R).

?- myasso(b, [[a|1],[b|2],[c|3]], R).
R = [b|2].

属性リスト／コンスセル構造（Prolog）

myprop(_, [], false) :- !.
myprop(K, [K,V|_], [K,V]) :- !.
myprop(K, [_,_|V], R) :- myprop(K, V, R).

?- myprop(b, [a,1,b,2,c,3], R).
R = [b, 2].

属性リスト／配列構造（Python）

def myprop(k, v):
    if v == []: return False
    elif k == v[0]: return [k, v[1]]
    else: return myprop(k, v[2:])

>>> myprop('b', ['a',1,'b',2,'c',3])
['b', 2]

属性リスト，特に配列構造の場合のセル参照・構築コストが大きくなります．ここで，検索キーは呼び出し元にあるということで，値のみ返すように修正してみましょう．

連想リスト／コンスセル構造（Prolog）

myasso(_, [], false) :- !.
myasso(K, [[K|V]|_], V) :- !.
myasso(K, [_|V], R) :- myasso(K, V, R).

?- myasso(b, [[a|1],[b|2],[c|3]], R).
R = 2.

属性リスト／コンスセル構造（Prolog）

myprop(_, [], false) :- !.
myprop(K, [K,V|_], V) :- !.
myprop(K, [_,_|V], R) :- myprop(K, V, R).

?- myprop(b, [a,1,b,2,c,3], R).
R = 2.

属性リスト／配列構造（Python）

def myprop(k, v):
    if v == []: return False
    elif k == v[0]: return v[1]
    else: return myprop(k, v[2:])

>>> myprop('b', ['a',1,'b',2,'c',3])
2

ある意味当たり前ですが，構築コストに違いが見られなくなりました．最後に，連想リスト／属性リストを構築する場合の処理を見てみます．

連想リスト／コンスセル構造（Prolog）

myalist([], _, []) :- !.
myalist(_, [], []) :- !.
myalist([A|K], [B|V], [[A|B]|R]) :- myalist(K, V, R).

?- myalist([a,b,c], [1,2,3], R).
R = [[a|1], [b|2], [c|3]].

属性リスト／コンスセル構造（Prolog）

myplist([], _, []) :- !.
myplist(_, [], []) :- !.
myplist([A|K], [B|V], [A,B|R]) :- myplist(K, V, R).

?- myplist([a,b,c], [1,2,3], R).
R = [a, 1, b, 2, c, 3].

属性リスト／配列構造（Python）

def myplist(k, v):
    if k == [] or v == []: return []
    else: return [k[0],v[0]] + myplist(k[1:], v[1:])

>>> myplist(['a','b','c'], [1,2,3])
['a', 1, 'b', 2, 'c', 3]

違いが全く見られなくなったと言っていいでしょう．実際には，配列構造は添字参照が可能ですので，要素参照はコンスセル構造と比べて速くなります．ただ，属性リストはペア構造がないため取り出しコストがぐっと高くなります．PrologやLISPがコンスセルのみであらゆるデータ構造を表現するのに対し，Python/Ruby/JavaScriptなどの主要スクリプト言語やデータ記述を目的とするJSONなどが，最初からペア構造と配列構造を併用しているのは，このあたりに理由があるのかもしれません．

連想リストと辞書型・連想配列・ハッシュテーブル

PythonやJSONで用意されるペア構造は，LISP系のコンスセル構造に基づく連想リストと同じ使われ方がされることがほとんどです（あくまで歴史的な経緯であり，ペア構造がLISP発祥，というわけではありません）．特にPythonの辞書型については，多くのLISP処理系の連想リストと同じく，大域・局所環境の名前管理にそのまま用いられています．

Python3.7.3

>>> x = 10
>>> def plusone(x): return x + 1
... 
>>> plusone(x)
11
>>> globals()['plusone']
<function plusone at 0x7f1588f42510>
>>> globals()['x']
10
>>> globals()['plusone'](globals()['x'])
11

このため，LISP処理系実装でもこの辞書型を使えば，評価器の一部，特にapply相当の実装がとても楽になります．Peter Norvig氏のlis.pyの実装を参考にすると，たとえばquoteとcar/cdr/consの実装例は次のようになります．

Python3.7.3

>>> genv = {
...   'car': lambda x: x[0],
...   'cdr': lambda x: x[1:],
...   'cons': lambda x,y: [x] + y
... }
>>> def myeval(s):
...     if s[0] == 'quote': return s[1]
...     else: return genv[s[0]](*[myeval(x) for x in s[1:]])
...
>>> myeval(['car',['quote',['a','b','c']]])
'a'
>>> myeval(['cdr',['quote',['a','b','c']]])
['b', 'c']
>>> myeval(['car',['cdr',['quote',['a','b','c']]]])
'b'
>>> myeval(['cons',['quote','a'],['quote',['b','c']]])
['a', 'b', 'c']

ただし，内部データ構造は配列構造のままです．内部構造にも辞書型を活用したいところですが，LISPの連想リストがコンスセルの連結リスト（その連結リストもコンスセルで構成）なのに対し，辞書型はその名の通り，添字に連番以外が使用できるよう作られた，順番のないキーと値のペアの集合です．他の言語では連想配列，ハッシュテーブルとも呼ばれていますが，連想リストと異なり，その目的専用で実装されているため，逆に，連想リスト以外にも使用するコンスセル構成に利用できないのが難しいところです．

連結リストのみのLISP処理系実装

名前環境の検索は値のみを返すことができれば良いのだとすると，少なくとも最小構成のLISP評価器を構成する際に明確なペア構造は必要ないことになります．むしろ，配列構造による属性リストで実装した方がセル消費・参照コストが低く，加えて，添字参照による高速処理も期待できます．また，ラムダ式を関数適用する際には，引数と値を束縛する名前環境を生成する必要がありますが，連想リストと生成コストが同じであり，上記の通り検索時には値のみを結果として受け取れば良いのであれば，属性リストでも問題がなくなります．

…ということで（？），次のコードは，上記を踏まえてPythonで実装した，Schemeサブセット（lambda quote cond car cdr eq?）のプログラムコードを実行する評価器の例です．なお，純LISP基本関数相当とかにこだわらず，Pythonの各種構文・関数を使用している他，S式入出力部の実装はなく，配列構造によってプログラムコードを表現しています．そのため，コード自体は20行もありません．前節の実装例と異なり，大域環境も属性リストで表現していることに御注意下さい．

mylisp.py

def myprop(k, v): return v[1] if k == v[0] else myprop(k, v[2:])
def myplist(k, v): return [x for a in map(lambda a,b: [a,b], k, v) for x in a]

genv = ['car', lambda x: x[0], 'cdr', lambda x: x[1:],
        'eq?', lambda x,y: x == y, 'else', True]

def evcond(p, e):
    return myeval(p[0][1], e) if myeval(p[0][0], e) else evcond(p[1:], e)

def myeval(s, e):
    if isinstance(s, str): return myprop(s, e + genv)
    else:
        if   s[0] == 'quote': return s[1]
        elif s[0] == 'cond': return evcond(s[1:], e)
        elif s[0] == 'lambda': return s + [e]
        else:
            f = myeval(s[0], e)
            a = [myeval(x, e) for x in s[1:]]
            if callable(f): return f(*a)
            else: return myeval(f[2], myplist(f[1], a) + f[3])

実行例は次の通り．myprop相当の処理を行っています．

>>> myeval(
... [[['lambda', ['u'], ['u', 'u']],
...   ['lambda', ['u'],
...     ['lambda', ['k', 'v'],
...       ['cond', [['eq?', 'k', ['car', 'v']],
...                 ['car', ['cdr', 'v']]],
...                ['else', [['u', 'u'], 'k', ['cdr', ['cdr', 'v']]]]]]]],
...  ['quote', 'c'],
...  ['quote', ['a', '1', 'b', '2', 'c', '3', 'd', '4', 'e', '5']]], [])
'3'
>>> myeval(
... [[['lambda', ['u'], ['u', 'u']],
...   ['lambda', ['u'],
...     ['lambda', ['k', 'v'],
...       ['cond', [['eq?', 'k', ['car', 'v']],
...                 ['car', ['cdr', 'v']]],
...                ['else', [['u', 'u'], 'k', ['cdr', ['cdr', 'v']]]]]]]],
...  ['quote', 'b'],
...  ['quote', ['a', '1', 'b', '2', 'c', '3', 'd', '4', 'e', '5']]], [])
'2'

備考

記事に関する補足

• 考察だけじゃなかったんかい（滅）．ちなみに，上記評価器にconsとpair?を加え，プログラムコードのS式から配列構造への変換を行えば，この評価器自身に対する超循環評価器となるはずです．でも『20行もありません』と書きたかったので削った．

• Pythonに差し替える前のClojureによるシンプルな評価器実装がもったいないのでここに残す．

mylisp.clj

(defn myplist [k v] (reduce concat (map list k v)))
(defn myprop [k v] (cond (= k (first v)) (fnext v) :else (myprop k (nnext v))))

(defn myeval [s e]
  (cond (seq? s)
        (cond (= (first s) 'quote) (fnext s)
              (= (first s) 'cond)
              (((fn [u] (u u)) (fn [u] (fn [p]
                  (cond (or (= (ffirst p) 'else) (myeval (ffirst p) e))
                        (myeval (first (nfirst p)) e)
                        :else ((u u) (rest p)))))) (rest s))
              (= (first s) 'lambda) (concat s (cons e ()))
              :else (let [f (myeval (first s) e) a (map (fn [x] (myeval x e)) (rest s))]
                      (cond (seq? f)
                            (myeval (nth f 2) (concat (myplist (fnext f) a) (nth f 3)))
                            :else (cond (= f 'car) (first (first a))
                                        (= f 'cdr) (rest (first a))
                                        (= f 'eq?) (= (first a) (fnext a))))))
        :else (myprop s (concat e '(car car cdr cdr eq? eq?)))))

(println (myeval (read) ()))

更新履歴

• 2021-07-22：連想リストと連想配列等との関連について追加
• 2021-07-22：記述例をScheme→Prolog，Clojure→Pythonに変更
• 2021-07-21：初版公開