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

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