Comparison the power of swi-prolog's code

[Feofilakt Femistoklov]

Hello.

I'm attempting to compare the power and conciseness of swi-prolog with other languages. I found the example of calculating sum of even numbers. First, author presents the C code (recursive):

int evenSum(int *list) { return accumSum(0,list); } int accumSum(int n, int *list) { int x; int *xs; if (*list == 0) { // if the list is empty return n; } else { x = list[0]; // let x be the first element of the list xs = list+1; // let xs be the list without x if ( 0 == (x%2) ) { // if x is even return accumSum(n+x, xs); } else { return accumSum(n, xs); } } }

Then he converts it to haskell code:

evenSum :: [Integer] -> Integer evenSum l = accumSum 0 l accumSum n l = if l == [] then n else let x = head l xs = tail l in if even x then accumSum (n+x) xs else accumSum n xs

and after few steps we have final solution:

import Data.List (foldl') evenSum :: Integral a => [a] -> a evenSum = (foldl' (+) 0) . (filter even)

It is really impressive - one line of code, except import and unnecessary definition. And I'm interested, what is the shortest and most beautiful solution of that problem on swi-prolog? I have not enough knowledge yet, so my code will be much larger.

[Jan Wielemaker]

On 11/17/2015 08:46 AM, Feofilakt Femistoklov wrote:
> Hello.
> I'm attempting to compare the power and conciseness of swi-prolog with
> other languages. I found the example of calculating sum of even numbers.
> First, author presents the C code (recursive):

> int evenSum(int *list) { returnaccumSum(0,list); } int accumSum(int n,
> int *list) { intx; int*xs; if(*list== 0) { // if the list is
> emptyreturnn; } else{ x = list[0]; // let x be the first element of the
> listxs = list+1; // let xs be the list without xif( 0== (x%2) ) { // if
> x is evenreturnaccumSum(n+x, xs); } else{ returnaccumSum(n, xs); } } }

>
> Then he converts it to haskell code:
> evenSum:: [Integer] -> IntegerevenSuml = accumSum 0l accumSumn l = ifl

> == [] thenn elseletx = head l xs = tail l inifeven x thenaccumSum (n+x)
> xs elseaccumSum n xs

>
> and after few steps we have final solution:
> import Data.List (foldl')evenSum:: Integrala => [a] -> a evenSum=
> (foldl' (+) 0) . (filter even)
>
> It is really impressive - one line of code, except import and
> unnecessary definition. And I'm interested, what is the shortest and
> most beautiful solution of that problem on swi-prolog? I have not enough
> knowledge yet, so my code will be much larger.

See http://swish.swi-prolog.org/p/mcGWYKey.swinb

Cheers --- Jan

[Carlo Capelli]

Haskell is *very* concise - almost cryptic - and  you could also drop the type declarations, to get still shorter code.

In (SWI)Prolog, you have foldl also...

?- foldl(\A^B^C^(A mod 2 =:= 1 -> C is B+A ; C=B), [1,2,3,4,5], 0, R).

you need ?-pack_install(lambda). ?-[library(lambda)]. for this to work.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at http://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Carlo Capelli]

oops, bug bug bug ... it's computing odd numbers, not even

[Pierpaolo Bernardi]

No, your versions (Jan's and Carlo's) do not bomb out if the list
contains a 0, so they're not equivalent to the C one!

:)

[Jan Wielemaker]

On 11/17/2015 09:09 AM, Carlo Capelli wrote:
> Haskell is *very* concise - almost cryptic - and you could also drop
> the type declarations, to get still shorter code.
>
> In (SWI)Prolog, you have foldl also...
>
> ?- foldl(\A^B^C^(A mod 2 =:= 1 -> C is B+A ; C=B), [1,2,3,4,5], 0, R).
>
>
> you need ?-pack_install(lambda). ?-[library(lambda)]. for this to work.

Cute! Maybe I should add library(lambda) to SWISH?

I do prefer the other versions though :)

--- Jan

>
>
>
> 2015-11-17 8:46 GMT+01:00 Feofilakt Femistoklov

> <feofilaktf...@gmail.com <mailto:feofilaktf...@gmail.com>>:

>
> Hello.
> I'm attempting to compare the power and conciseness of swi-prolog
> with other languages. I found the example of calculating sum of even
> numbers. First, author presents the C code (recursive):

> int evenSum(int *list) { returnaccumSum(0,list); } int accumSum(int
> n, int *list) { intx; int*xs; if(*list== 0) { // if the list is
> emptyreturnn; } else{ x = list[0]; // let x be the first element of
> the listxs = list+1; // let xs be the list without xif( 0== (x%2) )

> { // if x is evenreturnaccumSum(n+x, xs); } else{ returnaccumSum(n,
> xs); } } }
>
> Then he converts it to haskell code:

> evenSum:: [Integer] -> IntegerevenSuml = accumSum 0l accumSumn l =
> ifl == [] thenn elseletx = head l xs = tail l inifeven x

> thenaccumSum (n+x) xs elseaccumSum n xs

>
> and after few steps we have final solution:

