C++ linkage within class

Question

Being new to C++, I have trouble understanding a linkage problem I'm having. The following is the file that's giving me a headache:

#pragma once

#include <string>
#include "finite_automaton.h"


template<typename RL>
class RegularLanguage {
public:
    bool empty();
    RegularLanguage<RL> minimize();
    RegularLanguage<RL> complement();
    RegularLanguage<RL> intersectionWith(RegularLanguage<RL> other);
    RegularLanguage<RL> unionWith(RegularLanguage<RL> other);
    RegularLanguage<RL> concatenate(RegularLanguage<RL> other);
    RegularLanguage<RL> kleeneStar();

    /*
     * Returns a regular expression that describes the language of this automaton.
     */
    std::string string();

    bool disjoint(RegularLanguage<RL> other) {
        return intersectionWith(other).empty();
    }

    bool containedIn(RegularLanguage<RL> super) {
        return intersectionWith(super.complement()).empty();
    }

    bool contains(RegularLanguage<RL> sub) {
        return complement().intersectionWith(sub).empty();
    }

    bool equals(RegularLanguage<RL> other) {
        return contains(other) && containedIn(other);
    }
};

When I compile the project, I get the following errors during the linking phase:

undefined reference to `RegularLanguage<FiniteAutomaton>::complement()'
undefined reference to `RegularLanguage<FiniteAutomaton>::intersectionWith(RegularLanguage<FiniteAutomaton>)'
undefined reference to `RegularLanguage<FiniteAutomaton>::empty()'

both for RegularLanguage<RL>::containedIn(..) and RegularLanguage<RL>::contains(..).

What am I doing wrong? I do get some related errors pertaining to the classes that implement this template class, but I left them out so as not to post unnecessarily much code.

Answer 1

So to summarize what you're trying to do, you have a class template:

template<typename RL> class RegularLanguage {...};

with some methods implemented and others only declared, but not implemented. Then you try to derive from this and in the derived class implement those other methods that weren't implemented in RegularLanguage:

class FiniteAutomaton : public RegularLanguage<FiniteAutomaton>

You seem to be conflating two concepts in C++: inheritance (specifically, polymorphism) and templates.

Your assumption was that by inheriting from RegularLanguage you can implement the missing stuff in the derived class. That's not how templates work, but polymorphism does work that way. You need to either:

1. Fully implement all methods in the class template RegularLanguage, and then derive FiniteAutomaton from that.
2. Make RegularLanguage an abstract base class -- not a class template -- with (possibly pure) virtual methods, and derive from that. The methods you want to be implemented in FiniteAutomaton can be. Those may or may not be pure. The methods you don't want to implement in the base class should be declared as pure (=0), and then implemented in the derived class.

It sounds to me like what you're really trying to do would be better accomplished with #2, so here's an incomplete example of how to do that:

class RegularLanguage {
public:
    virtual RegularLanguage* Clone() = 0;  // Creates a copy of this object
    virtual RegularLanguage& complement() = 0; // pure virtual must be implemented in derived class
    virtual bool containedIn(RegularLanguage& super) // non-pure, does not have to be implemented in derived
    {
        return intersectionWith(super.complement()).empty();
    }
  virtual ~RegularLanguage() {}
};

class FiniteAutomaton 
:
  public RegularLanguage
{
public:
  RegularLanguage* Clone()
  {
    RegularLanguage* clone = new FiniteAutomaton (*this);
    return clone;
  }

  RegularLanguage* complement()
  {
    RegularLanguage* comp = this->Clone();
    comp->SetSomeStuff();
    return comp;
  }
};

There are a number of details hidden up there that I haven't mentioned. For one, the return type of complement is now a RegularLanguage pointer, rather than a RegularLanguage by-value. This is required¹ in order to avoid the so-called Slicing Problem which would break polymorphism.

For another, I have abandoned the use of templates here because as I've implemented this, there is no apparent need for them. However the use of templates and polymorphism are not completely mutually exclusive. The base class could employ templates, and in fact the base class could be a class template and still be an abstract base class. But the derived class must derive from a concrete instantiation of that base class template. Things get somewhat complicated here. Just be careful that you're not seeing everything as a nail and get carried away with that hammer.

For another, I didn't implement a virtual destructor in the base class before (this is fixed now) but you must². Just remember this: if a class is intended to be derived from, it should have a virtual destructor in virtually every case.

For another, I've added a Clone method to the base class as a pure virtual. This was in response to the suggestion that complement() shouldn't return this instance of the object, but a new instance which is the complement of this instance. In a polymorphic hierarchy, when we make copies of object we almost always need to do so through the base class pointer, so a Clone() type method is usually present in such a design.

---

¹ "This is required [passing by pointer]: Actually, you could return a reference as well. Return a reference if you can, but here we need to return a pointer. (Actually we should be returning smart pointers, but that's a tangent.)

² "You must [implement a virtual destructor]: Technically, you need to have a virtual destructor if you intend to delete the object through a base class pointer. I have never in my professional career seen an instance where I could not or should not implement a virtual destructor in the base class of a polymorphic hierarchy. It's close to correct to say you should always do this, even if you have no plans to delete through a base class pointer.

Answer 2

You need to declare bool empty() (and others not implemented in the base) as a pure virtual in the base class:

virtual bool empty() = 0;

and then override/implement them in a descendant class like this:

virtual bool empty(){
    ...
}

Answer 3

There is a series of problems with this code. The most obvious one has been pointed out: you need your functions pure virtual. But that's just the beginning.

When you make your functions pure virtual, you will immediately notice that the code does not compile any more. The tools will tell you that you cannot instantiate an abstract class. The reason is that you return objects of type ReguarLanguage<...> from your functions by value, thereby invoking the Curse of Object Slicing (look it up). The inability to instantiate an abstract class is just manifestation of Object Slicing.

In order to dispel the dreaded curse, you will have to do the Rite of Return by Pointer, and thereby invoke the lesser curse of Manual Memory Management (this is relatively easily defeated with a bit of Smart Pointer Magic these days).

But you are not only returning languages, you are also accepting them as arguments. Here you need a simpler incantation of Passing by Reference, which does not require any manual memory management. It looks like in your case you can implement the intersection and all the other things by using just the public interface of the "other" argument, so this simple change should suffice.

Oh, and don't forget the virtual destructor. Never forget the virtual destructor... only omit it if you know you don't need it, which is, if your class fits the OO paradigm, never.

---

If you look at your RegularLanguage class template, you may notice that it never use its template parameter. If this is the case, it can be safely de-templatized. No, wait, it does use the parameter — how else could it create e.g. a complement?

To put it simply, if you have a finite automaton that parses a language, the parser of the complement doesn't have to be a finite automaton. It may contain or reference a FA (or something else!) instead. So you may want to have a subclass of RegularLanguage called Complement that will contain a (polymorphic!) reference to another RegularLanguage — without even having to know what kind of parser is hidden inside that one.