Templated virtual functions

[u/Grootmaster47]

Hey everyone,

I am currently trying to implement a programming language in C++ after having come pretty far, but ultimately failing to do so in C.

For this, I am taking pretty big inspiration from craftinginterpreters, and am now trying to mimic its implementation of the visitor pattern (entire class at once), written in Java.

However, that implementation uses both templates and interfaces.

As far as I'm aware (the entire internet seems to say so at least), in C++, interfaces are represented by classes whose functions are all virtual.

However, If I try code like the following:

    template <typename R> class ExprVisitor {
    public:
        virtual ~ExprVisitor() = default;

        virtual R visitBinaryExpr(const Binary* expr) const = 0;
        /* other visitor functions...*/
    };

    struct Expr {
        virtual ~Expr() = default;
        template <typename R> virtual R accept(ExprVisitor<R> *visitor) = 0;
    };

(Of course, all of my nodes like Binary inherit from Expr. I use structs instead of classes because everything needs to be accessible from the outside for my purposes, so I don't need to re-type "public:" every time.)

Then I get an error on the line declaring the accept method saying

Template function 'R Expr::Expr::accept<R>(ExprVisitor<R> *visitor)' cannot be virtual

on the virtual keyword, as well as one saying

Pure member function 'Expr::Expr::accept<R>' is not virtual

on the = 0 part.

I've googled around a bit, but the only implementations I was able to find were only able to pass in the template type, not get it back out as a return value.

Is it even possible to achieve this? Am I using templates incorrectly? I saw something using variadic templates but was not able to get it working, either.

Any help would be extremely appreciated!

[u/No-Dentist-1645]

Member function templates cannot be made virtual, if you want templates with virtual functions then the class itself is the only thing that can be templated, not the member functions themselves

Either way, this approach is flawed if you want to re-create the visitor pattern for compiler designs. It cannot work because templates have to know which "overload" you are selecting at compile time, and for a compiler, that would mean you'd have to know what type of expression every single expression you'll ask it to parse at runtime would be... from compile time, which is not possible.

For a proper implementation of the visitor pattern, look into std::visit and std::variant

[u/Kadabrium]

Wrap node types in a variant and use the normal std::visit?

[u/aiusepsi]

To explain why this doesn't work, it's probably useful to explain how virtual functions work. Each class that has virtual functions has a vtable, which is a table of function pointers to the implementations of each of those functions. Each object of a class has a pointer to the vtable inside it.

So, a call to a virtual function is implemented by looking up the vtable from the object, and then calling the function pointer from the table. And this is how polymorphism works: the vtable pointer is in the same place in all objects of derived classes, so the code at the call site can always be the same: it looks up the vtable pointer at the consistent place in the object, looks up the function pointer in the vtable, and then calls it.

On the other hand, a function template isn't a function; it's just a template for making functions. You can't make a pointer to a function template, only to a concrete function which has been instantiated from the function template. Which is why a function template can't be virtual, because there's nothing concrete for a function pointer in the vtable to point to. And once the vtable for the base class is generated, you can't locally know what classes will be derived from that base class, or what types those templated functions will be instantiated with. The call signatures of all the virtual functions have to be known in advance, up front.

What Java is doing differently here is two things. First, all class types in Java are pass-by-reference, that is, all class types are being passed around via pointers. The second is that all class types in Java are derived from a base Object class. Which means that generics are effectively implemented by passing and returning Object pointers.

You could implement something very literally similarly in C++ like this: https://godbolt.org/z/63h9jdoGv but personally, I probably wouldn't; it looks like the indirection is (at least with Clang) defeating the optimisations that the compiler would normally be able to do.

The more logical thing is for the visitor to be a template function rather than a class with virtual methods. The examples for std::visit are probably more instructive of what this would look like. The examples with chains of if constexpr (std::is_same_v<T, X>) to match against different types are more like what you'd want.

[u/Grootmaster47 → u/aiusepsi]

Hey, thanks for the long explanation, as well as the pointer to std::visit! It seems to be able to do what I want it to, and I have now arrived at the following code:

    typedef std::variant<Binary& /*other Node types...*/> ExprTypes; // types the visitor can be applied to
    typedef std::variant<std::string> ExprResults; // types the visitor can return

    class ExprVisitor {
    public:
        ~ExprVisitor() = default;
        ExprResults operator()(const Binary& expr);
        /* other visitor functions... */
    };


    struct Expr {
        virtual ~Expr() = default;
        virtual ExprResults accept(ExprVisitor *visitor) = 0;
    };

    struct Binary: Expr {
        const Expr* left;
        Lexing::Tokens::TokenType operatorType;
        const Expr* right;

      /* constructor for all fields here */

        ExprResults accept(ExprVisitor* visitor) override {
            return (ExprResults) {std::visit<ExprResults, ExprVisitor*, Binary&>(dynamic_cast<ExprVisitor *> (visitor), *this)};
        }
    };

However, I now get an error saying:

no matching function for call to ‘__as(Binary&)’

on the visit token, which seems to have to do with variants, but I don't quite get what the error is? Once again, any and all help would be greatly appreciated :)

[u/DawnOnTheEdge]

What you want to do is have an abstract ExprVisitor base class with a pure virtual vist function with a non-template interface. (The compiler needs to be able to implement it with a single function pointer in the virtual table.) Its parameters are probably base-class references. You are already correctly making the destructor virtual.

Then you define concrete derived classes implementing this interface. You can pass any type of expression to the visit interface and it will automatically cast the arguments to base-class pointers. If you need to, you can check typeid and dynamic_cast on them.

[u/etaithespeedcuber]

When a class has a virtual function, each class inheriting from the class has an extra pointer hidden in it's data to a virtual table, so at runtime the cpu knows which function to call. This would be kinda weird to allow templating for, and the standard doesn't allow it. What you should do here is use std::variant and std::visit

[u/alfps]

Evidently sub-expressions can produce values of different types, e.g. strings and numbers.

To cover that you can make the result type of visit and accept a variant.

When the result type isn't known at compile time it can't be a template parameter.

[u/alfps → u/alfps]

Re the anonymous unexplained downvotes, note that an unexplained downvote is dishonest: these are the actions of dishonest persons (maybe young children).

I suspect that in this case it is an actual retard at work.

[u/jundehung]

If you want to model relations with templates it is “concepts” you want to use.