Confusing aggregation docu (library(aggregate))

[Jan Burse]

Dear All,

Just trying to figure out what the different aggregate
predicates do (*). So I find the following bootstrapping:

bagof(X, G, B) :- aggregate(bag(X), G, L).
setof(X, G, B) :- aggregate(set(X), X, G, L).

But this is somehow inconsistent with what I later read.
Namely I find:

aggregate(+Template, :Generator, -Result)
is a generalisation of findall/3 which lets you
compute sums, minima, maxima, and so on.

I understand the above that aggregate/3 calls something
similar to findall/3 under the hood. But I think this is
impossible since the above bootstrapping shows how
aggregate/3 can be used to define bagof/3.

Can somebody enlighten me?

Bye

(*)
http://www.sics.se/sicstus/docs/4.2.0/html/sicstus/lib_002daggregate.html

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message
news:k4ehls$urk$1...@news.albasani.net...

> Just trying to figure out what the different aggregate
> predicates do (*). So I find the following bootstrapping:
>
> bagof(X, G, B) :- aggregate(bag(X), G, L).
> setof(X, G, B) :- aggregate(set(X), X, G, L).

What do you mean by bootstrapping? I'd just take those as informal for
"bagof/setof *is as*...". But I concur it may be confusing: at a quick
skimming, I have found no such convention stated anywhere in the Sicstus
docs.

-LV

(*)
<http://www.sics.se/sicstus/docs/4.2.0/html/sicstus/lib_002daggregate.html>

[Jan Burse]

LudovicoVan schrieb:

>
> What do you mean by bootstrapping?

Not necessary actual but potential definition of
a built-in or library predicate by other built-in
or library predicates.

The term "bootstrapping" is used in some places
of Prolog ISO core standard, for example here:

8.14.2.5 Bootstrapped built-in predicates

The built-in predicates write-term/2, write/l,
write/a, writeq/l, writeq/2, write-canonical/l,
and write-canonical/2 all provide similar functionality
to write-term/3.

[...]

write-term(Term, Options) :-
current-output(S),
write-term(S, Term, Options).

write(Term) :-
current-output(S),
write-term(S, Term, [numbervars(true) I).

[...]

And then later:

A.1.4 About the style of the Formal Specification

The systematic use of “special predicates” where
bootstrapped or auxiliary definitions are given is
necessary to avoid clashes of names with user-defined
predicates. In fact “bootstrapping” consists of
adding to the initial complete database new predicate
definitions. In the case of bootstrapped control
construct or built-in predicates this is not needed
because they cannot be redefined by the user.

[Jan Burse]

LudovicoVan schrieb:

> I'd just take those as informal for "bagof/setof *is as*...".

Which begs the question whether the docu for aggregate/3
is adequate. This is what I am interested in.

Bye

[Jan Burse]

Jan Burse schrieb:

> Which begs the question whether the docu for aggregate/3
> is adequate. This is what I am interested in.

>> aggregate(+Template, :Generator, -Result)
>> is a generalisation of findall/3 which lets you
>> compute sums, minima, maxima, and so on.

There is more evidence that aggregate/3 is not based on
a findall/3 variant. For example the first given example
uses quantification via (^)/2:

dept_office_area(Dept, TotalArea) :-
aggregate(sum(Area),
I^O^office(I,Dept,Area,O), TotalArea).

If aggregate/3 where based on a findall/3 variant, the (^)/2
would be meaningless to it. So why is there an example of
aggregate/3 that uses (^)/2?

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4ekcm$4kl$1...@news.albasani.net...
> LudovicoVan schrieb:
<snipped>

>> What do you mean by bootstrapping?

> The term "bootstrapping" is used in some places
> of Prolog ISO core standard, for example here:

Thanks: I had bought the standard then my disk crashed (yeah, please don't
remind me about backups...) and now I should buy it again...!!

Doesn't it suck that the Prolog language is beautiful and so expressive, but
just there is nothing even near to an acceptable state of affairs in order
to make commercial, industry level products out of it? Engineering is all
about standardization, and I won't even get into how the current standard is
not even good enough to implement a fully conformant parser...

End of rant.

-LV

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4ekt1$4kl$3...@news.albasani.net...

> Jan Burse schrieb:

>> Which begs the question whether the docu for aggregate/3
>> is adequate. This is what I am interested in.

I had conceded on that: you have just snipped it.

> >> aggregate(+Template, :Generator, -Result)
> >> is a generalisation of findall/3 which lets you
> >> compute sums, minima, maxima, and so on.
>
> There is more evidence that aggregate/3 is not based on
> a findall/3 variant.

You don't need any evidence, what else could that mean if not the obvious
that I have explained up-thread?

IOW, your post here boils down to complaining about the Sicstus docs,
nothing more that I can see.

-LV

[Jan Burse]

LudovicoVan schrieb:

> IOW, your post here boils down to complaining about the Sicstus docs,
> nothing more that I can see.

Let me complain that you complain that I ask for enlightment,
whereby you see it as complaining.

BTW: SWI Prolog didn't make the mistake, at least now it reads:

aggregate(+Template, :Goal, -Result)
Aggregate bindings in Goal according to Template. The
aggregate/3 version performs bagof/3 on Goal.

http://www.swi-prolog.org/pldoc/doc_for?object=section%282,%27A.1%27,swi%28%27/doc/Manual/aggregate.html%27%29%29

So I guess it is true, also for SICStus most probably, that
aggregate/3 is based on bagof/3 and not on findall/3.

The issue has never been, this is never my intention, to show
that some standard is useless or that some product is useless.
In the present case, the standard is not involved since ISO
doesn't deal with aggregates. And the quality of a product
doesn't primarily reside in its documentation. Last
but not least:

- The Prolog ISO core standard is a great spec.

- SICStus Prolog is a great product.

I needed an enlightment because I wonder how to implement
aggregate/3 by myself. But it really looks like a case for
captain obvious.

Bye

[Jan Burse]

Jan Burse schrieb:

> But it really looks like a case for
> captain obvious.

Well he didn't fly by.

http://i0.kym-cdn.com/photos/images/original/000/067/034/633800769542445665-CAPTAINOBVIOUS.jpg

(LudovicoVan's comment probably meant that the bootstrapping
is wrong, but according to the SWI Prolog explanation of
aggregate/3 it would be correct. And why should SICStus
publish a wrong bootstrapping, isn't the error probability
in documentation higher for verbal text than for formal
statements?)

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4esug$miv$1...@news.albasani.net...

> LudovicoVan schrieb:
>
>> IOW, your post here boils down to complaining about the Sicstus docs,
>> nothing more that I can see.
>
> Let me complain that you complain that I ask for enlightment,
> whereby you see it as complaining.

You are cheating your way out here: just re-read your subject line.

> BTW: SWI Prolog didn't make the mistake, at least now it reads:
>
> aggregate(+Template, :Goal, -Result)
> Aggregate bindings in Goal according to Template. The
> aggregate/3 version performs bagof/3 on Goal.
>
> http://www.swi-prolog.org/pldoc/doc_for?object=section%282,%27A.1%27,swi%28%27/doc/Manual/aggregate.html%27%29%29

SWI is better in that it states explicitly, wherever needed, the "is as" I
had mentioned initially. (But, as said, I do not have any significant
experience with Sicstus, hence I could just have overlooked something in its
documentation: just as you could.)

> So I guess it is true, also for SICStus most probably, that
> aggregate/3 is based on bagof/3 and not on findall/3.

That one is specified precisely enough: look at the docs again.

> The issue has never been, this is never my intention, to show
> that some standard is useless or that some product is useless.

I didn't say otherwise.

> In the present case, the standard is not involved since ISO

But you mentioned "bootstrapping", remember? And on *that* sub-thread I
have made my rant, on the ISO standard indeed: its contents and the very
policies and strategies behind it. And I stand by my opinion, which is not
that of an expert logical programming theorist or similar, rather it is that
of a seasoned software and systems engineer who would actually love to build
industry level applications with this stuff, if this were at all possible.

> doesn't deal with aggregates. And the quality of a product
> doesn't primarily reside in its documentation.

Documentation *is* (not alone of course) primary, as you would know if you
were building software for a living (and this means, not only yours).

> Last but not least:
>
> - The Prolog ISO core standard is a great spec.

It just sucks, the thingy and the whole strategy: made so that you just
won't be able to build systems unless you adopt this or that proprietary
framework (or unless you have *lots* of money to invest up-front, which no
investor would allow, given the total lack of any of the industrial
requirements for any business project to be justified). These are simply
closed commercial policies, and be sure that Prolog is not the only example
of such.

> - SICStus Prolog is a great product.

Never claimed otherwise. I have never claimed anything at all about the
quality of Sicstus, actually.

> I needed an enlightment because I wonder how to implement
> aggregate/3 by myself. But it really looks like a case for
> captain obvious.

Oh, I'd agree on that: in any case, asking about what you are interested in
rather than reporting problems with -say- the Sucstus docs, may work way
better for that purpose. IMHO.

-LV

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4etej$nkd$1...@news.albasani.net...

> Jan Burse schrieb:
>> But it really looks like a case for
>> captain obvious.
>
> Well he didn't fly by.
>
> http://i0.kym-cdn.com/photos/images/original/000/067/034/633800769542445665-CAPTAINOBVIOUS.jpg
>
> (LudovicoVan's comment probably meant that the bootstrapping
> is wrong

Then I must conclude you cannot even read... Just kidding, but that is
really out of the blue.

-LV

[Jan Burse]

LudovicoVan schrieb:

> Oh, I'd agree on that: in any case, asking about what you are interested
> in rather than reporting problems with -say- the Sucstus docs, may work
> way better for that purpose. IMHO.

Well there a grammar nazis and newsgroup nazis. I hate both.

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4euin$q0q$1...@news.albasani.net...

You are still cheating your way out, now down to the plain personal offense.
To which I have to retort: you aren't as smart as you think...

Bye,

-LV

[Jan Burse]

LudovicoVan schrieb:

> It just sucks, the thingy and the whole strategy: made so that you just
> won't be able to build systems unless you adopt this or that proprietary
> framework (or unless you have *lots* of money to invest up-front, which
> no investor would allow, given the total lack of any of the industrial
> requirements for any business project to be justified). These are
> simply closed commercial policies, and be sure that Prolog is not the
> only example of such.

You must be kidding? You have open source SWI Prolog, tuProlog, etc..
Many Books publish the code of an Interpreter. There are cross
implementations in Closure, Scala, Haskell, etc..

Prolog in Haskell
http://www.cs.uu.nl/research/techreps/UU-CS-1999-28.html

Prolog in JavaScript
http://ioctl.org/logic/prolog1

Prolog in Scala
https://github.com/sonoisa/Prolog-in-Scala/blob/master/PrologInScalaSample.scala

Prolog in Scheme
http://lambda-the-ultimate.org/node/1104

Etc..

Prolog ist the most open technology I have ever seen. And the
ISO core standard does also a very good job in specifying the
exact behaviour of an interpreter. Further there are tons of
papers and there is WAM, etc...

[Jan Burse]

LudovicoVan schrieb:
> You are still cheating your way out here: just re-read your subject line.

Alone this statement above licenses me to doubt your motives.
It sounds really stupid to me to argue from subject lines,
and ignore the whole text of a post. Next time I will only
post a subject line, and not go into the length of explaining
what I really want to know. This will give me sure a better
recall... Ha Ha

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4evd5$rjj$1...@news.albasani.net...

> LudovicoVan schrieb:
>
>> It just sucks, the thingy and the whole strategy: made so that you just
>> won't be able to build systems unless you adopt this or that proprietary
>> framework (or unless you have *lots* of money to invest up-front, which
>> no investor would allow, given the total lack of any of the industrial
>> requirements for any business project to be justified). These are
>> simply closed commercial policies, and be sure that Prolog is not the
>> only example of such.
>
> You must be kidding?
>
> You have open source SWI Prolog, tuProlog, etc..

You just don't know what you are talking about, down there in your golden
Uni cubicle (just guessing, I don't know you personally, of course). I
won't get into a detailed criticism here, there is really no point, but just
note that there is no common, solid (yeah, you won't agree, my young
apprentice), and publicly available standard, and this is already a full
show-stopper as far as large-scale industrial adoption is concerned.

-LV

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4evk4$s8c$1...@news.albasani.net...

> LudovicoVan schrieb:
>
>> You are still cheating your way out here: just re-read your subject line.
>
> Alone this statement above licenses me to doubt your motives.

You are a cheater.

-LV

[Jan Burse]

Hi,

> You just don't know what you are talking about, down there in your
> golden Uni cubicle (just guessing, I don't know you personally, of
> course).

No, I don't ordain an university.

LudovicoVan schrieb:

> I won't get into a detailed criticism here, there is really no point,
> but just note that there is no common, solid (yeah, you won't agree, my
> young apprentice), and publicly available standard, and this is already
> a full show-stopper as far as large-scale industrial adoption is concerned.

I don't have an opinion about large-scale industrial adoption.

Bye

[Jan Burse]

LudovicoVan schrieb:
>
> You are a cheater.

Of course you are right.

[Ulrich Neumerkel]

"LudovicoVan" <ju...@diegidio.name> writes:
>"Jan Burse" <janb...@fastmail.fm> wrote in message
>news:k4ekcm$4kl$1...@news.albasani.net...
>> LudovicoVan schrieb:
><snipped>
>
>>> What do you mean by bootstrapping?
>
>> The term "bootstrapping" is used in some places
>> of Prolog ISO core standard, for example here:
>
>Thanks: I had bought the standard then my disk crashed (yeah, please don't
>remind me about backups...) and now I should buy it again...!!

You get the standard for such a low price that typing your remark
costs you more than paying for a new copy.

>Doesn't it suck that the Prolog language is beautiful and so expressive, but
>just there is nothing even near to an acceptable state of affairs in order
>to make commercial, industry level products out of it? Engineering is all
>about standardization, and I won't even get into how the current standard is
>not even good enough to implement a fully conformant parser...

Have a look at the current difference between systems:

http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment

That is much better than ever before. Consider the differences:
whenever systems differ from the standard, they frequently differ to
each other as well.

Please remember that most entries in this table were added because some
systems were different. So the table shows you only the things that
do not work in some system or another. The table does not show you
were systems work, but there things are taken for granted, aren't they?

[Ulrich Neumerkel]

Jan Burse <janb...@fastmail.fm> writes:
>LudovicoVan schrieb:
>>
>> What do you mean by bootstrapping?
>
>Not necessary actual but potential definition of
>a built-in or library predicate by other built-in
>or library predicates.
>
>The term "bootstrapping" is used in some places
>of Prolog ISO core standard, for example here:
>
> 8.14.2.5 Bootstrapped built-in predicates
>

> The built-in predicates write_term/2, write/1,
> write/2, writeq/1, writeq/2, write_canonical/1,
> and write_canonical/2 all provide similar functionality
> to write_term/3.
>
> [...]
>
> write_term(Term, Options) :-
> current_output(S),
> write_term(S, Term, Options).

Here is subclause 8.1.5 of 13211-1:1995 explaining the idea:


8.1.5 Bootstrapped built-in predicates

Sometimes several built-in predicates have similar func-
tionality. In such cases, one or more bootstrapped built-in
predicates are defined as special cases of a more genera1
built-in predicate.

The description of a bootstrapped built-in predicate states
how it relates to the general built-in predicate, usually
followed by a definition in Prolog that defines the logical
and procedural behaviour of the bootstrapped built-in
predicate when no error conditions are satisfied.

The error conditions and examples for a bootstrapped
built-in predicate are included in the appropriate clauses
of the general built-in predicate.

(end quote)

[bart demoen]

On Tue, 02 Oct 2012 13:03:26 +0200, Jan Burse wrote:

> Just trying to figure out what the different aggregate predicates do
> (*). So I find the following bootstrapping:
>
> bagof(X, G, B) :- aggregate(bag(X), G, L).
> setof(X, G, B) :- aggregate(set(X), X, G, L).

The documentation is a bit confusion if you really want to take it
literally. My guess is: the above is not meant as bootstrapping code
and might have been better written as

bagof(X, G, B) behaves as aggregate(bag(X), G, L)

But why don't you ask in the SICStus mailing list: that's the best
source for complaints about confusing docs, no ?

If you have a license for SICStus, you could also have a look at
library/aggregate.pl and see for yourself that ... aggregate/3 is defined
using bagof/3

and you know what ... the implementation of bagof/3 often uses findall/3
(see for instance boot/bags.pl in SWI-Prolog).

But since I'd rather teach to to fish instead of giving you fish, here is
a piece of useful advice: sending your documentation complaints to the
correct forum (in this case SICS mailing list) will help you faster and
without so much fuzz in comp.lang.prolog

Bart Demoen

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Jan Burse]

bart demoen schrieb:

> But since I'd rather teach to to fish instead of giving you fish, here is
> a piece of useful advice: sending your documentation complaints to the
> correct forum (in this case SICS mailing list) will help you faster and
> without so much fuzz in comp.lang.prolog

For gods sake, I didn't complain.

[Jan Burse]

bart demoen schrieb:

> If you have a license for SICStus, you could also have a look at
> library/aggregate.pl and see for yourself that ... aggregate/3

> is defined using bagof/3.

That's actually not true. My evaluation license has
already expired, and see now that I can still walk
the directory. And I indeed find the following
bootstrapping:

aggregate(Template, Generator, Result) :-
parse_template(Template, Pattern),
bagof(Pattern, Generator, List),
process_results(List, Pattern, Result).

Means a list of length 1000000 is generated? When
I want to count 1000000 elements? Grrr... Now I will
start complaining Joe.

Same issue in SWI Prolog implementation.

Bye

[Jan Burse]

Jan Burse schrieb:

> Now I will start complaining Joe.

But this would be a complaint about the implementation,
and not about the doc. Any rational to use bagof/3 and not
implement some template folding on the fly?

I was thinking about bootstrapping aggregate/3 and
aggregate_all/3 via:

sys_findall(T,G,I,A,R):
T: Like in findall/3.
G: Like in findall/3.
I: Initial value.
A: Accumulator closure (sic!).
R: Result value.

sys_bagof(T,G,I,A,R):
T: Link in bagof/3.
G: Like in bagof/3.
I: Initial value.
A: Accumulator closure (sic!).
R: Result value.

Here are some preliminary results:

/* count */
?- sys_findall(X,(X=1;X=1;X=1;X=1),0,A^B^C^(C is A+1),R).
R = 4
/* sum */
?- sys_findall(X,(X=1;X=2;X=3;X=4),0,A^B^C^(C is A+B),R).
R = 10

I did not yet do some measure. It could be that the closure
application is too slow, so that the bagof/3 bootstrapping
could win time wise over that on the fly folding. But I
have an application where large sets are counted, so memory
is also an issue somehow.

The good thing about many statistics functions is exactly
that they can be implemented stream wise, i.e. on the fly
folding. Machine learning will like it.

Bye

[Jan Burse]

Jan Burse schrieb:

> sys_findall(T,G,I,A,R):
> T: Like in findall/3.
> G: Like in findall/3.
> I: Initial value.
> A: Accumulator closure (sic!).
> R: Result value.

It still involves some copy_term/2 like in findall/3, but
only temporarily, to save the intermediate result before
redoing the goal. So the list is not built.

Bye

[Jan Burse]

bart demoen schrieb:

> sending your documentation complaints to the correct forum (in
> this case SICS mailing list) will help you faster and without
> so much fuzz in comp.lang.prolog

The only advantage, if this mailing list would be moderated,
would be possibly that I would not be molested by trolls such
as Bart Demoen and LudovicoVan, who don't know the difference
between asking for clarification and complaining.

[Jan Burse]

Jan Burse schrieb:

> who don't know the difference
> between asking for clarification and complaining.

Corr.
who pretend to not know the difference

between asking for clarification and complaining.

That's the mark of a troll, he could do better, but
since he is evil, he doesn't.

[LudovicoVan]

"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
news:2012Oct...@mips.complang.tuwien.ac.at...

> "LudovicoVan" <ju...@diegidio.name> writes:
>>"Jan Burse" <janb...@fastmail.fm> wrote in message
>>news:k4ekcm$4kl$1...@news.albasani.net...
>>> LudovicoVan schrieb:
>><snipped>
>>
>>>> What do you mean by bootstrapping?
>>
>>> The term "bootstrapping" is used in some places
>>> of Prolog ISO core standard, for example here:
>>
>>Thanks: I had bought the standard then my disk crashed (yeah, please don't
>>remind me about backups...) and now I should buy it again...!!
>
> You get the standard for such a low price that typing your remark
> costs you more than paying for a new copy.

Nice rhetoric, but it won't buy you a lunch. ;) The point was, not only
that it should be as free as, say, HTML is, rather and more importantly that
it should be *implementable* (at reasonable costs, of course, on this and on
how good things are never free), which it just isn't, and fundamentally: it
is not even self-consistent, in the grammar!

>>Doesn't it suck that the Prolog language is beautiful and so expressive,
>>but
>>just there is nothing even near to an acceptable state of affairs in order
>>to make commercial, industry level products out of it? Engineering is all
>>about standardization, and I won't even get into how the current standard
>>is
>>not even good enough to implement a fully conformant parser...
>
> Have a look at the current difference between systems:

Yes, I know: but I have commented on the current state of affairs already.
E.g., I am writing some Prolog code these days, and that I have to spend
more than 50% of the time just wondering how to build an
*effectively*portable code is simply unacceptable, at least to anyone not
used to waste his time as I am.

BTW, I still have to look at GNU Prolog, it promises a lot.

-LV

[Jan Burse]

LudovicoVan schrieb:

> Nice rhetoric, but it won't buy you a lunch. ;) The point was, not only
> that it should be as free as, say, HTML is, rather and more importantly
> that it should be *implementable* (at reasonable costs, of course, on
> this and on how good things are never free), which it just isn't, and
> fundamentally: it is not even self-consistent, in the grammar!

I still think Prolog is very free. You find
dozens of read.pl on the internet, that even
show you how to implement a Prolog parser in
Prolog itself. For example:

Remove %16, % 46, % 47 (what else?) from the following:
http://www.cs.huji.ac.il/~naomil/maria/read.pl
And I guess you then get an ISO Prolog parser.

You could >>bootstrap<< a Prolog system, by using
another Prolog system, and a little kernel that
can only read canonical terms. i.e. convert the
above via write_canonical and feed it to your
kernel.

> Yes, I know: but I have commented on the current state of affairs
> already. E.g., I am writing some Prolog code these days, and that I
> have to spend more than 50% of the time just wondering how to build
> an *effectively*portable code is simply unacceptable, at least to
> anyone not used to waste his time as I am.

Can you tells us in what areas you in particular
encauntered portability issues. What Prolog systems
did you have to go back and forth? Where there issues
with ISO predicates, or did it happen in other areas?

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4fmkj$e9f$1...@news.albasani.net...

> LudovicoVan schrieb:
>> Nice rhetoric, but it won't buy you a lunch. ;) The point was, not only
>> that it should be as free as, say, HTML is, rather and more importantly
>> that it should be *implementable* (at reasonable costs, of course, on
>> this and on how good things are never free), which it just isn't, and
>> fundamentally: it is not even self-consistent, in the grammar!
>
> I still think Prolog is very free.

Everybody is entitled, etc.

> You find
> dozens of read.pl on the internet, that even
> show you how to implement a Prolog parser in
> Prolog itself. For example:

You mean ISO conformant parsers??

> Remove %16, % 46, % 47 (what else?) from the following:
> http://www.cs.huji.ac.il/~naomil/maria/read.pl
> And I guess you then get an ISO Prolog parser.

You guess??

> You could >>bootstrap<< a Prolog system, by using
> another Prolog system, and a little kernel that
> can only read canonical terms. i.e. convert the
> above via write_canonical and feed it to your
> kernel.

Sure, we can do all sort of amazing stuff in Prolog. In the meantime, you
keep missing the point. No, actually you said you do not have an opinion...

-LV

[Ulrich Neumerkel]

"LudovicoVan" <ju...@diegidio.name> writes:
>"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
>news:2012Oct...@mips.complang.tuwien.ac.at...
>> "LudovicoVan" <ju...@diegidio.name> writes:
>>>"Jan Burse" <janb...@fastmail.fm> wrote in message
>>>news:k4ekcm$4kl$1...@news.albasani.net...
>>>> LudovicoVan schrieb:
>>><snipped>
>>>
>>>>> What do you mean by bootstrapping?
>>>
>>>> The term "bootstrapping" is used in some places
>>>> of Prolog ISO core standard, for example here:
>>>
>>>Thanks: I had bought the standard then my disk crashed (yeah, please don't
>>>remind me about backups...) and now I should buy it again...!!
>>
>> You get the standard for such a low price that typing your remark
>> costs you more than paying for a new copy.
>
>Nice rhetoric, but it won't buy you a lunch. ;) The point was, not only
>that it should be as free as, say, HTML is, rather and more importantly that
>it should be *implementable* (at reasonable costs, of course, on this and on
>how good things are never free), which it just isn't, and fundamentally: it
>is not even self-consistent, in the grammar!

International technical standards almost always cost some money. Why
should it be different in this case? Think of 26262, 9000 etc. The
regular price of part 1 is about USD 300, thanks to INCITS you get
it for USD 30.

What do you mean by "it is not even self-consistent in the grammar"?
I would be very much interested in knowing inconsistencies. And yes,
I am aware of several. Also Jan Burse, BTW, helped to discover some.
The current draft is N234, http://www.complang.tuwien.ac.at/ulrich/iso-prolog/stc

You do know anything else? Please tell us!

....

>> Have a look at the current difference between systems:
>
>Yes, I know: but I have commented on the current state of affairs already.
>E.g., I am writing some Prolog code these days, and that I have to spend
>more than 50% of the time just wondering how to build an
>*effectively*portable code is simply unacceptable, at least to anyone not
>used to waste his time as I am.

I am fully aware of this problem. But complaining alone does not help.
Many implementors state that they would be more conforming if actually
users wanted this. But - acoording to them - users never demand
conformance.

>BTW, I still have to look at GNU Prolog, it promises a lot.

At least, use GNU as a syntax checker!

[LudovicoVan]

"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
news:2012Oct...@mips.complang.tuwien.ac.at...

> What do you mean by "it is not even self-consistent in the grammar"?
> I would be very much interested in knowing inconsistencies. And yes,
> I am aware of several.

Then what the heck your objection would be to my statement?

> Also Jan Burse, BTW, helped to discover some.
> The current draft is N234,
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/stc
>
> You do know anything else? Please tell us!

You must be kidding.

> I am fully aware of this problem. But complaining alone does not help.

I have done more than just complaining: you have the "industrial
perspective" up-thread, should that matter. Does it?

> Many implementors state that they would be more conforming if actually
> users wanted this. But - acoording to them - users never demand
> conformance.

That is so wrong that I cannot believe you are serious... you and the
implementers...

-LV

[Ulrich Neumerkel]

Can we leave some steam out of the discussion?

It seems your question was about the deep requirements that
library(aggregate) imposes. Similar to setof/3, it does not
inherently require space proportional to the number of answers,
but many implementations do this nevertheless. A good test
for this is:

catch(setof(t,repeat,Ts), Pat,true).

This could loop in constant space, but many implementations
exhaust resources, which is still conforming behaviour.
However, only a few are able to signal an error that
can be caught. SWI, YAP, and B succeed with
Pat = error(resource_error(_),_).

library(aggregate) has more complex requirements in
this respect.

[Jan Burse]

LudovicoVan schrieb:

> Sure, we can do all sort of amazing stuff in Prolog. In the meantime,
> you keep missing the point. No, actually you said you do not have an
> opinion...

No I don't have an opinion on "large-scale industrial adoption"
since it insuinates that Prolog could be an all purpose language.
I think this is wrong similar to saying Prolog must become an
universal logic server, etc.. you name it.

I am open to mix and match, i.e. embed Prolog with other programming
languages be it imperative, functional etc..

But I still believe Prolog is very accessible for everybody. All
other programming languages slowly grow monstrous but Prolog has
kept its simplicity. The ISO standard is not on the hunt to
enlarge Prolog by feature after feature.

> You guess??

Yes, not every Prolog parser has D.H.D.Warren and Richard O'Keefe
read.pl as an ancestor. So I am not an expert on read.pl, but
rumors have it, that it is quite usable. But everybody is free
to play any tune, even bite the hand that feeds them (*).

Bye

(*)
http://www.youtube.com/watch?v=xwhBRJStz7w

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4fo93$hdb$1...@news.albasani.net...

> LudovicoVan schrieb:

>> Sure, we can do all sort of amazing stuff in Prolog. In the meantime,
>> you keep missing the point. No, actually you said you do not have an
>> opinion...
>
> No I don't have an opinion on "large-scale industrial adoption"
> since it insuinates that Prolog could be an all purpose language.

All I may keep insinuating is that you just don't know what you are talking
about.

EOD.

-LV

[Ulrich Neumerkel]

"LudovicoVan" <ju...@diegidio.name> writes:
>> I am fully aware of this problem. But complaining alone does not help.
>
>I have done more than just complaining: you have the "industrial
>perspective" up-thread, should that matter. Does it?

We do have quite a lot of stakeholders that claim to represent
an industrial perspective. For the moment, I am unaware
how you did contribute - that is "more than just complaining".

[Jan Burse]

Ulrich Neumerkel schrieb:

> library(aggregate) has more complex requirements in
> this respect.

The bootstrapped implementation is only a cosmetic implementation
without some meat. It only translates
<constructor>(<aggregate>(<expr>),..) to a corresponding fold function,
which is applied
after bagof/3 has been called.

This is correct versus some functional specification. But it is
not what one would expect concerning some common sense
non-functional requirements. One could argue that potentially
since among the aggregates we have bag/1 and set/1, the lists have
anyway to be generated. Yes, this is a little complication.

But for the other aggregates sum, max, count, etc.. it makes
absolutely no sense to generate the lists. And I take it for
granted that no SQL database would do their aggregates like
this. So the expectation for aggregate/3 and the other is that
you also get some non-functionaly goody.

But with this bootstrapping this is not the case. Except the
compiler detects a corresponding optimization, then I wouldn't
complain.

Bye

[Jan Burse]

LudovicoVan schrieb:

>> No I don't have an opinion on "large-scale industrial adoption"
>> since it insuinates that Prolog could be an all purpose language.
>
> All I may keep insinuating is that you just don't know what you are
> talking about.

Of course you are completely right.

[LudovicoVan]

"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
news:2012Oct...@mips.complang.tuwien.ac.at...

Idiot.

-LV

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4fp1f$iru$1...@news.albasani.net...

Ah, you said it! -- I'd agree with the above. OTOH, that's the kind of
stuff that should have no room in a standard, and you are comparing
implementations here.

-LV

[Jan Burse]

LudovicoVan schrieb:

> Ah, you said it! -- I'd agree with the above. OTOH, that's the kind
> of stuff that should have no room in a standard, and you are comparing
> implementations here.

BTW: comp.lang.prolog is about Prolog in general, independent of
the ISO core standard. Can I call you an idiot now? No I wont, but
please be aware about this. You made the same mistake already during
this thread.

I was mentioning the ISO core Prolog standard only to explain
where I borrowed the vocabulary "bootstrapping". But using a word
from a dictionary, doesn't mean that we are about to discuss this
dictionary.

Please open a new thread if you have a serious opinion about the
ISO core standard and want to discuss it.

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4fpvv$k7q$1...@news.albasani.net...

Hopeless.

Bye,

-LV

[van...@vsta.org]

LudovicoVan <ju...@diegidio.name> wrote:
>> Please open a new thread if you have a serious opinion about the
>> ISO core standard and want to discuss it.

> Hopeless.

On the contrary, Jan has an impressively deep understanding of
Prolog and I'm quite glad that he posts here.

--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

[LudovicoVan]

<van...@vsta.org> wrote in message news:ad1bls...@mid.individual.net...

> LudovicoVan <ju...@diegidio.name> wrote:
>
>>> Please open a new thread if you have a serious opinion about the
>>> ISO core standard and want to discuss it.
>> Hopeless.
>
> On the contrary, Jan has an impressively deep understanding of
> Prolog and I'm quite glad that he posts here.

Learn to read.

-LV

[LudovicoVan]

"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
news:2012Oct...@mips.complang.tuwien.ac.at...

> It seems your question was about the deep requirements that
> library(aggregate) imposes.

Do you really think that if I had to build something for real I would use
(most) any of the libraries that ship with the average product?

We need a standardized RISC-like Prolog, that is what we need.

-LV

[LudovicoVan]

"LudovicoVan" <ju...@diegidio.name> wrote in message
news:k4g094$n7p$1...@dont-email.me...

An executable spec, of course.

-LV

[Jan Burse]

bart demoen schrieb:
> and you know what ... the implementation of bagof/3 often uses findall/3
> (see for instance boot/bags.pl in SWI-Prolog).

My current understanding of the ISO core standard is that it is
not required that bagof/3 is bootstrapped from findall/3 AND
keysort/2. Reason is the little word "undefined" in the following
paragraph of the ISO core standard:

"bagof/3 assembles as a list the solutions of a goal for
each different instantiation of the free variables in that
goal. The elements of each list are in order of solution,
but the order in which each list is found is undefined."

For a little exploration of the idea of not using keysort/2,
but sys_keygroup/2 instead, see here:
https://plus.google.com/u/0/103259555581227445618/posts/LGR8StS9Js5

There are issues with using keysort/2 when the witnesses are
not comparable and/or should not be compared. For example
reference data types or rational trees (cyclic term data
structures).

Besides that, a non bootstrapped implementation or a bootstrapped
implementation that makes use of some special datastructure
built-ins can totally abstain from using findall/3.

Further a documentation that offers a very general predicate
as a bootstrap explanation is of course correct (i.e. the
findall/3). But a documentation that uses a more specific
predicate (i.e. the bagof/3) as a bootstrap explanation can
convey more information.

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4g8lq$ij2$1...@news.albasani.net...

> bart demoen schrieb:

>> and you know what ... the implementation of bagof/3 often uses findall/3
>> (see for instance boot/bags.pl in SWI-Prolog).
>
> My current understanding of the ISO core standard

You are not entitle to talk about the ISO standard around here.

> a bootstrap explanation

What do you mean by bootstrap explanation?

-LV

[Jan Burse]

LudovicoVan schrieb:

>
>> a bootstrap explanation
>
> What do you mean by bootstrap explanation?

An a predicate explanation that mentions a predicate
that is used in a possible bootstrapping of the
explained predicate. For example:

writeq(X):
Works as if write_term(X,[quote(true)]).

Is a bootstrap explanation in my little ad hoc lingo.

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4gt1r$de8$1...@news.albasani.net...

Thanks, makes sense.

-LV

[bart demoen]

On Tue, 02 Oct 2012 19:57:07 +0200, Jan Burse wrote:

> bart demoen schrieb:
>> If you have a license for SICStus, you could also have a look at
>> library/aggregate.pl and see for yourself that ... aggregate/3
> > is defined using bagof/3.
>
> That's actually not true.

Can you enlighten me on what part I wrote was actually not true ?

After your sentence "That's actually not true" you quote from
the library a clause that shows that aggregate/3 is defined using
bagof/3, so that part of my sentence is true.

Then it must be the part "if you have a ... you could have a look".
Have you a proof of the contrary, a counterexample perhaps ?

Just so this conversation wouldn't get even more confused, let me draw
your attention to a common laymen's believe
p -> q
also means
not(p) -> not(q).

So, what where you referring to when you wrote something " is actually
not true" ? Or did the pitfall get you ? Maybe by accident: nobody is
perfect after all.

BTW, you are welcome, even though you forgot to thank me for my help :-)
Or should I take being scolded at as an expression of your gratitude ?

Bart Demoen

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Jan Burse]

Jan Burse schrieb:

> Ulrich Neumerkel schrieb:
>> library(aggregate) has more complex requirements in
>> this respect.
>
> The bootstrapped implementation is only a cosmetic implementation
> without some meat. It only translates

BTW: Here is an example of bagof/3 underneath not
being able to scale:

SWI-Prolog, uses bagof/3 underneath aggregate/3 and aborts:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.0)
Copyright (c) 1990-2012 University of Amsterdam, VU Amsterdam

?- aggregate(count,Y^(between(0,19999999,Y),Z is Y//10000000),R).
ERROR: Out of global stack



On the other hand we have:

Preview Jekejeke Prolog, does something else and will not abort:

Jekejeke Prolog, Development Environment 0.9.6
(c) 1985-2012, XLOG Technologies GmbH, Switzerland

?- aggregate(count,Y^(between(0,19999999,Y),Z is Y//10000000),R).
Z = 1,
R = 10000000 ;
Z = 0,
R = 10000000


This experiment makes heavy use of call/n and is extensible
by the end-user. Aggregates are simply defined by a table:

% sys_aggr_funs(+Aggregate,-Template,-Init,-Next, -Unpack)
sys_aggr_funs(sum(X), X, 0, sys_sum_next, sys_null_unpack).
...


One might expect that bag/1 and set/1 aggregates will not
anymore work since aggregate/3 is not anymore based on
bagof/3.

But with some little new helpers (freeze and melt of terms),
they also fit into the framework. Both aggregates can be
done with corresponding Next and Unpack closures. So that
for example the following works fine:

?- aggregate(bag(X),Y^(between(0,19,Y),Z is Y//10,X is Y mod 10),R).
Z = 1,
R = [0,1,2,3,4,5,6,7,8,9] ;
Z = 0,
R = [0,1,2,3,4,5,6,7,8,9]


Constructor aggregates have also their corrsponding closures.

Bye

P.S.: The G+ post on this experiment can be found here:
http://plus.google.com/u/0/103259555581227445618/posts/jS6RAUQanED

[Jan Burse]

bart demoen schrieb:

> BTW, you are welcome, even though you forgot

> to thank me for my help:-). Or should I take

> being scolded at as an expression of your
> gratitude ?

Your post was 02.10.2012 19:21. This was 3 hours
after my post on 02.10.2012 16:15, where I already
discovered the SWI docu, and which basically setteled
my initial question.

So the only purpose of your post was to troll and
throw mud at me, and nothing else. From my post
you should have also learned that the discussion
has anyway left the scope of SICStus.

The Prolog FAQ reads:

> That being said, there are news://comp.lang.prolog/ readers who would
> be glad to help people making a legitimate attempt to learn Prolog.

I would add to the above, that the newsgroup is infected
by a couple of trolls, so newbees beware. Foremost one
troll named Bart Demoen who has a special affinity to me.
For a definition of the term troll see here:

"An individual who chronically trolls in sense 1; regularly posts
specious arguments, flames or personal attacks to a newsgroup,
discussion list, or in email for no other purpose than to annoy
someone or disrupt a discussion. Trolls are recognizable by the
fact that the have no real interest in learning about the topic
at hand — they simply want to utter flame bait. Like the ugly
creatures they are named after, they exhibit no redeeming
characteristics, and as such, they are recognized as a lower
form of life on the net, as in, "Oh, ignore him, he’s just a troll".
http://catb.org/jargon/html/T/troll.html

Bart Demoen you would be welcome to trolling, if it were
funny. Namely if you had the genuity to teach and entertain.
But throwing mud at others is lame.

Bye

[Jan Burse]

Dear All,

Jan Burse schrieb:

> Jan Burse schrieb:
>> Ulrich Neumerkel schrieb:
>>> library(aggregate) has more complex requirements in
>>> this respect.
>>
>> The bootstrapped implementation is only a cosmetic implementation
>> without some meat. It only translates
>
> BTW: Here is an example of bagof/3 underneath not
> being able to scale:

Was able to do some benchmarking for the incremental aggregate/3,
that does not use bagof/3 under the hood and thus does not materialize
a list of results before applying the aggregate. There are some positive
and some negative aspects of the benchmarking results.

The negative aspect is that the incremental aggregates do not yet
beat the materializing solution. The overhead could be induced
by the usage of FFI and call/n in the solution. Need to investigate
and will probably fall back to materializing for the moment, since
the overhead is too big for a real world application.

The positive result is that there is practically no difference between
the bagof/3 and the findall/3 solution, indicating that the bagof/3
itself as part of the materializing solution has a relatively good
implementation right now. Also in the incremental case the internal
assembly seems not to generate some overhead.

The results are as follows, running "perfect<number>" 26 times on
a Intel i5-2540M 2.40 GHz (3 GHz turbo):

prefect1 findall 985 (ms)
prefect2 bagof 979 (ms)
prefect3 accumulate 1'227 (ms) (incremental, does not use findall)
prefect4 aggregate 1'280 (ms) (incremental, does not use bagof)

Best Regards

(Troll disclaimer: Yes the above is a micro benachmark. Did also
a macro benchmark, in the real world application switching from
findall to accumulate in one place brought some test
from 28'000 ms to 31'000 ms)

---------------------------- Test Cases -----------------------

/****************************************************/
/* Findall */
/****************************************************/

perfect1(Hi,X) :-
between(1,Hi,X),
Y is X // 2,
findall(Z,(between(1,Y,Z), (X rem Z =:= 0)),L),
sumlist(L,X).

perfect1 :-
perfect1(500,_).

/****************************************************/
/* Bagof */
/****************************************************/

perfect2(Hi,X) :-
bagof(Z,Y^(between(1,Hi,X),
Y is X // 2,
(between(1,Y,Z), (X rem Z =:= 0))),L),
sumlist(L,X).

perfect2 :-
perfect2(500,_).

/****************************************************/
/* Accumulate */
/****************************************************/

perfect3(Hi,X) :-
between(1,Hi,X),
Y is X // 2,
accumulate(sum(Z),(between(1,Y,Z), (X rem Z =:= 0)),X).

perfect3 :-
perfect3(500,_).

/****************************************************/
/* Aggregate */
/****************************************************/

perfect4(Hi,X) :-
aggregate(sum(Z),Y^(between(1,Hi,X),
Y is X // 2,
(between(1,Y,Z), (X rem Z =:= 0))),X).

perfect4 :-
perfect4(500,_).

[Ulrich Neumerkel]

Jan Burse <janb...@fastmail.fm> writes:
>Jan Burse schrieb:
>> Ulrich Neumerkel schrieb:
>>> library(aggregate) has more complex requirements in
>>> this respect.
>>
>> The bootstrapped implementation is only a cosmetic implementation
>> without some meat. It only translates
>
>BTW: Here is an example of bagof/3 underneath not
>being able to scale:
>
>SWI-Prolog, uses bagof/3 underneath aggregate/3 and aborts:
>
> Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.0)
> Copyright (c) 1990-2012 University of Amsterdam, VU Amsterdam
>
> ?- aggregate(count,Y^(between(0,19999999,Y),Z is Y//10000000),R).
> ERROR: Out of global stack

For the sake of completeness, let me outline that this error is
a clean catch-able resource error:

?- catch(aggregate(count,Y^(between(0,19999999,Y),Z is Y//10000000),R),error(E,_),true).
E = resource_error(stack).

Which means that this overflow can be handled within SWI-Prolog.

[Ulrich Neumerkel]

Jan Burse <janb...@fastmail.fm> writes:
>The results are as follows, running "perfect<number>" 26 times on
>a Intel i5-2540M 2.40 GHz (3 GHz turbo):
>
>prefect1 findall 985 (ms)
>prefect2 bagof 979 (ms)
>prefect3 accumulate 1'227 (ms) (incremental, does not use findall)
>prefect4 aggregate 1'280 (ms) (incremental, does not use bagof)

...

>perfect1(Hi,X) :-
> between(1,Hi,X),
> Y is X // 2,
> findall(Z,(between(1,Y,Z), (X rem Z =:= 0)),L),
> sumlist(L,X).

What are you measuring here? Why the (rem)/2? Isn't just
summing up 1..N good enough as a test?

And summing it up twice separately to get a bit a feeling
of the overheads of sumlist/2?

[Jan Burse]

Ulrich Neumerkel schrieb:

>> Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.0)
>> > Copyright (c) 1990-2012 University of Amsterdam, VU Amsterdam
>> >
>> > ?- aggregate(count,Y^(between(0,19999999,Y),Z is Y//10000000),R).
>> > ERROR: Out of global stack
> For the sake of completeness, let me outline that this error is
> a clean catch-able resource error:
>
> ?- catch(aggregate(count,Y^(between(0,19999999,Y),Z is Y//10000000),R),error(E,_),true).
> E = resource_error(stack).
>
> Which means that this overflow can be handled within SWI-Prolog.

The issue at hand is not whether an overflow can be handled
or not. The issues is that no overflow at all should happen.
Consider the following histogram code in Java:

int[] histogram = {0,0}

for (int i=0; i<=19999999; i++) {
int j=i % 10000000;
histogram[j]++;
}

The above code scales indefinitely. I can replace 19999999 with
larger integers, or go BigInteger. But the imperative stile
of realization does not require that a list is materialized
with the classified values of j.

Call the above algorithm "incremental".

Now the definition of aggregate/3 in aggregate.pl uses bagof/3.
Means the classified values Z are grouped and put into lists.
Later the lists are returned according to the aggregate. The
count aggregate needs simply to compute the length of the lists.

Call the above algorithm "materializing".

The space requirement for count of an incremental algorithm
is O(m) where m is the size of the histogram. Ingnoring currently
the size of BigIntegers or so. The space requirement for count
of the materializing algorithm is O(k), where k is the number
of solutions.

I would prefer an O(m) algorithm over an O(k). But performance
measure shows that I am not yet there. See other post.

[Jan Burse]

Ulrich Neumerkel schrieb:

>> erfect1(Hi,X) :-
>> > between(1,Hi,X),
>> > Y is X // 2,
>> > findall(Z,(between(1,Y,Z), (X rem Z =:= 0)),L),
>> > sumlist(L,X).
> What are you measuring here? Why the (rem)/2? Isn't just
> summing up 1..N good enough as a test?
>
> And summing it up twice separately to get a bit a feeling
> of the overheads of sumlist/2?

The above test case is easy to verify for
correctness (*). You should get:

?- perfect<number>(500,X).
X = 6 ;
X = 28 ;
X = 496 ;
No

Since it is only called with 500, there shouldn't be an
issue with BigIntegers, all the operations can be made
with register integers.

perfect was already once discussed here in comp.lang.prolog
a while ago whether it is a good test case for findall/3. See
detailed measures by Bart Demoen.

You are free to provide other test cases. Also hints about
existing or suggestions for future non-materializing aggregates
are welcome. When accompaigned with test results the better.

My tests results show unambiguously that my current non-
materializing aggregate realization is not yet ripe. In a
non micro benchmark an application went from 28'000 ms to
31'000 ms, which is a little bit too much. So I am currently
falling back to bootstrap from bagof/3 (**).

Bye

(*)
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/06_bench/09_programs/09_perfect/package.html

(**)
https://plus.google.com/u/0/103259555581227445618/posts/Sp6gdzH1WQy

[Jan Burse]

Jan Burse schrieb:

> You are free to provide other test cases. Also hints about
> existing or suggestions for future non-materializing aggregates
> are welcome. When accompaigned with test results the better.

What could deliver incremental aggregates would be possibly
aggregate tabling. I think I saw this in B-Prolog, maybe XSB
has it also. But do I have to explicitly dispose the tabling?
And how about thread local aggregate requests, or recursive
aggregate requests?

Conscerning automatic dispose and thread local, then undoable
memoing comes to mind. Either via hypothetical reasoning or
forward chaining. But this is probably not anymore incremental,
since an undo trail is established and kept, which is a
materialization.

No easy way out...

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4s2eg$t6g$1...@news.albasani.net...

I have tried this variant for SWI-Prolog which uses non-backtracking
assignments to compute the aggregate. The performance is almost that of
perfect1. (Is it an advantage that this is not boot-strapped but does not
use native code either? I do not understand Ulrich Neumerkel's remark on
taking into account the overhead of sumlist/2: how is that not taken into
account?)

perfect_(nb_sum, High, X) :-
between(1, High, X),

Y is X // 2,

NbSum = nb(0),
forall(
( between(1, Y, Z),
X rem Z =:= 0
),
( arg(1, NbSum, S),
S1 is S + Z,
nb_setarg(1, NbSum, S1)
)
),
arg(1, NbSum, X).

?- perfect_test.
perfect(nb_sum, 10000) -> 6
perfect(nb_sum, 10000) -> 28
perfect(nb_sum, 10000) -> 496
perfect(nb_sum, 10000) -> 8128
% 25,291,011 inferences, 8.486 CPU in 8.520 seconds (100% CPU, 2980162 Lips)

perfect(findall, 10000) -> 6
perfect(findall, 10000) -> 28
perfect(findall, 10000) -> 496
perfect(findall, 10000) -> 8128
% 25,397,273 inferences, 8.455 CPU in 8.490 seconds (100% CPU, 3003727 Lips)

perfect(bagof, 10000) -> 6
perfect(bagof, 10000) -> 28
perfect(bagof, 10000) -> 496
perfect(bagof, 10000) -> 8128
% 25,582,025 inferences, 9.064 CPU in 9.100 seconds (100% CPU, 2822483 Lips)

true.

-LV

[Jan Burse]

LudovicoVan schrieb:
> ?- perfect_test.

> perfect(nb_sum, 10000) -> 8128
> % 25,291,011 inferences, 8.486 CPU in 8.520 seconds (100% CPU, 2980162
> Lips)
>

> perfect(findall, 10000) -> 8128
> % 25,397,273 inferences, 8.455 CPU in 8.490 seconds (100% CPU, 3003727
> Lips)
>

Thanks for sharing. You might see little different figures if
you try to provide a predicate accumulate/3 (*), that needs first
to translate the sum/1 aggregate denotation into S1 is S + Z.
Also I don't know from the hip, how you can provide an efficient
translation of the bag/1 aggregate via nb_setarg/3.

The latter would involve duplicate_term/2 and probaly move bag/1 from
O(n) (assuming findall/1 adds one element in O(1)) to O(n^2). But it
can be also done, although it is not straight forward. Last but not
least the aggregate functions have the requirement to allow
constructors, i.e.:

?- accumulate(x(sum(X),count),(X=1;X=2),Y). (*)
Y = x(3,2)

LudovicoVan schrieb:

> perfect(bagof, 10000) -> 8128
> % 25,582,025 inferences, 9.064 CPU in 9.100 seconds (100% CPU, 2822483
> Lips)

Another issue, and probably not related to you, I guess bagof
needs some improvments here. In my opinion it should not degrade
much compared to the findall/3 solution. On the contrary, it can
even perform a little better. See also here:

Jan Burse wrote:
> prefect1 findall 985 (ms)
> prefect2 bagof 979 (ms)

But maybe need more testing. There is a tradeoff between updating
the histogram. Which is near O(1) if a hashtable is used. And
growing the hashtable. As already mentioned, also in this thread,
I read the ISO core standard that it does not require that bagof/3
is based on keysort.

Bye

(*)
I guess my accumulate/3 = aggregate_all/3.

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4s709$9f0$1...@news.albasani.net...
> LudovicoVan schrieb:
>> [snipped some code]

>>
>> ?- perfect_test.
>> perfect(nb_sum, 10000) -> 8128
>> % 25,291,011 inferences, 8.486 CPU in 8.520 seconds (100% CPU, 2980162
>> Lips)
>>
>> perfect(findall, 10000) -> 8128
>> % 25,397,273 inferences, 8.455 CPU in 8.490 seconds (100% CPU, 3003727
>> Lips)
>
> Thanks for sharing. You might see little different figures if
> you try to provide a predicate accumulate/3 (*), that needs first
> to translate the sum/1 aggregate denotation into S1 is S + Z.
> Also I don't know from the hip, how you can provide an efficient
> translation of the bag/1 aggregate via nb_setarg/3.
>
> The latter would involve duplicate_term/2 and probaly move bag/1 from O(n)
> (assuming findall/1 adds one element in O(1)) to O(n^2). But it
> can be also done, although it is not straight forward. Last but not
> least the aggregate functions have the requirement to allow constructors,
> i.e.:
>
> ?- accumulate(x(sum(X),count),(X=1;X=2),Y). (*)
> Y = x(3,2)

Thank you for the feedback. I wouldn't think there is very much overhead
involved in parsing the template, also considering that this would happen
once, before the loop starts. Anyway, I do not have time right now but I
will try to implement the features you mention -- just for SWI, though. In
fact, a question stands: is an implementation based on non-backtracking
assigments worth considering at all? It is not really portable, is it?

-LV

[Jan Burse]

LudovicoVan schrieb:

>
> Thank you for the feedback. I wouldn't think there is very much
> overhead involved in parsing the template, also considering that this
> would happen once, before the loop starts.

For the non-incremental solution, the materializing solution,
only a preprocessing and a postprocessing is needed. I have
meanwhile implemented this, and I don't see some overhead.
Basically timings are findall=accumulate and
bagof=aggregate.

But if aggregates are allowed to sit inside constructors I
guess it is inevitable that some decoding also happens
inside the loop for an incremental solution. In my solution
that used call/n and FFI I observed quite an overhead
inside the loop.

Problem is that a call/n is not the fastest.

> In fact, a question stands: is an implementation based on
> non-backtracking assigments worth considering at all?
> It is not really portable, is it?

If aggregate/3 were a spec and not a library, every system can
implement as it likes. And it would not be required that some
file aggregate.pl is shuffeld around.

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4s9p9$h9n$1...@news.albasani.net...

> LudovicoVan schrieb:
>>
>> Thank you for the feedback. I wouldn't think there is very much
>> overhead involved in parsing the template, also considering that this
>> would happen once, before the loop starts.
>
> For the non-incremental solution, the materializing solution,
> only a preprocessing and a postprocessing is needed. I have
> meanwhile implemented this, and I don't see some overhead.
> Basically timings are findall=accumulate and
> bagof=aggregate.

I still do not see what difference there can be between (in your terms) the
incremental and the materializing solution, as far as parsing a template is
involved (of whichever complexity): in any case, we have the pre- and maybe
a post- parsing, in both cases this happens outside the loop, and in both
cases we need indirect calls.

> But if aggregates are allowed to sit inside constructors I
> guess it is inevitable that some decoding also happens
> inside the loop for an incremental solution. In my solution
> that used call/n and FFI I observed quite an overhead
> inside the loop.
>
> Problem is that a call/n is not the fastest.

Indirect calls are needed in the loop, but no additional "decoding" that I
can see. But again, isn't this an overhead that is common to both kinds of
solutions (and, essentially, to both a bootstrapped and a native approach,
where natively you'd be dealing with function pointers or delegates)? In
fact, my guess and implied question is that our benchmark so far shows
non-backtrackable assignment to be competitive to native code.... no? (I
was running SWI with default settings, BTW.)

> > In fact, a question stands: is an implementation based on
> > non-backtracking assigments worth considering at all?
> > It is not really portable, is it?
>
> If aggregate/3 were a spec and not a library, every system can
> implement as it likes. And it would not be required that some
> file aggregate.pl is shuffeld around.

+1 for discussing the ISO standard and for keeping a standard base library,
if any, to the essential. That said, I'd still take that RISC-like approach
I had mentioned: namely, here I'd rather advocate for the standardization of
non-backtrackable assignment...

-LV

[Jan Burse]

LudovicoVan schrieb:

> Indirect calls are needed in the loop, but no additional "decoding" that
> I can see. But again, isn't this an overhead that is common to both
> kinds of solutions (and, essentially, to both a bootstrapped and a
> native approach, where natively you'd be dealing with function pointers
> or delegates)? In fact, my guess and implied question is that our
> benchmark so far shows non-backtrackable assignment to be competitive to
> native code.... no? (I was running SWI with default settings, BTW.)

Well, change your code from:

loop :-

... S1 is S+A ...

?- loop.

Into the following:

add(S1,S,A) :- S1 is S+A.

loop(X) :-

... call(X,S1,S,A) ...

?- loop(add).

And do a measurement.

As long as the interpreter does not do partial evaluation
from a top query down into invoked predicates, there is not
much chance that this is fast. i.e. as long as loop/1 is
not inlined you see a performance degradation.

In SWI there is probably one. Jekejeke Prolog there is
also probably one, but I tried hard to minimize it. Currently
implementation uses a polymorphic cache, since call/2 is
important in the forward chainer. There we have f(X1,..,Xn)
events which are handled by f(X1,..,Xn,Y) predicates.

Actually now that I mentioned it, I have used call/n in the
incremental prototype. This meta predicate does also do a goal
expansion and goal conversion. Maybe should give a try to the
buddy predicate sys_call/n which bypasses these steps. Oki
Doki. New figures coming soon.

> > If aggregate/3 were a spec and not a library, every system can
> > implement as it likes. And it would not be required that some
> > file aggregate.pl is shuffeld around.
>
> +1 for discussing the ISO standard and for keeping a standard base
> library, if any, to the essential. That said, I'd still take that
> RISC-like approach I had mentioned: namely, here I'd rather
> advocate for the standardization of non-backtrackable assignment...

I was not refering to the ISO standard when I mentioned "spec".
What I wanted to express is that the predicte aggregate/3 has a
conceptual existence independent of some aggregate.pl. This is
also seen in the SICStus documentation, which initial referes
to SQL aggregates as a motivator.

Non backtrackable assigment and the like have already been
proposed as an inclusion to some ISO standard. If you search for
example here for "Global Variables" you find quite a number of hits:

http://people.sju.edu/~jhodgson/wg17/doclist.html

http://people.sju.edu/~jhodgson/wg17/proporsal4.pdf

The destructive compound approach is probably supperior to globally
named variables, since it allows to quickly have garbage collected
thread local value holders. If you have a FFI (Foreign Function
Interface) and a reference datatype, you can also easily implement
such value holders. The reference datatype is necessary, since in
the present case the compounds are not mutable. (*)

Until now I was not very fond of global variables and/or destructive
compounds. I was hoping to cover state via the forward chaining. But
the present case of aggregates seems to produce a business case
for something in this direction. But from the way I would implement
it, i.e. for example the FFI solution, I think it would differ
from the SWI solution, in that it would not be based on compounds.

Maybe this is indicative that it is more difficult to find
consense about low level features than about high level features.

Bye

(*)
Here is a sketch how to do it in the Jekejeke Prolog API. Garbage
collection is left to Java. I was using something similar in my
trial of the incremental aggregates:

public class Holder {
public Term holds;
}

public class DestructiveHolderAPI {

public static TermRef createHolder() {
return new TermRef(new Holder());
}

public static Term accessHolder(TermRef r) {
return ((Holder)r.getValue()).holds;
}

public static void updateHolder(TermRef r, Term v) {
v = .. make a copy of v ..
((Holder)r.getValue()).holds = v;
}

}

[Jan Burse]

Jan Burse schrieb:

> it, i.e. for example the FFI solution, I think it would differ
> from the SWI solution, in that it would not be based on compounds.

The FFI solution I gave is kind of a "safe" variant
of destructive assigment in Prolog. You cannot destroy
some predicate argument or somesuch.

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4sq4q$tsd$1...@news.albasani.net...
> LudovicoVan schrieb:
<snipped>

>> Indirect calls are needed in the loop, but no additional "decoding" that
>> I can see. But again, isn't this an overhead that is common to both
>> kinds of solutions (and, essentially, to both a bootstrapped and a
>> native approach, where natively you'd be dealing with function pointers
>> or delegates)? In fact, my guess and implied question is that our
>> benchmark so far shows non-backtrackable assignment to be competitive to
>> native code.... no? (I was running SWI with default settings, BTW.)
>
> Well, change your code from:
>
> loop :-
>
> ... S1 is S+A ...
>
> ?- loop.
>
> Into the following:
>
> add(S1,S,A) :- S1 is S+A.
>
> loop(X) :-
>
> ... call(X,S1,S,A) ...
>
> ?- loop(add).
>
> And do a measurement.

If I do that as below, I get pretty much the same results as earlier, just
with the overhead of the switch (which is additional functionality, anyway).
I.e. the overhead of using call/_ as below is negligible. But I have not
tried to implement a full-fledged aggregation predicate, so I am not yet
sure this approach can be pushed that far.

perfect_(nb_sum_call, High, X) :-

between(1, High, X),
Y is X // 2,
NbSum = nb(0),
forall(
( between(1, Y, Z),
X rem Z =:= 0
),
( arg(1, NbSum, S),

( false
-> fail
; false
-> fail
; false
-> fail
; false
-> fail
; call((S1 is S + Z))
),

nb_setarg(1, NbSum, S1)
)
),
arg(1, NbSum, X).

?- perfect_test.

perfect(nb_sum_call, 10000) -> 6
perfect(nb_sum_call, 10000) -> 28
perfect(nb_sum_call, 10000) -> 496
perfect(nb_sum_call, 10000) -> 8128
% 25,625,683 inferences, 8.471 CPU in 8.480 seconds (100% CPU, 3025159 Lips)

perfect(nb_sum, 10000) -> 6
perfect(nb_sum, 10000) -> 28
perfect(nb_sum, 10000) -> 496

perfect(nb_sum, 10000) -> 8128
% 25,291,011 inferences, 8.346 CPU in 8.360 seconds (100% CPU, 3030296 Lips)

perfect(findall, 10000) -> 6
perfect(findall, 10000) -> 28
perfect(findall, 10000) -> 496

perfect(findall, 10000) -> 8128
% 25,391,011 inferences, 8.377 CPU in 8.380 seconds (100% CPU, 3030947 Lips)

> I was not refering to the ISO standard when I mentioned "spec".
> What I wanted to express is that the predicte aggregate/3 has a conceptual
> existence independent of some aggregate.pl. This is
> also seen in the SICStus documentation, which initial referes
> to SQL aggregates as a motivator.

Well, pardon my insistence on standards: I'd definitely I agree that a
(standard!) aggregate/3 would be very good to have, and that SQL can tell
something on this side, etc.

> The destructive compound approach is probably supperior to globally
> named variables, since it allows to quickly have garbage collected
> thread local value holders.

Also great in that the scope is local.

> Maybe this is indicative that it is more difficult to find
> consense about low level features than about high level features.

You know, IMHO, all is needed is a proper standard: a definite semantics of
a core, essential, set of predicates, possibly over a grammar of reasonable
complexity. Then implementation is feasible and portability can happen.

-LV

[Jan Burse]

LudovicoVan schrieb:

> perfect_(nb_sum_call, High, X) :-
> between(1, High, X),
> Y is X // 2,
> NbSum = nb(0),
> forall(
> ( between(1, Y, Z),
> X rem Z =:= 0
> ),
> ( arg(1, NbSum, S),
> ( false
> -> fail
> ; false
> -> fail
> ; false
> -> fail
> ; false
> -> fail
> ; call((S1 is S + Z))
> ),
> nb_setarg(1, NbSum, S1)
> )
> ),
> arg(1, NbSum, X).

The above is not a call/n, its a call/1. Its not the
higher order solution I have in mind. Also note you
have a finite if-then-else. But if you allow arbitrary
constructors in an aggregate a finite if-then-else would
not do.

> ?- perfect_test.

> perfect(nb_sum_call, 10000) -> 8128
> % 25,625,683 inferences, 8.471 CPU in 8.480 seconds (100% CPU,
3025159 Lips)
>

> perfect(nb_sum, 10000) -> 8128
> % 25,291,011 inferences, 8.346 CPU in 8.360 seconds (100% CPU,
3030296 Lips)

All you have measured is the if-then-else and the call/1
overhead. Usually call/1 has a much smaller overhead than
call/n. But I am not sure whether this also holds for
SWI.

Bye

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4t9ar$856$1...@news.albasani.net...

Sure it will: that is switching over the available aggregation operators...

-LV

[Jan Burse]

Jan Burse schrieb:

> The above is not a call/n, its a call/1. Its not the
> higher order solution I have in mind. Also note you
> have a finite if-then-else. But if you allow arbitrary
> constructors in an aggregate a finite if-then-else would
> not do.

Also the if-then-else or whatever decoding logic for
the next step function of the aggregate would be done
outside of the forall/2, only once. So that inside the
forall/2 only the computed closure is called but no
decoding logic is needed.

Here is an example of such a next step decoding logic,
that can be used with call/3.

% decode_next_step(+Aggregate, -Closure)
% min, max, bag, set, etc..
decode_next_step(count, next_count) :- !.
decode_next_step(sum(X), next_sum(X)) :- !.
decode_next_step(C, next_constr(R)) :- C=..[_|L],
decode_next_step_list(L,R).

% decode_next_step_list(+Aggregates, -Closures)
decode_next_step_list([], []).
decode_next_step_list([A|As], [C|Cs]) :-
decode_next_step(A,C),
decode_next_step_list(As,Cs).

next_count(X,Y) :- Y is X+1.
next_sum(X,Y,Z) :- Z is Y+X.
next_constr(Cs,X,Y) :-
X=..[F|L],
next_list(Cs,L,R),
Y=..[F|R].

next_list([],[],[]).
next_list([C|Cs],[X|Xs],[Y|Ys]) :-
call(C,X,Y),
next_list(Cs,Xs,Ys).

Also provide decode_init_value/2 and decode_unpack_result/2.
The unpack is needed for the bag and set aggregate. Then
one can do the loop as follows:

accumulate(A,G,R) :-
decode_init_value(A,I),
decode_next_step(A,S),
decode_unpack_result(A,U),
/* set holder to I */
(
G,
/* retrieve holder into J */
call(S,J,K),
/* set holder to K */
fail; true
)
/* retrieve holder into J */
call(U,J,R).


Bye

[Jan Burse]

LudovicoVan schrieb:

>
> Sure it will: that is switching over the available aggregation operators...

There are infinitely many, and they are recursive. You
cannot switch over them. See SICStus docu:
http://www.sics.se/sicstus/docs/4.2.0/html/sicstus/lib_002daggregate.html

"where:

Template is operator(expression) or constructor(arg,...,arg)
each arg is operator(expression)
operator is sum | min | max {for now}
expression is an arithmetic expression"

Ok, they restrict arg to operator. So its not really recursive.
But I guess the constructor can be arbitrary long. For example
if you have a table t of 10 arguments, you can do:

aggregate(x(sum(X1),..,sum(X10)),t(X1,..,X10),R).

Bye

[Jan Burse]

Jan Burse schrieb:

> Here is an example of such a next step decoding logic,
> that can be used with call/3.

For a definition of call/n see here:
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call

[Jan Burse]

Jan Burse schrieb:

> accumulate(A,G,R) :-
> decode_init_value(A,I),
> decode_next_step(A,S),
> decode_unpack_result(A,U),
> /* set holder to I */
> (
> G,
> /* retrieve holder into J */
> call(S,J,K),
> /* set holder to K */
> fail; true
> )
> /* retrieve holder into J */
> call(U,J,R).
>

In the above there is also a meta call for G, which
slows down matters. G must be checked and converted
before called. I guess it is valid to do this once
before the loop. How to do this once is not shown
in the above code. It needs some low level coding.

But this also adds to the slowdown, if the check
and conversion is done everytime inside the loop.
So the meta call of G and call/3 both add up in
time, and gave me the bad figures. New figures
comming soon...

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4tak9$bfk$1...@news.albasani.net...

> LudovicoVan schrieb:
>>
>> Sure it will: that is switching over the available aggregation
>> operators...
>
> There are infinitely many, and they are recursive.

They aren't: the template could be a term of arbitrary complexity, but it
must contain occurrences from a finite set of operators, and those need to
be solved. Multiple occurrences of the same operator must unify together:
i.e. only one result per each distinct operator that appears in the template
needs to be computed.

-LV

[Jan Burse]

LudovicoVan schrieb:

> They aren't: the template could be a term of arbitrary complexity, but
> it must contain occurrences from a finite set of operators, and those
> need to be solved. Multiple occurrences of the same operator must unify
> together: i.e. only one result per each distinct operator that appears
> in the template needs to be computed.

Each operator has an argument (*). sum(X) and sum(Y) are not the
same function. You cannot use the same step operation for it
and the same holder location for it.

?- accumulate(x(sum(X),sum(Y)),t(X,Y),R)

You cannot turn this into:

loop :-
...
S1 is S+A
...

Its not one sum. Its two sums. You need to have something like:

loop :-
...
S1 is S+A

T1 is T+B
...

Bye

(*)

See SICStus docu:
http://www.sics.se/sicstus/docs/4.2.0/html/sicstus/lib_002daggregate.html

"where:

Template is operator(expression) or constructor(arg,...,arg)
each arg is operator(expression)
operator is sum | min | max {for now}
expression is an arithmetic expression"

The operator() is followed by an expression.

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4tbla$cui$1...@news.albasani.net...

> LudovicoVan schrieb:
>
>> They aren't: the template could be a term of arbitrary complexity, but
>> it must contain occurrences from a finite set of operators, and those
>> need to be solved. Multiple occurrences of the same operator must unify
>> together: i.e. only one result per each distinct operator that appears
>> in the template needs to be computed.
>
> Each operator has an argument (*). sum(X) and sum(Y) are not the
> same function. You cannot use the same step operation for it
> and the same holder location for it.
>
> ?- accumulate(x(sum(X),sum(Y)),t(X,Y),R)

I'd just expect X and Y to be unified to the same value at the end of the
operation.

> You cannot turn this into:
>
> loop :-
> ...
> S1 is S+A
> ...
>
> Its not one sum. Its two sums. You need to have something like:
>
> loop :-
> ...
> S1 is S+A
> T1 is T+B
> ...

I just don't get why you would do that: how could sum(X) ever be different
from sum(Y) at the end of the operation?

I also think you should have a second look at the SICStus doc: the template
specification is simpler than you seem to imply. In particular, you are not
allowed more than one level of nesting. In fact, if I will ever get to
implement this, I will just use a flat list: I see no advantage in having a
user-defined principal functor, OTOH the syntax for options is much more
common (for all I know, of course).

-LV

[LudovicoVan]

"LudovicoVan" <ju...@diegidio.name> wrote in message
news:k4tckg$ulc$1...@dont-email.me...

> "Jan Burse" <janb...@fastmail.fm> wrote in message
> news:k4tbla$cui$1...@news.albasani.net...
>> LudovicoVan schrieb:
>>
>>> They aren't: the template could be a term of arbitrary complexity, but
>>> it must contain occurrences from a finite set of operators, and those
>>> need to be solved. Multiple occurrences of the same operator must unify
>>> together: i.e. only one result per each distinct operator that appears
>>> in the template needs to be computed.
>>
>> Each operator has an argument (*). sum(X) and sum(Y) are not the
>> same function. You cannot use the same step operation for it
>> and the same holder location for it.
>>
>> ?- accumulate(x(sum(X),sum(Y)),t(X,Y),R)
>
> I'd just expect X and Y to be unified to the same value at the end of the
> operation.

OK, sorry, now I see what you mean: I'll have to think about it, although at
a first glance it does not seem like a dramatic complication...

Thanks for the conversation and good night for now,

-LV

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4tb5q$ca5$1...@news.albasani.net...

In the meantime I have tried the variant below: but still no need for call/n
really popping up. In fact, I have also checked the code in the
aggregate.pl that ships with SWI-Prolog, implemented using findall, etc.:
among other things, even there the only todo's mentioned are:

To be done
- Analysing the aggregation template and compiling a
predicate for the list aggregation can be done at compile
time.
- aggregate_all/3 can be rewritten to run in constant
space using non-backtrackable assignment on a term.

Indeed, using non-backtrackable assignment, there is no additional overhead
that I can see: the significant difference is that there is no need for two
scans, one can compute solutions while looping.

perfect_(nb_call, High, X) :-

between(1, High, X),
Y is X // 2,

Gen = (between(1, Y, Z), X rem Z =:= 0),
Sum = Z,
perfect_nb_call_(Gen, Sum, X).

perfect_nb_call_(Gen, Sum, X) :-
NbSum = nb(0),
forall(
Gen,
( arg(1, NbSum, S),
S1 is S + Sum,

nb_setarg(1, NbSum, S1)
)
),
arg(1, NbSum, X).

?- perfect_test.
perfect(nb_call, 10000) -> 6
perfect(nb_call, 10000) -> 28
perfect(nb_call, 10000) -> 496
perfect(nb_call, 10000) -> 8128
% 25,301,011 inferences, 8.315 CPU in 8.330 seconds (100% CPU, 3042869 Lips)

perfect(nb_sum, 10000) -> 6
perfect(nb_sum, 10000) -> 28
perfect(nb_sum, 10000) -> 496

perfect(nb_sum, 10000) -> 8128
% 25,291,011 inferences, 8.284 CPU in 8.299 seconds (100% CPU, 3053123 Lips)

perfect(findall, 10000) -> 6
perfect(findall, 10000) -> 28
perfect(findall, 10000) -> 496
perfect(findall, 10000) -> 8128

% 25,391,011 inferences, 8.284 CPU in 8.284 seconds (100% CPU, 3065195 Lips)

-LV

[Jan Burse]

LudovicoVan schrieb:

> ?- perfect_test.
> perfect(nb_call, 10000) -> 6
> perfect(nb_call, 10000) -> 28
> perfect(nb_call, 10000) -> 496
> perfect(nb_call, 10000) -> 8128
> % 25,301,011 inferences, 8.315 CPU in 8.330 seconds (100% CPU, 3042869
> Lips)
>
> perfect(nb_sum, 10000) -> 6
> perfect(nb_sum, 10000) -> 28
> perfect(nb_sum, 10000) -> 496
> perfect(nb_sum, 10000) -> 8128
> % 25,291,011 inferences, 8.284 CPU in 8.299 seconds (100% CPU, 3053123
> Lips)

Thanks again for sharing. So now you have ~100ms overhead
for the call of the goal. And in another post you had ~100ms
overhead for the call of the is/2. This adds up to
already an overhead of ~200ms.

Now if you would do some proper decoding of the aggregate,
with or without call/n, you will finally arrive at some
overall overhead >= ~200ms for the accumulate/3 (*) predicate.
Maybe your overall overhead will stay below 5%.

The overhead for an incremental aggreate/3 can be even
worse compared to the overhead of accumulate/3, since you
would need to deal with the grouping of witnesses.
Especially with generating a variant witness and index
into some data structure.

I also published figures for aggregate/3. I used some
fast internals already developed for bagof/3. Including
some direct access to some index data structure. Good
thing was it did not degrade considerably.

Jan Burse wrote:
> prefect1 findall 985 (ms)
> prefect2 bagof 979 (ms)

> prefect3 accumulate 1'227 (ms) (incremental, does not use findall)
> prefect4 aggregate 1'280 (ms) (incremental, does not use bagof)

My overall overhead in the above measure was >20%,
and not only <5%. But during the discussion here I saw
already some weak spots (call/n --> sys_call/n), so
maybe can bring it also down to 5%.

5% would be acceptable I guess. Let's see, we are still both
challenged here ...

Bye

(*)
I take accumulate/3 = aggregate_all/3.

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4ueo3$6mg$1...@news.albasani.net...
> LudovicoVan schrieb:
<snipped>

> Thanks again for sharing. So now you have ~100ms overhead

> for the call of the goal. And in another post you had [...]

Hmm, I may be missing something, but most of the overheads you are counting
I still would say belong to the functionality we are adding relative to your
original example. IOW, a full-fledged aggregation predicate would have all
that in any case. The only open bet I see is that a non-backtracking
version performs pretty much as the boot-strapped version (compensating
slowness for the single pass): and I have, for now, no glimpse that it can
perform better.

> 5% would be acceptable I guess. Let's see, we are still both
> challenged here ...

Cool! :) Well, at some point I might even try and extend from the
aggregate.pl that ships with SWI-Prolog, as I do not see what else we could
benchmark before getting into templates and all that. But the preliminary
question I am hinting at above stands: would such an effort be worth it?

-LV

[Jan Burse]

LudovicoVan schrieb:

> But the preliminary question I am hinting at above stands:
> would such an effort be worth it?

My initial expectation was, and I still hold this expectation,
that there is no overhead at all, but a speed up. So I am
currently working on:

> prefect3 accumulate ?? (ms) (incremental, does not use findall)
> prefect4 aggregate ?? (ms) (incremental, does not use bagof)
> prefect5 accumulate ?? (ms) (materializing, uses findall)
> prefect6 aggregate ?? (ms) (materializing, uses bagof)

For perfect5 and prefect6 I could use aggregate.pl, but I have
my own implementation right now. But it still needs a little
fix before I can show results. For perfect3 and prefect4 I
have already showed some figures, but there is also a
rework sheduled.

The expectation is basically:

perfect3 < perfect5

perfect4 < perfect6

Can this be verifyed? If not what does it indicate?

Bye

P.S.: To verify the above hypothesis one cannot use nb_sum or some
such. It must have the interface of accumulate/3 respective
aggregate/3, called with an aggregate denotation inside the
test case. Here are the test cases again:

/****************************************************/
/* Accumulate */
/****************************************************/

perfect3/5(Hi,X) :-
between(1,Hi,X),

Y is X // 2,

accumulate(sum(Z),(between(1,Y,Z), (X rem Z =:= 0)),X).

perfect3/5 :-
perfect3/5(500,_).

/****************************************************/
/* Aggregate */
/****************************************************/

perfect4/6(Hi,X) :-
aggregate(sum(Z),Y^(between(1,Hi,X),

Y is X // 2,

(between(1,Y,Z), (X rem Z =:= 0))),X).

perfect4/6 :-
perfect4/6(500,_).


P.S.S:
I take accumulate/3 = aggregate_all/3

[Ulrich Neumerkel]

"LudovicoVan" <ju...@diegidio.name> writes:
>perfect_(nb_sum, High, X) :-
> between(1, High, X),
> Y is X // 2,
> NbSum = nb(0),

NbSum = nb(0, _), % additional argument

> forall(
> ( between(1, Y, Z),
> X rem Z =:= 0
> ),
> ( arg(1, NbSum, S),
> S1 is S + Z,
> nb_setarg(1, NbSum, S1)
> )
> ),
> arg(1, NbSum, X).

Please note that a semantics for nb_setarg/3 is very
difficult to establish ; for ground terms it is
next-to-impossible. That is, you are currently
depending a lot on some implementation details that
might easily change.

Think of unfolding perfect_/3 once. It can easily
happen that this would cause nb(0) to be shared with a
user term that accidentally happens to be nb(0).

Adding an extra argument being an uninstantiated variable
mitigates the problem.

[LudovicoVan]

"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
news:2012Oct...@mips.complang.tuwien.ac.at...

> "LudovicoVan" <ju...@diegidio.name> writes:
>
>>perfect_(nb_sum, High, X) :-
>> between(1, High, X),
>> Y is X // 2,
>> NbSum = nb(0),
>
> NbSum = nb(0, _), % additional argument
>
>> forall(
>> ( between(1, Y, Z),
>> X rem Z =:= 0
>> ),
>> ( arg(1, NbSum, S),
>> S1 is S + Z,
>> nb_setarg(1, NbSum, S1)
>> )
>> ),
>> arg(1, NbSum, X).
>
> Please note that a semantics for nb_setarg/3 is very
> difficult to establish ; for ground terms it is
> next-to-impossible. That is, you are currently
> depending a lot on some implementation details that
> might easily change.

I think you have in mind nb_linkarg/3: nb_setarg/3, at least in SWI-Prolog,
is a "safe" variant that first duplicates the value with duplicate_term/2, a
"version of copy_term/2 that also copies ground terms".

> Think of unfolding perfect_/3 once. It can easily
> happen that this would cause nb(0) to be shared with a
> user term that accidentally happens to be nb(0).
>
> Adding an extra argument being an uninstantiated variable
> mitigates the problem.

I have read about this problem in the docs for nb_linkarg/3 and
nb_linkval/2, although there is not enough information there for me to
understand exactly what the underlying issue is (and why it is difficult to
establish a definite semantics: despite I have a vague idea about
folding/unfolding). If I can dare ask, a minimal example of how things can
go wrong would greatly help...

-LV

[Ulrich Neumerkel]

This duplication is only of relevance for arguments being
compound terms. In the example discussed we have simple integers.

The problem here is the original term in NbSum = nb(0). There is no
indication that this could not be shared with another term nb(0)
meaning something else and occuring somewhere else. Unfolding
might bring these otherwise separate representations together. So
prior to calling any nb_*, the terms might already share, when they
should not. Adding a (unique) variable to nb/1 prevents that
accidental sharing.

For the general case, there are many anomalies, like:

?- functor(T,f,2),functor(S,f,2),T=S,nb_setarg(1,T,2).
T = S, S = f(2,_G1871).

?- functor(S,f,2),functor(T,f,2),T=S,nb_setarg(1,T,2).
S = f(_G1870,_G1871),
T = f(2,_G1871).

But these are not that problematic: They only occur if
you are - on purpose - unifying such terms.

These things are not entirely hypothetical, unfolding is already
done in SWI when using library(apply_macros).

[LudovicoVan]

Sorry, I do not get the cogency of your example, where you are sharing the
very container, not the value (and nb_setarg duplicates the value). Is it
that another reference to nb(0) could exist what you mean by "NbSum = nb(0)
could be shared with another term nb(0)"? I feel like I am missing the
basic what is what here...

A subsequent, more specific question would be: is it ever the case that how
such predicates behave is beyond the control of the programmer? IOW,
assuming that the non-backtracking logic is properly encapsulated, is it
still possible that our non-backtracking predicate could behave differently
under different circumstances/usage scenarios?

For instance, say we have perfect_/3 defined as above, and a predicate
perfect_test/0 that calls it as:

perfect_test :- perfect_(nb_sum, 500, X), writeln(X).

The unfolding I would imaging is:

perfect_test :- writeln(6).
perfect_test :- writeln(28).
perfect_test :- writeln(496).

But, where is it that that (or anything similar) can go wrong?

-LV

[Jan Burse]

Ulrich Neumerkel schrieb:

> These things are not entirely hypothetical, unfolding is already
> done in SWI when using library(apply_macros).

The TermRef and FFI (*) (**) solution I gave is immune to
compound aliasing. Since the TermRef that wraps the holder
is opaque against unification.

But since one can arbitrarily pass around TermRef, for example
assert by one thread and retract by another thread, pretty
ugly things can happen neverthless.

But these ugly things are not the result of partial evaluation,
but stem from dangerous application logic. :-)

Bye

(*)
http://www.jekejeke.ch/idatab/doclet/prod/docs/05_run/03_interface/06_term/08_ref.html

(**)
http://www.jekejeke.ch/idatab/doclet/prod/docs/05_run/03_interface/06_term/08_ref.html

[Jan Burse]

LudovicoVan schrieb:

> Sorry, I do not get the cogency of your example, where you are sharing
> the very container, not the value (and nb_setarg duplicates the value).
> Is it that another reference to nb(0) could exist what you mean by
> "NbSum = nb(0) could be shared with another term nb(0)"? I feel like I
> am missing the basic what is what here...

Well if you want to burn Prolog clauses into a ROM, you cannot
use nb_setarg anymore. At least if I were to create a read-only
format of clauses I would encode nb(0) (*) as some byte sequence
that cannot be modified.

It begs the question whether your perfect_(nb_sum, High, X) is
really reentrant. Can it for example be used recursively or
concurrently? Did you do some tests? Mostlikely the correct
code would need to replace:

NbSum = nb(0)

By:

functor(NbSum,nb,1)

Which eventually changes the performance a little bit.

Bye

(*)
In Jekejeke Prolog it would definitely generate some intermediate
code where the compound is shared among different clause
invokation, making your code not reentrant.

[Jan Burse]

Jan Burse schrieb:

> (*)
> http://www.jekejeke.ch/idatab/doclet/prod/docs/05_run/03_interface/06_term/08_ref.html
> (**)
> http://www.jekejeke.ch/idatab/doclet/prod/docs/05_run/03_interface/06_term/08_ref.html

Oops, twice the same link. The other link is:
http://www.jekejeke.ch/idatab/doclet/prod/docs/05_run/03_interface/05_concepts/04_reference.html

[Jan Burse]

Jan Burse schrieb:

> Oops, twice the same link. The other link is:
> http://www.jekejeke.ch/idatab/doclet/prod/docs/05_run/03_interface/05_concepts/04_reference.html
>

Oops, have to rephrase the text, there is no such thing as ISO Prolog
handle/pointer. We only have things such as

7.10.2.1 Stream-term
A stream-term identifies a stream during a call of an
input/output built-in predicate. It is an implementation
dependent ground term which is created as a result of
opening a source/sink by a call of open/4 (8.11.5). A
stream-term shall not be an atom.

A standard-conforming program shall make no assumptions
about the form of the stream-term, except that:
a) It is a ground term.
b) It is not an atom.
c) It uniquely identifies a particular stream during the
time that the stream is open.

It is implementation dependent whether or not the processor
uses the same stream-term to represent different
source/sinks at different times.

NOTE - A stream-term is not an atom so that it can be
distinguished from an alias.

Must have been thinking about external stream term
representations such as '$stream'(<memory address>) in
some Prolog systems. But these representations are
practically not anymore found because of GC.

[LudovicoVan]

"Jan Burse" <janb...@fastmail.fm> wrote in message

news:k4vf5e$goh$1...@news.albasani.net...

> LudovicoVan schrieb:
>
>> Sorry, I do not get the cogency of your example, where you are sharing
>> the very container, not the value (and nb_setarg duplicates the value).
>> Is it that another reference to nb(0) could exist what you mean by
>> "NbSum = nb(0) could be shared with another term nb(0)"? I feel like I
>> am missing the basic what is what here...
>
> Well if you want to burn Prolog clauses into a ROM, you cannot
> use nb_setarg anymore. At least if I were to create a read-only
> format of clauses I would encode nb(0) (*) as some byte sequence
> that cannot be modified.

Well, in that case I'd guess you would not have an nb_setarg to begin with.

> It begs the question whether your perfect_(nb_sum, High, X) is
> really reentrant. Can it for example be used recursively or
> concurrently? Did you do some tests? Mostlikely the correct
> code would need to replace:

Some tests? Based partly on the nb_set and mainly on the existing assoc
modules in SWI-Prolog, I have myself written, now almost complete, an
nb_dict (non-backtracking dictionary). I have no idea about concurrent code
as I have not tried that, but there is surely no problem with recursion.

But I was after a possibly clear and definite explanation, not some more
trial and error.

-LV

[Jan Burse]

LudovicoVan schrieb:

> Some tests? Based partly on the nb_set and mainly on the existing assoc
> modules in SWI-Prolog, I have myself written, now almost complete, an
> nb_dict (non-backtracking dictionary). I have no idea about concurrent
> code as I have not tried that, but there is surely no problem with
> recursion.

It could be that the dictionary recursively works since in different
recursion levels, you are using different compounds. This happens for
example if a dictionary is implemented as a tree.

But it is easy to check whether accumulate/3 is reentrant,
just try the following:

?- accumulate(sum(R*X), (between(1,10,X),
accumulate(sum(Y), between(1,10,Y), R)), S).
S = 3025

Bye

P.S.: I take accumulate/3 = aggregate_all/3.

[Ulrich Neumerkel]

"LudovicoVan" <ju...@diegidio.name> writes:
>"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
>news:2012Oct...@mips.complang.tuwien.ac.at...

>> The problem here is the original term in NbSum = nb(0). There is no
>> indication that this could not be shared with another term nb(0)
>> meaning something else and occuring somewhere else. Unfolding
>> might bring these otherwise separate representations together. So
>> prior to calling any nb_*, the terms might already share, when they
>> should not. Adding a (unique) variable to nb/1 prevents that
>> accidental sharing.
>>

...

>> These things are not entirely hypothetical, unfolding is already
>> done in SWI when using library(apply_macros).
>
>Sorry, I do not get the cogency of your example, where you are sharing the
>very container, not the value (and nb_setarg duplicates the value). Is it
>that another reference to nb(0) could exist what you mean by "NbSum = nb(0)
>could be shared with another term nb(0)"? I feel like I am missing the
>basic what is what here...

It is a valid static optimization to fold several identical terms, as in:

... :- ..., P = nb(0), ..., Q = nb(0), ...

which can be replaced by:

... :- ..., P = nb(0), ..., Q = P, ...

In many parts you have already no control over such issues. Exactly
such optimizations change from release to release.

Similar things could also happen when meta-interpreting a clause:
A clever copy_term/2 might detect identical subterms.

>A subsequent, more specific question would be: is it ever the case that how
>such predicates behave is beyond the control of the programmer? IOW,
>assuming that the non-backtracking logic is properly encapsulated, is it
>still possible that our non-backtracking predicate could behave differently
>under different circumstances/usage scenarios?

Yes, GC could identify identical subterms and share them regardless of
your efforts of encapsulation.

>The unfolding I would imaging is:
>
>perfect_test :- writeln(6).
>perfect_test :- writeln(28).
>perfect_test :- writeln(496).

Here, you did much more unfolding, I simply thought about replacing the
rule by its body once. Such simple replacements are also performed
by apply_macros.

[Jan Burse]

Jan Burse schrieb:

> But it is easy to check whether accumulate/3 is reentrant,
> just try the following:
>
> ?- accumulate(sum(R*X), (between(1,10,X),
> accumulate(sum(Y), between(1,10,Y), R)), S).
> S = 3025

When using nb_setarg in the case of SWI-Prolog it will be
most likely reentrant. Since it seems that ground compounds
inside a clause are push on the environment each time a
clause is invoked. Like in WAM I guess. Or some other technique
is behind it, makeing it local.



Here is some test code:

/* Holder inside a clause */
p(0, 0).
p(s(X), s(Y)) :-
Holder=nb(0),
nb_setarg(1, Holder, X),
p(X, _),
arg(1, Holder, Y).

/* The ground term seems not to be shared */
?- p(s(0),X).
X = s(0).

?- p(s(s(0)),X).
X = s(s(0)).

?- p(s(s(s(0))),X).
X = s(s(s(0))).

?- p(s(s(s(s(0)))),X).
X = s(s(s(s(0)))).



And just for illustration, what happens if we explicitly share:

/* Holder passed as argument */
q(0, 0, _).
q(s(X), s(Y), Holder) :-
nb_setarg(1, Holder, X),
q(X, _, Holder),
arg(1, Holder, Y).

/* Now of course, things go wrong */
?- q(0,X,nb(0)).
X = 0.

?- q(s(0),X,nb(0)).
X = s(0).

?- q(s(s(0)),X,nb(0)).
X = s(0).

?- q(s(s(s(0))),X,nb(0)).
X = s(0).

[LudovicoVan]

"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
news:2012Oct...@mips.complang.tuwien.ac.at...

> "LudovicoVan" <ju...@diegidio.name> writes:
<snipped>

>>Sorry, I do not get the cogency of your example, where you are sharing the
>>very container, not the value (and nb_setarg duplicates the value). Is it
>>that another reference to nb(0) could exist what you mean by "NbSum =
>>nb(0)
>>could be shared with another term nb(0)"? I feel like I am missing the
>>basic what is what here...
>
> It is a valid static optimization to fold several identical terms, as in:
>
> ... :- ..., P = nb(0), ..., Q = nb(0), ...
>
> which can be replaced by:
>
> ... :- ..., P = nb(0), ..., Q = P, ...
>
> In many parts you have already no control over such issues. Exactly
> such optimizations change from release to release.
>
> Similar things could also happen when meta-interpreting a clause:
> A clever copy_term/2 might detect identical subterms.

But, at least in these cases, it seems to me that we do have control: we
could have written, as you had suggested earlier, P = nb(0, _) and Q = nb(0,
_), or even P = nbp(0) and Q = nbq(0), or even, I suppose, P = nb(p, 0) and
Q = nb(q, 0), etc. I mean, it seems to be in fact under the control of the
programmer whether or not there are multiple references to the same
"holder", no?

>>A subsequent, more specific question would be: is it ever the case that
>>how
>>such predicates behave is beyond the control of the programmer? IOW,
>>assuming that the non-backtracking logic is properly encapsulated, is it
>>still possible that our non-backtracking predicate could behave
>>differently
>>under different circumstances/usage scenarios?
>
> Yes, GC could identify identical subterms and share them regardless of
> your efforts of encapsulation.

Now you say "subterms": is it yet not as simple as I am getting it above?
E.g. do you mean the P = nb(p, 0) and Q = nb(q, 0) would not work? Would at
least the P = nb(0, _) and Q = nb(0, _) be guaranteed to work? (Assuming
the "incapsulation", i.e. that we are not sharing P or Q with the caller, as
in Jan's most recent example in another sub-thread.)

>>The unfolding I would imaging is:
>>
>>perfect_test :- writeln(6).
>>perfect_test :- writeln(28).
>>perfect_test :- writeln(496).
>
> Here, you did much more unfolding, I simply thought about replacing the
> rule by its body once. Such simple replacements are also performed
> by apply_macros.

I could have written it less aggressively, although the result seems to be
the same:

perfect_test :- X = 6, writeln(X).

Anyway, I thought unfolding was about replacing a subgoal with the
disjunction of its bindings (if that's correct terminology), not about
replacing it with its body. In the latter case I understand there could
unintended sharing of terms, although couldn't even these be circumvented,
say by adopting normative coding convention along the lines I am guess
above?

Incidentally (and assuming I am not in fact still overlooking something),
all this would not be a problem if it were standardized with a definite
semantics: there we might even have a standard built-in like -say-
new_nb_container/1 (or new_nb_container/2 for named containers) that is
guaranteed to return a reference to a new, non-shared container... or
something similar, the main difference with global variables being that
these are local to the stack frame.

-LV

[LudovicoVan]

"LudovicoVan" <ju...@diegidio.name> wrote in message

news:k517sj$mav$1...@dont-email.me...

> ... I thought unfolding was about replacing a subgoal with the disjunction
> of its bindings (if that's correct terminology) ...

I meant, the conjunction: please bear with me... In any case, that is indeed
not unfolding.

-LV

[Jan Wielemaker]

I agree with Ulrich. If you do not want surprises with (nb_)setarg
and friends, add a dummy variable. It stops aggressive sharing in code
optimization and GC. I'm not saying this will happen soon in SWI-Prolog,
but it I don't say it will nevery happen.

Cheers --- Jan

[LudovicoVan]

"Jan Wielemaker" <j...@invalid.invalid> wrote in message
news:50746ecc$0$26352$afc3...@read01.usenet4all.se...

I'm afraid I don't get it, and nobody answers my questions directly...
Also, I have had a look at your nb_rbtrees and nb_set modules (in
SWI-Prolog), and you don't do that!

-LV

[LudovicoVan]

"LudovicoVan" <ju...@diegidio.name> wrote in message

news:k52qu9$bbv$1...@dont-email.me...

For instance, I have a parented AVL tree where terminals are compounds of
the form nb(dict(P)), with P (a reference to the parent node) unbound at the
top. I should rather be using some nb(dict(P), _), correct?

OTOH, proper nodes of the tree are of the form nb(dict(K, V, P, L, R, S,
B)), where keys are ground and unique. Should I be adding a singleton
variable here as well?

Note: I am using nb_linkarg/3 to swap references around when rebalancing a
tree, and even to link a new value into a node, so that further bindings of
values are shared with the caller. In fact, I am more or less thinking
variables as pointers...

-LV

[LudovicoVan]

"LudovicoVan" <ju...@diegidio.name> wrote in message

news:k52v59$sk6$1...@dont-email.me...

I guess am mainly unclear if, in this problem of unintended sharing, what is
shared is atoms, or principal names of compound terms or sub-terms, or
entire ground terms, or all of these.

-LV