Cleanで関数プログラミング【第２部第６章】

目次へ最終更新 : 2002/12/15

第６章　インタプリタ

6.1　インタプリタ型プログラミング言語

6.2　パーサ

　本章では、（型検査のない、しかし、Cleanライクな）関数プログラミング言語のインタプリタを説明する。このインタプリタで使用される言語は、シンプルな純粋関数プログラミング言語である。演習では、この言語に、構成子、（抽象データ型を可能にする）パターン照合とリストの内包表記（ZF式）を拡張することができる。

　このインタプリタは、次章の表計算でも使用される。

　次セクションでは、まず、インタプリタ用の言語の説明を行う。

　残りのセクションでは、解釈に必要ないくつかのステップ、つまり、解析、グラフ変換及び評価を説明する。パーサについては、第２部第５章の解析技術を使用せずに、代わりに、専用の中置式パーサを使用する。解析は、あらゆる関数用の解析木をもたらす。グラフ変換は、解析木を、直接評価できる木に変換する。評価子は、それの評価を取り扱う。

　セクション4では、インタプリタのユーザーインターフェースを説明する。

6.1　インタプリタ型プログラミング言語
　我々の使用するインタプリタ型言語は、シンプルな純粋関数型言語である。その詳細な構文の説明はせずに、代わりに、多くの例によってそれを紹介する。これらの例は、ファイルtest.fpの中に見つけることができる。

多くの関数の定義

fac n = if (n=0) 1 (n*fac (n-1))

take n xs = if (xs=[]) [] (if (n=0) [] (hd xs : take (n-1) (tl xs))

filter p xs = if (xs=[]) [] (if (p (hd xs)) (hd xs : filter p (tl xs))
                                            (filter p (tl xs)))

notmodzero x y = y % x ~= 0 || x modulo y   // %は、定義済み中置演算子modである。

from x = x : from (x+1)

sieve xs = hd xs : sieve (filter (notmodzero (hd xs) (tl xs)))

primes = sieve (from 2)

　構文：条件ステートメント用の特別構文はないことが分かるが、代わりに、3つの引数を持つ関数ifを使用する。この方法では、関数の本体は、解析を簡単にする純粋中置式とみなすことができる。この言語とCleanの間の':'(cons)演算子の使用上の違いに注意。ここでは、':'は、純粋中置演算子である。従って、Cleanの[a:b]は、この言語のa:bと同等である。このことも解析を簡単にする。パターンと局所定義はサポートしない。

　データ型：定義済みデータ型は、num(int)、boolとlist(charとstringは読者が追加できる)のみである。組はまだサポートしないが、これも読者が加えることができる。この言語の型無し版では、リストを使って組を模倣できる。

　定義済み関数：if、hdとtlだけが、（ハードコードの）定義済み関数である。

　中置演算子：この言語は、以下の中置演算子をサポートしている。つまり、+、-、*、/、%、(mod)、^、=、~=、:(cons)、<、>、<=、>=である。今のところ、ユーザー自身が中置演算子を定義することはできない（演習参照）。

　カリー化は認められている。中置演算子@を使用して、１つの引数に、ある関数を適用することを指示する。

　レイアウト規則：レイアウト規則はシンプルで、関数定義は、行の最初に始まるので、行の最初から始まらない行は、前行の続きとみなされる。

インタプリタの使用
　インタプリタは、コマンドラインインターフェースを持つ。プロンプト(eval>)の後に、式を打ち込むことができる。起動中には、システムファイル(sys.fp)がロードされる。このシステムファイルは、take、drop、filterやmapのような標準的なリスト関数を保持する。ユーザーは、システム関数ファイルを編集できる。プロンプトでは、関数定義を含むユーザー定義ファイルをロードすることもできる。これは、コマンドload filenameによって行われる。ここでfilenameは、ファイルの名前（もしインタプリタと同一ディレクトリに無い場合にはそのパスも含める）である。ファイルの名前は、"引用符で囲まれては"ならない。

　ユーザー定義ファイルロード後、このファイル内で定義された関数を使用した式をプロンプト後に打ち込むことができる。例えば、例ファイルtest.fpのロード後に、take 30 primes。

6.2　パーサ
　関数又は式を解析する前に、まず、入力文字列をトークンのリストに変えなければならない。解析前のトークン化によって、+、-、*、^等のような中置演算子を認識し、文字のグループから識別子を形成する仕事から、パーサは解放される。関数tokenizeは、これを取り扱う。

:: Token = IdNum [Char] | Op [Char] | Lpar | Rpar | TokError [Char] Char

tokenize :: [Char] -> [Token]
tokenize []        = []
tokenize ['[]':xs] = [IdNum ['nil'] : tokenize xs]
tokenize ['<=':xs] = [Op ['<='] : tokenize xs]
tokenize ['>=':xs] = [Op ['>='] : tokenize xs]
tokenize ['<' :xs] = [Op ['<'] : tokenize xs]
tokenize ['>' :xs] = [Op ['>'] : tokenize xs]
tokenize ['~=':xs] = [Op ['~='] : tokenize xs]
tokenize [' ':xs]  = tokenize xs
tokenize ['\t':xs] = tokenize xs
tokenize ['(':xs]  = [Lpar : tokenize xs]
tokenize [')':xs]  = [Rpar : tokenize xs]
tokenize ['[':xs]  = [Lpar : tokenize xs]
tokenize [']':xs]  = [Op [':'], IdNum ['nil'], Rpar : tokenize xs]
tokenize [',':xs]  = [Op [':'] : tokenize xs]
tokenize ['\n':xs] = []
tokenize l=:[x:xs] | oper [x]    = [Op [x] : tokenize xs]
                   | isCharNum x = [idnum : tokenize r]
                                 = [TokError ['Unexpected token'] x]
                             where (idnum, r) = readIdNum l

　tokenizeの定義は簡単である。識別子と数値は、同一のトークン（IdNum）であるとみなされる。空リスト[]は、既にtokenizerによって認識されている。また、リスト[1,2,3]という速記は、1 : 2 : 3 : nilに変えられる。','がリスト内でのみ使用されるので、これを行うことができるのである。

　パーサは、ただ１つの関数parseからなる。関数parseは、優先度と結合方法（左か右か）と共に、中置演算子のリストが与えられれば、任意の中置式を解析できる。これらは、(定)関数operatorsによって供給される。演算子は、3つ組のリストからなり、その最初のフィールドは、演算子それ自体を持ち、第２フィールドは、（比較の為だけに）その優先度を持ち、第３フィールドは、演算子の結合性（左か右か）を持つ。

operators = [(['+'] ,10,'l'),(['*'] ,20,'l'),(['%'] ,5,'l'),(['/'] , 20,'l'),
             (['^'] ,30,'r'),(['='] , 3,'r'),([':'] ,0,'r'),(['@'] ,100,'l'),
             (['-'] ,10,'l'),(['<'] , 4,'r'),(['>'] ,4,'r'),(['~='],  3,'r'),
             (['<='], 4,'r'),(['>='], 4,'r'),(['<='],4,'r'),(['>='],  4,'r')]

　解析結果は、木の式である。式用のデータ型は以下のものである。

:: Expr
 = Func [Char] Int Expr    // 関数の出現：その名前、アリティと本体の出現
 | Var [Char] Int          // 変数：その名前と引数の数（最初の変数は0）
 | BOOL Bool               // 論理値
 | Num Int                 // 整数値
 | Null                    // 空リスト
 | Inf Expr [Char] Expr    // 中置式：左引数、演算子、右引数
 | PreError [Char]         // エラーのある式。引数はメッセージである。
 | Empty                   // 未定義式。例えば、記入前の関数本体。
 | SysFunc [Char]          // 埋め込み関数（if、hd又はtl）

　我々が抱えている１つの問題は、使用する式が、純粋な中置式ではないということである。これらは、関数適用も持つ。これを処理する為、不可視な適用演算子@の存在を仮定する。@は、あらゆる関数名と引数の間に存在している。より多くの引数が存在する場合にも、@をその引数の間に置かれなければならない（これは、カリー化を容易にする）。

　例： if (n=0) 1 (n * fac (n-1))は以下のように読まれるはずである。

if @ (n=0) @ 1 @ (n * fac @ (n-1))

　この式については、パーサは、以下の解析木を生成する。

Inf (Inf (Inf SysFunc ['if']
              ['@']
              (Inf (Var ['n'] 0)
                   ['=']
                   (Num 0)))
         ['@']
         (Num 1))
    ['@']
    (Inf (Var ['n'] 0)
         ['*']
         (Inf (Func ['Fac'] 1 Empty)
              ['@']
              (Inf (Var ['n'] 0)
                   ['-']
                   (Num 1)))))

　この解析木は、以下のように描くことができる。

                            @
                           / |
             --------------  --------------
            @                              *
           / |                            / |
     ------   -----                 ------  ------
    @              1               n              @
   / |                                           / |
 --   --                                       --  --
if      =                                    fac     -
       / |                                          / |
      n  0                                         n  1

　実際には、パーサは、式内の各関数、変数と定数用に部分式Funcを生成する。システム関数と定数は、graphTransによって、正当な部分式に翻訳される。変数用の式は、parsefuncのplacevarsによって修正される。最後に、関数fillinは、facのEmptyな関数本体を、示された式のコピーと置換えるのに使用される。

6.2.1　関数parse
　関数parseは、再帰下降型パーサである。第２部第５章のパーサとは対照的に、このパーサは決定的である。解析は、構文木のトップレベルで始まる。パーサは、低水準の文法規則を使用して、トップレベルの文法規則（解析用の開始記号）を認識しようと試みる。そして、このパーサは、文法規則を降りていく。再帰的規則に対しては、再帰的な出現を認識する為に、同一のパーサが使用される。更に、パーサの構築には、パーサコンビネータを使用しないで、テーラーメードの関数を使用する。

　様々な優先度の演算子を持つ式の解析は、一種のシフト簡約解析によって行われる。次の演算子が発見されるまで、現在の演算子と引数に関してしなければならないことの決定を延期する。演算子の優先度を比較することによって、構文をどのように構築すべきかを決めることができる。

　データ型Contextは、パーサの中にある文脈をトレースするのに使用される。現在のところは、これは、括弧付けられた式を跡づける（括弧をバランスする）ためにのみ必要である。より込み入った式を解析したい場合には、Contextを拡張できる。

:: Context = Bexp | Exp

　parseの型：

parse :: [Context] [Token] [Expr] [Token] -> (Bool,Expr,[Token],String)

　引数：

現在のところ括弧のバランスの為にのみ使用される文脈のスタック
入力トークンリスト
現在までに構築されている式（最初は、式はまだないので、多くとも１つの要素を持つリストを使用する）
出会った最後の中置演算子。これは、優先度を比較する為に維持されなければならない。演算子に出会わなければ、リストは空であり、そうでなければ、１つの要素を持つ。

　結果は、以下のフィールドを持つ４つ組である。

解析が成功しているかを伝える論理値
parseの結果
入力文字列の余り。parseの再帰呼出は、部分式のみを解析し、呼出側の関数に返す。
解析が成功していない場合、結果4は、適切なエラーメッセージを持つ。

