4 ms·

>Why should Prolog be slower than CLisp? In general, declarative programming tends to rely on having a sufficiently smart implementation. Maybe Prolog is simpl

>Why should Prolog be slower than CLisp? In general, declarative programming tends to rely on having a sufficiently smart implementation. Maybe Prolog is simply more efficient than I would've guessed

yorwba 9y ago
Prolog may be a "declarative" language, but you can still write imperative programs that rely heavily on resolution order, cuts and whatnot. So the natural solution in Prolog may be slower, but that doesn't mean you can't make it faster.
- fusiongyro 9y ago
  In my experience, it is hard to avoid factoring in the resolution order. Cuts are still gross as hell though. Often you can follow Bird's advice for Haskell and make an inefficient program that is obviously right as a base. Prolog programs often have a generate-and-test flavor; once you have a good base, you can start refining inefficiencies in one side or the other. Maybe it's easier to make your generator produce better-qualified candidates, maybe it's easier to make your test faster. Prolog also sometimes has surprising abilities owing to the unification process itself. For example, difference lists give you singly-linked lists with O(1) append to the tail. Data structures with "holes" are a generalization of that idea. There's also a whole book devoted to making Prolog programs efficient: The Craft of Prolog by Richard O'Keefe.
fusiongyro 9y ago
Most things that were considered shockingly inefficient in the 70s are faster than things we consider merely harmlessly inefficient today. :) In practice, Prolog requires the programmer to have some understanding of how it's going to be executed. This is in contrast to SQL, which is intentionally high-level to allow the database to figure out the best strategy and does require a lot more in the backend. Mercury also finds this abhorrent, but Mercury is another sufficiently-smart situation and a bit more obtuse.

>Why should Prolog be slower than CLisp? In general, declarative programming tends to rely on having a sufficiently smart implementation. Maybe Prolog is simply more efficient than I would've guessed

yorwba 9y ago

Prolog may be a "declarative" language, but you can still write imperative programs that rely heavily on resolution order, cuts and whatnot. So the natural solution in Prolog may be slower, but that doesn't mean you can't make it faster.

fusiongyro 9y ago
In my experience, it is hard to avoid factoring in the resolution order. Cuts are still gross as hell though. Often you can follow Bird's advice for Haskell and make an inefficient program that is obviously right as a base. Prolog programs often have a generate-and-test flavor; once you have a good base, you can start refining inefficiencies in one side or the other. Maybe it's easier to make your generator produce better-qualified candidates, maybe it's easier to make your test faster. Prolog also sometimes has surprising abilities owing to the unification process itself. For example, difference lists give you singly-linked lists with O(1) append to the tail. Data structures with "holes" are a generalization of that idea. There's also a whole book devoted to making Prolog programs efficient: The Craft of Prolog by Richard O'Keefe.

fusiongyro 9y ago

Most things that were considered shockingly inefficient in the 70s are faster than things we consider merely harmlessly inefficient today. :) In practice, Prolog requires the programmer to have some understanding of how it's going to be executed. This is in contrast to SQL, which is intentionally high-level to allow the database to figure out the best strategy and does require a lot more in the backend. Mercury also finds this abhorrent, but Mercury is another sufficiently-smart situation and a bit more obtuse.