dcgoricanec@watnot.UUCP (dcgoricanec) (03/18/86)
<chomp>
hello world .
Examine the following :
rubik_cube([],New_perm) :- write(New_perm),!.
rubik_cube([H|T],New_perm) :-
move_generator(H,New_perm,Newer_perm),
rubik_cube(T,Newer_perm).
This predicate is invoked by a list of cube moves such as
rubik_cube([u,r2,l,r2],Resultant_perm)?
Fine. I can submit a list of 25 such moves to a program on my ibm-xt with
512k running plvp+ but 26 moves causes a stack overflow.I would like
225 moves in my list ...
(Incidentally, the trace of 25 moves is truly impressive,filling the
80 col screen for 10 minutes.)
My question to the net is : Since this program is list-driven and only
recurses to split the list, how can I kill the thousands of
instantiations cluttering the stack when I move on to the next list element?
(ie. kind of like a cut but instead of inhibiting backtracking,
I want to inhibit recursive memory of past events)
Currently my program is 15k long and can solve u-face efficiently by using
the tables published by Singmaster. Generalization to the whole cube group
is trivial once I get prolog to handle a big list splitting.
Thistlewaite's algorithm will likely be the next predicate,graphics too...dep@allegra.UUCP (Dewayne Perry) (03/19/86)
<> I had a similar problem. I have written a prolog program to explore the problems of creating and maintaining a very large data base (using my record collection of 1500 records as an example, with full information about composers, peerformers, and pieces performed). With about one quarter of the records entered I encountered the stack overflow problem and started extending the stacks and other data structures. But of course as the data base goot bigger, the stacks had to be enlarged as well - a rather hopeless task. My solution to the problem is as follows (using the side-effect aspects of prolog): I had a main program something like getlist(L1), sort(L1,L2), putindb(L2), processdblist, ... the putindb goes like this: putindb([]). putindb([H|T]) :- assert( something(H) ), or maybe assertz putindb(T), !. then processdblist is processdblist :- something(H) # process(H), fail, processdblist. the database has things in the order desired and you process each member of the original list in the desired order. The # operator means "succeed only once - unbind on backtracking" (a very nice operator to bring a bit of sanity to loops in prolog). The stack problem has gone away because you dont hve to keep all the previous environments around in case you unwind to them while backtracking. Dewayne