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

2007-02-28

evalの作成(変数編) evalの作成(変数編) - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - evalの作成(変数編) - HaskellでLispを書く日記 evalの作成(変数編) - HaskellでLispを書く日記 のブックマークコメント

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

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

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

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

テスト環境の作成

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

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

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

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

補助関数assoc

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

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

環境である連想リストの頭の要素から順番に探していき、各要素中の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編) evalの作成(quote編) - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - evalの作成(quote編) - HaskellでLispを書く日記 evalの作成(quote編) - HaskellでLispを書く日記 のブックマークコメント

変数の次は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編) evalの作成(Nil編) - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - evalの作成(Nil編) - HaskellでLispを書く日記 evalの作成(Nil編) - HaskellでLispを書く日記 のブックマークコメント

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

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

eval (Nil) _ = Nil

テストする

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

今日までの全コード 今日までの全コード - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - 今日までの全コード - HaskellでLispを書く日記 今日までの全コード - HaskellでLispを書く日記 のブックマークコメント

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

次回予告 次回予告 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - 次回予告 - HaskellでLispを書く日記 次回予告 - HaskellでLispを書く日記 のブックマークコメント

ifを使えるようにする

トラックバック - http://haskell.g.hatena.ne.jp/haskelisp/20070228