　関数parseExpとparseは以下のものである。

parseExp :: [Token] -> Expr
parseExp xs | ok = r
= PreError (fromString error)
where (ok,r,rem,error) = parse [Exp] xs [] []

parse cs        []        [e] op = (True,e,[],"")                                // 1
parse [Bexp:cs] [Rpar:xs] [e] op = (True,e,[Rpar:xs],"")                         // 2
parse [Bexp:cs] []         e  op = (False,PreError [],[],"Missing )")            // 3
parse cs        [Rpar:xs]  e  op = (False,PreError [],
                                        [Rpar:xs], "unexpected )")               // 4
parse cs        [Lpar:xs] [ ] op                                                 // 5
| ok && okPar            = parse cs (tl r) [f] op
                                 = (False,PreError [],[],
                                       if ok "missing )" er)
  where (ok,f,r,er) = parse [Bexp] xs [] []
        okPar = r <> [] && hd r == Rpar
parse cs        [Lpar:xs] [e] op                                                 // 6
|  ok && okRpar                  = parse cs (tl r) [Inf e ['@'] f] op
                                 = (False,PreError [],[],
                                       if ok "missing )" er)
  where (ok,f,r,er) = parse [Bexp] xs [] []
        okRpar = r <> [] && hd r == Rpar
parse cs     [IdNum i:xs] [ ] op = parse cs xs [Func i 0 Empty] op               // 7
parse cs     [IdNum i:xs] [e] op = parse cs xs
                                             [Inf e ['@'] (Func i 0 Empty)] op   // 8
parse        [Op o:xs]    []  [] = (False,PreError [],[],
                                    "term expected at:" +++ toString o)// 9
parse cs     [Op o:xs]    [e] []                                                 // 10
 | ok                            = parse cs r [Inf e o f] []
                                 = (False,f,r,er)
  where (ok,f,r,er) = parse cs xs [] [Op o]
parse cs     [Op o1:xs]    [e] [Op o2]                                           // 11
 | prio o1 < prio o2 ||
   prio o1 == prio o2 &&
   assoc1 o2                     = (True,e,[Op o1:xs],"")
 | ok                            = parse cs r [Inf e o1 f] [Op o2]
                                 = (False,f,r,er)
  where (ok,f,r,er) = parse cs xs [] [Op o1]
parse cs [TokError er x:xs] es os = (False, PreError [], [], toString er)        // 12
parse cs             [x:xs] es os = (False, PreError "", [],
                                     "Syntax error near: " +++
                                     toString (printToken x))                    // 13

入力は残っておらず、eは結果である。
入力の右括弧と、文脈はブラケットの付いた式であるので、呼出側の関数に帰る（入力の括弧は除く）。
空の括弧とまだブラケット式の中にある文脈なので、エラーメッセージを出す。
右括弧とブラケットの中にない文脈なので、エラーメッセージを出す。
入力のLparは、これがOKであることが分かれば、まず、ブラケットの付いた式の再帰的呼出を行い、それから、可能な左手側としてのこのBexpの再帰呼出を継続する。
左手側の入力のLparは既に存在している。ブラケットの付いた式を再帰的に解析する。これは、関数適用の右手側になる。ここでは、左手側としての関数適用で、parseを再帰的に呼び出す。
入力の識別子。中置式の候補の左側として、この識別子を持つparseの再帰呼出。
既に左手側が解析されている入力の識別子、つまり、関数適用は、候補の左手側としてのこの関数適用を継続する。
入力の中置式は存在するが、左手側は存在しないので、エラー。
入力の中置演算子と左手側は存在するが、優先度を比較すべき前の演算子がないので、右手側の再帰呼出を行う。ここでは、優先度を次の演算子と比較する為に、その演算子が引数として与えられる。それに対応する中置式の木を形成し、左手側としてのこの木を再帰呼出する。
関連する2つの中置演算子の優先度を比較する。以下の例を参照。
トークンエラーに出くわすと、これは、パーサエラーに変わる。
全ての正しい場合は、既に処理されているので、これはエラーであるはずである。

ケース10と11の例：

この解析スキームに関する注意

　parseの修正なく、中置演算子としてモデル化できる限り、このパーサをより複雑な式に容易に拡張できる。ZF式でさえ、この方法で解析できる（演習6.1参照）。

関数定義の解析

　parsefileによるスクリプトファイルの解析は、ファイル内の関数定義の解析からなる。これは、ファイル内の行を読込み、空行をスキップし、1つの関数定義を作り上げる行（字下げのない行に続く字下げされた行）を結合することによって、行われる。

parsefile :: [([Char],[Expr],Int,Expr)] String *Files
              -> *(Bool,*Files,[([Char],[Expr],Int,Expr)])
parsefile sysfuncs fn files = (okparse && okfillin, files2,resfuncs)
where
  (input,files2) = ReadFileStrings fn files
  funcs          = (map parsefunc o mergeLines o remEmpty o map fromString) input
  parseErrors    = [b \\ (_,_,_,b) <- funcs | isParseError b]
  okparse        = parseErrors == []
  okfillin       = fillinErrors == []
  fillinErrors   = [b \\ (_,_,_,b) <- recfuncs | isParseError b]
  recfuncs       = map (fillin (sysfuncs ++ recfuncs)) funcs // 再帰定義！！
  resfuncs | okparse &&
             okfillin     = recfuncs
           | not okparse  = [([],[],0,PreError (flatten [print b ++ ['\n']
                             \\ b <- parseErrors]))]
           | not okfillin = [([],[],0,PreError (flatten [print b ++ ['\n']
                             \\ b <- fillinErrors]))]

remEmpty xss = [xs \\ xs <- xss | xs <> []]

