Help us understand the problem. What is going on with this article?

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

この記事は,様々なプログラミング言語で最低限の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) (Lemmon . 180)))
=> (Orange . 210)

評価器本体の実装内容は次の通り.

  • "McCarthy's Original Lisp"を基にした,超循環評価器としての性質をもつLISP処理系
  • 数字を含むアトムは全てシンボルとし,変数の値とする場合はquote')を使用
  • 構文としてquoteの他,condlambdaが使用可能
  • 組込関数:cons car cdr eq atom(内部でコンスセルを作成)
  • 真偽値はt(真),および,nil(偽)=空リスト(=NULL相当)
  • 評価器実装専用として,caarassocなどのユーティリティ関数を定義
  • エラーチェックなし,モジュール化なし,ガーベジコレクションなし

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

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

評価器の解説

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

  • 引数としてS式eと環境変数をとる.
  • eが真偽値を示す文字列ならば所定の真偽値を返す.
  • eがリスト構造ではないならば束縛変数とみなし,対応する値を環境変数から取得して返す.
  • eがリスト構造であり,先頭の要素e1がリスト構造ではないならば,次の処理を行う.
    • e1quoteならば,eの2番目の要素をそのまま値として返す.
    • e1atom eq car cdr consならば,引数要素を評価した後に関数適用を行い,その結果を返す.
    • e1condならば,条件式と処理を組にしたリストをevconに渡し,その結果を返す.
    • それ以外の場合は,e1をlambda式の束縛変数とみなし,対応するlambda式を環境変数から取得して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式内のローカル環境変数の値を適用できませんから,再帰処理定義のためには,グローバルな環境変数に変数束縛を直接追加する構文や,Yコンビネータのような不動点コンビネータが必要となってきます.

備考

記事に関する補足

  • 趣旨としては他にも,簡易処理系とはいえ,ホスト言語の様々な機能を活用しないと実装できないことから,その言語を本格的に学ぶための題材として適切な種類と規模,というのもあります.とりあえず,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) (Lemmon . 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) (Lemmon . 180))))
=> (ORANGE . 210)

更新履歴

  • 2020-09-18:備考欄に余計な補足を追記
  • 2020-09-16:評価器の解説を追加
  • 2020-09-16:初版公開 ※実装言語が増えた場合はリンクのみ更新して履歴には記録しない予定
ytaki0801
``Don't feel as if the key to successful computing is only in your hands.'' -- Alan J. Perlis
http://nbk.bz/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした