Есть обновленная версия этой статьи: http://wordsandbuttons.online/logic_programming_in_cpp.html

Логическое программирование, вероятно, является самой эзотерической парадигмой программирования из существующих. Все мы слышали об ООП и ФП, но LP? Разве она не певица?

Что ж, логическое программирование может быть вам ближе, чем вы думаете. Для LP существует семейство специальных языков, среди которых Prolog является самым популярным, но вам не обязательно изучать его, чтобы заниматься логическим программированием. Фактически, способ вывода типов компилятором почти такой же, как обратное отслеживание, которое Пролог использует для вывода данных. Мы можем использовать его, чтобы попробовать LP с C ++.

Так что, если вы хотите научиться логическому программированию на знакомом языке, вот ваш шанс!

Определения и аналогии

В Prolog есть условия для хранения данных, которые могут быть нескольких типов:

  • атом - любое слово или даже полное предложение. Например: x, alice или ‘year 2016’.
  • число - с плавающей запятой или целое число.
  • составной термин - сложный тип данных, состоящий из атомов и чисел. Сюда входят списки и строки.

Во время компиляции C ++ у нас есть классы, которые мы можем использовать как атомы.

В Prolog вы строите отношения между данными с помощью правил и фактов. Если вы хотите сказать, что «Алисе нравится Боб», Алиса и Боб - данные, а лайки - отношение. В Prolog это можно сделать так:

likes(alice, bob).

Это называется факт. А правило - это просто факт с условиями. Допустим, Алисе нравится не обязательно Боб, а все, кто добр, умен и пишет на C ++. Что в Прологе будет:

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

Person - это переменная Пролога. Переменные всегда начинаются с заглавной буквы и оцениваются в любой термин, который соответствует набору условий.

Логическое программирование - это дедукция. У вас есть набор терминов, известных фактов и правил. Тогда вы хотите узнать то, чего раньше не знали. Например, если мы хотим знать, нравится ли Алисе Боб в соответствии с ее правилом, приведенным выше, мы должны познакомить Боба с набором фактов, а затем спросить Пролог следующим образом:

?- likes(alice, bob).

Итак, учитывая следующий набор фактов, нравится Алисе Боб или нет?

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

Да, она делает. Боб добрый, умный и пишет на C ++, поэтому он естественно нравится Алисе. Теперь давайте докажем это с помощью компилятора C ++!

Мы будем использовать классы как атомы, функции как факты и шаблонную функцию как правило. Если компилятор правильно выводит все типы, то правило верно.

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

Он компилируется, поэтому Алисе нравится Боб!

Однако он не связан, потому что ни одна из функций / фактов не определена. Но поскольку мы все равно не хотим запускать время выполнения, это скорее привилегия, чем недостаток. Получаем приятную заметку от компоновщика:

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

И теперь мы можем видеть, какие типы вычтены по тому или иному факту.

Проблема раскраски карты

Задача раскраски карты особенно привлекательна для иллюстрации логического программирования из-за ее символического значения. Самой первой теоремой, полностью доказанной компьютером, была Теорема четырех цветов. Это фактически доказывает, что каждую планарную карту можно раскрасить не более чем в 4 цвета.

Но сначала это не понравилось. Полное доказательство состояло из « 50 страниц, содержащих текст и диаграммы, 85 страниц, заполненных почти 2500 дополнительными диаграммами, и 400 страниц микрофиш, содержащих дополнительные диаграммы и тысячи отдельных проверок утверждений, сделанных в 24 леммах в основной раздел текста ”, и на тот момент единственным способом проверить все это была ручная проверка, которая сама по себе чревата ошибками.

Так действительно ли доказательство, которое мы не можем проверить, является доказательством?

Что ж, нам не нужно доказывать общую теорему с помощью C ++, мы просто хотим найти схему раскраски.

Я позаимствовал эту идею у Бернардо Пиреса. Если вас заинтересовал Пролог и логическое программирование, обязательно прочтите его статью. Он использует Пролог для раскрашивания карты Германии в четыре цвета. Мы бы попробовали сделать то же самое с C ++ и картой Украины.

Сначала нам нужно определить цвета.

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

Теперь, поскольку мы хотим, чтобы компилятор выводил цвета для нас, мы должны дать ему класс, выводимый в любой цвет.

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

В Prolog есть оператор для объявления неравенства данных. Поэтому, когда Бернардо хочет объявить правило, согласно которому все соседние государства должны иметь разные цвета, он просто пишет это:

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

У нас нет такой роскоши в C ++, хотя мы можем придумать несколько способов ее подражания. Самый грубый способ - объявить связь между каждой парой неравных цветов.

// 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
template <typename Region1Color, typename Region2Color>
void neighbor(Region1Color, Region2Color)
{
    color(Region1Color());
    color(Region2Color());
    different(Region1Color(), Region2Color());
}

Запрограммируем карту Украины, как правило, состоящую из всех neighbor правил. Каждый раз, когда регион граничит с другим регионом, будет правило. Остерегайтесь стены кода!

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

Теперь возбудимый момент. Будет ли он компилироваться при вызове со всеми AnyColor() параметрами?

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

No.

Нет однозначной окраски карты. По крайней мере, мы можем менять цвета местами взаимозаменяемо, ведь Green или White - это всего лишь имена классов, поэтому нет причин для того, чтобы какая-либо область имела какой-либо определенный цвет. Единого решения нет, но компилятор его не находит.

Дело в том, что хотя компилятор C ++ и Prolog имеют некоторые общие черты, они все же принципиально отличаются. Пролог с возвратом фактически останавливается, когда он может выводить значения, а компилятор - нет. Он не будет компилироваться, если не будет одного и только одного возможного вывода. На практике это означает, что Пролог допускает двусмысленность, а компилятор - нет.

Мы можем сделать это на Прологе:

color(blue).
color(yellow).
color(while).
color(green).
:- color(Which), write(Which).
blue

Но в C ++ мы не можем вывести color(AnyColor()).

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

И это хорошо. Последнее, что нам нужно, - это неоднозначная компиляция.

Заключение

Прошу прощения, если это заставляет вас чувствовать себя немного обманутым. Сначала я обещаю вам логическое программирование, не покидая известного окружения, а потом оно просто кажется фундаментально ограниченным. Я старался быть честным во всех аспектах: вы можете заниматься логическим программированием во время компиляции, но вам все равно нужно изучить Prolog или что-то подобное, чтобы иметь реальный опыт работы с парадигмой.

Но мы можем извлечь урок из этого опыта.

  1. Во-первых, в логическом программировании или даже в декларативном программировании в целом нет ничего волшебного. В каком-то смысле мы делали это целую вечность с помощью классов и шаблонов.
  2. Во-вторых, компилятор действительно работает как доказывающий, так что компилируемая программа должна удовлетворять всем отношениям между типами. Сторонники статической типизации считают это преимуществом, но также и недостатком тех, кто предпочитает динамическую типизацию. Потому что и то, и другое. В то время как значимые отношения действительно делают вашу программу более устойчивой к дефектам, неправильные и бесполезные только создают когнитивные издержки.
  3. Говоря о накладных расходах, поскольку компилятор C ++ на самом деле выполняет больше работы, чем Prolog, теперь вы можете понять, почему требуется так много времени для компиляции кода с полным шаблоном и множеством взаимосвязей типов.

В заключение, если вы хотите продолжить логическое программирование, я все же советую вам изучить Пролог. И если вы хотите продолжить изучение C ++, я бы посоветовал вам выучить еще больше языков.

Хакерский полдень - это то, с чего хакеры начинают свои дни. Мы часть семьи @AMI. Сейчас мы принимаем заявки и рады обсуждать рекламные и спонсорские возможности.

Если вам понравился этот рассказ, мы рекомендуем прочитать наши Последние технические истории и Современные технические истории. До следующего раза не воспринимайте реалии мира как должное!