LoginSignup
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@yhirose

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

Last updated at Posted at 2020-02-19

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

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

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

今回も前回と同じ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;
}
3
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?