jmc.lispをjmc.scmに書き直してみた

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

"jmc.lisp"とは，[John McCarthy氏の原初のLISPインタプリタ記述](http://www-formal.stanford.edu/jmc/recursive/recursive.html)を，[Paul Graham氏がCommon Lispで実装したもの](http://paulgraham.com/lispcode.html)です．[概要](https://ja.wikipedia.org/wiki/%E7%B4%94LISP)は次の通り．

* 実装は`quote` `atom` `eq` `cons` `car` `cdr` `cond` `defun`を使用
* 機能は`quote` `atom` `eq` `cons` `car` `cdr` `cond` `lambda` `label`を提供

jmc.lispをGNU Emacs（今回に限ってはEmacs Lispと同じ構文・基本関数で書かれているため）で実行した例は次の通り．

```emacs-lisp
*** Welcome to IELM ***  Type (describe-mode) for help.
ELISP> (load "~/tmp/jmc.lisp")
t
ELISP> (eval. '((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)
```

ダイナミックスコープということもあり，実行例ではlambda式を`letrec`（Scheme）や`labels`（Common Lisp）などの代わりに使用しています（つまり，`label`はなくても良い）．

#jmc.scm
これを，Schemeで書き直してみたというのがこの記事の主旨です．

* 実装は`quote` `pair?` `eq?` `cons` `car` `cdr` `cond/else` `define` `#t` `#f`を使用
* 機能は`quote` `pair?` `eq?` `cons` `car` `cdr` `cond/else` `lambda` `#t` `#f`を提供

```Scheme
(define (atom. x)
  (and. (not. (null. x)) (not. (pair? x))))

(define (null. x)
  (eq? x '()))

(define (and. x y)
  (cond (x (cond (y #t) (else #f)))
        (else #f)))

(define (not. x)
  (cond (x #f)
        (else #t)))

(define (append. x y)
  (cond ((null. x) y)
        (else (cons (car x) (append. (cdr x) y)))))

(define (list. x y)
  (cons x (cons y '())))

(define (pair. x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom. x)) (not. (atom. y)))
         (cons (list. (car x) (car y))
               (pair. (cdr x) (cdr y))))))

(define (assoc. x y)
  (cond ((eq? (caar y) x) (cadar y))
        (else (assoc. x (cdr y)))))

(define (eval. e a)
  (cond
    ((eq? e '#t) #t)
    ((eq? e '#f) #f)
    ((eq? e 'else) #t)
    ((atom. e) (assoc. e a))
    ((atom. (car e))
     (cond
       ((eq? (car e) 'quote) (cadr e))
       ((eq? (car e) 'pair?) (pair?  (eval. (cadr e) a)))
       ((eq? (car e) 'eq?)   (eq?    (eval. (cadr e) a)
                                     (eval. (caddr e) a)))
       ((eq? (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq? (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq? (car e) 'cons)  (cons   (eval. (cadr e) a)
                                     (eval. (caddr e) a)))
       ((eq? (car e) 'cond)  (evcon. (cdr e) a))
       (else (eval. (cons (assoc. (car e) a) (cdr e)) a))))
    ((eq? (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(define (evcon. c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        (else (evcon. (cdr c) a))))

(define (evlis. m a)
  (cond ((null. m) '())
        (else (cons (eval. (car m) a)
                    (evlis. (cdr m) a)))))
```

[GNU Guile](https://www.gnu.org/software/guile/) 3.0を用いた実行例は次の通り．

```Scheme
$ guile
（起動時の表示はカット．プロンプトは"guile>"のみ）
guile> (load "./jmclisp.scm")
guile> (eval. '((lambda (assoc k v) (assoc k v))
...             '(lambda (k v)
...                (cond ((eq? v '()) #f)
...                      ((eq? (car (car v)) k)
...                       (car v))
...                      (else (assoc k (cdr v)))))
...             'Orange
...             '((Apple . 120) (Orange . 210) (Lemon . 180)))
...            '())
$1 = (Orange . 210)
```

#備考

##記事に関する補足
* `cadr`とかも使ってるのは御容赦を．jmc.lispでも未定義で使ってたりするし．
* jmc.scmで更にjmc.scmを記述できるはずだけど…~~実行が面倒そう．~~→[元の"jmc.lisp"でやってみました](https://qiita.com/ytaki0801/items/7a9d424ecac6932c5dd8)．
* 初期のLISP（≒jmc.lisp）がダイナミックスコープなのは[バグ](https://qiita.com/esumii/items/f077b951171e4f15c347)，というのは，開発者が意図していなかったという意味で，僕もそう思う（苦笑）．ラムダ式ならレキシカルスコープじゃないと辻褄が合わないし，なにより，必要ないはずの`label`が定義されていたあたりなんといいますか．まあ，おかげでこうして，超手軽に再帰処理を定義・実行できる処理系を，いろんなプログラミング言語でこれまた超手軽に定義・実行できるのだけれども．

##更新履歴
* 2020-09-14：備考欄に『jmc.lispでjmc.lispを実行してみた』記事について追記
* 2020-09-11：備考欄にダイナミックスコープに関する補足を追加
* 2020-09-08：初版公開