> import Data.List (foldl')evenSum:: Integrala => [a] -> a evenSum=

> (foldl' (+) 0) . (filter even)
>
> It is really impressive - one line of code, except import and
> unnecessary definition. And I'm interested, what is the shortest and
> most beautiful solution of that problem on swi-prolog? I have not
> enough knowledge yet, so my code will be much larger.
>
> --
> You received this message because you are subscribed to the Google
> Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it,
> send an email to swi-prolog+...@googlegroups.com

> <mailto:swi-prolog+...@googlegroups.com>.

> Visit this group at http://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.
>
>

> --
> You received this message because you are subscribed to the Google
> Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to swi-prolog+...@googlegroups.com

> <mailto:swi-prolog+...@googlegroups.com>.

[Wouter Beek]

On Tue, Nov 17, 2015 at 9:13 AM, Jan Wielemaker <J.Wiel...@vu.nl> wrote:

Cute!  Maybe I should add library(lambda) to SWISH?

Adding a datapoint:  I use Ulrich's lambda every day.​  I would appreciate it if it could be auto-loaded.

---
Best,

Wouter.

Email: w.g.j...@vu.nl

WWW: wouterbeek.com

Tel: +31647674624

[Jan Wielemaker]

On 11/17/2015 09:26 AM, Wouter Beek wrote:
> On Tue, Nov 17, 2015 at 9:13 AM, Jan Wielemaker <J.Wiel...@vu.nl
> <mailto:J.Wiel...@vu.nl>> wrote:
>
> Cute! Maybe I should add library(lambda) to SWISH?
>
> Adding a datapoint: I use Ulrich's lambda every day.​ I would
> appreciate it if it could be auto-loaded.

I still dislike the overhead of the copy_term/2 on every iteration used
by library lambda). Doing even_sum on a list 1..1000,000 requires (using
-O):

- Native: 0.128 sec.
- Using Lambda: 2.865 sec.

There seems to be a large demand for having something that avoids
the need for a explicit helper predicates. I see:

- Joachim Schimpf logical loops, developed for ECLiPSe, now also
in SICStus.
- Ulrich's Lambda. Seems quite widely used.
- Using Paulo's variation on the Lamdba that can be goal-expanded.
- Using B-Prolog list comprehension.

All except Ulrich's library(lambda) are compiled away and should
perform equally well. Otherwise I have these observations:

- Logical loops
+ Fairly ok syntax
+ Iterates over various `sets` (lists, compound arguments, ranges
of numbers)
+ Provides various accumulators.
+ Basically combines maplist, foldl and friends with an arbitrary
executable Prolog body.
- Implementation forces determinism in places this may not be
desired. Haven't checked whether that is needed by design or
just an implementation choice.
- Comes with primitives that abstract over the built-in set of
iterators and accumulators (that is a +), but this is rather
hard to grasp.
- Library Lambda
+ Elegant combination with call/N
+ Proper interaction with determinism
- Ugly syntax (might be personal)
- Slow
- Paulo's version
As Ulrich's, but compiled. I forgot which detail makes it less
clean but possible to compile under goal expansion.
- List comprehension
Similar in design to Logical loops AFAIK. No experience.

About half a year ago took logical loops from Joachim's original
version, adapted it to fit better into the SWI-Prolog compilation and
added some stuff SICStus added as well. Turned out there were some bugs.
Joachim told me to use the current source from ECLiPSe that should fix
this and add more iterators and accumulators.

I'm tempted to go for that because of the advantages above and the fact
that it would provide compatible support in three important Prolog
versions. That is not a standard yet, but at least moving somewhere.

Anything I missed?

Cheers --- Jan

[Paulo Moura]

> On 17/11/2015, at 10:27, Jan Wielemaker <J.Wiel...@vu.nl> wrote:
>
> On 11/17/2015 09:26 AM, Wouter Beek wrote:
>> On Tue, Nov 17, 2015 at 9:13 AM, Jan Wielemaker <J.Wiel...@vu.nl
>> <mailto:J.Wiel...@vu.nl>> wrote:
>>
>> Cute! Maybe I should add library(lambda) to SWISH?
>>
>> Adding a datapoint: I use Ulrich's lambda every day.​ I would
>> appreciate it if it could be auto-loaded.
>
> I still dislike the overhead of the copy_term/2 on every iteration used
> by library lambda). Doing even_sum on a list 1..1000,000 requires (using
> -O):
>
> - Native: 0.128 sec.
> - Using Lambda: 2.865 sec.

A benchmark example with compiled lambdas:

?- lambda_benchmarks::bench2.
Adding 1 to every integer in the list [1..100000] using a local add1/2 predicate:
% 200,001 inferences, 0.025 CPU in 0.036 seconds (71% CPU, 7916756 Lips)
Adding 1 to every integer in the list [1..100000] using map/3 with the integer::plus/3 predicate:
% 400,002 inferences, 0.072 CPU in 0.085 seconds (85% CPU, 5536590 Lips)
Adding 1 to every integer in the list [1..100000] using map/3 with a lambda argument with a is/2 goal:
% 300,001 inferences, 0.025 CPU in 0.025 seconds (100% CPU, 12211544 Lips)
true.

As we discussed before, compiling away sufficiently instantiated lambda expressions is key.

> There seems to be a large demand for having something that avoids
> the need for a explicit helper predicates. I see:
>
> - Joachim Schimpf logical loops, developed for ECLiPSe, now also
> in SICStus.
> - Ulrich's Lambda. Seems quite widely used.
> - Using Paulo's variation on the Lamdba that can be goal-expanded.

The variation is in syntax (as adding new operators was not an option given's Logtalk wide portability; thus, I reused existing standard operators). Using Carlo's example:

?- meta::fold_left([A,B,C]>>(B mod 2 =:= 1 -> C is B+A ; C=A), 0, [1,2,3,4,5], R).
R = 9.

> - Using B-Prolog list comprehension.
>
> All except Ulrich's library(lambda) are compiled away and should
> perform equally well. Otherwise I have these observations:
>
> - Logical loops
> + Fairly ok syntax
> + Iterates over various `sets` (lists, compound arguments, ranges
> of numbers)
> + Provides various accumulators.
> + Basically combines maplist, foldl and friends with an arbitrary
> executable Prolog body.
> - Implementation forces determinism in places this may not be
> desired. Haven't checked whether that is needed by design or
> just an implementation choice.
> - Comes with primitives that abstract over the built-in set of
> iterators and accumulators (that is a +), but this is rather
> hard to grasp.
> - Library Lambda
> + Elegant combination with call/N
> + Proper interaction with determinism
> - Ugly syntax (might be personal)
> - Slow
> - Paulo's version
> As Ulrich's, but compiled.

The compiler also warns you about unclassified variables and variables with dual role in lambda expressions. For example:

* Unclassified variable A in lambda expression: [B,C]>>f(B,C,A)
* in file /Users/pmoura/logtalk/examples/lambdas/lambdas.lgt between lines 197-199
* while compiling object warnings
* Variable A have dual role in lambda expression: {A}/[B,C,A]>>f(B,C,A)
* in file /Users/pmoura/logtalk/examples/lambdas/lambdas.lgt between lines 202-203
* while compiling object warnings

These are often (but not always) programmer errors.

> I forgot which detail makes it less
> clean but possible to compile under goal expansion.

No idea. Either you like or dislike the syntax :-)

