Tomitomi's blog

勉強したこと、やってみたことなどを書き連ねていく場

Lispインタプリタ自作してみた。

先々週ぐらいにふと思い立って小規模なlispインタプリタを書き始めて、その後その上に関数実装するのにハマっていたのですが最近落ち着いてきたのでブログ記事にしました。

なぜ作った

clispLispやろうとするとすでにリストの操作関数などがたくさん用意してあって便利だと思うのですが、そういったものを自分で作ってみたいと 思ったのがきっかけです。 そこで、作るなら更地の状態から自分で関数を定義していって環境構築するのが楽しそうだと思ったのでインタプリタから自作しました。

 

どんなやつ?

正直に言いますと、自分はCommon Lisp処理系はclispしか触ったことありません。

また、Lisp言語をちゃんと使っていたわけではないので「自分から見たLisp言語ってこんな感じ?」というイメージが結構入っていることをご了承ください。

  • リストは再帰的に評価されて関数として実行されます。ここは普通のLispと同じです。
  • clispでは変数の値と定義された関数が区別されていますが、自分のLispでは区別されていません。 したがって、以下のような書き方ができます。
    
        (define A (lambda (x y) (+ x y) ) )
        (A 1 2)
                                    
  • ※defineは与えられたシンボルをデータと関連付ける特殊形式でsetqと同じようなものです。
  • データ型はNIL,T,コンス,シンボル,数値,文字列,ラムダ式,組み込み関数,特殊形式の9つです。
  • 組み込み関数及び特殊形式はは純Lispに毛を生やしたような感じで
    • Lispからatom,eq,car,cdr,cons,quote,define,if,lambda
    • 数値の処理用に+,-,*,/
    • その他にquit,import
    これだけです。(追加する可能性はありますが)
  • atom,eq,car,cdr,cons,quote,if,lambda,quit,+,-,*,/はclispを参考にして作ったので使い方は同じだと思います。
  • importは見ての通りファイルからプログラムを読み込む関数で引数としてファイル名を表す文字列を指定します。(今の所文字列型の唯一の 使いどころ)
  • ユーザー定義関数(このインタプリタではすなわちラムダ式)の中でdefineを使って宣言したシンボルはユーザー定義関数の中でのみ有効です。

つくったもの

インタプリタ自体へのリンクはここに貼っておきます。

 

github.com

また、このインタプリタ向けの自作ユーティリティ群は最後に晒しておきます。

感想

 

  • インタプリタ自作は初めてだったので感覚はつかめた気がする。(するだけ)
  • 言語仕様がシンプルなので実装しやすかった。
  • マクロできるようにしたいとも思いますがまたやる気がでればやろうと思います。
  • ユーティリティの作成は再帰のいい練習になりました。

自作ユーティリティ群


(define = eq)

(define iota 
	(lambda (n m)
		(if (= n (+ m 1) )
			NIL
			(cons
				n
				(iota (+ n 1) m)
			)
		)
	)
)


(define append
	(lambda (l a)
		(if (atom l)
			(cons a NIL)
			(cons (car l) (append (cdr l) a))
		)
	)
)

(define nth
	(lambda (n l)
		(if (eq n 1)
			(car l)
			(nth (- n 1) (cdr l))
		)
	)
)


(define list
	(lambda (&rest A)
		A
	)
)

(define length
	(lambda (l)
		(if (atom l)
			0
			(+ 1 (length (cdr l)) )
		)
	)
)

(define find
	(lambda (c l)
		(if (atom l)
			NIL
			(if (eq c (car l))
				(car l)
				(find (cdr l))
			)
		)
	)
)

(define member
	(lambda (c l)
		(if (atom l)
			NIL
			(if (eq c (car l))
				(cdr l)
				(find (cdr l))
			)
		)
	)
)

(define reverse
	(lambda (l)
		(if (atom (cdr l))
			(cons (car l) NIL)
			(append (reverse (cdr l)) (car l))
		)
	)
)

(define map
	(lambda (f l)
		(if (atom l)
			NIL
			(cons
				(f (car l))
				(map f (cdr l))
			)
		)
	)
)

(define map2
	(lambda (f l1 l2)
		(if (atom l1)
			NIL
			(cons
				(f (car l1) (car l2))
				(map2 f (cdr l1) (cdr l2))
			)
		)
	)
)

(define filter
	(lambda (f l)
		(if (atom l)
			NIL
			(if (f (car l))
				(cons (car l) (filter f (cdr l)) )
				(filter f (cdr l))
			)
		)
	)
)

(define zip
	(lambda (a b)
		(map2
			(lambda (x y) (list x y) )
			a
			b
		)
	)
)

(define not
	(lambda (test)
		(if test
			NIL
			T
		)
	)
)

(define or
	(lambda (&rest test)
		(if (filter (lambda (x) x) test)
			T
			NIL
		)
	)
)

(define and
	(lambda (&rest test)
		(define _and
			(lambda (test)
				(if (atom test)
					T
					(if (car test)
						(_and (cdr test))
						NIL
					)
				)
			)
		)
		(_and test)
	)
)

(define joint
	(lambda (a b)
		(if (atom b)
			a
			(joint (append a (car b)) (cdr b))
		)
	)
)

(define flat
	(lambda (l)
		(if (atom l)
			NIL
			(if (atom (car l))
				(cons (car l) (flat (cdr l)) )
				(joint (flat (car l)) (flat (cdr l)) )
			)
		)
	)
)

(define pow
	(lambda (a n)
		(if (eq n 0)
			1
			(* a (pow a (- n 1)))
		)
	)
)