読者です 読者をやめる 読者になる 読者になる

ゆとりーなの日記

日記的な事を書いて行くと思はれる

OCamlは偉大だった

 某講義に於いてOcamlで直線言語インタープリタを作るってのがあったのですが、まぁ何かあったらC++で書き下したくなるのが人情じゃないですか。というわけで行きます。Ocamlのコード貼っ付けるのが手っ取り早いんですが、課題の答案を日記に貼ったら学事に呼び出されたという前例があるとの噂なのでその辺りは賢者しておきます。
 取り敢えず以下のコードが食えるようにします。OcamlC++では流石に函数呼び出し方法等は違うのでそこらへんは甘えました。

interp(CompoundStm(AssignStm("a", OpExp(NumExp(5), Plus, NumExp(3))),
        CompoundStm(AssignStm("b", EseqExp(PrintStm({IdExp("a"),(OpExp(IdExp("a"), Minus, NumExp(1)))}),
         OpExp(NumExp(10), Times, IdExp("a")))),
           PrintStm({IdExp("b")}))));
8
7
80
interp(CompoundStm(AssignStm("a", NumExp(1)), 
        CompoundStm(AssignStm("b", OpExp(EseqExp(AssignStm("a", NumExp(2)), NumExp(3)), Plus, NumExp(4))),
         PrintStm({IdExp("a"), IdExp("b")}))));
2
7
interp(CompoundStm(AssignStm("b", OpExp(NumExp(5), Plus, NumExp(3))),
        CompoundStm(PrintStm({EseqExp(AssignStm("b", OpExp(NumExp(10), Times, NumExp(8))), NumExp(1))}), 
         PrintStm({IdExp("b")}))));
1
80

 はい。まずは木表現の部分。boost::variantを使う方向で行きました。仮想函数ベースでもいけるのでしょうがvariant先生の方がOcamlのバージョンに表記が近づけるかなと思ったのでこちらを採用しました。我々はコンパイル時間の代わりに表記の見栄えを買ったのです。

constexpr struct Plus_ {} Plus = {};
constexpr struct Minus_ {} Minus = {};
constexpr struct Times_ {} Times = {};
constexpr struct Div_ {} Div = {};

typedef boost::variant<Plus_, Minus_, Times_, Div_> binop;

struct stm;
struct exp;

typedef std::tuple<stm, stm> CompoundStm_;
typedef std::tuple<id, exp> AssignStm_;
typedef std::vector<exp> PrintStm_;
typedef std::string IdExp_;
typedef int NumExp_;
typedef std::tuple<exp, binop, exp> OpExp_;
typedef std::tuple<stm, exp> EseqExp_;

struct stm {
  typedef boost::variant<CompoundStm_, AssignStm_, PrintStm_> stm_;
  stm(const stm_ &v);
  std::shared_ptr<stm_> data;
};

struct exp {
  typedef boost::variant<IdExp_, NumExp_, OpExp_, EseqExp_> exp_;
  exp(const exp_ &v);
  std::shared_ptr<exp_> data;
};

stm::stm(const stm_ &v) : data(std::make_shared<stm_>(v)) {}

exp::exp(const exp_ &v) : data(std::make_shared<exp_>(v)) {}

stm::stm_ CompoundStm(const stm &s1, const stm &s2) {
  return stm::stm_(CompoundStm_(s1, s2));
}

stm::stm_ AssignStm(const id &i, const exp &e) {
  return stm::stm_(AssignStm_(i, e));
}

stm::stm_ PrintStm(const std::initializer_list<exp> &s) {
  return stm::stm_(PrintStm_(s));
}

exp::exp_ IdExp(const std::string &i) {
  return exp::exp_(IdExp_(i));
}

exp::exp_ NumExp(int i) {
  return exp::exp_(NumExp_(i));
}

exp::exp_ OpExp(const exp &e1, const binop &b, const exp &e2) {
  return exp::exp_(OpExp_(e1, b, e2));
}