> - List comprehension
> Similar in design to Logical loops AFAIK. No experience.
>
> About half a year ago took logical loops from Joachim's original
> version, adapted it to fit better into the SWI-Prolog compilation and
> added some stuff SICStus added as well. Turned out there were some bugs.
> Joachim told me to use the current source from ECLiPSe that should fix
> this and add more iterators and accumulators.
>
> I'm tempted to go for that because of the advantages above and the fact
> that it would provide compatible support in three important Prolog
> versions. That is not a standard yet, but at least moving somewhere.

It's also in Logtalk's TODO list for a long time :(

> Anything I missed?

Cheers,

Paulo

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

Email: <mailto:pmo...@logtalk.org>
Web: <http://logtalk.org/>
-----------------------------------------------------------------

[Jan Wielemaker]

On 11/17/2015 12:52 PM, Paulo Moura wrote:

>> On 17/11/2015, at 10:27, Jan Wielemaker <J.Wiel...@vu.nl> wrote:

>> - Native: 0.128 sec.
>> - Using Lambda: 2.865 sec.
>
> A benchmark example with compiled lambdas:
>
> ?- lambda_benchmarks::bench2.
> Adding 1 to every integer in the list [1..100000] using a local add1/2 predicate:
> % 200,001 inferences, 0.025 CPU in 0.036 seconds (71% CPU, 7916756 Lips)

You cheat :) You use 100,000 instead of 1,000,000 :) Anyway, a
compiled loop is a compiled loop. The details won't matter that much
unless you miss last-call optimization or determinism.

>> - Using Paulo's variation on the Lamdba that can be goal-expanded.
>
> The variation is in syntax (as adding new operators was not an option given's Logtalk wide portability; thus, I reused existing standard operators). Using Carlo's example:
>
> ?- meta::fold_left([A,B,C]>>(B mod 2 =:= 1 -> C is B+A ; C=A), 0, [1,2,3,4,5], R).
> R = 9.

I thought op/3 was standard. I guess you refer to the fact that
operators can be global or local in different systems and if there
are local operators they can behave in several ways? I'm tempted to
like >> better than ^ as it reminds me too much about setof/3
existential quantification.

Could it be the composability, as shown in this box in the lambda.pl
docs? I recall from long ago that there was something wrong with your
compilation in Ulrich's eyes (I may be wrong).

?- call(f,A1,A2).
?- call(\X^f(X),A1,A2).
?- call(\X^Y^f(X,Y), A1,A2).
?- call(\X^(X+\Y^f(X,Y)), A1,A2).
?- call(call(f, A1),A2).
?- call(f(A1),A2).
?- f(A1,A2).
A1 = x,
A2 = y.

>> I'm tempted to go for that because of the advantages above and the fact
>> that it would provide compatible support in three important Prolog
>> versions. That is not a standard yet, but at least moving somewhere.
>
> It's also in Logtalk's TODO list for a long time :(

Joachim's code is short and clean. At least, the original version :)

Cheers --- Jan

[Paulo Moura]

> On 17/11/2015, at 12:09, Jan Wielemaker <J.Wiel...@vu.nl> wrote:
>
> On 11/17/2015 12:52 PM, Paulo Moura wrote:
>
>>> On 17/11/2015, at 10:27, Jan Wielemaker <J.Wiel...@vu.nl> wrote:
>
>>> - Native: 0.128 sec.
>>> - Using Lambda: 2.865 sec.
>>
>> A benchmark example with compiled lambdas:
>>
>> ?- lambda_benchmarks::bench2.
>> Adding 1 to every integer in the list [1..100000] using a local add1/2 predicate:
>> % 200,001 inferences, 0.025 CPU in 0.036 seconds (71% CPU, 7916756 Lips)
>
> You cheat :) You use 100,000 instead of 1,000,000 :)

Is not even the same computation :-) Just the example I have handy and that anyone can trivially run as-is.

> Anyway, a compiled loop is a compiled loop. The details won't matter that much
> unless you miss last-call optimization or determinism.

Not a problem.

>>> - Using Paulo's variation on the Lamdba that can be goal-expanded.
>>
>> The variation is in syntax (as adding new operators was not an option given's Logtalk wide portability; thus, I reused existing standard operators). Using Carlo's example:
>>
>> ?- meta::fold_left([A,B,C]>>(B mod 2 =:= 1 -> C is B+A ; C=A), 0, [1,2,3,4,5], R).
>> R = 9.
>
> I thought op/3 was standard.

Of course! :-)

> I guess you refer to the fact that operators can be global or local in different systems and if there
> are local operators they can behave in several ways?

In part, yes. But Ulrich's syntax introduces new operators. The risk of conflict when you're targeting more than a dozen Prolog systems, not to mention user code, was too great for me to ignore and simply hope for the best. There's also the know issue with white-spaces in its syntax as well:

?- maplist(\(A-B)^(B-A)^true, [1-a,2-b,3-c], Zs).
false.

?- maplist(\ (A-B)^(B-A)^true, [1-a,2-b,3-c], Zs).
Zs = [a-1, b-2, c-3].

> I'm tempted to
> like >> better than ^ as it reminds me too much about setof/3 existential quantification.
>
> Could it be the composability, as shown in this box in the lambda.pl
> docs?

No. All those examples run perfectly. In fact, they are included in the Logtalk distribution in its "lambdas" example. Including the one you cite below.

> I recall from long ago that there was something wrong with your
> compilation in Ulrich's eyes (I may be wrong).

You're :-) Ulrich have been publicly spread FUD about Logtalk lambdas implementation since 2009. Is yet to provide any evidence of his claims.

> ?- call(f,A1,A2).
> ?- call(\X^f(X),A1,A2).
> ?- call(\X^Y^f(X,Y), A1,A2).
> ?- call(\X^(X+\Y^f(X,Y)), A1,A2).
> ?- call(call(f, A1),A2).
> ?- call(f(A1),A2).
> ?- f(A1,A2).
> A1 = x,
> A2 = y.

?- logtalk<<assertz(f(x, y)).
true.

