Arantium Maestum

プログラミング、囲碁、読書の話題

HaskellとParsecでLisp REPL　その５（Bool型の追加）

Haskell

今回の変更点

github.com

ブール値の追加。データ型とパーサの拡張のみ。

データ型

data LispVal = Atom String
             | List [LispVal]
             | Number Integer
             | Bool Bool

ちゃんとshowできるようにしておく：

showVal (Bool True) = "#t"
showVal (Bool False) = "#f"

パーサ拡張

Bool型はユーザ入力が"#t"ならBool True、"#f"ならBool Falseである。このパーサはちょっとだけややこしい。

というのは、今までの三つの種類のデータ型はそもそも先頭の文字をパースした時点でどの要素になるかがわかったのだが、Bool型の場合Atom型とかぶってしまっている。

まず、Atom型のパーサのほうがBool型よりも許容度が高いので（"#t"はAtom型としてもパース可能）、パースを試す順番はBoolのほうが先でなければいけない：

parseExpr = parseBool
        <|> parseAtom
        <|> parseList
        <|> parseNumber

これで"#t"がAtom型として認識されてしまう問題は回避できる。

しかし、まだ気をつけないといけない。

今までのような実装だとたとえば"#define"のような文字列をパースする時に、parseBoolが"#"は処理し"d"を読んだ時点で諦めるので、"#"文字が次のparseAtomに渡されない問題が発生する。

parseBool :: Parser LispVal
parseBool = (try parseTrue) <|> (try parseFalse)

parseBoolがtryを使うことによって解決する。tryはバックトラックしてくれるので、parseTrueを試してみて失敗したら元の文字まで戻ってparseFalseに回し、それも失敗したらまた元の文字まで戻って次のパーサに回す。

parseTrue/parseFalseの定義：

parseTrue :: Parser LispVal
parseTrue = string "#t" >> return (Bool True)

parseFalse :: Parser LispVal
parseFalse = string "#f" >> return (Bool False)

ParsecのParserはモナドなので>>とかreturnがでてくる。"#t"や"#f"のパースが成功したら、マッチした文字列は使わず直接Bool True/Bool FalseをParserモナドに入れて返す。

評価器・REPL・Main

例によって変更なし

次回

ブール値が表現できるようになったので、ブール値を返す比較演算子を定義する。

HaskellとParsecでLisp REPL　その４（四則演算）

Haskell

今回の変更点

github.com

ついに四則演算の実装。入力をそのまま返すのではなく、入力を評価・変換して出力するようになり、「ちゃんとしたREPL」にちょっと近づく。

データ型とパーサ

今回は変更なし。四則演算ならAtom、List そしてNumber型だけで十分。演算子がAtom、数値がNumber、それを式として繋げる容器がListだ。

評価器

Evaluatorに一つ変換ルールを追加：

eval :: LispVal -> LispVal
eval (List (Atom funcName : args)) = apply funcName $ map eval args
eval lispVal                       = lispVal

ロジックとしては以下のとおり：

  1. あるLispValがList型で、その先頭の要素が任意のAtom型の場合、そのListを関数適用の式とみなす。
  2. まず先頭以外の要素すべてを評価する
  3. 評価された先頭以外の要素に対しapply funcNameで関数適用する（funcNameは先頭要素のAtom型が保持している文字列）

applyがキモで、これは新しいModuleのFunctionsで定義されている。

関数適用と演算の定義

Functions内をみていく。このModuleからはapplyしか公開しない。あとは内部実装。

まずはそのapplyの定義：

apply :: String -> [LispVal] -> LispVal
apply funcName args = maybe (Number 0) ($ args) $ lookup funcName primitives

すこしややこしく見えるが、やっていることはおおまかに二つ

  • Haskellの標準関数であるlookupを使ってfuncNameをprimitivesテーブルの中から探す
  • lookupはMaybe型を返すので、それをmaybe関数で処理
    • funcNameがprimitivesに含まれず、MaybeがNothingだった場合(Number 0)を返す
    • funcNameが見つかりMaybeがJust 該当する関数だった場合、その関数にargsを適用した結果を返す

($ args) fがf argsになるのは面白い。慣れるまですこし面食らったが・・・

primitivesテーブルは、「文字列と[LispVal] -> LispVal型の関数のタプル」が入っているHaskellのリスト：

primitives :: [(String, [LispVal] -> LispVal)]
primitives = [
  ("+", numBinOp (+)),
  ("-", numBinOp (-)),
  ("*", numBinOp (*)),
  ("/", numBinOp div)
  ]

今のところ四則演算のみ。Haskell自身の四則演算関数を自前のnumBinOpの引数にすることで[LispVal] -> LispVal型にしている。

numBinOpの定義：

numBinOp :: (Integer -> Integer -> Integer) -> [LispVal] -> LispVal
numBinOp op args = Number $ foldl1 op $ map numerify args

Haskellの整数をとる二項演算関数を[LispVal] -> LispValに変換する。

  • LispValのリストであるargsを（後述の）numerify関数でHaskellのIntegerに変換
  • Integerのリストに対し、二項演算をfoldl1する
    • (op a b c d) = (op (op (op a b) c) d) = (((aopb)opc)opd)
  • その結果のIntegerをNumber型に格納して（LispVar化して）返す

という流れになっている。

numerifyのコード：

numerify :: LispVal -> Integer
numerify (Number n) = n
numerify _          = 0

パターンマッチでNumber型からは保持する整数を取り出し、それ以外のLispValはDon't Careパターンで0と解釈する。

これで四則演算の関数が定義・登録された。

現在気になっている点

  • numBinOpが二項演算じゃない
    • 任意の数に対してfoldl1している
    • パターンマッチで二項演算を強制することもできるが・・・
    • 名前をnumBinOpからnumOpなどに変えたほうがいいかもしれない
  • 動的なだけじゃなくて弱い型になっている
    • 登録されていない関数適用は数値0を返す
    • 数値以外のLispValへの四則演算適用は、そのLispValを数値0と解釈して続行
    • 後々エラー処理を追加するのでその時に解決

REPL・Main

変更なし

実行

>> (+ 1 2)
3 // 足せる
>> (+ 1 2 3)
6 // ３以上の要素に対しても適用可能
>> (* (+ 5 (- 7 3)) (/ 9 2))
36 // 四則すべて・ネストも可
>> (+ (1 2 3))
0 // リストは関数適用時には0として認識される・要素１でも適用可能
>> (1 2 3)
(1 2 3) // 関数適用外の場合リストはそのままの値として評価される
>> (+ 1 x)
1 // `Atom`も0として評価される
>> (f 5)
0 // 登録されていない`Atom`を関数として使う場合の結果も0
>> quit

やはりREPLらしくなってきた。

四則演算ができるところまで実装されたリリース

github.com

srcとapp/Main.hsにコードが記述されている。

次回

if構文をサポートしたいので、次回はとりあえずブール値を表すデータ型の追加。

HaskellとParsecでLisp REPL　その３（Number型の追加）

Haskell

今回の変更点

github.com

REPLで数字を入力するとパースエラーになる。Atom、Listに続いてNumberもパースしデータとして扱えるようにしたい。

LispValにNumber型を追加

LispValに新たにNumber型を定義し、Haskellの整数を保持させる：

data LispVal = Atom String
             | List [LispVal]
             | Number Integer

showVal関数は、単にNumberが保持する整数の文字列を返す：

showVal (Number n)      = show n

パーサを拡張

トップレベルのパーサにparseNumberを追加：

parseExpr :: Parser LispVal
parseExpr = parseAtom
        <|> parseList
        <|> parseNumber

parseNumberの定義：

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

数字が一つ以上続いているのを文字列として捉え、readでHaskellのIntegerに変換してからNumberデータコンストラクタに渡し、returnでParserモナド値にしている。

AtomやListと違ってロジックが簡単なのでdo記法はなし。しかし>>=は処理の流れがけっこう追いにくく感じる。慣れの問題？

評価器・REPL・main

前回と同じく変更なし

実行

REPLを走らせてみるとこんな感じ：

>> a
a
>> 1
1
>> ()
()
>> (1 2 3)
(1 2 3)
>> (+ 1 2 3)
(+ 1 2 3)
>> quit

とりあえず数字を入力してもパースエラーは起きなくなっている。

しかしなんの計算も評価も行われず、ただ単に入力をそのまま出力しているだけ。悲しい。

次回は数値に対する四則演算を評価するように変更する。

HaskellとParsecでLisp REPL　その２（Listも使えるREPL）

Haskell

LISPとはそもそもLISt Processingの略なので、リストを全く扱えない状態からいち早く脱却したい。

というわけで次はリストの実装。ユーザから(a1 a2 a3)といった文字列を受けとり、List型として表現できるようにする。

gistからちゃんとしたgithub repoに変えてみた。リリースタグにリンクできるだけでなく、前回からの変更点も：

github.com

このようにリンクできるのがうれしい。

LispVal型の拡張

Atom型だけだった代数型データにListを追加：

data LispVal = Atom String
             | List [LispVal]

ListはLispValのリストを保有する。

showが使えるようにshowValも拡張：

showVal (List contents) = "(" ++ (unwords $ map show contents) ++ ")"

パーサの拡張

トップレベルのパーサparseExprがListを認識するよう拡張：

parseExpr :: Parser LispVal
parseExpr = parseAtom
        <|> parseList

まずはparseAtomを試し、そのパースが失敗した場合parseListを試す。

parseList :: Parser LispVal
parseList = do {
    char '(';
    xs <- sepBy parseExpr (skipMany1 space);
    char ')';
    return $ List xs;
}

評価器・REPL・main

evalやREPL、mainは変更の必要なし。現在リストは変換されず、そのまま値として扱われる。

使用例

これだけの変更で、ユーザがリストを入力するとちゃんとパースされて表示される：

~$ ./v2
>> (a b c)
(a b c)
>> (a (b c))
(a (b c))
>> (a (b (c (d))))
(a (b (c (d))))
>> (a b 2)
No match: "lisp" (line 1, column 6):
unexpected "2"
expecting space, letter or "("
>> (+ a1 a2)
(+ a1 a2)
>> (+ 1 2)
No match: "lisp" (line 1, column 4):
unexpected "1"
expecting space, letter or "("
>> quit
~$

再帰的な(a (b (c (d))))といった構造もちゃんとパースできている。しかしまだ数字はパースされない。次回は数字も受け入れるようにする。

HaskellとParsecでLisp REPL　その１（Atomをパースし表示するREPL）

Haskell

ここ一週間ほどHaskellを試しがてら、以下のチュートリアルをいじっていた：

Write Yourself a Scheme in 48 Hours - Wikibooks, open books for an open world

まずは全部通しで実装してみて、その後コードをいろいろ書き換えたり。

このチュートリアル、非常に勉強になったしHaskellやParsec習得のために大変おすすめなのだが、ひとつ気になったのはREPLができるのが第６章という遅さ。

第２章の「パーサ作成」の時点でコードを表すデータ構造を相当作り込んでいるし、第３章では例外処理なども作っている。各パートでけっこう多機能なパーサ、評価器などを作っていってからREPLに組み合わせている感がある。

個人的には超簡単なEnd-to-EndのREPLを最初に作って、そこに機能をくっつけていくほうがしっくりくる。

というわけでその方法で作り直す段階を個別に記事にしていく。

Read-Eval-Print-Loop

最低限のLisp REPLとはなんだろうか。

そもそもREPLとはRead-Eval-Print-Loopの略なので

  1. ユーザから文字列を受けとり、コードを表す内部データ構造に変換 (Read)
  2. データ構造を評価 (Eval)
  3. 評価結果をプリント出力 (Print)
  4. はじめに戻ってユーザ入力を待つ (Loop)

を兼ね備えている必要がある。

とりあえず今回は「Lispの『関数名』『変数名』などを表すAtomを正しくパースし、そのものとして評価し、プリントし、そしてループする」というところまで実装する。

コード：

Ultra-Minimal Lisp REPL written in Haskell - Atom only · GitHub

LispValデータ構造

Lispコードを表現するのに代数的データ型LispValを定義する：

data LispVal = Atom String

Atom型は文字列を一つ保持するデータ型。

今回はLispValが取り得る型はAtomのみ。今後、機能を足していくに従ってLispValの型が増えていく。

LispValを文字列として表示できるようにShow型クラスのインスタンスとしておく：

instance Show LispVal where show = showVal

showVal :: LispVal -> String
showVal (Atom name) = name

Atom型をshowする場合、保持している文字列が返される。

「文字列→LispVal」パーサ

まずはトップレベルの関数：

readExpr :: String -> LispVal
readExpr input = case (parse parseExpr "lisp" input) of
  Left err  -> Atom $ "No match: " ++ show err
  Right val -> val

型からわかる通り、文字列からLispValへと変換する関数。Parsecのparse関数と後述するparseExprを使っている。

parseは第三引数の文字列に対して第一引数のパーサを適用し、Either型を返してくる。成功したらRight、失敗したらLeft。 パターンマッチで、失敗したらLeftに含まれているエラーメッセージをAtomに入れて返し、成功ケースの場合はRightに含まれているLispValを直接返す。

トップレベルのパーサ：

parseExpr :: Parser LispVal
parseExpr = parseAtom

今回は非常に簡単。今後他のデータ型が増えていくに従いparseExprも他のパーサを組み合わせる形になっていく。

ポイントとしては、Parsecの提供するParserモナドのなかで処理が進んでいくこと。ParsecがMonadic Parserだと言われる所以である。

parseAtomの定義：

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

parseAtom :: Parser LispVal
parseAtom = do {
    first <- (letter <|> symbol);
    rest <- many (letter <|> digit <|> symbol);
    return $ Atom (first:rest);
}

