5 ms·

Picat: A Logic-Based, Multi-Paradigm, Programming Language

102 points by nickpsecurity 9y ago

EtDybNuvCu 9y ago
Interesting syntax. Can Picat programs be run backwards or in other-than-expected directions, as in Prologs and Kanrens? This relational aspect is the killer feature of logical languages, and it would be unfortunate if Picat doesn't have it.
- doublec 9y ago
  Yes, it's possible in picat. For example, here's factorial in picat that can be computed backwards: http://www.hakank.org/picat/factorial_reversible.pi http://www.hakank.org/picat/factorial_reversible.pi
CocoaGeek 9y ago
The mix of logical and imperative programming is nice. That's probably what I should have done for fizz :(
nickpsecurity 9y ago
Here's the homepage of what appears to be the author or one of them. He's done a lot of interesting work on logical programming, solvers, etc. I pinged him via email in case he wants to answer anyone's questions about it. http://www.sci.brooklyn.cuny.edu/~zhou/ http://www.sci.brooklyn.cuny.edu/~zhou/
dgreensp 9y ago
Example 1 makes this look like a very imperative language, otherwise why would you write out a “map” as an imperative loop? We are back to manually allocating an array the same size as an existing array, and having to remember to increment a counter at the end of a loop? I will write code like that only if there is a performance reason.
FractalLP 9y ago
My biggest problem with logic programming is that my imperative brain can't make the jump to thinking in those terms. Maybe if someone could post a bunch of examples comparing idiomatic python to prolog I could start to think in those terms. There is a 99 problems in Prolog, but those aren't exactly what I think is needed. I think that should also be done for functional programming, but I find FP far easier to grok.
- triska 9y ago
  In a sense, if you already understand functional programming, then the leap to logic programming is comparatively straight-forward: Say you have a function f with N arguments that yields a value y. That is, you have y = f(x_1,...,x_N). Then you can regard such a function as a relation with (N+1) arguments, relating the N arguments to the intended result y. So, in other words, the function can be modeled as a predicate P(x_1, ..., x_N, y) that holds iff y = f(x_1, ..., x_N). The key differences between functions and predicates are: 1. In contrast to a function, a predicate can relate the same arguments to multiple (different) results. 2. You can query a predicate in all directions, also if none of the arguments and not even the result is known, and it will still often yield useful answers. In fact, it no longer even makes sense to regard one particular argument as the "result". A predicate simply holds for certain combinations of arguments, and does not hold for others. Hence, you can consider predicates as a natural generalization of functions, and if you are already familiar with functional programming, logic programming will likely be comparatively easy to grasp. A large number of the 99 problems you mention are very imperatively worded, and if you solve them only in the way they are phrased then you will benefit only little from the true potential of Prolog. For example, the task descriptions ask you to "find", "reverse", "flatten" and "eliminate", but rarely to actually express the relation between things so that you can use the predicate in all directions and thus truly benefit from logic programming. Ideally, the same Prolog predicate can be used to generate all solutions, validate any given solution, to compute a specific solution etc.
- YeGoblynQueenne 9y ago
  If you want to see a discussion of Prolog alongside a functional and an imperative language, there's George Luger's textbook, "AI Algorithms, Data Structures and Idioms in Prolog, Lisp, and Java". You can find some chapters of it on the author's webpage, here: https://www.cs.unm.edu/~luger/ https://www.cs.unm.edu/~luger/ (You can also find the whole book online for free but I'm not sure of the legality of that so I'm not linking to it). There's some examples of programs implemented in both Python and Prolog on Rosetta Code, too.
YeGoblynQueenne 9y ago
That looks nice. List comprehensions, higher-order functions and arrays in a logic-based language with CLP and planning facilities sounds great. In terms of looks, I'm not sure why but it reminds me of a cross between Python and Prolog. There's a few things that look a bit strange though. e.g.: perms([]) = [[]]. perms(Lst) = [[E|P] : E in Lst, P in perms(Lst.delete(E))]. So, "|" is a cons operator, but can't be used to take a list apart by recursively separating its head from its tail? That's a bit strange. Also: Compared with Prolog, Picat is arguably more expressive and scalable: it is not rare to find problems for which Picat requires an order of magnitude fewer lines of code to describe than Prolog and Picat can be significantly faster than Prolog because pattern-matching facilitates indexing of rules. That's just ... no :) [Because modern Prologs index all predicats, including rules, by pattern mathing and there's nothing more expressive than FOL so].
- ScottBurson 9y ago
  I don't know exactly what's meant by "pattern-matching facilitates indexing of rules", but I wouldn't dismiss it so quickly. Zhou has long experience with a Prolog implementation (B-Prolog) and seems to know his stuff. The tabling feature in particular suggests that this is a state-of-the-art offering. As for expressiveness, I think he's using the term in the sense of "how easy it is to express things", not "what is possible to express".
  - YeGoblynQueenne 9y ago
    >> I don't know exactly what's meant by "pattern-matching facilitates indexing of rules", but I wouldn't dismiss it so quickly. Far as I can tell, "pattern-matching facilitates indexing of rules" means that the indexing scheme builds an index with a key for every instantiation pattern of a predicate in the program database. Prolog uses pattern matching to match a query (or a goal) to the head of a predicate in its database. To speed things up, predicates are indexed by their functor name (the predicate symbol) and the value of their first argument, if it is a constant. That's all for default Prolog. In modern Prologs keys are built for deeper patterns- more arguments, or compound arguments at different depth etc. The particulars depend on the implementation, but basically what I get from "pattern matching facilitates etc" is that Picat allows indexing on multiple arguments, including compound terms, which could enable matching the entire pattern of a query to an index key. Which is cool and all but it's not something you won't find in Prolog. You can find details of one indexing scheme for Prolog in Swi-Prolog's documentation on its jiti clause indexing, here: http://www.swi-prolog.org/pldoc/man?section=jitindex http://www.swi-prolog.org/pldoc/man?section=jitindex Hope the above makes sense- I assume some knowledge of Prolog, let me know otherwise and I'm happy to clarify.
afaz 9y ago
Picat is a pragmatic mix of several programming paradigms, and it supports both directional and non-directional computing. Pattern-matching is directional. Consider the following predicate definitions: p([a,b|_]) => true. q([X,X]) => true. A call p(L) succeeds only when L has at least two elements and the first two elements are a and b, respectively. A call q(L) succeeds only when L has exactly two identical elements. Functions are directional. In Prolog, the length(L,N) predicate can be used to compute the length of L and can also be used to create a list of a given length N. In Picat, you need to use function new_list(N) to create a list, and use function len(L) to compute the length of L. Loops are directional. Unlike in ECLiPSe-CLP where it is possible to iterate over a list that is to be created, in Picat the collection of every iterator must be fixed. Unification is non-directional. A call X = Y is like an equality constraint over terms. Built-ins predicates, such as member(X,L) and append(L1,L2,L3), are defined by using unification, and can be used in the same way as in Prolog. Constraints are non-directional. While a unification X = Y has a unique solution when it succeeds, a system of constraints may have multiple solutions. Picat provides a built-in, called solve, that calls the imported solver to search for a satisfactory or an optimal solution.
pagnol 9y ago
How does this compare to Mercury?
- triska 9y ago
  Picat has a built-in planner that enables some interesting solutions to planning tasks. Picat has strong built-in support for important constraints, notably constraints over finite domains which is a very important paradigm for solving combinatorial tasks, and a strong SAT solver that is in fact so good that it is quite competitive with some much more specialized SAT solvers. Compared to Picat, the syntax of Mercury is much closer to Prolog. In fact, Mercury's syntax is so close to Prolog that many Mercury programs are also syntactically valid Prolog code (if you remove or support some declarations that are specific to Mercury). In contrast to Picat, Mercury is statically typed, with explicit type, mode and determinism declarations. Mercury can and does reorder goals to satisfy mode constraints. Mercury supports definite clause grammars (DCGs), like Prolog. Mercury is a pure language, and Picat isn't: For example, Picat programs may emit output on the terminal without any special declarations or other dedicated provisions.
  - pagnol 9y ago
    Thank you for taking the time to respond! It's quite an honor to receive an answer from you, as your book has been a valuable resource whenever I worked with Prolog.