?- logtalk<<call(f, A1, A2).

A1 = x,
A2 = y.

?- logtalk<<call([X]>>f(X), B1, B2).
B1 = x,
B2 = y.

?- logtalk<<call([X,Y]>>f(X,Y), C1, C2).
C1 = x,
C2 = y.

?- logtalk<<call([X]>>({X}/[Y]>>f(X,Y)), D1, D2).
D1 = x,
D2 = y.

?- logtalk<<call(call(f, E1), E2).
E1 = x,
E2 = y.

?- logtalk<<call(f(F1), F2).
F1 = x,
F2 = y.

Syntax variants are just syntax variants.

>>> I'm tempted to go for that because of the advantages above and the fact
>>> that it would provide compatible support in three important Prolog
>>> versions. That is not a standard yet, but at least moving somewhere.
>>
>> It's also in Logtalk's TODO list for a long time :(
>
> Joachim's code is short and clean. At least, the original version :)

Maybe this Christmas I will manage to find some free time to revisit his code.

[Markus Triska]

Hi Jan,

I strongly second the proposal to add library(lambda) to SWISH, since this short and elegant library is very widely used and its being available in SWISH would benefit many users tremendously!

In fact, I think SWI-Prolog would benefit significantly if library(lambda) were added to the core distribution: YAP also has it in the core already, so it would be great for compatibility if SWI would also have it.

Regarding the "do" loops that are available in Eclipse and SICStus Prolog, there are alas some quite troubling declarative deficits, at least in their current incarnation. For example, I strongly recommend to carefully study the revision that Mats Carlsson, the designer and main implementor of SICStus Prolog, made to one of his answers on Stackoverflow, removing an impure looping construct in order to obtain a more declarative and correct version of the code:

http://stackoverflow.com/posts/21604706/revisions

Mats is a great master of efficient Prolog implementation and desirable declarative properties, and such revisions and the discussions that lead to them quite clearly indicate some unsettled questions and are, in my view, reason enough to proceed very carefully with adding constructs that hurt declarative properties. Especially as these desirable properties are preserved with logically pure implementations such as library(lambda)!

I understand your efficiency concern. However, there may be a way to implement the construct faster. In comparison, what good is a fast construct that yields incorrect results when used in the wrong modes? In my experience, a slow and pure construct can often be salvaged by a more efficient implementation, but an impure construct can typically not be made pure, no matter how fast it is.

All the best!
Markus

[Jan Wielemaker]

Hi Markus,

I see the need for some library that fills this gap. library(lambda) in
its current form is not an option. I refuse to add a library that comes
with a 20 times slowdown for a simple loop. The construct should simply
come at no noticible overhead.

So, it won't go there unless at least someone writes a compiler for
them. Then still, the syntax is horrible and sensitive for hard to
explain places where you do/not need spaces. Paulo's syntax is a little
better. Apparently there is some unknown reason why Ulrich thinks it is
wrong ...

I consider logical loops more attractive right now. At a glance, I see
no reason why the logical loop construct needs cuts in the translation.


Cheers --- Jan

On 11/17/2015 06:43 PM, Markus Triska wrote:
> Hi Jan,
>
> I strongly second the proposal to add library(lambda) to SWISH, since
> this short and elegant library is very widely used and its being
> available in SWISH would benefit many users tremendously!
>
> In fact, I think SWI-Prolog would benefit significantly if
> library(lambda) were added to the core distribution: YAP also has it in
> the core already, so it would be great for compatibility if SWI would
> also have it.
>
> Regarding the "do" loops that are available in Eclipse and SICStus
> Prolog, there are alas some quite troubling declarative deficits, at
> least in their current incarnation. For example, I strongly recommend to
> carefully study the revision that Mats Carlsson, the designer and main
> implementor of SICStus Prolog, made to one of his answers on
> Stackoverflow, removing an impure looping construct in order to obtain a
> more declarative and correct version of the code:
>
> http://stackoverflow.com/posts/21604706/revisions
>

> Mats is a great master of efficient Prolog implementation /and/

> desirable declarative properties, and such revisions and the discussions
> that lead to them quite clearly indicate some unsettled questions and
> are, in my view, reason enough to proceed very carefully with adding
> constructs that hurt declarative properties. Especially as these
> desirable properties are preserved with logically pure implementations
> such as library(lambda)!
>
> I understand your efficiency concern. However, there may be a way to
> implement the construct faster. In comparison, what good is a fast
> construct that yields incorrect results when used in the wrong modes? In
> my experience, a slow and pure construct can often be salvaged by a more
> efficient implementation, but an impure construct can typically not be
> made pure, no matter how fast it is.
>
> All the best!
> Markus
>
>
> On Tuesday, November 17, 2015 at 11:27:12 AM UTC+1, Jan Wielemaker wrote:
>
> On 11/17/2015 09:26 AM, Wouter Beek wrote:

[Feofilakt Femistoklov]

People, you completely confused me. What libraries should I use, they are standard or not, what libraries are better, what is right and what is wrong, what are best practices... Now I understand why many beginners are disappointing in prolog. After learning how to solve famous logical puzzles and games (that are already solved billion times), beginner needs handy tools for routine practical problems (such like fold of a list) and best practices to use it, that are really hard to find. No one want write its own decision for every usual problem. Other languages show how easy they allow to solve standard tasks and, that are most important, only right way to do it, but swi-prolog don't. Do not misunderstand me please, I talk from a beginner's position.

[Boris Vassilev]

Hello Feofilact,

as a beginner, there is Stack Overflow, there is comp.lang.prolog, there is an IRC channel, and of course there are some nice online resources that teach basic Prolog, for example:

- Learn Prolog Now! (which now works with SWISH)

- The good old "99 Prolog Problems", to which there are plenty of solutions on top of the solutions that come with the problem statement

People have also written actual books about Prolog, the kind you find in libraries, for example, "The Art of Prolog" by Sterling and Shapiro (among others).

All of the pointers in this email is also available on the SWI-Prolog web site, not in one single spot, addmittedly, but between the very prominent "Tutorials" drop down menu and the FAQ you should be able to find all I have listed here. So this is before even doing a google search.

This list is (as you noticed) *not* the best place to ask general questions about Prolog syntax and getting hands on mentoring on solving basic programming problems. SWI-Prolog is one of many Prolog implementations.

What is very impressive, however, is that you got very good responses on the list.

Cheers,

Boris

Currently in the EEST time zone: This is UTC +3:00 (and I sleep at night)
Save our in-boxes! http://emailcharter.org

On Wed, Nov 18, 2015 at 5:27 AM, Feofilakt Femistoklov <feofilaktf...@gmail.com> wrote:

People, you completely confused me. What libraries should I use, they are standard or not, what libraries are better, what is right and what is wrong, what are best practices... Now I understand why many beginners are disappointing in prolog. After learning how to solve famous logical puzzles and games (that are already solved billion times), beginner needs handy tools for routine practical problems (such like fold of a list) and best practices to use it, that are really hard to find. No one want write its own decision for every usual problem. Other languages show how easy they allow to solve standard tasks and, that are most important, only right way to do it, but swi-prolog don't. Do not misunderstand me please, I talk from a beginner's position.

--

You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.

[Feofilakt Femistoklov]

Ok.

1. As a beginner, I know all resources that are useful to me. I able to google when I know how exactly formulate question, or I'm reading the book when I know the theme relative to my problem. And sometimes I asking at the forums, like now.

2. It does not matter, what do you think this list is the best place or *not* the best place for. "Welcome to the SWI-Prolog discussion forum.  Please use this forum to (1) ask questions how to solve programming problems in (SWI-)Prolog, (2) ask questions about porting and installation, (3) discuss best practices for applying Prolog, (4) announce your great library, application, etc., (5) discuss the future of (SWI-)Prolog or other topics of interest to the (SWI-)Prolog community." You can read it on http://www.swi-prolog.org/forum.

3. I'm comparing prolog (swi) and haskell now. For all aspects, especially for comfort learning. You can spend 5 minutes at the haskell's main page https://www.haskell.org/ and you will be sure that you shouldn't write your own realisations of list functions. You'll know about map, fold, etc. As for swi-prolog, you can use something like this (in better case):

even_sum([], 0).

even_sum([H|T], Sum) :-

    H mod 2 =:= 0, !,

    even_sum(T, Sum0),

    Sum is Sum0+H.

even_sum([_|T], Sum) :-

    even_sum(T, Sum).

for many years. I don't keep in mind this concrete functions, I attempt to say that learning swi-prolog and learning, how to write really good programs on swi prolog instead reinventing the wheel, are too much different things.

Sorry for wasting your time.

[Boris Vassilev]

I did not try to start an argument, just help. I am not certain what you mean by "As for swi-prolog, you can use something like this (in better case): <code snippet> for many years". The example you show here, from the SWISH notebook that Jan linked, is followed by two more examples, the second of those is not something you can easily do with Haskell anyway (as far as I know).

Good luck!

Currently in the EEST time zone: This is UTC +3:00 (and I sleep at night)
Save our in-boxes! http://emailcharter.org

--

[Julio Di Egidio]

On Wednesday, November 18, 2015 at 8:35:09 AM UTC, Feofilakt Femistoklov wrote:

> I'm comparing prolog (swi) and haskell now.

I think you should consider at least two facts:

1) Prolog and logic programming in general is an utterly different paradigm if you have never seen it before, so do not be disappointed if it involves a *significant* learning curve: IME, it takes weeks to get started, months to start getting things done, and years to become proficient with it.

