Унификация и поиск с возвратом на C#

Эта статья является ответом на статью «Задача Эйнштейна на Прологе». В ней автор пишет, что Пролог очень хорошо подходит для решения этой задачи и что суммарное количество строк почти совпадает с условиями задачи. Здесь я хочу показать, что на C# количество строк кода может быть примерно тем же. Я просто скопирую решение на Прологе и немного изменю синтаксис. Сначала приведу итоговый результат, а потом распишу функции. Вот что получилось:

public static IEnumerable<bool> Einstein(object houses)
{
    return
        /* 0. Всего 5 домов */
        YP.unify(houses, List(_, _, _, _, _))
        /* 1. Норвежец живёт в первом доме. */
        .And(Nth1(1, houses, List("norwegian", _, _, _, _)))
        /* 2. Англичанин живёт в красном доме. */
        .And(Member(List("englishman", _, _, _, "red"), houses))
        /* 3. Зелёный дом находится слева от белого, рядом с ним. */
        .And(Nextto(List(_, _, _, _, "green"), List(_, _, _, _, "white"), houses))
        /* 4. Датчанин пьёт чай. */
        .And(Member(List("dane", _, _, "tea", _), houses))
        /* 5. Тот, кто курит Marlboro, живёт рядом с тем, кто выращивает кошек. */
        .And(Neighbors(List(_, _, "marlboro", _, _), List(_, "cat", _, _, _), houses))
        /* 6. Тот, кто живёт в жёлтом доме, курит Dunhill. */
        .And(Member(List(_, _, "dunhill", _, "yellow"), houses))
        /* 7. Немец курит Rothmans. */
        .And(Member(List("german", _, "rothmans", _, _), houses))
        /* 8. Тот, кто живёт в центре, пьёт молоко. */
        .And(Nth1(3, houses, List(_, _, _, "milk", _)))
        /* 9. Сосед того, кто курит Marlboro, пьёт воду. */
        .And(Neighbors(List(_, _, "marlboro", _, _), List(_, _, _, "water", _), houses))
        /* 10. Тот, кто курит Pall Mall, выращивает птиц. */
        .And(Member(List(_, "bird", "pallmall", _, _), houses))
        /* 11. Швед выращивает собак. */
        .And(Member(List("swede", "dog", _, _, _), houses))
        /* 12. Норвежец живёт рядом с синим домом. */
        .And(Neighbors(List("norwegian", _, _, _, _), List(_, _, _, _, "blue"), houses))
        /* 13. Тот, кто выращивает лошадей, живёт в синем доме. */
        .And(Member(List(_, "horse", _, _, "blue"), houses))
        /* 14. Тот, кто курит Winfield, пьет пиво. */
        .And(Member(List(_, _, "winfield", "beer", _), houses))
        /* 15. В зелёном доме пьют кофе. */
        .And(Member(List(_, _, _, "coffee", "green"), houses));
}

И сам запрос решения:

var houses = new Variable();
var owner = new Variable();
Einstein(houses)
    // У кого рыба?
    .And(Member(List(owner, "fish", _, _, _), houses))
    // Выводим владельца рыбы.
    .And(WriteLine(() => owner))
    // Выводим полное решение.
    .And(WriteLine(() => houses))
    .Count();

Результат работы программы:
german
((norwegian, cat, dunhill, water, yellow), (dane, horse, marlboro, tea, blue), (englishman, bird, pallmall, milk, red), (german, fish, rothmans, coffee, green), (swede, dog, winfield, beer, white))

Количество строк кода примерно тоже, что и в решении на Прологе.

Что же происходит под капотом? В данном решении я воспользовался библиотекой YieldProlog, которая позволяет производить унификацию параметров и поиск с возвратом. Здесь не происходит какой-либо промежуточной компиляции Пролог программы. Это честное решение на C#.

Унификация параметров происходит с помощью функции YP.unify(arg1, arg2). Это основная функция, можно сказать, ядро всего решения. Реализация достаточно простая, но лучше, чем про нее написано в документации, я все равно не напишу. А сама документация небольшая. Поэтому отсылаю к ней.

Первой строкой решения как раз и происходит связывание переменной houses со списком несвязанных переменных. Для задания списков будем использовать функтор с пятью аргументами, так как в нашей задаче все списки состоят только из пяти элементов. Вот код метода List:

public static object List(params object[] list)
{
    return Functor.make("", list);
}

Здесь Functor – это класс из библиотеки YieldProlog.

