6
\$\begingroup\$

I'm new to C++, so I'm trying to learn the language by implementing all the type systems and languages in Pierce's Types and Programming Languages. My first attempt starts at the very beginning and implementes this very simple language "Arithmetic Expressions" on page 41 in the book (for those that want to look at it, which is not required to understand my question).

I'm looking for at least advice on the following:

  1. Language feature use.

  2. Efficiency, e.g. unnecessary object creation.

One point that bugs me is also that the language has the following evaluation rule. If nv is a numeric value, then pred (succ nv) evaluates to nv. To evaluate a pred term it seems like one needs to be able to peek inside the succ term to pull out the subterm. I'm currently doing this by making Pred a friend of the Succ class. However, such an dependency seems somewhat ugly to me.

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

I also don't really like the external TermType class. My design is pretty much based on what I would typically do in C, i.e. the AST is linked together using void pointers and the first field of each AST node type contains a numeric value, which tells the type of struct it needs to be cast to. Maybe there's a technique in C++ that allows getting around the sort of downcasting without incurring a runtime overhead?

\$\endgroup\$

migrated from programmers.stackexchange.com Nov 5 '15 at 17:44

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • \$\begingroup\$ @user202953: It's probably a good idea to add your test-code. \$\endgroup\$ – Deduplicator Nov 6 '15 at 2:11
3
\$\begingroup\$

Your hierarchy necessarily involves virtual methods, and therefore some kind of pointer. However, you have opted for a dangerous mix of raw pointers and shared pointers. The main problem is that a user of the Term class must deal with these pointers themselves, even though the pointers are merely an implementation detail of the Term class. It would therefore be better to design Term in a way that manages the pointer for us. In C++, this is generally done via an opaque pointer, also known as the pImpl pattern. The outer wrapper Term only has non-virtual methods, and just delegates to its contained values that must implement a specific interface. For example:

class Term;

class TermIf {
public:
    virtual void print(std::ostream&) const = 0;
    virtual Term eval() const = 0;
    virtual ~TermIf() {}
};

class Term {
    std::shared_ptr<TermIf> mImpl;
    Term(std::shared_ptr<TermIf> impl) : mImpl{impl} {}

public:
    template<typename TermImpl, typename... Args>
    static Term make(Args&& ... args) {
        return Term(std::shared_ptr<TermIf>(new TermImpl(std::forward<Args>(args)...)));
    }

    friend std::ostream& operator << (std::ostream& out, const Term& t) {
        t.mImpl->print(out);
        return out;
    }

    Term eval() const {
        return mImpl->eval();
    }
};

Now that the pointers are nicely encapsulated, they no longer get in the way. Previously, your code segfaulted for me for a simple test case since the ownership of pointers was not precisely managed. Here, only the Term class must deal with pointers, and is easily to verify to be correct.

The static Term make() might require a bit of explanation. To construct a new Term, we would have to write something like Term(std::shared_ptr<Conditional>(new Conditional(a, b, c))) which gets quite annoying. This template function uses perfect forwarding to create a new term with a simple expression such as Term::make<Conditional>(a, b, c). Again, this serves to encapsulate the details revolving around pointers inside the Term class rather than making pointer management the responsibility of users.

We do not require the enum class TermType since the types are already encoded in the types of the subclasses such as True, Conditional, or Succ. We could instead use a dynamic_cast, which tries to down-cast an object or returns a null pointer if not successful. This a bit awkward with a pImpl, and I generally dislike dynamic casts. Instead, we can create a bunch of virtual methods such as asPred() that return null, or a pointer to the object if it is of the expected class. Given a Term t, we can then write code such as if (auto pred = t.asPred()) pred->use_pred_only_method(). This is exactly equivalent to a dynamic cast, but has a nicer API. Now our code would look like:

class True;
class False;
class Conditional;
class Zero;
class Succ;
class Pred;
class IsZero;

class Term;

class TermIf {
public:
    virtual void print(std::ostream&) const = 0;
    virtual Term eval() const = 0;
    virtual ~TermIf() {}

    virtual const True* asTrue() const { return nullptr; }
    virtual const False* asFalse() const { return nullptr; }
    virtual const Conditional* asConditional() const { return nullptr; }
    virtual const Zero* asZero() const { return nullptr; }
    virtual const Succ* asSucc() const { return nullptr; }
    virtual const Pred* asPred() const { return nullptr; }
    virtual const IsZero* asIsZero() const { return nullptr; }
};

