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)

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

import Text.ParserCombinators.Parsec

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

instance Show Sexp where
  show (Nil) = "()"
  show (Symbol a) = a
  show (Cons a b) = "(" ++ show a ++ showCdr b ++ ")"
  show (Subr _) = "#<subr>"

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) } )

eval (Nil) env = Nil
eval (Symbol s) env = assoc s env
eval (Cons (Symbol "quote") (Cons a _)) _ = a
eval (Cons (Symbol "if") (Cons p (Cons t (Cons e _)))) env = if eval p env /= Symbol "#f" then eval t env else eval e env
eval (Cons fun arg) env = apply (eval fun env) (evals arg env)

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

apply (Subr fun) arg = fun arg

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

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))"

lisp str = print $ eval (read str) env

main = do
  lisp "x"
  lisp "(car x)"
  lisp "(cdr x)"
  lisp "(cons x x)"
  lisp "(cons (car x) x)"

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

もうちょっと組み込み関数を増やす

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

2007-03-06

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

なんとなくifが出来ると言語っぽい処理をしている気がしてくるので、今回はifを作ることにする。

ifは(if p t e)と3つの引数をとり、pの評価結果が真のとき(#tをはじめとして#f以外の全ての値)にt(thenのつもり)を評価して返し、pの評価結果が偽のとき(#fのときのみ)にe(elseのつもり)を評価して返す。

真偽値の登録

今回作っているlispは一応scheme系を自称しているので真偽値は#t/#fで表すことにする。パース結果としての#t/#fを評価したときに評価結果としても#t/#fとなってほしいので、#tと#fを環境に登録する。

env = read "((x . a) (y . b) (#t . #t) (#f . #f))"

Eqクラスインスタンス

最終的にifの内部処理ではSexp型の値としての#f(=Symbol "#f")との比較をすることになるので、Sexp型自体で同値判定(==)の演算が出来るようにEqクラスインスタンスとする。

deriving宣言を使ってみたらうまく動いているようなので今回はこれを使って楽をする。

data Sexp = Nil | Symbol String | Cons Sexp Sexp deriving Eq

if用eval部分

ifの処理をするのは、4つの要素をもつリストであり最初の要素がifになっている場合のとき。なので、4段階にConsされたものにおいて、順番に(Symbol "if")、p、t、eにパターンマッチさせる。そしてマッチしたならば、pについてevalし、その結果がSymbol "#f"と等しくなかった場合はtについてevalし、等しい場合はeについてevalする。

eval (Cons (Symbol "if") (Cons p (Cons t (Cons e _)))) env = if eval p env /= Symbol "#f" then eval t env else eval e env

テスト

ifの処理をテストしてみる。とはいっても、まだ真偽値を返す関数を1つも持っていないので、寂しいけど定数をあたえてテストする。

真を表す#tのときは、xを評価したaを返す。偽を表す#fのときはyを評価したbを返す。

他の値でも試してみる。()、'foo等も#fではないので真の扱いになりx側を評価する。

最後にifの入れ子を試してみる。

Main> eval (read "(if #t x y)") env
a
Main> eval (read "(if #f x y)") env
b
Main> eval (read "(if () x y)") env
a
Main> eval (read "(if 'foo x y)") env
a
Main> eval (read "(if (if #t #f #t) x y)") env
b

エラー処理解決 エラー処理解決 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - エラー処理解決 - HaskellでLispを書く日記 エラー処理解決 - HaskellでLispを書く日記 のブックマークコメント

前回assoc関数中でerror関数を使って例外を発生させようとしたのに出来なかった件が解決。今回から以下の修正版に差し替える。単に++の優先度を見落としていただけだったorz

assoc s _ = error $ "unbound variable: " ++ show s

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

import Text.ParserCombinators.Parsec

data Sexp = Nil | Symbol String | Cons Sexp Sexp deriving Eq

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) } )

eval (Nil) env = Nil
eval (Symbol s) env = assoc s env
eval (Cons (Symbol "quote") (Cons a _)) _ = a
eval (Cons (Symbol "if") (Cons p (Cons t (Cons e _)))) env = if eval p env /= Symbol "#f" then eval t env else eval e env

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

env = read "((x . a) (y . b) (#t . #t) (#f . #f))"

main = do
  print $ eval (read "(if #t x y)") env
  print $ eval (read "(if #f x y)") env
  print $ eval (read "(if () x y)") env
  print $ eval (read "(if 'foo x y)") env
  print $ eval (read "(if (if #t #f #t) x y)") env

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

組み込み関数を入れる

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

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

2007-02-24

パーサの作成 01:28 パーサの作成 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - パーサの作成 - HaskellでLispを書く日記 パーサの作成 - HaskellでLispを書く日記 のブックマークコメント

リストの表示(出力)が出来るようになったので、今度はパーサを作って読み込み(入力)を出来るようにする。

これができればテストのたびにCons (Symbol …とか書く苦労から解放される…。

それと、せっかくなので評判が良さそうなParsecを使ってみる。

S式用パーサ

S式というのは、アトムリストのどちらか。

なので、S式を読み込む場合は、まず最初の文字が"("かどうかを見て、"("だったらリスト用パーサを使って読み込む。(1行目)

そうじゃなかったらアトム(今のところシンボルのみだが)として読み込む。いまのところアトムというのはシンボルだけなので、スペース" "か括弧"("or")"以外の文字の1つ以上の繰り返しをシンボルにして返す。(2行目)

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

リスト用パーサ

リストを読み込む場合は、まずひとつS式を読み込んでcar部とし、cdr部はリスト用パーサを再帰的に呼び出す。(2行目)

閉じかっこ")"まできたらNilを返して終端とする。(1行目)

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

リスト用パーサ2

"(a . b)"の形式も読み込めるようにする。

最初の文字が"."かどうかを見て、そうだったらひとつS式を読み込む("b"の部分

ここでそのまま読み込んだS式を返して次の処理に進んでしまうと、パーサのカーソル(?)が")"の位置のままになっているのでまずい。

このためリストパーサで1回空読みをさせてカーソル位置を")"の後ろに進めてから"b"の部分の値を返すようにする。

listParser = ...
   <|> do { string "."; b<-sexpParser; listParser; return b }

空白等読み飛ばし

これまでのコードでは、なんらかの要素を読み込んだ後での空白等の読み飛ばしをまったくやっていないので、次の要素を読みはじめる前に常に空白等の読み飛ばしをする処理を行うようにする。

sexpParser = spaces >> (実際のパース処理...)
listParser = spaces >> (実際のパース処理...)

quote対応

今後のことを考えて、'aという表記があったら(quote a)として読み込む機能も入れておく。

S式の読み込み時に、最初の文字が「'」だったら、"a"の部分S式を読み込み、"quote"というシンボルと"a"の部分の値をリストにしたものを返すようにする。

このとき、単純に「Cons (Symbol "quote") a」とやってしまうと(quote a)ではなく、(quote . a)というリストになってしまうので注意。

sexpParser = ...
   <|> do { string "'"; a<-sexpParser; return (Cons (Symbol "quote") (Cons a Nil)) }

テスト

ここまで書いたものをつかって読み込みのテスト

*Main> parse sexpParser "" "a"
Right a
*Main> parse sexpParser "" "()"
Right ()
*Main> parse sexpParser "" "(a b)"
Right (a b)
*Main> parse sexpParser "" "(a . (b . c))"
Right (a b . c)
*Main> parse sexpParser "" "(car '(a b))"
Right (car (quote (a b)))

前半の例はなんか詐欺みたいな感じだが、とりあえず成功ということで。

readクラス 01:28 readクラス - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - readクラス - HaskellでLispを書く日記 readクラス - HaskellでLispを書く日記 のブックマークコメント

パーサが出来たので、これを使ってSexp型をreadクラスインスタンスにする。

といいつつ、readクラスのことはまだぜんぜん理解不足。本当はreadクラスフレームワーク自体でかなりのことが出来そうな印象だけど、今回は単純にreadsPrec関数からベタにparse関数を呼び出すだけ。

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

今日までの全コード 01:28 今日までの全コード - 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) } )

main = do
  print (read "()"::Sexp)
  print (read "a"::Sexp)
  print (read "(a b)"::Sexp)
  print (read "(a . (b . c))"::Sexp)
  print (read "(car '(a b))"::Sexp)

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

インタプリタ本体(eval)を作り始める予定

2007-02-20

はじめに 03:47 はじめに - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - はじめに - HaskellでLispを書く日記 はじめに - HaskellでLispを書く日記 のブックマークコメント

Audrey TangPugsを書くのにHaskellを使ったことだし、

Haskell勉強する題材として言語処理系を書いてみることにしました。

Schemeっぽいものを想定しているけど、Schemeの実装はよく知らないのでおかしいところがあったら教えてください。

リストの準備 03:47 リストの準備 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - リストの準備 - HaskellでLispを書く日記 リストの準備 - HaskellでLispを書く日記 のブックマークコメント

Haskellではもともとリストというデータ構造を持っている。

なので、これをつかっていきなりインタプリタの作成に取りかかりたいところだが、ここで問題がひとつ。

["define","null?",["lambda",["x"],["eq?","x",[]]]]

のような深さの異なる要素を持ったものはHaskellリストでは作れない。

しかたがないので、まず自前のリストを作ることにする。

とりあえず最初の段階としては、S式のとり得る値として「シンボル」「リスト(ペア)」「空リスト」の3つを用意する。

空リストNilシンボルはSymbol、リストはConsのデータコンストラクタを使う。

これらをまとめたS式型コンストラクタSexpで表して、以下のdata宣言にする。

data Sexp = Nil | Symbol String | Cons Sexp Sexp

想定している使い方は、

例えば、シンボルaなら、Symbol "a"、

(a b)というリストなら、Cons (Symbol "a") (Cons (Symbol "b") Nil)という感じ。

ちなみに、()がNil

リストの表示 03:47 リストの表示 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - リストの表示 - HaskellでLispを書く日記 リストの表示 - HaskellでLispを書く日記 のブックマークコメント

データ構造を定義したはいいけど表示ができないといろいろ困るのでshow関数を定義する。

例えばCons (Symbol "a") (Cons (Symbol "b") Nil)という値だったら、haskell風の表記なら[a,b]となるところだけど、lisp風の(a b)という表記に変換する方向でいくことにする。

このほうがlispを作ってる雰囲気が出そうなので…。

空リスト

空リストはかんたん。決めうちで"()"を返す。

show Nil = "()"

シンボル

シンボルもかんたん。自分が持ってる文字列の要素を使えばいい。

(右辺をshow xとすると出力にダブルクォートがついて嬉しくない)

show (Symbol x) = x

リスト

最後にリストの表示。

show (Cons x y) = "(" ++ show x ++ " " ++ show y ++ ")"

何も考えずにこう書いてしまうと、

show Cons (Symbol "a") (Cons (Symbol "b") Nil)
=>(a (b ()))

となってしまいよろしくない。

一番外側はかっこでくくるけど、中の要素はスペースで区切って並べるだけにする必要がある。1つの関数では書ける気がしないので、リストの2つめ以降の要素(cdr部)の表示には補助関数showCdrを使う。

おおもとのshowは以下のように頭の要素だけshowしてあとはshowCdrにおまかせ。

show (Cons x y) = "(" ++ show x ++ showCdr y ++ ")"

で、showCdr側で以下のようにして、順にスペースと要素1つを挿入していく。

showCdr (Cons x y) = " " ++ show x ++ showCdr y

ここまでくれば後はリストの終端の処理だけ。

とじかっこはすでに最初のshowで出しているので、最後のNilでは何も表示しない。

showCdr Nil = ""

これで普通リストはOKのはず。ちょっと実験してみる。

show $ Cons (Symbol "a") (Cons (Symbol "b") Nil)
=>(a b)

よし。

リストその2

リストの最後はNilとは限らない。

Cons (Symbol "a") (Cons (Symbol "b") (Symbol "c"))

といった感じの最後がNilで終わらないものの処理を追加する。

この場合は、最終的には(a b . c)と表示すればいいのだから、

上記Nil等とのパターンマッチ漏れたものに対して、

showCdr x = " . " ++ show x

とすればいい。これも実験してみる。

show $ Cons (Symbol "a") (Cons (Symbol "b") (Symbol "c"))
=>(a b . c)

できた。

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

data Sexp = Nil | Symbol String | Cons Sexp Sexp

instance Show Sexp where
  show (Nil) = "()"
  show (Symbol x) = x
  show (Cons x y) = "(" ++ show x ++ showCdr y ++ ")"

showCdr (Nil) = ""
showCdr (Cons x y) = " " ++ show x ++ showCdr y
showCdr x = " . " ++ show x

main = do
  print $ Nil
  print $ Symbol "a"
  print $ Cons (Symbol "a") (Cons (Symbol "b") Nil)
  print $ Cons (Symbol "a") (Cons (Symbol "b") (Symbol "c"))

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

次はS式のパーサを作る予定

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