102 points by nickpsecurity 9y ago

Interesting syntax. Can Picat programs be run backwards or in other-than-expected directions, as in Prologs and Kanrens? This relational aspect is the killer feature of logical languages, and it would be unfortunate if Picat doesn't have it.

doublec 9y ago
Yes, it's possible in picat. For example, here's factorial in picat that can be computed backwards: http://www.hakank.org/picat/factorial_reversible.pi http://www.hakank.org/picat/factorial_reversible.pi

CocoaGeek 9y ago

The mix of logical and imperative programming is nice. That's probably what I should have done for fizz :(

nickpsecurity 9y ago

Here's the homepage of what appears to be the author or one of them. He's done a lot of interesting work on logical programming, solvers, etc. I pinged him via email in case he wants to answer anyone's questions about it. http://www.sci.brooklyn.cuny.edu/~zhou/ http://www.sci.brooklyn.cuny.edu/~zhou/

dgreensp 9y ago

Example 1 makes this look like a very imperative language, otherwise why would you write out a “map” as an imperative loop? We are back to manually allocating an array the same size as an existing array, and having to remember to increment a counter at the end of a loop? I will write code like that only if there is a performance reason.

FractalLP 9y ago

My biggest problem with logic programming is that my imperative brain can't make the jump to thinking in those terms. Maybe if someone could post a bunch of examples comparing idiomatic python to prolog I could start to think in those terms. There is a 99 problems in Prolog, but those aren't exactly what I think is needed. I think that should also be done for functional programming, but I find FP far easier to grok.

triska 9y ago
In a sense, if you already understand functional programming, then the leap to logic programming is comparatively straight-forward: Say you have a function f with N arguments that yields a value y. That is, you have y = f(x_1,...,x_N). Then you can regard such a function as a relation with (N+1) arguments, relating the N arguments to the intended result y. So, in other words, the function can be modeled as a predicate P(x_1, ..., x_N, y) that holds iff y = f(x_1, ..., x_N). The key differences between functions and predicates are: 1. In contrast to a function, a predicate can relate the same arguments to multiple (different) results. 2. You can query a predicate in all directions, also if none of the arguments and not even the result is known, and it will still often yield useful answers. In fact, it no longer even makes sense to regard one particular argument as the "result". A predicate simply holds for certain combinations of arguments, and does not hold for others. Hence, you can consider predicates as a natural generalization of functions, and if you are already familiar with functional programming, logic programming will likely be comparatively easy to grasp. A large number of the 99 problems you mention are very imperatively worded, and if you solve them only in the way they are phrased then you will benefit only little from the true potential of Prolog. For example, the task descriptions ask you to "find", "reverse", "flatten" and "eliminate", but rarely to actually express the relation between things so that you can use the predicate in all directions and thus truly benefit from logic programming. Ideally, the same Prolog predicate can be used to generate all solutions, validate any given solution, to compute a specific solution etc.
YeGoblynQueenne 9y ago
If you want to see a discussion of Prolog alongside a functional and an imperative language, there's George Luger's textbook, "AI Algorithms, Data Structures and Idioms in Prolog, Lisp, and Java". You can find some chapters of it on the author's webpage, here: https://www.cs.unm.edu/~luger/ https://www.cs.unm.edu/~luger/ (You can also find the whole book online for free but I'm not sure of the legality of that so I'm not linking to it). There's some examples of programs implemented in both Python and Prolog on Rosetta Code, too.

YeGoblynQueenne 9y ago

That looks nice. List comprehensions, higher-order functions and arrays in a logic-based language with CLP and planning facilities sounds great. In terms of looks, I'm not sure why but it reminds me of a cross between Python and Prolog. There's a few things that look a bit strange though. e.g.: perms([]) = [[]]. perms(Lst) = [[E|P] : E in Lst, P in perms(Lst.delete(E))]. So, "|" is a cons operator, but can't be used to take a list apart by recursively separating its head from its tail? That's a bit strange. Also: Compared with Prolog, Picat is arguably more expressive and scalable: it is not rare to find problems for which Picat requires an order of magnitude fewer lines of code to describe than Prolog and Picat can be significantly faster than Prolog because pattern-matching facilitates indexing of rules. That's just ... no :) [Because modern Prologs index all predicats, including rules, by pattern mathing and there's nothing more expressive than FOL so].