exp::exp_ EseqExp(const stm &s, const exp e) {
  return exp::exp_(EseqExp_(s, e));
}

 アホみたいに長いですね。C++は前方参照能力がしょぼいので残当しています。前方宣言であーだこーだやった結果がこれです。あとinitializer_listの型推論が案外だらしないのでサポートのために一段函数を噛ましてやる必要があります。因みにこの部分に相当するOcamelのコードはなんと10行です。
 続いて文の評価と式の評価。

std::unordered_map<std::string, int> table;

typedef int (*o_t)(int, int);

struct interOp : boost::static_visitor<o_t> {
  o_t operator ()(const Plus_ &) const {
    return [](int lhs, int rhs) {return lhs + rhs;};
  }
  
  o_t operator ()(const Minus_ &) const {
    return [](int lhs, int rhs) {return lhs - rhs;};
  }
  
  o_t operator ()(const Times_ &) const {
    return [](int lhs, int rhs) {return lhs * rhs;};
  }
  
  o_t operator ()(const Div_ &) const {
    return [](int lhs, int rhs) {return lhs / rhs;};
  }
};

struct interStm : boost::static_visitor<void> {
  void operator ()(const CompoundStm_ &s) const;
  void operator ()(const AssignStm_ &s) const;
  void operator ()(const PrintStm_ &s) const;
};

struct interExp : boost::static_visitor<int> {
  int operator ()(const IdExp_ &e) const;
  int operator ()(const NumExp_ &e) const;
  int operator ()(const OpExp_ &e) const;
  int operator ()(const EseqExp_ &e) const;
};

void interStm::operator ()(const CompoundStm_ &s) const {
  boost::apply_visitor(interStm(), *std::get<0>(s).data);
  boost::apply_visitor(interStm(), *std::get<1>(s).data);
}
  
void interStm::operator ()(const AssignStm_ &s) const {
  table[std::get<0>(s)] = boost::apply_visitor(interExp(), *std::get<1>(s).data);
}

void interStm::operator ()(const PrintStm_ &s) const {
  for (const auto &x : s) {
    std::cout << boost::apply_visitor(interExp(), *x.data) << std::endl;
  }
}

int interExp::operator ()(const IdExp_ &e) const {
  return table[e];
}

int interExp::operator ()(const NumExp_ &e) const {
  return e;
}

int interExp::operator ()(const OpExp_ &e) const {
  return (*boost::apply_visitor(interOp(), std::get<1>(e)))(boost::apply_visitor(interExp(), *std::get<0>(e).data), boost::apply_visitor(interExp(), *std::get<2>(e).data));
}

int interExp::operator ()(const EseqExp_ &e) const {
  boost::apply_visitor(interStm(), *std::get<0>(e).data);
  return boost::apply_visitor(interExp(), *std::get<1>(e).data);
}

template <typename Prog>
void interp(Prog prog) {
  boost::apply_visitor(interStm(), prog);
}

 boost::variantのおかげで大分Ocamlの書き方に近づいてはいるものの、やはり前方参照能力の貧弱さ故に冗長な書き方になってしまいます。あとはOcamlではバイナリオペレーションの型をinterExp内でダイレクトに分岐出きるのに対してC++ではvariantのせいで型情報が消えているためこちらも別にビジターしなければいけないのが面倒です。結果返す型も函数ポインタでラムダと残当してしまいました。因みにこちらの方のOcamlは大体20行程で済んでます。
 一方でOcamlでは変数の正しい値をテーブルから取り出すために「函数型イカ娘」を片手に函数再帰をどんどん積んで行くというみたいなそれなりに複雑な事象に頭をリソースをさかれてしまいます。特に途中の代入を保存とかを考え出すと若干厄介です。一方でC++では函数型的な書き方以外もサポートされているので、昔馴染みの手続き型なノリでテーブルを更新することが出来るというお得なところもあるといえばあります。しかし綜合的に見るとOcamlの2倍以上のコードを書かなければならないことを考慮すると、Ocamlは偉大でしたのです。