HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

AST implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewreinventing-the-wheelcppstackoverflowc++c++11grammar
astimplementationstackoverflow

Problem

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:

-
Language feature use.

-
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 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 eval() { return std::shared_ptr(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 eval() { return std::shared_ptr(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& g, std::shared_ptr& t,

Solution

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 mImpl;
    Term(std::shared_ptr impl) : mImpl{impl} {}

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

    friend std::ostream& operator 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(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(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 mImpl;
    Term(std::shared_ptr impl) : mImpl{impl} {}

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

    friend std::ostream& operator 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

  • 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 == (in

Code Snippets

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

Context

StackExchange Code Review Q#109911, answer score: 3

Revisions (0)

No revisions yet.