Haskell vs Prolog, or "Giving Haskell a choice"

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Haskell vs Prolog, or "Giving Haskell a choice"

Postby Berengal » Wed Feb 25, 2009 5:16 am UTC

I've become more and more familiar with Haskell, and more and more have I begun to realize its true potential. It's truly frightening, really. One of the things I've started to realize is how well it can adapt different programming paradigms without sacrificing its functional purity.
Another language I'm quite fond of is Prolog, and I'm actually somewhat sad I haven't spent more time hacking in it.
That said, I decided to try a little experiment: writing Prolog in Haskell, staying as true to Prolog as possible, and see if the forced paradigm breaks it.

I'll be rather thorough in explaining how things work for the benefit of the Prolog and Haskell illiterates out there, so if you're familiar with both you might want to tl;dr, or just bask in the glory that is Prolog and Haskell combined.

At first this might seem somewhat difficult. Prolog doesn't have functions or procedures, but predicates. These have no return value (except succeed/fail). Instead, predicates have symetric arguments, meaning they work both ways: if a variable is assigned a value in a predicate, it keeps that value when the predicates returns. A small example: append/3 takes three lists where the first and second concatenated is the third. 'append([1,2,3],[4,5,6], Result).' then binds Result to [1,2,3,4,5,6]. A definition of append/3 might look like

Code: Select all

append([],Out, Out).
append([Head|Tail], BackEnd, [Head|Out]) :- append(Tail, BackEnd, Out).

The first clause should be obvious enough: When the first list is empty, the second and third are the same. The second is a bit more magic: When Head is the first element of the first list, is is also the head of the last list, and furthermore, the tail of the first list (Tail) concatenated to the second list (BackEnd) is the tail of the third list (Out).
The notation 'predicate/n' simply indicates that the predicate takes n arguments. 'predicate/n' and 'predicate/m' are two completely different predicates that have nothing to do with eachother (except what's stated in the code, and provided m and n are different numbers) meaning you can reuse names if you want to.

The magic of symetric arguments is that not only does 'append([1,2,3],[4,5,6],Result).' append two lists, but 'append(First, Second, [1,2,3,4,5,6]).' splits the last list into two lists, yielding each possible split in turn, and 'append([1,2,3], _, [1,2,3,4,5,6]).' succeeds only if [1,2,3] is a prefix of [1,2,3,4,5,6], and so on for postfix, infix, splitting in exactly half etc. (some with a few extra minor clauses).
As you can see, quite fun stuff.

Unfortunately, building a unification engine in Haskell is somewhat out of my league, so I'll have to resort to single-purpose functions, at least for now.


Another thing that makes prolog such a cool language is the built-in backtracking. When you say 'member(N, [1,2,3,4,5]), N > 4.' it will try to unify N using the definition of member/2 (the first argument is an element of the second argument). The first such definition it finds is "N is the head of the list", and assign N = 1. It will then try 1 > 4, and fail. It will then backtrack to member and try the second definition: "N is a member of the tail of the list", which recurses on the tail of the list, and again it looks up member, finds the first definition again and assigns N = 2 and so on until either it finds a member of the list such that N > 4, or the entire predicate fails.

Now this is actually quite easy to accomplish in Haskell, as you'll see.

Anyway, I needed a problem to solve, and one that's quite trivial in Prolog but rather hard in most other languages is the n-queens problem.
Short description: Given n queens and a chess board of n by n size, how many different ways can you place those queens on the board so that none of them can attack eachother (and what are the exact configurations)?
My solution gives the answer as a list of numbers, where each number is the row number, and the position in the list is the column (first element is in column 1, second in column 2 etc). An example (incorrect) solution to n = 3 is [1,3,2] which would look like

Code: Select all

Q|_|_
_|_|Q
_|Q|_

(The n-queens problem has no solutions for n = 2 and 3 by the way, although it does have one for n = 1 ;) )

I won't try to solve it in the most efficient way possible, but rather in a clear and logical way typical of prolog, and then try to implement the same solution in Haskell to see if it's still as clear and logical.

Solving this in prolog is easy: We can begin by declaring the top predicate.

Code: Select all

nqueens(Size, Out) :-
  numlist(1, Size, UnplacedQueens),
  nqueens([], UnplacedQueens, Out).

nqueens(Out, [], Out).
nqueens(PlacedQueens, UnplacedQueens, Out) :-
  select(Queen, UnplacedQueens, NewUnplacedQueens),
  cannotAttack(Queen, PlacedQueens),
  nqueens([Queen|PlacedQueens], NewUnplacedQueens, Out).

(I should probably note that comma is 'and' in prolog-speak, and this works excellent as a statement separator).

This is actually two different predicates, but the first one is just a convenience one, creating a list of numbers and calling the second one. The second one is the interesting one.