LispのAtomの特徴は「アルファベット文字か指定の特殊記号で始まり、それら文字か数字が0個以上続く」というもの。

それをほぼそのまま書き表している。Parserモナドのなかで処理しているのでdo記法。最後にParser LispVal型のものを返している。

評価器

評価法は「LispVal -> LispVal」の変換則を再帰的に加えていくというもの。適用できる変換則がないLispValの値はそのLispValそのもの。

eval :: LispVal -> LispVal
eval lispVal = lispVal

今回はLispValがAtomだけで、変換則はない。非常に単純。

REPL各部分とmain関数

まずは標準入力から文字列を受けとる関数：

readPrompt :: String -> IO String
readPrompt prompt = putStr prompt >> hFlush stdout >> getLine

上で定義した関数を組み合わせて文字列をLisp的に評価し結果をプリントする関数：

readEvalPrint :: String -> IO()
readEvalPrint = putStrLn . show . eval . readExpr

readPromptとreadExprが分離されているのが「REPL」という名前からすると微妙・・・　そもそもパーサの部分はReadなのかEvalなのか？

特定の入力をうけとるまでループし続ける関数：

loopUntil :: (a -> Bool) -> IO a -> (a -> IO ()) -> IO ()
loopUntil pred prompt action = do {
    x <- prompt;
    if pred x
      then return ()
      else (action x >> loopUntil pred prompt action)
}

もし停止条件が入らない場合は：

loop prompt action = prompt >>= action >> loop prompt action

というような書き方になるだろうか。停止条件のための条件分岐が必要なので少し長めのコードになっている。

do {}記法にマルチラインの式が入る場合の書き方がイマイチ自信がない・・・

これらの関数を組み合わせたmain：

main :: IO ()
main = loopUntil (== "quit") (readPrompt ">> ") readEvalPrint

"quit"が入力されるまでループし続けて、入力された文字列を評価してプリントしていく。

使用例

ghc -package parsec -o lisp-v1 --make lisp-v1.hsなどでコンパイルできる。

./lisp-v1を実行してみると：

~$ ./lisp-v1
>> a
a
>> a1
a1
>> +a1
+a1
>> 1
No match: "lisp" (line 1, column 1):
unexpected "1"
expecting letter
>> (+ a b)
No match: "lisp" (line 1, column 1):
unexpected "("
expecting letter
>> quit
~$

このようなREPLが走る。まだ数字やリストは受け入れられない。

次回はリストを受けとりパースできるようにする。

4月の抱負

書籍

今月は以下の本を読みたい：

  • Thinking Functionally with Haskell　（終わらせる！）
  • プログラミングのための確率統計
  • 証明の楽しみ 基礎編

他にもいろんな本やClojureや機械学習やギター曲や水泳にも手を出すつもりだが、とりあえず上記の3冊は終わらせる勢いでやっていく。

Thinking Functionally with Haskellが終わったらModern Compiler Implementation in MLだな・・・

『アホでマヌケなプログラミング』読んだ

書籍

lepton著『アホでマヌケなプログラミング』を読んだ。

非プログラマ（ゆるくプログラマ志望な人？）に「プログラマの実態」を紹介する本。

著者は企業の新卒向けプログラミング研修の講師などをよく務めていたらしい。「文系卒、プログラミング経験なし」の新卒人材をプログラマにしたててプロジェクトに投入する現場のこぼれ話がたくさん載っている。研修を受ける人々の話だったり、使われているプログラミング言語の話だったり、実際に行われているプロジェクトの内実・人間模様だったり。

出版されたのが2003年ということもあってやはり少し古い感じがするのと、そもそも「プログラミング経験なしの人材の大量投入」という個人的にはあまり関わったことのない現場についての話なのとで、あまり自分の実体験と合致する印象ではなかった。ただその分なかなか興味深かったことも確か。

2000年問題や銀行合併、はてはΣ計画などの過去のすったもんだあったプロジェクトについての話もゴシップ的な楽しさがある。営業と開発の確執やら、担当者不在で繁忙期にO(n**2)のアルゴリズムでバッチ処理しなきゃいけなかった時の話やら、「本当にあったプログラマの怖い話」あるいは「日本式プログラマという種族の文化人類学的資料」といった感じ。文体もまさに2000年代初頭のインターネットによくあった、微妙にくだけた理系おじさん調。

癖はすごくあるけど、「こういうプログラマ界隈が主流だった」ということを少しだけ肌で感じられるだけでもとても面白い本だった。

しかし、これを読んでなお「プログラマになろうかな」と思い続けた読者が果たしていたのだろうか？