Is findall/3 "Vienesse" despite being non-monotonic?

[jjtolton]

My understanding is that forall/3 findall/3 is not monotonic, yet I still see it widely used, even in Scryer code.

Is forall/3 findall/3 something to be embraced, or is it simply an expedient alternative that should be avoided in Viennese Prolog?

Edit: I meant findall/3 not forall/3.

[UWN]

You mean forall/2 probably. That's another influence.

[jjtolton]

Ack, I meant findall/3.

[UWN]

Using findall/3 means that all the burden of correctness is relegated to the programmer. It is particularly cumbersome if the answers found contain variables even more so when attached with constraints. Note that Scryer (like SICStus) does not copy the constraints

?- findall(X,dif(X,1),Xs).
   Xs = [_A].

But also in the case of ground answers (thus just solutions), the code remains non-monotonic.

(I am not so happy that you call this Viennese (or not). This is about program properties only, regardless where they came from. Maybe it is better to talk about purity, but then this is also overused)

[jjtolton]

Using findall/3 means that all the burden of correctness is relegated to the programmer.

Could you possibly explain a bit more? Is this not always the case (that the burden of correctness is relegated to the programmer)?

But also in the case of ground answers (thus just solutions), the code remains non-monotonic.

This is where I get confused. It seems to me this would mean "should be avoided whenever possible -- and it's always possible".

(I am not so happy that you call this Viennese (or not). This is about program properties only, regardless where they came from. Maybe it is better to talk about purity, but then this is also overused)

😅.

[bakaq]

"should be avoided whenever possible -- and it's always possible"

It's not always possible. What is true is that monotonic Prolog is Turing complete (that is, it can express every known computation), but that doesn't mean that you can do anything. brainfuck is also (famously) Turing complete, but you can't do networking with it. Monotonic Prolog struggles with side effects, and can't do things like reifying the number of solutions, both things that you might want to do.

For every non-trivial program you will may want to have a non-monotonic part at least for IO. The idea of "the Viennese school", at least how I understand it, is that you can encode your algorithm entirely in monotonic Prolog, and you get many benefits from that (declarative debugging, more general relations, alternative execution strategies, etc...). Given your algorithm implemented, you can then drop to a lower register of Prolog to get things that are impossible monotonically (get first solution with once/1, number of solutions with findall/3, unprovability with (\+)/1, etc...). Threading side-effects with the algorithm in this philosophy is very non-trivial, but probably possible (we really need an "non-deterministic IO Monad" for Prolog).

[jjtolton]

Perhaps this should be move to its own "monotonicity" thread -- monotonicity is an interesting constraint in that it seems to be a stronger constraint than purity.

In functional programming, it is generally accepted that it's possible to have a function that is internally impure (perhaps implemented with a mutational construct for efficiency), but as long as the side effects do not escape the scope of the function, then it does not impact the purity of the code in which it is situated, and is very often regarded as "pure" from a black-box perspective.

However, a non-monotonic predicate seems to be able to "corrupt" large chunks of code. A non-monotonic predicate will make the encapsulating scope also non-monotonic.

In functional programming, there are plenty of functional techniques (such as monads) to wrap impure sections of code and contain the impure side effects, but I know of know such logical analogues yet in Prolog.

This is why I am trying to be especially aware of the nuances, consequences, tradeoffs, and mitigations of nonmonotonic predicates (in this case, findall/3) because a single misplaced predicate can potentially deconsecrate an entire codebase!!

[UWN]

Could you possibly explain a bit more? Is this not always the case (that the burden of correctness is relegated to the programmer)?

As long as you stay in the pure subset many properties hold without any deeper analysis of your code.
Like, any generalization of a succeeding query will be true as well (or loop or produce some error — thus modulo non-termination and errors). But it will never ever fail. Outside of that subset it starts to get much more difficult. There ensuring that everything works as expected is now completely your burden.

?- X=2,findall(X,X=1,[]).
   X = 2.
?-     findall(X,X=1,[]). % generalization
   false.

[jjtolton]

That reddit post is so complete... what else is there to say 😍

[UWN]

The idea of "the Viennese school", at least how I understand it, is that you can encode your algorithm entirely in monotonic Prolog, ...

The idea is a little bit less ambitious. Just make the pure, monotonic part of Prolog stronger. As declared
2008, 2008, 2009 and some other places.