フィボナッチ数列計算のためだけに作った言語、FibLang

「FizzBuzzを書くためだけに作った言語、FizzBuzzLang」の第2弾です。

フィボナッチ数列計算以外のことは何もできません。

今回も前回と同じ6つのステップで行います。

1. 頭の中のオレオレ言語で「フィボナッチ数列計算プログラム」を書く
2. 文法をPEG (Parsing Expression Grammar) に落とす
3. AST (抽象構文木) を出力するパーサーの作成
4. 値
5. 環境
6. 評価器

1. 頭の中のオレオレ言語でフィボナッチ数列計算プログラムを書く

def fib(x)
  x < 2 ? 1 : fib(x - 2) + fib(x - 1)

for n from 1 to 30
  puts(fib(n))

FizzBuzLangとほぼ同じですが、以下の違いがあります。

• 関数定義: def
• 新たな演算子: +, -, <
• 必要ない演算子: %, ==

2. 文法をPEGに落とす

今回も「PEG Playground」上で試行錯誤しながら、PEG文法を作成する。

完成したPEG文法はこちら。

# Syntax Rules
STATEMENTS              <- (DEFINITION / EXPRESSION)*
DEFINITION              <- 'def' Identifier '(' Identifier ')' EXPRESSION
EXPRESSION              <- TERNARY
TERNARY                 <- CONDITION ('?' EXPRESSION ':' EXPRESSION)?
CONDITION               <- INFIX (ConditionOperator INFIX)?
INFIX                   <- CALL (InfixOperator CALL)*
CALL                    <- PRIMARY ('(' EXPRESSION ')')?
PRIMARY                 <- FOR / Identifier / '(' EXPRESSION ')' / Number
FOR                     <- 'for' Identifier 'from' Number 'to' Number EXPRESSION

# Token Rules
ConditionOperator       <- '<'
InfixOperator           <- '+' / '-'
Identifier              <- !Keyword < [a-zA-Z][a-zA-Z0-9_]* >
Number                  <- < [0-9]+ >

Keyword                 <- 'def' / 'for' / 'from' / 'to'
%whitespace             <- [ \t\r\n]*

3. AST (抽象構文木) を出力するパーサーの作成

これは前回と全く同じ。

4. 値

今回はString型は必要ないので削除。Function型は、ユーザーが関数定義できるようになるために改良。

FizzBuzzLangの時のFunction

using Function = function<Value(const Value&)>;

FibLangのFunctionではstructにし、引数(param)と関数本体(eval)を保存できるようにした。

struct Function {
  string param;
  function<Value(shared_ptr<Environment> env)> eval;

  Function(const string& param,
           function<Value(shared_ptr<Environment> env)>&& eval)
      : param(param), eval(eval) {}
};

さらに==演算子を削除し、<演算子を追加する。

  // Comparison
  bool operator<(const Value& rhs) const {
    switch (type) {
      case Type::Nil:
        return false;
      case Type::Bool:
        return to_bool() < rhs.to_bool();
      case Type::Long:
        return to_long() < rhs.to_long();
      default:
        throw logic_error("invalid internal condition.");
    }
    // NOTREACHED
  }

5. 環境

Environmentは特に変更はなし。

6. 評価器

STATEMENTSとDEFINITIONルール用の評価器を追加。