2) You are comparing Prolog with Haskell, but Haskell is a functional language, so you are really comparing the proverbial apples and oranges...

HTH,

Julio

[Paulo Moura]

> On 17/11/2015, at 18:35, Jan Wielemaker <J.Wiel...@vu.nl> wrote:
>
> Hi Markus,
>
> I see the need for some library that fills this gap. library(lambda) in
> its current form is not an option. I refuse to add a library that comes
> with a 20 times slowdown for a simple loop. The construct should simply
> come at no noticible overhead.

I have written today a module library implementing Logtalk lambdas syntax (1), aptly named "yall" (yet another lambda library :-), and also wrote a patch for the "apply_macros" library to get rid of the overhead of using lambda expressions in maplist/N calls. A couple of examples:

----- test.pl
less(X, Y) :- X < Y.

a :- numlist(1, 100000, List), maplist(less(0), List).

b :- numlist(1, 100000, List), maplist([A]>>less(0, A), List).

add1(X, Y) :- Y is X + 1.

c :- numlist(1, 100000, List), maplist(add1, List, _).

d :- numlist(1, 100000, List), maplist([X,Y]>>(Y is X+1), List, _).
-----

?- use_module(library(apply_macros)).
true.

?- [yall].
true.

?- time(true).
% 2 inferences, 0.000 CPU in 0.000 seconds (62% CPU, 400000 Lips)
true.

?- time(a).
% 400,072 inferences, 0.029 CPU in 0.042 seconds (70% CPU, 13591249 Lips)
true.

?- time(b).
% 500,010 inferences, 0.021 CPU in 0.035 seconds (61% CPU, 23288775 Lips)
true.

?- time(c).
% 400,010 inferences, 0.031 CPU in 0.047 seconds (66% CPU, 12866609 Lips)
true.

?- time(d).
% 400,010 inferences, 0.040 CPU in 0.056 seconds (71% CPU, 10074042 Lips)
true.

A look behind the curtains (aka hackers porn :-):

?- listing(a/0).
a :-
numlist(1, 100000, A),
'__aux_maplist/2_less+1'(A, 0).

true.

?- listing('__aux_maplist/2_less+1'/2).
'__aux_maplist/2_less+1'([], _).
'__aux_maplist/2_less+1'([B|C], A) :-
less(A, B),
'__aux_maplist/2_less+1'(C, A).

true.

?- listing(b/0).
b :-
numlist(1, 100000, A),
'__aux_maplist/2___aux_lambda_1+0'(A).

true.

?- listing('__aux_maplist/2___aux_lambda_1+0'/1).
'__aux_maplist/2___aux_lambda_1+0'([]).
'__aux_maplist/2___aux_lambda_1+0'([A|B]) :-
'__aux_lambda_1'(A),
'__aux_maplist/2___aux_lambda_1+0'(B).

