この記事は？
- Haskell の基本機能だけでプログラミング言語作成したのでご紹介します
- 既存のライブラリやパーサジェネレータ等を使用せずにプログラミング言語を作成
- 元ネタは「Go言語でつくるインタプリタ」という書籍
- https://www.oreilly.co.jp/books/9784873118222/
- この書籍で作成するプログラミング言語の名は Monkey
- Haskell 等の関数型言語でいちからプログラミング言語を作ってみたいという方の一助となれば・・
作成した理由
- 元ネタである「Go言語でつくるインタプリタ」に感銘を受けました
- 非常に簡潔に書かれた書籍であり僕の様な CS の基礎知識のない人間でもある程度理解できた
- Go で書かれているというのも「簡潔さ」と「理解のしやすさ」の一因ではないかと思います
- Haskell を好むため同じものを Haskell でも作りたくなりました
作成した Haskell 製インタプリタ
- 名前は Haskey です
- 前述の Go 言語製インタプリタ Monkey をもじったネーミングです
Haskey の機能紹介
「Go言語でつくるインタプリタ」第4章までのハッシュを除いた機能全てを実装しました。
詳細は GitHub リポジトリを参照願います
以下 Haskey を REPL として実行した際の結果です
prompt$ haskey
Hello! This is the Haskey programming language!
Feel free to type in commands
Usage: haskey --help
>> let a = 100;
>> let b = 200;
>> a + b;
300
>> if(a > 1000){ true; }else{ false; };
False
>> let add = fn(x, y) { x + y };
>> let sub = fn(x, y) { x - y };
>> let applyFunc = fn(a, b, func) { func(a, b) };
>> applyFunc(2, 2, add);
4
>> applyFunc(10, 2, sub);
8
>> "Hello" + " " + "World";
Hello World
Haskey における関数は値(ファーストクラス)として扱えます
>> fn(a, b){ a + " " + b }("love", "Haskell");
love Haskell
>> let applyFunc = fn(a, b, func) { return func(a, b); };
>> applyFunc(2, 2, add);
4
>> applyFunc(10, 2, sub);
8
クロージャもサポートしています
>> let mulXFunc = fn(x){ fn(y){ y * x; } };
>> let doubleFunc = mulXFunc(2);
>> doubleFunc(100);
200
>> doubleFunc(200);
400
>> let threeTime = mulXFunc(3);
>> threeTime(100);
300
>> threeTime(200);
600
作成時の取り決め
- 元ネタである Go 製インタプリタ Monkey とほぼ同程度の機能を実装する
- Haskell における基本機能のみを使用
- 例外で使用したパッケージ
- text
- 文字列に使用
- containers
- Map で使用
- optparse-applicative
- コマンドライン引数の処理に使用
- HUnit
- ユニットテストで使用
- raw-strings-qq
- 主にテスト時の生文字列作成に使用
- text
- 例外で使用したパッケージ
例外で使用したパッケージは文字列処理のパフォーマンス向上やユニットテストを簡潔に扱うためであり、インタプリタ作成における主要な箇所には基本的に使用していません。
Haskey 作成の概要
作成の大まかな手順は以下の通りです。これらをテストファーストで実装していきました。
- 字句解析実装
- 構文解析実装
- 評価器実装
- 配列、ビルトイン関数などのその他機能を実装
ひとつひとつをもう少し掘り下げて説明します。
字句解析
- 対象モジュール
- src/Haskey/Lexer.hs
入力されたソースコード let hoge = 123; などを [LET, IDENTIFIRE "hoge", ASSIGN, INT 123, SEMICOLON]のように
トークン化していく工程です。特に Haskell 的な型システムによる抽象化などはなくひたすら泥臭く実装しました。Go との違いはほとんどなかった気がします。
Go 版は構文解析の際に必要な数のトークンのみ都度作成するのに対して、Haskell 版は入力を一気に先頭からトークンにして
それをまるっと次の処理(構文解析器)に渡す設計です。そのくらいしか Go との違いはなかった気がします。
以下の nextToken 関数内のガード記法で文字を引っ掛けてトークンを作成していきます。
-- | nextToken
--
nextToken :: T.Text -> (Tok.Token, T.Text)
nextToken s | T.null s = (eof, "")
| C.isSpace ch = nextToken remain
| -- skip white space
T.isPrefixOf "==" s = readFix Tok.Eq "==" s
| T.isPrefixOf "!=" s = readFix Tok.NotEq "!=" s
| ch == '=' = (newToken Tok.Assign ch, remain)
| ch == '+' = (newToken Tok.Plus ch, remain)
| ch == '-' = (newToken Tok.Minus ch, remain)
| ch == '!' = (newToken Tok.Bang ch, remain)
| ch == '*' = (newToken Tok.Asterisk ch, remain)
| ch == '/' = (newToken Tok.Slash ch, remain)
| ch == '<' = (newToken Tok.Lt ch, remain)
| ch == '>' = (newToken Tok.Gt ch, remain)
| ch == ';' = (newToken Tok.Semicolon ch, remain)
| ch == '(' = (newToken Tok.Lparen ch, remain)
| ch == ')' = (newToken Tok.Rparen ch, remain)
| ch == ',' = (newToken Tok.Comma ch, remain)
| ch == '{' = (newToken Tok.Lbrace ch, remain)
| ch == '}' = (newToken Tok.Rbrace ch, remain)
| ch == '[' = (newToken Tok.Lbracket ch, remain)
| ch == ']' = (newToken Tok.Rbracket ch, remain)
| ch == '"' = readString s
| isLetter ch = readIdentifire s
| C.isDigit ch = readNumber s
| otherwise = (newToken Tok.Illegal ch, remain)
where
ch = T.head s
remain = T.tail s
eof = Tok.Token { Tok.tokenType = Tok.Eof, Tok.literal = "" }
構文解析
- 対象モジュール
- src/Haskey/Parser.hs
前工程で作成したトークンから抽象構文木(AST)を作成する工程です。
AST を構成する要素としては文(Statement)があり文はまた式(Expression)などから構成されます。
Haskell での攻略方法ですが、既存のライブラリこそ使用していないものの結局自前でパーサコンビネータを作成して対応しました。
パーサコンビネータとは小さなパーサを組み合わせてより大きなパーサを組み立てる手法です。
色々考えたんですが Haskell に於いて「パースする」という作業はパーサコンビネータを使用するのが一番簡潔という自分なりの結論に達したわけです。
具体的には Parser 型を定義し、Monad 型クラスのインスタンスとしました。
Parser 型が処理したい内容は主に以下です。
- Token から抽象構文木を生成する
- Token 配列を入力に受け取る
- Token が構文エラーの場合はエラー処理をする
上記のうち 2, 3 は Haskell の文脈処理に落とし込みました。つまり Monad 型クラスのインスタンスである Parser 型がサポートするバインド関数(>>=)や fmap 関数などに
処理を任せてプログラマ(僕)はトークンから文や式を生成することだけに集中します。そのための下準備として Parser 型を Monad 型クラスのインスタンスとするための実装をしました。
-- Parser combinator
newtype Parser a = Parser { runParser :: [Tok.Token] -> Result a}
data Result a = Done a Remaining
| Fail Reason Remaining
deriving (Eq, Show)
type Remaining = [Tok.Token]
type Reason = String
instance Functor Parser where
-- fmap :: (a -> b) -> Parser a -> Parser b
fmap g p = Parser
(\input -> case runParser p input of
(Fail reason remaining) -> Fail reason remaining
(Done result remaining) -> Done (g result) remaining
)
instance Applicative Parser where
-- pure :: a -> Parser a
pure v = Parser (\input -> Done v input)
-- <*> :: Parser (a -> b) -> Parser a -> Parser b
pg <*> px = Parser
(\input -> case runParser pg input of
(Fail reason remaining) -> Fail reason remaining
(Done result remaining) -> runParser (fmap result px) remaining
)
instance Monad Parser where
-- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = Parser
(\input -> case runParser p input of
(Fail reason remaining) -> Fail reason remaining
(Done result remaining) -> runParser (f result) remaining
)
-- return :: a -> Parser a
-- return's default implementation is pure
-- fail :: String -> m a
fail s = Parser (\input -> Fail s input)
一応、自前でモナドを作成する場合は「モナド則」というのを満たす必要があるのですがこの Parser 型はモナド則を満たせているかの確認は全くしていません。
Monad 型クラスのインスタンスにするためには Applicative 型クラスのインスタンスにする必要があり、そのためには Functor 型クラスのインスタンス
にする必要がある・・・といった具合で Monad のインスタンスにするためにはそれなりに手間が必要でこのあたり少し面倒でした。
しかし、作りきってしまえばその後のパーサの作成は驚くほどすんなり進みました。
まず、パースするのについてまわる構文エラーの処理やトークンの入力処理など自分の手で書く必要がなくなりました。
それらは事前に実装した Monad 型クラスがサポートする関数たちがいい感じでやってくれます。この後はテストファーストを心がけながら、小さなパーサを組み合わせていくだけで自然と書きあがりました
いくつかパーサのソースをピックアップします
Let 文(識別子の定義)のパーサ
-- | parseLetStatement
--
parseLetStatement :: Parser Ast.Statement
parseLetStatement =
Ast.LetStatement
<$> next parseLet
<*> next parseIdentifire
<* next parseAssign
<*> parseExpression Lowest
<* goAheadIfNextSemicolon
if 式のパーサ
-- | parseIfExpression
--
parseIfExpression :: Parser Ast.Expression
parseIfExpression =
Ast.IfExpression
<$> next (expectCur Tok.If)
<*> parentheses (parseExpression Lowest)
<* nextToken
<*> parseBlockStatement
<*> (parseElseBlock <|> pure Ast.NilStatement)
Haskell の構文をあまり知らない方でも「ああ, Let 文のパーサは let のパースと Identifire のパースと・・(略)を組み合わせ作っているんだな」
というのがわかるかと思います。
Go との違いはやはりパーサコンビネータを中心に構文解析を構築したところでしょうか。
それによりパーサを組むという処理以外の煩わしい部分(エラー処理や Token の入力)などは自前で書く必要もなくなりました。
Go 版はソースコードのテキスト先頭から順にトークン化しエラー処理を交えながら構文解析をするという感じの設計です。
評価
- 対象モジュール
- src/Haskey/Evaluator.hs
前工程で構築した AST を実際に評価し結果を得ます。
5 + 5; という入力に対しては 10 という結果を、 let f = fn(){ return "hello"; }; f(); に対しては hello という結果を得ます。
こちらも色々考えた結果「評価する型」を作成し、Monad による文脈処理で攻略することにしました。
Evaluator 型を定義し、処理させたい内容として以下を実装しました。
- 環境を入力に評価した結果を返す
- 環境の状態を扱う
- 評価が失敗した際のエラー処理を行う
ここに現れる「環境」というのは定義した識別子とデータを紐付けた情報です。
評価時に出現した識別子の情報を環境に持たせて併せて評価します。
これもまた 2, 3 の処理は自動で処理するよう文脈に落としこみました。
以下の通り Evaluator 型を定義し Parser 型を定義した時と同じ要領で Monad 型クラスのインスタンスにします。
環境(Environment)と組になっている Buffer は後にご説明します。
newtype Evaluator a = Evaluator {runEvaluator :: (Obj.Environment, Buffer) -> Result a}
これもまた モナド則の確認はしていません。
次に評価関数(eval) を実装する Node 型クラスを定義し AST を構築する 文(Statement 型)や式(Expression 型)をそのインスタンスとすることにより再帰的に評価を行っていきます。
-- | class Node
--
class Node a where
eval :: a -> Evaluator Obj.Object
instance Node Ast.Program where
eval = evalProgram . Ast.statements
instance Node Ast.Statement where
eval (Ast.LetStatement _ name v) =
eval v >>= set (Ast.expValue name) >> return Obj.Void
eval (Ast.ReturnStatement _ e) = Obj.ReturnValue <$> eval e
eval (Ast.ExpressionStatement _ e) = eval e
eval (Ast.BlockStatement _ stmts) = evalBlockStatement stmts
eval (Ast.FailStatement _ s) = return $ Obj.Error s
eval _ = return $ Obj.Error "unknown node"
instance Node Ast.Expression where
eval (Ast.Identifire _ v) = evalIdentifire v
eval (Ast.IntegerLiteral _ v) = pure $ Obj.Integer v
eval (Ast.Boolean _ v) =
pure (if v then Obj.Boolean True else Obj.Boolean False)
eval (Ast.PrefixExpression _ op r) = eval r >>= evalPrefixExpression op
eval (Ast.FunctionLiteral _ params' body') =
Obj.Function params' body' <$> getEnv
eval (Ast.CallExpression _ func args) =
join $ liftM2 applyFunction (eval func) (mapM eval args)
eval (Ast.InfixExpression _ l op r) =
join $ liftM2 (evalInfixExpression op) (eval l) (eval r)
eval (Ast.IfExpression _ cond cons alte) =
eval cond
>>= (\c -> if isTruthy c then eval cons else evalIfExists alte)
eval (Ast.StringLiteral _ s ) = pure $ Obj.String s
eval (Ast.ArrayLiteral _ es) = Obj.Array <$> mapM eval es
eval (Ast.IndexExpression _ left index) =
join $ liftM2 evalIndexExpression (eval left) (eval index)
Go との違いはこちらも構文解析と同じよう評価コンビネータ？を定義しエラー処理や環境の引き回しを自動で行うよう設計しました。
ここまでで評価の実装も完了プログラム言語として最低限機能するようになりました。
その他の実装
その後以下の機能を実装しました。
- 配列の実装
- ビルトイン関数の実装
- 標準出力の実装
これらはもはやは消化試合と考えていたんですが標準出力関数puts()の実装でつまずきました。
恐らくちゃんとした Haskeller なら事前に気づくと思うようなことなのですが。
Go 版は puts() 評価時に Print するのですが Haskell は言語使用上副作用や IO の伴う処理は原則専用の型の関数でしか扱えません。
これまでの設計で評価関数は IO を処理できる関数として設計していなかったため、そのままでは標準出力できません。
色々悩みましたが解決策としては評価時に入力として環境と共に Buffer を引数にとり、標準出力が生じた際にはバッファリングし main 関数内で評価の合間にフラッシュする設計としてお茶を濁しました。
まとめ
Haskell の基本機能のみでプログラミング言語が書けるのかは不安でしたが、実際は「Go言語でつくるインタプリタ」の内容を写経 + αくらいの感覚で書けました。
もともとの Go 版の実装がシンプルであり、他の言語に簡単に置き換え可能な Go 自体のポテンシャルにも改めて気きづきました。
Haskell としての良さはやはりエラー処理、状態の引き回しなど本質的な部分以外を
型システムに落とし込むことにより、本来やりたい作業だけに集中できるというのが非常に気持ちよかったです。