Value eval(const Ast& ast, shared_ptr<Environment> env) {
  switch (ast.tag) {
    // Rules
    case "STATEMENTS"_:
      return eval_statements(ast, env);
    case "DEFINITION"_:
      return eval_definition(ast, env);
    case "TERNARY"_:

Value eval_statements(const Ast& ast, shared_ptr<Environment> env) {
  if (!ast.nodes.empty()) {
    auto it = ast.nodes.begin();
    while (it != ast.nodes.end() - 1) {
      eval(**it, env);
      ++it;
    }
    return eval(**it, env);
  }
  return Value();
}

Value eval_definition(const Ast& ast, shared_ptr<Environment> env) {
  const auto& name = ast.nodes[0]->token;
  const auto& param = ast.nodes[1]->token;
  auto body = ast.nodes[2];

  env->set_value(name,
                 Value(Function(param, [=](shared_ptr<Environment> callEnv) {
                   return eval(*body, callEnv);
                 })));

  return Value();
}

MULTIPLICATIVEはINFIXと名前を変更し、%ではなく+と-を扱えるようになった。それに伴いeval_multiplicativeをeval_infixにリネームし、処理内容を修正。

Value eval_infix(const Ast& ast, shared_ptr<Environment> env) {
  auto l = eval(*ast.nodes[0], env).to_long();
  for (auto i = 1; i < ast.nodes.size(); i += 2) {
    auto o = ast.nodes[i]->token;
    auto r = eval(*ast.nodes[i + 1], env).to_long();
    if (o == "+") {
      l += r;
    } else if (o == "-") {
      l -= r;
    }
  }
  return Value(l);
}

eval_conditionは<を使うように修正。

Value eval_condition(const Ast& ast, 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);
}

eval_callは引数を扱えるように修正。

Value eval_call(const Ast& ast, shared_ptr<Environment> env) {
  auto name = ast.nodes[0]->token;
  auto fn = env->get_value(name).to_function();
  auto val = eval(*ast.nodes[1], env);

  auto callEnv = make_shared<Environment>(env);
  callEnv->set_value(fn.param, move(val));

  try {
    return fn.eval(callEnv);
  } catch (const Value& e) {
    return e;
  }
}

最後にビルトイン関数putsを新しいFunction型に合わせて修正。

  env->set_value("puts", Value(Function("arg", [](shared_ptr<Environment> env) {
                   cout << env->get_value("arg").str() << endl;
                   return Value();
                 })));

コンパイルして実行すると、

> time ./fib fib.fib
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269

real    1m8.487s
user    1m8.177s
sys 0m0.103s

おっ、遅すぎる。。。 ^^;

(2020/7/21 追記）-O2で再度コンパイルして実行したところ、実行時間は以下のように改善されました。

real    0m10.811s
user    0m10.768s
sys 0m0.016s

350行に満たないコード量でFibLangインタープリタを完成したものの、構文木駆動型インタープリタでは遅すぎることが判明。次回はバックエンドにLLVMを用いて高速化してみよう。

最終的なソースコード

fib.cc

//
//  FibLang
//  A Programming Language just for writing Fibonacci number program. :)
//
//  Copyright (c) 2020 Yuji Hirose. All rights reserved.
//  MIT License
//

#include <fstream>

#include "peglib.h"

using namespace std;
using namespace peg;
using namespace peg::udl;

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;
}

//-----------------------------------------------------------------------------
// Parser
//-----------------------------------------------------------------------------

shared_ptr<Ast> parse(const vector<char>& source, ostream& out) {
  parser parser(R"(
    # Syntax Rules
    STATEMENTS              <- (DEFINITION / EXPRESSION)*
    DEFINITION              <- 'def' Identifier '(' Identifier ')' EXPRESSION
    EXPRESSION              <- TERNARY
    TERNARY                 <- CONDITION ('?' EXPRESSION ':' EXPRESSION)?
    CONDITION               <- INFIX (ConditionOperator INFIX)?
    INFIX                   <- CALL (InfixOperator CALL)*
    CALL                    <- PRIMARY ('(' EXPRESSION ')')?
    PRIMARY                 <- FOR / Identifier / '(' EXPRESSION ')' / Number
    FOR                     <- 'for' Identifier 'from' Number 'to' Number EXPRESSION

    # Token Rules
    ConditionOperator       <- '<'
    InfixOperator           <- '+' / '-'
    Identifier              <- !Keyword < [a-zA-Z][a-zA-Z0-9_]* >
    Number                  <- < [0-9]+ >
    Keyword                 <- 'def' / 'for' / 'from' / 'to'

    %whitespace             <- [ \t\r\n]*
  )");

  parser.enable_ast();

  parser.log = [&](size_t ln, size_t col, const string& msg) {
    out << ln << ":" << col << ": " << msg << endl;
  };

  shared_ptr<Ast> ast;
  if (parser.parse_n(source.data(), source.size(), ast)) {
    return AstOptimizer(true).optimize(ast);
  }

  return nullptr;
}

//-----------------------------------------------------------------------------
// Value
//-----------------------------------------------------------------------------

struct Value;
struct Environment;

struct Function {
  string param;
  function<Value(shared_ptr<Environment> env)> eval;

  Function(const string& param,
           function<Value(shared_ptr<Environment> env)>&& eval)
      : param(param), eval(eval) {}
};

struct Value {
  enum class Type { Nil, Bool, Long, Function };
  Type type;
  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(Function&& f) : type(Type::Function), v(f) {}

  // Cast value
  bool to_bool() const {
    switch (type) {
      case Type::Bool:
        return any_cast<bool>(v);
      case Type::Long:
        return any_cast<long>(v) != 0;
      default:
        throw runtime_error("type error.");
    }
  }

  long to_long() const {
    switch (type) {
      case Type::Long:
        return any_cast<long>(v);
      default:
        throw runtime_error("type error.");
    }
  }

  Function to_function() const {
    switch (type) {
      case Type::Function:
        return any_cast<Function>(v);
      default:
        throw runtime_error("type error.");
    }
  }

  // Comparison
  bool operator<(const Value& rhs) const {
    switch (type) {
      case Type::Nil:
        return false;
      case Type::Bool:
        return to_bool() < rhs.to_bool();
      case Type::Long:
        return to_long() < rhs.to_long();
      default:
        throw logic_error("invalid internal condition.");
    }
    // NOTREACHED
  }

  // String representation
  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::Function:
        return "[function]";
      default:
        throw logic_error("invalid internal condition.");
    }
  }
};

//-----------------------------------------------------------------------------
// Environment
//-----------------------------------------------------------------------------

struct Environment {
  shared_ptr<Environment> outer;
  map<string, Value> values;

  Environment(shared_ptr<Environment> outer = nullptr) : outer(outer) {}

  const Value& get_value(const string& s) const {
    if (values.find(s) != values.end()) {
      return values.at(s);
    } else if (outer) {
      return outer->get_value(s);
    }
    throw runtime_error("undefined variable '" + s + "'...");
  }

  void set_value(const string& s, Value&& val) { values.emplace(s, val); }
};

//-----------------------------------------------------------------------------
// Interpreter
//-----------------------------------------------------------------------------

Value eval(const Ast& ast, shared_ptr<Environment> env);

Value eval_statements(const Ast& ast, shared_ptr<Environment> env) {
  if (!ast.nodes.empty()) {
    auto it = ast.nodes.begin();
    while (it != ast.nodes.end() - 1) {
      eval(**it, env);
      ++it;
    }
    return eval(**it, env);
  }
  return Value();
}

Value eval_definition(const Ast& ast, shared_ptr<Environment> env) {
  const auto& name = ast.nodes[0]->token;
  const auto& param = ast.nodes[1]->token;
  auto body = ast.nodes[2];

  env->set_value(name,
                 Value(Function(param, [=](shared_ptr<Environment> callEnv) {
                   return eval(*body, callEnv);
                 })));

  return Value();
}

Value eval_ternary(const Ast& ast, shared_ptr<Environment> env) {
  auto cond = eval(*ast.nodes[0], env).to_bool();
  auto idx = cond ? 1 : 2;
  return eval(*ast.nodes[idx], env);
}

Value eval_condition(const Ast& ast, 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_infix(const Ast& ast, shared_ptr<Environment> env) {
  auto l = eval(*ast.nodes[0], env).to_long();
  for (auto i = 1; i < ast.nodes.size(); i += 2) {
    auto o = ast.nodes[i]->token;
    auto r = eval(*ast.nodes[i + 1], env).to_long();
    if (o == "+") {
      l += r;
    } else if (o == "-") {
      l -= r;
    }
  }
  return Value(l);
}

Value eval_call(const Ast& ast, shared_ptr<Environment> env) {
  auto name = ast.nodes[0]->token;
  auto fn = env->get_value(name).to_function();
  auto val = eval(*ast.nodes[1], env);

  auto callEnv = make_shared<Environment>(env);
  callEnv->set_value(fn.param, move(val));

  try {
    return fn.eval(callEnv);
  } catch (const Value& e) {
    return e;
  }
}

Value eval_for(const Ast& ast, 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 = make_shared<Environment>(env);
    call_env->set_value(ident, Value(i));
    eval(expr, call_env);
  }

  return Value();
}

Value eval(const Ast& ast, shared_ptr<Environment> env) {
  switch (ast.tag) {
    // Rules
    case "STATEMENTS"_:
      return eval_statements(ast, env);
    case "DEFINITION"_:
      return eval_definition(ast, env);
    case "TERNARY"_:
      return eval_ternary(ast, env);
    case "CONDITION"_:
      return eval_condition(ast, env);
    case "INFIX"_:
      return eval_infix(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 "Number"_:
      return Value(stol(ast.token));
  }

  return Value();
}

Value interpret(const Ast& ast) {
  auto env = make_shared<Environment>();

  env->set_value("puts", Value(Function("arg", [](shared_ptr<Environment> env) {
                   cout << env->get_value("arg").str() << endl;
                   return Value();
                 })));

  return eval(ast, env);
}

//-----------------------------------------------------------------------------
// main
//-----------------------------------------------------------------------------

int main(int argc, const char** argv) {
  if (argc < 2) {
    cerr << "usage: fib [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;
  }

  auto ast = parse(source, cerr);
  if (!ast) {
    return 3;
  }

  try {
    interpret(*ast);
  } catch (const exception& e) {
    cerr << e.what() << endl;
    return 4;
  }

  return 0;
}