true.

?- listing('__aux_lambda_1'/1).
'__aux_lambda_1'(A) :-
less(0, A).

true.

?- listing(c/0).
c :-
numlist(1, 100000, A),
'__aux_maplist/3_add1+0'(A, _).

true.

?- listing('__aux_maplist/3_add1+0'/2).
'__aux_maplist/3_add1+0'([], []).
'__aux_maplist/3_add1+0'([A|C], [B|D]) :-
add1(A, B),
'__aux_maplist/3_add1+0'(C, D).

true.

?- listing(d/0).
d :-
numlist(1, 100000, A),
'__aux_maplist/3___aux_lambda_2+0'(A, _).

true.

?- listing('__aux_maplist/3___aux_lambda_2+0'/2).
'__aux_maplist/3___aux_lambda_2+0'([], []).
'__aux_maplist/3___aux_lambda_2+0'([A|C], [B|D]) :-
'__aux_lambda_2'(A, B),
'__aux_maplist/3___aux_lambda_2+0'(C, D).

true.

?- listing('__aux_lambda_2'/2).
'__aux_lambda_2'(B, A) :-
A is B+1.

true.

As you can see, there's still some room for improvement. Also, "apply_macros" currently optimizes maplist/N calls but not e.g. foldl/N calls. Logtalk's meta-compiler understand these and other common meta-predciates (foldr/N, scanl/N, scanr/N, partition/4, findall_member/4-5, include/3, exclude/3, and map_reduce/5). I'm quite busy with contract work but if someone is willing to help here please send me a private mail.

(1) Logtalk's lambda syntax in a nutshell:

{...}/[...]>>Goal

The {...} optional part is used for lambda-free variables. The order of variables doesn't matter hence the {...} set notation.

The [...] optional part lists lambda parameters. Here order of variables matters hence the list notation.

Both (/)/2 and (>>)/2 are standard operators so no new operators are added. An advantage of this syntax is that we can simply unify a lambda expression with Free/Parameters>>Lambda to access each of its components. Spaces in the lambda expression are not a problem although the goal may need to be written between ()'s.

[Feofilakt Femistoklov]

I did not try to start an argument, just help. I am not certain what you mean by "As for swi-prolog, you can use something like this (in better case): <code snippet> for many years". The example you show here, from the SWISH notebook that Jan linked, is followed by two more examples, the second of those is not something you can easily do with Haskell anyway (as far as I know).

Good luck!

Thank you. I mean, it is hard for beginner to find right functions and libraries, so he writes his own realizations. In that SWISH link the first code snippet is bad and followed by good examples. I read many materials about prolog but I never met this good example before. Probably, it because there are many implementations of prolog, and authors do not present useful functions and tricks in their papers, only common things that are in any prolog.

I think you should consider at least two facts:
1) Prolog and logic programming in general is an utterly different paradigm if you have never seen it before, so do not be disappointed if it involves a *significant* learning curve: IME, it takes weeks to get started, months to start getting things done, and years to become proficient with it.
2) You are comparing Prolog with Haskell, but Haskell is a functional language, so you are really comparing the proverbial apples and oranges...
HTH,
Julio

1) I think, you are overestimating the logic paradigm, like many adepts. It is just a programming paradigm, with advantages and disadvantages. For man who never seen OOP either LP, this two paradigms will be same difficult. Logic paradigm is not so hard, just unaccustomed.

2) I know all of it :) I have my own criteria. For example, the C code in my first message is worse than haskell code below (but I know that C is better than haskell in space of driver writing, for example). Now I want to find out, what code - on haskell or on prolog - is more good-looking for me.

[Markus Triska]

Hi,

On Thursday, 19 November 2015 04:23:27 UTC+1, Feofilakt Femistoklov wrote:

Thank you. I mean, it is hard for beginner to find right functions and libraries, so he writes his own realizations. In that SWISH link the first code snippet is bad and followed by good examples. I read many materials about prolog but I never met this good example before. Probably, it because there are many implementations of prolog, and authors do not present useful functions and tricks in their papers, only common things that are in any prolog.

Yes, that (i.e., trying to ensure compatibility with other systems as far as possible) is one of the reasons why several Prolog programmers do not use or present some of the features that were added to several Prolog systems within the last years and decades. Compatibility is definitely a good goal. On the other hand, the more widely used a feature is, the more other systems will adapt it too, so I encourage you to also try out and study features that are only available in a small minority of implementations.

But also take into account other human factors: Prolog is a language with a long tradition. If you have been using Prolog for, say, 30 years, then it will be hard initially for you to fully embrace a feature that was added within the last, say, 2, 5 or 8 years, no matter how useful it is and how much sense it makes to adopt it in your work.

Take CLP(FD) constraints as a single example: It is easy for you, as a beginner, to understand constraints and use them, and you would not want to code in Prolog without them (see the DCG question for example). Yet, I assure you that people who have only slightly more experience than you will go out of their way to argue (and I am using the word loosely) against using constraints in exactly those cases you need.

Why? Nobody cares: As in other disciplines, such issues are solved in ways that are more biological, rather than logical, in nature. The Prolog lecture material you will see in another 20 years will look very different from the material we see today, since more advanced features of Prolog will be more widely known and taken for granted then, and the teaching material will evolve accordingly to higher and higher standards.

All the best!
Markus

[Feofilakt Femistoklov]

It is the most sensible description of the prolog (not as tool of the logic programming paradigm, but as a programming language) that I have ever seen. Thank you.

[Wouter Beek]

​Hi Markus, others,​

On Thu, Nov 19, 2015 at 8:01 AM, Markus Triska <tri...@logic.at> wrote:

Take CLP(FD) constraints as a single example: It is easy for you, as a beginner, to understand constraints and use them, and you would not want to code in Prolog without them (see the DCG question for example). Yet, I assure you that people who have only slightly more experience than you will go out of their way to argue (and I am using the word loosely) against using constraints in exactly those cases you need.

​Are there not very clear performance issues with using constraints?  I will use an example you gave earlier:

