7行インタプリタ実装まとめ

【追記】簡易LISP処理系の各プログラミング言語実装例の記事作成に伴い，こちらの記事の更新は無期延期としたいと思います．

拙作まとめ／チートシート第四段．下記Webページを読んで，最初の7行インタプリタ（ラムダ計算）をPythonその他のプログラミング言語でも書いておこうと思ったのがきっかけ．このため，当面は，元言語のScheme記述と，Python記述のみ．

• 7 lines of code, 3 minutes: Implement a programming language from scratch

(λ x . x)
→ ((λ x . x))
((λ x . x) (λ a . a))
→ (λ a . a)
(((λ f . f) (λ g . g)) (λ a . a))
→ ((λ a . a))
(((λ f . (λ x . (f x))) (λ g . g )) (λ a . a))
→ ((λ a . a))

なお，この記事では，ラムダ記号は（『λ』ではなく）『/』を用いている．

移植作業（？）の都合上，構成は各言語ごとに次のパートに分かれている．ただし，既存関数との重複を避けるため，evalはeval7，applyはapply7の関数名としている．

• リスト構造の入力
• 環境用の連想リスト
• evalの実装
• applyの実装
• リスト構造の出力
• 動作確認

Scheme（処理内容の解説付き）（R5RS）

• リスト構造の入力

read一択．S式の字句・構文解析（パース）をしてくれる．

gosh> (read (open-input-string "(hoge hage (hige (foo bar)) baz)"))
(hoge hage (hige (foo bar)) baz)

• 環境用の連想リスト

assqでOK．

gosh> (assq 'a '((a 10) (b 20) (c 30)))
(a 10)

• evalの実装

式の評価部．上記Webページのほぼコピペ．式eと環境envを受け取り，式eが変数ならば環境envから対応する値を取り出して戻し，式eが単独のラムダ式ならば値として環境envに追加して戻す，それ以外は，関数(car e)と関数に与える値(cadr e)のリストとみなし，関数・値それぞれを先に自己評価してから（applicative order），関数適用するためのapplyを呼び出す．

(define (eval7 e env)
  (cond ((symbol? e)      (cadr (assq e env)))
        ((eq? (car e) '/) (cons e env))
        (else             (apply7 (eval7 (car  e) env)
                                  (eval7 (cadr e) env)))))

• applyの実装

関数適用部．上記Webページのほぼコピペ．関数fと値xを受け取り，関数の変数(cadr (car f))と値xを対応付け，残りの未適用の値(cdr f)と併せて環境とし，関数本体の式(cddr (car f))と共に，式の評価部evalを呼び出す．

実装上の注意点として，入力されたラムダ式のピリオドの右側はSchemeでは自動的にドット対のcdr部となるので，たとえば，fが((/ a . (/ c . d)))の時の(cddr (car f))は，(. (/ c . d))ではなく(\ c . d)となる．

(define (apply7 f x)
  (eval7 (cddr (car f))
         (cons (list (cadr (car f)) x)
               (cdr f))))

• リスト構造の出力

displayをそのまま使用．

gosh> (display '((/ a . a)))
((/ a . a))#<undef>

• 動作確認

gosh> (display (eval7 (read) '()))
(((/ f . (/ x . (f x))) (/ g . g )) (/ a . a))
((/ a . a))#<undef>

Python（Python 3，Python2）

• リスト構造の入力

こちらのread_from_tokens()のパクリ．エラー処理は亡き者にされた．

def readlist(x):
    xl = x.replace('(', ' ( ').replace(')', ' ) ').split()
    def ret(ts):
        t = ts.pop(0)
        if t == '(':
            r = []
            while ts[0] != ')': r.append(ret(ts))
            ts.pop(0)
            return tuple(r)
        else:
            return t
    return ret(xl)

>>> readlist('(hoge hage (hige (foo bar)) baz)')
('hoge', 'hage', ('hige', ('foo', 'bar')), 'baz')

• 環境用の連想リスト

最初は辞書型を使おうと思ったが，λ評価の時に面倒なことになりそうだったので，タプル型想定で実装．

def assoc(k, vl):
    if not vl: return False
    elif vl[0][0] == k: return vl[0]
    else: return assoc(k, vl[1:])

>>> assoc('a', (('a', 10), ('b', 20), ('c', 30)))
('a', 10)

• evalの実装

添字大活躍．Scheme（LISP）の(car x),(cdr x),(cadr x)がPythonのx[0],x[1:],x[1]なのは定番（普通は逆）．

def eval7(e, env):
    if isinstance(e, str): return assoc(e, env)[1]
    elif e[0] == '/':      return (e,) + env
    else:                  return apply7(eval7(e[0], env), eval7(e[1], env))

• applyの実装

添字大活躍第二弾．cddr=[2:]ではなくcdddr=[3:]なのは'.'除去のため（Scheme実装の解説参照）．

def apply7(f, x): return eval7(f[0][3:][0], ((f[0][1], x),) + f[1:])

• リスト構造の出力

入力の逆．こちらはさすがに自作．最後の[:-1]はとても技巧的．

def writelist(x):
    def ret(xs):
        r = ('(')
        for t in xs:
            if isinstance(t, tuple):
                r += ret(t)
            else:
                r = r + t + ' '
        r = r[:-1] + ') '
        return r
    return ret(x)[:-1]

>>> writelist(('a', 'b', ('c', 'd'), (('e', 'f'), ('g', 'h'))))
'(a b (c d) ((e f) (g h)))'

• 動作確認

Python3の場合（input()を使う）．

>>> print(writelist(eval7(readlist(input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))

Python2の場合（raw_input()を使う）．

>>> print(writelist(eval7(readlist(raw_input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))

備考

参考文献

• Matt Might：7 lines of code, 3 minutes: Implement a programming language from scratch
• Peter Norvig：(How to Write a (Lisp) Interpreter (in Python))
• Qiita：Pythonのリスト内包表記はチューリング完全だから純LISPだって実装できる

記事に関する補足

• Scheme版はGauche，GNU Guile，SCMで確認．SCMでは『\』が使えなかった…．

変更履歴

• 2020-09-11：簡易LISP処理系の各プログラミング言語実装例の記事作成に伴い更新無期延期の旨冒頭に追記
• 2020-08-09：初版公開