|
== 評価器作成の手始め ==
== Beginning the Evaluator ==
今の所、我々のパーサは与えられたプログラム片を認識するかしないかを出力していただけです。機能するSchemeインタプリタに向かって最初の一歩を取ろうとしています - プログラム片に値を割り当てることによって。初めはゆっくりと進みますが、直に意味ある計算を行うところまで辿りつきます。
Currently, we've just been printing out whether or not we recognize the given program fragment. We're about to take the first steps towards a working Scheme interpreter: assigning values to program fragments. We'll be starting with baby steps, but fairly soon you'll be progressing to doing working computations.
Let's start by telling Haskell how to print out a string representation of the various possible LispVals:
まずはHaskellにいろんな<code>LispVal</code>の文字列表現の表示方法を教えるところから始めましょう。
<syntaxhighlight lang="haskell">
showVal :: LispVal -> String
showVal :: LispVal -> String
showVal (String contents) = "\"" ++ contents ++ "\""
showVal (Atom name) = name
showVal (Number contents) = show contents
showVal (Bool True) = "#t"
showVal (Bool False) = "#f"
</syntaxhighlight>
これが私たちにとって初めての、本物のパターンマッチの導入です。パターンマッチは代数的データ型を分解し、そのコンストラクタに応じてコード節を選び、それぞれの部分を変数に束縛する手立てです。どんなコンストラクタもパターンの中に現れることができます。パターンはタグが与えられた値のタグと同じで、全てのサブパターンが対応する部分に一致する場合マッチします。パターンは任意の深さに入れ子にすることができ、マッチングは内から外、左から右の順番で行なわれます。関数定義の節は書かれた順にマッチするまで試されます。もしこの説明が難しく感じられても、これからさらに深く評価器について学ぶ時、深く入れ子になったパターンにいくつかあたることになります。
This is our first real introduction to pattern matching. Pattern matching is a way of destructuring an algebraic data type, selecting a code clause based on its constructor and then binding the components to variables. Any constructor can appear in a pattern; that pattern matches a value if the tag is the same as the value's tag and all subpatterns match their corresponding components. Patterns can be nested arbitrarily deep, with matching proceeding in an inside -> outside, left -> right order. The clauses of a function definition are tried in textual order, until one of the patterns matches. If this is confusing, you'll see some examples of deeply-nested patterns when we get further into the evaluator.
現時点においては、上述の定義の一つ一つが<code>LispVal</code>のコンストラクタの一つにマッチし、右辺がそのコンストラクタの値に対して何を行うか示している、ということだけ覚えておいてください。
For now, you only need to know that each clause of the above definition matches one of the constructors of LispVal, and the right-hand side tells what to do for a value of that constructor.
The List and DottedList clauses work similarly, but we need to define a helper function <span class="inline_code">unwordsList</span> to convert the contained list into a string:
<code>List</code>と<code>DottedList</code>節は似たように働きますが、中のリストを文字列に変換するヘルパー関数<code>unwordsList</code>を定義する必要があります。
<syntaxhighlight lang="haskell">
showVal (List contents) = "(" ++ unwordsList contents ++ ")" ▼ showVal (DottedListList head tailcontents) = "(" ++ unwordsList head ++ " . " ++ showVal tailcontents ++ ")"
▲ showVal ( ListDottedList contentshead tail) = "(" ++ unwordsList contentshead ++ " . " ++ showVal tail ++ ")"
</syntaxhighlight>
The unwordsList function works like the Haskell Prelude's [http://www.haskell.org/onlinereport/standard-prelude.html#$vunwords unwords] function, which glues together a list of words with spaces. Since we're dealing with a list of LispVals instead of words, we define a function that first converts the LispVals into their string representations and then applies unwords to it:
<code>unwordsList</code>関数はHaskellプレリュードのリスト中の文字列をスペースで接ぎ合わせる[http://www.haskell.org/onlinereport/standard-prelude.html#$vunwords unwords]関数のように働きます。ここでは<code>LispVal</code>のリストを扱っているので、<code>LispVal</code>を文字列表現に直してからそれに<code>unwords</code>を適用する関数を作ります。
<syntaxhighlight lang="haskell">
unwordsList :: [LispVal] -> String
unwordsList =:: unwords[LispVal] .-> map showValString
unwordsList = unwords . map showVal
</syntaxhighlight>
<code>unwordsList</code>の定義は引数を含みません。これは''point-free style''、つまり関数定義を関数合成と部分適用のみで書く手法の例です。個々の値や"points"にかかずらわる代わりに、いくつかの組み込み関数の組み合わせを使います。まず、[http://www.haskell.org/onlinereport/standard-prelude.html#$vmap map]を<code>showVal</code>に部分適用すると、<code>LispVal</code>のリストを取り、それらの文字列表現のリストを返す関数が出来ます。Haskellの関数は''カリー化''されています。これは、<code>map</code>のような二引数関数が実際は一引数関数を返す関数だということを意味します。結果として、引数を一つだけ与えた場合、好きなようにできる一引数関数を得ることができます。この場合はそれを<code>unwords</code>と合成します。すなわち、<code>map showVal</code>は<code>LispVal</code>のリストをそれらの文字列表現のリストに変え、<code>unwords</code>がそれをスペースで繋ぎ合わせます。
Our definition of unwordsList doesn't include any arguments. This is an example of ''point-free style''<nowiki>: writing definitions purely in terms of function composition and partial application, without regard to individual values or "points". Instead, we define it as the composition of a couple of built-in functions. First, we partially-apply </nowiki>[http://www.haskell.org/onlinereport/standard-prelude.html#$vmap map] to showVal, which creates a function that takes a list of LispVals and returns a list of their string representations. Haskell functions are ''curried''<nowiki>: this means that a function of two arguments, like </nowiki><span class="inline_code">map</span>, is really a function that returns a function of one argument. As a result, if you supply only a single argument, you get back a function one argument that you can pass around, compose, and apply later. In this case, we compose it with unwords: <span class="inline_code">map showVal</span> converts a list of LispVals to a list of their string representations, and then <span class="inline_code">unwords</span> joins the result together with spaces.
上で使った[http://www.haskell.org/onlinereport/standard-prelude.html#tShow show]はどんな<code>Show</code>クラスのインスタンス型の値も文字列に変換する関数です。<code>LispVal</code>も同じように扱いたいので、<code>show</code>メソッドとして<code>showVal</code>を用いる<code>Show</code>クラスのメンバーにします。
We used the function [http://www.haskell.org/onlinereport/standard-prelude.html#tShow show] above. This standard Haskell function lets you convert any type that's an instance of the class Show into a string. We'd like to be able to do the same with LispVal, so we make it into a member of the class Show, defining its "show" method as showVal:
<syntaxhighlight lang="haskell">
instance Show LispVal where show = showVal
</syntaxhighlight>
A full treatment of typeclasses is beyond the scope of this tutorial; you can find more information in 型クラスの完全な解説はこのチュートリアルの範囲を越えています。[http://www.haskell.org/tutorial/classes.html other tutorials] and the や[http://www.haskell.org/onlinereport/decls.html#sect4.3 Haskell 98 report].により詳しい情報があります。
<code>readExpr</code>関数を、単に値を見つけたと報告するのではなく、パースした値の文字列表現を返すように変え、上の関数を試してみましょう。
Let's try things out by changing our readExpr function so it returns the string representation of the value actually parsed, instead of just "Found value":
<syntaxhighlight lang="haskell">
readExpr input = case parse parseExpr "lisp" input of
Left err ->> "No match: " ++ show err
Right val ->> <span class="changed_code">"Found " ++ show val</span>
</syntaxhighlight>
コンパイル・実行すると、
And compile and run...
<syntaxhighlight lang="text">
jdtang@debian:~/haskell_tutorial/code$ ghc -package parsec -o parser listing4.1.hs
jdtang@debian:~/haskell_tutorial/code$ ./parser "(1 2 2)"
Found (1 2 2)
jdtang@debian:~/haskell_tutorial/code$ ./parser "'(1 3 (\"this\" \"one\"))"
Found (quote (1 3 ("this" "one")))
</syntaxhighlight>
== 評価器作成の手始め: プリミティブ ==
== Beginnings of an evaluator: Primitives ==
Now, we start with the beginnings of an evaluator. The purpose of an evaluator is to map some "code" data type into some "data" data type, the result of the evaluation. In Lisp, the data ''types'' for both code and data are the same, so our evaluator will return a LispVal. Other languages often have more complicated code structures, with a variety of syntactic forms.
Evaluating numbers, strings, booleans, and quoted lists is fairly simple: return the datum itself.
eval :: LispVal -> LispVal
eval val@(String _) = val
We still can't do all that much useful with the program (witness the failed (+ 2 2) call), but the basic skeleton is in place. Soon, we'll be extending it with some functions to make it useful.
== 基本的なプリミティブを加える ==
== Adding basic primitives ==
Next, we'll improve our Scheme so we can use it as a simple calculator. It's still not yet a "programming language", but it's getting close.
<syntaxhighlight lang="haskell">
primitives :: [(String, [LispVal] -> LispVal)]
primitives =:: [("+"String, numericBinop[LispVal] (+-> LispVal)),]
primitives = [("-+", numericBinop (-+)),
("*-", numericBinop (*-)),
("/*", numericBinop div(*)),
("mod/", numericBinop moddiv),
("quotientmod", numericBinop quotmod),
("remainderquotient", numericBinop remquot)],
("remainder", numericBinop rem)]
</syntaxhighlight>
Look at the type of <span class="inline_code">primitives</span>. It is a list of pairs, just like <span class="inline_code">lookup</span> expects, ''but the values of the pairs are functions from [LispVal] to LispVal''. In Haskell, you can easily store functions in other data structures, though the functions must all have the same type.
Compile and run this the normal way. Note how we get nested expressions "for free" because we call eval on each of the arguments of a function:
<syntaxhighlight lang="text">
debian:/home/jdtang/haskell_tutorial/code#% ghc -package parsec -o eval listing7.hs
debian:/home/jdtang/haskell_tutorial/code#% ./eval "(+ 2 2)"
4
debian:/home/jdtang/haskell_tutorial/code#% ./eval "(+ 2 (-4 1))"
2
debian:/home/jdtang/haskell_tutorial/code#% ./eval "(+ 2 (- 4 1))"
5
debian:/home/jdtang/haskell_tutorial/code#% ./eval "(- (+ 4 6 3) 3 5 2)"
3
</syntaxhighlight>
{{Exercises|1=
# Add primitives to perform the various [http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3 type-testing] functions of R5RS: symbol?, string?, number?, etc. ▼# Change unpackNum so that it always returns 0 if the value is not a number, even if it's a string or list that could be parsed as a number.
# Add the [http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3.3 symbol-handling functions] from R5RS. A symbol is what we've been calling an Atom in our data constructors ▼}}
練習問題4
{{auto navigation|Error Checking and Exceptions|Parsing}}
▲# Add primitives to perform the various <code>symbol?</code>・<code>string?</code>・<code>number?</code>など、R5RSの様々な[http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3 type-testing] functions of R5RS: symbol?, string?, number?, etc.プリミティブを加えなさい。
{{auto category}}
# <code>unpackNum</code>を値がたとえ数値としてパースできるリスト・文字列であっても、数値でなければ必ず0を返すようにしなさい。
▲# Add the R5RSの[http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3.3 symbol-handling functions] from R5RS. A symbol is what we've been calling an Atom in our data constructorsを加えなさい。シンボルとは私たちがアトムと呼んできたものです。
| 