class Term {
    std::shared_ptr<TermIf> mImpl;
    Term(std::shared_ptr<TermIf> impl) : mImpl{impl} {}

public:
    template<typename TermImpl, typename... Args>
    static Term make(Args&& ... args) {
        return Term(std::shared_ptr<TermIf>(new TermImpl(std::forward<Args>(args)...)));
    }

    friend std::ostream& operator << (std::ostream& out, const Term& t) {
        t.mImpl->print(out);
        return out;
    }

    Term eval() const {
        return mImpl->eval();
    }

    const True* asTrue() const { return mImpl->asTrue(); }
    const False* asFalse() const { return mImpl->asFalse(); }
    const Conditional* asConditional() const { return mImpl->asConditional(); }
    const Zero* asZero() const { return mImpl->asZero(); }
    const Succ* asSucc() const { return mImpl->asSucc(); }
    const Pred* asPred() const { return mImpl->asPred(); }
};

Notice how the operator<< for output is defined as a free function operating on the Term class. This makes printing out any Term much easier than a print() method, which is here only used to implement the output operator.

Since we got rid of the pointers and can just use Term, the rest of the code is fairly straightforward.

// Booleans

class True : public TermIf {
public:
    void print(std::ostream& out) const override {
        out << "True";
    }

    Term eval() const { return Term::make<True>(); }

    const True* asTrue() const override { return this; }
};

class False : public TermIf {
public:
    void print(std::ostream& out) const override {
        out << "False";
    }

    Term eval() const { return Term::make<False>(); }

    const False* asFalse() const override { return this; }
};

// Conditionals

class Conditional : public TermIf {
    Term cond;
    Term true_branch;
    Term false_branch;
public:
    Conditional(Term cond, Term true_branch, Term false_branch)
        : cond{cond}, true_branch{true_branch}, false_branch{false_branch}
    {}

    void print(std::ostream& out) const override {
        out << "if (" << cond << ") {" << true_branch << "} else {" << false_branch << "}";
    }

    Term eval() const override {
        if (cond.eval().asTrue() != nullptr)
            return true_branch.eval();
        else
            return false_branch.eval();
    }

    const Conditional* asConditional() const override { return this; }
};

// Numerals

class Zero : public TermIf {
public:
    void print(std::ostream& out) const override { out << 0; }

    Term eval() const override { return Term::make<Zero>(); }

    const Zero* asZero() const override { return this; }
};

class Succ : public TermIf {
    Term mInner;
public:
    Succ(Term x) : mInner{x} {}

    Term inner() const { return mInner; }

    void print(std::ostream& out) const override { out << "succ " << inner(); }

    Term eval() const override; 

    const Succ* asSucc() const override { return this; }
};

class Pred : public TermIf {
    Term mInner;
public:
    Pred(Term x) : mInner{x} {}

    Term inner() const { return mInner; }

    void print(std::ostream& out) const override { out << "pred " << inner(); }

    Term eval() const override;

    const Pred* asPred() const override { return this; }
};

Term Succ::eval() const {
    Term x = inner().eval();
    if (auto pred = x.asPred())
        return pred->inner();
    return Term::make<Succ>(x);
}

Term Pred::eval() const {
    Term x = inner().eval();
    if (auto succ = x.asSucc())
        return succ->inner();
    return Term::make<Pred>(x);
}

class IsZero : public TermIf {
    Term mInner;
public:
    IsZero(Term x) : mInner{x} {}

    Term inner() const { return mInner; }

    void print(std::ostream& out) const override { out << "iszero " << inner(); }

    Term eval() const override {
        if (inner().eval().asZero())
            return Term::make<True>();
        return Term::make<False>();
    }

    const IsZero* asIsZero() const override { return this; }
};

One thing that still bugs me with this code is that each type must implement a print and eval method. This means that the responsibility of the ast classes are:

  • representing a syntax tree
  • pretty-printing the syntax tree
  • evaluating a syntax tree
  • representing a value (except for Conditional and IsNull).

We can factor two of these concerns by using the Visitor Pattern, but that is a bit complicated in C++, so I'll ignore it here.

