I didn’t know Haskell to be slow – certainly doesn’t seem that way in popular benchmarks, but I’ll soon find out for myself. Gonna do AoC 2022 in Haskell + Prolog in a few weeks.
Here is what I get for Prolog:
time(take(5000,primes(iter(succ,2)),_)).
% 38,009,267 inferences, 2.005 CPU in 2.005 seconds (100% CPU, 18954407 Lips)
true.
and for Haskell given the following implementation:
sieve :: [Integer] -> [Integer]
sieve [] = []
sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0]
and then in the interpreter:
:set +s
length . take 5000 $ sieve [2..]
% 5000
% (2.39 secs, 3,181,528,440 bytes)
but if I compile the code and run it in bash I get:
time ./primes
% 5000
% real 0m0.312s
% user 0m0.294s
% sys 0m0.005s
Bare in mind that the Haskell implementation is naive. There are significantly faster implementations available because arrays are a thing.
I’m about 10 problems into AoC2022 in Haskell at the moment. It made me realise just how much of the Prolog I’ve written is basically functional programming. In terms of my style I’d say maybe 90%. I do wonder however – when Prologness is maximised – what that percentage could be in the best case scenario.
I suppose “Prologness” is maximised when the code can maximally lean on implicit backtracking or where the homoiconicity of the language is a significantly utilised.
I saw a talk once about the duality between logic and computation. Remember the guy mentioning how we are destined to – as a result – make every discover twice: one by a logician and the other by a computer scientist 
2 Likes
Haskell is quite nice. To me, its just like Prolog from a practical perspective because most Prolog that I wrote is functional programming in spirit. Passing things around by value is really convenient. Even after a year in Prolog I’d still be writing things like X+1 as a predicate variable by accident. Piping functions together also feels very natural. I’d wish for Prolog to have similar syntactic sugar to the “.” operator such that (f . g) x results in f(g(x)). Of course its not just sugar in Haskell, its literally “all you need” ala lambda calculus. I guess the motivation for a functional logic programming language are fairly obvious.
I’m on Day 17 AoC 2022. My benchmark for conciseness is @BarrensZeppelin , his solutions in Python/Prolog are here. My Haskell ones are here. Its meaningful to me that with a couple of weeks of Haskell and a limited vocabulary, one can produce concise solutions to fiddly problems. I think it indicates something about the expressiveness of the paradigm.
1 Like
I run a 2.4GHz i7 CPU from deep deep yesteryear. Ceteris paribus, I’m not really surprised that compiled languages run faster than Prolog implementations if for no other reason than that Prolog is typically interpreted. My understanding is that SWI doesn’t use JIT compilation? I think if you assume even a small runtime multiple for SICStus vs SWI (and I understand that there is a big one, and SICStus compiles), it would likely beat 0.3s, ceteris paribus.
BogoMIPS: 5606.40, and its 2.8Ghz not 2.4 – correction.
Prolog is typically compiled to byte code executed by a virtual machine. SWI-Prolog has JIT indexing.
Haskell has something called “sequences”. They are based on finger trees, and its a purely functional structure which allows for O(1) reads/writes to beginning and end of a sequence. Its also O(log n) for random access.
Since its purely functional, the concept probably ports to Prolog with all the same benefit: no more O(n) to access the last element
Haskell is slow, where Prolog is slow: frequent random access or mutation of array-like structures. These sorts of operations map poorly to the hardware’s memory model and can end up orders of magnitude slower compared to a compiled language with native arrays.
I eventually finished AoC2022 in dribs and drabs of time. Its here. I can’t really tell if its more/less difficult than 2023 which I had solved in Prolog.
Initially I was sure that all the planning problems were going to take me lots more LOC in Haskell but the opposite was true. DFS, BFS, Dijkstra, A*, state space definition, and so on, were more succinct to write down compared to my 2023 experience because passing things around by value requires less boiler plate. E.g. f . g x rather than g(X,Y), f(Y).
I think control statements such as function guards and case make it easier to express conditional variation on what is otherwise the same code. In Prolog I end up explicitly writing variants of the same predicate in order to use pattern matching for the same thing, which is often much more verbose.
What I prefer in Prolog is the ability to express data in the language directly. E.g. dynamically add some predicates at the beginning of the code, and then use it throughout without having to pass it around.
I’d like to say that clpfd is some kind of an advantage but – and not for lack of trying – I still can’t understand what its for. Things I’ve solved with it in AoC2023, I now know are just as easy without it. Meanwhile, I did miss CHR. I had found it very useful for simulating how a state evolves through simple constraints.
Throughout, I found myself reasoning about problems in Prolog. What I then wrote down in Haskell is very much “Prolog inspired”: I could not find a Haskell repo with a lower average LOC than mine (<27 LOC mean), which I attribute largely to this approach. To wit, I find that Prolog is still the superior “mindware” for me, even though its Earthly incarnations are more verbose than I’d like them to be.
@meditans, it’d be great to hear your thoughts RE Haskell/Prolog since you know both languages better than me and you seem to prefer Prolog
1 Like
I won’t find the time to comment in detail on your Prolog code but I can give you useless observations. Every language gives you the ability to “not repeat yourself”. It is easier in Prolog, since you can write mini-interpreters with very low friction. If your goal is to write less end up with less code eventually, you would write it out once, then figure out the common parts, and almost always you will find a way to abstract the common parts to an ad-hoc interpreter. But this is of course the exact same rabbit hole that every LISPer has visited.
I tried to like Haskell and couldn’t because it is so restrictive in its extensive syntax. Prolog has almost no syntax and I feel like I am running free which is a good thing to do when you are not at work 
PS: it is more approachable if you have a concrete example of code that you think is repetitive in Prolog. But you can find a lot of repetitive code in the standard libraries of SWI-Prolog, too. Sometimes it is for efficiency and sometimes probably to make it easier to read. Not sure.
2 Likes
Referring to SWI-Prolog -- Manual
There are two major use cases of CLP(FD) constraints:
- declarative integer arithmetic (section A.9.3)
- solving combinatorial problems such as planning, scheduling and allocation tasks.
Point 1. is all about supporting true relational arithmetic in a relational programming language, so not really useful when doing a language comparison. Standard Prolog has functional arithmetic (N (ground) inputs, 1 output) so that’s just going to be equivalent to Haskell (a functional programming language), except that Haskell is much richer since you can embed your own functions/types in otherwise numeric expressions. (To be fair, some Prologs are better at this than SWIP’s current compiled arithmetic.)
Point 2. is about potentially optimizing some problems by using a test then generate strategy. If that doesn’t fit, then clpfd probably isn’t the solution.
@ridgeworks, those are the reasons I wanted to like clpfd. This is the probably the best thing I’ve built using it. I think that one easily assumes that clpfd is a solver, but it isn’t. Its just something you might use to build a problem specific solver, taking care not to use any impure Prolog or tabling in an incompatible way of course
I had an actual scheduling problem the other day. I smashed it out in Prolog in about 2 hours. I used the fdset_ predicates from clpfd. It was beautiful and I was over the moon with it. Shortly after, the team started asking me to add more constraints, and more participants to the schedule.
Very quickly it became impossibly slow, because I had essentially written a brute force search…quickly. However, when I needed to make it scale a bit, I had to backtrack and start thinking carefully about the data structure, the solution space, the search algorithm. Suddenly, clpfd has nothing useful for me, and unless I was going to spend a week coding a search algorithm from scratch, it was just much easier to move the problem to MiniZinc instead where I could invoke solvers, and wouldn’t have to write my own. That’s what I think the challenge is with clpfd (for me).
It may be tricky to find folks who’ve solved all of AoC in both Prolog and Haskell (being two fairly exotic languages), if that’s what you’re looking for. Our resident @BarrensZeppelin does it in Python and Prolog. His AoC 2022 Prolog solutions are here.
?- time(([U,V]::integer(0, 1000000000), {(36641*U)-24 == 394479375*V})).
% 96,065 inferences, 0.009 CPU in 0.009 seconds (100% CPU, 10781613 Lips)
U::integer(2303938, 997701977),
V::integer(214, 92671).
?- time(([U,V]::integer(0, 1000000000), {(36641*U)-24 == 394479375*V}, solve([U,V]))).
% 4,284,164 inferences, 0.439 CPU in 0.440 seconds (100% CPU, 9750102 Lips)
U = 346688814,
V = 32202 ;
% 4,427,744 inferences, 0.438 CPU in 0.439 seconds (100% CPU, 10103822 Lips)
U = 741168189,
V = 68843 ;
% 2,734,115 inferences, 0.271 CPU in 0.271 seconds (100% CPU, 10091898 Lips)
false.
1 Like
Some caution is necessary in interpreting these results. Note that the clpfd results are quite tight but take considerably longer to get there. The reason for that is that clpBNR has a throttling mechanism on the fixed point iteration, which terminates the iteration after some count (user definable) unless the intervals are being narrowed by some minimum amount (~10% IIRC). You can observe the effect:
?- set_prolog_flag(clpBNR_iteration_limit,100000).
true.
?- time(([U,V]::integer(0, 1000000000), {(36641*U)-24 == 394479375*V})).
% 3,186,237 inferences, 0.731 CPU in 0.731 seconds (100% CPU, 4360867 Lips)
U::integer(76891234, 923103915),
V::integer(7143, 85742).
but it’ll take some time to achieve the same bounds as clpfd. And as clpBNR isn’t particularly optimized for integer problems, I would expect to achieve the same tight result might actually take longer than clpfd.
On the other hand:
This demonstrates the advantage of not spending a lot of time on the fixed point iteration (due to low throttling value) and using the labelling to derive solutions, which has to be done anyway to separate the two solutions.
I’m not overly happy with this sort of “engineering” requirement but haven’t yet seen a better way of addressing the problem. (Note that Tom Hickey’s CLIP system (CLP(Intervals)) .ca 2000 proposed a similar mechanism.)
Not really my decision to make, but I will support any reasonable alternative, or complement, to a pack. Any particular problem with packs? I’ve been working with @jan to get a version of clpBNR on SWISH. Maybe that with a pack based solution for local use is good enough?
Anyway this is drifting off-topic so maybe we need a new one if this discussion has any legs.
1 Like
I can try jotting down my two cents on what I think is an interesting distinction (my perspective is biased by being very interested in mathematical logic).
tl;dr Haskell and Prolog have two different ideas of what computation means, in the sense of what’s the underlying mechanism of computation.
There is this beautiful result in type theory called Curry–Howard correspondence (The Curry here is Haskell Curry, from which the name Haskell comes from). It shows you that in a type theory (you can think in haskell, even if the correspondence is not perfect) types have a direct relations with logical statements, and a program with a given type corresponds to a proof of the corresponding logical statements.
Since you know some haskell, here’s an example:
f :: a -> Either a b
f a = Left a
Now, the type a -> Either a b corresponds to the logical propositional formula A → A ∨ B, and actually the fact that you can write a program with that type at all is because that proposition is a tautology. The implementation of the function is a proof of that proposition.
In fact the program above is also the shortest program that you could write. Another program could be:
f a = snd (42, Left a)
Crucially, evaluating an expression in haskell means starting with a complicated proof (your code), and simplifying it until it becomes the simplest proof possible (your result). So, in this framework (type theory and haskell) computation means normalization (in the sense of simplification of a program - a proof - to its maximum degree, the so called normal form).
In the world of prolog instead, computation is essentially the search of a suitable deduction tree. So, not the normalization of a proof. Instead it is the search of a proof, in principle by any mean possible. Logic + control, they say, but I can imagine the control part being a very wild thing.
I think this is fundamentally a more stimulating conceptual framework for thinking about computational phenomena. But apart from the philosophical enjoyment, what is there to gain by adopting this perspective?
I think it nudges us toward thinking of programs that are not easily expressed in the other paradigm. As an example, a program that sees it’s own deduction process, notices useful patterns, and finds ways of restructuring the computation to exploit that pattern. A sort of CDCL for SAT solvers, but on steroids.
Hope it was useful @emiruz 
ps. I’m not the first to present this as the more interesting distinction. I must have read this somewhere (it could be in one of Triska’s video on youtube but I can’t trace it down).
pps. I’m also not sure I prefer prolog to haskell. Both are beautiful, and flawed; which one to use depends on a lot of considerations. I also like lisps (clojure in particular). It is true however that for now my ideal language would be based on ideas taken from the prolog way of seeing computations.
4 Likes
Thank you for the insightful response!
That Haskell, like the lambda calculus, has a sort of replacement scheme for simplifying equations, doesn’t imply that it terminates. I.e. that it “normalises” doesn’t mean it succeeds in every case, and I guess that is akin to the halting problem.
Further, you can also restrict yourself in Haskell to just the decidable portion of the language – or just be mindful of the problematic cases like in Prolog – in which case the result will presumably be strongly normalising.