ScottBurson 9y ago
I don't know exactly what's meant by "pattern-matching facilitates indexing of rules", but I wouldn't dismiss it so quickly. Zhou has long experience with a Prolog implementation (B-Prolog) and seems to know his stuff. The tabling feature in particular suggests that this is a state-of-the-art offering. As for expressiveness, I think he's using the term in the sense of "how easy it is to express things", not "what is possible to express".
- YeGoblynQueenne 9y ago
  >> I don't know exactly what's meant by "pattern-matching facilitates indexing of rules", but I wouldn't dismiss it so quickly. Far as I can tell, "pattern-matching facilitates indexing of rules" means that the indexing scheme builds an index with a key for every instantiation pattern of a predicate in the program database. Prolog uses pattern matching to match a query (or a goal) to the head of a predicate in its database. To speed things up, predicates are indexed by their functor name (the predicate symbol) and the value of their first argument, if it is a constant. That's all for default Prolog. In modern Prologs keys are built for deeper patterns- more arguments, or compound arguments at different depth etc. The particulars depend on the implementation, but basically what I get from "pattern matching facilitates etc" is that Picat allows indexing on multiple arguments, including compound terms, which could enable matching the entire pattern of a query to an index key. Which is cool and all but it's not something you won't find in Prolog. You can find details of one indexing scheme for Prolog in Swi-Prolog's documentation on its jiti clause indexing, here: http://www.swi-prolog.org/pldoc/man?section=jitindex http://www.swi-prolog.org/pldoc/man?section=jitindex Hope the above makes sense- I assume some knowledge of Prolog, let me know otherwise and I'm happy to clarify.

afaz 9y ago

Picat is a pragmatic mix of several programming paradigms, and it supports both directional and non-directional computing. Pattern-matching is directional. Consider the following predicate definitions: p([a,b|_]) => true. q([X,X]) => true. A call p(L) succeeds only when L has at least two elements and the first two elements are a and b, respectively. A call q(L) succeeds only when L has exactly two identical elements. Functions are directional. In Prolog, the length(L,N) predicate can be used to compute the length of L and can also be used to create a list of a given length N. In Picat, you need to use function new_list(N) to create a list, and use function len(L) to compute the length of L. Loops are directional. Unlike in ECLiPSe-CLP where it is possible to iterate over a list that is to be created, in Picat the collection of every iterator must be fixed. Unification is non-directional. A call X = Y is like an equality constraint over terms. Built-ins predicates, such as member(X,L) and append(L1,L2,L3), are defined by using unification, and can be used in the same way as in Prolog. Constraints are non-directional. While a unification X = Y has a unique solution when it succeeds, a system of constraints may have multiple solutions. Picat provides a built-in, called solve, that calls the imported solver to search for a satisfactory or an optimal solution.

pagnol 9y ago

How does this compare to Mercury?

triska 9y ago
Picat has a built-in planner that enables some interesting solutions to planning tasks. Picat has strong built-in support for important constraints, notably constraints over finite domains which is a very important paradigm for solving combinatorial tasks, and a strong SAT solver that is in fact so good that it is quite competitive with some much more specialized SAT solvers. Compared to Picat, the syntax of Mercury is much closer to Prolog. In fact, Mercury's syntax is so close to Prolog that many Mercury programs are also syntactically valid Prolog code (if you remove or support some declarations that are specific to Mercury). In contrast to Picat, Mercury is statically typed, with explicit type, mode and determinism declarations. Mercury can and does reorder goals to satisfy mode constraints. Mercury supports definite clause grammars (DCGs), like Prolog. Mercury is a pure language, and Picat isn't: For example, Picat programs may emit output on the terminal without any special declarations or other dedicated provisions.
- pagnol 9y ago
  Thank you for taking the time to respond! It's quite an honor to receive an answer from you, as your book has been a valuable resource whenever I worked with Prolog.