LISPC（発表用資料）

動機

私の読んでいるStructures and Interpretations of Computer Programs (SICP) (https://www.vocrf.net/docs_ja/jsicp.pdf) の4章ではLispのInterpreterを何個も実装する．その時に”Lispは普通Interpreter上で動作するが，頑張ればCompilerも作れるのでは？”と思い立ったのがきっかけ．

基礎知識

インタープリタ

プログラムを一行ずつ逐次解釈しながら実行を進めるソフトウェア．

コンパイラ

プログラムをそのプログラミング言語よりも低レベルな言語（アセンブリや機械語）へ翻訳するソフトウェア．

動的型付け

変数の型を実行時に動的に付ける方式．Pythonなどで利用されている．

静的型付け

変数の型が実行前にすべて決定されている方式．C言語などで利用されている．

クロージャ

関数と関数の作られた環境のペアからなる関数オブジェクト．関数実行時に作られた環境やさらにその環境よりも外側の環境の変数をキャプチャすることができる．LispやPythonでは言語レベルでサポートされているが，C言語などではサポートされていない（C++ではSTLを用いることにより表現可能．）．

環境モデル

手続き型プログラミングの実行過程を表現したモデル（SICPで登場．）．クロージャなどの仕組みを視覚的に理解することができる．

機能

すべてのLispの機能を一人で短期間で実装するのは非常に厳しいので今回は条件分岐や手続きなど基本的な機能に加え，個人的に実装したい機能のみを実装した． 今回実装した少し特殊な機能は動的型付けとクロージャである． また，今回はyaccなどの既存ツールを一切用いず，純粋にlibcのみを用いて実装した． また，本当はArmをジェネレートする予定であったが途方もなかったので今回はCをジェネレートしている．

動的型付け

これの実装は比較的簡単で出力先の言語ですべての型をオブジェクトとして扱うようにするだけである．本当はラップしたオブジェクトに型の種類を登録しておき，もっと型セーフな言語にしたかったが今回は実装できていない．

クロージャ

今回の実装の肝である．実装の指針としてはSICP中で出てきた環境モデルで考えながら実装を進めた．具体的にはProcedureは関数へのポインタと作られた環境へのポインタとのペアで表現されるというものである． また，クロージャを使うと必然的に環境を保存しておく必要があるためスタックを用いることが難しい．そのため，環境を表すオブジェクトを用いるのだが，その環境オブジェクトはすべて保存しておく必要はなく，不要なものはメモリを解放していく必要がある．そのため，GCなどの何らかのメモリを解放する機構が必要となる．しかし，今回は実装できていない．

クロージャをサポートする手続きがあればリストを実装することができるという話

この話は初見では直感に反することだと思う． なぜなら，リストのように複数の値をまとめて格納するには，格納できる分のメモリ空間が必要であり，そのメモリ空間はmallocなどを使って確保されなければならないと感じるからである． しかし，その直感に反してクロージャをサポートする手続きがあればリストを表現することができるということが言える． まず，リストは動的型付けであれば複数のペア（2つの値のみを保存可能）によって表現できるということを説明する．ペアの操作には以下の手続きを用いる．

(cons a b) ;aとbからなるペアを作成する
(car p) ;pairの1つ目の要素（上で言うa）を取得する
(cdr p) ;pairの2つ目の要素（上で言うb）を取得する

例えばpairのcar側に現在の値，pairのcdr側に次のpairのポインタを格納していけば次々と長いデータのリストを表現することが可能である．リストの終端は何らかの終端子（例えばnull）とかを置けば良い．

(define lst (cons 0 (cons 1 (cons 2 (cons 3 null)))))
(print (car lst)) ;0
(print (caddr lst)) ;2 = (car (cdr (cdr lst)))

次にペアはクロージャをサポートした手続きを用いて実装が可能だということを説明する． ペアを表現するにはメッセージパッシングというテクニックを用いる． これのテクニックはペアに限らず任意のオブジェクトを手続きを用いて表現したい時に用いることのできるテクニックだ．

(define (make-pair a b)
	(lambda (m)
		(cond ((eq? m 'get-car) a)
			  ((eq? m 'get-cdr) b)
			  (else (error "Unknown method: MAKE-PAIR" m)))))

(define (cons a b) (make-pair a b))
(define (car p) (p 'get-car))
(define (cdr p) (p 'get-cdr))

つまり，この手法ではペアオブジェクトとして扱われる実体は実は手続きであるということになる．

今後やりたいこと

parserの書き直し，メモリ管理システムの実装，LLVMのGenerate，最適化，遅延評価の導入，必要呼びの正規順序評価版の作成．

メモリ管理システム

基本的に参照カウントでメモリを解放． 循環参照などはオブジェクトの数が一定数を超えたらGC（mark and sweep）を実行して解放．