Logic programming in C++

It is well known that C++ is a multi-paradigm programming language. It combines procedural, functional, object-oriented, and generic programming features in an arsenal of things to shoot your foot with.

A little less known that it also employs logic programming paradigm. It doesn't expose its features directly, yet understanding the paradigm while not enriching your arsenal per se makes you much less prone to metaphorical self-injuries.

What's logic programming?

Logic programming is about making the computer deduce facts for you. You write down the things you know, write down the rules that hold true for these things, and then you ask the question. Like, “who killed John F. Kennedy”?

Of course, the computer can only work with the facts you provide. It doesn't do surveillance or interrogation for you. It doesn't have the intuition. But it does the deduction fast and robust, that's all we can expect from the machine.

The most popular logic programming language now is Prolog. It was invented in France, and its name stands for “programmation en logique”, which is in itself quite logical.

Let's take a quick tour in Prolog to see what we can learn from it.

In Prolog you have terms to store data. Terms are:

You build relations between data with rules and facts. When you want to say that “Alice likes Bob”, Alice and Bob are the data and likes is the relation. In Prolog, you can write it down like this. 

likes(alice, bob).

Such relations are called facts in Prolog. There are also rules which are conditional facts. Let’s say Alice likes someone who is kind, and intelligent and writes in C++. The rule for that would be: 

likes(alice, Person) :-
  kind(Person),
  intelligent(Person),
  writes(Person, cpp).

The Person is a Prolog variable. Syntaxically, variables always begin with a capital letter. Semantically, they can denote any term that fits the conditions.

Logic programming is all about deduction. You have a set of terms, known facts, and rules. Then you want to know something you didn’t know before. For instance, if we're going to know if Alice likes Bob according to her rule above, we have to introduce Bob with a set of facts and then ask Prolog like this: 

?- likes(alice, bob).

Prolog programming is declarative. This means that we only have to give it rules and facts, but not the way the facts and rules should be checked. Prolog finds the way for us.

So, given the following set of facts, does Alice like Bob or not? 

kind(bob).
kind(george).
kind(steven).
intelligent(bob).
intelligent(steven).
writes(bob, cpp).
writes(bob, assembly).
writes(george, cpp).
writes(steven, prolog). 

likes(alice, Person) :-
  kind(Person),
  intelligent(Person),
  writes(Person, cpp).
  
?- likes(alice, bob).

Analogies in C++

C++ doesn't have logic deduction as a language feature. But it has something similar. It has type deduction which is very close conceptually. Now let's translate our Prolog program into C++.

Classes will be our atoms.

Polymorphic functions will be our facts.

And a template function will be our rule. 

// people
class Alice{};
class Bob{};
class George{};
class Steven{};

// languages
class Cpp{};
class Prolog{};
class Assembly{};

// facts
void kind(Bob);
void kind(George);
void kind(Steven);
void intelligent(Bob);
void intelligent(Steven);
void writes(Bob, Cpp);
void writes(Bob, Assembly);
void writes(George, Cpp);
void writes(Steven, Prolog);

// the rule
template <typename Person> void likes(Alice, Person person)
{
    kind(person);
    intelligent(person);
    writes(person, Cpp());
}

// check the rule for Bob
int main()
{
    likes(Alice(), Bob());
}

Type deduction is not entirely the same as logic programming, but in many regards, it works the same. The program compiles only if the compiler deduces all the types correctly. The very fact of compilation is the answer to our question.

So does Alice like Bob in C++?

Logic programming v.s. type deduction

While being similar, type deduction differs from logic programming in one crucial way. I guess it would be best to illustrate it with the example.

I stole this idea from Bernardo Pires. If you got interested in Prolog and logic programming in general, please read his article. He uses Prolog to color map of Germany in four colors. We will try to do the same with C++ and the map of Ukraine.

By Albedo-ukr [CC BY-SA 2.5], via Wikimedia Commons

At first, we would have to define colors. 

// colors
class Yellow{};
class Blue{};
class White{};
class Green{};
void color(Yellow);
void color(Blue);
void color(White);
void color(Green);

We need to generalize them to use in our rules, and that's one possible way to do that. 

// AnyColor object can be Yellow, Blue, White or Green
class AnyColor : public Yellow, Blue, White, Green {};

Unlike C++, Prolog has an operator to declare data inequality. So when Bernardo wants to declare a rule stating that all the neighboring regions should have different colors, he writes this: 

neighbor(StateAColor, StateBColor) :- color(StateAColor), 
    color(StateBColor), 
    StateAColor \= StateBColor.

