problem with stack 
Author Message
 problem with stack

I would like to use this predicate :

conc3(X,Y,Z,T):-append(X,Y,U),append(U,Z,T).

but when I test it, I have a problem of stack :

?- conc3(X,Y,Z,[1]).

X = []
Y = []
Z = [1] ;

X = []
Y = [1]
Z = [] ;

X = [1]
Y = []
Z = [] ;
ERROR: Out of global stack

I don't arrive to change the size of stacks.

Could you help me please.

Thanks

maga



Wed, 15 Jun 2005 06:32:41 GMT  
 problem with stack

Quote:

> I would like to use this predicate :

> conc3(X,Y,Z,T):-append(X,Y,U),append(U,Z,T).

> but when I test it, I have a problem of stack :

> ?- conc3(X,Y,Z,[1]).

> X = []
> Y = []
> Z = [1] ;

> X = []
> Y = [1]
> Z = [] ;

> X = [1]
> Y = []
> Z = [] ;
> ERROR: Out of global stack

> I don't arrive to change the size of stacks.

The problem results from the first append, if all the arguments
are free it always succeeds...

?- append(X,Y,Z).
X = []
Y = _G161
Z = _G161 ;
X = [_G242]
Y = _G161
Z = [_G242|_G161] ;
X = [_G242, _G248]
Y = _G161
Z = [_G242, _G248|_G161] ;
...
So when the second append fails, it backtracks to the first which succeeds, goes on to the second which fails...

It can be reordered to accept your query

conc3(X,Y,Z,T):-append(U,Z,T),append(X,Y,U).

?- conc3(X,Y,Z,[1]).

X = []
Y = []
Z = [1] ;

X = []
Y = [1]
Z = [] ;

X = [1]
Y = []
Z = [] ;

No
?-

But...

?- conc3([1],[2],Y,Z).

