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

【追記】[簡易LISP処理系の各プログラミング言語実装例](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)の記事作成に伴い，こちらの記事の更新は無期延期としたいと思います．

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

* [7 lines of code, 3 minutes: Implement a programming language from scratch](http://matt.might.net/articles/implementing-a-programming-language/)

> (λ 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式の字句・構文解析（パース）をしてくれる．

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

* 環境用の連想リスト

`assq`でOK．

```scheme
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`を呼び出す．

```scheme
(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)`となる．

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

* リスト構造の出力

`display`をそのまま使用．

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

* 動作確認

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

#Python（Python 3，Python2）

* リスト構造の入力

[こちら](http://norvig.com/lispy.html)の`read_from_tokens()`のパクリ．エラー処理は亡き者にされた．

```python
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)
```
```python
>>> readlist('(hoge hage (hige (foo bar)) baz)')
('hoge', 'hage', ('hige', ('foo', 'bar')), 'baz')
```

* 環境用の連想リスト

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

```python
def assoc(k, vl):
    if not vl: return False
    elif vl[0][0] == k: return vl[0]
    else: return assoc(k, vl[1:])
```
```python
>>> 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]`なのは定番（普通は逆）．

```python
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実装の解説参照）．

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

* リスト構造の出力

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

```python
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]
```
```python
>>> writelist(('a', 'b', ('c', 'd'), (('e', 'f'), ('g', 'h'))))
'(a b (c d) ((e f) (g h)))'
```

* 動作確認

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

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

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

```python
>>> 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](http://matt.might.net/articles/implementing-a-programming-language/)
* Peter Norvig：[(How to Write a (Lisp) Interpreter (in Python))](http://norvig.com/lispy.html)
* Qiita：[Pythonのリスト内包表記はチューリング完全だから純LISPだって実装できる](https://qiita.com/t-sin/items/662b055447ec87476384)

##記事に関する補足
* Scheme版はGauche，GNU Guile，SCMで確認．SCMでは『\』が使えなかった…．

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