【他言語版へのリンク記事】簡易LISP処理系の実装例【各言語版まとめ】

この記事は，下記拙作記事のRuby版を抜粋・修正したものを利用した，簡易LISP処理系（"McCarthy's Original Lisp"）の実装例をまとめたものです．

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

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

$ 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"の詳細についてはまとめ記事を参照．ダイナミックスコープということもあり，実行例では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
先の記事より，ほぼそのまま抜粋．
S式入力：s_read
先の記事から，字句解析部を()および'の識別に変更（s_lex），抽象構文木生成部をドット対とクォート記号対応としつつ，リスト処理関数でコンスセルによる構文木を生成するよう変更（s_syn），それらをまとめたS式入力関数s_readを定義．
S式出力：s_string
S式出力部は新規に作成．内部ではnilである空リストは()を，真偽値はt nilを出力するよう設定．
評価器：s_eval＋ユーティリティ関数
"McCarthy's Original Lisp"をベースに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：初版公開