This was memory fragmentation
A.L.
this was memory fragmentation, but caused not by Prolog, but by legacy
module written in C and having very poor memory management. Prolog was
crashing because it was not able to get memory.
Pre-alocating memory to Prolog shifted crashes to other places and
this way we discovered the real source of problems.
However, coming back to basics... Bart posted the following program:
a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
a(N,_) :- N =< 0.
When executed on SICStus with sufficiently large N it takes 200 MB.
Questoon: is it possible to raclaim this memory and how? Or this is
memory leak?
I am not asking how to modify this program in such a way that it will
NOT consume thsi much memory. Question is how to get this memory back.
A.L.
Jan Wielemaker
You really don't know? All this memory is in choicepoints, so:
(1) Fix it using a `green' (O'Keefe terminology) cut. This
is what you must do.
(2) Fix it using a cut after the computation completes. This
is a commonly seen solution, but it is bad style. Bugs must
be fixes where they are, not somewhere else. Note that memory
won't drop right away, but the next garbage collection will get
rid of most.
(3) Use the poor mens GC:
findall(G, G, List), member(G, List).
I must stress that such code needs to be fixed where the bug is. You
can use SWI-Prolog's PlUnit to find determinism errors through your
test suite. It also runs on SICStus (>=3.8, not tested on 4.x).
Cheers --- Jan
A.L.
wrote:
Yes, I DO know how to modify the program. But this was not my
question.
I explicitly asked, quote myself: " I am not asking how to modify this
program in such a way that it will NOT consume this much memory.
Question is how to get this memory back."
Means, the question was: Will this memory be ever garbage collected?
When choicepoint memory is considered "free" ("not referenced" in Java
jargon)?
A.L.
Jan Wielemaker
I read that :-) Thats why I gave the (2) and (3) options. They are
bad style emergency measures, but they do the job.
> Means, the question was: Will this memory be ever garbage collected?
> When choicepoint memory is considered "free" ("not referenced" in Java
> jargon)?
Open choicepoints *are* referenced and cannot be gc'ed (well, you could
write an intelligent garbage collector that will find the above problem,
it it won't find others. Implementors taking the trouble to sort that
out do so by enhancing clause indexing and then this problem runs fine
immediately.
To get back at your loop, you have
loop(State) :-
step(State, State2),
loop(State2).
That is free of leaks iff step is deterministic. You can also write
it as
loop(State) :-
step(State, State2), !,
loop(State2).
Now it is obviously free of leaks, but if there is a determinism problem
somewhere inside step/2, step/2 may run out of memory totally unneeded.
Of course, I assume you take care that side-effects in step/2 are also
free of leaks and State doesn't grow unbounded.
Cheers --- Jan
A.L.
wrote:
>
>Open choicepoints *are* referenced and cannot be gc'ed (well, you could
>write an intelligent garbage collector that will find the above problem,
>it it won't find others. Implementors taking the trouble to sort that
>out do so by enhancing clause indexing and then this problem runs fine
>immediately.
Thanks, this clarifies mproblem.
A.L.
bart demoen
> However, coming back to basics... Bart posted the following program:
>
> a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
> a(N,_) :- N =< 0.
>
> When executed on SICStus with sufficiently large N it takes 200 MB.
> Questoon: is it possible to raclaim this memory and how? Or this is
> memory leak?
Jan has answered very appropriately, so I will attack these two
questions from a different angle.
First of all, the two questions suggest that
if it is possible to reclaim this memory, it is not a memory leak
which by all reasonable definitions of "memory leak", this would be a
wrong belief. Memory leaks are the result of a bug, because memory
that is not needed, is kept alive. Of course, the question remains:
whose bug is it. If it is a bug by the Prolog programmer, there is no
other solution than to change the program, so
> I am not asking how to modify this program in such a way that it will
> NOT consume thsi much memory. Question is how to get this memory back.
is unreasonable, since also "how to get this memory back" involves
changing the program: there was a bug in the program, remember !
Of course the bug could be in the Prolog system, and then removing the
bug from the Prolog system would be the ideal solution.
In the above program, it is almost trivial to adapt the compiler to
avoid the memory leak, actually, you can do it yourself with term
expansion. So, you might conclude: it was a bug in the Prolog system.
But have a look at a small variant of the above a/1 predicate:
b(N,_) :- cat(N), M is N - 1, b(M,foo(1,2,3,4,5)).
b(N,_) :- dog(N).
where cat/1 and dog/1 are Prolog predicates, doing a lot of computation,
and you (the programmer of b/2, cat/1 and dog/1) know that for all
values of N, cat(N) and dog(N) are mutually exclusive (and always
terminate and do not have side effects), but the compiler has no clue ...
is it now YOUR bug that you didn't put a cut after cat(N), or is it a
bug of the Prolog system that it couldn't detect all the properties
that make it correct to have the cut inserted by the compiler ?
Take into account that the necessary conditions (for inserting the
cut) are in general undecidable. From which it follows that any
compiler is bound to detect only sufficient conditions. For instance,
a compiler that does one level of inlining and by chance there are the
definitions
cat(N) :- N > 0.
dog(N) :- N =< 0.
will detect that a cut can be inserted.
But in general, it won't.
Still, YOU can assist the compiler, and in two ways. The first one is
obvious: you put the cut in your code, right after the cat(N) goal, or
at the very least right after the top call to b/2.
The second one is more productive: with term expansion, you write
general rules to transform the above b/2 clauses (and other predicate
definitions) to a form with the cut whenever admissible. (for some
systems, it might even be better to make it into an if-then-else)
The latter is exactly what hProlog does: the compiler has a small
module source_optimize that does this kind of source2source
transformations before the source code goes to the bytecode
generator. The compiler doesn't even need to know about it. I can add
stuff to it any day - I regularly do, because it is little effort for
huge gains, but I am aware that it will never be complete.
AFAIK, such a module could easily be hooked into the SWI, SICStus, Yap
... compiler by their implementors. But since all these systems have
term expansion (an evil heritage from DEC-10 Prolog :-) you can do it
yourself.
BTW, DIY was kind of an Edinburgh clan adagio and it has proven to be
quite contra productive (the other extreme is Java, where everything
has been done for you), but term expansion is still the only thing you
are left with.
Cheers
Bart Demoen
vsc...@gmail.com
> On Tue, 05 Feb 2008 08:25:28 -0600, A.L wrote:
> > However, coming back to basics... Bart posted the following program:
>
> > a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
> > a(N,_) :- N =< 0.
>
Hi!
I consider this a limitation (bug) in current Prolog compilers. Every
Prolog compiler should compile this code into something like this:
a(N,_) :- var(X), original_code_for_a(X).
a(N,_) :- ( N> 0 -> .. ; ... ).
B-Prolog is the one I know who gets close to this. Apologies to anyone
I don't mention.
Our excuses:
- People add the cuts anyway, so why should we bother :)
- In general, detecting whether tests are disjoint is a complex
problem, even for built-ins. Better not to make any promises, than
failing to recognize cases the user knows are deterministic, right?
- Deep guards (user-code) are difficult, as Bart explained.
Still, we have known how to do better for quite a while, and we sure
should be able to. So I think you're asking the right question.
Cheers
Vitor
Bart Demoen
>>>a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
>>>a(N,_) :- N =< 0.
>>
>
> Hi!
>
> I consider this a limitation (bug) in current Prolog compilers. Every
> Prolog compiler should compile this code into something like this:
>
> a(N,_) :- var(X), original_code_for_a(X).
> a(N,_) :- ( N> 0 -> .. ; ... ).
Why the first clause ? The second one is enough, no ?
>
> B-Prolog is the one I know who gets close to this. Apologies to anyone
> I don't mention.
Apology accepted ... hProlog :-) It's not a real Prolog system of course.
Cheers
Bart Demoen
A.L.
wrote:
>On Tue, 05 Feb 2008 08:25:28 -0600, A.L wrote:
>
>> However, coming back to basics... Bart posted the following program:
>>
>> a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
>> a(N,_) :- N =< 0.
>>
>> When executed on SICStus with sufficiently large N it takes 200 MB.
>> Questoon: is it possible to raclaim this memory and how? Or this is
>> memory leak?
>
>Jan has answered very appropriately, so I will attack these two
>questions from a different angle.
>
>First of all, the two questions suggest that
>
> if it is possible to reclaim this memory, it is not a memory leak
>
>which by all reasonable definitions of "memory leak", this would be a
>wrong belief. Memory leaks are the result of a bug, because memory
>that is not needed, is kept alive. Of course, the question remains:
>whose bug is it. If it is a bug by the Prolog programmer, there is no
>other solution than to change the program, so
For me, this is obviously a "bug" of Prolog system. Prolog doesn't
know how to handle simple situation (well, some Prologs know)...
A.L.
Jan Wielemaker
> On Tue, 05 Feb 2008 22:01:28 +0100, bart demoen <b...@cs.kuleuven.be>
> wrote:
>
>>On Tue, 05 Feb 2008 08:25:28 -0600, A.L wrote:
>>
>>> However, coming back to basics... Bart posted the following program:
>>>
>>> a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
>>> a(N,_) :- N =< 0.
<snip>
>>which by all reasonable definitions of "memory leak", this would be a
>>wrong belief. Memory leaks are the result of a bug, because memory
>>that is not needed, is kept alive. Of course, the question remains:
>>whose bug is it. If it is a bug by the Prolog programmer, there is no
>>other solution than to change the program, so
>
> For me, this is obviously a "bug" of Prolog system. Prolog doesn't
> know how to handle simple situation (well, some Prologs know)...
Its most definitely not a bug. Neither the ISO standard, nor the
documentation of your Prolog system says this situation must be
recognised.
I'm not at all sure it is desirable for Prolog implementations to deal
with this automatically. At the moment the bottom-line of clause
indexing is widely described and recognised. The more intelligent you
make this, the less clear it will become what is and what is not
recognised. We know we can't get this perfect.
One possible option is to allow for declarations, so you can state
something like this.
:- exclusive([ N>X, N=<X ]).
:- exclusive([ N>X, N=:=X, N<X ]).'
But also (if we know this is true in our domain):
:- exclusive([red(X),green(X)]).
Next learn your editor/development environment to indicate what will
be recognised.
Cheers --- Jan
A.L.
wrote:
>On 2008-02-06, A.L <alew...@fala2005.com> wrote:
>> On Tue, 05 Feb 2008 22:01:28 +0100, bart demoen <b...@cs.kuleuven.be>
>> wrote:
>>
>>>On Tue, 05 Feb 2008 08:25:28 -0600, A.L wrote:
>>>
>>>> However, coming back to basics... Bart posted the following program:
>>>>
>>>> a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
>>>> a(N,_) :- N =< 0.
>
><snip>
>
>>>which by all reasonable definitions of "memory leak", this would be a
>>>wrong belief. Memory leaks are the result of a bug, because memory
>>>that is not needed, is kept alive. Of course, the question remains:
>>>whose bug is it. If it is a bug by the Prolog programmer, there is no
>>>other solution than to change the program, so
>>
>> For me, this is obviously a "bug" of Prolog system. Prolog doesn't
>> know how to handle simple situation (well, some Prologs know)...
>
>Its most definitely not a bug. Neither the ISO standard, nor the
>documentation of your Prolog system says this situation must be
>recognised.
It IS a bug.
My Prolog documentation doesn't say that this is a problem. Actually,
program with this "bug" behaves as expected. Problems are exlusively
with the compiler inability to recognize the problem, and the GC
inability to collect choicepoints. My manual says nothing about
strategy of GC, what can be collected and what cannot be, and what are
consequences of "bad" programming of otherwise correct program.
One again, for me it IS a bug, and it belongs to the category of
"showstoppers". This is fine if we are writing student programs or
"two-liners" but is not fine if I have 25K lines of Prolog and I have
manualy detect situations as above. And probably many similar
situations that we haven't discussed here.
A.L.
Jan Wielemaker
> On 06 Feb 2008 14:46:13 GMT, Jan Wielemaker <j...@nospam.ct.xs4all.nl>
> wrote:
>
>>On 2008-02-06, A.L <alew...@fala2005.com> wrote:
>>> On Tue, 05 Feb 2008 22:01:28 +0100, bart demoen <b...@cs.kuleuven.be>
>>> wrote:
>>>
>>>>On Tue, 05 Feb 2008 08:25:28 -0600, A.L wrote:
>>>>
>>>>> However, coming back to basics... Bart posted the following program:
>>>>>
>>>>> a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
>>>>> a(N,_) :- N =< 0.
>>
>><snip>
>>
>>>>which by all reasonable definitions of "memory leak", this would be a
>>>>wrong belief. Memory leaks are the result of a bug, because memory
>>>>that is not needed, is kept alive. Of course, the question remains:
>>>>whose bug is it. If it is a bug by the Prolog programmer, there is no
>>>>other solution than to change the program, so
>>>
>>> For me, this is obviously a "bug" of Prolog system. Prolog doesn't
>>> know how to handle simple situation (well, some Prologs know)...
>>
>>Its most definitely not a bug. Neither the ISO standard, nor the
>>documentation of your Prolog system says this situation must be
>>recognised.
>
> It IS a bug.
>
> My Prolog documentation doesn't say that this is a problem. Actually,
Are you implying your Prolog documentation is supposed to point you at
anything that can be a problem? Like the famous magnetron that is not
supposed to be used for drying your pet? I think the system
documentation should indeed indicate somewhere what the capabilities
of clause indexing of the system is as this is system specific (though
there is a more or less accepted baseline).
The fact that if clause indexing cannot make the choice deterministic
requires you to add a `green' cut is discussed in the literature.
Read The Craft of Prolog. Anyone who wants to do serious programming
in Prolog should read this (writing your own compiler is an
alternative taken by some Prolog programmers :-)
> One again, for me it IS a bug, and it belongs to the category of
> "showstoppers". This is fine if we are writing student programs or
> "two-liners" but is not fine if I have 25K lines of Prolog and I have
> manualy detect situations as above. And probably many similar
> situations that we haven't discussed here.
Then you need a better environment. I'd be surprised if Ciao's
assertion language cannot find this for you. SWI-Prolog's unit test,
toplevel, profiler and graphical debugger help discovering and finding
these errors. Before I had those this type of error happened a lot to
me, but these days they are extremely rare.
Cheers --- Jan
Bart Demoen
Using a little common sense, I think that the manual is quite clear about
NOT doing choicepoint collection.
Books and tutorials are usually full of warnings for left behind useless
choicepoints.
Let me shift to C - take the function
int f(int i)
{
if (i > 0) return(f(i-1));
else return(17);
}
and call f(123234234). The fact that it segmentation faults, is it because
of a bug in the C-compiler ? Or in the operating system that hasn't documented
that it does not gc the runtime stack ? Or should the programmer have known
that this will go wrong (with gcc optimization lower than -O2) ?
> One again, for me it IS a bug, and it belongs to the category of
> "showstoppers". This is fine if we are writing student programs or
> "two-liners" but is not fine if I have 25K lines of Prolog and I have
> manualy detect situations as above. And probably many similar
> situations that we haven't discussed here.
Let's try to turn this into something more constructive (unusual for me, but
I am getting older) ...
Where would you draw the line ? Can you specify what a system must recognize
as deterministic (and put itself the appropriate cuts) in order not to be
considered buggy by you ?
BTW, I think SWI teaches you to fish, while implementations that only recognize
some determinism, just give you a fish. The best thing is of course to get
some (even a lot of) fish for free, and also know how to fish, just in case.
Cheers
Bart Demoen
A.L.
wrote:
>
>Are you implying your Prolog documentation is supposed to point you at
>anything that can be a problem? Like the famous magnetron that is not
>supposed to be used for drying your pet? I think the system
>documentation should indeed indicate somewhere what the capabilities
>of clause indexing of the system is as this is system specific (though
>there is a more or less accepted baseline).
>
I would expect that Prolog manual and Prolog literature would point to
all IMPORTANT and NON-TRIVIAL issues of internal compiler functioning
and memory management that I cannot gather other way than to be
enlighted by Supreme Spirit of by asking on this group.
Especialy, NOWHERE it is said (with notable exception of Craft of
Prolog that ahs this on 5 pages and talks mostly about DEC-10) how GC
works, what can be collected or not, and how programming style can
impact this.
>The fact that if clause indexing cannot make the choice deterministic
>requires you to add a `green' cut is discussed in the literature.
>Read The Craft of Prolog. Anyone who wants to do serious programming
>in Prolog should read this (writing your own compiler is an
>alternative taken by some Prolog programmers :-)
>
Thanks for advice. I memorized "Craft of Prolog" many years ago, and
your idea of "writing your own compiler to learn Prolog" is nothing
more than one more proof of huge gap between the industry and the
academia. And for me (sorry, I was a professor for 25 years, therefore
I feel free to write about this profession whatever I want) this is
something what I call "academic arrogance". No doubt that Prolog is
not used (except me and maybe few other) for commercial development.
>> One again, for me it IS a bug, and it belongs to the category of
>> "showstoppers". This is fine if we are writing student programs or
>> "two-liners" but is not fine if I have 25K lines of Prolog and I have
>> manualy detect situations as above. And probably many similar
>> situations that we haven't discussed here.
>
>Then you need a better environment. I'd be surprised if Ciao's
>assertion language cannot find this for you. SWI-Prolog's unit test,
>toplevel, profiler and graphical debugger help discovering and finding
>these errors. Before I had those this type of error happened a lot to
>me, but these days they are extremely rare.
If SWI a) provides as good CLP(FD) as SICStus has, b) provides paid
support as good as SICStus provides, c) provides commercial license,
I definitely will consider switching.
A.L.
vsc...@gmail.com
> vsco...@gmail.com wrote:
> >>>a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
> >>>a(N,_) :- N =< 0.
>
> > Hi!
>
> > I consider this a limitation (bug) in current Prolog compilers. Every
> > Prolog compiler should compile this code into something like this:
>
> > a(N,_) :- var(X), original_code_for_a(X).
> > a(N,_) :- ( N> 0 -> .. ; ... ).
>
> Why the first clause ? The second one is enough, no ?
Yes, in this case it wouldn't be needed, but in the general case it
would make sense to have that test.
> Apology accepted ... hProlog :-) It's not a real Prolog system of course.
>
Oopss, sorry again!
Cheers
Vitor
> Cheers
>
> Bart Demoen
bart demoen
> On Feb 6, 1:41 pm, Bart Demoen <b...@cs.kuleuven.ac.be> wrote:
>> vsco...@gmail.com wrote:
>> >>>a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
>> >>>a(N,_) :- N =< 0.
>>
>> > Hi!
>>
>> > I consider this a limitation (bug) in current Prolog compilers. Every
>> > Prolog compiler should compile this code into something like this:
>>
>> > a(N,_) :- var(X), original_code_for_a(X).
>> > a(N,_) :- ( N> 0 -> .. ; ... ).
>>
>> Why the first clause ? The second one is enough, no ?
>
>
> Yes, in this case it wouldn't be needed, but in the general case it
> would make sense to have that test.
Ok. But then you should put a cut after the var(X) test, so that the
compiler can turn it into [also fixing some varname typos]
a(N,_) :-
(var(N) ->
original_code_for_a(N)
;
N > 0 ->
...
;
...
).
right ? [just trying to get on your nerves :-]
Cheers
Bart Demoen
bart demoen
> On 06 Feb 2008 15:27:17 GMT, Jan Wielemaker <j...@nospam.ct.xs4all.nl>
> wrote:
>>The fact that if clause indexing cannot make the choice deterministic
>>requires you to add a `green' cut is discussed in the literature.
>>Read The Craft of Prolog. Anyone who wants to do serious programming
>>in Prolog should read this (writing your own compiler is an
>>alternative taken by some Prolog programmers :-)
>>
>
> Thanks for advice. I memorized "Craft of Prolog" many years ago, and
> your idea of "writing your own compiler to learn Prolog" is nothing
> more than one more proof of huge gap between the industry and the
> academia. And for me (sorry, I was a professor for 25 years, therefore
> I feel free to write about this profession whatever I want) this is
> something what I call "academic arrogance".
Please A.L., apologize to Jan for not having noticed the :-) at the end of
his "advice", and for having jumped to hasty conclusions about his
arrogance.
The only arrogance (maybe hubris is the better word) Jan has
shown in the past decade, was to offer almost singlehandedly the most
complete and usefull Prolog system for free to the world, and to continue
doing that, despite being accused from time to time to be arrogant.
And let's get back to the basics of this discussion, which is after all,
quite relevant: it involves a developer and an knowledgable user - if not
an SWI user, at least a Prolog user.
Cheers
Bart Demoen
A.L.
<b...@cs.kuleuven.ac.be> wrote:
>
>
>Let me shift to C - take the function
>
>int f(int i)
>{
> if (i > 0) return(f(i-1));
> else return(17);
>}
>
>and call f(123234234). The fact that it segmentation faults, is it because
>of a bug in the C-compiler ? Or in the operating system that hasn't documented
>that it does not gc the runtime stack ? Or should the programmer have known
>that this will go wrong (with gcc optimization lower than -O2) ?
>
And what when there is NO segmentattion faults, i.s. the above
function completes successfully?...
I was not complaining that your 2 liner gives segmentation fault...
>
>Where would you draw the line ? Can you specify what a system must recognize
>as deterministic (and put itself the appropriate cuts) in order not to be
>considered buggy by you ?
>
I don't know. In conventinal languages you have C from one side, where
you can write whatever you want and compiler swallows everything, and
Ada from other side when it is really hard to oursmart the compiler. I
would prefer to have Prolog closer to Ada than to C...
>BTW, I think SWI teaches you to fish, while implementations that only recognize
>some determinism, just give you a fish. The best thing is of course to get
>some (even a lot of) fish for free, and also know how to fish, just in case.
I appreciate this, my only compian is that I cannot find this in
Prolog textbooks. EXPLICITLY stated.
A.L.
A.L.
wrote:
>On Wed, 06 Feb 2008 10:18:04 -0600, A.L wrote:
>
>> On 06 Feb 2008 15:27:17 GMT, Jan Wielemaker <j...@nospam.ct.xs4all.nl>
>> wrote:
>>>The fact that if clause indexing cannot make the choice deterministic
>>>requires you to add a `green' cut is discussed in the literature.
>>>Read The Craft of Prolog. Anyone who wants to do serious programming
>>>in Prolog should read this (writing your own compiler is an
>>>alternative taken by some Prolog programmers :-)
>>>
>>
>> Thanks for advice. I memorized "Craft of Prolog" many years ago, and
>> your idea of "writing your own compiler to learn Prolog" is nothing
>> more than one more proof of huge gap between the industry and the
>> academia. And for me (sorry, I was a professor for 25 years, therefore
>> I feel free to write about this profession whatever I want) this is
>> something what I call "academic arrogance".
>
>Please A.L., apologize to Jan for not having noticed the :-) at the end of
>his "advice", and for having jumped to hasty conclusions about his
>arrogance.
>
I do. I didn't notice.
However, trying to explain my attitude: I am bombarded by telephone
calls from field guys that Prolog server is crashing in production
environment, what can have rather bad consequences it I don't solve
the problem QUICKLY. First case was resolved: Prolog was not guilty.
Second case: Prolog is guilty.
There is evidently fire under my ass :)
Anyway, once again - apologize for temper and bad manners...
>And let's get back to the basics of this discussion, which is after all,
>quite relevant: it involves a developer and an knowledgable user - if not
>an SWI user, at least a Prolog user.
Sure.
A.L.
Joachim Schimpf
> On Feb 5, 9:01 pm, bart demoen <b...@cs.kuleuven.be> wrote:
>> On Tue, 05 Feb 2008 08:25:28 -0600, A.L wrote:
>>> However, coming back to basics... Bart posted the following program:
>>> a(N,_) :- N > 0, M is N - 1, a(M,foo(1,2,3,4,5)).
>>> a(N,_) :- N =< 0.
>
> Hi!
>
> I consider this a limitation (bug) in current Prolog compilers. Every
> Prolog compiler should compile this code into something like this:
>
> a(N,_) :- var(X), original_code_for_a(X).
> a(N,_) :- ( N> 0 -> .. ; ... ).
Don't forget that N > 0 and N =< 0 may both fail with ieee floats.
So to be safe you'd need some analysis too.
-- Joachim
Jan Wielemaker
>
Thanks for the apologies (other reply). They weren't needed as far as
I'm concerned. Though the baseline of my posts is intended constructive
I do take the liberty to tease a bit.
>>> One again, for me it IS a bug, and it belongs to the category of
>>> "showstoppers". This is fine if we are writing student programs or
>>> "two-liners" but is not fine if I have 25K lines of Prolog and I have
>>> manualy detect situations as above. And probably many similar
>>> situations that we haven't discussed here.
>>
>>Then you need a better environment. I'd be surprised if Ciao's
>>assertion language cannot find this for you. SWI-Prolog's unit test,
>>toplevel, profiler and graphical debugger help discovering and finding
>>these errors. Before I had those this type of error happened a lot to
>>me, but these days they are extremely rare.
>
> If SWI a) provides as good CLP(FD) as SICStus has, b) provides paid
> support as good as SICStus provides, c) provides commercial license,
> I definitely will consider switching.
clp(fd) is getting pretty good, thanks to all the work by Markus Triska
and Ulrich Neumerkel for the testing. I think the aim is to make it
really good, but it is not likely to become fast. Of course, sometimes
it outsmarts other implementations and than it is really fast, but the
baseline is definitely (much) slower. It is funny that you raise these
issues while I think it is far easier to master efficient Prolog than to
find out what you have to do for an efficient clp(fd) program.
As far as (b) is concerned, you can get paid support. Generally the
unpaid support appears to do the job quite well though. The license
allows for embedding in proprietary code. It doesn't give any warrantees
though.
On the other hand, I think SICStus is a very good commercial Prolog
implementation. There are benefits in both systems and unfortunately,
except for trivial programs, it is not easy to switch. It can be done,
and I know people who moved big programs either way.
Cheers --- Jan
Cesar Rabak
> On Wed, 06 Feb 2008 17:18:27 +0100, Bart Demoen
> <b...@cs.kuleuven.ac.be> wrote:
>
>>
>> Let me shift to C - take the function
>>
>> int f(int i)
>> {
>> if (i > 0) return(f(i-1));
>> else return(17);
>> }
>>
>> and call f(123234234). The fact that it segmentation faults, is it because
>> of a bug in the C-compiler ? Or in the operating system that hasn't documented
>> that it does not gc the runtime stack ? Or should the programmer have known
>> that this will go wrong (with gcc optimization lower than -O2) ?
>>
>
> And what when there is NO segmentattion faults, i.s. the above
> function completes successfully?...
>
> I was not complaining that your 2 liner gives segmentation fault...
>
>> Where would you draw the line ? Can you specify what a system must recognize
>> as deterministic (and put itself the appropriate cuts) in order not to be
>> considered buggy by you ?
>>
>
> I don't know. In conventinal languages you have C from one side, where
> you can write whatever you want and compiler swallows everything, and
> Ada from other side when it is really hard to oursmart the compiler. I
> would prefer to have Prolog closer to Ada than to C...
>
I don't see how in the Earth an Ada compilerš could avoid a stack
overflow like the above snippet. . .
Regards,
--
Cesar Rabak
[1] and yes, I do know Ada and have see stack overflows in it!
A.L.
wrote:
>
>I don't see how in the Earth an Ada compilerš could avoid a stack
>overflow like the above snippet. . .
>
Read from beginning. This was not about stack overflow, this was about
compiler allowing/not allowng some things.
A.L.
Bart Demoen
>> a(N,_) :- ( N> 0 -> .. ; ... ).
>
>
> Don't forget that N > 0 and N =< 0 may both fail with ieee floats.
> So to be safe you'd need some analysis too.
Both failing is not a big problem, just make the if-then-else into
a(N,_) :- ( N> 0 -> .. ; N =< 0, ... ).
which og course would be wrong if both can succeed :-(
Cheers
Bart Demoen
vsc...@gmail.com
This is getting interesting.
If we observe that the constant 0 is an integer, then we may avoid the
problem by using:
a(N,_) :- ( integer(N) -> (N> 0 -> ... ; ... ) ; original_code ).
or, in case we want to accept expressions that evaluate to an integer:
a(N,_) :- ( evaluates_to_integer(N,N1) -> (N1 > 0 -> ... ; ... ) ;
original_code ).
This would allow to further simplify the code for N1>0, as no type-
checking would now be required.
But I am sure Bart will find something wrong with this :) Or he is
doing this already :)
Cheers
Vitor
Cheers
Vitor
vsc...@gmail.com
I should comment a little further:
1. As you are probably aware, the SICStus manual has a pretty good
discussion on this problem:
I believe this part of the SICStus manual should actually be of
interest to any considering large scale programming in Prolog.
SICstus also provides a determinacy checker:
I don't know if the determinacy checker would work in this case, but
the Making Predicates Determinate Discussion is very appropriate.
2. I personally find it amazing how much stuff Jan does for SWI. Even
trying to copy some of his stuff to YAP is really hard work :( It
would be great if he, or I, or Bart, could address all these issues,
and making Prolog more declarative is a real issue.
But given that we are only human, we have to focus resources where we
see most need :(.
The good news is that I think people in the LP community are trying to
work together: Jan and I are trying to share code as much as possible,
and I see a general feeling of collaboration within the Prolog
community. Hopefully, pooling our resources together will allow us to
progress faster.
So, there is hope :)
Cheers
Vitor
On Feb 6, 9:15 pm, Jan Wielemaker <j...@nospam.ct.xs4all.nl> wrote:
Jan Wielemaker
> As I was the one to introduce the word bug in this context, I believe
> I should comment a little further:
>
> 1. As you are probably aware, the SICStus manual has a pretty good
> discussion on this problem:
>
> http://www.sics.se/sicstus/docs/latest4/html/sicstus.html/Making-Predicates-Determinate.html#Making-Predicates-Determinate
This at least confirms the issue is discussed in the manual. What is
missing is that although the faulty design behaves bad on backtracking
or negative input, the choicepoint issue raised by A.L. doesn't apply
to it, while this is the cause of many programs running out of stack or
simply being much too slow.
I also think the definition is still poor and should read
fac(N, X) :-
N > 0, !,
N1 is N - 1,
fac(N1, Y),
X is N * Y.
fac(0, 1) :- !.
fac(X, _) :-
must_be(nonneg, X).
(must_be/2 is part of SWI-Prolog library that will throw the proper
exception here: instantiation error, type error or domain error
depending on what is wrong). Alternatively one could write:
fac(N, I) :-
must_be(nonneg, N),
fac2(N, I).
fac2(0, 1) :- !.
fac2(N, X) :-
N > 0, !,
N1 is N - 1,
fac2(N1, Y),
X is N * Y.
I wouldn't state that if-then-else is faster than clauses. This depends
on the implementation and the implementation is free to rewrite the one
into the other. But, this is a *SICStus* manual, so if it applies for
SICStus, fine.
> 2. I personally find it amazing how much stuff Jan does for SWI. Even
> trying to copy some of his stuff to YAP is really hard work :( It
Luckily I'm not doing the bulk of the work. I only help a bit polishing
annoying incompatibilities and port some code from YAP to SWI (e.g. the
rbtree library).
> would be great if he, or I, or Bart, could address all these issues,
> and making Prolog more declarative is a real issue.
I'm not so sure Prolog needs to be declarative in this case. It will
never become a fully declarative language without lots of declarations.
Mercury is much further in that.
It would of course be good to have more widely accepted static analysis
tools. And have them mentioned in textbooks.
Prolog needs good and compatible implementations and lots of libraries
that help people writing real applications with it. A few more updated
textbooks wouldn't do any harm either.
> But given that we are only human, we have to focus resources where we
> see most need :(.
>
> The good news is that I think people in the LP community are trying to
> work together: Jan and I are trying to share code as much as possible,
> and I see a general feeling of collaboration within the Prolog
> community. Hopefully, pooling our resources together will allow us to
> progress faster.
:-)
Cheers --- Jan
Tom Schrijvers
>I'm not so sure Prolog needs to be declarative in this case. It will
>never become a fully declarative language without lots of declarations.
>Mercury is much further in that.
>
>It would of course be good to have more widely accepted static analysis
>tools. And have them mentioned in textbooks.
>
>
The problem is that static analysis and declarations come together. Without
declarations it's hard to much local analysis, and you need local
analysis to
make analysis practical. Also, the lack of a module system that prevents
arbitrary
calls and all the meta-programming features make analysis hard. Once you
have a
proper module and type system, it becomes much easier to analyse and
optimize.
That's not to say that there are useful things that can be done already.
On the one hand
you want performance to be predictable (1). On the other hand nobody
wants to be bothered
by tediously optimizing things they alreayd know. (2) So why not go the
way of having more
of these optimizing term expansions in libraries. You have to
consciously import the library to
get the optimization - which solves (1) to some extent, and you don't
have to look at all the
optimization details (2). This approach should be fairly portable too.
So you get portable performance
as long as the optimizing libraries use a common subset of features with
specified performance
characteristics.
The apply_macros library in SWI-Prolog is a nice example. It specializes
the higher-order/meta predicate maplist.
Some optimizations have been discussed in this thread. Would it be so
difficult to turn
them into an optimizing library?
Tom
Bart Demoen
[and then some fac/2 definitions]
I like these versions of fac/2 a lot - not because they are so
beautiful, but because they tell us where Prolog is bad, and how
things could be improved.
Here is the first version in the SICStus manual:
fac1(0, 1).
fac1(N, X) :-
N1 is N - 1,
fac1(N1, Y),
X is N * Y.
Let's have a look at what the SICStus manual says is the preferred
version of fac:
fac_pref(N, X) :-
( N > 0 ->
N1 is N - 1,
fac_pref(N1, Y),
X is N * Y
; N =:= 0 ->
X = 1
).
Note first the different semantics:
?- fac1(1-1,X).
ERROR: Out of local stack
?- fac1(2-1,X).
X = 1 ;
ERROR: Out of local stack
?- fac_pref(1-1,X).
X = 1
?- fac_pref(2-1,X).
X = 1
The fact that Prolog evaluates variables in arithmetic is very sneaky.
There is a good point NOT to do that.
In the "preferred" version, there is no good reason to have the
-> after the N =:= 0; a comma is fine. The -> suggests that there are
any choicepoints to be cut, but there aren't.
Now Jan's first version:
facjan1(N, X) :-
N > 0, !,
N1 is N - 1,
facjan1(N1, Y),
X is N * Y.
facjan1(0, 1) :- !.
facjan1(X, _) :-
must_be(nonneg, X).
?- facjan1(1-1,X).
ERROR: Type error: `nonneg' expected, found `1-1'
Exception: (11) throw(error(type_error(nonneg, 1-1), _G252)) ? creep
?- facjan1(2-1,X).
X = 1
Clearly not what one wants, and the origin is the same.
But Jan has a preferred version as well:
facjan_pref(N, I) :-
must_be(nonneg, N),
fac2(N, I).
fac2(0, 1) :- !.
fac2(N, X) :-
N > 0, !,
N1 is N - 1,
fac2(N1, Y),
X is N * Y.
?- facjan_pref(0,X).
X = 1
?- facjan_pref(1-1,X).
ERROR: Type error: `nonneg' expected, found `1-1'
Exception: (11) throw(error(type_error(nonneg, 1-1), _G252)) ? creep
So, facjan_pref is explicit: the N must be a number (and an int and not negative).
In the other versions, there was no(t always) a need for that.
I guess the cut after the N > 0 test in the last clause remained there
because of cut&paste, so let's ignore it.
Now, the code for facjan_pref/fac2 specifies twice that the N must be
> 0: once in the mustbe goal, and once in the second clause of fac2 -
how redeundant is that ...
But we cannot remove the last N > 0, because then we get
?- facjan_pref(0,7).
ERROR: Out of local stack
which is due to the first clause of fac2: it should have been
fac2(0,Res) :- !, Res = 1.
Given that experts (Jan, Vitor) make subtle mistakes, and given the
pitfalls of floating point arithmetic (see what Joachim wrote), and
because of the pitfalls of unification (with 0 for instance) is quite
different from arithmetic equality testing (=:= 0) ...
wouldn't the following be a better way to write fac/2:
:- type facbartpref(nonnegint:in, int:out). % (*)
facbartpref(0,1).
facbartpref(N,Res) :-
N \== 0,
M is N - 1,
facbartpref(M,Temp),
Res is N * Temp.
I have replaced the N > 0 by N \== 0. A decent compiler should be able
to avoid choicepoints, and if statically, it cannot prove that
facbartpref is called correctly, it can insert a minimal set of tests
to ensure this.
Why is the Prolog community still so scared of type/mode declarations,
when their advantage is so obvious.
(*) modulo choice of syntax and type system
Cheers
Bart Demoen
Ulrich Neumerkel
>Why is the Prolog community still so scared of type/mode declarations,
>when their advantage is so obvious.
My personal experience is that truly strict types and modes
shift your attention away from your problem toward fighting the
system or (in an academic setting) proposing extentions. Sooner
or later you have to figure out how to transfer data from one
type "microcosmos" to another - and you will discover that
"show"ing things as strings is the only way out thereby undermining
the very intent of types (and at the same time introducing
unnecessary strictness). Note also, that type systems as such do not
prevent the creation of infinite data structures (Haskell: repeat 1).
Still, it would be nice to be able to express in a portable manner
certain assumptions that correspond to types and modes in Prolog.
SWI's library(error) is a starting point. This library could
be easily adopted by other systems. Why not focus optimizing
analysis on removing must_be/2 goals? This looks to me more
realistic than switching to declarations. You can step-by-step
start to enter must_be/2 goals in your existing programs without
any rewrite. And you can step-by-step remove those must_be/2 goals
automatically with some analysis.
No matter whether you use declarations or not there is no way
around actually testing your programs. library(plunit) under SWI
and SICStus 3.12 gives you a simple framework for that. Once
again, adopting such a framework requires significantly less work
than adding declarations to your program. Just start with some
top level test cases.
I believe that work in static analysis would be more profitable
to actual systems if it would consider such a setting.
Concerning the original poster, it seems that the following predicate
would have helped him in understanding some issues of nondeterminism
of Prolog implementations. determinate_call/1 is in some sense
comparable to once/1. However, while once/1 just cuts away alternatives,
determinate_call/1 issues an error informing you that the goal
in question leaves resource-consuming alternatives open.
Maybe there is a chance to agree on a name for it?
(Working in SICStus since 3.7, SWI since 5.6.38)
determinate_call(Goal) :-
call_cleanup(Goal, Det = true),
( Det == true
-> true
; throw(error(representation_error(nondeterminate(Goal)),_))
).
Tom Schrijvers
>My personal experience is that truly strict types and modes
>shift your attention away from your problem toward fighting the
>system or (in an academic setting) proposing extentions.
>
I think that the many strongly typed languages and their users show that
people can live quite happily with a type system. One would say that types
are the current state of the art. All major languages have types. Most new
languages not written by hackers, but academics have a type system. If
Prolog
hadn't been invented before type system became widely spread, then it
probably
would have types too.
//
>Sooner or later you have to figure out how to transfer data from one
>type "microcosmos" to another - and you will discover that
>"show"ing things as strings is the only way out thereby undermining
>the very intent of types (and at the same time introducing
>unnecessary strictness). Note also, that type systems as such do not
>prevent the creation of infinite data structures (Haskell: repeat 1).
>
>
There is an infinite number of bugs a type system won't catch. Without
types
you get at least twice as many bugs that are not caught. And I sure
don't see
a lot of Strings being passed around in Haskell.
>Still, it would be nice to be able to express in a portable manner
>certain assumptions that correspond to types and modes in Prolog.
>
>SWI's library(error) is a starting point. This library could
>be easily adopted by other systems. Why not focus optimizing
>analysis on removing must_be/2 goals? This looks to me more
>realistic than switching to declarations. You can step-by-step
>start to enter must_be/2 goals in your existing programs without
>any rewrite. And you can step-by-step remove those must_be/2 goals
>automatically with some analysis.
>
>
A lot of this is a matter of syntax, right? Your must_be/2
goal combines the type declarations and assertions of typed
languages. The nice thing about separating these is that you get
static guarantees from types. So if you're willing to write these
declarations
in a slightly different syntax than those other declarations, then you
can avoid all runtime overhead for them and get the static guarantee
that your program will not run into any type bugs.
My CHR compiler has its own type and mode declarations, and a static type
checker, because types are pretty useful for catching bugs and also
for optimized compilation. It should be pretty straightforward to extract
the type checking functionality into a separate library. Anyone
interested in
using that?
>No matter whether you use declarations or not there is no way
>around actually testing your programs. library(plunit) under SWI
>and SICStus 3.12 gives you a simple framework for that. Once
>again, adopting such a framework requires significantly less work
>than adding declarations to your program. Just start with some
>top level test cases.
>
>
Typed languages need testing too. Types even help in testing.
Have a look at the QuickCheck testing framework in Haskell.
Cheers,
Tom
Joachim Schimpf
This can actually happen with ECLiPSe's "bounded real" data type,
which captures the imprecision inherent in the float representation.
But I didn't want to stray too far from the topic...
-- Joachim
A.L.
<to...@cs.kuleuven.ac.be> wrote:
>U
>
>There is an infinite number of bugs a type system won't catch. Without
>types
>you get at least twice as many bugs that are not caught.
Right. We have a "legacy" application, written in Smalltalk, in years
1998 - 1997 and in production until 2004. This is rather big
application, close to million lines. In 2004 we stopped developing
actively, i.e. stopped adding new features. Since we had quite bit of
customers, application was actively maintained.
The number of bugs was consistently in the range of 20 a month, and
this number was steady until application was trashed 2 years ago
(including Smalltalk). The majority of these bugs were because server
was assuming some type and client was providing some other type.
The same application rewritten in Java (and, ehem.. Prolog :)
stabilized very quickly to about one bugs a month, and this number is
steadily decreasing. Moreover, these bugs have rather
structural/algorithmic nature than passing wrong data.
Generally, "type free" languages are not welcomed in the industry...
A.L.
Jan Wielemaker
> Jan Wielemaker wrote:
> [and then some fac/2 definitions]
>
> I like these versions of fac/2 a lot - not because they are so
> beautiful, but because they tell us where Prolog is bad, and how
> things could be improved.
<snip>
> Clearly not what one wants, and the origin is the same.
> But Jan has a preferred version as well:
>
> facjan_pref(N, I) :-
> must_be(nonneg, N),
> fac2(N, I).
>
> fac2(0, 1) :- !.
> fac2(N, X) :-
> N > 0, !,
> N1 is N - 1,
> fac2(N1, Y),
> X is N * Y.
>
> ?- facjan_pref(0,X).
>
> X = 1
> ?- facjan_pref(1-1,X).
> ERROR: Type error: `nonneg' expected, found `1-1'
> Exception: (11) throw(error(type_error(nonneg, 1-1), _G252)) ? creep
>
> So, facjan_pref is explicit: the N must be a number (and an int and not negative).
> In the other versions, there was no(t always) a need for that.
>
> I guess the cut after the N > 0 test in the last clause remained there
> because of cut&paste, so let's ignore it.
I feel a bit ashamed. Ok, the second cut is an obvious in-a-hurry
copy-and-paste error. The test however was not intended :-( I guess
I intended
fac2(0, X) :- !,
X = 1.
fac2(N, X) :-
N1 is N - 1,
fac2(N1, Y),
X is N * Y.
But having to write that I guess I prefer (keeping the must_be test in
front of it).
fac2(N, X) :-
( N > 0
-> N1 is N - 1,
fac2(N1, Y),
X is N * Y
; X = 1
).
The point I wanted to make is that one should not prefer if-then-else
over clauses for performance reasons, but of course there is still the
steadfastness.
> wouldn't the following be a better way to write fac/2:
>
> :- type facbartpref(nonnegint:in, int:out). % (*)
>
> facbartpref(0,1).
> facbartpref(N,Res) :-
> N \== 0,
> M is N - 1,
> facbartpref(M,Temp),
> Res is N * Temp.
>
> I have replaced the N > 0 by N \== 0. A decent compiler should be able
> to avoid choicepoints, and if statically, it cannot prove that
> facbartpref is called correctly, it can insert a minimal set of tests
> to ensure this.
I'm still in doubt. Surely, it helps producing quality and maintainable
code. SWI library(error) isn't really an alternative as Ulrich wants to
see it. It wasn't intended to be that. It came from the need to add
some sanity checks in some strategic places in your program and the fact
that I find typing something like this a bit of a nightmare:
throw(error(domain_error(my_domain, X), _))
I prefer typing:
domain_error(my_domain, X)
must_be(+Type, +Value) is a bit into the direction of a type system. It
came from the frustration that if you do a runtime type-check and have
to report an error this is just too much typing (instantiation error,
type error, domain error?). Second, I guess something like this is
always useful if you do not want to add a complete rigit type system to
Prolog (I certainly dont want that) and you need to type-check something
deep down a term.
Whether or not you want a type system is merely what users you aim for.
Type systems means more typing (of the sort you do with your fingers
:-). I think I'd be glad to have it at an interface (API) level, but I
generally wouldn't want it for the bulk of the implementation work. At
the API level (i.e. module exports) the burden of entering it is
compensated for by its documentation benefits. Having just types there
is generally enough to ensure that type errors don't go unnoticed for
too long (causing the program to say 'No'). I have long considered
allowing for something like this:
:- module(arithmetic,
[ fac(+nonneg, -integer)
]).
It clearly defines the interface. We can even add names:
:- module(animals,
[ cow(?Resource:atom)
]).
The good thing about this is that it is no burden at all, because often
I now write this:
:- module(animals,
[ cow/1 % ?Resource:atom
]).
I don't know how many types one needs to infer (most of) the rest.
Surely the Ciao people know, as the assertion framework does exactly
this.
Cheers --- Jan
tomena...@gmail.com
> allowing for something like this:
>
> :- module(arithmetic,
> [ fac(+nonneg, -integer)
> ]).
>
> It clearly defines the interface. We can even add names:
>
> :- module(animals,
> [ cow(?Resource:atom)
> ]).
>
> The good thing about this is that it is no burden at all, because often
> I now write this:
>
> :- module(animals,
> [ cow/1 % ?Resource:atom
> ]).
>
> I don't know how many types one needs to infer (most of) the rest.
> Surely the Ciao people know, as the assertion framework does exactly
> this.
It's a bit of a misconception that you have to type a lot with your
fingers to have types. Look at Haskell, Mercury and maybe Ciao too?
Usually it's possible to get by with only typing the type definitions
(which you don't do all that much once you've got a good set of
predefined ones). In Haskell you normally don't have to give type
declarations for any functions. I'd say that's pretty much having
types without typing many more characters :-) So I don't think the
extra character count is really valid. On the contrary, you're typing
more with your must_be declarations.
It is possible to do rapid prototyping in Haskell too, if that's what
you're afraid of. The type system isn't in the way. On the contrary,
more bugs are eliminated that way up front. I bet I could get one more
solution in the Prolog Programming Contest this way :-)
Tom
bart demoen
> Generally, "type free" languages are not welcomed in the industry...
I think that most people - whether from industry or academia - understand
this, and also know why industry wants types.
The question is why typed languages are not welcomed in academia ?
Or maybe I should be more specific, because typed languages are welcomed
in most academic circles, also in declarative programming circles, so:
WHY ARE TYPED LANGUAGES NOT WELCOMED IN LP-ACADEMIA ?
^^
But that is not a fair question either, because other LP languages
do embrace types, and even see them as necessaray (see e.g. ASP type of
languages).
The argument about having to "type a lot" (as in hitting the keyboard
often) is really no good: every declared type saves more keyboard strokes
than it required - even if the system has no type inference.
The argument that one can achieve a lot with the mustbe predicate ...
well yes, but as we say in flemmish: it is a plaster on a wooden leg.
Because mustbe cannot give guaranties. If you think it can - just consider
the fact that I can omit the mustbe checks. Saying it is the programmer's
fault, if (s)he doesn't put the checks, is like saying that - while not
enforcing driving at the right side of the road - it is the driver's fault
(s)he drove at the wrong side, when an accident occurs.
Programming without types is fine for people like Jan, Ulrich and ... (I'm
stuck, who else can I add to this list): they are disciplined people who
would of course never drive at the wrong side of the road intentionally,
but that is the key point: even they DO drive at the wrong side sometimes,
unintentionally, because they are human (I must confess I never do, but I
am an alien, or else I do it on purpose) and because programming is a
complicated game.
Now surely, I hate to comply to rules, just like any free minded European;
I hate to type the declarations and predicates, but I know it is good for
me, and for those who must use my software.
I hate to put on my safety belt in the car.
I hate to limit my speed.
I hate to be sober when I drive.
I hate to pay taxes.
I generally hate to do the right thing.
I hate people making me do things I hate, especially when they are right.
And I hate to admit this, but I know I should embrace those things I hate.
Not letting Prolog evolve into a typed language, is denying it survival.
Or rather, it is like signing its death certificate prematurely.
Cheers
Bart Demoen
A.L.
wrote:
>
>Not letting Prolog evolve into a typed language, is denying it survival.
>Or rather, it is like signing its death certificate prematurely.
>
Yes.
Actually, about 75% of my Prolog code is testing that data submitted
to Prolog predicate is correct - with pretty broad notion of
correctness - including some sort of "type checking". This comes from
Smalltalk era, when for each method we had to implement series of
assertions checking the "type" of arguments.
In Prolog case - if predicate fails, it must fail because the logic
says this, but not because data is not correct. If data is not
correct, Prolog must throw exception. But all these tests are "do this
myself". I would really prefer that some of these tests are done by
type system, compiler when possible, and runtime system, without my
intervention.
A.L.
Jan Wielemaker
> Programming without types is fine for people like Jan, Ulrich and ... (I'm
> stuck, who else can I add to this list): they are disciplined people who
> would of course never drive at the wrong side of the road intentionally,
> but that is the key point: even they DO drive at the wrong side sometimes,
> unintentionally, because they are human (I must confess I never do, but I
> am an alien, or else I do it on purpose) and because programming is a
> complicated game.
Well, I live in Amsterdam and ride my bicycle daily through the city
center. You should know better than calling me disciplined :-)
You forget the popularity of Perl, Javascript and doubtlessly many more
languages that are more popular than Prolog. I also know quite some
Prolog users and I think quite a few will move away from Prolog.
Learning them to use modules is already hard enough. Not to mention
getting them as far as writing some documentation and testing or even a
bit of pretty layout, so you can read the code. I carefully wrote PlDoc
to invite people to write a bit of documentation by making it easy for
them and rewarding them as much as I could. I am really happy to have
convinced one person (I will not name) and got him to write
documentation after 20 years of Prolog programming :-)
I think I am in favour of a type system, but not one that forces you to
define every argument type.
> Now surely, I hate to comply to rules, just like any free minded European;
> I hate to type the declarations and predicates, but I know it is good for
> me, and for those who must use my software.
>
> I hate to put on my safety belt in the car.
> I hate to limit my speed.
> I hate to be sober when I drive.
> I hate to pay taxes.
> I generally hate to do the right thing.
> I hate people making me do things I hate, especially when they are right.
> And I hate to admit this, but I know I should embrace those things I hate.
>
> Not letting Prolog evolve into a typed language, is denying it survival.
> Or rather, it is like signing its death certificate prematurely.
If someone writes a nice and simple type system that can support some
static analysis and (optionally) do source-code transformation to insert
runtime checks that can be easily ported to a number of Prolog systems,
you probably have your types quickly. I surely will consider adding it
to SWI-Prolog and I'm sure Vitor will add it to YAP, etc. If I had
twice as much time I would have done it long ago :-(
Cheers --- Jan
Jan Wielemaker
If you are willing to spend this much code on testing data and you have
25 Klines of code it might have been a better idea to spend some of
these 25 Klines of code on an even simple minded type system. Most
likely that would have made your code shorter. Even a simple minded
library as SWI-Prolog's error.pl (241 lines, including documentation and
the famous GNU header) probably would have made the overhead a lot
shorter.
75% of your code to things that is not the logic of the program is
simply unbearable as you cannot find the logic anymore. Its like
long comments in the middle of a predicate.
Its pretty simple to define term-expansion for :- type pred(arg1, ...).
and make it create wrappers for each predicate that has a type
declaration. The big advantage thereof is that its declarative nature
makes it a lot easier to do more with it and you can easily decide not
to generate the wrappers.
Below is a little wrapper generator I once wrote for
:- must_succeed
foo/1,
bar/2.
It should be easy to port to SICStus. Operators in SICStus are not
local to modules and subject to import/export, so you must define these
globally. *-> is if/3. I don't know whether SICStus has
prolog_load_context/2 (might, it was introduced by Quintus AFAIK).
Ok, this isn't about types, but just insert the famous must_be/2
for all typed arguments creates the wrapper you want.
Cheers --- Jan
================================================================
:- module(must_succeed,
[ op(1150, fx, must_succeed)
]).
:- multifile
user:term_expansion/2,
pred_must_succeed/2.
:- dynamic
user:term_expansion/2.
wrappers((A,B)) --> !,
wrappers(A),
wrappers(B).
wrappers(Name/Arity) -->
{ functor(Head, Name, Arity),
atom_concat(Name, '_', WrapName),
Head =.. [Name|Args],
WrappedHead =.. [WrapName|Args],
prolog_load_context(module, Module)
},
[ (must_succeed):pred_must_succeed(Head, Module),
( Head :- ( WrappedHead
*-> true
; throw(error(must_succeed(Head), _))
)
)
].
rename((Head :- Body), (NewHead :- Body)) :- !,
rename(Head, NewHead).
rename(Head, NewHead) :-
prolog_load_context(module, Module),
pred_must_succeed(Head, Module),
Head =.. [Name|Args],
atom_concat(Name, '_', WrapName),
NewHead =.. [WrapName|Args].
user:term_expansion((:- must_succeed(Preds)),
[ (:- multifile (must_succeed):pred_must_succeed/2)
| Clauses
]) :-
phrase(wrappers(Preds), Clauses).
user:term_expansion(Clause, NewClause) :-
rename(Clause, NewClause).
bart demoen
> Actually, about 75% of my Prolog code is testing that data submitted
> to Prolog predicate is correct
I am surprised by the large figure of 75%. I understand that some code is
needed to check correctness of calls across modules (say, calls to the
exported predicates), but I had expected this to account for the minority
of predicates and not need that much code. Why are my expectations wrong ?
> In Prolog case - if predicate fails, it must fail because the logic
> says this, but not because data is not correct.
I agree.
> If data is not
> correct, Prolog must throw exception.
But the programmer must still specify which data is correct, no ?
And what language should (s)he specify it in ? My point being: one can go
the CIAO way, and allow any general (Prolog) program to specify a "type",
or one can go the ADA, Haskell, Mercury ... way and stick to a more easily
decidable formalism to specify what is correct data.
The question is really: do we want better support from the language, or do
we stick with the old-fashioned, no-longer-in-vogue, unreliable, dangerous,
unacceptable-to-the-large-software-systems-developing-outside-world point
of view ?
The above question might come across as formulated in a biased way, but
no bias is intended: if anyone finds a more balanced (and at the same
time more realistic) way to express my thoughts, please post it.
Cheers
Bart Demoen
A.L.
wrote:
>
>
>If you are willing to spend this much code on testing data and you have
>25 Klines of code it might have been a better idea to spend some of
>these 25 Klines of code on an even simple minded type system. Most
>likely that would have made your code shorter. Even a simple minded
>library as SWI-Prolog's error.pl (241 lines, including documentation and
>the famous GNU header) probably would have made the overhead a lot
>shorter.
>
>75% of your code to things that is not the logic of the program is
>simply unbearable as you cannot find the logic anymore. Its like
>long comments in the middle of a predicate.
>
>Its pretty simple to define term-expansion for :- type pred(arg1, ...).
>and make it create wrappers for each predicate that has a type
>declaration. The big advantage thereof is that its declarative nature
>makes it a lot easier to do more with it and you can easily decide not
>to generate the wrappers.
Well, I didn't write that this 75% testing code is "dumb code" and
that I don't know how to make my life easier by developing small tools
and frameworks.
I don't remember what part of this overhead is something that is
actually treated by something similar to code that you attached (that
maybe could be tested by type system) and how much testing addresses
data correctness from business perspective (that has nothing common
with type system)
These 75% is nothing shocking and is in sync with Java. We do Test
Driven Development (TDD) where tests are written before code is
written, and actually these tests constitute documentation. The ratio
between testing code to functional code is about 50% to 75% and is
more or less industry standard.
The problem with prolog and constraint programming is associated with
the fact that from user's perspective "fail" is not enough - I have to
tell the user WHY there was a failure. This is not strictly testing
code, but actually if there is a failure I have to do a lot of
additional data analysis. Obviously, this part cannot be done by
compiler and type system...
A.L.
Cesar Rabak
concrete concept. . .
We already agree that stack overflow is not in the set of the "some things".
Jan Wielemaker
> wrote:
>
>>
>>
>>If you are willing to spend this much code on testing data and you have
>>25 Klines of code it might have been a better idea to spend some of
>>these 25 Klines of code on an even simple minded type system. Most
>>likely that would have made your code shorter. Even a simple minded
>>library as SWI-Prolog's error.pl (241 lines, including documentation and
>>the famous GNU header) probably would have made the overhead a lot
>>shorter.
>>
>>75% of your code to things that is not the logic of the program is
>>simply unbearable as you cannot find the logic anymore. Its like
>>long comments in the middle of a predicate.
I'm a bit lost now. Are we talking lines of source code or execution
time? First I though I misunderstood and it is time instead of lines,
but the remarks below on Java testing indicate it is lines, but it
includes testing code.
> The problem with prolog and constraint programming is associated with
> the fact that from user's perspective "fail" is not enough - I have to
> tell the user WHY there was a failure. This is not strictly testing
> code, but actually if there is a failure I have to do a lot of
> additional data analysis. Obviously, this part cannot be done by
> compiler and type system...
I think everybody agrees that an error is generally more appropriate
than a failure. Some work has been done to automate the process of
blaming some part of the code for the failure. I don't know if anything
of that is in active use these days though.
Cheers --- Jan
Bart Demoen
It's not too far from the topic we have moved to: your comment shows that
we need a type system :-)
Cheers
Bart Demoen
A.L.
wrote:
>
>I'm a bit lost now. Are we talking lines of source code or execution
>time? First I though I misunderstood and it is time instead of lines,
>but the remarks below on Java testing indicate it is lines, but it
>includes testing code.
>
testing (that is done by writing EXTERNAL tests using framework that I
call pUnit, as analogy to jUnit and I had to write myself). I don't
count this code.
The other testing is a) sort of a testing that could be done by type
system, and this is analogy to my former Smalltalk
"must_be_instance_of" assertions. I must be getting list when I expect
a list, and structure of this list must be as it is expected, b) data
integrity test that type system would not do (like time of effect of
some action cannot precede time of cause of this action)
This 75% does not cover pUnits, pUnit tests is additional XXXX lines
of code.
All this testing is necessary since: a) System is large and developed
in pieces as collection of modules. It takes time. Sometimes I myself
don't remember exactly what is specification of a module and do stupid
mistakes, b) Prolog queries are constructed in Java and delivered to
Prolog using PrologBeans. Constructing these queries in Java can be
screwed up, and I prefer to be sure that (especially during
development) it is carefully checked that Prolog gets from Java what
it should get. For the same reason, there is extensive logging of all
Prolog actions.
Of course, this is huge overhead, and there is an option to switch
both testing and logging off.
>> The problem with prolog and constraint programming is associated with
>> the fact that from user's perspective "fail" is not enough - I have to
>> tell the user WHY there was a failure. This is not strictly testing
>> code, but actually if there is a failure I have to do a lot of
>> additional data analysis. Obviously, this part cannot be done by
>> compiler and type system...
>
>I think everybody agrees that an error is generally more appropriate
>than a failure. Some work has been done to automate the process of
>blaming some part of the code for the failure. I don't know if anything
>of that is in active use these days though.
>
This what I would really need is some sort of "explanation module" for
constraint system. Something is being done in this area, but it is far
from being production ready.
A.L.
Jan Wielemaker
> On 08 Feb 2008 08:18:47 GMT, Jan Wielemaker <j...@nospam.ct.xs4all.nl>
> wrote:
>
>>
>>I'm a bit lost now. Are we talking lines of source code or execution
>>time? First I though I misunderstood and it is time instead of lines,
>>but the remarks below on Java testing indicate it is lines, but it
>>includes testing code.
>>
> I messed up. There are two types of testing that I am doing: unit
> testing (that is done by writing EXTERNAL tests using framework that I
> call pUnit, as analogy to jUnit and I had to write myself). I don't
> count this code.
>
> The other testing is a) sort of a testing that could be done by type
> system, and this is analogy to my former Smalltalk
> "must_be_instance_of" assertions. I must be getting list when I expect
> a list, and structure of this list must be as it is expected, b) data
> integrity test that type system would not do (like time of effect of
> some action cannot precede time of cause of this action)
>
> This 75% does not cover pUnits, pUnit tests is additional XXXX lines
> of code.
So my first reading was correct after all. There is 75% characters
(or lines) of the source code that does not add to the logic but is
merely there to validate assumptions? That is really huge.
Ok, Prolog source is overall so much shorter that the total amount of
code and readability might still not be bad ...
What is interesting now is how much of the 75% could be replaced by a
type system and how much lines are needed for the declarations that
replace these tests.
Cheers --- Jan
fodor...@gmail.com
> people can live quite happily with a type system. One would say that types
> are the current state of the art. All major languages have types. Most new
> languages not written by hackers, but academics have a type system. If
> Prolog hadn't been invented before type system became widely spread, then it
> probably would have types too.
Some LP systems have types. For instance, Flora2 has types equivalent
to those from the XML Schema, you can declare your own types
(classes), check the static type constraints, use IRIs etc.
Regards,
Paul .
Ulrich Neumerkel
>A lot of this is a matter of syntax, right? Your must_be/2
>goal combines the type declarations and assertions of typed
>languages. The nice thing about separating these is that you get
>static guarantees from types. So if you're willing to write these declarations
>in a slightly different syntax than those other declarations, then you
>can avoid all runtime overhead for them and get the static guarantee
>that your program will not run into any type bugs.
It seems your focus is on writing new programs, whereas my focus
is more on existing programs. Sometimes, writing programs from
scratch is not an option. But still I would like to have some
guarantees.
tomena...@gmail.com
> is more on existing programs. Sometimes, writing programs from
> scratch is not an option. But still I would like to have some
> guarantees.
The type checker library I posted supports both worlds. It checks only
predicates with type declarations, and inside ignores all calls to
predicates
without declarations. This way you can still use all your existing
code, and
get benefits from the type checker on any new code you write. Also, of
course,
you can add type declarations to your old code. Would that approach be
useful
for your situation?
Tom
Ulrich Neumerkel
What happens with the unchecked parts? Are the assumptions
checked dynamically when passing from unchecked code to checked
code? In general: What dynamic properties can you guarantee? This
question may seem odd to you, after all the notion of types has
been so long with us. But type checking seems to have many
different interpretations. Sometimes meaning finding some not all
errors (related to typing).
Just because TCLP has been mentioned in another thread:
http://www710.univ-lyon1.fr/~ecoquery/tclp/exemples/append.html
modified to
append([],L,L) :- L = a.
append([X|L],L2,[X|R]) :- append(L,L2,R).
results in
:- typeof append(list(A),list(A),list(A)) is pred.
which goes against my expectation.
Bart Demoen
>>The type checker library I posted supports both worlds. It checks only
>>predicates with type declarations, and inside ignores all calls to predicates
>>without declarations. This way you can still use all your existing code, and
>>get benefits from the type checker on any new code you write. Also, of course,
>>you can add type declarations to your old code. Would that approach be useful
>>for your situation?
>
>
> What happens with the unchecked parts? Are the assumptions
> checked dynamically when passing from unchecked code to checked
> code? In general: What dynamic properties can you guarantee? This
> question may seem odd to you
It is not an odd question, but you can't expect that there are very precise
and detailed answers for the current prototype.
I guess the aim is that if the program has all types declared, and the predicates
are typed according to them, and the program passes the type checker, then the
program "will not go wrong".
If you leave certain parts undeclared, you can't have that guarantee, but we might
work towards "some" guarantee. In any case, it is better to know that
if I call this predicate correctly, it will not go wrong, than to know nothing
of that sort, even if I don't have the same guarantee for other predicates.
But given the current stage of the "typed Prolog project", it would be productive
if you told comp.lang.prolog what would you like to happen to
unchecked parts and the passing from unchecked to checked ?
Cheers
Bart Demoen
Peter Schachte
> Still, it would be nice to be able to express in a portable manner
> certain assumptions that correspond to types and modes in Prolog.
>
> SWI's library(error) is a starting point. This library could
> be easily adopted by other systems. Why not focus optimizing
> analysis on removing must_be/2 goals? This looks to me more
> realistic than switching to declarations.
These don't have the same expressiveness. Type declarations are declarative
and mode-independent, whereas must_be/2 goals are procedural and
mode-specific. You can't just use must_be/2 on the arguments of a predicate
that is meant to work in multiple modes, you have to split the var and nonvar
cases first, whereas a type declaration just says that if the argument is
ever bound, it must have a certain type.
Besides, if people complain about the "visual noise" of type declarations,
they'll never put up with must_be goals, which get buried in the running
code, and tend to force you to create a single clause driver predicate to do
the testing and then call the multi-clause predicate to do the real work (or
else repeat the must_be goals in every clause).
--
Peter Schachte The spirit of democracy cannot be imposed from
scha...@cs.mu.OZ.AU without. It has to come from within.
www.cs.mu.oz.au/~schachte/ -- Mahatma Gandhi
Phone: +61 3 8344 1338
Peter Schachte
> Type systems means more typing (of the sort you do with your fingers
> :-). I think I'd be glad to have it at an interface (API) level, but I
> generally wouldn't want it for the bulk of the implementation work. At
> the API level (i.e. module exports) the burden of entering it is
> compensated for by its documentation benefits. Having just types there
> is generally enough to ensure that type errors don't go unnoticed for
> too long (causing the program to say 'No'). I have long considered
> allowing for something like this:
>
> :- module(arithmetic,
> [ fac(+nonneg, -integer)
> ]).
This looks really intuitive to me. You already have to give predicate names
and arities for exported predicates; just throwing in the types is good
documentation for little extra work. If the compiler also Hindley-Miller
type-checked the whole module based on those declarations (and some :- type
declarations given in the module), I can't see why anyone who would bother to
use modules wouldn't also bother to include types.
The tricky thing to handle, though, would be the general term-handling
predicates like functor/3, arg/3 and univ. What type would you give a
predicate like this?
append_terms(T, U, V) :-
append(Targs,Uargs,Vargs),
T =.. [F|Targs],
U =.. [F|Uargs],
V =.. [F|Vargs].
You'll need some kind of universal top type. This might really reduce the
effectiveness of the type checker.
That said, I don't see how can you check the 'nonneg' type. Would this
predicate type-check successfully (with or without any conceivable
declaration for test/3)?
test(X, Y, Z):-
I is X - Y,
fac(I, Z).
Ulrich Neumerkel
Bart Demoen <b...@cs.kuleuven.ac.be> writes:
>I guess the aim is that if the program has all types declared, and the predicates
>are typed according to them, and the program passes the type checker, then the
>program "will not go wrong".
I would expect something a little bit more concrete. Which concrete
dynamic checks could I assume to be true? Is it guaranteed for an
argument being of type list that must_be(list_or_partial_list, L)
always succeeds or must_be(list,L) never issues a type error?
>If you leave certain parts undeclared, you can't have that guarantee, but we might
>work towards "some" guarantee. In any case, it is better to know that
>if I call this predicate correctly, it will not go wrong, than to know nothing
>of that sort, even if I don't have the same guarantee for other predicates.
In any bigger system there are always unchecked parts. And that is
not only user code; take SWI's BIPs & libs. It will take a lot of
time to have all of them checked. Some of them (like =../2,
atom_to_term/3) may never be (statically) checkable. Therefore, a
clean type safe method of embedding unchecked code is needed. Calls
to unchecked code have to be decorated explicitly indicating the
dynamic tests required, the actual tests being proposed by the type
checker. This manifests clearly in the source text that some runtime
overhead is to be expected and at the same time motivates to remove it
by enlarging the type safe parts. But also the other side needs
similar checks: i.e. calling safe code from unsafe - if one prefers to
do that safely.
Consider just the alternative: ignoring the unchecked goals. While
this seems to be the accepted default method, it means that you are
analysing a different program - the program without those goals. But
if I would be interested in that program I would have written it in
the first place.
>But given the current stage of the "typed Prolog project", it would be productive
>if you told comp.lang.prolog what would you like to happen to
>unchecked parts and the passing from unchecked to checked ?
How do you compare to Mycroft-O'Keefe?
Ulrich Neumerkel
>The tricky thing to handle, though, would be the general term-handling
>predicates like functor/3, arg/3 and univ. What type would you give a
>predicate like this?
>
> append_terms(T, U, V) :-
> append(Targs,Uargs,Vargs),
> T =.. [F|Targs],
> U =.. [F|Uargs],
> V =.. [F|Vargs].
>
>You'll need some kind of universal top type. This might really reduce the
>effectiveness of the type checker.
The best seems to not type check such code at all (apart
from it being nonterminating), but to resume checking
(with dynamic checks) probably at the point where
append_terms/3 is called - or even somewhere above.
Ulrich Neumerkel
>Ulrich Neumerkel wrote:
>> Still, it would be nice to be able to express in a portable manner
>> certain assumptions that correspond to types and modes in Prolog.
>>
>> SWI's library(error) is a starting point. This library could
>> be easily adopted by other systems. Why not focus optimizing
>> analysis on removing must_be/2 goals? This looks to me more
>> realistic than switching to declarations.
>
>These don't have the same expressiveness. Type declarations are declarative
>and mode-independent, whereas must_be/2 goals are procedural and
>mode-specific. You can't just use must_be/2 on the arguments of a predicate
>that is meant to work in multiple modes, you have to split the var and nonvar
>cases first, whereas a type declaration just says that if the argument is
>ever bound, it must have a certain type.
Certainly I agree that they do not have the same expressiveness.
Not that I ever claimed that. Note that must_be/2 clearly distinguishes
between instantiation errors and type errors. Would you claim that
those type errors are procedural too? In some sense they are, when
a different selection results in failure.
>Besides, if people complain about the "visual noise" of type declarations,
>they'll never put up with must_be goals, which get buried in the running
>code, and tend to force you to create a single clause driver predicate to do
>the testing and then call the multi-clause predicate to do the real work (or
>else repeat the must_be goals in every clause).
To whom do you refer by people?
Jan adopted must_be/2 in SWI after some discussion with major
input from Richard O'Keefe. It was never meant as an all encompassing
replacement for type systems. But at least it produces real guarantees
dynamically. Exactly the thing missing in current type systems.
If an argument has type list(_) and [_|a] is an answer (see some
postings above), there is good reason to complain.
If declarations would lead to actual guarantees that can be tested/relied
upon dynamically, things would be different. Up to now, I have not
seen such a system for Prolog. In Mercury, strong guarantees are produced.
What would be desirable is something more flexible and less moded.
Peter Schachte
> Peter Schachte <scha...@cs.mu.oz.au> writes:
>> Ulrich Neumerkel wrote:
>>> This library could
>>> be easily adopted by other systems. Why not focus optimizing
>>> analysis on removing must_be/2 goals?
>> These don't have the same expressiveness. Type declarations are declarative
>> and mode-independent, whereas must_be/2 goals are procedural and
>> mode-specific.
> Certainly I agree that they do not have the same expressiveness.
> Not that I ever claimed that. Note that must_be/2 clearly distinguishes
> between instantiation errors and type errors. Would you claim that
> those type errors are procedural too?
Perhaps "procedural" vs. "declarative" isn't the right distinction. I just
mean that must_be/2 doesn't tend to work very well for predicates meant to
work in multiple modes (unless they already have separate code for the
different modes).
>> Besides, if people complain about the "visual noise" of type declarations,
>> they'll never put up with must_be goals, which get buried in the running
>> code
> To whom do you refer by people?
The many people who can't bear the thought of putting type declarations in
their Prolog code.
> Jan adopted must_be/2 in SWI after some discussion with major
> input from Richard O'Keefe. It was never meant as an all encompassing
> replacement for type systems. But at least it produces real guarantees
> dynamically. Exactly the thing missing in current type systems.
Type systems do give strong guarantees for languages like Haskell and
Mercury. But bolting a Haskell-style type system onto an existing typeless
language like Prolog would not be painless (otherwise we'd all be using the
Mycroft-O'Keefe type system already).
> If declarations would lead to actual guarantees that can be tested/relied
> upon dynamically, things would be different. Up to now, I have not
> seen such a system for Prolog. In Mercury, strong guarantees are produced.
> What would be desirable is something more flexible and less moded.
Mercury's type system works independently of its modes (Ie, Prolog could use
its type system without it's mode system), and, as you say, does give
reliable guarantees. OTOH, a Prolog program would probably make more use of
Mercury's universal type than a Mercury program, and Mercury requires
explicit casts between proper types and the universal type. I doubt many
Prolog programmers would put up with that.
--
Peter Schachte He that would make his own liberty secure must
scha...@cs.mu.OZ.AU guard even his enemy from oppression.
www.cs.mu.oz.au/~schachte/ -- Thomas Paine