Current term representation
Ulrich Neumerkel
blam([L|L]) :-
blam(L).
id([], []).
id([L1|R1], [L2|R2]) :-
id(L1,L2),
L1 = L2,
id(R1,R2),
R1 = R2.
blid(N) :-
length(L, N),
blam(L),
id(L,K),
L == K.
Are there systems, that execute a goal blid(N) in space proportional
to N? Say blid(24). So far, I have only encountered systems that
require 2^N. The idea is to perform the factorization dynamically
within unification. Ideally the two =/2 goals are not required, if GC
is able to handle the situation.
LudovicoVan
wrote:
I am puzzled by this problem, but I am having some hard times actually
getting the terms of it. Maybe you can elaborate a little bit on the
problem setting and the intended result? (More significant names for
the predicates might help.)
To clarify where I am lost: I am guessing the 'blam' predicate defines
the Von Neumann ordinals (in reverse), but I don't get the purpose
neither of the 'id' predicate (isn't it just a convoluted list copy?),
nor of the 'blid' predicate (and why that last L==K anyway?).
Moreover, if I use a plain list copy instead of the 'id' predicate
(coded as 'id1' below) I get exactly the same outcome.
1 ?- [user].
|: blam([]).
blam([L| L]) :-
blam(L).
id([], []).
id([L1| R1], [L2| R2]) :-
id(L1, L2),
L1 = L2,
id(R1, R2),
R1 = R2.
id1([], []).
id1([L1| R1], [L2| R2]) :-
L1 = L2,
id1(R1, R2).
blid(N) :-
length(L, N),
blam(L),
id(L, K),
L == K.
|: |: |: |: |: |: |: |: |: |: |: |: |: |: |: |: |: |: |: |:
% user://1 compiled 0.02 sec, 1,336 bytes
true.
2 ?- between(0,4,N),
| length(L,N),
| blam(L),
| format('[~w] ~w~n',[N,L]),
| id(L,K),
| format('K = ~w~n', [K]),
| fail;
| true.
[0] []
K = []
[1] [[]]
K = [[]]
[2] [[[]], []]
K = [[[]], []]
[3] [[[[]], []], [[]], []]
K = [[[[]], []], [[]], []]
[4] [[[[[]], []], [[]], []], [[[]], []], [[]], []]
K = [[[[[]], []], [[]], []], [[[]], []], [[]], []]
true.
3 ?- between(0,4,N),
| length(L,N),
| blam(L),
| format('[~w] ~w~n',[N,L]),
| id1(L,K),
| format('K = ~w~n', [K]),
| fail;
| true.
[0] []
K = []
[1] [[]]
K = [[]]
[2] [[[]], []]
K = [[[]], []]
[3] [[[[]], []], [[]], []]
K = [[[[]], []], [[]], []]
[4] [[[[[]], []], [[]], []], [[[]], []], [[]], []]
K = [[[[[]], []], [[]], []], [[[]], []], [[]], []]
true.
I know I am missing something, as I don't even get where
"factorisation" comes into place. Maybe you can help and clarify?
-LV
bart demoen
> blam([]).
> blam([L|L]) :-
> blam(L).
>
> id([], []).
> id([L1|R1], [L2|R2]) :-
> id(L1,L2),
> L1 = L2,
> id(R1,R2),
> R1 = R2.
>
> blid(N) :-
> length(L, N),
> blam(L),
> id(L,K),
> L == K.
>
>
> Are there systems, that execute a goal blid(N) in space proportional to
> N? Say blid(24).
Paul Tarau might be the only implementor who has put the factorization
during unification in his system (BinProlog) - even more than once, but
if I remember correctly, he was never sure this was something valuable,
and always ended up taking it out.
> So far, I have only encountered systems that require
> 2^N. The idea is to perform the factorization dynamically within
> unification. Ideally the two =/2 goals are not required, if GC is able
> to handle the situation.
I assume that you mean runtime GC - your example would be "covered" by
the GC I "described" in A Different Look at Garbage Collection for the
WAM. ICLP 2002 - it was never implemented.
It would also be interesting to check whether compile time GC can handle
it - I will send your example to some people here in the department.
Cheers
Bart Demoen
Ulrich Neumerkel
>On Mon, 18 May 2009 17:26:08 +0000, Ulrich Neumerkel wrote:
>> Are there systems, that execute a goal blid(N) in space proportional to
>> N? Say blid(24).
>
>Paul Tarau might be the only implementor who has put the factorization
>during unification in his system (BinProlog) - even more than once, but
>if I remember correctly, he was never sure this was something valuable,
>and always ended up taking it out.
The tragic is that there are uses to a better term representation.
Currently, we are locked: Programs, exploiting these properties
are slow or consume too much space. So they are rewritten.
Implementors do not see much gain in existing programs, so they are
not interested in improving their systems.
There is a single paper I am aware of that actually shows some uses.
Richard A. O'Keefe: O(1) reversible tree navigation without cycle.
TPLP 1(5): 617-630 (2001)
Also as: http://arxiv.org/abs/cs.PL/0406014
>I assume that you mean runtime GC - your example would be "covered" by
>the GC I "described" in A Different Look at Garbage Collection for the
>WAM. ICLP 2002 - it was never implemented.
>
>It would also be interesting to check whether compile time GC can handle
>it - I will send your example to some people here in the department.
Static optimizations for this particular case are not interesting,
because the actual cases are not that regular - there is no direct
textual correlation between identical subterms - you cannot add just
some = goals to reduce the problem to factorizing unification.
The example is the minimum I found so far to exemplify the problem,
provided no static transformation is applied. After all, blid/1
could be reduced statically to:
blid(N) :-
length(_, N).
Here are two further cases that are less challenging. Still
?- bleq(1000). and ?- bleqeq(1000) do not succeed everywhere
(rapidly).
bleq(N) :-
length(L, N),
blam(L),
length(K, N),
blam(K),
L = K.
bleqeq(N) :-
length(L, N),
blam(L),
length(K, N),
blam(K),
L == K.
These are all synthetic benchmarks, that help to identify the
problems.
Bart Demoen
>
> Static optimizations for this particular case are not interesting,
Yes they are - if static optimization would not be able to deal
with this particular regular case, one can abandon all hope for more
complex situations.
> Here are two further cases that are less challenging. Still ?-
> bleq(1000). and ?- bleqeq(1000) do not succeed everywhere (rapidly).
They do in SWI, SICStus, hProlog.
?- bleq(1000). doesn't in Yap, BProlog, XSB, ECLiPSe - and even for
much smaller input (23 in Yap for instance)
?- bleqeq(1000). ends with segmentation fault in Yap (but is fast for
smaller values) and does not work for BProlog, XSB, ECLiPSe
Interesting how unification can be screwed up :-)
But what was the point of the example program ? That some implementations
do screw up ?
XSB and Yap have a term representation that is almost identical to
SICStus and hProlog - so at least there is no reason why they need to
screw up.
Cheers
Bart Demoen
fodor
for the systems that didn't work. I cannot figure out why it would
take so much time (it is just unifying very large terms - maybe there
is something I don't see).
The following papers might be helpfull to you (I checked and you can
easily find them on Google):
Unification Factoring for Eficient Execution of Logic Programs
S.Dawson C.R Ramakrishnan I.V Ramakrishnan K. Sagonas S. Skiena T.
Swift D.S. Warren
Principles and practice of unification factoring
Steven Dawson, C.R. Ramakrishnan, Steven Skiena and Terrance Swift
Regarding term representation you can look over the following paper:
Term Indexing, by R Sekar, IV Ramakrishnan, and Andrei Voronkov (it's
available as pdf on Dr. Voronkov's Web page). You can find there
various data-structures (i.e., all kinds of trees and adaptive
automatas), but I doubt that any Prolog system is actually using them
(except one, namely tries, used in XSB and, to my knowledge, in Yap,
for the data structures for tabling).
Paul....@gmail.com
The algorithm Bart refers to is quite simple:
when unifying subterms f(...) and f'(...), if their unification
succeeds
you destructively replace the pointer to f'(...) with the one to f
(...) and
value trail the original pointer to f'.
This means that if later the GC can prove that it is ok to discard the
value trailed
for f', you win. I guess this could happen when it becomes clear that
you can commit
to the change - on CUT or if determinism is detected in some other
way.
I also guess that you are likely to lose for sure if heavy
backtracking forces you
to undo the trailed value repeatedly.
It helps you to win if you have the value trailing cell for a given
subterm pointer
reused (something that BinProlog had since late 1992 or so, and it is
also mentioned
in Jacques Noye's thesis).
Paul Tarau
fodor
prior post are not relevant to your problem. They deal with a
different problem (i.e., portions of arguments can be common to
several clauses, so indexing can be improved by factoring out the
common parts). I think that your problem is quite interesting and so
are the responses that you got to the post.
bart demoen
> The tragic is that there are uses to a better term representation.
Please tell us more about the "better term representation": it seems to
me that some programs would benefit from something "better", but most
programs would pay a price. Also, it seems not about a "term
representation" (any representation is fine - it's about the sharing).
Are you just homesick for hash-consing (or a variant) ?
Cheers
Bart Demoen
Ulrich Neumerkel
>On Tue, 19 May 2009 21:17:27 +0000, Ulrich Neumerkel wrote:
>> The tragic is that there are uses to a better term representation.
>Please tell us more about the "better term representation": it seems to
>me that some programs would benefit from something "better", but most
>programs would pay a price. Also, it seems not about a "term
>representation" (any representation is fine - it's about the sharing).
One better term representation is the sharing of identical but
"unrelated" terms. Hash-consing is not necessary for this. It is
sufficient to minimize terms from time-to-time during GC. The
algorithm is minimization of finite automata. The runtime overheads
are neglectable, as this is would be a policy decision.
In this manner space requirements could be reduced.
BTW: This discussion had already some positive impact on one
implementation. Yap-6.0.0.0-60-ga10bf47 now passes bleq/1! I wish
that blid/1 could follow soon.
bart demoen
> bart demoen <b...@cs.kuleuven.be> writes:
>>On Tue, 19 May 2009 21:17:27 +0000, Ulrich Neumerkel wrote:
>>> The tragic is that there are uses to a better term representation.
>>Please tell us more about the "better term representation": it seems to
>>me that some programs would benefit from something "better", but most
>>programs would pay a price. Also, it seems not about a "term
>>representation" (any representation is fine - it's about the sharing).
>
> One better term representation is the sharing of identical but
> "unrelated" terms. Hash-consing is not necessary for this.
I didn't say that hash-consing is necessary - it would be sufficient.
> It is sufficient to minimize terms from time-to-time during GC.
I was under the impression that the Java experience with finalization
has shown once and for all that relying on GC for maintaining
invariants/properties (besides the obvious) is the wrong gamble.
> The algorithm is minimization of finite automata. The runtime
> overheads are neglectable,
Minimization of (D)FA is (at least) n*log(n) and that does not feel
neglectable in view of the fact that GC is linear in the size of the live
data (at least if you have a decent copying collector). But I must admit
that I do not see the connection to DFA minization: I thought the problem
at hand is more like common subexpression elimination, which is harder
IIRC. Or have you actually implemented/measured something ? (since you
write "overheads are" rather than "overheads would be") And are you sure
you are taking into account variables ?
> as this is would be a policy decision.
That sounds like a politicians argument - please elaborate.
> In this manner space requirements could be reduced.
Yes [see my 2002 paper I referred to earlier], and locality of reference
could be destroyed.
> BTW: This discussion had already some positive impact on one
> implementation. Yap-6.0.0.0-60-ga10bf47 now passes bleq/1!
In my experience, it is enough to e-mail Vitor with a Yap problem, and he
will solve it.
Cheers
Bart Demoen
Ulrich Neumerkel
>On Tue, 26 May 2009 17:26:30 +0000, Ulrich Neumerkel wrote:
>> bart demoen <b...@cs.kuleuven.be> writes:
>>>On Tue, 19 May 2009 21:17:27 +0000, Ulrich Neumerkel wrote:
>>>> The tragic is that there are uses to a better term representation.
>>>Please tell us more about the "better term representation": it seems to
>>>me that some programs would benefit from something "better", but most
>>>programs would pay a price. Also, it seems not about a "term
>>>representation" (any representation is fine - it's about the sharing).
>>
>> One better term representation is the sharing of identical but
>> "unrelated" terms. Hash-consing is not necessary for this.
>
>I didn't say that hash-consing is necessary - it would be sufficient.
Hash-consing is definitely not sufficient. At the point
in time of the creation of a structure - that's where the
hash comes into play - its arguments might still need the
instantations to get shared to other terms.
>> The algorithm is minimization of finite automata. The runtime
>> overheads are neglectable,
>
>Minimization of (D)FA is (at least) n*log(n) and that does not feel
>neglectable in view of the fact that GC is linear in the size of the live
>data (at least if you have a decent copying collector). But I must admit
>that I do not see the connection to DFA minization: I thought the problem
>at hand is more like common subexpression elimination, which is harder
>IIRC. Or have you actually implemented/measured something ? (since you
>write "overheads are" rather than "overheads would be") And are you sure
>you are taking into account variables ?
CSE considers cost and benefit of sharing. You would have a similar
difficult choice if you would consider sharing vs. trailing, or
moving structures to newer generations. That's what you probably
mean by taking into account variables - at least your ICLP 2002 paper
suggests this. That is difficult and I do not see how much
this would save.
Introducing sharings that do not require extra trailing covers
less, but it covers the interesting cases as the techniques
described by Richard O'Keefe. blid/1 (without =/2) is a minimal
example for this.
n log(n) up to n^2 runtime is still preferable to a resource
error. In the best case, space reduction is from n to ld n for
finite terms, and arbitrarily for infinite trees.
>> as this is would be a policy decision.
>
>That sounds like a politicians argument - please elaborate.
Policy in the sense of a policy-mechanism separation. It has nothing
to do with politics.
Running blid/1 smoothly is just one step towards better systems.
Bart Demoen
> There is a single paper I am aware of that actually shows some uses.
>
> Richard A. O'Keefe: O(1) reversible tree navigation without cycle. TPLP
> 1(5): 617-630 (2001)
One older reference is
Findall without findall/3
André Mariën
Bart Demoen
ICLP93 Budapest
It talks about input sharing and solution sharing.
What the O'Keefe paper "needs" is input sharing.
And more interestingly: input sharing turns out to be easy and
to get optimal results one must avoid hash-consing; Phuong-Lan Nguyen and
myself are currently writing up a tech report on how to do it in the WAM.
If you use hash-consing, the O(n^2) space goes away in the particular
query in the O'Keefe paper, but the O(n^2) time remains. Our approach
also makes time linear :-)
I'll keep you posted.
Cheers
Bart Demoen
ps. there is also a 1995 post in comp.lang.prolog from Edmund Grimley-
Evans asking for more sharing in findall/3
bart demoen
> bart demoen <b...@cs.kuleuven.be> writes:
>
> Hash-consing is definitely not sufficient. At the point in time of the
> creation of a structure - that's where the hash comes into play - its
> arguments might still need the instantations to get shared to other
> terms.
That only makes it worse - do you remember when someone asked in this
forum why it takes linear time to find out the length of a list, and why
a list (like a Java vector) does not carry its own length as a constant
time accessible piece of info ? To realise that, unification of a free
variable with something would become non-constant time. Definitely
to be avoided !
Giving the above, and a little more thinking, being on the lurk out to
share the maximal amount of ground terms all the time feels really like
one of the worst ideas ever in (Prolog) implementation.
I have put Prolog between () on purpose in the above: any language
implementation, not just Prolog, could in principle benefit space wise
for some programs of more data structure sharing.
> Introducing sharings that do not require extra trailing covers less, but
> it covers the interesting cases as the techniques described by Richard
> O'Keefe.
What interesting techniques did O'Keefe describe where ?
> Running blid/1 smoothly is just one step towards better systems.
It might be a step towards a system that runs quite a bit worse for
almost all programs except blid/1.
Cheers
Bart Demoen
Joachim Schimpf
I agree. I think an execution model where unification is linear
in the term size (rather than the size of the unknown representation
of the term) is quite reasonable.
-- Joachim
Paul....@gmail.com
wrote:
The overwriting of equal subterms + trailing on successful unification
that I mentioned in a previous posting results in extreme cases in
containing exponential growth while keeping the (amortized) cost of
unification linear. As it also takes care of infinite term
unification, it is definitely worth having as an option. While Bart is
basically right that not messing with things like hash consing does
well on typical programs, Prolog's situation is somewhat atypical - it
is known for instance that in FP implementation graph reduction with
overwriting of a function by its value once it is computed is very
important for performance. With this in mind I consider the issue of
inducing term sharing at runtime still open.
Paul Tarau
Ulrich Neumerkel
>On Tue, 26 May 2009 19:48:06 +0000, Ulrich Neumerkel wrote:
>
>> bart demoen <b...@cs.kuleuven.be> writes:
>>
>> Hash-consing is definitely not sufficient. At the point in time of the
>> creation of a structure - that's where the hash comes into play - its
>> arguments might still need the instantations to get shared to other
>> terms.
>
>That only makes it worse - do you remember when someone asked in this
>forum why it takes linear time to find out the length of a list, and why
>a list (like a Java vector) does not carry its own length as a constant
>time accessible piece of info ? To realise that, unification of a free
>variable with something would become non-constant time. Definitely
>to be avoided !
Absolutely. However, my statement above was a reply to your claim:
>>>I didn't say that hash-consing is necessary - it would be sufficient.
It seems this line was somehow omitted.
I never advocated hash-consing. Introducing sharing during GC and
unification is the interesting thing.
>> Introducing sharings that do not require extra trailing covers less, but
>> it covers the interesting cases as the techniques described by Richard
>> O'Keefe.
>
>What interesting techniques did O'Keefe describe where ?
Richard A. O'Keefe: O(1) reversible tree navigation without cycle.
TPLP 1(5): 617-630 (2001)
Also as: http://arxiv.org/abs/cs.PL/0406014
(first posted in this thread Tue, 19 May 2009 21:17:27 GMT)
bart demoen
> bart demoen <b...@cs.kuleuven.be> writes:
>>What interesting techniques did O'Keefe describe where ?
>
> Richard A. O'Keefe: O(1) reversible tree navigation without cycle. TPLP
> 1(5): 617-630 (2001)
We must have had a misunderstanding - as so often between the two of us:
I thought you meant interesting techniques related to term sharing, and
I had looked in vain for that in the above paper.
Cheers
Bart Demoen
bart demoen
> The overwriting of equal subterms + trailing on successful unification
is something that adds a constant factor to the cost of unification (of
two terms that have never been unified before)
> that I mentioned in a previous posting results in extreme cases in
> containing exponential growth while keeping the (amortized) cost of
> unification linear.
Since your technique does not change the complexity of an individual
unification, the latter part seems evident, right ?
BTW, did you mean by growth space, time or both ? and I am confused by the
word "containing" in the above sentence - meant as "reducing" ?
> As it also takes care of infinite term unification,
> it is definitely worth having as an option. While Bart is basically
> right that not messing with things like hash consing does well on
> typical programs, Prolog's situation is somewhat atypical - it is known
> for instance that in FP implementation graph reduction with overwriting
> of a function by its value once it is computed is very important for
> performance.
Overwriting a function call by its value is itself a constant
time operation and does not change the complexity of the function
evaluation. That's why it is so good to remember the value, and it
does not hurt if you never reuse that value (except possibly space wise).
> With this in mind I consider the issue of inducing term
> sharing at runtime still open.
Absolutely. It would be nice to check on realistic programs how much
sharing could be achieved and investigate what minimal techniques are
sufficient for doing the sharing.
Cheers
Bart Demoen
Ulrich Neumerkel
Checking programs that have been written for current systems
cannot show much sharing. After all, they run on current systems
without extra sharing.
The situation is a little bit comparable to the time, when failure
driven loops were written to avoid memory overflows in systems
lacking GC. Such programs did not show significant gains from GC.
Only programs using forward recursion did.
bart demoen
> bart demoen <b...@cs.kuleuven.be> writes:
>>Absolutely. It would be nice to check on realistic programs how much
>>sharing could be achieved and investigate what minimal techniques are
>>sufficient for doing the sharing.
>
> Checking programs that have been written for current systems cannot show
> much sharing. After all, they run on current systems without extra
> sharing.
That looks like a good argument not to do some checking ... but it isn't.
Current programs could run in significantly less space if sharing were provided,
or they could not - I prefer to be open to the outcome of such an experiment.
And maybe you should try to measure how much harm is done to declarative program
construction by systems not providing all possible sharing, because if no harm is
done currently by not having sharing, and no gain is to be expected in practice by
having sharing, why bother with sharing, except for writing papers :-)
Cheers
Bart Demoen
Ulrich Neumerkel
Measuring harm is even more speculative in nature.
There is evidence for programs that would benefit, like Richard O'Keefe's
program I mentioned in this thread. Also relatively simple programs like
http://www.complang.tuwien.ac.at/ulrich/dipl/D-4#4.4.1
delete_all/3 would profit.
When I wrote this 20 years ago in my diploma thesis, I did not expect that
twenty years later this relatively straight forward improvement would not
be common practice. Instead, we are discussing whether or not a
feasibilty study is worth doing or not.
bart demoen
> There is evidence for programs that would benefit, like Richard O'Keefe's
> program I mentioned in this thread.
So I am happy to announce now that this problem has been solved and
that it didn't need any big machinery like hash-consing or adapting the
gc etc. Have a look at
http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW553.abs.html
> Also relatively simple programs like
>
> http://www.complang.tuwien.ac.at/ulrich/dipl/D-4>4.4.1
[that's the blam program posted earlier]
>
> delete_all/3 would profit.
Nobody denies that "there exist programs that would benefit from X".
Your blam, O'Keefe's findall query, and delete_all/3 are THREE
examples, not convincing me at all of the general usefulness of any
serious implementation changes to current systems - for one thing: if
one uses delete_all, one is quickly prototyping (and don't care about
efficiency) or one has no clue about programming.
And I object to the following reasoning: "... therefore,
implementations should optimize for X [regardless of any negative
impact on other stuff]".
> When I wrote this 20 years ago in my diploma thesis, I did not expect that
> twenty years later this relatively straight forward improvement would not
> be common practice.
Please get to grips with the thesis-reality discrepancy :-)
> Instead, we are discussing whether or not a
> feasibilty study is worth doing or not.
Blame yourself for that: I proposed it, you deny it is worth
doing. And it is BTW not a relatively straight forward improvement to
have optimal sharing all the time. It might not even be an improvement.
If you would care to look at the recent literature on hash-consing,
you might notice that it comes as a design pattern or a library. That
is far removed from a general implementation strategy.
I am all for more sharing, but not if it means [probably lots of]
"distributed fat" (my thanks to Zoltan Mercury for teaching me this
last expression). Stronger arguments than delete_all or blam are
needed. As I said, the O'Keefe findall issue is already solved.
Cheers
Bart Demoen
Ulrich Neumerkel
>On Thu, 25 Jun 2009 13:31:30 +0000, Ulrich Neumerkel wrote:
>
>> There is evidence for programs that would benefit, like Richard O'Keefe's
>> program I mentioned in this thread.
>
>So I am happy to announce now that this problem has been solved and
>that it didn't need any big machinery like hash-consing or adapting the
>gc etc. Have a look at
>
>http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW553.abs.html
How can the results of hProlog be reproduced?
It looks interesting even if it focuses on findall/3.
There were some more measurements in O'Keefe's paper unrelated
to findall/3.
Again, hash-consing is not the alternative to consider.
I noticed that the results for SWI are given only for very small
values. With -G this could be extended:
http://www.swi-prolog.org/pldoc/doc_for?object=section(2,'2.4',swi('/doc/Manual/cmdline.html'))
>> Also relatively simple programs like
>>
>> http://www.complang.tuwien.ac.at/ulrich/dipl/D-4#4.4.1
...
bart demoen
> How can the results of hProlog be reproduced?
By getting a copy of hProlog and running the benchmarks ...
> It looks interesting even if it focuses on findall/3.
The question in the O'Keefe paper was very specific for findall/3.
The delete_all/3 problem you mentioned, can also be solved much better
than by throwing in a lot of low-level implementation work that affects
many programs adversely. delete_all/3 belongs in the library, so replace its
ordinary definition by
mda(L,Y,O) :- mda(L,Y,L,A,A,O).
mda([],_,L,_,_,L).
mda([X|R],Y,In,A,B,Out) :-
(X == Y ->
Out = A,
mda(R,Y,R,C,C,B)
;
B = [X|C],
mda(R,Y,In,A,C,Out)
).
mda stands for my-delete-all. It might look complicated, but its amortized overhead
is very low, so low that I bet a box of belgian chocolates that no general
technique for getting the same sharing can beat it before ICLP2010.
> There were some
> more measurements in O'Keefe's paper unrelated to findall/3.
Yes, but they were unrelated to the sharing problem, so I don't understand why
you mention those other measurements.
> Again, hash-consing is not the alternative to consider.
What is the alternative to consider ?
I don't think hash-consing is the solution either. To me, the solution is
providing sharing when the user wants it, through some API, and when she does
not ask for it, at best through program transformation.
Cheers
Bart Demoen
Ulrich Neumerkel
>On Sat, 27 Jun 2009 10:20:56 +0000, Ulrich Neumerkel wrote:
>
>
>> How can the results of hProlog be reproduced?
>
>By getting a copy of hProlog and running the benchmarks ...
How?
>The delete_all/3 problem you mentioned, can also be solved much better
>than by throwing in a lot of low-level implementation work that affects
>many programs adversely. delete_all/3 belongs in the library, so replace its
>ordinary definition by
>
>mda(L,Y,O) :- mda(L,Y,L,A,A,O).
>
>mda([],_,L,_,_,L).
>mda([X|R],Y,In,A,B,Out) :-
> (X == Y ->
> Out = A,
> mda(R,Y,R,C,C,B)
> ;
> B = [X|C],
> mda(R,Y,In,A,C,Out)
> ).
This rewrite is not necessarily better apart from making
a library extremely complex and brittle. The volatility
of terms is reduced.
p(L) :- mda(L,not_in_list,_).
L is the last reference to the list. The list is kept alife
for the entire predicate. The naive version requires space
proportional to the remaining list.
>> Again, hash-consing is not the alternative to consider.
>
>What is the alternative to consider ?
To factorize after GC from time to time. Optimizations
as you have suggested them for findall are then still interesting,
but only for reasons of speed improvements.
bart demoen
> bart demoen <b...@cs.kuleuven.be> writes:
> >By getting a copy of hProlog and running the benchmarks ...
>
> How?
Download http://www.cs.kuleuven.be/~bmd/HPROLOG.tar.gz and find the
README in the HPROLOG directory. I hope this works for you (intel
32-bit kubuntu is the only possibility).
[I send this to Ulrich earlier today, and it works for him - I will
not leave that version of hProlog for a long time there]
> >mda(L,Y,O) :- mda(L,Y,L,A,A,O).
> >
> >mda([],_,L,_,_,L).
> >mda([X|R],Y,In,A,B,Out) :-
> > (X == Y ->
> > Out = A,
> > mda(R,Y,R,C,C,B)
> > ;
> > B = [X|C],
> > mda(R,Y,In,A,C,Out)
> > ).
>
> This rewrite is not necessarily better apart from making
> a library extremely complex and brittle.
That a library is complex is not a problem.
Whether it is brittle depends on what you mean by that.
> brittle adj. Said of software that is functional but easily broken
> by changes in operating environment or configuration, or by any
> minor tweak to the software itself.
With this definition of brittle, it seems not more brittle to me than
your definition of delete_all - one is not supposed to perform tweaks
to library code.
> The volatility of terms is reduced.
>
> p(L) :- mda(L,not_in_list,_).
>
> L is the last reference to the list. The list is kept alife
> for the entire predicate.
True - and good point - but didn't you write yourself in
http://www.complang.tuwien.ac.at/ulrich/dipl/D-4#4.4.1 :
Falls beide Listen in der nachfolgenden Berechnung noch
benötigt werden, könnten sie wieder zu einem Vorkommnis vereint
werden.
mda/3 seems perfect for that situation, i.e. when also the input list
is still needed. Maybe you should make up your mind on what you want.
> The naive version requires space proportional to the remaining list.
Only when GC kicks in at the right moments, and that will cost (time)
with the current GC technology.
> >What is the alternative to consider ?
>
> To factorize after GC from time to time.
If GC kicks in at the wrong moment, sharing is suboptimal during most
of the execution. Most moments are wrong.
I have other versions of delete_all, with other properties: none gives
all the guarantees at the same time. Maybe all of them should be in
the library, together with their properties, and the compiler should choose
the appropriate one, based on some analysis of the code.
That seems to me the only way to get the best of all worlds most of the
time, without paying a large penalty almost always.
But in the end, sigh, it is a challenge to try to implement factorization
during GC, and quite possibly, we will give in to it :-) Anybody cares to
work with us ? [we are picky !]
Cheers
Bart Demoen
Ulrich Neumerkel
>Download http://www.cs.kuleuven.be/~bmd/HPROLOG.tar.gz
I can only cheer your decision!
>On Mon, 29 Jun 2009 10:51:21 +0000, Ulrich Neumerkel wrote:
>> L is the last reference to the list. The list is kept alife
>> for the entire predicate.
>
>True - and good point - but didn't you write yourself in
>http://www.complang.tuwien.ac.at/ulrich/dipl/D-4#4.4.1 :
>
> Falls beide Listen in der nachfolgenden Berechnung noch
> ben"otigt werden, k"onnten sie wieder zu einem Vorkommnis vereint
> werden.
>
>mda/3 seems perfect for that situation, i.e. when also the input list
>is still needed. Maybe you should make up your mind on what you want.
Reading the cited paragraph up to its end, it should be evident what I
meant then but also today:
> ... dadurch h"atte aber die Klarheit des Programms sowie auch seine
> Ausf"uhrungsgeschwindigkeit gelitten.
>> The naive version requires space proportional to the remaining list.
>
>Only when GC kicks in at the right moments, and that will cost (time)
>with the current GC technology.
We have here two notions of space requirement. Yours is the space
required by an actual process with a concrete GC strategy.
The space requirements I refer to, is the ideal minimal one which
could be observed, by calling GC after each elementary operation.
The advantage of considering that minimum is that a concrete run
will never use less space than it, ceteris paribus. Also it is now
easy to compare a concrete strategy with that minimum. However, I do
not see a good and comparable approximation for the maximum - or for
your notion of space requirement.
>> >What is the alternative to consider ?
>>
>> To factorize after GC from time to time.
>
>If GC kicks in at the wrong moment, sharing is suboptimal during most
>of the execution. Most moments are wrong.
>
>I have other versions of delete_all, with other properties: none gives
>all the guarantees at the same time. Maybe all of them should be in
>the library, together with their properties, and the compiler should choose
>the appropriate one, based on some analysis of the code.
Isn't that a very complex and hard to maintain approach? Who should
test all these various versions? To me it seems already hard enough
to keep and test one version.
>That seems to me the only way to get the best of all worlds most of the
>time, without paying a large penalty almost always.
I considered factorization based on the idea to view terms as a
DFA. Which means, translated into Prolog, that
carpet(C) :- carpet(s(C)).
?- carpet(C).
will run out of space, while
?- C = s(C), carpet(C).
will not. carpet/1 seems quite an appropriate name for it.
To roll one together, you need a start.
But, if one goes only for trees? ... Maybe
there is a way to prevent the current worst case too...
One alternative considered later was in the context of BinProlog.
(I cannot find the source to it) Somewhat to walk through -
similar to e.g. acyclic_term, but to hash the tree when going
back. Maybe Paul has a better memory than I. Not sure that
this extends to general GC, though.
bart demoen
> ... dadurch h"atte aber die Klarheit des Programms sowie auch seine
> Ausf"uhrungsgeschwindigkeit gelitten.
Die Klarheit des Programms is of no consequence when the delete_all
alternatives are in the library: how things are written in the library
is of no concern to the application programmer; (s)he is (or should
be) only concerned with the properties and guarantees that library
predicates have/give. [this might be a very old-fashioned attitude of
me; these days, I see around me mostly people who care only about
reusing software they don't know anything about, except a badly
specified input-output behaviour].
And the Ausf"uhrungsgeschwindigkeit of most programs will suffer if GC
tries to do factorization of terms.
> We have here two notions of space requirement. Yours is the space
> required by an actual process with a concrete GC strategy.
>
> The space requirements I refer to, is the ideal minimal one which
> could be observed, by calling GC after each elementary operation.
While I understand that we might have different notions of space
requirement [but see later], you seem to present yours as an absolute
and pure one. I think it is not: GC (even after each elementary
operation) makes a safe approximation of what will be needed in the
future and that is undecidable. Which means that by putting in more
effort in deciding on a smaller set of useful data, the ideal minimal
footprint of a particular program can change drastically.
The minimum surely depends on a concrete GC strategy, and always on
the concrete GC usefulness logic (thanks again to MALI people in
Rennes to make that notion explicit).
> However, I do not see a good and comparable approximation for the
> maximum - or for your notion of space requirement.
[this is the see later]
You seem to understand my notion better than I do myself. I though
that the maximum space requirement is pretty clear in a given context:
just run the program without GC and observe. I admit that it depends
on the observed system, but so is your minimal notion relying on GC.
But maybe you meant something else ?
It would clearly be a good thing if we understand better what minimal
space requirement really is. I have been interested in it at least
since 'A Different Look at Garbage Collection for the WAM" in 2002.
But "calling GC after each elementary operation" is such an
underspecification of it.
> Isn't that a very complex and hard to maintain approach? Who should
> test all these various versions? To me it seems already hard enough
> to keep and test one version.
While I acknowledge that you have done some remarkable things in
testing software, I am compelled to say this:
- [a no brainer really:] keeping a version is not hard at all
- testing three versions of the same API should cost about three times
as much as to test just one: run the same tests on all three
versions - at least if you only test input-output behaviour - if you
want to go for coco (or any other notion that gives you confidence)
instead of i-o, use tools
- and finally: don't test, but prove
I know we are not yet living in the world where we can prove all
correct programs correct, but neither do we have the resources to run
GC after every elementary operation.
> carpet(C) :- carpet(s(C)).
>
> ?- carpet(C).
>
> will run out of space, while
>
> ?- C = s(C), carpet(C).
>
> will not.
Sorry to put you back on the ground with your two feet (as we say in
flemmish), but ...
SWI ?- C = s(C), carpet(C).
ERROR: Out of global stack
hProlog ?- C = s(C), carpet(C).
Exiting because ... heap expansion malloc-ed in wrong part of memory :-)
SICStus: ?- C = s(C), carpet(C).
! Resource error: insufficient memory
B-Prolog: ?- C = s(C), carpet(C).
[..]
No enough memory with top address bits set!
Yap: ?- C = s(C), carpet(C).
[this takes for ages because Yap can have larger than 2gig heap ...]
ERROR!!
OUT OF STACK SPACE ERROR- Database crashed against stacks
Maybe you meant carpet(s(C)) :- carpet(C). ?
Anyway, you are now straying to (infinite) rational trees, and perhaps
some things are different in that bush.
> One alternative considered later was in the context of BinProlog.
> (I cannot find the source to it) Somewhat to walk through -
> similar to e.g. acyclic_term, but to hash the tree when going
> back. Maybe Paul has a better memory than I.
Please, Paul, comment !
Cheers
Bart Demoen
Ulrich Neumerkel
>On Tue, 30 Jun 2009 19:34:25 +0000, Ulrich Neumerkel wrote:
>I know we are not yet living in the world where we can prove all
>correct programs correct, but neither do we have the resources to run
>GC after every elementary operation.
That is a measure to compare a concrete strategy against. Not
something to run.
>> carpet(C) :- carpet(s(C)).
>>
>> ?- carpet(C).
>>
>> will run out of space, while
>>
>> ?- C = s(C), carpet(C).
>>
>> will not.
>Sorry to put you back on the ground with your two feet (as we say in
>flemmish), but ...
There was a sentence prior to that:
::I considered factorization based on the idea to view terms as a
::DFA. Which means, translated into Prolog, that ...
So what I said above refers to that minimization, not to current
systems.
>Maybe you meant carpet(s(C)) :- carpet(C). ?
No.
>Anyway, you are now straying to (infinite) rational trees, and perhaps
>some things are different in that bush.
As I understand it, for infinite trees, there is no way to
avoid the worst case. But the other approach which would effectively
ignore the cycles (and thus would run out of space as current
systems for above query) runs at least inherently linear.
bart demoen
> I never advocated hash-consing. Introducing sharing during GC and
> unification is the interesting thing.
I know it has been a long time, but let me get back to this,
especially as we have some (still developing) results on the topic.
Introducing sharing during GC was done in
@techreport{ appelhashconsinggc,
AUTHOR = "Andrew~W.~Appel and Mercelo~J.~R.~Goncalves",
TITLE = "{Hash-consing Garbage Collection}",
INSTITUTION = "Princeton University",
Number = "CS-TR-412-93",
PAGES = "1-18",
month = feb,
YEAR = 1993 }
albeit by hash-consing.
The results reported there are not encouraging - at best some 15%
space and time improvement, and most often not more than 1%. But since
not all languages and implementations are created equal, we
investigated this a bit further, and we now have a working
gc+representation sharing system in hProlog.
We are now looking for benchmark programs - some of the ones in the
above mentioned paper are "broken" from the point of view of
representation sharing.
If you have programs, please send them - we will acknowledge your help
in a future publication (if ever accepted :-) We can not deal with
programs using the dynamic database, and we prefer programs not using
setarg, flag, setval ... In particular, Prolog programs doing
Knuth-Bendix, Lex, Simple, VLIW or Yacc from the above mentioned Appel
paper (together with test data/queries) are much appreciated.
Thanks
Bart Demoen
ps. as a side-effect of this line of investigation, we looked at some
SWI-Prolog (or Yap) programs in The Computer Language Benchmarks Game;
there is so much room for improvement there !
Bart Demoen
> I know it has been a long time, but let me get back to this, especially
> as we have some (still developing) results on the topic.
Finally written up in:
Bart Demoen and Phuong-Lan Nguyen
"Representation sharing for Prolog"
http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW571.abs.html
Cheers
Bart Demoen
Ulrich Neumerkel
Some comments:
i You suggest to use an extra declaration for terms of a certain
functor. This would inevitably collide with the approaches currently
discussed within WG 17. Wouldn't it be sufficient to have one functor
'$modifiable'/2 and one functor '$nonbacktrackable'/2? In this manner
the declaration mechanism can be avoided altogether. The second
argument should be a free variable. This would better fit to the
current drafts for global variables w.r.t ground/1.
It would be best to go through the current Japanese draft for WG17 in
the light of possible conflicts. We need progress here! In the ICLP
2008 proceedings I read: "Despite many (also recent) efforts, the ISO
commitee seems unable to make substantial progress" - interesting
observation about WG17. We need more than mere observations.
Please refer to for the Japanese global variables draft
http://www.sju.edu/~jhodgson/wg17/Drafts/
ii Terminology: in the context of Prolog IV the notion factorize has
been used - also as a toplevel print option. Factoring is used in
resolution for quite similar purpose. Representation sharing sounds
very similar to structure sharing. And if we are at it, why not see
GC as an abbreviation for Gleaning Cells?
iii As far as I understand the paper you consider finite terms only.
Definitely this is the most interesting part. Just rereading the thread:
>> carpet(C) :- carpet(s(C)).
>
>> ?- carpet(C).
>
>> will run out of space, while
>
>> ?- C = s(C), carpet(C).
>
>> will not.
>
>Sorry to put you back on the ground with your two feet (as we say in
>flemmish), but ... [all systems produce resource errors]
>Maybe you meant carpet(s(C)) :- carpet(C). ?
carpet(C) :-
carpet(s(C)).
Will produce a term that gets bigger and bigger. Except if the
initial goal is a rational tree that can "roll" the entire term
(carpet) together. If you do not like a predicate without answers
consider:
carpet(C,C).
carpet(C0,C) :-
carpet(s(C0),C).
?- X0 = s(X0), carpet(X0,X).
should run in constant space.
iv Keeping your approach separated from GC seems to be an excellent
idea - this helps to encourage other systems to adopt it. Hopefully
you will have the same luck as your efforts to popularize attributed
variables. Where would SWI or YAP be today without them?
v Diplomarbeit corresponds to Master Thesis, not Ph.D.
vi Concerning the name blam - I read this first in the LISP 1.5
primer. Contrary to frequent citations in the LISP literature it does
not occur in the LISP 1.5 Programmer's manual.
bart demoen
[...]
Thanks for your comments.
> i You suggest to use an extra declaration for terms of a certain
> functor. This would inevitably collide with the approaches currently
> discussed within WG 17. Wouldn't it be sufficient to have one functor
> '$modifiable'/2 and one functor '$nonbacktrackable'/2?
It is not sufficient: given that some popular systems (SWI comes to
mind) allow setarg/3 on any term (and also nd_setarg/3), we would
argue that de facto, it is not sufficient.
Given that we also advocate type declarations and a non-predicate based
module system, we think that in a research paper, we should not give in
to your wish :-)
> The second argument should be a free variable.
The second argument of what ? And why ?
> It would be best to go through the current Japanese draft for WG17 in
> the light of possible conflicts. [...]
Is this still related to representation sharing, or were you
free-wheeling ?
> ii Terminology: in the context of Prolog IV the notion factorize has
> been used - also as a toplevel print option. Factoring is used in
> resolution for quite similar purpose. Representation sharing sounds
> very similar to structure sharing.
Please provide a more concrete reference than "in the context of
Prolog IV". We are willing to adhere to common practice for naming
this "thing", but literature does not suggest that
factorization/factoring is common or that "sharing" is
inferior. Different sources have used different names for virtually
the same thing ("folding" in Carlsson-Sahlin, "[input] sharing" in
Marien-Demoen ICLP93, "hash-consing" in the functional context {even
though that only side-ways refers to the concept of sharing}, the word
"sharing" in section 5 of the O'Keefe pearl) - none of the mentioned
literature was prevented to be published because it didn't use the
word "factor" or any of its derivatives. Even though there might be
confusion with the term structure sharing, we maintain that
representation sharing is the best name.
> And if we are at it, why not see GC as an abbreviation for Gleaning
> Cells?
Is this a joke ? I do not understand it. Are you opposing to the fact
that in the tech report, we use GC as an abbreviation for garbage
collection ? That would be easy to remedy and we wouldn't use GC in a
submission for a journal. In a tech report, which has a less formal
nature, we didn't think it would hurt.
> iii As far as I understand the paper you consider finite terms only.
No - we IMPLEMENTED only finite terms. We considered cyclic terms, but
had nothing to contribute as off now: the Goncalves-Appel paper tells
us how to deal with cyclic terms, and up to now, we did not take the
effort to deal with them in the implementation.
> carpet(C) :-
> carpet(s(C)).
>
> Will produce a term that gets bigger and bigger. Except if the
> initial goal is a rational tree that can "roll" the entire term
> (carpet) together. If you do not like a predicate without answers
> consider:
>
> carpet(C,C).
> carpet(C0,C) :-
> carpet(s(C0),C).
>
> ?- X0 = s(X0), carpet(X0,X).
>
> should run in constant space.
Let me first remind you: you claimed that
>> carpet(C) :- carpet(s(C)).
>
>> ?- carpet(C).
>
>> will run out of space, while
>
>> ?- C = s(C), carpet(C).
>
>> will not.
The fact is that every implementation I tested, runs out of space also
for the second query. It has nothing to do with whether I like
predicates without answers. Just try that query in SWI, SICStus, Yap
and you will see (also in hProlog with representation sharing).
Now you write:
> ?- X0 = s(X0), carpet(X0,X).
>
> should run in constant space.
The "should" is your wish list. I am not convinced that it "should":
the decision should be based on cost/benefit. If it can only run in
constant space at the cost of a lot of "distributed fat" in the
implementation, I think it shouldn't. The other part of my answer is:
if representation sharing is implemented also for cyclic terms, it
might [I have not looked enough at what Goncalves-Appel did for cyclic
terms, but my impression is that the term produced by X = f(X) and Y =
f(f(Y)) would not share their representation]. I would not make it a
high priority.
> iv Keeping your approach separated from GC seems to be an excellent
> idea - this helps to encourage other systems to adopt it.
That was the aim - as usual.
> v Diplomarbeit corresponds to Master Thesis, not Ph.D.
I knew that, but had no Master Thesis thingie in my bibs.bib yet -
it will get corrected. Thanks.
Cheers
Bart Demoen
Ulrich Neumerkel
>On Wed, 25 Nov 2009 13:12:20 +0000, Ulrich Neumerkel wrote:
>
>[...]
>
>Thanks for your comments.
>
>> i You suggest to use an extra declaration for terms of a certain
>> functor. This would inevitably collide with the approaches currently
>> discussed within WG 17. Wouldn't it be sufficient to have one functor
>> '$modifiable'/2 and one functor '$nonbacktrackable'/2?
>
>It is not sufficient: given that some popular systems (SWI comes to
>mind) allow setarg/3 on any term (and also nd_setarg/3), we would
>argue that de facto, it is not sufficient.
I had the impression that we agreed to civilize usage of setarg/3.
>Given that we also advocate type declarations and a non-predicate based
>module system, we think that in a research paper, we should not give in
>to your wish :-)
It would help convergence. We do not have that many personal resources.
>> The second argument should be a free variable.
>
>The second argument of what ? And why ?
This convention alone, could make setarg/3 safer to use by
preventing to merge any otherwise identical structures. setarg/3 could
insist that the last argument is a free variable. That would
be a very low cost change.
The second reason is the current Japanese draft. Please do not
ignore it. http://www.sju.edu/~jhodgson/wg17/Drafts/
>> It would be best to go through the current Japanese draft for WG17 in
>> the light of possible conflicts. [...]
>
>Is this still related to representation sharing...
This is related. At least there is the question of groundness.
I.e. shall such a "variable" be ground or not.
>> ii Terminology: in the context of Prolog IV the notion factorize has
>> been used - also as a toplevel print option. Factoring is used in
>> resolution for quite similar purpose. Representation sharing sounds
>> very similar to structure sharing.
>
>Please provide a more concrete reference than "in the context of
>Prolog IV". We are willing to adhere to common practice for naming
>this "thing", but literature does not suggest that
>factorization/factoring is common or that "sharing" is
>inferior. Different sources have used different names for virtually
http://pageperso.lif.univ-mrs.fr/~alain.colmerauer/DocPrologiv/pdfbienarrange/1-TutorielSurvol.pdf
Le Manuel de Prolog IV
1.3 L'environnement de programmation
1.3.5 Factorisation des sorties
>> ?- X0 = s(X0), carpet(X0,X).
>>
>> should run in constant space.
>
>The "should" is your wish list.
That's what you get if you take minimization of determinate
finite automata. Which somewhat started the discussion.
bart demoen
> I had the impression that we agreed to civilize usage of setarg/3.
From what did you have that impression - something I said ?
I might have forgotten - please remind me.
> >> The second argument should be a free variable.
> >
> >The second argument of what ? And why ?
>
> This convention alone, could make setarg/3 safer to use by
> preventing to merge any otherwise identical structures. setarg/3 could
> insist that the last argument is a free variable. That would
> be a very low cost change.
Sorry - second argument you said first, now you say last argument of
setarg/3 - that's the third argument - I am very willing to give it a
shot to understand you, but can you please be more precise and a bit
more explicit ?
And explain please why this would help preventing otherwise identical
structures: I do not understand this.
Just in case you think I am saying this maliciously: I am
not - I really do not understand you.
> The second reason is the current Japanese draft. Please do not
> ignore it. http://www.sju.edu/~jhodgson/wg17/Drafts/
>
> >> It would be best to go through the current Japanese draft for WG17 in
> >> the light of possible conflicts. [...]
> >
> >Is this still related to representation sharing...
>
> This is related. At least there is the question of groundness.
> I.e. shall such a "variable" be ground or not.
In what sense ? I see no relation whatsoever between our paper on
Representation Sharing for Prolog and the Japanese draft for WG17.
Please be more specific.
> http://pageperso.lif.univ-mrs.fr/~alain.colmerauer/DocPrologiv/pdfbienarrange\
/1-TutorielSurvol.pdf
>
> Le Manuel de Prolog IV
> 1.3 L'environnement de programmation
> 1.3.5 Factorisation des sorties
That manual contains the substring "factor" in 4 places - once in
an english-looking Prolog atom, 3 times in a french word of which once
in quotes ...
With all respect for Prolog IV and its fathers ... before we adopt
that name for the concept, can you show us at least one English
(american or british) reference where "factorization" or "factoring"
is used with the same meaning ? I still maintain that "representation
sharing" is a good way to refer to what our paper is about, and up to
now the best way. I am willing to give in to good arguments by native
english people though.
Cheers
Bart Demoen
Jan Wielemaker
> On Wed, 25 Nov 2009 21:35:32 +0000, Ulrich Neumerkel wrote:
>> This convention alone, could make setarg/3 safer to use by
>> preventing to merge any otherwise identical structures. setarg/3 could
>> insist that the last argument is a free variable. That would
>> be a very low cost change.
>
> Sorry - second argument you said first, now you say last argument of
> setarg/3 - that's the third argument - I am very willing to give it a
> shot to understand you, but can you please be more precise and a bit
> more explicit ?
> And explain please why this would help preventing otherwise identical
> structures: I do not understand this.
> Just in case you think I am saying this maliciously: I am
> not - I really do not understand you.
You are looking at the wrong place. Ulrich talks about the last argument *of
the second argument of setarg/3*. I guess you know that trick: instead of
using a term a(a,b,c), use a term a(a,b,c,_) and one of the problems with
setarg suddenly disappears: the risk of unwanted sharing (currently due to
SWI-Prolog's copy_term/3 that does not copy ground (sub-)terms.
Cheers -- Jan
bart demoen
> You are looking at the wrong place. Ulrich talks about the last
> argument *of the second argument of setarg/3*. I guess you know that
> trick: instead of using a term a(a,b,c), use a term a(a,b,c,_) and one
> of the problems with setarg suddenly disappears
I didn't know that trick - is it fool proof ? What if in a(a,b,c,_X) and
a(a,b,c,_Y) the _X and _Y get unified; then sharing can happen and a setarg/3
on one of them affects the other. So it solves one problem but leaves some
others.
Cheers
Bart Demoen
Ulrich Neumerkel
Let me add one more comment on your paper. The Introduction states:
- in 1989, the Diplomarbeit of Ulrich Neumerkel [13] mentions how by applying
DFA-minimization to Prolog terms, certain program can run in linear space
(instead of quadratic).
^^^^^^^^^ Should read exponential
http://www.complang.tuwien.ac.at/ulrich/dipl/D-4.html.gz#4.4.1 mentions
BLAM-lists and notes that "Through such a list it is possible with
N elements (cons-cells) to represent 2^N-1 elements"
Quadratic is the runtime to attempt to minimize a term like s^N.
I agree with your scepticism about such runtimes, but at that
time I was more interested to find a solution including rational
trees. That finite terms permit much better treatment I understood
only much later - actually in the context of BinProlog.
bart demoen <b...@cs.kuleuven.be> writes:
>On Wed, 25 Nov 2009 21:35:32 +0000, Ulrich Neumerkel wrote:
>
>> I had the impression that we agreed to civilize usage of setarg/3.
>
>From what did you have that impression - something I said ?
>I might have forgotten - please remind me.
https://mailbox.iai.uni-bonn.de/mailman/public/swi-prolog/2009/002336.html
Quote:
UWN: or at least to civilize them
BD: Indeed, that's the approach.
>> >> The second argument should be a free variable.
>> >
>> >The second argument of what ? And why ?
>>
>> This convention alone, could make setarg/3 safer to use by
>> preventing to merge any otherwise identical structures. setarg/3 could
>> insist that the last argument is a free variable. That would
>> be a very low cost change.
>
>Sorry - second argument you said first, now you say last argument of
>setarg/3 - that's the third argument - I am very willing to give it a
>shot to understand you, but can you please be more precise and a bit
>more explicit ?
>And explain please why this would help preventing otherwise identical
>structures: I do not understand this.
Let me say it just in Prolog, ok?
setarg(Arg, Term, Value) :-
functor(Term, F, A),
arg(A, Term, LastArg),
must_be(var, LastArg), % SWI library(error)
old_setarg(Arg, Term, Value).
In this manner setarg/3 will be restricted to structures whose last
argument is a variable. In this manner those structures would not
accidentally be merged by the pass that increases sharing.
The precise error to issue by must_be/2 is BTW still subject
to discussion and you are invited to comment on
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/error_k
Quite a lot of people were already so kind to comment - it is
quite reassuing to know that some people still care about Prolog, why
not you too? I try to get agreement *prior* to a meeting. This
saves time and effort!
>> The second reason is the current Japanese draft. Please do not
>> ignore it. http://www.sju.edu/~jhodgson/wg17/Drafts/
>>
>> >> It would be best to go through the current Japanese draft for WG17 in
>> >> the light of possible conflicts. [...]
>> >
>> >Is this still related to representation sharing...
>>
>> This is related. At least there is the question of groundness.
>> I.e. shall such a "variable" be ground or not.
>
>In what sense ? I see no relation whatsoever between our paper on
>Representation Sharing for Prolog and the Japanese draft for WG17.
Look at 2.1.3
?- new_mutable(M,1), \+ground(M).
shall succeed. I.e. M is not ground.
>> http://pageperso.lif.univ-mrs.fr/~alain.colmerauer/DocPrologiv/pdfbienarrange/1-TutorielSurvol.pdf
>>
>> Le Manuel de Prolog IV
>> 1.3 L'environnement de programmation
>> 1.3.5 Factorisation des sorties
^^^^^^^^^^^^^ this here!
>
>That manual contains the substring "factor" in 4 places - once in
>an english-looking Prolog atom, 3 times in a french word of which once
>in quotes ...
It is this section 1.3.5 above which shows this option for
printing terms such that common subterms are printed only
once. No need to make a global search in the manual.
>With all respect for Prolog IV and its fathers ... before we adopt
>that name for the concept, can you show us at least one English
>(american or british) reference where "factorization" or "factoring"
>is used with the same meaning ? I still maintain that "representation
>sharing" is a good way to refer to what our paper is about, and up to
>now the best way. I am willing to give in to good arguments by native
>english people though.
You do know that there are no references "with the same meaning"
since - to my understanding and according to your report - there is
simply no such work. So we have to look for related areas.
o Factoring of Common Subterms - a static optimization technique
for XSB see 3.10.3 of its manual. This essentially is the static
counterpart to increasing sharing dynamically. Though I doubt
they go that far.
o Unification factoring - actually some indexing transformation
for XSB as well. Seems to be quite popular with XSB.
o In resolution theorem proving, there is a step called factoring.
It is factoring literals not terms.
http://scholar.google.com/scholar?q=resolution+factoring
o Prime factorization. Quite similar:
X = p(s^N(X)) Notation: s^1(X) = s(X), s^3(X) = s(s(s(X)))
X is the minimal term for all multiples of that cycle.
E.g. for X1 = p(s^N(p(s^N(X1)))) &ct
Also, if you would like to minimize a cyclic list of the form
?- length(Xs,CycleLength), phrase(Xs, Cyclic, Cyclic).
it is helpful to consider the factors of CycleLength. The
minimal cycle can only be a factor - not necessarily a prime
factor.
o Functional people go by the notion "hash-consing", but I think
we agree that this is not the most fortunate notion. In particular
since there is no hashing happening during consing. In fact there
is no need for any hashes at all, simple sorting does it as well.
o Representation sharing is less specifc. It would be also
a good name for what mergemem does.
http://www.complang.tuwien.ac.at/ulrich/mergemem/
Convinced?
Ulrich Neumerkel
You do know that there can never be a completely fool proof approach
here. The programmer who uses this must know what he does when we unifies two
such terms. But the point is this: At least he is only responsible for
his very own code. Without this trick it might happen that things
get shared that are entirely independent of each other.
bart demoen
> bart demoen <b...@cs.kuleuven.be> writes:
>>On Thu, 26 Nov 2009 21:01:48 +0000, Jan Wielemaker wrote:
>>
>>> You are looking at the wrong place. Ulrich talks about the last
>>> argument *of the second argument of setarg/3*. I guess you know that
>>> trick: instead of using a term a(a,b,c), use a term a(a,b,c,_) and one
>>> of the problems with setarg suddenly disappears
>>
>>I didn't know that trick - is it fool proof ? What if in a(a,b,c,_X) and
>>a(a,b,c,_Y) the _X and _Y get unified; then sharing can happen and a
>>setarg/3 on one of them affects the other. So it solves one problem but
>>leaves some others.
>
> You do know that there can never be a completely fool proof approach
> here.
Yes there is, nl the one proposed in our paper: a declaration. It is foolproof
in the sense that if it is declared, no sharing will occur, and you can't program
"around" the declaration. Sure, you can forget the declaration and decide to live
dangerously, but it is not the same thing as this free variable requirement you
propose: that is just a hack or workaround at best; nothing principled is involved.
Cheers
Bart Demoen
bart demoen
> it is quite
> reassuing to know that some people still care about Prolog, why not you
> too?
I resent very much your suggestion that I do not care about Prolog.
Ulrich Neumerkel
There is no reason for your resenting. Please read my full statement:
The precise error to issue by must_be/2 is BTW still subject
to discussion and you are invited to comment on
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/error_k
Quite a lot of people were already so kind to comment - it is
quite reassuing to know that some people still care about Prolog, why
bart demoen
You are indeed repeating you insinuation that I do not care about Prolog.
Which I resent once more.
No cheers to you anymore
Bart Demoen
Ulrich Neumerkel
The "proposal" of mine you mention was never meant as a language
construct. WG17 works on defining clean constructs for this.
My proposal was meant as a minimial extension to a system supporting
setarg/3 - preparing it's way to a safe system only using
comparatively clean constructs.
In the long term, one or two such destructible terms might be
sufficient to support WG17's constructs.
Concluding from your description above, your declarations will not
produce any guarantees, as you say one can "decide" to live
dangerously. So while these declarations imply some overhead
(someone has to integrate them and maintain their code), they
will not help to make code safer.
Also, it seems that you allow a ground term to be destructable -
I think that is particularly cumbersome. A ground/1 would not
be sufficient for tabling - an extra check for the presence
of a problematic structure would be needed.
bart demoen
> In the long term, one or two such destructible terms might be sufficient
> to support WG17's constructs.
There have been quite a few individuals in the past, more intelligent than
both if us together, who have made statements of the form
"one or two of X will suffice for Y"
and were proven wrong shortly after their statement was taken seriously.
So allow me to not take yours seriously :-)
But seriously now: the declaration I propose offers a general way to deal
with destructive assignment. If you want to use it (behind the scenes) just
for the one or two destructible terms you can image now, that's fine.
> Concluding from your description above, your declarations will not
> produce any guarantees, as you say one can "decide" to live dangerously.
I said that, and I am now ready to reconsider what I said: I was just
considering the use of the declaration during the process of introducing
more representation sharing. But of course (and I am glad you sort of
indirectly pointed it out to me) the same declaration can be used to disallow
any destructive update on functors that have no such declaration. I did not
think about that, but now, thanks to your remark, the thing is indeed foolproof.
A little test in set_arg/3 and we are done.
Once more: thank you for making me think just a little further !
> So while these declarations imply some overhead (someone has to
> integrate them and maintain their code), they will not help to make code
> safer.
Now they do, and the overhead is epsilon larger than the overhead involved in
supporting destructive assignment on just one or two terms.
> Also, it seems that you allow a ground term to be destructable - I think
> that is particularly cumbersome. A ground/1 would not be sufficient for
> tabling - an extra check for the presence of a problematic structure
> would be needed.
First: isn't there a similar problem for global variables ?
Second: tabling (as implemented in XSB, Yap, ...) involves making a
copy - even of ground terms. While I always was (and still am) interested in
the possibility to not copy ground terms during tabling, I don't think that
the extra test of "is this a problematic structure" will destroy the whole thing.
We are talking here of a (small) constant time check every time a functor is seen,
during a procedure that dereferences, checks tags, and checks for cycles in the term.
Hardly something to worry about.
Cheers to all except Ulrich,
Bart Demoen
Ulrich Neumerkel
>On Thu, 03 Dec 2009 19:41:34 +0000, Ulrich Neumerkel wrote:
>So allow me to not take yours seriously :-)
The more arguments you put forward, the better!
>> So while these declarations imply some overhead (someone has to
>> integrate them and maintain their code), they will not help to make code
>> safer.
>
>Now they do, and the overhead is epsilon larger than the overhead involved in
>supporting destructive assignment on just one or two terms.
This is definitely an improvement! Nevertheless, think about the very
idea that someone can write:
:- destructible((.)/2).
Maybe accidentally. It then suffices that setarg/3 accesses a list.
Also I do not quite see how you can handle the issues of modularity.
How can I be sure that a term is not used for destructive purposes?
I use - say (-)/2.
>> Also, it seems that you allow a ground term to be destructable - I think
>> that is particularly cumbersome. A ground/1 would not be sufficient for
>> tabling - an extra check for the presence of a problematic structure
>> would be needed.
>
>First: isn't there a similar problem for global variables ?
That was already discussed in Udine - and the conclusion then
was to go for nonground terms. The implementation with open
lists reflects this.
>Second: tabling (as implemented in XSB, Yap, ...) involves making a
A concrete implementation can handle this - absolutely. But
if I write such things myself - for some cases - it would
increase the weight put on me. So most probably I would
live with incorrect code. Much in the same manner, as all
implementations of subsumes_term/2 that use numbervars/3.
Most of the time they work. Kind of.
bart demoen
> This is definitely an improvement! Nevertheless, think about the very
> idea that someone can write:
>
> :- destructible((.)/2).
>
> Maybe accidentally. It then suffices that setarg/3 accesses a list.
This one is easy: I don't have to think about it - someone adopting the
general schema should. And in this case, the solution is: don't let
anybody declare the list constructor as destructible.
I actually think that a declaration like
:- mutable(f(yes,no,yes)).
(modulo the names choosen) would be better: it indicates which argument of
f/3 can be updated destructively.
> Also I do not quite see how you can handle the issues of modularity. How
> can I be sure that a term is not used for destructive purposes? I use -
> say (-)/2.
I might have pointed this one out before - SWI mailing list perhaps.
I rephrase that: as long as the module system allows only to assign predicates
to a module, and not functors, this is not possible. This does not mean my
proposal is nonsense, but says something (a bit weaker) about the predicate
based module system that Prolog systems have allowed to become their de facto
standard. In a module system that allows to assign functors to modules, it would
be easy.
What I suggest above does not mean (anymore) that I would like all Prolog
systems to change their module system to atom-based - it is too late for that.
Still, a declaration of the form
:- local_functor(foo(_,_,_)).
would help enormously: the compiler/loader can take this.
More declarations ? Yes, that's the way to go for getting more reliable
Prolog programs/systems that use nifty features (like representation sharing, or
implementation hiding).
>>> Also, it seems that you allow a ground term to be destructable - I
>>> think that is particularly cumbersome. A ground/1 would not be
>>> sufficient for tabling - an extra check for the presence of a
>>> problematic structure would be needed.
[...]
>>Second: tabling (as implemented in XSB, Yap, ...) involves making a
>
> A concrete implementation can handle this - absolutely. But if I write
> such things myself - for some cases - it would increase the weight put
> on me. So most probably I would live with incorrect code.
That would be entirely your own choice of course, and I can only respect it.
Cheers
Bart Demoen
Ulrich Neumerkel
>On Thu, 03 Dec 2009 21:26:17 +0000, Ulrich Neumerkel wrote:
>> Also I do not quite see how you can handle the issues of modularity. How
>> can I be sure that a term is not used for destructive purposes? I use -
>> say (-)/2.
>
>I might have pointed this one out before - SWI mailing list perhaps.
>I rephrase that: as long as the module system allows only to assign predicates
>to a module, and not functors, this is not possible. This does not mean my
>proposal is nonsense, but says something (a bit weaker) about the predicate
>based module system that Prolog systems have allowed to become their de facto
>standard. In a module system that allows to assign functors to modules, it would
>be easy.
>
>What I suggest above does not mean (anymore) that I would like all Prolog
>systems to change their module system to atom-based - it is too late for that.
>Still, a declaration of the form
> :- local_functor(foo(_,_,_)).
>would help enormously: the compiler/loader can take this.
Which concrete Prolog system do you have in mind that could support
this?
I have some sympathy for that desire, but I cannot see any existing
atom/name based Prolog system that does not violate some of the very
basic expectations Prolog programmers have.
Also, it might be helpful to concentrate on efforts that are compatible
with ISO 13211-2 Modules. Synergy isn't coming from going against a
standard.
>More declarations ? Yes, that's the way to go for getting more reliable
>Prolog programs/systems that use nifty features (like representation sharing, or
>implementation hiding).
It depends what kind of declaration we are after. But
more declarations mean more mental weight for a programmer
to handle. This might be outweighted by the actual properties
guaranteed by those declarations. But in this particular
case here, this seems just a burden with no advantage at all.
Can I e.g. install such a declaration dynamically? Can I
retract such a declaration dynamically? Looks to me like
a lot of unnecessary headache.
If you really like to have many destructible functors, you could
demand that their names all start with e.g. '$destr'.
How is the compiler affected by your declaration?
>>>> Also, it seems that you allow a ground term to be destructable - I
>>>> think that is particularly cumbersome. A ground/1 would not be
>>>> sufficient for tabling - an extra check for the presence of a
>>>> problematic structure would be needed.
>[...]
>>>Second: tabling (as implemented in XSB, Yap, ...) involves making a
>>
>> A concrete implementation can handle this - absolutely. But if I write
>> such things myself - for some cases - it would increase the weight put
>> on me. So most probably I would live with incorrect code.
>
>That would be entirely your own choice of course, and I can only respect it.
That isn't a rational choice made by deliberation - it's just what
will happen inevitably - when programming we do not have that much
attention left.
bart demoen
> bart demoen <b...@cs.kuleuven.be> writes:
>>late for that. Still, a declaration of the form
>> :- local_functor(foo(_,_,_)).
>>would help enormously: the compiler/loader can take this.
>
> Which concrete Prolog system do you have in mind that could support
> this?
[btw I meant "the compiler/loader can take care of this]
Every concrete Prolog system could support this. ECLiPSe has something
in that line for declaring named fields for a local structure; M-Prolog
had locally hidden functors. It wouldn't be a big deal to support
local functors. If you have an M-Prolog manual, I suggest you read its
module system specs.
> I have some sympathy for that desire, but I cannot see any existing
> atom/name based Prolog system that does not violate some of the very
> basic expectations Prolog programmers have.
The predicate based module system violates the basic expectation
of every Prolog programmer that a simple meta-interpreter works.
I think in violating expectations, the pbms scores higher.
> Also, it might be helpful to concentrate on efforts that are compatible
> with ISO 13211-2 Modules. Synergy isn't coming from going against a
> standard.
Synergy might lead to extinction - evolution in the right direction is
at least as important as synergy.
> It depends what kind of declaration we are after. But more declarations
> mean more mental weight for a programmer to handle. This might be
> outweighed by the actual properties guaranteed by those declarations.
> But in this particular case here, this seems just a burden with no
> advantage at all.
"seems" is the operative word here: unless you are open minded and give
it some try, you will never know. I know I am unable to convince you: you
have to do it yourself.
> Can I e.g. install such a declaration dynamically? Can I retract such a
> declaration dynamically?
Both: maybe - I haven't thought about it until you asked, but installing
such a declaration (if done for a local functor) seems fine to me; retracting
it feels wrong to me, but mostly because I cannot see the consequences.
> If you really like to have many destructible functors, you could demand
> that their names all start with e.g. '$destr'.
That would be a convention, one that can too easily be not obeyed, like
calling setarg only on structures with a unique variable as last argument.
And his is exactly the sort of thing that a modern Prolog system should get rid
off: conventions with a strong semantics.
The current convention of having just the $mutable/2 functor for mutable terms
and still exposing that name and arity, is equally bad - I understand it from
the point of view "there is a problem, we want a solution now, and we see nothing
better without more effort" - but it on principles it cannot be defended.
> How is the compiler affected by your declaration?
A rhetorical question I presume.
> That isn't a rational choice made by deliberation - it's just what will
> happen inevitably - when programming we do not have that much attention
> left.
We can at least try to spent time and attention during the language
development phase, so that everyone benefits during the programming phase.
That's why I am just proposing things, not trying to enforce them. I am pointing
out potential and even if proven wrong in the end, I will not be convinced by
your negativism only.
Remember how this thread started, how negative I was about representation sharing,
and then still decided to give representation sharing a try ?
Cheers
Bart Demoen
Ulrich Neumerkel
>On Tue, 08 Dec 2009 21:40:57 +0000, Ulrich Neumerkel wrote:
>> Which concrete Prolog system do you have in mind that could support
>> this?
>
>[btw I meant "the compiler/loader can take care of this]
>
>Every concrete Prolog system could support this. ECLiPSe has something
>in that line for declaring named fields for a local structure; M-Prolog
>had locally hidden functors. It wouldn't be a big deal to support
>local functors. If you have an M-Prolog manual, I suggest you read its
>module system specs.
So far, any such extensions had some - hidden or not - price tag,
that far exceeded the benefits. Indirect references will not help.
>> I have some sympathy for that desire, but I cannot see any existing
>> atom/name based Prolog system that does not violate some of the very
>> basic expectations Prolog programmers have.
>
>The predicate based module system violates the basic expectation
>of every Prolog programmer that a simple meta-interpreter works.
>I think in violating expectations, the pbms scores higher.
Your conclusions are not based on any concrete systems I presume.
That makes it very difficult to find counterexamples.
In any case the very absence of such systems could lead us
to some conclusions about their fitness.
>> Also, it might be helpful to concentrate on efforts that are compatible
>> with ISO 13211-2 Modules. Synergy isn't coming from going against a
>> standard.
>
>Synergy might lead to extinction - evolution in the right direction is
>at least as important as synergy.
May I suggest that you look at FP? At least for them
synergy (literally: together-work) did work. I do not want
to draw too general conclusions from that, hof course.
>> If you really like to have many destructible functors, you could demand
>> that their names all start with e.g. '$destr'.
>That would be a convention, one that can too easily be not obeyed, like
>calling setarg only on structures with a unique variable as last argument.
I do not get it. Please repeat. This convention plus the variable as
last argument restriction should not be enough? That is, two such
tests during setarg/3 are not safer than any of the conventions
mentioned before? Maybe there is some indirect effect I am simply
missing.
Maybe you also mean by "convention" something that is not enforced
by setarg/3.
>And his is exactly the sort of thing that a modern Prolog system should get rid
>off: conventions with a strong semantics.
>
>The current convention of having just the $mutable/2 functor for mutable terms
>and still exposing that name and arity, is equally bad - I understand it from
>the point of view "there is a problem, we want a solution now, and we see nothing
>better without more effort" - but it on principles it cannot be defended.
Which current convention are you referring to? Maybe one '$mutable'/2 is
not enough, maybe. Two?
>> How is the compiler affected by your declaration?
>
>A rhetorical question I presume.
Unfortunately not, I wish it would be one. I am thinking of unfolding
and the hassle caused by it.
>Remember how this thread started, how negative I was about representation sharing,
>and then still decided to give representation sharing a try ?
I agree with your assessment. But I prefer to look at brighter sides.