AST实现

Question

我是C++的新手，所以我试图通过实现皮尔斯类型和编程语言中的所有类型系统和语言来学习这种语言。我的第一次尝试从一开始就开始了，并在书的第41页实现了这个非常简单的语言“算术表达式”(对于那些想看它的人来说，这并不是理解我的问题所必需的)。

我至少在以下几个方面寻求建议：

1. 语言特征使用。
2. 效率，例如不必要的对象创建。

还有一点让我感到困扰的是，语言有以下的评估规则。如果nv是一个数值，则pred (succ nv)的计算结果为nv。要计算pred项，似乎需要能够在succ项中查看以提取子项。我目前正在通过使Pred成为Succ类的朋友来完成这一任务。然而，对我来说，这种依赖似乎有点丑陋。

enum class TermType { kTrue, kFalse, kCond, kZero, kSucc, kPred, kIsZero };

class Term {
 public:
  virtual void print(std::ostream&) const = 0;
  virtual std::shared_ptr<Term> eval() = 0;
  virtual TermType GetType() const = 0;
  virtual bool operator==(bool) const { return false; }
  virtual bool operator==(int) const { return false; }
};

// Booleans

class True : public Term {
 public:
  void print(std::ostream& out) const { out << "True"; }
  std::shared_ptr<Term> eval() { return std::shared_ptr<Term>(new True()); }
  TermType GetType() const { return TermType::kTrue; }
  bool operator==(bool) const;
};

bool True::operator==(bool b) const { return b; }

class False : public Term {
 public:
  void print(std::ostream& out) const { out << "False"; }
  std::shared_ptr<Term> eval() { return std::shared_ptr<Term>(new False()); }
  TermType GetType() const { return TermType::kFalse; }
  bool operator==(bool) const;
};

bool False::operator==(bool b) const { return !b; }

// Conditionals

class Conditional : public Term {
 public:
  Conditional(Term* g, Term* t, Term* f)
      : guard_{g}, tbranch_{t}, fbranch_{f} {}
  Conditional(std::shared_ptr<Term>& g, std::shared_ptr<Term>& t,
              std::shared_ptr<Term>& f)
      : guard_{g}, tbranch_{t}, fbranch_{f} {}

  void print(std::ostream&) const;
  std::shared_ptr<Term> eval();
  TermType GetType() const { return TermType::kCond; }

 private:
  std::shared_ptr<Term> guard_;
  std::shared_ptr<Term> tbranch_;
  std::shared_ptr<Term> fbranch_;
};

void Conditional::print(std::ostream& out) const {
  out << "if (";
  guard_->print(out);
  out << ") {";
  tbranch_->print(out);
  out << "} else {";
  fbranch_->print(out);
  out << "}";
}

std::shared_ptr<Term> Conditional::eval() {
  if (*guard_->eval() == true)
    return tbranch_->eval();
  else
    return fbranch_->eval();
}

// Numerals

class Succ;

class Zero : public Term {
 public:
  void print(std::ostream& out) const { out << "0"; }
  std::shared_ptr<Term> eval() { return std::shared_ptr<Term>(this); }
  TermType GetType() const { return TermType::kZero; }
  bool operator==(int n) const { return n == 0; }
};

class Succ : public Term {
  friend class Pred;

 public:
  Succ(Term* t) : t_{t} {}
  Succ(std::shared_ptr<Term> t) : t_{t} {}
  void print(std::ostream&) const;
  std::shared_ptr<Term> eval();
  TermType GetType() const { return TermType::kSucc; }

 private:
  std::shared_ptr<Term> t_;
};

void Succ::print(std::ostream& out) const {
  out << "succ ";
  t_->print(out);
}

std::shared_ptr<Term> Succ::eval() {
  return std::shared_ptr<Term>(new Succ(t_->eval()));
}

class Pred : public Term {
 public:
  Pred(Term* t) : t_{t} {}
  Pred(std::shared_ptr<Term> t) : t_{t} {}
  void print(std::ostream&) const;
  std::shared_ptr<Term> eval();
  TermType GetType() const { return TermType::kPred; }

 private:
  std::shared_ptr<Term> t_;
};

void Pred::print(std::ostream& out) const {
  out << "pred ";
  t_->print(out);
}

std::shared_ptr<Term> Pred::eval() {
  std::shared_ptr<Term> t = t_->eval();
  if (t->GetType() == TermType::kSucc)
    return std::static_pointer_cast<Succ>(t)->t_;
  else
    return t;
}

class IsZero : public Term {
 public:
  IsZero(Term* t) : t_{t} {}
  IsZero(std::shared_ptr<Term> t) : t_{t} {}
  void print(std::ostream&) const;
  std::shared_ptr<Term> eval();
  TermType GetType() const { return TermType::kIsZero; }

 private:
  std::shared_ptr<Term> t_;
};

void IsZero::print(std::ostream& out) const {
  out << "iszero ";
  t_->print(out);
}

std::shared_ptr<Term> IsZero::eval() {
  if (t_->eval() == 0)
    return std::shared_ptr<Term>(new True());
  else
    return std::shared_ptr<Term>(new False());
}

我也不太喜欢外部TermType类。我的设计很大程度上是基于我通常在C中所做的工作，即AST使用空指针链接在一起，每个AST节点类型的第一个字段包含一个数字值，该值告诉需要将其转换到的结构类型。也许C++中有一种技术可以在不引起运行时开销的情况下绕过这种类型的下传？