Your operator overloading is a bit faulty. As a rule of thumb: binary operators should not be declared as member operators, but as free functions. This makes it easier to verify that the necessary properties of these operators hold. For example, when x == y then it should also be y == x. This is not the case for your bool Zero::operator==(int) const (while zero == 0 works, 0 == zero or zero != 0 would fail). Given any one of these operators, the rest is easy to define as free functions:

bool operator == (const Term& t, int n) { /* actual implementation */ }
bool operator == (int n, const Term& t) { return t == n; }
bool operator != (const Term& t, int n) { return !(t == n); }
bool operator == (int n, const Term& t) { return t != n; }

Unfortunately, C++ does not autogenerate these operators for us. Since free functions cannot be virtual, using Zero or any other subtype does not make sense in the signature – it must be Term. In your case, you would have to call a virtual member function from the operator. With my refactoring, the operator== can be defined as

bool operator == (const Term& t, int n) {
    if (term.asZero())
      return n == 0;
    if (auto pred = term.asPred())
        return prec.inner() == (n + 1);
    if (auto succ = term.asSucc())
        return succ.inner() == (n - 1);
    return false;
}

In fact, that would be way clearer if we define a conversion to int from the Zero, Pred, and Succ classes. For example:

class Term {
  ...
  operator int() {
    if (auto zero = asZero()) return 0;
    if (auto pred = asPred()) return int(pred->inner()) - 1;
    if (auto succ = asSucc()) return int(succ->inner()) + 1;
    throw ...;
  }
};

Then:

bool operator == (const Term& t, int n) {
    if (term.asZero() || term.asPred() || term.asSucc())
        return n == int(term);
    return false;
}

Note that once you separate value representation from AST representation, these operations will be simplified further. In the meanwhile, you could create a interface IntValue that is inherited by Succ, Pred, and Zero and defines operator int() etc.. With the appropriate asIntValue() operation, this would then simplify the equality operator to

if (auto intvalue = term.asIntValue())
    return n == int(*intvalue);
return false;

A similar approach could be used to group the boolean values with an BoolValue type.

\$\endgroup\$
1
\$\begingroup\$
  1. Prefer std::make_shared<T>(...) over std::shared_ptr<T>(new T(...)). That's not only shorter, it's also potentially more efficient as it can coalesce the allocation for the counters and the payload.

    Otherwise, you need to make Term::~Term virtual (and explicitly defaulted), or polymorphic deallocation won't work.

  2. You can reuse a statically allocated constant, if you use non-owning std::shared_ptrs.

  3. You can use a single template for constants, and explicitly specialize parts as needed.

  4. No need for GetType as you can use RTTI with typeid and dynamic_cast.

  5. Mark your classes final whenever you can. Unless a class is designed as a base-class, making it one is normally a bug, and disallowing it allows some optimizations.

  6. Aside from the fact that binary operators generally should not be member-functions, overriding one that way is the wrong solution to your problem anyway:
    You should evaluate both sides and compare them manually.

  7. print should return the used stream, and just be used as an implementation-detail for std::ostream& operator<<(std::ostream&, const Term&).

  8. Succ::eval needs an implementation that actually simplifies.
    You know, just collapse it with Pred in one template.

  9. Put it all in your own namespace.

  10. Be wary of single-argument constructors, as they can be used for implicit type-conversions unless marked explicit.

On coliru:

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

}
\$\endgroup\$
0
\$\begingroup\$

I don't know the book but have personally written few parsers, compilers and virtual machines, so, I will answer from this perspective.

AST v.s. eval()

I do not fully understand why you have selected mathematical representation of numbers which can be found in set-theory. There is one element to be known - zero (or empty set) and a construct to create another - succ(zero) (e.g. set containing one element - the previous set).

In classical numerical evaluation, you would have some Numeric type containing the numeric value. Succ and Pred would then access the value and add/substract one (increase or decrease).

With your cunnert design, 1 ~ succ(zero), but pred does not know 1, it only knows succ(something) or something_else. This way you either have to make t_ somehow public (e.g. by public getter) or have to use the friending as you did.

C++ features used

It is safe to use shared_ptr but it would be better to have some constants and actually share them! The examle would be Zero::eval() - looks like good attempt to share, but you'll need std::enable_shared_from_this to make it working (trully sharing one instance, not creating new ones). But you will also need static versions and probably hide the constructor (to ensure, there is only one Zero and only one True, not multiple).

The TermType can be replaced by typeid

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.