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, might be closer to you than you think. There is a family of dedicated languages for LP, among which 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 Prolog uses to deduce data. We can exploit it to try LP with C++. logic programming Prolog backtracking So if you want to learn some logic programming in a familiar language, here is your chance! Definitions and analogies In Prolog you have to store data, which can be of several types: terms — basically any word or even a full sentence. Like: , , or . atom x alice ‘year 2016’ — floating point or integer. number — complex data type constructed of atoms and numbers. This includes lists and strings. compound term In C++ compile time we have classes we can use as atoms. In Prolog you build relations between data with and . When you want to say that “ ”, and are data and is a relation. In Prolog you can set it like this: rules facts Alice likes Bob Alice Bob likes ( , ). likes alice bob This is called a . And the 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: fact rule ( , Person) :- (Person), (Person), (Person, ). likes alice kind intelligent writes cpp A is a Prolog variable. Variables always start with a capital letter and they evaluate into any term that fits the set of conditions. Person 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 as , as and as a . If compiler gets to deduce all the types right, then the rule is true. classes atoms functions facts template function rule class Alice{};class Bob{};class George{};class Steven{}; // people class Cpp{};class Prolog{};class Assembly{}; // languages 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); // facts template <typename Person> void likes(Alice, Person person){kind(person);intelligent(person);writes(person, Cpp());} // rule int main(){likes(Alice(), Bob());} // check the rule for 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 ` ( )'...: undefined reference to ` ( )'...: undefined reference to ` ( , )'clang: error: linker command failed with exit code 1 kind Bob intelligent Bob writes Bob Cpp 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 “ ”, and the only way to verify it all at the time was manual validation, which is error prone by itself. 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 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 . 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. his article By Albedo-ukr (Image:Ukraine-Historical regions .svg) [CC BY-SA 2.5 ( )], via Wikimedia Commons http://creativecommons.org/licenses/by-sa/2.5 At first we would have to define colors. class Yellow{};class Blue{};class White{};class Green{};void color(Yellow);void color(Blue);void color(White);void color(Green); // colors Now since we want compiler to deduce colors for us, we have to give it a class deducible into any color. class AnyColor : public Yellow, Blue, White, Green {}; // class for color deduction 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. 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); // color inequality (instead of \= orerator) Neighborhood rule will then look like this: template <typename , typename >void neighbor( , ){color( ());color( ());different( (), ());} // neighborhood Region1Color Region2Color Region1Color Region2Color Region1Color Region2Color Region1Color Region2Color Let’s program the map of Ukraine as a rule consisting of all rules. Every time a region shares a border with another region, there will be a rule. Beware the wall of code! neighbor 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);} // map: neighborhood of regions Now the excitable moment. Would it compile when called with all parameters? AnyColor() 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());} // try to color map of Ukraine 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 or 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. Green White 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. 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. 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. 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 . And if you want to go on with C++, I would advice you to languages. Prolog learn even more