Answer 1

1. 喜欢std::make_shared<T>(...)而不是std::shared_ptr<T>(new T(...))。这不仅更短，而且可能更有效，因为它可以合并计数器和有效负载的分配。否则，您需要使Term::~Term虚拟(并显式地默认)，否则多态去分配将无法工作。
2. 如果使用不拥有的std::shared_ptrs，则可以重用静态分配的常量。
3. 您可以对常量使用单个模板，并在需要时显式地指定部分。
4. 不需要GetType，因为您可以在typeid和dynamic_cast中使用RTTI。
5. 尽可能标记您的类final。除非一个类被设计为一个基类，否则它通常是一个bug，并且不允许它进行一些优化。
6. 除了二进制运算符通常不应该是成员函数这一事实之外，以这种方式重写二进制运算符也是解决问题的错误方法: ，您应该评估双方并手动比较它们。
7. print应该返回已使用的流，并仅用作std::ostream& operator<<(std::ostream&, const Term&)的实现细节。
8. Succ::eval需要一个实际简化的实现。，你知道，只要在一个模板中用Pred折叠它。
9. 将其全部放在您自己的命名空间中。
10. 注意单参数构造函数，因为除非标记为explicit，否则它们可以用于隐式类型转换。

论科尔鲁：

#include <iostream>
#include <memory>
#include <type_traits>
#include <assert.h>
#include <stdlib.h>

namespace my_ast {

struct Term {
    using pointer = std::shared_ptr<Term>;
    virtual std::ostream& print(std::ostream&) const = 0;
    virtual pointer eval() const = 0;
    virtual bool equal(const Term&) const { assert(0); abort(); }
};

inline std::ostream& operator<<(std::ostream& o, const Term& t) { return t.print(o); }
inline bool operator==(const Term& a, const Term& b) {
    return a.eval()->equal(*b.eval());
}
inline bool operator!=(const Term& a, const Term& b) { return !(a == b); }

// Constants

template<class T> struct Constant final : Term {
    static const char* name();
    std::ostream& print(std::ostream& out) const { return out << name(); }
    pointer eval() const { static Constant x = {}; return {pointer(), &x}; }
    bool equal(const Term& b) const { return typeid(*this) == typeid(b); }
};

using True = Constant<std::true_type>;
using False = Constant<std::false_type>;
using Zero = Constant<std::integral_constant<int, 0>>;

template<> const char* True::name() { return "True"; }
template<> const char* False::name() { return "False"; }
template<> const char* Zero::name() { return "0"; }

// Others

struct Conditional final : Term {
    Conditional(const pointer& g, const pointer& t, const pointer& f)
    : guard_{g}, tbranch_{t}, fbranch_{f} { assert(g && t && f); }
    std::ostream& print(std::ostream& out) const {
        return out << "if (" << *guard_ << ") {" << *tbranch_ << "} else {"
                   << *fbranch_ << '}';
    }
    pointer eval() const { return (*guard_ == True() ? tbranch_ : fbranch_)->eval(); }
private:
    pointer guard_, tbranch_, fbranch_;
};

template<bool first> struct SuccOrPred final : Term {
    explicit SuccOrPred(const pointer& t) : t_(t) { assert(t); }
    std::ostream& print(std::ostream& out) const {
        return out << (first ? "succ " : "pred ") << *t_;
    }
    friend class SuccOrPred<!first>;
    pointer eval() const {
        auto r = t_->eval();
        if(auto x = dynamic_cast<SuccOrPred<!first>>(&*r))
            return x->t_;
        return std::make_shared<SuccOrPred>(r);
    }
    bool equal(const Term& b) const {
        auto x = dynamic_cast<const SuccOrPred*>(&b);
        return x && *x->t_ == *t_;
    }
private:
    pointer t_;
};

using Succ = SuccOrPred<true>;
using Pred = SuccOrPred<false>;

struct IsZero final : Term {
    explicit IsZero(const pointer& t) : t_{t} { assert(t); }
    std::ostream& print(std::ostream& out) const { return out << "iszero " << *t_; }
    pointer eval() const {
        return *t_->eval() == Zero() ? True().eval() : False().eval();
    }
private:
    pointer t_;
};

}

Answer 2

我不知道这本书，但我个人写了几个解析器，编译器和虚拟机，所以，我将从这个角度回答。

AST诉S. eval()

我不完全理解你为什么选择数列的数学表示，这在集合论中是可以找到的。有一个要知道的元素--零(或空集)和创建另一个元素的构造-succ(0)(例如，包含一个元素的集合--前一个集合)。

在经典的数值计算中，将有一些包含数值的Numeric类型。然后，Succ和Pred将访问该值并添加/减1(增加或减少)。

根据你的设计，1 ~ succ(zero)，但是pred不知道1，它只知道succ(something)或something_else。通过这种方式，您要么以某种方式使t_公开(例如，通过公共getter)，要么像您所做的那样使用好友。

C++特性使用

使用shared_ptr是安全的，但是最好有一些常量并实际地共享它们！例子是Zero::eval() --看起来是很好的共享尝试，但是您需要std::enable_shared_from_this来使它工作(笨拙地共享一个实例，而不是创建新的实例)。但是您还需要静态版本，并且可能隐藏构造函数(为了确保只有一个Zero和一个True，而不是多个)。

TermType可以由typeid代替