```
as(0) --> [].
as(N) --> {N #> 0, N #= N0 + 1}, [a], as(N0).
```

The above code is declarative, aesthetically pleasing and plays well with constraints (which are all great benefits!).  Let's compare it to some ugly code that I would write if I were in a hurry and has to process a ton of data:

```
as_ugly(N) --> as_ugly(0, N).
as_ugly(N, N) --> [].
as_ugly(N1, N) --> {(nonvar(N) -> N1 =< N ; true)}, [a], {N2 is N1 + 1}, as_ugly(N2, N).
```

Many people, when given the option to choose between the above two code snippets, would go for the one that is more performant:

​```

?- time(phrase(as_ugly(1000000), Cs)), time(phrase(as_ugly(N), Cs)).
% 5,000,001 inferences, 0.619 CPU in 0.620 seconds (100% CPU, 8077299 Lips)
% 4,000,001 inferences, 0.506 CPU in 0.507 seconds (100% CPU, 7903051 Lips)
Cs = [a, a, a, a, a, a, a, a, a|...],
N = 1000000

?- time(phrase(as(1000000), Cs)), time(phrase(as(N), Cs)).
% 168,000,000 inferences, 18.958 CPU in 18.978 seconds (100% CPU, 8861660 Lips)
% 400,278,639 inferences, 169.491 CPU in 169.671 seconds (100% CPU, 2361658 Lips)
ERROR: Out of global stack
```

I believe CLP(FD) is a /huge/ innovation.  I use it on a weekly if not daily basis.  But as soon as I start to process larger amounts of data I find myself going back to the code and trading declarativeness for speed.  Do you believe these performance issues can be resolved over time?  If that could be the case then I see no further reason to not simple replace is/2 with #=/2 in all Prolog implementations everywhere.

---
Best,

Wouter.

[Feofilakt Femistoklov]

?- time(phrase(as_ugly(1000000), Cs)), time(phrase(as_ugly(N), Cs)).

% 5,000,001 inferences, 0.619 CPU in 0.620 seconds (100% CPU, 8077299 Lips)
% 4,000,001 inferences, 0.506 CPU in 0.507 seconds (100% CPU, 7903051 Lips)
Cs = [a, a, a, a, a, a, a, a, a|...],
N = 1000000

