e-mon

備忘録

HaskellでSchemeを書く#4

追記:見直すこと!!

ここらで一度、ソースを整理することにした。 ついでにためてた宿題も片付けることに。

まずは、構文解析の章。

1.parseNumberの書き換え

  • 1.do記法
parseNumber :: Parser LispVal
parseNumber = do
  x <- many1 digit
  return $ (Number . read) x

*2.>>=による明示的シーケンシング

parseNumber :: Parser LispVal
parseNumber = many1 digit >>=  return . Number . read

2は解答を見てしまった。>>= (return (Number . read))とかいていて、なんで通らないんだ・・と思ってたけども、合成しないといけなかったのか。未だ不慣れ・・・

*Main> :t (return (Number . read))
(return (Number . read)) :: Monad m => m (String -> LispVal)
*Main> :t return . Number .read
return . Number .read :: Monad m => String -> m LispVal

2.parseStringの終端判定修正

3.escape文字の実装

これは問題の理解に手間取った・・。\\\"とか、\\nのようなものを実装すればいいんだな。
なのでとりあえず一度\\でパースして続く文字を取り出してあげれば、\"が単体で出てきたときに終端文字として正しく認識される、ということかな。
parseStringの中でパースするにあたり、Parser Charで返さなきゃ行けなくて、エスケープ文字を抽出したあと一文字で返す方法がわからず(文字列として連結して渡そうとしてた)、結局かなり筋が悪い感じになった

parseString :: Parser LispVal
parseString = do char '"'
                 x <- many (parseEscape <|> noneOf "\"")
                 char '"'
                 return $ String x

parseEscape :: Parser Char
parseEscape = do char '\\'
                 x <- oneOf "\\nrts"
                 return $ case x of
                  'n' -> '\n'
                  'r' -> '\r'
                  't' -> '\t'
                  _   -> x
*Main> parseTest parseString "\"abc\\\"abc\\\\1\\n3\""
"abc"abc\1
3"

直したい・・・。

4.'#'prefixの実装

The radix prefixes are #b (binary), #o (octal), #d (decimal), and #x (hexadecimal). With no radix prefix, a number is assumed to be expressed in decimal.

parseNumberよりは、parseAtomを直すのが良いように思える・・・。どうせなので、prefixParserを作る。#prefixを別で処理することにしたので、symbolに吸い込まれないように修正。

symbol :: Parser Char
symbol = oneOf "!$%&|*+-/:<=>?@^_~"

parseAtom :: Parser LispVal
parseAtom = do first <- letter <|> symbol
               rest <- many (letter <|> digit <|> symbol)
               let atom = first:rest
               return $ case atom of
                          _    -> Atom atom

parsePrefix :: Parser LispVal
parsePrefix = do char '#'
                 prefix <- letter <|> symbol
                 expression <- many(letter <|> digit)
                 return $ case prefix of
                  'x' -> Number $ fst $ (readHex expression) !! 0
                  'd' -> (Number . read) expression
                  'o' -> Number $ fst $ (readOct expression) !! 0
                  --'b' -> readBin
                  't' -> Bool True
                  'f' -> Bool False

parseAtomの意味がなくなってしまったな・・・。本当は、firstで処理を分けたかったけど、その場合だと、 一度文字列を処理してparsePrefixでparseするという関数をもう1つ作らなければならなかったのでそちらのほうが筋悪と考えた。readBinNumericモジュールになかったのでまた考える。

*Main Numeric> parseTest parsePrefix "#d1234"
1234
*Main Numeric> parseTest parsePrefix "#x1234"
4660

5.Characterリテラルの実装

Characters are objects that represent printed characters such as letters and digits. Characters are written using the notation #\\ or #\\. For example:

  • #\a ; lower case letter
  • #\A ; upper case letter
  • #\( ; left parenthesis
  • #\ ; the space character
  • #\space ; the preferred way to write a space
  • #\newline ; the newline character

#\から始まる表現みたい。何もLispValに加えるほどのものでも無い気がするけど、どうなんだろう。 後続の文字が1文字ならそのまま返して、space or newlineなら変換して返す感じかなぁ。 一文字だったら、文字列に一致したら、っていう条件分岐の書き方がわからない・・、のでカンニング・・・

value <- try (string "newline" <|> string "space") 
          <|> do { x <- anyChar; notFollowedBy alphaNum ; return [x] }

alphaNumletterdigitをあわせたパーサで、notFollowedByは、何かと組み合わせて、指定されたパーサでパースできるものが続いてる場合はError、そうじゃなければ通す、みたいな関数らしい。(参考Parsec notFollowedBy - tnomuraのブログ) doのこういうくくり方全然思いつけないなぁ・・。写経することにする。ついでにShowValも変更。

6.Floatコンストラクタの追加

これは、これまでのに比べると簡単。

parseFloat :: Parser LispVal
parseFloat = do
  head <- many1 digit
  char '.'
  tail <- many1 digit
  return $ Float $ fst $ (readFloat $ head ++ "." ++ tail) !! 0

parseExprにはtryを入れて、parseNumberの前に追加

*Main Numeric Text.ParserCombinators.Parsec> parseTest parseExpr "(12.3 123)"
(12.3 123)

7.数値表現の追加

Mathematically, numbers may be arranged into a tower of subtypes in which each level is a subset of the level above it:

number

  • complex
  • real
  • rational
  • integer

realinteger実装済なので、rationalcomplexの実装。まずは、rational有理数・・。

4/6  => 2/3
3/12 => 1/4
10/5 => 2    ; 整数に変換される

こんな感じになるらしい。なんと、HaskellにはRational型があった。凄い。10 % 11のように表示されるということだけど、少数に直したりすると正確な値とはずれるらしい。(参考:すごい乱暴な方法でHaskellの少数を正確数にする-Qiita)
念頭におきつつ、多分今回は関係ないので、とりあえず例にあるような形の数字を、Rational型にする。

parseRational :: Parser LispVal
parseRational = do
  denom <- many1 digit
  char '/'
  num <- many1 digit
  return $ Rational $ read(denom) % read(num)

そのまんまな感じ。

複素数も、Data.Complexなるモジュールにあったので、そのまま流用。
Schemeでの複素数の例

5-3i => 5.0-3.0i
1.2+2.4i => 1.2+2.4i
1/2+1/4i => 0.5+0.25i
parseComplex :: Parser LispVal
parseComplex = do
  re <- many1 digit
  mark <- char '+' <|> char '-'
  im <- many1 digit
  char 'i'
  return $ Complex $case mark of
    '+' -> read(re) :+ read(im)
    '-' -> read(re) :+ (- read(im))

勢いに任せてこんな感じで実装し、答え合わせをすると、実数で表示されてるのを完全に忘れてた。確かにSchemeでも実数表示になってる・・。書き直し・・。

parseComplex :: Parser LispVal
parseComplex = do
  re <- (try parseFloat <|> do { x <- many1 digit;return $ Float $ fst $ head $ readFloat(x)})
  mark <- char '+' <|> char '-'
  im <- (try parseFloat <|> do { x <- many1 digit;return $ Float $ fst $ head $ readFloat(x)})
  char 'i'
  return $ Complex $case mark of
    '+' -> toDouble(re) :+ toDouble(im)
    '-' -> toDouble(re) :+ ( - toDouble(im))

結局toDoubleを実装してこのように。do記法でやってみたけど、これは見た目があれだなぁ・・

かなり急いでやってしまったのでまた見直す事。 現在の進捗:github