48時間でSchemeを書こう/評価: 第一部

評価器作成の手始め

今の所、我々のパーサは与えられたプログラム片を認識するかしないかを出力していただけです。機能するSchemeインタプリタに向かって最初の一歩を取ろうとしています - プログラム片に値を割り当てることによって。初めはゆっくりと進みますが、直に意味ある計算を行うところまで辿りつきます。

まずはHaskellにいろんなLispValの文字列表現の表示方法を教えるところから始めましょう。

showVal :: LispVal -> String
showVal (String contents) = "\"" ++ contents ++ "\""
showVal (Atom name) = name
showVal (Number contents) = show contents
showVal (Bool True) = "#t"
showVal (Bool False) = "#f"

これが私たちにとって初めての、本物のパターンマッチの導入です。パターンマッチは代数的データ型を分解し、そのコンストラクタに応じてコード節を選び、それぞれの部分を変数に束縛する手立てです。どんなコンストラクタもパターンの中に現れることができます。パターンはタグが与えられた値のタグと同じで、全てのサブパターンが対応する部分に一致する場合マッチします。パターンは任意の深さに入れ子にすることができ、マッチングは内から外、左から右の順番で行なわれます。関数定義の節は書かれた順にマッチするまで試されます。もしこの説明が難しく感じられても、これからさらに深く評価器について学ぶ時、深く入れ子になったパターンにいくつかあたることになります。

現時点においては、上述の定義の一つ一つがLispValのコンストラクタの一つにマッチし、右辺がそのコンストラクタの値に対して何を行うか示している、ということだけ覚えておいてください。

ListとDottedList節は似たように働きますが、中のリストを文字列に変換するヘルパー関数unwordsListを定義する必要があります。

showVal (List contents) = "(" ++ unwordsList contents ++ ")"
showVal (DottedList head tail) = "(" ++ unwordsList head ++ " . " ++ showVal tail ++ ")"

unwordsList関数はHaskellプレリュードのリスト中の文字列をスペースで接ぎ合わせるunwords関数のように働きます。ここではLispValのリストを扱っているので、LispValを文字列表現に直してからそれにunwordsを適用する関数を作ります。

unwordsList :: [LispVal] -> String
unwordsList = unwords . map showVal

unwordsListの定義は引数を含みません。これはpoint-free style、つまり関数定義を関数合成と部分適用のみで書く手法の例です。個々の値や"points"にかかずらわる代わりに、いくつかの組み込み関数の組み合わせを使います。まず、mapをshowValに部分適用すると、LispValのリストを取り、それらの文字列表現のリストを返す関数が出来ます。Haskellの関数はカリー化されています。これは、mapのような二引数関数が実際は一引数関数を返す関数だということを意味します。結果として、引数を一つだけ与えた場合、好きなようにできる一引数関数を得ることができます。この場合はそれをunwordsと合成します。すなわち、map showValはLispValのリストをそれらの文字列表現のリストに変え、unwordsがそれをスペースで繋ぎ合わせます。

上で使ったshowはどんなShowクラスのインスタンス型の値も文字列に変換する関数です。LispValも同じように扱いたいので、showメソッドとしてshowValを用いるShowクラスのメンバーにします。

instance Show LispVal where show = showVal

型クラスの完全な解説はこのチュートリアルの範囲を越えています。other tutorialsやHaskell 98 reportにより詳しい情報があります。

readExpr関数を、単に値を見つけたと報告するのではなく、パースした値の文字列表現を返すように変え、上の関数を試してみましょう。

readExpr input = case parse parseExpr "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found " ++ show val

コンパイル・実行すると、

$ ghc -package parsec -o parser listing4.1.hs
$ ./parser "(1 2 2)"
Found (1 2 2)
$ ./parser "'(1 3 (\"this\" \"one\"))"
Found (quote (1 3 ("this" "one")))

評価器作成の手始め: プリミティブ

