FizzBuzzを書くためだけに作った言語、FizzBuzzLang
FizzBuzzを書くためだけのインタープリタ言語、FizzBuzzLangを作ってみました。以下のプログラムを実行できます。それ以外のことは何もできません。
for n from 1 to 100
puts n % 3 == 0 ? (n % 5 == 0 ? 'FizzBuzz' : 'Fizz') : (n % 5 == 0 ? 'Buzz' : n)
そもそもなぜ実用価値ゼロの言語を作ろうとしたのかというと，どれだけ少ない労力で現実に動く言語を作ることができるのかを実験してみたかったから。FizzBuzzを書くのに必要なレベルなら、意外と簡単にできるのではと。（さすがに1時間では無理そうだが…）
使用言語はC++。できるだけ楽をするため、字句解析・構文解析器は拙作のPEGパーサージェネレータ「cpp-peglib」を使って作成。インタープリタは手書き。
完成までのステップは以下の通り。
- 頭の中のオレオレ言語でFizzBuzzを書く
- 文法をPEG (Parsing Expression Grammar) に落とす
- AST (抽象構文木) を出力するパーサーの作成
- 値
- 環境
- 評価器
3.までは比較的楽に行けると予想。続くインタープリタ関連のステップが山場。
1. 頭の中のオレオレ言語でFizzBuzzを書く
目標は、1から100までのFizzBuzz結果を標準出力に書き出すこと。色々な言語で書かれたFuzzBuzzプログラムを眺めながら、最終的に先程のプログラムになった。
for n from 1 to 100
puts n % 3 == 0 ? (n % 5 == 0 ? 'FizzBuzz' : 'Fizz') : (n % 5 == 0 ? 'Buzz' : n)
このFizzBuzzLangプログラムに含まれる言語要素は、
- 数値タイプ:
0 - 文字列タイプ:
'FizzBuzz' - 比較演算子:
== - 3項演算子:
?,: - 余剰演算子:
% - 括弧演算子:
(,) - 繰り返しと実引数:
for,n,from,to - 値の出力関数:
puts
最初の2つはこの言語のプリミティブ型。その後は各種演算子、最後に繰り返しと出力関数。足し算すらできない貧弱な言語ではあるものの、とりあえずFizzBuzzは書けるのでOK。
2. 文法をPEGに落とす
「PEG Playground」上で試行錯誤しながら、FizzBuzzLangのPEG文法を作成する。「Grammar」ペインにはPEGを、「Code」ペインにはその言語のソースコードを記述する。
基本的には字句レベルの文法から始め、下位の構文に進み、徐々に上位の構文を作成していく。このボトムアップな方法で文法を構築すると、その時点までの文法に間違いがないことを確認しつつ確信を持って進めることができる。
以下のように「Grammar」ペインと「Code」ペインの上方にある双方のインジケーターが「Valid」になり、さらに右下の「Optimited AST」ペインの内容が正しければ完成。
完成したPEG文法はこちら。
# Syntax Rules
START <- _ EXPRESSION _
EXPRESSION <- TERNARY
TERNARY <- CONDITION (_ '?' _ EXPRESSION _ ':' _ EXPRESSION)?
CONDITION <- MULTIPLICATIVE (_ ConditionOperator _ MULTIPLICATIVE)?
MULTIPLICATIVE <- CALL (_ MultiplicativeOperator _ CALL)*
CALL <- PRIMARY (__ EXPRESSION)?
PRIMARY <- FOR / Identifier / '(' _ EXPRESSION _ ')' / String / Number
FOR <- 'for' __ Identifier __ 'from' __ Number __ 'to' __ Number __ EXPRESSION
# Token Rules
ConditionOperator <- '=='
MultiplicativeOperator <- '%'
Identifier <- !Keyword [a-zA-Z][a-zA-Z0-9_]*
String <- "'" < (!['] .)* > "'"
Number <- [0-9]+
~_ <- Whitespace*
~__ <- Whitespace+
Whitespace <- [ \t\r\n]
Keyword <- 'for' / 'from' / 'to'
例のFizzBuzzプログラムのASTは以下の通り。
+ START/0[FOR]
- Identifier (n)
- Number (1)
- Number (100)
+ EXPRESSION/0[CALL]
- PRIMARY/1[Identifier] (puts)
+ EXPRESSION/0[TERNARY]
+ CONDITION
+ MULTIPLICATIVE
- CALL/0[Identifier] (n)
- MultiplicativeOperator (%)
- CALL/0[Number] (3)
- ConditionOperator (==)
- MULTIPLICATIVE/0[Number] (0)
+ EXPRESSION/0[TERNARY]
+ CONDITION
+ MULTIPLICATIVE
- CALL/0[Identifier] (n)
- MultiplicativeOperator (%)
- CALL/0[Number] (5)
- ConditionOperator (==)
- MULTIPLICATIVE/0[Number] (0)
- EXPRESSION/0[String] (FizzBuzz)
- EXPRESSION/0[String] (Fizz)
+ EXPRESSION/0[TERNARY]
+ CONDITION
+ MULTIPLICATIVE
- CALL/0[Identifier] (n)
- MultiplicativeOperator (%)
- CALL/0[Number] (5)
- ConditionOperator (==)
- MULTIPLICATIVE/0[Number] (0)
- EXPRESSION/0[String] (Buzz)
- EXPRESSION/0[Identifier] (n)
3. ASTを出力するパーサーの作成
peglib.hをここからダウンロードし、上記のPEG文法を使ってパーサーを作成する。とりあえず入力ファイルを読み込み、パースしてASTを作成し、その内容を標準出力にダンプできるようにする。
パーサー関数parseのコードはこんな感じ。
std::shared_ptr<peg::Ast> parse(const std::vector<char>& source, std::ostream& out) {
peg::parser parser(R"(
# Syntax Rules
START <- _ EXPRESSION _
EXPRESSION <- TERNARY
TERNARY <- CONDITION (_ '?' _ EXPRESSION _ ':' _ EXPRESSION)?
CONDITION <- MULTIPLICATIVE (_ ConditionOperator _ MULTIPLICATIVE)?
MULTIPLICATIVE <- CALL (_ MultiplicativeOperator _ CALL)*
CALL <- PRIMARY (__ EXPRESSION)?
PRIMARY <- FOR / Identifier / '(' _ EXPRESSION _ ')' / String / Number
FOR <- 'for' __ Identifier __ 'from' __ Number __ 'to' __ Number __ EXPRESSION
# Token Rules
ConditionOperator <- '=='
MultiplicativeOperator <- '%'
Identifier <- !Keyword [a-zA-Z][a-zA-Z0-9_]*
String <- "'" < (!['] .)* > "'"
Number <- [0-9]+
~_ <- Whitespace*
~__ <- Whitespace+
Whitespace <- [ \t\r\n]
Keyword <- 'for' / 'from' / 'to'
)");
// AST生成機能をON
parser.enable_ast();
// エラー出力ハンドラの設定
parser.log = [&](size_t ln, size_t col, const std::string& msg) {
out << ln << ":" << col << ": " << msg << std::endl;
};
std::shared_ptr<peg::Ast> ast;
if (parser.parse_n(source.data(), source.size(), ast)) {
// AST内の冗長なノードを取り除く
return peg::AstOptimizer(true).optimize(ast);
}
return nullptr;
}
パーサーを呼び出すコード。
// ソースコードのパースとASTの生成
auto ast = parse(source, cerr);
if (!ast) {
return 3;
}
// ASTの出力
cout << peg::ast_to_s(ast) << endl;
ソースコード全体を見る
#include "peglib.h"
#include <fstream>
using namespace std;
bool read_file(const char* path, vector<char>& buf) {
ifstream ifs(path, ios::in);
if (ifs.fail()) {
return false;
}
buf.resize(static_cast<unsigned int>(ifs.seekg(0, ios::end).tellg()));
ifs.seekg(0, ios::beg).read(&buf[0], static_cast<streamsize>(buf.size()));
return true;
}
std::shared_ptr<peg::Ast> parse(const std::vector<char>& source, std::ostream& out) {
peg::parser parser(R"(
# Syntax Rules
START <- _ EXPRESSION _
EXPRESSION <- TERNARY
TERNARY <- CONDITION (_ '?' _ EXPRESSION _ ':' _ EXPRESSION)?
CONDITION <- MULTIPLICATIVE (_ ConditionOperator _ MULTIPLICATIVE)?
MULTIPLICATIVE <- CALL (_ MultiplicativeOperator _ CALL)*
CALL <- PRIMARY (__ EXPRESSION)?
PRIMARY <- FOR / Identifier / '(' _ EXPRESSION _ ')' / String / Number
FOR <- 'for' __ Identifier __ 'from' __ Number __ 'to' __ Number __ EXPRESSION
# Token Rules
ConditionOperator <- '=='
MultiplicativeOperator <- '%'
Identifier <- !Keyword [a-zA-Z][a-zA-Z0-9_]*
String <- "'" < (!['] .)* > "'"
Number <- [0-9]+
~_ <- Whitespace*
~__ <- Whitespace+
Whitespace <- [ \t\r\n]
Keyword <- 'for' / 'from' / 'to'
)");
// AST生成機能をON
parser.enable_ast();
// エラー出力ハンドラの設定
parser.log = [&](size_t ln, size_t col, const std::string& msg) {
out << ln << ":" << col << ": " << msg << std::endl;
};
std::shared_ptr<peg::Ast> ast;
if (parser.parse_n(source.data(), source.size(), ast)) {
// AST内の冗長なノードを取り除く
return peg::AstOptimizer(true).optimize(ast);
}
return nullptr;
}
int main(int argc, const char** argv) {
if (argc < 2) {
cerr << "usage: fzbz [source file path]" << endl;
return 1;
}
auto path = argv[1];
vector<char> source;
if (!read_file(path, source)) {
cerr << "can't open the source file." << endl;
return 2;
}
// ソースコードのパースとASTの生成
auto ast = parse(source, cerr);
if (!ast) {
return 3;
}
// ASTの出力
cout << peg::ast_to_s(ast) << endl;
return 0;
}
これまでのコードをfzbz.ccに保存し、コンパイル。
g++ -std=c++11 -o fzbz fzbz.cc
先ほどのFizzBuzzプログラムをfizzbuzz.fzbzに保存し、実行。
> ./fzbz fizzbuzz.fzbz
+ START/0[FOR]
- Identifier (n)
- Number (1)
...
無事にASTが構築されたことを確認！
4. 値
ここからインタープリタの作成に入る。今回の山場。
再度FuzzBuzzプログラムを注意深く眺め、その中に存在する値の型について調べてみる。
for n from 1 to 100
puts n % 3 == 0 ? (n % 5 == 0 ? 'FizzBuzz' : 'Fizz') : (n % 5 == 0 ? 'Buzz' : n)
明らかに分かるのは1, 100, 3, 5, 0などの数値型 (Number), 'FizzBuzz', 'Fizz', 'Buzz'の文字列型 (String)。実はそれ以外にも、コード内にはさらに3つの型が潜んでいる。n % 3 == 0の比較演算子の戻り値である論理型 (Bool), putsの関数型 (Function), puts n % 3...の関数コールの戻り値であるNil型。
それらの5つの型の値を表せるValue型を定義してみる。
typedef std::function<Value(const Value&)> Function;
struct Value {
enum class Type { Nil, Bool, Long, String, Function };
Type type;
peg::any v;
// Constructor
Value() : type(Type::Nil) {}
explicit Value(bool b) : type(Type::Bool), v(b) {}
explicit Value(long l) : type(Type::Long), v(l) {}
explicit Value(const std::string& s) : type(Type::String), v(s) {}
explicit Value(const Function& f) : type(Type::Function), v(f) {}
...
}
コンストラクタを通じてType typeに型をセットし、peg::any v に値を格納する。（C++17からはpeg::anyの代わりに標準の std::anyが使えます。）
FizzBuzzLang の型と、C++のNative型との対応は以下の通り。
| FizzBuzzLang Type | Native Type |
|---|---|
| Nil | void |
| Bool | bool |
| Long | long |
| String | std::string |
| Function | std::function<Value (const Value&)> |
続いて値を取り出す、もしくは別の型にキャストするメソッド群を追加。間違った型にキャストしようとする場合、例外を送出する。
// Cast value
bool to_bool() const {
switch (type) {
case Type::Bool:
return v.get<bool>();
case Type::Long:
return v.get<long>() != 0;
default:
throw std::runtime_error("type error.");
}
}
long to_long() const {
switch (type) {
case Type::Long:
return v.get<long>();
default:
throw std::runtime_error("type error.");
}
}
std::string to_string() const {
switch (type) {
case Type::String:
return v.get<std::string>();
default:
throw std::runtime_error("type error.");
}
}
Function to_function() const {
switch (type) {
case Type::Function:
return v.get<Function>();
default:
throw std::runtime_error("type error.");
}
}
さらに比較演算用メソッドを追加。右値の型を左値の型に合わせて比較する。
// Comparison
bool operator==(const Value& rhs) const {
switch (type) {
case Type::Nil:
return rhs.type == Type::Nil;
case Type::Bool:
return to_bool() == rhs.to_bool();
case Type::Long:
return to_long() == rhs.to_long();
case Type::String:
return to_string() == rhs.to_string();
default:
throw std::logic_error("invalid internal condition.");
}
}
最後に、値を文字表現に変換するメソッドを追加して完成。
// String representation
std::string str() const {
switch (type) {
case Type::Nil:
return "nil";
case Type::Bool:
return to_bool() ? "true" : "false";
case Type::Long:
return std::to_string(to_long());
case Type::String:
return to_string();
default:
throw std::logic_error("invalid internal condition.");
}
}
5. 環境
環境とは、簡単に言えば値を保持する辞書 (std::map<std::string, Value> values) 。
struct Environment {
std::shared_ptr<Environment> outer;
std::map<std::string, Value> values;
Environment(std::shared_ptr<Environment> outer = nullptr): outer(outer) {}
const Value& get_value(const std::string& s) const {
if (values.find(s) != values.end()) {
return values.at(s);
} else if (outer) {
return outer->get_value(s);
}
throw std::runtime_error("undefined variable '" + s + "'...");
}
void set_value(const std::string& s, const Value& val) { values[s] = val; }
};
環境は，自分の外側の環境を指すstd::shared_ptr<Environment> outerを設定することができる。（ブロックスコープを持つ言語ではブロックごとに環境が生成され、親の環境と結合される。それでブロックのネストが深くなればなるほど、この環境連鎖も長くなっていく。）
get_valueはまず現在の環境から値を探し，もしなければouterの外部環境から探す。そこにもなければ，outerのouterに遡ってさらに探していく。
6. 評価器
今回作成するインタープリタは「構文木駆動型」。評価器はASTのルートノードから処理を開始し、再帰的に子ノードを評価していく。
peglib.hで定義されているASTノードの主要なメンバー変数は以下の3つ。（簡略化しています。）
struct Ast {
const unsigned int tag; // ASTノードのタイプ
const std::string token; // ノードのトークン文字列
std::vector<std::shared_ptr<Ast> nodes; // 子ノードのリスト
};
評価器への入力はASTノードと環境。ノードはtagで表されるノードタイプに従って適切に処理される。
Value eval(const peg::Ast& ast, std::shared_ptr<Environment> env) {
using namespace peg::udl;
switch (ast.tag) {
// Rules
case "TERNARY"_:
return eval_ternary(ast, env);
case "CONDITION"_:
return eval_condition(ast, env);
case "MULTIPLICATIVE"_:
return eval_multiplicative(ast, env);
case "CALL"_:
return eval_call(ast, env);
case "FOR"_:
return eval_for(ast, env);
// Tokens
case "Identifier"_:
return Value(env->get_value(ast.token));
case "String"_:
return Value(ast.token);
case "Number"_:
return Value(stol(ast.token));
}
return Value();
}
ノードタイプがString場合は、token文字列をそのまま値として返す。Numberの場合、token文字列を数値に変換した値を返す。Identifierの場合、token文字列をキーとして環境辞書から値を取得し、その値を返す。
構文タイプのノードの場合、それぞれの構文に特化した評価器を呼び出す。例えばfor構文の場合はeval_forが呼び出される。
Value eval_for(const peg::Ast& ast, std::shared_ptr<Environment> env) {
auto ident = ast.nodes[0]->token;
auto from = eval(*ast.nodes[1], env).to_long();
auto to = eval(*ast.nodes[2], env).to_long();
auto& expr = *ast.nodes[3];
for (auto i = from; i <= to; i++) {
auto call_env = std::make_shared<Environment>();
call_env->set_value(ident, Value(i));
call_env->append_outer(env);
eval(expr, call_env);
}
return Value();
}
eval_forに渡されるASTノードには、構文ルールから必ず4つの子ノードが含まれることが保証されている。
一番目の子ノードは、現在のインデックスが入る変数名。2番めは開始値。3番めは終了値。最後は評価されるべき式。
開始値と終了値を使って式の評価を繰り返す。イテレーション毎に新たな環境を作成し、その時点のインデックス値を与えられた変数名に設定し、さらに現在の環境を外側の環境として設定する。この環境を用いて式ノードを評価する。for構文自体はNill値を返す。
他の構文ルールに対応した評価器も同様に作成する。
Value eval_ternary(const peg::Ast& ast, std::shared_ptr<Environment> env) {
auto cond = eval(*ast.nodes[0], env).to_bool();
auto val1 = eval(*ast.nodes[1], env);
auto val2 = eval(*ast.nodes[2], env);
return cond ? val1 : val2;
}
Value eval_condition(const peg::Ast& ast, std::shared_ptr<Environment> env) {
auto lhs = eval(*ast.nodes[0], env);
auto rhs = eval(*ast.nodes[2], env);
auto ret = lhs == rhs;
return Value(ret);
}
Value eval_multiplicative(const peg::Ast& ast,
std::shared_ptr<Environment> env) {
auto l = eval(*ast.nodes[0], env).to_long();
for (auto i = 1; i < ast.nodes.size(); i += 2) {
auto r = eval(*ast.nodes[i + 1], env).to_long();
l = l % r;
}
return Value(l);
}
Value eval_call(const peg::Ast& ast, std::shared_ptr<Environment> env) {
auto fn = env->get_value(ast.nodes[0]->token).to_function();
auto val = eval(*ast.nodes[1], env);
return fn(val);
}
いよいよ大詰。ビルトイン関数putsを含む初期環境を準備し，ASTのルートノードに対して評価器を呼び出すinterpret関数を作成。
Function putsFn = [](const Value& val) -> Value {
std::cout << val.str() << std::endl;
return Value();
};
Value interpret(const peg::Ast& ast) {
auto env = std::make_shared<Environment>();
env->set_value("puts", Value(putsFn));
return eval(ast, env);
}
最後にmain内でこの関数を呼び出す。
auto ast = parse(source, cerr);
if (!ast) {
return 3;
}
try {
interpret(*ast);
} catch (const exception& e) {
cerr << e.what() << endl;
return 4;
}
最終的なソースコードはこちら。
コンパイルして実行。FizzBuzzが正しく出力された！
> ./fzbz fizzbuzz.fzbz
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...
300行に満たないコード量でFizzBuzzLangインタープリタを完成。こんな程度の言語でも、 実際に動いているのを見ると感動です！