Try logic programming with C++ compiler

There is a renovated version of this article: http://wordsandbuttons.online/logic_programming_in_cpp.html

Logic programming is probably the most esoteric programming paradigm there is. We have all heard about OOP and FP, but LP? Isn’t she a singer?

Well, logic programming might be closer to you than you think. There is a family of dedicated languages for LP, among which Prolog is the most popular, but you don’t necessary have to learn it to do logical programming. In fact, the way compiler deduce types is almost the same backtracking Prolog uses to deduce data. We can exploit it to try LP with C++.

So if you want to learn some logic programming in a familiar language, here is your chance!

Definitions and analogies

In Prolog you have terms to store data, which can be of several types:

• atom — basically any word or even a full sentence. Like: x, alice, or ‘year 2016’.
• number — floating point or integer.
• compound term — complex data type constructed of atoms and numbers. This includes lists and strings.

In C++ compile time we have classes we can use as atoms.

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

likes(alice, bob).

This is called a fact. And the rule is just a fact with conditions. Let’s say Alice likes not necessary Bob, but everyone who is kind and intelligent and writes in C++. Which in Prolog would be:

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

A Person is a Prolog variable. Variables always start with a capital letter and they evaluate into any term that fits the set of 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 knew before. For instance, if we want 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).

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).

Just screening the answer with giant Prolog shell prompt.

Yes she does. Bob is kind, intelligent and writes in C++ so Alice naturally likes him. Now let’s prove this with C++ compiler!

We’ll use classes as atoms, functions as facts and template function as a rule. If compiler gets to deduce all the types right, then the rule is true.

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

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

// factsvoid 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);

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

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

It compiles therefore Alice likes Bob!

It doesn’t link though because none of the functions/facts are defined. But since we don’t want to get to run time anyway, it’s more a perk than a flaw. We get a nice note from the linker:

example.o: In function `main':...: undefined reference to `kind(Bob)'...: undefined reference to `intelligent(Bob)'...: undefined reference to `writes(Bob, Cpp)'clang: error: linker command failed with exit code 1

And now we can see what types are deducted for which fact.

The map coloring problem

Map coloring problem is particularly appealing for illustrating logical programming because of its symbolical meaning. The very first theorem proven entirely by the computer was The Four Color Theorem. It actually proves that every planar map can be colored with no more than 4 colors.

But it wasn’t accepted well at the beginning. The full proof consisted of “50 pages containing text and diagrams, 85 pages filled with almost 2500 additional diagrams, and 400 microfiche pages that contain further diagrams and thousands of individual verifications of claims made in the 24 lemmas in the main section of the text”, and the only way to verify it all at the time was manual validation, which is error prone by itself.

So is the proof we can’t verify really a proof?

Well, we don’t have to prove the general theorem with C++, we only want to find a coloring scheme.

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

By Albedo-ukr (Image:Ukraine-Historical regions .svg) [CC BY-SA 2.5 (http://creativecommons.org/licenses/by-sa/2.5)], via Wikimedia Commons

At first we would have to define colors.

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

Now since we want compiler to deduce colors for us, we have to give it a class deducible into any color.

// class for color deductionclass AnyColor : public Yellow, Blue, White, Green {};

Prolog has an operator to declare data inequality. So when Bernardo wants to declare a rule that says that every neighboring states should have different colors, he simply writes this:

neighbor(StateAColor, StateBColor) :- color(StateAColor),color(StateBColor),StateAColor \= StateBColor. /* \= is the not equal operator */

We don’t have this luxury in C++, although we can think out several ways to emulate it. The most brute way would be to declare relationship between every pair of not equal colors.

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

Neighborhood rule will then look like this:

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

Let’s program the map of Ukraine as a rule consisting of all neighbor rules. Every time a region shares a border with another region, there will be a rule. Beware the wall of code!

// map: neighborhood of regionstemplate <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);}

Now the excitable moment. Would it compile when called with all AnyColor() parameters?

// try to color map of Ukraineint 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());}

Once again screening the answer.

No.

There is no disambiguate coloring for a map. For the very least we can swap colors interchangeably, after all Green or White are only class names, so there’s no reason for any region to be of any particular color. There is no single solution but compiler fails to find any.

The thing is, while C++ compiler and Prolog do have some things in common, they are still fundamentally different. Prolog with backtracking actually stops when it can deduce values, while compiler don’t. It wouldn’t compile unless there is one and only one possible deduction. In practice this means that Prolog is ok with ambiguity, while compiler is not.

We can do this in Prolog:

color(blue).color(yellow).color(while).color(green).

:- color(Which), write(Which).blue

But in C++ we can’t deduce color(AnyColor()).

source_file.cpp:82:5: error: call to 'color' is ambiguouscolor(AnyColor());^~~~~source_file.cpp:6:6: note: candidate functionvoid color(Yellow);^source_file.cpp:7:6: note: candidate functionvoid color(Blue);^source_file.cpp:8:6: note: candidate functionvoid color(White);^source_file.cpp:9:6: note: candidate functionvoid color(Green);^1 error generated.

Which is good. The last thing we need is an ambiguate compilation.

Conclusion

I’m sorry if this makes you feel a bit deceived. At first I promise you logical programming without leaving the known environment, and then it just appears to be fundamentally limited. I was trying to be honest in every part though: you can do some logic programming in compile time, but you still have to learn Prolog or alike to have some real experience with the paradigm.

But we can extract a lesson from this experience.

1. First of all, there’s nothing magical about logical programming, or even declarative programming at a whole. In a way we have been doing this for ages with classes and templates.
2. Second, the compiler indeed works as a prover in a way that compilable program has to suffice all the relationships between types. Which is seen as an advantage by static typing proponents, but also as a disadvantage by those who prefer dynamic typing. Because it is both. While meaningful relationships indeed make your program more defect-proof, wrong and unhelpful ones only introduce cognitive overhead.
3. Speaking of overhead, since C++ compiler actually does more work than Prolog, you can now realize why it takes it so long to compile template-full code with lots of type relationships.

In conclusion, if you want to go on with logical programming, I would still advice you to learn Prolog. And if you want to go on with C++, I would advice you to learn even more languages.