HaskellでLispを書く日記

■ evalの作成（変数編）

道具（リスト構造）の準備が終わったので、やっと本題のインタプリタに取りかかれる…

具体的にはevalという関数を作成する。

関数evalは引数を２つとり、１つは評価するS式そのもの、もう１つは変数と値の対応を記録したデータベース。

このデータベースのことはこれ以降は環境と呼び、haskell上の変数名としては主にenvを使うことにする。

テスト用環境の作成

実際にdefine等を使って変数を定義するのは後回しにするとして、まずは変数の読み出し部分を作るためのテスト用の環境をでっち上げておく。

本来ならちゃんと効率のことも考えたデータ構造で作るべきなのかもしれないけど、今回はお手軽にすますということで、作ったばかりのSexp型を使った連想リストで作る。

変数xに値a、変数yに値bが入っている状態の環境は以下の通り。

env = read "((x . a) (y . b))"

補助関数assoc

環境の中から対応する変数を見つけてその値を返す処理を行う関数assocを作る

assocは２引数関数で、引数１に探したい変数名、引数２に環境をとる。

環境である連想リストの頭の要素から順番に探していき、各要素中のcar部に対応する変数名があったらそのcdr部を返し、そうでなかったら残りの要素について同様の処理をする。

本当はリストの最後(=Nil)まで来たら変数が存在しない旨の例外を発生させたかったのだが、haskellでの例外処理の使い方がよくわからなかったのでコメントアウト状態…

--assoc s Nil = error "unbound variable: " ++ show s
assoc s (Cons (Cons (Symbol k) v) e) = if s==k then v else assoc s e

変数用eval

出来たassocを使って変数のevalが出来るようにする。

eval (Symbol s) env = assoc s env

さっそくテスト

Main> eval (read "x") env
a
Main> eval (read "y") env
b

■ evalの作成(quote編)

変数の次はquoteに対応させる。

これは環境へのアクセスとかもなく単にquote式の中身を返すだけだから簡単。

eval (Cons (Symbol "quote") (Cons a _)) _ = a

ではこれもテスト

*Main> eval (read "(quote foo)") env
foo
*Main> eval (read "'foo") env
foo

'fooはパースの段階で(quote foo)になっているので同じ結果になる。

■ evalの作成(Nil編)

Nil=()の対応を忘れてた。

()を評価したら()を返す。

eval (Nil) _ = Nil

テストする

Main> eval (read "()") env
()

■ 今日までの全コード

import Text.ParserCombinators.Parsec

data Sexp = Nil | Symbol String | Cons Sexp Sexp

instance Show Sexp where
  show (Nil) = "()"
  show (Symbol a) = a
  show (Cons a b) = "(" ++ show a ++ showCdr b ++ ")"

showCdr (Nil) = ""
showCdr (Cons a b) = " " ++ show a ++ showCdr b
showCdr a = " . " ++ show a

instance Read Sexp where
  readsPrec _ s = case parse sexpParser "" s of Right a -> [(a,"")]

sexpParser = spaces >>
  (    do { string "("; listParser }
   <|> do { string "'"; a<-sexpParser; return (Cons (Symbol "quote") (Cons a Nil)) }
   <|> do { a<-many1 $ noneOf "'( )"; return (Symbol a) } )

listParser = spaces >>
  (    do { string ")"; return Nil }
   <|> do { string "."; a<-sexpParser; listParser; return a }
   <|> do { a<-sexpParser; b<-listParser; return (Cons a b) } )

env = read "((x . a) (y . b))"

--assoc s Nil = error "unbound variable: " ++ show s
assoc s (Cons (Cons (Symbol k) v) e) = if s==k then v else assoc s e

eval (Nil) env = Nil
eval (Symbol s) env = assoc s env
eval (Cons (Symbol "quote") (Cons a _)) _ = a

main = do
  print $ eval (read "x") env
  print $ eval (read "y") env
  print $ eval (read "(quote foo)") env
  print $ eval (read "'foo") env
  print $ eval (read "()") env

■ 次回予告

ifを使えるようにする