Теперь вместо длинной записи Functor.make(new [] {new Variable(), new Variable(), …}) я могу использовать более короткую List(new Variable(), new Variable(), …). А чтобы создание списка выглядело более элегантно добавил свойство:

public static Variable _ { get { return new Variable(); } }

Тогда список не унифицированных переменных будет записываться так: List(_, _, …).

Далее опишу предикаты member(Elem, List), nth1(N, List, Elem), nextto(X, Y, List) и neighbors(X, Y, List). Я специально не стал использовать списки вида [head | tail], а использую обычные массивы, так как у меня нет задачи повторить описание данных предикатов аналогично их описанию на Прологе.

member(Elem, List) будет выглядеть так:

public static IEnumerable<bool> Member(object elem, object list)
{
    foreach (var e in YP.getFunctorArgs(list))
        foreach (var l1 in YP.unify(elem, e))
            yield return false;
}

Здесь все очень просто. В цикле перебираем элементы списка и каждый элемент унифицируем с элементом списка.

Конструкция:

foreach (var l1 in YP.unify(elem, e))
    yield return false;

служит для унификации двух переменных.

nth1(N, List, Elem) превратится в:

public static IEnumerable<bool> Nth1(object n, object list, object elem)
{
    int i = 0;
    foreach (var e in YP.getFunctorArgs(list))
    {
        i++;
        foreach (var l1 in YP.unify(elem, e))
            foreach (var l2 in YP.unify(i, n))
                yield return false;
    }
}

Здесь мы так же перебираем каждый элемент списка и для каждого элемента проводим его унификацию с параметром elem. Если же параметр у нас уже связан с каким-то значением и это значением совпадает со значением какого-то элемента списка, то проводим унификацию номера этого элемента в списке с параметром n.

nextto(X, Y, List) запишем так:

public static IEnumerable<bool> Nextto(object x, object y, object list)
{
    var nativeList = YP.getFunctorArgs(list);
    var e1 = nativeList.FirstOrDefault();
    foreach (var e2 in nativeList.Skip(1))
    {
        foreach(var l1 in YP.unify(x, e1))
            foreach(var l2 in YP.unify(y, e2))
                yield return false;
        e1 = e2;
    }
}

Перебираем уже не по одному элементу, а по два и проводим унификацию двух соседних элементов списка с параметрами x и y.

neighbors(X, Y, List) реализуем точно так же как в решении на Прологе:
public static IEnumerable<bool> Neighbors(object x, object y, object list)
{
    foreach (var l1 in Nextto(x, y, list))
        yield return false;
    foreach (var l1 in Nextto(y, x, list))
        yield return false;
}

Использование итераторов — очень важная часть решения. Они как раз и позволяют делать поиск с возвратом. Если унификация двух переменных успешна, происходит следующий шаг итерации и переход к вложенному циклу, если такой есть. Если унификация не успешна, происходит прерывание данного цикла и переход к следующей итерации внешнего цикла.

В решении данной задачи идут подряд 15 предикатов. В YieldProlog для этого придется записать 15 вложенных циклов:

foreach (var l1 in Pred1(...))
  foreach (var l2 in Pred2(...))
    …
    foreach (var l15 in Pred15(...))
      yield return false;

Это неудобно и некрасиво. Поэтому добавим вспомогательный метод And, который выстраивает цепочки предикатов:

public static IEnumerable<bool> And(this IEnumerable<bool> source, IEnumerable<bool> inner)
{
    foreach (bool l1 in source)
        foreach (bool l2 in inner)
            yield return false;
}

Это всё. Можно вызывать функцию Einstein:

var houses = new Variable();
Einstein(houses);

И, ничего не происходит. А все потому, что мы просто построили итератор с помощью yield, но не создали цикл итерации. Можно его создать явно:

foreach (var l1 in Einstein(houses))
    Console.WriteLine(houses);

А можно просто вызвать метод Count, который пройдет по итератору и подсчитает количество итераций.

Кроме того, до того, как запустить наш итератор, мы можем к нашему решению добавлять новые условия:

Einstein(houses)
    // У кого рыба?
    .And(Member(List(owner, "fish", _, _, _), houses))
    // Выводим владельца рыбы.
    .And(WriteLine(() => owner))
    // Выводим полное решение.
    .And(WriteLine(() => houses))
    .Count();

Вспомогательная функция WriteLine:

public static IEnumerable<bool> WriteLine(Func<object> s)
{
    Console.WriteLine(s());
    yield return false;
}

Вместо резюме


Данная статья возникла с вопроса, каким образом в C# можно было бы легко описывать логические задачи. И здесь я привел один из способов. У меня не было цели получить оптимальное решение по производительность или объему памяти. Существуют библиотеки, которые позволяют писать программы на Прологе, компилировать их и подключать в виде библиотек к своему проекту. Мне же захотелось получить решение встроенными средствами C#. Поискав по интернету, нашел библиотеку YieldProlog, которая и решает эту задачу. То есть, я могу описывать логические задачи на привычном мне языке, используя привычный синтаксис. При этом описываю задачу аналогично описанию на Прологе. Да еще и есть возможность использовать типы и возможности C#. Да еще и с возможностью оптимизировать решение по мере необходимости.

Если кому-то интересно, то время работы программы на моем стареньком ноутбуке AMD Turion 1.8ГГц выполняется за 0.1 сек.
Поделиться публикацией

Комментарии 11

    +3
    А почему не F#? Мне кажется, он бы лучше подошел для решения это задачи и тоже .NET.
      0
      Всем и так понятно, что на F# это сделать так же легко, как и на прологе. По-моему, цель статьи — именно показать, что и C# им не уступит, вопреки распространенному мнению.
        0
        Ну понятно, что благодаря библиотекам, LINQ и прочему синтаксчическому сахару в C# можно сделать практически все, что угодно. В качестве теоретического эксперимента — занятно.
          0
          Это как раз не всегда понятно.
          И да, это просто эксперимент, развлечение на досуге.
          0
          Мне не понятно. В F# есть встроенное средство для проверки доказательств / решения системы утверждений, или вы имеете в виду, что для него просто есть библиотека с удобным синтаксисом?
          0
          К сожалению, F# не знаю. Но, если приведете решение этой задачи на F#, будет любопытно посмотреть. Вообще, интересно смотреть решение одной и той же задачи на разных языках или даже одном языке, но разные подходы.
            0
            Вы сделали мне вызов и это хорошо, попытаюсь :)
              0
              После недолгого гугления я обнаружил следующее решение (по английски эта задача называется Zebra Puzzle): gist.github.com/henrik-ch/3751106
              Пусть оно может и не такое красивое как у вас, однако тоже лаконичное.
            +2
            По сути получается, что в шарпе с помощью библиотеки, реализующий основные пролог функции, программа, написанная на прологе, использующая основные функции, выглядит так же, как и в прологе? Ну допустим, но что из этого следует? На шарпе можно добиться того же результата? Да, конечно, это же тьюринг-полный язык, а как мы помним тезис тьюринга-черча, это значит что на нем мы можем посчитать что душе угодно. С тем же успехом можно взять ассемблер и брейнфак, можно даже с помощью макросов получить что-то похожее. Значит ли это, что этот язык подходит для реализации задачи? Не думаю.

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

            Но в любом случае, спасибо за статью. Я не согласен лишь в выводом, что если примотать кирпич к отвертке — то получится сносный молоток. Каждой задаче — свой инструмент. There is no silver bullet, Neo.
              0
              Так ведь библиотека и является инструментом. Который подходит для решения данной задачи. Я знаю C# и если вижу какую-то интересную задачу, то первым делом пытаюсь ее решить именно на этом языке. И я сделаю это гораздо быстрее и эффективнее, чем на более подходящем для этой задачи языке, но который я не знаю. Хотя специалист по тому языку, возможно, сделает на нем более эффективное решение. Зависит от цели — решить задачу или решить ее наиболее оптимально по какому-то критерию. Я даже числодробилки пишу на C#, хотя C для этого лучше подходит. Потому что это доставляет мне больше удовольствия, хотя код может получиться процентов на пятьдесят медленнее.
                0
                Есть хорошая поговорка: «Когда у тебя в руках молоток, все кажется гвоздями», или в оригинале:

                image

                Поэтому задача хорошего программиста — уметь пользоваться несколькими инструментами (или хотя бы хорошо знать об их существовании), чтобы выбрать нужный. И знать не в смысле «окей, я знаю, на С это выглядело бы примерно так», а знать в смысле понимать идеологию языка.

                В моем случае изучение лиспа и F# позволило намного шире и эффективнее использовать лямбды в шарпе, а знание работы ассемблера и устройство памяти позволило писать cache-obvious алгоритмы, которые выполняются в разы быстрее просто от организации блочного прохода по массиву.

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

            Самое читаемое