では評価器を作りましょう。評価器の目標は、コードの型を、評価結果であるデータの型に写すことです。Lispでは、コードとデータ両方の型が同じなので、評価器はLispValを返します。他の言語ではコードが様々な文法によるより複雑な構造を持っていることが多いです。

数値・文字列・真偽値・クォートされた文字列を評価するのは非常に簡単で、それ自身を返せばよいだけです。

eval :: LispVal -> LispVal
eval val@(String _) = val
eval val@(Number _) = val
eval val@(Bool _) = val
eval (List [Atom "quote", val]) = val

新しい種類のパターンが出てきました。この記法val@(String _)は文字列であるLispVal全てにマッチし、valにそのLispVal全体(Stringコンストラクタの中身だけでなく)を束縛します。戻り値はString型ではなくLispVal型を持ちます。アンダースコアは「どうでもいい」変数で、どんな値にもマッチしますが、どんな値にも束縛されません。アンダースコアはどんなパターンにおいても使うことができますが、主に@パターンとコンストラクタタグを調べたいだけの時に便利です。

最後の節はネストしたパターンの例です。Listに含まれるデータの型はLispValのリスト[LispVal]です。ここではそれを取って[Atom "quote", val]という二つの値、シンボル"quote"とvalに束縛される任意の値を含むリストに対してマッチさせ、valを返します。

ではevalを既にあるコードに統合しましょう。まずreadExprが式の文字列表現の代わりに式そのものを返すように直しましょう。

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

そしてmain関数を、式を読み、それを評価して、文字列に変えた後、表示するように変更します。今や私たちは>>=演算子と関数合成演算子を知っているので、それらを使ってコードを少し簡潔にしましょう。

main :: IO ()
main = getArgs >>= print . eval . readExpr . head

mainでは、getArgsアクションの結果を取り、以下のように働く合成関数に渡します。

1. 最初の値を取り(head)、
2. 構文解析して(readExpr)、
3. 評価し(eval)、
4. 文字列に変換して表示します(print)。

いつも通りコンパイル・実行してください。

% ghc -package parsec -o eval listing4.2.hs
% ./eval "'atom" 
atom
% ./eval 2
2
% ./eval "\"a string\""
"a string"
% ./eval "(+ 2 2)"

Fail: listing6.hs:83: Non-exhaustive patterns in function eval

今のところ特に実用的なことは出来ませんが((+ 2 2)が失敗していますね)、基本的な骨格は出来上がりました。さらに関数を足してこれを拡張していきましょう。

基本的なプリミティブを加える

次に、私たちのSchemeを簡単な計算機として使えるようにします。まだ「プログラミング言語」と呼ぶには程遠いですが、前進はしています。

evalに関数適用を扱う節を加えることから始めましょう。覚えておかねばならないのは、関数定義の全ての節はまとめておかなければならず、書かれた順に評価されるということです。従って、次の節は他の節全ての後に置かれるべきです。

eval (List (Atom func : args)) = apply func $ map eval args

これも入れ子になったパターンですが、今回はリテラルのリストではなくコンス演算子:に対してマッチします。Haskellにおいて、リストは実際のところ数珠繋がりになったコンス適用と空リストの構文糖衣です: [1, 2, 3, 4] = 1:(2:(3:(4:[])))。リテラルのリストではなくコンス自体にパターンマッチさせることで、私たちは「リストの二番目の要素」の代わりに「リストの残り」を指定していることになります。例えば、(+ 2 2)をevalに渡したとすると、funcは+に束縛され、argsは[Number 2, Number 2]に束縛されます。

節の残りは2つの既出の関数とまだ定義していない関数1つで構成されています。再帰的に引数のそれぞれを評価するためにevalをargsにmapします。これによって私たちは(+ 2 (- 3 1) (* 5 4))のような組み合わさった式を書くことができます。その後、評価済の引数のリストをもとの関数と共にapplyに渡します。

apply :: String -> [LispVal] -> LispVal
apply func args = maybe (Bool False) ($ args) $ lookup func primitives

