[Из песочницы] Унификация и поиск с возвратом на C#26.01.2015 17:49
Эта статья является ответом на статью «Задача Эйнштейна на Прологе». В ней автор пишет, что Пролог очень хорошо подходит для решения этой задачи и что суммарное количество строк почти совпадает с условиями задачи. Здесь я хочу показать, что на C# количество строк кода может быть примерно тем же. Я просто скопирую решение на Прологе и немного изменю синтаксис. Сначала приведу итоговый результат, а потом распишу функции. Вот что получилось:
public static IEnumerable 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 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 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 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 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 And (this IEnumerable source, IEnumerable 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 WriteLine (Func
