LoginSignup
25
27

More than 1 year has passed since last update.

@ytaki0801(Yozo TAKIZAWA)

簡易LISP処理系の実装例【各言語版まとめ】

Last updated at Posted at 2020-09-16

【2021-04-17追記】下記実装例のうち，C言語版についても，SICP実装例に準拠したレキシカルスコープを採用した評価器として書き直し，更に，スクリーンエディタKiloにS式評価（GNU Emacsでいうsexp-last-eval）と括弧対応表示の機能と共に組み込んだソフトウェアとして GutHub開発・公開に移行 しました．
【2020-11-09追記】下記実装例のうち，JavaScript版についても，SICP実装例に準拠したレキシカルスコープ，および，HTML入力フォームを用いた簡易REPLを想定して書き直し，Webブラウザから利用 できるようにしました．
【2020-10-21追記】下記実装例のうち，シェルスクリプト／大域変数版については可搬性・有用性が高いと判断し，SICP実装例に準拠したレキシカルスコープ，および，簡易REPLを採用したソフトウェアとして GitHub開発・公開に移行 しました．

この記事は，様々なプログラミング言語で，最低限のS式入出力およびリスト処理を実装した上で，John McCarthy氏の原初のLISPインタプリタ記述をPaul Graham氏がCommon Lispで実装した"McCarthy's Original Lisp"（jmc.lisp）について，各言語向けに移植・動作確認してみた記述例のリンク集および共通解説をまとめたものです．

なお，複数の種類の括弧を用いた記述の簡易パーサ，基本リスト処理のみを実装した例をまとめた記事もあり，こちらの記述から抜粋・修正して組み込んでいる場合もあります．

この記事の方が新しく，少しずつ整理していますが，各リンク先記事との整合性が合っていなかったり，記述や説明が重複していたりする箇所があるかもしれません．御了解いただけますと幸いです．

実装例の趣旨

LISP系言語については，開発当初より『LISP自身でそのLISP処理系を記述する』という，超循環評価器（meta-circular evaluator）としての実装が行われています．最低限の機能をもったLISP処理系であればそのような実装は可能であり，しかも，その評価器の仕組みはとても簡単です．McCarthy's Original Lispの他，SICP 4.1など，Webでも多くの記述例が公開されています．

これらを参照すれば，LISP系以外の他のプログラミング言語でも，超循環評価器としての性質をもつ同じLISP処理系が容易に実装でき，言語処理系実装の入門用として最適…のはずなのですが，LISP処理系ならば標準で装備している，字句・構文を規定する『S式』の入出力処理，および，S式に基づく基本リスト処理（car，cdr，cons，eq，atom）の実装の方が開発言語ごとの手間が圧倒的にかかり，それが敷居になっているところがあります．

そこで，各プログラミング言語で簡単なS式入出力および基本リスト処理の実装例を別途作成し，"McCarthy's Original Lisp"を可能な限りそのまま移植・動作確認することで，言語処理系実装の最初の敷居を下げてみよう，というのが，今回の各実装例の趣旨です．

処理系の概要

次のサンプルの通り，名前付けや関数定義の記述方法がなく，ひとつのまとまったS式のみの処理を行うものですが，ダイナミックスコープということもあり，lambda式を用いて再帰関数を定義して利用することも可能です（SchemeのletrecやCommon Lispのlabelsなどの代わり）．