組み込み関数lookupはペアのリストからキー(その最初の引数)を探します。しかし、リスト中のどのペアもキーにマッチしない場合、lookupは失敗するでしょう。これを表現するため、lookupは組み込みのMaybe型のインスタンスを返します。maybe関数を使って成功・失敗の時にそれぞれどうするかを指定します。もし関数が見つからなければ、#fに相当するBool False型を返します(後でより頑健なエラーチェックを入れます)。もし見つかれば、($ args)を使ってそれを引数に適用します。

次に、私たちの実装するプリミティブのリストを定義します。

primitives :: [(String, [LispVal] -> LispVal)]
primitives = [("+", numericBinop (+)),
              ("-", numericBinop (-)),
              ("*", numericBinop (*)),
              ("/", numericBinop div),
              ("mod", numericBinop mod),
              ("quotient", numericBinop quot),
              ("remainder", numericBinop rem)]

primitivesの型を見てください。primitivesはlookupに期待されるようにペアのリストですが、ペアの値は[LispVal]からLispValへの関数です。Haskellでは、簡単に関数を他のデータ構造に格納することができます。ただし、格納される関数は全部同じ型を持っている必要があります。

また、格納されている関数自身、関数numericBinop(まだ定義されてませんが)の結果です。numericBinopはHaskellのプリミティブ関数を取り、引数のリストを解すコードでラップし、プリミティブ関数を適用し、結果をNumberコンストラクタでラップして返します。

numericBinop :: (Integer -> Integer -> Integer) -> [LispVal] -> LispVal
numericBinop op params = Number $ foldl1 op $ map unpackNum params

unpackNum :: LispVal -> Integer
unpackNum (Number n) = n
unpackNum (String n) = let parsed = reads n in 
                          if null parsed 
                            then 0
                            else fst $ parsed !! 0
unpackNum (List [n]) = unpackNum n
unpackNum _ = 0

R5RS Schemeと同様、2引数だけに囚われないことにします。私たちの定義する数値操作はどんな長さのリストにも働くことができます。よって(+ 2 3 4) = 2 + 3 + 4で、(- 1 5 5 3 2) = 15 - 5 - 3 - 2です。ビルトイン関数foldl1を使ってこうします。foldl1は、本質的には、リスト中の全てのコンス演算子を二項演算子opに置きかえます。

R5RS Schemeとは違って、私たちは弱い型付けの一種を実装しています。それは、もし値が数値として解釈できる(文字列"2"のように)ならば、それが文字列であっても数値として扱うということを意味します。これはunpackNumに幾つか余分の節を付けることで実現します。もし私たちが文字列をunpackしているならば、Haskellのビルトイン関数readsでパースできるか試してみます。readsは(パースされた結果の値、残りの文字列)というペアのリストを返します。

リストに対しては、一つの値のみを持つリストに対してパターンマッチを行い、それをunpackすることを試みます。他は全て次の場合に流れつきます。

どんな理由にしろ数値を得ることができなかった場合、今のところは0を返すことにしておきます。すぐ後にこれがエラーを出すようにします。

通常通りコンパイル・実行してください。関数の引数それぞれに対してevalを呼ぶことで、いかに私たちが入れ子の表現を「タダで」使うことができるかに注目しましょう。

% ghc -package parsec -o eval listing7.hs
% ./eval "(+ 2 2)"
4
% ./eval "(+ 2 (-4 1))"
2
% ./eval "(+ 2 (- 4 1))"
5
% ./eval "(- (+ 4 6 3) 3 5 2)"
3

練習問題4

1. symbol?・string?・number?など、R5RSの様々なtype-testingプリミティブを加えなさい。
2. unpackNumを値がたとえ数値としてパースできるリスト・文字列であっても、数値でなければ必ず0を返すようにしなさい。
3. R5RSのsymbol-handling functionsを加えなさい。シンボルとは私たちがアトムと呼んできたものです。