Y = _G168
Z = [1, 2|_G168] ;
ERROR: (user://2:126):
        Out of global stack

--
Geoff



Wed, 15 Jun 2005 13:45:06 GMT  
 problem with stack
Hi.

Quote:

> I would like to use this predicate :
> conc3(X,Y,Z,T):-append(X,Y,U),append(U,Z,T).
> ?- conc3(X,Y,Z,[1]).

Of course,
 conc3(X,Y,Z,T) :- append(U,Z,T),append(X,Y,U).
is working.

| ?- conc3(X,Y,Z,[1]).
X = [], Y = [], Z = [1] ? ;
X = [], Y = [1], Z = [] ? ;
X = [1], Y = [], Z = [] ? ;
no


Quote:
>  Consider the following definition of 'app/3':
>   app([],L,L).
>   app([X|L1],L2,L3) :- app(L1,L2,L3).

Of course, this is wrong, but If you have,
   app([X|L1],L2,L3) :- app(L1,L2,L3).
   app([],L,L).
simple question like
   ?-app(X,[a],Y).
will give you the same of error of mega's conc3.

Quote:
>  In general, you cannot design a Prolog predicate to work in
>(i,i,...,i,o) mode and expect it will necessarily work in (o,o,...,o,i)
>mode.

It is possible using some non logical predicate or some extra normal
predicate, but it is not useful to do that, because it is easier to
prepare different version of predicates for different i/o modes.

---

              PRESTO, Japan Science and Technology Corporation



Wed, 15 Jun 2005 16:16:47 GMT  
 problem with stack
Thanks for your help.

I've understood my error and my predicate which uses conc3 works well now.



Quote:
> Hi.


> > I would like to use this predicate :
> > conc3(X,Y,Z,T):-append(X,Y,U),append(U,Z,T).
> > ?- conc3(X,Y,Z,[1]).

> Of course,
>  conc3(X,Y,Z,T) :- append(U,Z,T),append(X,Y,U).
> is working.

> | ?- conc3(X,Y,Z,[1]).
> X = [], Y = [], Z = [1] ? ;
> X = [], Y = [1], Z = [] ? ;
> X = [1], Y = [], Z = [] ? ;
> no




- Show quoted text -

Quote:
> >  Consider the following definition of 'app/3':
> >   app([],L,L).
> >   app([X|L1],L2,L3) :- app(L1,L2,L3).

> Of course, this is wrong, but If you have,
>    app([X|L1],L2,L3) :- app(L1,L2,L3).
>    app([],L,L).
> simple question like
>    ?-app(X,[a],Y).
> will give you the same of error of mega's conc3.

> >  In general, you cannot design a Prolog predicate to work in
> >(i,i,...,i,o) mode and expect it will necessarily work in (o,o,...,o,i)
> >mode.

> It is possible using some non logical predicate or some extra normal
> predicate, but it is not useful to do that, because it is easier to
> prepare different version of predicates for different i/o modes.

> ---

>               PRESTO, Japan Science and Technology Corporation



Wed, 15 Jun 2005 22:55:04 GMT  
 problem with stack

Quote:

> Hi.


>>I would like to use this predicate :
>>conc3(X,Y,Z,T):-append(X,Y,U),append(U,Z,T).
>>?- conc3(X,Y,Z,[1]).

> Of course,
>  conc3(X,Y,Z,T) :- append(U,Z,T),append(X,Y,U).
> is working.

> | ?- conc3(X,Y,Z,[1]).
> X = [], Y = [], Z = [1] ? ;
> X = [], Y = [1], Z = [] ? ;
> X = [1], Y = [], Z = [] ? ;
> no

   Hmm.

   ?- conc3([1],[2],[3],L).
   L = [1,2,3] ;
   ERROR: Out of global stack.

Quote:

>> Consider the following definition of 'app/3':
>>  app([],L,L).
>>  app([X|L1],L2,L3) :- app(L1,L2,L3).

> Of course, this is wrong,

   Of course, I meant to say

   app([],L,L).
   app([X|L1],L2,[X|L3]) :- app(L1,L2,L3).

Quote:
> but if you have,
>    app([X|L1],L2,L3) :- app(L1,L2,L3).
>    app([],L,L).
> simple question like
>    ?-app(X,[a],Y).
> will give you the same of error of maga's conc3.

   I don't get your drift.

   If you have

      p([X|L]) :- p(X).

then

      ?- p(Q).

will give you the same error that maga's 'conc3/4'
gave for the query

      ?- conc3(X,Y,Z,[1]).

and I am sure there are many similar examples.

   The question is, /why/ does the stack overflow?

   I think the answer is that the given query and the
given rules force the P.I.E. into an infinite loop
that causes it to insert a monotonically increasing
number of variable bindings into the evironment, and
by simulating the unification (inference) process by hand,
I tried to show exactly how that comes about.

   But the conclusion I reached does not depend on the mistake
I made in 'app/3', because if I revise the argument I presented,
using the new (corrected) definition of 'app/3', I come to the same
conclusion, so I still think my theory is essentially correct.

Quote:
>> In general, you cannot design a Prolog predicate to work in
>>(i,i,...,i,o) mode and expect it will necessarily work in (o,o,...,o,i)
>>mode.

> It is possible using some non logical predicate or some extra normal
> predicate, but it is not useful to do that, because it is easier to
> prepare different version of predicates for different i/o modes.

   That is the alternative.

   The fact remains, you can't design a Prolog predicate to work in
(i,i,...,i,o) mode and always expect it to work in (o,o,...,o,i) mode.

   And, of course, it is not always necessary to resort to non-logical
trickery to make a Prolog predicate "work both ways". For example, if I
am not mistaken,

   conc3([],L2,L3,L) :-
     app(L2,L3,L).
   conc3([X|L1],L2,L3,[X|L]) :-
     conc3(L1,L2,L3,L).

seems to work nicely every which way.

Quote:
> ---

>               PRESTO, Japan Science and Technology Corporation

--
Bill
http://www.sonic.net/~sequitur


Thu, 16 Jun 2005 12:37:18 GMT  
 problem with stack

Quote:

> I would like to use this predicate :

> conc3(X,Y,Z,T):-append(X,Y,U),append(U,Z,T).

> but when I test it, I have a problem of stack :

> ?- conc3(X,Y,Z,[1]).

> X = []
> Y = []
> Z = [1] ;

> X = []
> Y = [1]
> Z = [] ;

> X = [1]
> Y = []
> Z = [] ;
> ERROR: Out of global stack

> I don't arrive to change the size of stacks.

> Could you help me please.

> Thanks

> maga

  Here's what I think is happening.

  Consider the following definition of 'app/3':

   app([],L,L).
   app([X|L1],L2,[X|L3]) :- app(L1,L2,L3).

and think in terms of givens (i-mode) and unknowns (o-mode).

  Let x-mode mean either i-mode or o-mode.

  When the query

     ?- conc3(X,Y,Z,[1]). % (o,o,o,i)

is matched to the head of the rule

     conc3(V1,V2,V3,V4):- app(V1,V2,V5),app(V5,V3,V4).

the rule instantiates to

     conc3(X,Y,Z,[1]) :- app(X,Y,V5), app(V5,Z,[1]).

and the question becomes

(A)  ?- app(X,Y,V5), app(V5,Z,[1]).  % (o,o,o), (i,o,i)

  Note that here the first call to 'app/3' has mode (o,o,o): U' is an
introduced variable, so it's first occurrence has to receive a value,
after which subsequent occurrences of the same variable are in input mode.

  When

     app(X,Y,V5)

is matched to the head of the rule

     app([V6|V7],V8,[V6|V9]) :- app(V7,V8,V9).

the rule instantiates to

     app([V6|V7],Y,[V6|V9]) :- app(V7,Y,V9).

with X -> [V6|V7] and V5 -> [V6|V9],

and question changes from

(A)  ?- app(X,Y,V5), app(V5,Z,[1]).  % (o,o,o), (i,o,i)

to

(B)  ?- app(V7,Y,V9), app([V6|V9],Z,[1]). % (o,o,o), (i,o,i)

When

     app(V7,Y,V9)

is matched to the head of the rule

     app([V10|V11],V12,[V10|V13]) :- app(V11,V12,V13).

the rule instantiates to

     app([V10|V11],Y,[V10|V13]) :- app(V11,Y,V13)

with V7 -> [V10|V11] and V9 -> [V10|V13],

and the question changes from

(B)  ?- app(V7,Y,V9), app([V6|V9],Z,[1]). % (o,o,o), (i,o,i)

to

(C) ?- app(V11,Y,V13), app([V6|[V10|V13],Z,[1]). % (o,o,o),(i,o.i)

  Clearly, at this rate, the second part of the question will never be
reached, but each time around the loop two new bindings will be pushed
onto the environment stack, so eventually you will run out of
environment space.

  In general, you cannot design a Prolog predicate to work in
(i,i,...,i,o) mode and expect it will necessarily work in (o,o,...,o,i)
mode.

--
http://www.sonic.net/~sequituir



Sat, 18 Jun 2005 02:44:33 GMT  
 problem with stack

Quote:


>> I would like to use this predicate :

>> conc3(X,Y,Z,T):-append(X,Y,U),append(U,Z,T).

>> but when I test it, I have a problem of stack :

>> ?- conc3(X,Y,Z,[1]).

>> X = []
>> Y = []
>> Z = [1] ;

>> X = []
>> Y = [1]
>> Z = [] ;

>> X = [1]
>> Y = []
>> Z = [] ;
>> ERROR: Out of global stack

>> I don't arrive to change the size of stacks.

>> Could you help me please.

>> Thanks

>> maga

$doc "conc3.pl"
/*
app([],L,L).
app([X|L1],L2,[X|L3]) :-
        app(L1,L2,L3).
*/

/*
              Note
              ~~~~
For the purposes of this demo, the base <rule>

<rule>;  this is contrary to good practice, but it
makes the essential  point of this demo -- which is,
to show why the query


causes a global stack overfow -- much easier to see;
if the <rule>s are reversed, a global stack overflow
still occurs, but the $trace output then becomes much
too cluttered to make any sense out of.

*/




$end_para
/*
iiio_conc3(X,Y,Z,T):-app(X,Y,U),app(U,Z,T).
*/



$end_para
/*
oooi_conc3(X,Y,Z,T) :- app(U,Z,T),app(X,Y,U).
*/



$end_para
/*
p([X|L]) :- p(X).
*/



$end_para
/*
conc3([],L2,L3,L) :-
        app(L2,L3,L).
conc3([X|L1],L2,L3,[X|L]) :-
        conc3(L1,L2,L3,L).
*/






$end_para

$end_doc


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\__ this is the query

Searching...





~4->[1], ~3->Z, ~2->Y, ~1->X






~5->[~6|~9], ~8->Y, X->[~6|~7]





~9->[~10|~13], ~12->Y, ~7->[~10|~11]





~13->[~14|~17], ~16->Y, ~11->[~14|~15]





~17->[~18|~21], ~20->Y, ~15->[~18|~19]





~21->[~22|~25], ~24->Y, ~19->[~22|~23]





~25->[~26|~29], ~28->Y, ~23->[~26|~27]





~29->[~30|~33], ~32->Y, ~27->[~30|~31]





~33->[~34|~37], ~36->Y, ~31->[~34|~35]





~37->[~38|~41], ~40->Y, ~35->[~38|~39]





~41->[~42|~45], ~44->Y, ~39->[~42|~43]





~45->[~46|~49], ~48->Y, ~43->[~46|~47]





~49->[~50|~53], ~52->Y, ~47->[~50|~51]





~53->[~54|~57], ~56->Y, ~51->[~54|~55]





~57->[~58|~61], ~60->Y, ~55->[~58|~59]





~61->[~62|~65], ~64->Y, ~59->[~62|~63]





~65->[~66|~69], ~68->Y, ~63->[~66|~67]





~69->[~70|~73], ~72->Y, ~67->[~70|~71]





~73->[~74|~77], ~76->Y, ~71->[~74|~75]





~77->[~78|~81], ~80->Y, ~75->[~78|~79]





~81->[~82|~85], ~84->Y, ~79->[~82|~83]





~85->[~86|~89], ~88->Y, ~83->[~86|~87]





~89->[~90|~93], ~92->Y, ~87->[~90|~91]





~93->[~94|~97], ~96->Y, ~91->[~94|~95]





~97->[~98|~101], ~100->Y, ~95->[~98|~99]





~101->[~102|~105], ~104->Y, ~99->[~102|~103]





~105->[~106|~109], ~108->Y, ~103->[~106|~107]





~109->[~110|~113], ~112->Y, ~107->[~110|~111]





~113->[~114|~117], ~116->Y, ~111->[~114|~115]





~117->[~118|~121], ~120->Y, ~115->[~118|~119]





~121->[~122|~125], ~124->Y, ~119->[~122|~123]





~125->[~126|~129], ~128->Y, ~123->[~126|~127]





~129->[~130|~133], ~132->Y, ~127->[~130|~131]





~133->[~134|~137], ~136->Y, ~131->[~134|~135]





<trap_get>

Interrupt!

1010 Stack overflow

<question> canceled.

--
http://www.sonic.net/~sequitur



Sat, 18 Jun 2005 11:55:50 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Odd Problem with Stack Space and S87

2. problems with stack

3. problem with stack..

4. Maximizing register usage: problems with stack?

5. problems with stack management for large runs on beowulf cluster using intel fortran compiler 8.1.024

6. Array size problem non stack related

7. Stack overflow problem but increasing stack size does not solve the problem

8. Regex, stack overflow, and adjusting stack size

9. Addressable Stacks and optimizations (was: Addressable Stacks?)

10. Addressable Stacks and optimizations (was: Addressable Stacks?)

11. stacking stacks of database info.....

12. Allocating on the stack and *only* on the stack

 

 
Powered by phpBB® Forum Software