We can do the same in modern C++, but it gets needlessly tricky, so we'll define inequality as a simple set of facts instead. 

// color inequality (instead of \= orerator)
void different(Yellow, Blue);
void different(Yellow, White);
void different(Yellow, Green);
void different(Blue, Yellow);
void different(Blue, White);
void different(Blue, Green);
void different(White, Yellow);
void different(White, Blue);
void different(White, Green);
void different(Green, Yellow);
void different(Green, Blue);
void different(Green, White);

Next, we want every two adjacent regions to have different colors. Here's a rule for that. 

// neighborhood rule
template <typename Region1Color, typename Region2Color>
void neighbor(Region1Color, Region2Color)
{
    color(Region1Color());
    color(Region2Color());
    different(Region1Color(), Region2Color());
}

Now we have to program the map of Ukraine as pairs of adjacent regions. 

// map: neighborhood of regions
template <typename ZK, typename LV, typename IF, 
          typename VL, typename CZ, typename TP, 
          typename RV, typename KM, typename ZH, 
          typename VN, typename OD, typename KV, 
          typename CK, typename CH, typename MK, 
          typename KR, typename PT, typename KS, 
          typename SM, typename DR, typename CR, 
          typename ZP, typename KH, typename DN,
          typename LH>
void ukraine(ZK zk, LV lv, IF iv, VL vl, CZ cz, TP tp, 
             RV rv, KM km, ZH zh, VN vn, OD od, KV kv, 
             CK ck, CH ch, MK mk, KR kr, PT pt, KS ks, 
             SM sm, DR dr, CR cr, ZP zp, KH kh, DN dn, 
             LH lh)
{
    neighbor(zk, lv); neighbor(zk, iv); neighbor(lv, vl);
    neighbor(lv, rv); neighbor(lv, tp); neighbor(lv, iv);
    neighbor(iv, tp); neighbor(iv, cz); neighbor(vl, rv);
    neighbor(tp, rv); neighbor(tp, km); neighbor(tp, cz);
    neighbor(cz, km); neighbor(cz, vn); neighbor(rv, km);
    neighbor(rv, zh); neighbor(km, zh); neighbor(km, vn);
    neighbor(zh, kv); neighbor(zh, vn); neighbor(vn, kv);
    neighbor(vn, ck); neighbor(vn, kr); neighbor(vn, od);
    neighbor(od, kr); neighbor(od, mk); neighbor(kv, ch);
    neighbor(kv, pt); neighbor(kv, ck); neighbor(ck, pt);
    neighbor(ck, kr); neighbor(ch, sm); neighbor(ch, pt);
    neighbor(mk, kr); neighbor(mk, dr); neighbor(mk, ks);
    neighbor(kr, pt); neighbor(kr, dr); neighbor(pt, sm);
    neighbor(pt, kh); neighbor(pt, dr); neighbor(sm, kh);
    neighbor(ks, cr); neighbor(ks, zp); neighbor(dr, kh);
    neighbor(dr, dn); neighbor(dr, zp); neighbor(zp, dn);
    neighbor(kh, lh); neighbor(kh, dn); neighbor(dn, lh);
}

And finally, we write the function that starts type deduction for every region. 

// try to color map of Ukraine
int main()
{
    ukraine(AnyColor(),AnyColor(),AnyColor(),AnyColor(),
            AnyColor(),AnyColor(),AnyColor(),AnyColor(),
            AnyColor(),AnyColor(),AnyColor(),AnyColor(),
            AnyColor(),AnyColor(),AnyColor(),AnyColor(),
            AnyColor(),AnyColor(),AnyColor(),AnyColor(),
            AnyColor(),AnyColor(),AnyColor(),AnyColor(),
            AnyColor());
}

Given that there are no typos and we wrote down all our rules and facts correctly, will this program compile or not?

Conclusion

When you write in C++ you actually write in two languages at once. First is C++, and the second one is invisible Prolog.

If written properly, the second program is ultimately helpful. If you build your type relations right, every compilation will reassure you that your expectations about the entity relations are also correct. Type deduction will work just as the logic deduction. Pragmatically, this means fewer bugs and fewer surprises in general.

However, if being neglected, it turns your code into an untangleable mess of incomprehencibles really-really fast. Every new rule not only adds to the complexity, it multiplies it, so the complexity tends to grow in geometric proportion. The other problem with the compile time programming is that it doesn't have a debugger, and the error messages for templates are notoriously bad. Not only it gets ugly fast, but it is very hard to make it right again.

And that's why acknowledging the invisible language is even more important than mastering the visible one.

 ← there's more. + Github & Twitter & Hacker News