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

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

この記事は，下記拙作記事のRuby版を抜粋・修正したものを利用した，簡易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式入出力やリスト処理実装の方が開発言語ごとの手間が多く，それが敷居になっている人向けにまとめています．

#処理系の概要
実行例は次の通り．Ruby 2.5.5にて確認．

```shell
$ irb --simple-prompt
>> load "jmclisp.rb"
=> true
>> s_rep("(car (cdr '(10 20 30)))")
=> "20"
>> s_rep(gets.chomp)
((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`（偽）＝空リスト
* エラーチェックなし，モジュール化なし，ガーベジコレクションなし

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

#実装例

##ソースコード一式

```jmclisp.rb
####
#### 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) [x, y].freeze end
def car(s) s[0] end
def cdr(s) s[1] end
def eq(s1, s2) s1 == s2 end
def atom(s) s.is_a?(String) || eq(s, nil) || eq(s, true) || eq(s, false) end


#### S-expression input: s_read

def s_lex(s)
  for p in ['(',')','\''] do
    s = s.gsub(p, " #{p} ")
  end
  s.split
end

def s_syn(s)
  def quote(x, s)
    if s.length != 0 && s[-1] == '\'' then
      s.delete_at(-1)
      cons("quote", cons(x, nil))
    else x
    end
  end
  t = s.delete_at(-1)
  if t == ')' then
    r = nil
    while s[-1] != '(' do
      if s[-1] == '.' then
        s.delete_at(-1)
        r = cons(s_syn(s), car(r))
      else
        r = cons(s_syn(s), r)
      end
    end
    s.delete_at(-1)
    quote(r, s)
  else
    quote(t, s)
  end
end

def s_read(s) s_syn(s_lex(s)) end


#### S-expression output: s_string

def s_strcons(s)
  sa_r = s_string(car(s))
  sd = cdr(s)
  if eq(sd, nil) then sa_r
  elsif atom(sd) then "#{sa_r} . #{sd}"
  else "#{sa_r} #{s_strcons(sd)}"
  end
end

def s_string(s)
  if    eq(s, nil)   then "()"
  elsif eq(s, true)  then "t"
  elsif eq(s, false) then "nil"
  elsif atom(s) then s
  else "(#{s_strcons(s)})"
  end
end


#### JMC Lisp evaluator: s_eval

def caar(x) car(car(x)) end
def cadr(x) car(cdr(x)) end
def cadar(x) car(cdr(car(x))) end
def caddr(x) car(cdr(cdr(x))) end
def caddar(x) car(cdr(cdr(car(x)))) end

def s_null(x) eq(x, nil) end

def s_append(x, y)
  if s_null(x) then y
  else cons(car(x), s_append(cdr(x), y))
  end
end

def s_list(x, y) cons(x, cons(y, nil)) end

def s_pair(x, y)
  if s_null(x) and s_null(y) then nil
  elsif (not atom(x)) and (not atom(y))
    cons(s_list(car(x), car(y)), s_pair(cdr(x), cdr(y)))
  else nil
  end
end

def s_assoc(x, y)
  if eq(caar(y), x) then cadar(y)
  else s_assoc(x, cdr(y))
  end
end

def s_eval(e, a)
  if    eq(e, "t")   then true
  elsif eq(e, "nil") then false
  elsif atom(e) then s_assoc(e, a)
  elsif atom(car(e))
    if    eq(car(e), "quote") then cadr(e)
    elsif eq(car(e), "atom")  then atom(s_eval(cadr(e), a))
    elsif eq(car(e), "eq")    then eq(  s_eval(cadr(e), a), s_eval(caddr(e), a))
    elsif eq(car(e), "car")   then car( s_eval(cadr(e), a))
    elsif eq(car(e), "cdr")   then cdr( s_eval(cadr(e), a))
    elsif eq(car(e), "cons")  then cons(s_eval(cadr(e), a), s_eval(caddr(e), a))
    elsif eq(car(e), "cond")  then evcon(cdr(e), a)
    else s_eval(cons(s_assoc(car(e), a), cdr(e)), a)
    end
  elsif eq(caar(e), "lambda")
    s_eval(caddar(e), s_append(s_pair(cadar(e), evlis(cdr(e), a)), a))
  else print("Error")
  end
end

def evcon(c, a)
  if s_eval(caar(c), a) then s_eval(cadar(c), a)
  else evcon(cdr(c), a)
  end
end

def evlis(m, a)
  if s_null(m) then nil
  else cons(s_eval(car(m), a), evlis(cdr(m), a))
  end
end


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

##解説

* リスト処理：`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式出力部は新規に作成．内部では`nil`である空リストは`()`を，真偽値は`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`を定義．

#備考

##記事に関する補足
* 評価器のみの場合，~~約70行／1950バイトほど．Python版と比較して`then`と`end`の分だけが増えている感じ？~~コメントの御意見を受けて，ほぼ不要の``return``と一部の`then`を削除したところ，約60行／1560バイトほど．むしろPython版よりも小さくなったという．

##更新履歴
* 2020-09-11：ソースコードから不要な`return`等を削除（コメントより）
* 2020-09-11：実装例をソースコード一式＋解説の構成に変更
* 2020-09-11：初版公開