簡易LISP処理系の実装例（Python版）

【他言語版へのリンク記事】[簡易LISP処理系の実装例【各言語版まとめ】](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)

この記事は，下記拙作記事のPython版を抜粋・修正したものを利用した，原初LISP処理系（["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)）の実装例をまとめたものです．

* [『括弧文字列』簡易パーサ実装例まとめ](https://qiita.com/ytaki0801/items/b8d7d4c778fe98966ce5)
* [リスト処理関数（cons,car,cdr,eq,atom）実装例まとめ](https://qiita.com/ytaki0801/items/a11c8143c5c63a406c7f)

最低限の機能をもったLISP処理系の実装の場合，本体である評価器（eval）実装はとても簡単であり，むしろ，字句・構文解析を行うS式入出力やリスト処理実装の方が開発言語ごとの手間が多く，それが敷居になっている人向けにまとめています．

# 処理系の概要
実行例は次の通り．Python2では`input()`を`raw_input()`に読み替えて下さい．

```lisp
$ python3 -i jmclisp.py
>>> s_rep("(car (cdr '(10 20 30)))")
'20'
>>> s_rep(input())
((lambda (x) (car (cdr x))) '(abc def ghi))
'def'
>>> s_rep("((lambda (f x y) (f x (f y '()))) 'cons '10 '20)")
'(10 20)'
>>> s_rep("((lambda (f x y) (f x (f y '())))     \
...        '(lambda (x y) (cons x (cons y '()))) \
...        '10 '20)")
'(10 (20 ()))'
>>> s_rep("((lambda (assoc k v) (assoc k v)) \
...        '(lambda (k v)                    \
...           (cond ((eq v '()) nil)         \
...                 ((eq (car (car v)) k)    \
...                  (car v))                \
...                 ('t (assoc k (cdr v))))) \
...        'Orange \
...        '((Apple . 120) (Orange . 210) (Lemon . 180)))")
'(Orange . 210)'
```

実装内容は次の通り．

* ["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)をベースにした評価器
* 数字を含むアトムは全てシンボルとし，変数の値とする場合は`quote`（`'`）を使用
* 構文として`quote`の他，`cond`と`lambda`が使用可能
* 組込関数：`atom` `eq` `cons` `car` `cdr`（内部でコンスセルを作成）
* 真偽値は`t`（真）および`nil`（偽）＝空リスト＝`None`
* エラーチェックなし，モジュール化なし，ガーベジコレクションなし

"McCarthy's Original Lisp"の詳細については[まとめ記事](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)を参照．ダイナミックスコープということもあり，実行例ではlambda式を`letrec`（Scheme）や`labels`（Common Lisp）などの代わりに使用しています．

#実装例

##ソースコード一式

```jmclisp.py
#
# JMC Lisp: defined in McCarthy's 1960 paper,
# with S-expression input/output and basic list processing
#


# basic list processing: cons, car, cdr, eq, atom

def cons(x, y): return (x, y)
def car(s): return s[0]
def cdr(s): return s[1]
def eq(s1, s2): return s1 == s2
def atom(s): return isinstance(s, str) or eq(s, None) or isinstance(s, bool)


# S-expression input: s_read

def s_lex(s):
    for p in "()'": s = s.replace(p, " " + p + " ")
    return s.split()

def s_syn(s):
    def quote(x):
        if len(s) != 0 and s[-1] == "'":
            del s[-1]
            return cons("quote", cons(x, None))
        else: return x
    t = s[-1]
    del s[-1]
    if t == ")":
        r = None
        while s[-1] != "(":
            if s[-1] == ".":
                del s[-1]
                r = cons(s_syn(s), car(r))
            else: r = cons(s_syn(s), r)
        del s[-1]
        return quote(r)
    else: return quote(t)

def s_read(s): return s_syn(s_lex(s))


# S-expression output: s_string

def s_strcons(s):
    sa_r = s_string(car(s))
    sd = cdr(s)
    if eq(sd, None):
        return sa_r
    elif atom(sd):
        return sa_r + " . " + sd
    else:
        return sa_r + " " + s_strcons(sd)

def s_string(s):
    if   eq(s, None):  return "()"
    elif eq(s, True):  return "t"
    elif eq(s, False): return "nil"
    elif atom(s):
        return s
    else:
        return "(" + s_strcons(s) + ")"


# JMC Lisp evaluator: s_eval

def caar(x): return car(car(x))
def cadr(x): return car(cdr(x))
def cadar(x): return car(cdr(car(x)))
def caddr(x): return car(cdr(cdr(x)))
def caddar(x): return car(cdr(cdr(car(x))))

def s_null(x): return eq(x, None)

def s_append(x, y):
    if s_null(x): return y
    else: return cons(car(x), s_append(cdr(x), y))

def s_list(x, y): return cons(x, cons(y, None))

def s_pair(x, y):
    if s_null(x) and s_null(y): return None
    elif (not atom(x)) and (not atom(y)):
        return cons(s_list(car(x), car(y)), s_pair(cdr(x), cdr(y)))

def s_assoc(x, y):
    if eq(caar(y), x): return cadar(y)
    else: return s_assoc(x, cdr(y))

def s_eval(e, a):
    if   eq(e, "t"):   return True
    elif eq(e, "nil"): return False
    elif atom(e): return s_assoc(e, a)
    elif atom(car(e)):
        if   eq(car(e), "quote"): return cadr(e)
        elif eq(car(e), "atom"):  return atom(s_eval(cadr(e), a))
        elif eq(car(e), "eq"):    return eq(  s_eval(cadr(e), a),
                                              s_eval(caddr(e), a))
        elif eq(car(e), "car"):   return car( s_eval(cadr(e), a))
        elif eq(car(e), "cdr"):   return cdr( s_eval(cadr(e), a))
        elif eq(car(e), "cons"):  return cons(s_eval(cadr(e), a),
                                              s_eval(caddr(e), a))
        elif eq(car(e), "cond"):  return evcon(cdr(e), a)
        else: return s_eval(cons(s_assoc(car(e), a), cdr(e)), a)
    elif eq(caar(e), "lambda"):
        return s_eval(caddar(e),
                      s_append(s_pair(cadar(e), evlis(cdr(e), a)), a))
    else: print("Error")

def evcon(c, a):
    if s_eval(caar(c), a): return s_eval(cadar(c), a)
    else: return evcon(cdr(c), a)

def evlis(m, a):
    if s_null(m): return None
    else: return cons(s_eval(car(m), a), evlis(cdr(m), a))


# REP (no Loop): s_rep
def s_rep(e): return s_string(s_eval(s_read(e), s_read("()")))
```

##解説

* リスト処理：`cons` `car` `cdr` `eq` `atom`
[先の記事](https://qiita.com/ytaki0801/items/a11c8143c5c63a406c7f)のタプル定義版をほぼそのまま抜粋．

* S式入力：`s_read`
[先の記事](https://qiita.com/ytaki0801/items/b8d7d4c778fe98966ce5)から，字句解析部を`()`および`'`の識別に変更（`s_lex`），抽象構文木生成部をドット対とクォート記号対応としつつ，リスト処理関数でコンスセルによる構文木を生成するよう変更（`s_syn`），それらをまとめたS式入力関数`s_read`を定義．

* S式出力：`s_string`
S式出力部は新規に作成．内部では`None`である空リストは`()`を，真偽値は`t` `nil`を出力するよう設定．

* 評価器：`s_eval`＋ユーティリティ関数
["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)をベースに`s_eval`関数およびユーティリティ関数を作成．

* REP (no Loop)：`s_rep`
`s_read`→`s_eval`→`s_string`をまとめた`s_rep`を定義．


#備考

##記事に関する補足
* 初版の[SICP 4.1](https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node76.html)ベースの評価器実装例（レキシカルスコープ／クロージャ対応）は，GitHubの[こちら](https://github.com/ytaki0801/Samples/blob/master/Scheme/implementations/FixLisp.py)に移動．なお，評価器のみの場合，[SICP 4.1](https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node76.html)版は約70行／2400バイトほど，現在の[jmc.lisp](https://qiita.com/ytaki0801/items/2d2a1edf371c103711bd)版は約50行／1900バイトほど．

##更新履歴
* 2020-10-21：リポジトリの位置の変更に伴いリンクを修正
* 2020-09-11：実装例をソースコード一式＋解説の構成に変更
* 2020-09-08：評価器実装を"McCarthy's Original Lisp"ベースに変更
* 2020-09-07：実行例を修正
* 2020-09-07：初版公開