?- time(phrase(as(1000000), Cs)), time(phrase(as(N), Cs)).
% 168,000,000 inferences, 18.958 CPU in 18.978 seconds (100% CPU, 8861660 Lips)
% 400,278,639 inferences, 169.491 CPU in 169.671 seconds (100% CPU, 2361658 Lips)
ERROR: Out of global stack
```

I believe CLP(FD) is a /huge/ innovation.  I use it on a weekly if not daily basis.  But as soon as I start to process larger amounts of data I find myself going back to the code and trading declarativeness for speed.  Do you believe these performance issues can be resolved over time?  If that could be the case then I see no further reason to not simple replace is/2 with #=/2 in all Prolog implementations everywhere.

---
Best,

Wouter.

Why such a difference in performance?

[Julio Di Egidio]

On Thursday, November 19, 2015 at 8:16:10 AM UTC, Wouter Beek wrote:

Do you believe these performance issues can be resolved over time?  If that could be the case then I see no further reason to not simple replace is/2 with #=/2 in all Prolog implementations everywhere.

But you have to keep in mind that  is/2 is not simply some kind of limited version of #=/2: it is rather a functional thing.  IOW, declarative integer arithmetic is fine as long as the underlying notion is that of *relations*, but I would suggest it is not the way to go if the underlying notion rather is one of pure *functions*...  No?

Julio

[Markus Triska]

Hi Wouter, all,

On Thursday, November 19, 2015 at 9:16:10 AM UTC+1, Wouter Beek wrote:

I believe CLP(FD) is a /huge/ innovation.  I use it on a weekly if not daily basis.  But as soon as I start to process larger amounts of data I find myself going back to the code and trading declarativeness for speed.  Do you believe these performance issues can be resolved over time?  If that could be the case then I see no further reason to not simple replace is/2 with #=/2 in all Prolog implementations everywhere.

I recommend you simply do exactly what you say: Use CLP(FD) constraints for all integer arithmetic, i.e., replace (is)/2 by (#=)/2, and replace (=<)/2 by the CLP(FD) constraint (#=<)/2 in your example to obtain:

:- use_module(library(clpfd)).

as(N) --> as(0, N).

as(N, N) --> [].
as(N1, N) --> {(nonvar(N) -> N1 #=< N ; true)}, [a], {N2 #= N1 + 1}, as(N2, N).

Timing with the CLP(FD) version:

?- time(phrase(as_ugly(1000000), Cs)), time(phrase(as_ugly(N), Cs)).

5,000,001 inferences, 0.437 CPU in 0.437 seconds (100% CPU, 11452954 Lips)

2,000,001 inferences, 0.172 CPU in 0.172 seconds (100% CPU, 11641945 Lips)

The performance difference to low-level integer arithmetic is well within a factor of 2 in this example (more like 1.6). In many other examples, it will be much lower than that. Also for didactic reasons, consider using CLP(FD) constraints throughout your programs for all integer arithmetic, especially if you are already using CLP(FD) constraints in other parts of your program. It makes no sense to teach two types of predicates to beginners, as the benefits of the pure CLP(FD) predicates outweigh their costs (overhead typically well within a factor of 2) so significantly, and CLP(FD) constraints are the more general solution that is far easier to understand.

Note that I am not saying that all versions of your code will be equally efficient if they just all use CLP(FD) constraints. They won't, as these examples nicely prove. However, that's nothing unusual: Your impure and lower-level variants won't all be equally efficient either, assuming you even get them to work correctly.

We all see that the above code is not the most declarative and pure, but at least we have not fallen even lower! Don't throw everything away just because you lost one part. Start with using CLP(FD) constraints for integer arithmetic (which is easy), and proceed from there to purer and purer solutions. In a pace that gives other users a chance to come along.

For now, just consider the simple principle: For integer arithmetic, (is)/2 can always be replaced by (#=)/2 with typically very acceptable overhead. That's one of the most important design goals of library(clpfd). After all, who wants to use Prolog without proper support for integers??

All the best,
Markus

[Julio Di Egidio]

On Thursday, November 19, 2015 at 4:22:45 PM UTC, Markus Triska wrote:

For now, just consider the simple principle: For integer arithmetic, (is)/2 can always be replaced by (#=)/2 with typically very acceptable overhead. That's one of the most important design goals of library(clpfd). After all, who wants to use Prolog without proper support for integers??

But you have to keep in mind that  is/2 is not simply some kind of limited version of #=/2: it is rather a functional thing.  IOW, declarative integer arithmetic is fine as long as the underlying notion is that of *relations*, but I would suggest it is *not* the way to go if the underlying notion rather is one of pure *functions*...  No?

(Indeed performance is the *last* problem.)

Julio

[Wouter Beek]

Hi Markus,

Thank you for your insightful answer!  I would like to be able to program in a paradigm that I will call pure+performant logic programming (for lack of a better term).

The way I see it, writing a pure+perform program consists of the following steps:

  1. You come up with a declarative implementation that has the correct behavior, that can be analyzed, and that is generally short and easy to understand.

  2. Test (1) and find out that it goes out of memory or takes to long to computer for larger input sizes.

  3. Come up with a couple of imperative adaptations of (1) that trade declarativeness for performance.

  4. Go through (2) -> (3) -> (2) etc. until time and space seem to be acceptable.

In order to ease the (2) -> (3) -> (2) iteration it may be a good idea to add the following step as well:
  0. Write a bunch of scalability test cases that cover all instantiations.  The test cases should not only be intended to determine correctness but also performance.  This means that they should contain significantly larger inputs then is usually the case with e.g. unit tests.

In our little example we would write the following in step (1):

    as(0) --> [].
    as(N) --> {N #> 0, N #= N0 + 1}, [a], as(N0).

And then in step (4) we would end up with:

    as(N) --> as(0, N).
    as(N, N) --> [].
    as(N1, N) --> {(nonvar(N) -> N1 #=< N ; true)}, [a], {N2 #= N1 + 1}, as(N2, N).

We keep the result of step (1) around because that is what we actually wanted to write.  We can use it to explain the intended purpose of the program, we can use it for educational purposes when the input argument is small, we might recheck the performance of (1) in a future Prolog that is more performant, etc.

Do you know of techniques / tools that may ease the above outlined program development approach?

---
Best,

Wouter.

Email: w.g.j...@vu.nl

WWW: wouterbeek.com

Tel: +31647674624

[Wouter Beek]

​Hi Julio,

​

On Thu, Nov 19, 2015 at 6:06 PM, Julio Di Egidio <ju...@diegidio.name> wrote:

But you have to keep in mind that  is/2 is not simply some kind of limited version of #=/2: it is rather a functional thing.  IOW, declarative integer arithmetic is fine as long as the underlying notion is that of *relations*, but I would suggest it is *not* the way to go if the underlying notion rather is one of pure *functions*...  No?

​I'm sorry I do not get this point.​  Can you expand on it or give an example?  I'm not sure what a pure function is.

(Indeed performance is the *last* problem.)

​FMPOV that depends a lot on the use case.  I want to perform non-trivial reasoning over a collection of 40 billion ground statements.  That does generally not work with non-performant tools.

[Julio Di Egidio]

On Thursday, November 19, 2015 at 7:01:35 PM UTC, Wouter Beek wrote:

> ​

On Thu, Nov 19, 2015 at 6:06 PM, Julio Di Egidio <ju...@diegidio.name> wrote:

But you have to keep in mind that  is/2 is not simply some kind of limited version of #=/2: it is rather a functional thing.  IOW, declarative integer arithmetic is fine as long as the underlying notion is that of *relations*, but I would suggest it is *not* the way to go if the underlying notion rather is one of pure *functions*...  No? 

​I'm sorry I do not get this point.​  Can you expand on it or give an example?  I'm not sure what a pure function is.

A pure function is something that given an input returns one and only one output: you can think of it as corresponding to a deterministic predicate (given that e.g. user-defined arithmetic functions are generally not allowed, and certainly not allowed in SWI, otherwise these would be a more direct example of pure (user-defined) functions.)

That said, you should rather realise that "declarative+pure" [where "pure" for Prolog instead means just Horn clauses with not even cuts] is just a *strict subset* of all of computation, not to mention that "pure Prolog" is already completely a red herring: that is rather called Datalog, and it is not even Turing complete!  It is not per chance that Markus just keeps reiterating his slogans with not even a shadow of actual arguments...

(Indeed performance is the *last* problem.)

​FMPOV that depends a lot on the use case.  I want to perform non-trivial reasoning over a collection of 40 billion ground statements.  That does generally not work with non-performant tools.

Note that I did not say performance does not matter, I said it comes last.  It is indeed a general engineering (construction) indication: that first of all you have to write code properly, and only after, and only if you do get into performance bottlenecks, you would care to address those specific problems: the main point and indication being that, if you write code properly (and assuming the platform is decent enough), 80% of the problems, of performance or otherwise, simply do not arise at all...

Julio

[Stefan Kral]

On Thursday, November 19, 2015 at 10:05:37 PM UTC+1, Julio Di Egidio wrote:
> That said, you should rather realise that "declarative+pure"
> [where "pure" for Prolog instead means just Horn clauses with not even cuts]
> is just a *strict subset* of all of computation, not to mention that
> "pure Prolog" is already completely a red herring:
> that is rather called Datalog, and it is not even Turing complete! 

I do not get your message. Are you saying that pure Prolog is not Turing-complete? And that pure Prolog is Datalog? Please clarify.

Cheers, Stefan.

[Stefan Kral]

On Tuesday, November 17, 2015 at 9:26:51 AM UTC+1, Wouter Beek wrote:
> On Tue, Nov 17, 2015 at 9:13 AM, Jan Wielemaker <J.Wiel...@vu.nl> wrote:
> Cute!  Maybe I should add library(lambda) to SWISH?
> Adding a datapoint:  I use Ulrich's lambda every day.​  I would appreciate it if it could be auto-loaded.

Same for me. I definitely miss lambda in swish!

Cheers, Stefan.