HaskellでLispを書く日記 このページをアンテナに追加 RSSフィード

2007-03-14

組み込み関数対応 組み込み関数対応 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - 組み込み関数対応 - HaskellでLispを書く日記 組み込み関数対応 - HaskellでLispを書く日記 のブックマークコメント

やっぱりlisp(LISt Processing)というからには、car,cdr,consが使えないと。というわけでこれらの組み込み関数を使えるようにする。

組み込み関数は、これまでのquoteやifのように個別対応をするのではなく、carであろうがconsであろうがインタプリタとしては統一的な扱いですませられるようにする。

例えば、x=a,y=(b c)の時に(cons x y)を評価する場合を例にとると、

1.関数部分(リストの頭)を評価シンボルconsを評価して、consという変数の中に入っている「1番目の引数であたえられる値をを2番目の引数であたえられるリストに追加するという処理」を取り出す。

2.引数部分(リストの残り)を評価→全ての引数(ここではxとy)を評価して、それぞれaと(b c)を取り出す。

3.関数部分にあった処理を引数部分リスト適用(=apply)する→上記1.で取り出した「処理」を使って(b c)にaを追加したリストを求める。

という扱いにする。具体的には以下のようなものを想定。

eval (Cons fun arg) env = apply (eval fun env) (evals arg env)

apply (Subr fun) arg = fun arg

つまり、インタプリタ関数によってどんな処理をするかということを知っているわけではなく、単にcarとかcdrとかいう変数の中身を取り出して(eval fun env)、そこにあった処理をapplyで呼び出しているだけ。

データコンストラクタSubr

組み込み関数を表すデータコンストラクタとしてSubrを追加する。Subrが持つ値はS式引数にとってS式を返す関数なのでSexp->Sexp型の関数になる。

なんでSubrにしたかというと、gaucheでcarを評価したら#<subr car>と表示されたから。subrはサブルーチンの略(?)らしい。

deriving Eqでは関数Sexp->Sexpの比較は出来ないと怒られるので、(==)関数も自前で作ることにする。あとおまけでshowも追加。

data Sexp = Nil | Symbol String | Cons Sexp Sexp | Subr (Sexp->Sexp)

instance Eq Sexp where
  (==) Nil Nil = True
  (==) (Symbol a) (Symbol b) = a==b
  (==) (Cons a as) (Cons b bs) = a==b && as==bs
  (==) _ _ = False

  show (Subr _) = "#<subr>"

car,cdr,consを環境に追加

上記Subr型を値にもつ変数car,cdr,consを環境に追加する。

ちょっとだけキータイプ数を減らすためにユーティリティ関数としてdefineを定義する。

defineは3つの引数key,val,envをとり、keyシンボル化したものとvalを対にして環境envに追加した環境を返すもの。(なので、defineの返値にさらにdefineを連続して使う。)

define key val env = Cons (Cons (Symbol key) val) env
env =
 define "car" (Subr (\(Cons (Cons a _) _)->a)) $
 define "cdr" (Subr (\(Cons (Cons _ a) _)->a)) $
 define "cons" (Subr (\(Cons a (Cons b _))->Cons a b)) $
   read "((x . (a b c)) (#t . #t) (#f . #f))"

引数評価用evals

関数適用するためには事前に全ての引数評価が行われていなければいけないので、リストになっている引数を全て評価したリストを返す関数evalsを作る。

汎用的なmap関数を作って引数関数evalをとるようにしてもいいのかもしれないけど、他にmapを使い回す予定がいまのところはないので、普通にevalsを作る。

evals (Cons a b) env = Cons (eval a env) (evals b env)
evals a env = eval a env

テスト

ここでもズボラ化。いちいちeval (read …と書くのがめんどくさくなってきたので、ユーティリティ関数lispを定義する。

lisp str = print $ eval (read str) env

で、テスト

Main> lisp "x"
(a b c)
Main> lisp "(car x)"
a
Main> lisp "(cdr x)"
(b c)
Main> lisp "(cons x x)"
((a b c) a b c)
Main> lisp "(cons (car x) x)"
(a a b c)
トラックバック - http://haskell.g.hatena.ne.jp/haskelisp/20070314