The first clause in the second predicate simply states that when UnplacedQueens is empty, PlacedQueens (as it's called in the second clause) is the same as Out, which we use as our return argument.
'select/3' takes an element of a list, a list, and the list without the element. In this case, I provide it with the second list and let it figure out the values of the first and third itself. In english this is "Queen is an element of UnplacedQueens, and NewUnplacedQueens is UnplacedQueens but with Queen removed".

'cannotAttack/2' is a predicate we will define later, but it simply states that the selected Queen cannot attack the already PlacedQueens. This is a fact. It is not a test or some way to coerce Queen into the right value, but a pure and simple factual statement. If prolog finds that 'cannotAttack/2' is false, it will conclude that it made an error in one of the previous steps and backtrack.

The last statement is a recursive one, and this is perhaps best viewed in a procedural context. It states that "if Queen is a member of UnplacedQueens (first statement), and Queen cannot attack PlacedQueens (second statement), then add Queen to PlacedQueens, and find the next queen using NewUnplacedQueens. The resulting Out is my Out."

If you've understood the problem and the format of the solution I'm looking for, it shouldn't be hard to see that this solution is correct provided 'cannotAttack/3' is correct. It's important to remember that none of the terms can fail! If one of them does, it backtracks and tries different definitions of previous predicates. If it has tried all definitions and still can't satisfy the predicate, it pops the stack and tries the different definitions for terms in the calling predicate. If it pops the stack all the way up without finding a solution that satisfies all the terms, it tells you there is no solution.

Okay, so let's define the 'cannotAttack/2' predicate:

Code: Select all

cannotAttack(Row, PlacedQueens) :- cannotAttack(Row, 1, PlacedQueens).
cannotAttack(_Row, _N, []).
cannotAttack(Row, N, [Queen|PlacedQueens]) :-
  Queen =\= Row - N,
  Queen =\= Row + N,
  Next is N + 1,
  cannotAttack(Row, Next, PlacedQueens).

(An underscore in front of a variable name means it's ignored. Prolog will give a warning about unused variables without an underscore, but otherwise won't do anything else. It's simply to protect against typos.)

Again, the first predicate is a simple wrapper around our second predicate which is doing all the work.

The first clause of the second predicate simply states that when PlacedQueens is empty the predicate is true.

If you've understood the format of my solution, the second clause should be easy to understand as well. It simply checks if the Row we're checking is on a diagonal to any of the already PlacedQueens. A Row is on the same diagonal as a Queen if their distance in the list is the same as the absolute difference between the row numbers. We do this by recursion: The distance from the Row to the first element in the list is 1 (because Row will eventually be placed right in front of it), and so either Row - 1 or Row + 1 should be the same as Queen (which is also a row, remember). We check that they're not, increment the distance N and recurse.


Okay, so we've got a prolog solution which is rather explicit and elegant and using Prolog's nifty backtracking feature, which Haskell clearly lacks. What remains now is to implement it in Haskell and see if it's just as explicit and elegant there. To do that, we need to implement backtracking somehow.

Or do we? When the backtracking in our program backtracks to somewhere, it's always the select term. When a select term backtracks (i.e. it has run out of elements to return) it pops the stack and backtracks to the select term in the calling nqueens. Wouldn't it be possible to instead of backtrack just create a list of all possible different values for Queen and NewUnplacedQueen at once, map the rest of the clause over that list and collect all the solutions it produces? Something like 'concatenate (map restOfPredicate possibleValuesForQueenAndNewUnplacedQueens)' should work, right?

Now for a rethorical question. Do you know what the list monad looks like?
The rethorical answer: The list monad can be viewed as a computation over values that change. The bind operator for lists can be defined something like 'listA >>= funcToListB = concat (map funcToListB listA)'. Looks familiar? It's the "collect all solutions" function I wished for in the above paragraph. What about the computations that fail? The list monad defines 'fail = []', the empty list, or as we'll see it, no solutions found.

Where do we get this list of possible values then? Let's take a look at prolog again. Prolog gets its different values by committing to a certain definition. If that definition leads to a contradiction, it backtracks and chooses another definition. One way to look at this is a simple 'or' statement. "The value of N is 5 OR 7, I'll commit to 5 for now... no, that was wrong, I'll choose 7 instead." In prolog, 'or' is usually done by splitting predicates into two different definitions, or clauses, like

Code: Select all

choicePoint(N) :- N = 5.
choicePoint(N) :- N = 7.

(Prolog also has an 'or' operator for choices that are too trivial to factor out into their own predicates.)

Since we're using lists to implement choice and each element is a different possible value, we'll use cons instead. Our Haskell definition of choicePoint is then 'choicePoint = 5:7:[]'

Okay, so we've figured out how to do backtracking. The only problem is that creating huge lists where most values probably won't be used, instead of using backtracking to compute those values lazily as we need them...
Except Haskell is also lazy. Even more so than Prolog, in fact. No problem here then. Let's carry on.

Before we start on the solution, we need to implement the 'select' function. This isn't built-in in Haskell, it not being a logic programming language. We won't be able to get all the functionality of the Prolog select in Haskell with just one function, but we'll ignore that fact and implement it so it fits our needs: take a list and return an element and a list without the element. In Prolog 'select' might look something like

Code: Select all

select(Elem, [Elem|Rest], Rest]. % First element is Elem, rest is Rest
select(Elem, [Head|Tail], [Head|ElemLessList]] :- select(Elem, Tail, ElemLessList). % Elem is found recursively, but remove Head from the input list and cons it back on on the way back up the stack

Using the rule about choice we made above, that different definitions in Prolog is cons in Haskell we define:

Code: Select all

select :: [a] -> [(a, [a])]
select [] = fail []
select (x:xs) = (x, xs) -- Equal to the first definition
                  : -- OR
                (map (\(a,b) -> (a, x:b)) (select xs)) -- Equal to the second definition

Not quite as elegant as the prolog equivalent, but I blame variable unification for that. We have to manually cons the head of the list back on to every possible choice returned by the recursive select call, but Prolog just unifies them on the way back. You can also clearly see the relationship between different choices and lists here in that the returning result of a recursion needs to map any function over it, instead of working with a returned value directly like in Prolog.
Also note that we explicitly need to provide a failure clause, or we would get a runtime error trying to extract the first element of an empty list. Prolog knows when it's out of choices

Okay, so now on to nqueens function. This should, as the prolog equivalent, take a number and return a list of all possible solutions.

Code: Select all

nqueens:: Integer -> [[Integer]]
nqueens size = nqueens' [] [1..size]
  where nqueens' placedQueens [] = return placedQueens
        nqueens' placedQueens unplacedQueens =
          do (queen, newUnplacedQueens) <- select unplacedQueens
             True <- return (cannotAttack queen placedQueens)
             nqueens' (queen:placedQueens) newUnplacedQueens

Compare this to the prolog predicate above. Astonishingly similar aren't they? If you're only somewhat familiar with Haskell, you should take note of the 'do' used. Unlike it's common useage, to do stuff like print to the console in the IO monad, we're in fact working in the list monad here, where computations aren't done over IO and interaction with the outside world, but over lists. 'x <- someList' just fetches a value from someList and does computation on it. When it's done, it fetches the next value, just as in list-comprehension, and in the end it concats the results together into a list of successful computations. When we do 'True <- return (booleanValue)' it tries to match the boolean value with True, and if it fails it returns "fail", which for lists is the empty list, which we again interpret as "no solutions found for this choice".
Finally, we return the list of solutions found by the recursive call, which will be concatenated with the solutions found for all other values of (queen, newUnplacedQueens).

If you understood the Prolog predicate, there should be little new to understand here. Let's have a look at 'cannotAttack'

Code: Select all

cannotAttack :: Integer -> [Integer] -> Bool
cannotAttack row placedQueens = cannotAttack' row 1 placedQueens
  where cannotAttack' _row _n [] = True
        cannotAttack' row n (queen:placedQueens) =
          queen /= row + n &&
          queen /= row - n &&
          cannotAttack' row (n + 1) placedQueens

If anything, this looks even more like the prolog code from before. Remember that comma is the 'and' operator in Prolog. Haskell uses the more common '&&', but other than that it's pretty much completely identical.

I'll let you draw your own conclusions. Mine is that Prolog and Haskell are awesome, but Haskell needs unification (Erlang has this, I know, and is actually very close to Prolog in several respects, but it lacks backtracking).
Some people say Haskell is the best imperative language there is. I also think it has shown that it makes a pretty good logic programming language as well.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

levantis
Posts: 20
Joined: Thu Feb 05, 2009 1:42 pm UTC

Re: Haskell vs Prolog, or "Giving Haskell a choice"

Postby levantis » Wed Jun 16, 2010 9:22 pm UTC

Nice! I`m just a haskell beginner, and didn`t look further the first page of prolog textbooks, but you inspired me again )

And yes, it`s always fun to write in a paradigm of another language.

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Re: Haskell vs Prolog, or "Giving Haskell a choice"

Postby MHD » Wed Jun 16, 2010 9:59 pm UTC

You are a computer science god.
I simply love reading your essays on comp-sci, and I always feel like I'm gaining at least 5 IQ points per essay.
Do you have a list of links to the threads like this you have ever written? I would love to get my hands on that, maybe even show them to some of my friends and/or teachers.

Anyway, Berengal, you are a wonderful mind and I hope to see more works like this in the future.
Keep hacking my friend!
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Haskell vs Prolog, or "Giving Haskell a choice"

Postby Berengal » Thu Jun 17, 2010 3:34 am UTC

16 months between post and first reply. I'd thought this was long since dead.
MHD wrote:Do you have a list of links to the threads like this you have ever written?
No, afraid not.

By the way, Haskell has better monads than the list monad for doing logic, like the logic monad.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

redgrowth
Posts: 24
Joined: Mon May 03, 2010 6:02 pm UTC

Re: Haskell vs Prolog, or "Giving Haskell a choice"

Postby redgrowth » Thu Jun 17, 2010 5:49 am UTC

Not to be trite, but isn't Haskell + Prolog = Erlang?


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 6 guests