Hacker News new | past | comments | ask | show | jobs | submit login
Picat: A Logic-Based, Multi-Paradigm, Programming Language (picat-lang.org)
102 points by nickpsecurity on Mar 11, 2018 | hide | past | favorite | 22 comments



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.


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].


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".


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

Hope the above makes sense- I assume some knowledge of Prolog, let me know otherwise and I'm happy to clarify.


Ah, that's interesting. I wasn't aware that modern Prologs did that much indexing, though it stands to reason that they would; I hadn't really thought about it.


To second the other poster, (Felleisen) expressiveness is not power, it's more like a ratio of power to program length.


Sure, but that's a bit arbitrary. So I feel free to pick at it :)


Not quite arbitrary, it's mathematically defined via Kolmogorov complexity, the latter just happens to be uncomputable, so we only have approximations using the best available compression techniques. It's good enough for rough estimates.


In principle, maybe. In practice people mean that they can write program P in language A in n lines, whereas they need m lines to write P in language B, therefore A is better than B because m > n.

Which of course means nothing- I can probably write a hello world in 1000 lines in Java, if I try really hard. Just because I can find a shorter program in my favourite language but can't find one in yours, doesn't mean one doesn't exist. And even if you yourself can't find such a program, doesn't mean it doesn't exist.

That's what I mean by "arbitrary": in practice, people come up with whatever interpretation of "expressive" suits them to claim their favourite language is more of that.


> Just because I can find a shorter program in my favourite language but can't find one in yours, doesn't mean one doesn't exist. And even if you yourself can't find such a program, doesn't mean it doesn't exist.

This doesn't matter. Ordering all program strings by Kolmogorov complexity means you can find the shortest program that can produce a certain output string.


I suggest the string "The heat death of the universe should be anytime now".


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.


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


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/


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.


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.


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.


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/

(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.


How does this compare to Mercury?


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.


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.


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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: