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

型エラーや悪い引数などを対処できるようになったので、プリミティブのリストを、単純な計算以上のことをするように肉付けしていきます。等価性評価、条件演算子、基本的な文字列操作などを加えましょう。
始めに、以下をプリミティブのリストに加えてください。
これらは私たちがまだ書いていない補助関数、numBoolBinop・boolBoolBinop・strBoolBinopに依存しています。可変長の引数を取り整数を返す代わりに、これらは全て2つの引数を取り真偽値を返します。これらが互いに引数の型のみが違うので、一般化されたboolBinop関数に重複箇所をまとめましょう。boolBinopはその引数に適用するunpackerによってパラメータ化されます。
引数それぞれが型エラーを投げるかもしれないので、(Errorモナドの)doブロックの中でそれらを順番にunpackしなくてはなりません。その後、opを2つの引数に適用して、それをBoolコンストラクタで包んで返します。どんな関数もバックティックで囲むことで中置演算子にすることができます(`op`)。
型シグネチャも見てみてください。boolBinopは2つの関数を最初の二引数として取ります。一つ目の関数はLispValからHaskellの地の型に戻すのに使われ、二つ目が実際に行うべき操作となります。振舞の違うところをパラメータ化することで、関数を再利用しやすくできます。
ではboolBinopを異なるunpackerで特定化する3つの関数を定義しましょう。
私たちはHaskellにどのように文字列をLispValからunpackするかまだ教えていませんでした。これは値に対してパターンマッチを行ない、それを返すかエラーを投げる、というunpackNumと似た動作をします。繰り返しになりますが、文字列として解釈できる値を渡された時は、これらの関数は暗黙の内にそれを文字列に変換します。
真偽値をunpackするのにも似たようなコードを使います。
次のステップに進む前に、これをコンパイル・テストして上手くいくことを確かめましょう。
では次に、我々の評価器にif節を加えましょう。標準Schemeと同じように、私たちの評価器は#fを偽とし、それ以外の値全てを真とします。
これは入れ子のパターンマッチの例です。ここでは、4つの要素を持つリストに対してマッチを行っています。4要素の内、最初はアトム"if"でなければなりませんが、他はどんなSchemeの式でもよいです。最初の引数を取って評価し、それが真であればその次を、偽であればその次の次の式を評価します。
コンパイル・実行してください。条件分岐で遊ぶことができます。
おまけとして、リストを扱うプリミティブも加えましょう。Schemeのリストをペアによってではなく、Haskellの代数的データ型によって表現することにしたので、多くのLispに比べこれらプリミティブの定義はいくらか複雑になります。書き下されたS式に対してそれらがどう振る舞うかで考えるのが一番簡単でしょう。
これらは極めて直感的にパターン節に変換することができます。(x : xs)がリストの最初の要素と残りを分けてくれることを思い出してください。
cdrでも同じことをします。
最初の3ケースは一つの節で表現することができます。私たちのパーサは()をList []として表現していて、(x : xs)というパターンを[x]に対してマッチさせる時、xsは[]に束縛されます。他の場合は別の節で扱いましょう。
consはちょっと難しいので、節一つ一つを見ていきましょう。何かとnilをコンスすると、nilを最後とする一要素のリストができます。
何かとリストをコンスすると、リストの先頭に要素を貼り付けるような感じになります。
ただし、そのリストがDottedListだった場合、末尾は変らないのでそれはDottedListのままであるべきです。
二つの非リストをコンスした場合、もしくはリストを先にした場合、DottedListができます。これはそのようなコンスセルがnilで終わっていないからです。
最後に、2つより多いまたは少ない引数を渡されたらエラーです。
私たちの最後のステップはeqv?を実装することです。Schemeは三段階の等価性述語を提供しています: eq?、eqv?、そしてequal?です。eq?とeqv?は私たちの目的からすると大体同じです;それらは2つのものを、同じ字面を持てば同じであると認識し、かなり遅い述語です。そこで私たちは一つだけ関数を書いて、eq?とeqv?という2つの名前で登録することができます。
リストの比較以外、これらの殆どは自明です。これはリストが同じ長さかどうか確かめた後、2つのリストをzipし、allを使ってどれか一つでもeqvPairが偽を返すペアがあれば偽を返すようにします。eqvPairは局所的定義の一例です。それはwhereを使って定義され、普通の関数のように働きますが、eqvのその節のその部分のみで有効です。eqvは引数の数が2である限りエラーを投げないので、Left err -> Falseが実行されることはありません。
以前私たちは弱い型付けを導入したので、型を無視して2つの値が同じと解釈できるかどうか見るequal?関数を実装します。例えば、(eqv? 2 "2") => #fですが、(equal? 2 "2") => #tであって欲しいのです。基本的には、unpack関数全てを試してみて、その中のどれかがHaskell的に等しければ真を返すようにします。
明らかな方法は、unpack関数をリストに格納してmapMを使ってそれらを順に実行するというものですが、残念ながら、これは上手くいきません。なぜなら、標準ではHaskellはリストは同じ型のものしか含むことができないからです。色々なunpack関数は違った型の値を返すので、同じリストにしまうことはできません。
ここでは型クラスによって制約される異型リスト(heterogeneous list)を作るために存在型というGHCの拡張を使うことでこの問題を回避します。Haskellでは言語拡張はとてもありふれたことです。言語拡張はそれなりに大きなプログラムを書くときには事実上必須で、しばしば異なる実装間で互換性があります(存在型はHugsとGHCの両方で動き、標準化の候補です)。この拡張を使うために特別なフラグをコンパイラに渡す必要があることに注意してください。後述してあるように -fglasgow-exts を付けるか、より新しい、 -XExistentialQuantification を付けるか、あるいは {-# LANGUAGE ExistentialQuantification #-} というプラグマをファイルの先頭に付けるかのどれかをする必要があります。一般に -Xfoo というコンパイラのフラグをつけることと {-# LANGUAGE foo #-} というプラグマをソースコード中に入れることは等価です。
最初にやらなければならないのは、LispVal -> 何かという関数において、その「何か」が同値性をサポートしていればどんなものでも保持することのできる型を定義することです。
これは、型の制約を除けば、普通の代数的データ型と同じようなものです。上の定義は「Eqのインスタンスであるどんな型についても、LispValからその型への関数で、エラーを投げるかもしれないものからUnpackerを定義することができる」と言っています。AnyUnpackerで関数をラップしなければなりませんが、そうすれば私たちはUnpackerのリストを作ることができ、やりたかったことができるようになります。
equal?に直接取り掛かるのではなく、まずunpackerを取ってそれがunpackする2つのLispValが等しいかどうか判断するヘルパー関数を定義しましょう。
実際の関数を得るためにパターンマッチした後、ThrowsErrorモナドのためのdoブロックに入ります。ここでLispValからHaskellの値を取り出し、それらが等しいかどうか調べます。もしその過程のどこかでエラーが起これば、constを使って偽を返します。constを使うのはcatchErrorがエラーに適用する関数を求めているからです。
最後に、equal?をこれらの補助関数を使って定義します。
最初のアクションが[unpackNum, unpackStr, unpackBool]の異型リストを作り、それに部分適用された(unpackEquals arg1 arg2)をmapします。これはBoolのリストを作るので、Preludeの関数orでそのどれか一つでも真であれば真を返すようにします。
二つ目のアクションはeqv?で2つの引数を比べます。equal?の方がeqv?より緩くあってほしいので、equal?は少なくともeqv?が真を返す時は真を返すべきです。加えて、これによってリストやdotted-listのような場合を扱わなくてよくなります(ただ、これはバグを引き起こします。このセクションの練習問題2番を見てください)。
最後に、equal?はこれらの値のorを取って、結果をBoolコンストラクタに包んでLispValを返します。let (Bool x) = eqvEquals in xは代数的データ型からさっと値を取り出すやり方で、Bool xをeqvEqualsの値にパターンマッチさせ、xを返します。let式の結果はキーワードinに続く式の結果です。
これらの関数を使うには、プリミティブのリストに加える必要があります。
このコードをコンパイルするには、-fglasgow-extsでGHC拡張を有効にしなければなりません。
練習問題