Article: 15104 of comp.lang.forth
Path: news.tuwien.ac.at!mips.complang.tuwien.ac.at!anton
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth
Subject: Re: Stack manipulations (about 100 lines)
Date: 30 Mar 1995 15:58:56 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 84
Distribution: world
Message-ID: <3lekg0$3bp@news.tuwien.ac.at>
References: <3l60lh$s8j@ixnews4.ix.netcom.com>
NNTP-Posting-Host: mips.complang.tuwien.ac.at

On a related note, some time ago I wrote a short Prolog program that
finds the shortest stack manipulation sequences for a given stack
effect. Or, alternatively, the shortest sequences equivalent to a
specific sequence.

E.g., to find sequences reversing the top three stack items, I can
make the query:

| ?- findbest(X,[1,2,3],[],[3,2,1],[]).

X = [swap,rot] ? ;

X = [rot,rot,swap] ? ;

X = [tuck,drop,rot] ? 

yes


What I typed in was "findbest(X,[1,2,3],[],[3,2,1],[])." and the
";"s. This query asks for lists X of stack manipulation words that
have the data stack effect ( 3 2 1 -- 1 2 3 ) and the return stack
effect ( -- ). Note that the top stack items are leftmost in Prologs
list, in contrast to Forth (i.e. ( a b ) corresponds to [b,a]). The
Prolog system produced solutions, strarting with the shortest one,
"swap rot"; I asked for two more solutions using ";", then hit return
to ignore the other solutions.

Similarly, one can ask for the best sequence equivalent to a given
one:

| ?- find([nip,over,tuck,drop],[1,2,3,4],[],X,[]),findbest(L,[1,2,3,4],[],X,[]).

L = [nip,over,swap],
X = [1,3,3,4] ? ;

L = [swap,drop,over,swap],
X = [1,3,3,4] ? ;

L = ['>r',drop,dup,'r>'],
X = [1,3,3,4] ? ;
...


Here, I first asked for the data stack effect ( 4 3 2 1 -- X ) of the
sequence "nip over tuck dup drop", then searched for the list L of
stack manipulation word with the same stack effect. As a result, the
data stack effect is ( 4 3 2 1 -- 4 3 3 1 ); the shortest list is "nip
over swap".

And here's the Prolog program. It should be obvious how to add or
remove descriptions of stack manipulation words. And I'm sure Micheal
Gassanenko will come up with a (Bac)Forth version:-).
----------------------------------------------------------
%eff(Word,Data_Stack_in, Return_Stack_in, Data_Stack_out, Return_Stack_out).
eff(swap,[A,B|D],R,[B,A|D],R).
eff(dup,[A|D],R,[A,A|D],R).
eff(drop,[A|D],R,D,R).
eff('>r',[A|D],R,D,[A|R]).
eff('r>',D,[A|R],[A|D],R).
eff('r@',D,[A|R],[A|D],[A|R]).
eff(rot,[A,B,C|D],R,[C,A,B|D],R).
eff(over,[A,B|D],R,[B,A,B|D],R).
eff('2dup',[A,B|D],R,[A,B,A,B|D],R).
eff(nip,[A,B|D],R,[A|D],R).
eff(tuck,[A,B|D],R,[A,B,A|D],R).

%delay find(nonvar,any,any,any,any).
find([],D,R,D,R).
find([Word|Words],Din,Rin,Dout,Rout):-
	eff(Word,Din,Rin,D1,R1),
	find(Words,D1,R1,Dout,Rout).

findbest(L,Din,Rin,Dout,Rout):-
	genlist(L),
	find(L,Din,Rin,Dout,Rout).

genlist([]).
genlist([_|T]):- genlist(T).
----------------------------------------------------------
- anton
-- 
M. Anton Ertl                    Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen