2

I would like to construct a simple parser/typechecker/evaluator for the simply typed lambda calculus. I've already implemented such in Rust, but as someone new to C++, I'm unsure what the best way to represent the AST in. As an example, in Rust, I can define a recursive sum type. I can then use pattern matching or the Visitor pattern to visit subterms.

enum Term {
    // de Bruijn index
    Var(usize),
    // Lambda abstraction x: T. t
    Abs(Box<Term>, Box<Term>),
    // Application t1 t2
    App(Box<Term>, Box<Term>),
}

fn ex(term: &mut Term) {
    match term {
        Term::Var(idx) => {

        },
        Term::Abs(ty, tm) => {
            ex(tm.as_mut());
        },
        Term::App(t1, t2) => {
            // do something
        }
    }
}

Without sum types, it seems like there are 2 primary ways to represent something similar in C++: an enum/union pair (which I would use in C), or a class hierarchy with the visitor pattern (full implementation not shown)

class Expr {
public:
  virtual void visit(Visitor &v) const = 0;
  virtual ~Expr() {}
};

class Var : public Expr {
public:
  Var(int idx) : debruijn{idx} {}

private:
  int debruijn;
};

class App : public Expr {
public:
  App(std::unique_ptr<Expr> t1, std::unique_ptr<Expr> t2)
      : e1{std::move(t1)}, e2{std::move(t2)} {}

private:
  std::unique_ptr<Expr> e1;
  std::unique_ptr<Expr> e2;
};

class Abs : public Expr {
public:
  Abs(Type ty, std::unique_ptr<Expr> e) : e{std::move(e)}, ty{ty} {}

private:
  Type ty;
  std::unique_ptr<Expr> e;
};

Is this the best way to do it? I would like to start off my C++ learning by writing code in the most modern and idiomatic style.

crunch
  • 156
  • 8

1 Answers1

1

As of C++17, C++ does have sum-types - sort of, in the standard library: std::variant.

And you can use std::visit with the overloaded hack for matching the right case class. Using that for an AST should be pretty idiomatic these days.

Also, you might want to use std::optional<T> instead of std::unique_ptr<T>.

... Alternatively, you can have a look at the Boost.Spirit X3 library, which generates parsers, and see what goes on under the hood there. It's a C++14 library.

einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • Thanks for the response. I looked into using `std::variant` but I'm not sure how well that will scale if I want to add more than 3 syntactic forms - I will look into it though. For `std::unique_ptr`, I was under the impression that this was the best way to store a pointer to a derived class, so that I can still use polymorphic dispatch – crunch Nov 02 '19 at 14:46
  • @crunch: Why should it be a pointer, though? If you don't need the type-erasure aspect for subclasses, you can just use value semantics. – einpoklum Nov 02 '19 at 16:23
  • 1
    I thought (and experienced) that using value semantics would essentially upcast `Abs` to `Expr` and erase the overridden virtual functions on `Abs` with those defined on `Expr` – crunch Nov 02 '19 at 17:14
  • @crunch: Not if you use variants... e.g. if Expr is a variant of the possible different kinds of expressions, that shouldn happen. Although... I wonder if that won't get you some circular dependencies. (browses around...) Oh, it's probably fine, see [this question](https://stackoverflow.com/q/53502760/1593077). – einpoklum Nov 02 '19 at 18:09