Unification and search with return on C #

This article is a response to the article “The Einstein Problem on the Prologue” . In it, the author writes that Prolog is very well suited for solving this problem and that the total number of lines almost coincides with the conditions of the problem. Here I want to show that in C # the number of lines of code can be about the same. I'll just copy the solution on Prolog and change the syntax a bit. First I will give the final result, and then I will write out the functions. Here's what happened:

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

And the solution itself:

 var houses = new Variable(); var owner = new Variable(); Einstein(houses) //   ? .And(Member(List(owner, "fish", _, _, _), houses)) //   . .And(WriteLine(() => owner)) //   . .And(WriteLine(() => houses)) .Count(); 

The result of the program:

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

The number of lines of code is approximately the same as in the Prolog solution.

What happens under the hood? In this solution, I used the YieldProlog library, which allows unification of parameters and search with return. There does not occur any intermediate compilation of the Prolog program. This is a fair decision in C #.
')
Parameter unification is performed using the function YP.unify (arg1, arg2). This is the main function, one might say, the core of the entire solution. The implementation is quite simple, but better than it is written in the documentation, I still will not write. And the documentation itself is small. Therefore, refer to it.

The first line of the solution is the binding of the houses variable to the list of unrelated variables. To set the lists, we will use a functor with five arguments, since in our problem all the lists consist of only five elements. Here is the code for the List method:

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

Here Functor is a class from the YieldProlog library.

Now, instead of the long entry Functor.make (new [] {new Variable (), new Variable (), ...}) I can use the shorter List (new Variable (), new Variable (), ...). And to make the list look more elegantly added property:

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

Then the list of unified variables will be written as: List (_, _, ...).

Next, I will describe the predicates member (Elem, List), nth1 (N, List, Elem), nextto (X, Y, List) and neighbors (X, Y, List). I specifically did not use the lists of the form [head | tail], but I use ordinary arrays, since I have no task to repeat the description of these predicates in the same way as their description on the Prolog.

member (Elem, List) will look like this:

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

Everything is very simple here. In the loop we iterate over the elements of the list and unify each element with the element of the list.

Design:

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

serves to unify two variables.

nth1 (N, List, Elem) will turn into:

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

Here we also iterate through each element of the list and for each element we unify it with the parameter elem. If the parameter we already have is associated with some value and this value coincides with the value of some list item, then we unify the number of this item in the list with the parameter n.

nextto (X, Y, List) we write this:

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

We are going over not one element at a time, but two at a time and unifying two adjacent elements of the list with the x and y parameters.

neighbors (X, Y, List) are implemented in the same way as in the Prolog solution:

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

Using iterators is a very important part of the solution. They just allow you to do a search with a return. If the unification of the two variables is successful, the next iteration step occurs and the transition to the nested loop, if there is one. If the unification is not successful, this loop is interrupted and the next iteration of the outer loop proceeds.

In solving this problem, 15 predicates go in a row. In YieldProlog, you have to write 15 nested loops for this:

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

This is inconvenient and ugly. Therefore, we add an auxiliary method And, which builds chains of predicates:

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

It's all. You can call the Einstein function:

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

And, nothing happens. That's because we simply built an iterator using yield, but did not create an iteration loop. You can create it explicitly:

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

And you can simply call the Count method, which will go through the iterator and calculate the number of iterations.

In addition, before starting our iterator, we can add new conditions to our solution:

 Einstein(houses) //   ? .And(Member(List(owner, "fish", _, _, _), houses)) //   . .And(WriteLine(() => owner)) //   . .And(WriteLine(() => houses)) .Count(); 

Auxiliary function WriteLine:

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

Instead of a resume

This article arose from the question of how logical tasks could be easily described in C #. And here I brought one of the ways. I had no goal to get the optimal solution in terms of performance or memory size. There are libraries that allow you to write programs on the Prolog, compile them and connect as libraries to your project. I also wanted to get a solution using built-in C # tools. Searching on the Internet, I found the YieldProlog library, which solves this problem. That is, I can describe logical tasks in my usual language using familiar syntax. At the same time, I describe the problem in the same way as on Prolog. Yes, and it is possible to use the types and features of C #. Yes, and with the ability to optimize the solution as needed.

If anyone is interested, then the program runs on my old AMD Turion 1.8 GHz laptop in 0.1 seconds.