Help us understand the problem. What is going on with this article?

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

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

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

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

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

  1. 頭の中のオレオレ言語でFizzBuzzを書く
  2. 文法をPEG (Parsing Expression Grammar) に落とす
  3. AST (抽象構文木) を出力するパーサーの作成
  4. 環境
  5. 評価器

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. 評価器

STATEMENTSDEFINITIONルール用の評価器を追加。

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

MULTIPLICATIVEINFIXと名前を変更し、%ではなく+-を扱えるようになった。それに伴いeval_multiplicativeeval_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

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした