multisets

Jan Wielemaker wrote:

> Anyone with a rough model of Prolog execution will assume that the
> findall/between version is slower. Ok, on one particular system it is
> the other way around, but by so little it doesn't matter much which
> option you choose.

Eh, no.
As a user I expect the numlist version to be faster by a factor 4 to 15
(according to my measurements on other systems, that is reasonable).
So if in a particular system, the numlist version is as slow as the findall
version, the difference between what I expected to get and what I actually g
et
is huge, not little - and so it does matter.

Cheers

Bart Demoen

On 2008-02-28, Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> Jan Wielemaker wrote:
> 
>
> Eh, no.
> As a user I expect the numlist version to be faster by a factor 4 to 15
> (according to my measurements on other systems, that is reasonable).
> So if in a particular system, the numlist version is as slow as the findal
l
> version, the difference between what I expected to get and what I actually
 get
> is huge, not little - and so it does matter.

Well, that depends.  If you *need* the list of integers, there are
these two choices (in a lot of variations of course).  So you take
numlist/3 and you are happy on (I hope) all systems.  If you have the
choice to solve your problem without generating the list of integers,
things may become different.  Still, the
non-findall/assert/whatever-database-operation version is generally
faster on most Prolog systems, given equal complexity of the
algorithm.

Of course it is annoying that the execution time of your algorithm is
hard to estimate on a particular Prolog platform and thus a
`non-portable' aspect of the program.

This is not new and not unique to Prolog. SWI-Prolog uses two
radically different implementations for message queues between threads
(Windows/Unix), because after simple porting of the Unix implemention
using pthread-win32 the Windows version was 100 times slower.  This
was caused by pthread-win32 sticking too close to the POSIX semantics
for condition variables.  A weaker conforming implementation that
still satisfied Prolog's needs could be implemented, getting
comparable performance.

I have encountered many similar issues in the operating system
interfaces.  Annoying, but a fact of life.  The good news it that as
long as there is a healthy competition some of these issues are
resolved.

Cheers --- Jan

On Fri, 22 Feb 2008, Stephan Lukits wrote:

> Hi,
> this time I wonder how the Prolog gs would write
> a predicate which gets multisets of cardinality C
> filled with numbers between M and N (inclusive).
> (Example: C: 2, M: 1, N 2:
> [1, 1]; [1, 2]; [2,2] (because [1, 2] = [2, 1]))


Try to think logically and recursively.

The multiset of cardinality C filled with numbers between
M and N is:

The multiset of cardinality C filled with numbers between M+1 and N

appended to

The multiset of cardinality C-1 with filled with numbers between
M+1 and N, modified by adding M to each set.

From this, the Prolog program follows.

The basis of learning to program in Prolog is that you think in terms
like this when you are presented with a problem like this. If you
immediately start thinking in terms of Prolog code, you have lost it -
you are learning the ABC without first learning the language as a mother
tongue.

Matthew Huntbach

On Mar 3, 5:08 am, Matthew Huntbach <m...@dcs.qmul.ac.uk> wrote:
> On Fri, 22 Feb 2008, Stephan Lukits wrote: 
>
> Try to think logically and recursively.

> The multiset of cardinality C filled with numbers between
> M and N is:
>
> The multiset of cardinality C filled with numbers between M+1 and N
>
> appended to
>
> The multiset of cardinality C-1 with filled with numbers between
> M+1 and N, modified by adding M to each set.

[snip]

The above allows for at most a single occurrence of M
in any multiset of cardinality C.  [Some programmers
may be more familiar with the term "bag" rather than
multiset, but the idea allows multiple occurrences
of identical items (which a set would not allow).]

regards, chip

Chip Eastham wrote:
 
>
>
> [snip]
>
> The above allows for at most a single occurrence of M
> in any multiset of cardinality C.

I am sure Matthew knows what a multiset is - he was typing to fast:
his final M+1 should have been an M.

Cheers

Bart Demoen

On Mon, 3 Mar 2008, Bart Demoen wrote:
> Chip Eastham wrote:
 

> I am sure Matthew knows what a multiset is - he was typing to fast:
> his final M+1 should have been an M.

Ah yes, I was looking in just briefly, and  "multiset" with
"set of sets", I'd tend to use the term "bag" for "multiset", as Chip
noted, and probably would have seen the problem correctly had this
term been used. OK, the problem becomes slightly more difficult, but the
approach remains the same - think of how what you want can be expressed
logically, almost always with lists this involves seeing how it relates to
the same problem on the tail of the list, thus leading to a recursive
program.

Matthew Huntbach

Matthew Huntbach schrieb:
> [...] the approach remains the same - think of how what you want can be
> expressed logically, almost always with lists this involves seeing how it
> relates to the same problem on the tail of the list, thus leading to a
> recursive program.

Hi Matthew,

your advice sounds very appealing but:

1.  Half of the stuff in my winter-lecture about Prolog was about
non-logical components of Prolog.  To use Prolog in a realistic
way you have to use them, IMHO.

2.  I doubt that you can find Bart's  definition of multisets:

multiset(Size,From,To,MultiSet) :-
findall(X,between(From,To,X),Items), % (*)
length(MultiSet,Size),
multiset(MultiSet,Items).

multiset([],_).
multiset(MultiSet,Items) :-
MultiSet = [El|Els],
Items = [I|Is],
(
El = I,               % I is in the multiset
multiset(Els,Items)
;
multiset(MultiSet,Is) % I is not
).

without an idea how they could built with Prologs backtracking
and unification strategy.  Or to put it the other way around:
I'd really appreciate to hear the logical definition of the
above code.

3.  To your image with the child learning a language:  A child has
several years to pick up the basics of a language.  Yesterday
I had my examen about an introduction into declarative Programming.
We had only a few month for the functional and the logical paradigm.
One of the questions from my Prof. was "How do we have to accommodate
the unification process in Prolog to unify Variables with finite
domains"...

Thus your advice is good but IMHO it fits not in everybody's reality.

Thank you all for your comments!
Regards
Stephan

Stephan Lukits wrote:

>       multiset([],_).
>       multiset(MultiSet,Items) :-
>           MultiSet = [El|Els],
>           Items = [I|Is],
>           (
>             El = I,               % I is in the multiset
>             multiset(Els,Items)
>           ;
>             multiset(MultiSet,Is) % I is not
>           ).
>
>     without an idea how they could built with Prologs backtracking
>     and unification strategy.  Or to put it the other way around:
>     I'd really appreciate to hear the logical definition of the
>     above code.


Ok, but let me take a step back in the reasoning, because one problem
here is that the mathematical notion of a set and a multiset are prone
to be mixed up with their REPRESENTATION.
This problem is often denied by programmers, or at least ignored (I suffer
from it as well).


Here first the "mathematics"

I will abbreviate
"MS is a multiset with elements from the set S"
to      "MS is a multiset from S"


the empty multiset is always a multiset
if we represent the empty multiset by [], than this covers
clause 1
and
let I be any element of S
then MS is a multiset from S, if
MS contains I and MS \ {I} is a multiset from S
and
then MS is a multiset from S, if
MS is a multiset from S \ {I}

Now all one needs to do is to translate the mathematical statement
that does not talk about representation into a statement that uses the
representation.

So let's fix the representation

1) a set is represented by a list where each listelement occurs only
once (it is not important to order this representation for the current
exercise, but you may)

2) a multiset is represented by a list with possible duplicates, but
such that duplicates are adjacent in the list (again, the ordering is
optional)

With this representation we can turn

"let I be any element of S" into  S = [I|_]
"MS contains I and MS \ {I}" into MS [I|RestMS]
"S \ {I}" into                    RestS in S = [I|RestS]

and you are done.

But we don't have to make that choice - we could have instead

"let I be any element of S" into append(_,[I],S)

(that is: the last element of S is picked)
and you should convince yourself easily that this leads to a correct
program as well. [don't forget to turn
"S \ {I}" into   RestS in append(RestS,[I],S)]

because the mathematics said you could pick ANY element.


Now, not all is said about the program: one must prove that the
representation of the multiset is as expected (grouped identical
elements), and if you introduced order at some points, also this must
be taken care off.

Note that we don't need to know that the first argument is a list
skeleton for correctness of the clauses (as Hornclauses).
But if we want to reason about all solutions, or the order of
solutions, we need to take that into account.


It might seem that I have drifted from a logical definition to a
correctness proof, but that's because I want to give some reason why
my logic describes what the program does.


Cheers

Bart Demoen

On Tue, 4 Mar 2008, Stephan Lukits wrote:
> Matthew Huntbach schrieb:
 

> Hi Matthew,
>
> your advice sounds very appealing but:
>
> 1.  Half of the stuff in my winter-lecture about Prolog was about
>    non-logical components of Prolog.  To use Prolog in a realistic
>    way you have to use them, IMHO.

As I've said before, using the non-logical components of Prolog before
you've properly grasped basic recursive and backtracking programming
is, IMHO, a recipe for disaster. Typically, it leads to novices
using the non-logical aspects as a crutch to excuse going back
to old imperative programming habits, when actually there's a
perfectly good pure logic solution.

> 2.  I doubt that you can find Bart's  definition of multisets:
[...]
>    without an idea how they could built with Prologs backtracking
>    and unification strategy.  Or to put it the other way around:
>    I'd really appreciate to hear the logical definition of the
>    above code.

I've now tried it, and with Bart's correction to my original, there's
a perfectly good pure logic programming to the solution. No need to
findall or if-then-else. Once you have the recursive bit mentioned
previously, you just have to add the base cases, which is a bit
tricky here as there's two:

cardmultiset(C,M,N) when C is 1 and
cardmultiset(C,M,N) when M equals N

but this is fairly obvious now, I hope - first case is
[M], [M+1], ... , [N]

second case is [M,M,...,M] with M repeated C times.

Also, these days I tend not to use backtracking, so I gave my
solution in terms of returning a list of all solutions, but
you can easily make it backtrack over all solutions by
having the two recursive cases alternative clauses rather
than returning two lists of solutions which are appended.

> 3.  To your image with the child learning a language:  A child has
>    several years to pick up the basics of a language.  Yesterday
>    I had my examen about an introduction into declarative Programming.
>    We had only a few month for the functional and the logical paradigm.
>    One of the questions from my Prof. was "How do we have to accommodate
>    the unification process in Prolog to unify Variables with finite
>    domains"...
>
> Thus your advice is good but IMHO it fits not in everybody's reality.

It may of course be the case that not all profs teach Prolog as I think
the language ought to be taught. The approach I'm suggesting anyway
is not unique to Prolog. Learning to think recursively in this way is
a useful skill whatever language you happen to use it with, it happens
Prolog is particularly oriented to this style of programming but you
could do it in Java as well. I think it better to have a thorough
grounding in these abstraction first before jumping into the
syntactical details of particular programming languages.

Matthew Huntbch

On Tue, 04 Mar 2008 15:33:58 +0000, Matthew Huntbach wrote:


> I've now tried it, and with Bart's correction to my original, there's
> a perfectly good pure logic programming to the solution. No need to
> findall or if-then-else.

Have you seen my first solution to the original problem ?
Have you understood that the part of my second solution using findall was
just an interface to something pure, using only lists (and not even
arithmetic) ?

> Once you have the recursive bit mentioned
> previously, you just have to add the base cases, which is a bit
> tricky here as there's two:
>
> cardmultiset(C,M,N) when C is 1 and
> cardmultiset(C,M,N) when M equals N
>
> but this is fairly obvious now, I hope - first case is
> [M], [M+1], ... , [N]
>
> second case is [M,M,...,M] with M repeated C times.

Can you please show Prolog code ?

> Also, these days I tend not to use backtracking

Why ?

> solution in terms of returning a list of all solutions, but
> you can easily make it backtrack over all solutions by
> having the two recursive cases alternative clauses rather
> than returning two lists of solutions which are appended.

Prolog code please: that's what comp.lang.prolog is about !

Cheers

Bart Demoen