Harrorth--を考える
始めに
forthという言語があります．逆ポーランド記法（RPN）を使うちょっと見た目が変わった言語ですが，こっそりいろいろな形であちこちに使われています．例えば（商業的な）印刷には欠かせないAdobeのPostScriptの原型になってたりJavaのVMが似たような構造になってるとのこと．
RPNは，普通なら
(1+2)*3
のように書く数式を
1 2 + 3 *
と書く記法です．「1に2を足して，それに3をかける」というように計算の順番をそのまま並べただけの記法ですが，非常にシンプル，たとえば計算の順番を変える「括弧」が不要，なのでいろいろ便利です．PostScriptなんかの場合，計算資源がそんなにないプリンタで動かすのが目的なのでシンプルなのが一番です．
RPNを考えるときには，データを扱う構造としてスタックを考えます．
1 2 + 3 *
の場合，
- 1をスタックにつむ
- 2をスタックにつむ
- スタックにつまれた1と2を取り出して，
- 足し算をして
- 結果の3をスタックにつむ
- 3をスタックにつむ
- スタックにつまれた3と3を取り出して
- 掛け算をして
- その結果の9をスタックにつむ
という動作で，計算結果の9が得られます．
この記法を使った言語（のはしり）がforthで，いろいろな実装があるようですが，Haskellで実装したHarrorthというのがあります．Pugsの中の人nothingmuchさんがチュートリアル的に作ったもののようですが，これを真似してみようかと思います．
という先人もいらっしゃるようです．
とりあえず，先に進みます．
Pugsの中の人のドキュメント類を読み進めていきます．ただ，実際のソースはこのドキュメントの最後の方での大幅な更新が施されたものなので，ドキュメントとソースが一致していません．ここでは先人と同じく，初期のHarrorthのコードを（内容を省いたりして）再現すべく進めていくことにします．
もともとのHarrorthから乖離していくことを考えて，「Harrorth--」と名前をつけてしまいます．
AST（Astract Syntax Tree，抽象構文木）
Harrorth--のコード，たとえば極めて単純に
1 2 + 3 *
のようなものを与えたときに，それをパースして処理しやすいようにASTを構築します．といっても，Harrorth--のASTは，コードに逆ポーランド記法を使うこともあって，それほど複雑にはなりません．必要なものはとりあえず
でしょうか．コードを文字列として与えて，そのコードをパースした結果のASTは，これらの要素の集まりなので，リストで表現することにします．さらに大胆に簡単のため，リテラルは「整数のみ」，演算子は「文字列のみ」ということにしてしまいます．例えば，今までの「1 2 + 3 *」は
1 2 add 3 mul
と書くことにしてしまいます．これをHaskellのコードにすると
{-- Harrorth-- parser.hs (1) --} type AST = [Exp] data Exp = Push Literal | Invoke Word deriving Show type Literal = Integer type Word = String
です（invokeは「起動する」「呼び出す」という意味）．つまり，「1 2 add 3 mul」を処理すると
[Push 1, Push 2, Invoke "add", Push 3, Invoke "mul"]
というAST（Haskellのリスト）ができて欲しいのです．
ここで本当なら，「スタック」も作っておくべきかもしれませんが，今はパーサだけに注目することにします．
パーサを考える
Haskellでパーサといえば，まずはParsecです．ということでParsecを使ってみます．使ってみたいからです．そもそも，今考えているようなRPNでコードが書かれるのならば，Parsecを使うことはありません．けど，使いたいし，Harrorthの人も使ってるので使います．
import Text.ParserCombinators.Parsec type AST = [Exp] data Exp = Push Literal | Invoke Word deriving Show type Literal = Integer type Word = String
さて，パーサです．文字列をASTに変換するパーサを作りたいので
harrorthP::Parser AST harrorthP = do ast <- harroth eof return ast
です．harroth自体もやはりParser AST型のパーサ，eofは終わりを検出するパーサ，astはharrorthによる結果（AST型）で，この結果をreturnで返します．
harroth::Parser AST自体は，空白区切りのIntegerとStringで構成されるコードを受け入れて，それぞれInteger（Literal）かString（Word）かで処理します．
harrorth::Parser AST harrorth = sepEndBy harrorthExp (skipMany1 space)
spaceは空白をパースするパーサ，skipMany1は次にくるパーサを最低でも1回パースして，何も返さない（スキップする）パーサなので，(skipMany1 space)は一個以上の空白を読み飛ばすパーサになります．sepEndBy
つまり，本質は「1個以上の空白で区切られた」「harrorthExp::Parser Exp」の列をパースすることになります．そして，HarrorthExp::Parser Expは「Literal」か「Word」です．ASTは[Exp]であることを注意しておきます．
harrorthExp::Parser Exp harrorthExp = literal <|> word literal::Parser Exp literal = (many1 digit) >>= \x ->return (Push (read x)) word::Parser Exp word = (many1 letter) >>= \x ->return (Invoke x)
今までのものをすべてまとめておきますが，ここで少しだけ細工を加えておきます．このままだとパースの対象文字列の先頭に空白があるとエラーがでます．そこで先頭の0個以上の空白を読み飛ばすようにしておきます．
{-- Harroth-- ./Harroth/harrorth--.hs --} import Text.ParserCombinators.Parsec -- AST type AST = [Exp] data Exp = Push Literal | Invoke Word deriving Show type Literal = Integer type Word = String -- Parser harrorthP::Parser AST harrorthP = do skipMany space ast <- harrorth eof return ast harrorth::Parser AST harrorth = sepEndBy1 harrorthExp (skipMany1 space) harrorthExp::Parser Exp harrorthExp = literal <|> word literal::Parser Exp literal = (many1 digit) >>= \x ->return (Push (read x)) word::Parser Exp word = (many1 letter) >>= \x ->return (Invoke x)
これをghciで読み込んで
ghci GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> :l Harrorth/harrorth--.hs [1 of 1] Compiling Main ( ./harrorth/harrorth--.hs, interpreted ) Ok, modules loaded: Main. *Main> parseTest harrorthP " 1 2 add 3 mul " Loading package parsec-2.1.0.1 ... linking ... done. [Push 1,Push 2,Invoke "add",Push 3,Invoke "mul"] *Main> parseTest harrorthP "1 2 add 3 mul" [Push 1,Push 2,Invoke "add",Push 3,Invoke "mul"] *Main>
うまくいきました．ぶっちゃけた話，これじゃせいぜい「RPN電卓」の一部ですが，その分していることはシンプルで勉強用にはちょうどいいと思います．
評価器（Evaluater）
ASTを構築することができました．しかしこれを実際に処理できないと意味がありません．まずはスタックを準備します．ここに処理結果をおさめていきます．
data Interp = Interp{ stack::[Literal] } deriving Show
これをHarrorth--のインタプリータの型とします．Interp型は，データコンストラクタとしてInterpを，そのフィールドとして[Literal]型のstackをもちます．これによって，
stack:: Interp -> [Literal] stack Interp {stack=xs} = xs
が定義され，また，例えば，
*Main> Interp {stack=[]}} Interp {stack = []} *Main> Interp {stack=[]} {stack = [1,2]} Interp {stack = [1,2]}
とできるので，スタックの更新も可能です（正確には更新ではなく，再作成ですが）．
さて，動作を考えましょう．ASTが与えられると，スタックに「その実行結果」を保存してくれればいいのですが，Haskellには安直に「状態保存」に使えるようなグローバル変数とか代入はありません．そこでStateモナドでも使おうかとか思ったわけですが，Harrorthのnothingmuchさんのドキュメントにしたがって「変数で持ちまわす」ことにします．ASTを実行する関数interpを
interp:: Interp -> AST -> Interp
とすることにしましょう．いま，Harrorth--のASTの要素としては，Push LiteralとInvoke Wordしかないので，それぞれの挙動を考えると，
Interp {stack=[x,y,...]} -> Push 3
-> Interp {stack = [3,x,y,...]}
Interp {stack=[x,y,...]} -> Invoke "something"
-> Interp {stack = [x,y,...]が何かされた結果}
とならなければいけません．このような動作をASTの各要素に順番に施していく必要があります．
interp:: Interp -> AST -> Interp interp i x:xs = let i'= procExp i x in interp i' xs
という流れが妥当に思われます．「procExp」は，インタプリータiをもとに，ASTの先頭要素（型はExp）を処理して新しいインタプリータを作ります．そしてそれを次の処理に回します．このときASTの最初の要素は処理されているので，残りのxsだけが対象になることに注意です．このような再帰処理を行うので，再帰の停止条件が必要です．動作が終了するのはASTが空っぽになったときで，空っぽのASTに対しては，インタプリータは変化しません．したがって，まとめると
interp:: Interp -> AST -> Interp interp i (x:xs) = let i'= procExp i x in interp i' xs interp i [] = i
です．次にprocExpを考えます．型は明らかに
procExp:: Interp -> Exp -> Interp
です．まずは簡単のため，ExpのうちPush Literalのみを考えると，新しいリテラルをスタックの上に積むのだから
procExp:: Interp -> Exp -> Interp procExp Interp {stack=xs} (Push lit) = Interp {stack=lit:xs}
です．ここまでやってやっとすこし動くはずなので，動かしてみます．
*Main> interp Interp {stack=[]} [Push 1, Push 2]
Interp {stack = [2,1]}
*Main>
おお，スタックに積まれてます．
残りのInvole Wordの方を考えます．スタックといえば，まずはpushとpopです．pushはただ単にリテラルをおけばいいのですでにできてますが，popはまだです．既存のスタック「から」何かをする処理の中で一番簡単そうなので，pop，ASTの形ではInvoke "pop"を考えます．
procExp:: Interp -> Exp -> Interp procExp Interp {stack=x:xs} (Invoke "pop") = Interp {stack=xs}
動かしてみます．
*Main> interp Interp {stack=[3]} [Push 4, Invoke "pop", Push 10]
Interp {stack = [10,3]}
期待通りうごきました．
まとめ
さて・・・Harrorthを真似て機能制限して簡単な部分だけ，簡単に実装してきましたが，Harrorth，そしてforthの仕様はちょっと私の直観とは反する部分があります．やはりここはPostScriptにあわせていきたいです．PostScriptならghostscriptという「動作確認の先生」もいます．
ということで，Harrorth--はここらで名前を変えて紛らわしくないようにします．phorthと名乗ることにします．PostScript/Haskell/Harrorth(forth)です（笑）．
最語にHarroth--をコンパイルできる形に整理しておきます．
{--
Harroth-- ./Harroth/harrorth--.hs
--}
import Text.ParserCombinators.Parsec
-- AST
type AST = [Exp]
data Exp = Push Literal | Invoke Word deriving Show
type Literal = Integer
type Word = String
-- Parser
harrorthP::Parser AST
harrorthP = do skipMany space
ast <- harrorth
eof
return ast
harrorth::Parser AST
harrorth = sepEndBy1 harrorthExp (skipMany1 space)
harrorthExp::Parser Exp
harrorthExp = literal <|> word
literal::Parser Exp
literal = (many1 digit) >>= \x ->return (Push (read x))
word::Parser Exp
word = many1 letter >>= \x ->return (Invoke x)
-- Evaluater
data Interp = Interp{ stack::[Literal] } deriving Show -- interpreter
interp:: Interp -> AST -> Interp
interp i (x:xs) = let i'= procExp i x
in interp i' xs
interp i [] = i
procExp:: Interp -> Exp -> Interp
procExp (Interp {stack=xs}) (Push lit) = Interp {stack=lit:xs}
procExp (Interp {stack=x:xs}) (Invoke "pop") = Interp {stack=xs}
main = do src <- getLine
case (parse harrorthP "" src) of
Left err -> do putStr "parse Error ar"
print err
Right x -> printInterp x
printInterp:: AST -> IO ()
printInterp ast = print (interp Interp{stack=[]} ast) これを
ghc --make -o harrorth-- harrorth--.hs
とすれば，harrorth--ができあがり，
harrorth-- 1 2 3 pop 100 Interp {stack = [100,2,1]}
というようにとりあえず実行できます．
まったくの機能不足，エラー処理もない，試作にしてもまったくの役立たずですが，とりあえずは動きます．Harrothのドキュメントはこのあとモナディックな世界に突入していきますが，その内容も考慮して，もっと「グラフィックのないPostScript」という方向でphorthを考えていきます．