(car (cdr '(10 20 30)))
=> 20

((lambda (x) (car (cdr x))) '(abc def ghi))
=> def

((lambda (f x y) (f x (f y '()))) 'cons '10 '20)
=> (10 20)

((lambda (f x y) (f x (f y '())))
 '(lambda (x y) (cons x (cons y '())))
 '10 '20)
=> (10 (20 ()))

((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"を基にした，超循環評価器としての性質をもつLISP処理系
  • 数字を含むアトムは全てシンボルとし，変数の値とする場合はquote（'）を使用
  • 構文としてquoteの他，condとlambdaが使用可能
  • 組込関数：cons car cdr eq atom（内部でコンスセルを作成）
  • 真偽値はt（真），および，nil（偽）＝空リスト（＝NULL相当）
  • 評価器実装専用として，caarやassocなどのユーティリティ関数を定義
  • エラーチェックなし，モジュール化なし，ガーベジコレクションなし

また，S式入出力およびリスト処理実装の構成は次の通り．

  • 基本リスト処理：cons car cdr eq atom
  • S式字句解析：1行の文字列から( ) 'を字句として，空白を区切り記号として，文字列配列を生成
  • S式構文解析：( )の括りをconsでリスト化，'は(quote ...)を挿入，.はコンスセルを生成
  • S式出力：ドット対簡略その他の表現に基づくリスト構造などを表示，または，文字列として出力
  • REP (no Loop)：文字列1行読み込み→S式抽象構文木生成→評価→S式出力をまとめた関数を定義

実装上の最大のネックは（意外にも）コンスセルであり，特に静的型付き言語では，最小限のアトムとしての文字列とコンスセル自身の双方を参照できる『セル』の実装が非常に困難であるケースが見られます．また，動的型付き言語でも，内部で構成したコンスセル構造の中身がそのままでは表示できず，コンスセル実装とセットでS式出力部を作成する方が良い場合があります．

評価器の解説

s_evalの処理内容を箇条書きにすると，次のようになります．なお，元の"jmc.lisp"と異なり，label機能は省いています．

  • 引数としてS式eと環境変数をとる．
  • eが真偽値を示す文字列ならば所定の真偽値を返す．
  • eがリスト構造ではないならば束縛変数とみなし，対応する値を環境変数から取得して返す．
  • eがリスト構造であり，先頭の要素e1がリスト構造ではないならば，次の処理を行う．
    • e1がquoteならば，eの2番目の要素をそのまま値として返す．
    • e1がatom eq car cdr consならば，引数要素を評価した後に関数適用を行い，その結果を返す．
    • e1がcondならば，条件式と処理を組にしたリストをevconに渡し，その結果を返す．
    • それ以外の場合は，e1を束縛済み変数とみなし，対応する値（lamda式を含む）を環境変数から取得してeの先頭要素として置き換え，あらためて評価した結果を返す．
  • e1もリスト構造であり先頭の要素がlambdaならば，lambda式の値適用とみなし，次の処理を行う．
    • 適用する値要素をリストにしたものをevlisに渡し，それぞれの要素が評価された結果を再度リストとして受け取る．
    • lambda式の各引数と評価済の各値要素を対応付けたリストを作り，環境変数に追加する．
    • lambda式の処理本体を，更新後の環境変数を用いて評価した結果を返す．
  • eが上記以外の構成の場合は，エラーとして()を返す．

肝となるのは，lambda式を別のlambda式の引数に束縛した後の，lambda式の値適用，たとえば，

(s_eval '((lambda (f) (f '(a b c))) '(lambda (x) (cdr x))) '()))
=> (s_eval '(f '(a b c)) '((f (lambda (x) (cdr x))) . ()))
=> (s_eval '((lambda (x) (cdr x)) '(a b c)) '((f (lambda (x) (cdr x))) . ()))
=> (s_eval '(cdr x) '((x (a b c)) (f (lambda (x) (cdr x))) . ()))
=> (cdr (s_eval 'x '((x (a b c)) (f (lambda (x) (cdr x))) . ())))
=> (cdr '(a b c))
=> (b c)

のように実行されていく処理でしょうか．環境変数内でlambda式に名前が付くことによって，その名前で自分自身を呼び出す再帰処理が定義可能です．

環境変数は，引数持ち回りとはいえ，ひとつのみです．ですのでダイナミックスコープとなるのですが，今回の評価器は，lambda式のみのS式はエラーとし（というよりも，真偽値およびクォートされた記述以外は値としてそのまま返さない），lambda式の処理本体としてlambda式を記述する，すなわち，lambda式を返すlambda式は処理できません．高階関数機能としては，いわゆる第二級オブジェクト相当となります．

実のところ，真偽値のように，lambda式のみの場合はそのまま返すこともできなくはないのですが，lambda式内にローカル環境変数を保持する，クロージャ機能を実装したレキシカルスコープとしないと，名前衝突（funarg）の問題が起きます．そして，レキシカルスコープ（クロージャ機能実装）とするには，lambda式の生成と実行のタイミングを考慮した評価器としなければならず，根本的な作り直しが必要となります．

備考

記事に関する補足

  • 趣旨としては他にも，簡易処理系とはいえ，ホスト言語の様々な機能を活用しないと実装できないことから，その言語を本格的に学ぶための題材として適切な種類と規模，というのもあります．とりあえず，Haskellのリストモナドの妙なクセは一通りわかった（えっ）．

  • 上記を踏まえると，最小構成とはいえ立派な言語処理系なので，今回の内容を参考にあらためて書き換えや機能強化をやってみることで，その言語をそれなりに活用できることを示すのにもいいんじゃないかなあとか．たとえば，他分野の人がプログラミング系職種への転職を考えた場合，面接とかで

面接員「履歴書には◯◯言語ができると書かれていますが，どの程度習得されているのですか？」
あなた「そうですねえ，ごく簡単な言語処理系の実装程度でしょうか」
面接員「その実装言語の仕様は？（パーサライブラリ使った電卓プログラム写経かな）」
あなた「えっと，少なくとも再帰手続きが定義できますかね」
面接員「！？」
あなた「いやあ，字句解析も抽象構文木生成もライブラリ使わずだったのでちょっと大変でした」
面接員「！？」

とかいうハッタリをかますのにちょうどいいというか．あながち嘘じゃないし．え，僕ですか？僕は今回の内容は『どんな言語でもできて当たり前，むしろ時間かかりすぎ＆無駄多すぎ，エラーチェックなしとかなめてんのか』と言われる立場なので…はい．

  • 実行サンプルのScheme版，Common Lisp版はそれぞれ次の通り．
sample.scm
(car (cdr '(10 20 30)))
=> 20

((lambda (x) (car (cdr x))) '(abc def ghi))
=> def

((lambda (f x y) (f x (f y '()))) cons '10 '20)    ; 引数として渡された関数名はクォートする必要がない
=> (10 20)

((lambda (f x y) (f x (f y '())))
 (lambda (x y) (cons x (cons y '())))    ; 引数として渡されたlambda式もクォートする必要がない
 '10 '20)
=> (10 (20 ()))

(letrec ((assoc_ (lambda (k v)
                      (cond ((eq? v '()) '())
                            ((eq? (car (car v)) k)
                             (car v))
                            (else (assoc_ k (cdr v)))))))
  (assoc_ 'Orange
          '((Apple . 120) (Orange . 210) (Lemon . 180))))
=> (Orange . 210)
sample.lsp
(car (cdr '(10 20 30)))
=> 20

((lambda (x) (car (cdr x))) '(abc def ghi))
=> DEF    ; シンボルとしてのアルファベット表示は全て大文字となる

((lambda (f x y) (funcall f x (funcall f y '()))) 'cons '10 '20)    ; 引数として渡された関数はfuncallを用いて実行
=> (10 20)

((lambda (f x y) (funcall f x (funcall f y '())))    ; 引数として渡されたlambda式はfuncallを用いて実行
 (lambda (x y) (cons x (cons y '())))    ; lambda式はクォートする必要がない
 '10 '20)
=> (10 (20 NIL))

(labels ((assoc_ (k v)
           (cond ((eq v '()) '())
                 ((eq (car (car v)) k)
                  (car v))
                 (t (assoc_ k (cdr v))))))
  (assoc_ 'Orange
          '((Apple . 120) (Orange . 210) (Lemon . 180))))
=> (ORANGE . 210)

更新履歴

  • 2021-04-17：冒頭にC言語版の評価器書き直しおよびKiloへの組込みについて追記
  • 2020-11-09：冒頭にJavaScript版の評価器書き直しおよびWebブラウザからの利用について追記
  • 2020-10-29：評価器の解説のレキシカルスコープに関する記述を修正
  • 2020-10-21：冒頭にシェルスクリプト／大域変数版のGitHub開発・公開への移行について追記
  • 2020-10-12：処理系の概要に，実装上のネックに関する補足を追加
  • 2020-10-12：各言語版リンクを動的型付き系・静的型付き系・LISP系で分類
  • 2020-09-18：備考欄に余計な補足を追記
  • 2020-09-16：評価器の解説を追加
  • 2020-09-16：初版公開　※実装言語が増えた場合はリンクのみ更新して履歴には記録しない予定
25
27
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
25
27