mergeLines = foldr f []
             where f a [[' ':b]:bs]  = [(a ++ [' ':b]) : bs]
                   f a [['\t':b]:bs] = [(a ++ [' ':b]) : bs]
                   f a bs            = [a : bs]

　関数定義は、（最低の優先度を持つ）トップの演算子としての'='を持つ中置式と見ることもでき、その左側は、関数名の変数への適用であり、右手側は、関数の定義本体式である。

　parsefuncは、変数名のフィルタと、それらの関数本体内での置換を処理する（placevarsは、置換を行わない）。

parsefunc :: [Char] -> ([Char],[Expr],Int,Expr)
parsefunc inv = pfunc (Inf func ['='] body)
where func = (parseExp o tokenize) (takeWhile (noteq '=') inv)
      body = (parseExp o tokenize) (tl (dropWhile (noteq '=') inv))

pfunc (Inf l ['='] body) = (name,vars,#vars,substbody)
where [Var name _ :vars] = findVars l
      substbody | isParseError body = PreError (['Error in function '] ++ name
                                         ++ [': '] ++ error
                                    = placevars vars (graphTrans body)
      (PreError error)              = body

findVars (Func n a b)    = [Var n 0]
findVars (Inf l ['@'] r) = findVars l ++ findVars r

placevars vs (Func f nv bf) | vn == (-1) = Func f nv bf
                                         = Var f vn
where vn = hd ([i \\ (i,Var v n) <- zip([0..],vs) | v == f] ++ [-1])
placevars vs (Inf a o b) = (Inf (placevars vs a) o (placevars vs b))
placevars vs x           = x

　解析された関数は、組のリスト、つまり、(name, variables, nr_of_vars, body_expression)の中に維持される。

　式内では、他の関数呼出が発生する。これらの関数呼出は最初に、(Func name 0 Empty)と解析される。ここで、nameは、関数の名前である（Exprの定義参照）。評価をスピードアップする為に、関数に対応する式は、評価前に既に置換えられる（実行時検索を回避する）。これは、関数fillinで行われる。fillinでは、その関数の結果は、その引数として使用できることに注意（従って、置換えられる本体はそれ自体、既に置換えられている）！

recfuncs = map (fillin (sysfuncs ++ recfuncs)) funcs
   ^                                    ^
   |____________________________________|

　非遅延（関数型）言語では、これは、再帰関数定義の無限再帰に結びつくだろう。しかし、遅延関数型言語では、これは、ポインタの（同じように効率的な）代わりである。

　fillinでは、式内に出現する関数が実際に存在するかどうかも検査される。

fillin :: [([Char],[Expr],Int,Expr)] ([Char],[Expr],Int,Expr) ->
          ([Char],[Expr],Int,Expr)
fillin pfs (n,vs,nvs,bf) = (n,vs,nvs,fbody)
where fbody | okfill = fillinbody
                     = PreError (['Error in '] ++ n ++ [': '] ++ error)
      (okfill,fillinbody,error) = fillbody pfs bf

fillbody pfs (Func name n b) | isEmpty fs = (False,PreError [],
                                             ['function not found: '] ++ name)
                                          = (True,Func name nvs bf, [])
where [(_,_,nvs,bf):_] = fs
      fs = findfuncs name pfs

fillbody pfs (Inf e1 o e2)                = (okleft && okright,
                                             Inf fillinleft o fillinright,
                                             errorleft ++ errorright)
where (okleft,fillinleft,errorleft)       = fillbody pfs e1
      (okright,fillinright,erroright)     = fillbody pfs e2

fillbody pfs x                            = (True,x,[])

findfuncs name fss = [(n,vs,nvs,b) \\ (n,vs,nvs,b) <- fss | name == n]

解析された式の変換

　parseは、関数名、数値、if、hdとtlのような定義済み（システム）関数を区別していない解析木を返す。graphTransは、これを処理する。

graphTrans :: Expr -> Expr
graphTrans (Inf e1 oper e2)             = Inf (graphTrans e1) oper
                                              (graphTrans e2)
graphTrans (Func ['True'] n bf)         = BOOL True
graphTrans (Func ['False'] n bf)        = BOOL False
graphTrans (Func ['hd'] n bf)           = (SysFunc ['hd'])
graphTrans (Func ['tl'] n bf)           = (SysFunc ['tl'])
graphTrans (Func ['if'] n bf)           = (SysFunc ['if'])
graphTrans (Func ['nil'] n bf)          = Null
graphTrans (Func f n bf) | isNum (hd f) = Num (toInt (toString) f))
                                        = Func f n bf
graphTrans x                            = x

6.3　評価
　parseEvalは、入力文字列の解析と評価を処理する。式が評価される前に、まず、この式で出現する関数本体が置換される。これは、関数fillbodyによって行われる（parsefileも参照）。

parseEval :: [([Char],[Expr],Int,Expr)] [Char] -> [Char]
parseEval fs xs | okparse && okfillin = printeval (eval fillexp [])
                | not okparse  = perror
                | not okfillin = fillinerror
where okparse                        = not (isParseError exp)
      (PreError perror)              = exp
      (okfillin,fillexp,fillinerror) = (fillbody fs o graphTrans) exp
      exp                            = (parseExp o tokenize) xs

eval :: Expr [Expr] -> Expr

　evalは、入力として式及びオペランドスタックを取る式を評価する。

　以下では、evalのいくつかの場合を議論する。

eval (Num n) es = (Num n)
eval (BOOL b) es = (BOOL b)
eval (PreError s) es = (PreError s)

　これらは、何も起こらないので、簡単な場合である。

eval (SysFunc ['if']) [BOOL t,e2,e3:es] | t = e2
                                            = e3

　ifの評価は、スタック上に3つのオペラントを必要とする。最初のオペランドの評価がTrueならば、第2のオペランドが返ってくるが、そうでなければ、第3のものが返ってくる。

eval (SysFunc ['hd']) [Inf h [':'] t:es] = h
eval (SysFunc ['tl']) [inf h [':'] t:es] = t

　hdとtlの評価は、スタック上に1つのオペランドを必要とする。これは、頭部と尾部のconsを表現する中置式でなければならない。hdの場合には、頭部を返し、そうでなければ、尾部を返す。

eval (Func f n bf) es | #es < n = partapp (Func f n bf) es
                                = eval (substvar es bf) (drop n es)
where partapp e [] = e
      partapp e [ex:es] = partapp (Inf e '@' ex) es

      substvar es (Var x n) = es ! n
      substvar es (Inf a o b) = Inf (substvar es a) o (substvar es b)
      substvar es x = x

　関数呼出の評価。まず、スタックに十分な引数があるかを検査する。もし無いならば（関数のカリー化使用）、関数をその引数に適用することからなる元の式が返される（partapp）。そうでなければ、関数本体内で、引数がsubstvarによって置換され、その結果が、引数をスタックからポップした後に評価される。スタックの引数の場所は、その変数番号に正確に対応していることに注意。

eval (Inf e1 ['@'] e2) es = eval e1 [eval e2 [] : es]

　関数適用を表現する中置式を評価すると、スタックに右側（引数）がプッシュされ、左側のevalが呼び出される。その引数は、スタックに置かれ評価されるが、Cleanの遅延性によって、実際の評価は、本当に必要とされる時まで延期されるので、結果的に遅延インタプリタをもたらすことに注意。

eval (Inf h [':'] t) es = Inf (eval h es) [':'] (eval t es)

　頭部と尾部のconsを表現する中置式を評価すると、（遅延）評価された頭部と尾部を持つ同一式が返る。

eval (Inf e1 ['+'] e2) es  = Num (getNum (eval e1 []) + getNum (eval e2 []))
eval (Inf e1 ['-'] e2) es  = Num (getNum (eval e1 []) - getNum (eval e2 []))
eval (Inf e1 ['*'] e2) es  = Num (getNum (eval e1 []) * getNum (eval e2 []))
eval (Inf e1 ['/'] e2) es  = Num (getNum (eval e1 []) / getNum (eval e2 []))
eval (Inf e1 ['%'] e2) es  = Num (getNum (eval e1 []) mod getNum (eval e2 []))
eval (Inf e1 ['^'] e2) es  = Num (getNum (eval e1 []) ^ getNum (eval e2 []))
eval (Inf e1 ['<'] e2) es  = BOOL (getNum (eval e1 []) < getNum (eval e2 []))
eval (Inf e1 ['>'] e2) es  = BOOL (getNum (eval e1 []) > getNum (eval e2 []))
eval (Inf e1 ['<='] e2) es = BOOL (getNum (eval e1 []) <= getNum (eval e2 []))
eval (Inf e1 ['>='] e2) es = BOOL (getNum (eval e1 []) >= getNum (eval e2 []))
eval (Inf e1 ['~='] e2) es = BOOL (getNum (eval e1 []) <> getNum (eval e2 []))
eval (Inf e1 ['='] e2) es  = BOOL (eval e1 [] == eval e2 [])

　残っている中置式の評価は簡単である。getNumは、(Num num)式からnumを取り出す。分割はサポートされていないことに注意。

eval x es = (PreError (['Cannot be evaluated near: '] ++ print x))

　evalが適用可能でない場合、適切なエラーメッセージが生成される。

6.4　ユーザーインターフェース
　インタプリタは、コマンドラインインターフェースを持つので、ユーザーは、プロンプトの後に式を打込み、リターンを押し、結果を検査することができる。

　Startは、このようなインターフェースを開始する為の準備動作を行う。Startは、filesとsioを開き、sys.fpからシステム関数を読込み、ioの残りを処理するProcessLinesを呼出す。出力のバッファリングを避ける為、結果は、出力に文字列全体として書かれるのではなく、一文字一文字書かれる。これは、ユーティリティ関数fwriteclistによって行われる。

Start :: *World -> *File
Start world = finalsio
where
  (files,worldwithoutfiles) = openfiles world
  (sio,files2)              = stdio files
  hallosio                  = fwrites hallo sio
  syssio | ok               = fwriteclist ['Reading system files\n'] hallosio
                            = fwriteclist (firstError sysfuncs) hallosio
  (finalsio,_)              = ProcessLines sysfuncs [] syssio files3
  (ok,files3,sysfuncs)      = parsefile [] libfile files2

hallo = "Interpreter for simple functional programming language (in Clean) V1.0\n"
endstring = "quit\n"
prompt    = "\neval> "
libfile   = "sys.fp"

　ProcessLinesは、入力デバイス（端末）から入力文字列を再帰的に取り、それがquit、load filename又は評価されるべき式かどうかを検査する。

　quitに出くわす場合、ProcessLinesが返る。

　load filenameの場合、ファイル名を抜き出し、そのファイルを解析し、引数の（ファイルで見つけた）新規関数でProcessLinesを再帰的に呼出す。

　入力文字列が空である（ユーザーがリターンを打つ）場合、ProcessLinesが再帰的に呼出される。

　他の全ての場合では、入力文字列は式と想定されるので、parseEvalが、この文字列の為に呼出され、その結果が出力に書込まれ、ProcessLinesが再帰的に呼出される。

ProcessLines :: [([Char],[Expr],Int,Expr)]
                [([Char],[Expr],Int,Expr)] *File *Files
                -> *(.File,*Files);

ProcessLines sysfuncs funcs sio files
| string == endstring  = (readio,files)
| isload               = ProcessLines sysfuncs newfuncs loadsio files2
                         // ファイルのロード
| string == "\n"       = ProcessLines sysfuncs funcs readsio files
                         // 空行のスキップ
                       = ProcessLines sysfuncs funcs resultsio files
                         // 評価式
where
  promptsio            = fwrites prompt sio
  input                = fromString string
  (string, readsio)    = freadline promptsio
  resultsio            = fwriteclist (parseEval (sysfuncs ++ funcs) input) readsio
  (isload,fn)          = isloadstring input
  loadsio | ok         = fwriteclist ['No errors in file'] readsio
                       = fwtiteclist (firstError newfuncs) readsio
  (ok,files2,newfuncs) = parsefile sysfuncs filename files
  filename             = toString (takwWhile (noteq '\n') fn)

isloadstring ['load ': fn] = (True,fn)
isloadstring x             = (False,[])

6.5　インタプリタ用の例プログラム
Sys.fp（システムファイル）

from x = x : from (x+1)
fromto x y = if (x=y) [x] (x : fromto (x+1) y)
downto x y = if (x=y) [x] (x : downto (x-1) y)
take n xs = if (n=0) nil (if (xs = nil) nil ((hd xs) : take (n-1) (tl xs)))
drop n xs = if (xs=[]) [] (if (n=0) xs (drop (n-1) (tl xs)))
map f xs = if (xs = []) [] (f ( (hd xs)) : (map f (tl xs)))
insert x xs = if (xs=[]) [x] (if (x < (hd xs))
                                 (x:xs)
                                 (hd xs : insert x (tl xs)))
sort xs = if (xs=[]) [] (insert (hd xs) (sort (tl xs))
add x xs = if (xs=[]) [x] (hd xs : add x (tl xs))
append xs ys = if (xs=[]) ys (hd xs : append (tl xs) ys)
concat xss = if (xss=[]) [] (if (hd xss = [])
                                (concat (tl xss))
                                (hd (hd xss) : concat (tl (hd xss) : tl xss)))
filter p xs = if (xs=nil) nil (if (p (hd xs))
                                  (hd xs : filter p (tl xs))
                                  (filter p (tl xs)))
takewhile f xs = if (xs = []) [] (if (f (hd xs))
                                     ((hd xs) : takewhile f (tl xs))
                                     [])
foldr f a xs = if (xs = []) a (f (hd xs) (foldr f a (tl xs)))
foldl f a xs = if (xs = []) a (foldl f (f a (hd xs)) (tl xs))

Test.fp（例ファイル）

fac n = if (n=0) 1 (n*fac (n-1))
notmodzero x y = y % x ~= 0
mod x y = x % y
sieve xs = (hd xs) : sieve (filter (notmodzero (hd xs)) (tl xs))
primes = sieve (from 2)

6.6　インタプリタに型検査を加える
　次のステップは、型検査器をインタプリタに拡張することである。型検査は、実行時エラーを排除できる。というのも、そのエラーをコンパイル時に既に検知するからである。例えば、整数を文字列に加えたり、異なった型の要素を持つリストを有したり等である。インタプリタに使用する型検査器は、ユーザーが関数の型を与えることなく、その型を導出できる。

6.6.1　型検査器がもたらすインタプリタ型言語の制限
　型検査器は、インタプリタ型言語に一定の制限を課す。型検査を簡潔にする為、この制限が含まれる。演習では、これらの制限を除去する提案を行う。

　最初の制限は、定義ファイルの関数が、依存性によって順序付けられていなければならないということである。これは、関数fが関数gに依存している（gがfの定義内に現れる）ならば、定義ファイル内において、fの前にgを定義しなければならないということを意味する。

　結果として、相互依存関数は認められない。例えば、

f = 1 : g
g = 2 : f,

　は、（今のところ）認められない定義である。

　再帰関数定義は認められる。

型の定義

:: Type = VarT Int | Arrow Type Type | NumT | BoolT |
          ListT Type | TypeError String | CharT

　例：eval>プロンプトの後にinfoと打込むと、現在ロードされている関数の型が表示される。

from :: num -> [num]
fromto :: num -> num -> [num]
downto :: num -> num -> [num]
take :: num -> [t0] -> [t0]
drop :: num -> [t0] -> [t0]
map :: (t0 -> t1) -> [t0] -> [t1]
insert :: num -> [num] -> [num]
sort :: [num] -> [num]
add :: t0 -> [t0] -> [t0]
append :: [t0] -> [t0] -> [t0]
concat :: [[t0]] -> [t0]
filter :: (t0 -> bool) -> [t0] -> [t0]
takewhile :: (t0 -> bool) -> [t0] -> [t0]
foldr :: (t0 -> t1 -> t1) -> t1 -> [t0] -> t1
foldl :: (t1 -> t0 -> t1) -> t1 -> [t0] -> t1
fac :: num -> num
notmodzero :: num -> num -> bool
sieve :: [num] -> [num]
primes :: [num]
compose :: (t0 -> t2) -> (t1 -> t0) -> t1 -> t2
som :: num -> num
plus :: num -> num -> num

サポートしている関数

fillintypes types (VarT n)    = deref types (types ! n)
fillintypes types (Arrow l r) = Arrow (fillintypes types l) (fillintypes types r)
fillintypes types (ListT l)   = ListT (fillintypes types l)
fillintypes types x           = x

substtypes [] t = t
substtypes [s:ss] t = substtypes ss (substtype s t)

substtype (VarT m, r) (VarT n) | n == m = r
                                        = VarT n
substtype t (Arrow l r) = Arrow (substtype t l) (substtype t r)
substtype t (ListT l) = ListT (substtype t l)
substtype t tt = tt

deref types (VarT n)
 = dref (types!n)
 where dref (VarT m) | n == m = VarT n
                              = deref types (VarT m)
       dref (Arrow l r) = Arrow (deref types l) (deref types r)
       dref (ListT l) = ListT (deref types l)
       dref x = x

deref types (Arrow l r) = Arrow (deref types l) (deref types r)
deref types (ListT a) = ListT (deref types a)
deref types x = x

occur (VarT n) (VarT m) = n == m
occur t (Arrow l r) = occur t l || ocurr t r
occur t (ListT l) = occur t l
occur t tt = False

// 型l rの単一化

unify types l r
 | l == r = (True,types,[])
          = (ok,restypes,error)
   where (ok,restypes) = unif types (deref types l) (deref types r)
         error = unerror ok (deref types l) (deref types r)

unif types (VarT n) (VarT m) | n == m = (True,types)
                                      = (True,update n (VarT m) types)
unif types (VarT n) b = (not (occur (VarT n) b), update n b types)
unif types a (VarT n) = (not (occur (VarT n) a), update n a types)
unif types (ListT a) (ListT b) = unif types a b
unif types (Arrow a b) (Arrow c d)
 = (rl && rr, if rl typesr typesl)
 where
  (rl,typesl) = unif types a c
  (rr,typesr) = unif typesl (deref typesl b) (deref typesl d)
unif types a b | a == b = (True,types)
                        = (False,types)

update n a xs = [y \\ (x,i) <- zip(xs,[0..]),y <- [if (i==n) a x]]

関数derivetypeとbuildType

derivetype functypes (func,vars,nvar,body)
 | not okBuild = (okBuild,TypeError (toString (['Error in '] ++ func ++ [', '] ++ error)),0)
               = (okBuild,renamedtype , # diftypes)
where

 types = [VarT n \\ n <- [0..]]

 bodytype = buildArrows nvar
 restype = (fillintypes dertypes bodytype)
 diftypes = (removeDup o typeVars) restype
 renamedtype = substtypes [(t, VarT n) \\ (t,n) <- zip (diftypes, [0..])] restype

 (okBuild,dertypes,nvartypes,error) = buildType body types (VarT nvar) nvar

 buildType (PreError m) types restype ntype
  = (False,[],0,fromString m)

 buildType (Var x n) types restype ntype
  = (okun,newtypes,ntype,error)
    where (okun,newtypes,error) = unify types (types ! n) restype

 buildType Null types restype ntype
  = (ok,newtypes,ntype+1,error)
  where (ok,newtypes,error) = unify types restype (ListT (VarT (ntype + 1)))

 buildType (SysFunc ['if']) types restype ntype
  = (ok,newtypes,ntype+1,error)
  where (ok,newtypes,error) = unify types restype (renType (ntype + 1) typeIf)

 buildType (SysFunc ['hd']) types restype ntype
  = (ok,newtypes,ntype+1,error)
  where (ok,newtypes,error) = unify types restype (renType (ntype + 1) 
                                                           (Arrow (ListT (VarT 0)) (VarT 0)))

 buildType (SysFunc ['tl']) types restype ntype
  = (ok,newtypes,ntype+1,error)
  where (ok,newtypes,error) = unify types restype (renType (ntype+1)
                                                           (Arrow (ListT (VarT 0)) 
                                                                  (ListT (VarT 0))))

 buildType (Func name n b) types restype ntype
  | name == func = (okself,newselftypes,ntype,erself)
                 = (okfound && ok,newtypes,ntype+nvartype,error)
  where (ok,newtypes,ermatch) = unify types restype (renType (ntype+1) typefunc)
        (okfound,typefunc,nvartype) = findtype name functypes
        (okself,newselftypes,erself) = unify types restype (fillintypes types bodytype)
        error = if (not okfound) (['function not found: '] ++ name ++ ['\n'])
                                 ermatch

 buildType (Num n) types restype ntype
  = (ok,newtypes,ntype,error)
  where (ok,newtypes,error) = unify types restype NumT

 buildType (CHAR n) types restype ntype
  = (ok,newtypes,ntype,error)
  where (ok,newtypes,error) = unify types restype CharT

 buildType (Inf l ['@'] r) types restype ntype
  = (okr && okl,newtypesl,ntypel,errorl++errorr)
  where
    (okr,newtypesr,ntyper,errorr) = buildType r types (VarT (ntype + 1)) (ntype + 1)
    (okl,newtypesl,ntypel,errorl) = buildType l newtypesr
                                    (Arrow (VarT (ntype + 1)) restype)
                                    ntyper

 buildType (Inf l [':'] r) types restype ntype
  = (ok && okl && okr, newtypesr,ntyper,errorr++errorl++error)
  where
   (ok,newtypes,error) = unify types restype (ListT elemtype)
   (okl,newtypesl,ntypel,errorl) = buildType l newtypes elemtype (ntype + 1)
   (okr,newtypesr,ntyper,errorr) = buildType r newtypesl (ListT elemtype) ntypel
   elemtype = VarT (ntype+1)

 buildType (Inf l o r) types restype ntype
  | isMember o [['='],['~=']] = (ok && okl && okr,
                                 newtypesr,ntyper,errorr++errorl++errorr)
  where
   (ok,newtypes,error) = unify types restype BoolT
   (okl,newtypesl,ntypel,errorl) = buildType l newtypes elemtype (ntype + 1)
   (okr,newtypesr,ntyper,errorr) = buildType r newtypesl elemtype ntypel
   elemtype = VarT (ntype+1)

 buildType (Inf l o r) types restype ntype
  | isMember o [['+'],['-'],['*'],['/'],['%'],['^']] = (ok && okl & okr,
                                                       newtypesl,
                                                       ntypel,
                                                       error++errorr++errorl)
  where
   (ok,newtypes,error) = unify types restype NumT
   (okr,newtypesr,ntyper,errorr) = buildType r newtypes NumT ntype
   (okl,newtypesl,ntypel,errorl) = buildType l newtypesr NumT ntyper

 buildType (Inf l o r) types restype ntype
  | isMember o [['<'],['>'],['<='],['>=']] = (ok && okl && okr,
                                              newtypesl, ntypel,
                                              error++errorr++errorl)
  where
   (ok,newtypes,error) = unify types restype BoolT
   (ok,newtypesr,ntyper,errorr) = buildType r newtypes NumT ntype
   (ok,newtypesl,ntypel,errorl) = buildType l newtypesr NumT ntyper

6.7　演習

ZF式を解析できるような方法で、パーサを拡張しなさい。例えば、（Cleanの）ZF式を考える。
これは、以下の中置式であると考えることができる。
ここでは、[1..10]とx % 2 = 0は、可読性の為、解析されないままである。

適切な優先度と結合性を持つ\\、|、<-の中置演算子を、パーサに加えなさい。

ZF式の式を囲む大括弧（'['と']'）の処理方法を考えなさい。

ユーザー定義中置演算子を解析・使用できるような方法で、parsefileを拡張しなさい。このような中置演算子の名前、優先度と結合性は、Cleanの場合に似た方法で加えるべきである。

例：関数concatによって定義される、優先度3を持つ左結合の演算子++を加える為に、infixl 3 ++ = concatを加える。

最初見ると、問題がある。関数を解析し始める前に、全ての中置演算子を見付けなければならない。それには、ファイルに２回行く必要がある。しかし、これは真ではない。fillinの使用に似た方法で遅延評価を利用すれば、ファイルに１回だけ行けばよくなる。

現在のところ、インタプリタは、整数、論理値とこれらのリストしか処理できない。文字及び文字列処理をインタプリタに拡張しなさい。これを行う為には、以下のものを加えなければならない。
- 文字'a'と文字列"this is a string"を処理するように、トークナイザを拡張しなければならない。（改行、'\n'等の特別記法に注意する）
- これらの新規データ型を処理するように、Exprを拡張しなければならない（文字列は、諸文字のリストとして表現できる）。
- 諸文字のリストを文字列として印字するように、printを調整しなければならない。
- （numとboolのような当たり前の）文字の評価を処理するように、evalを調整しなければならない。
（難問）演習6.7.1では、ZF式の解析をparseに加えたが、ここでは、ZF式の評価を評価子(evaluator)に加えなさい。これを行う為には、まず、ZF式の解析木を、評価可能な形に書換えなければならない。これは、GraphTransで行うことができる。

（プロジェクト）前セクションのインタプリタの主要な欠点の1つは、代数データ型を処理できないことである。例えば、木に似たデータに作用する演算を持つようなデータを定義するのは困難である。Cleanでは、このようなデータ型を以下のように定義する。
パターン照合を使用して、木に作用する関数を定義できる。
特に、このパターン照合を使用すると、代数データ型は非常にパワフルになる。

型を加えることなく、代数データ型をインタプリタに加えることができる。構成子とパターン照合のみを加える。構成子は、型のタグと見ることができるので、パターン照合を可能にするにはこれさえ加えればよい。構成子を関数名と区別する為に、構成子は、大文字から始まらなければならない。関数名が大文字から始まるのを認めてはならない。すると、このインタプリタの形式化手法においては、関数insertは以下のものになる。
構成子とパターン照合をインタプリタに加えるには、インタプリタに以下のものを加えなければならない。
- 関数定義の左手側のパターンを解析することと、パターンに出現する変数を抜き出すことを可能にするように、Parsefuncを調整しなければならない。
- 構成子を認識するようにGraphTransを調整しなければならない。
- 関数呼出の場合に正しい本体を選択する為に、パターン照合をevalに加えなければならない。
- 異なったパターンに対応する複数の本体を持つ関数を持てるように、Funcの定義を拡張しなければならない。
これを実現する為に、型Exprに以下のケースを拡張する。
Cstr [Char]：構成子は、1つの名前を持つ。

Funcp [Char] Int [([Expr],Expr)]：パターンを持つ関数は、名前、多くのパターンと以下のものからなる2つ組のリストを持つ。つまり、その組は、引数を照合しなければならないパターンのリスト（パターンも式である）と、照合が成功する場合に実行しなければならない本体式からなる。

インタプリタに、上記のものを加えて実装しなさい。

First Uploaded : December 8, 2002
Last Updated : December 15, 2002

Back

第６章 インタプリタ

6.1 インタプリタ型プログラミング言語

多くの関数の定義

インタプリタの使用

6.2 パーサ

6.2.1 関数parse

6.3 評価

6.4 ユーザーインターフェース

6.5 インタプリタ用の例プログラム

Sys.fp（システムファイル）

Test.fp（例ファイル）

6.6 インタプリタに型検査を加える

6.6.1 型検査器がもたらすインタプリタ型言語の制限

6.7 演習

第６章　インタプリタ

6.1　インタプリタ型プログラミング言語

6.2　パーサ

6.2.1　関数parse

6.3　評価

6.4　ユーザーインターフェース

6.5　インタプリタ用の例プログラム

6.6　インタプリタに型検査を加える

6.6.1　型検査器がもたらすインタプリタ型言語の制限

6.7　演習