Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #45503
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: How do you remember the stack? |
| Date | 2016-02-13 12:33 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2016Feb13.133301@mips.complang.tuwien.ac.at> (permalink) |
| References | <07ab86b1-3681-47c0-80ea-d7bd908925e7@googlegroups.com> <579900110.477043450.336442.dunno-dunno.dunno@news.mixmin.net> <9479860c-a779-4ab8-9e64-1e0c5f761b41@googlegroups.com> <2016Feb13.122718@mips.complang.tuwien.ac.at> |
anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Another possible answer is the stack manipulation optimizer I posted
>here a few years ago:
><http://www.complang.tuwien.ac.at/forth/stack-opt>. I guess one could
>extend this to deal with straight-line code containing other words
>than stack manipulation, but the simple exhaustive search is limited
>to just a few words.
I have now extended the old version with rules for '+' to show that it
is not limited to stack manipulation words. Drawback: The more words
you add, the slower the search becomes. + also demonstrates that we
can specify commutativity and make use of that in the optimization.
A simple case:
?- find([swap,+],[a,b,c,d],[],X,[]), findbest(L,[a,b,c,d],[],X,[]).
X = [b+a, c, d],
L = [+] .
I queried Prolog to give me all sequences L equivalent to [swap,+],
starting with the shortest one(s). I provide a data stack with four
elements (with the leftmost element being the TOS) and a return stack
with none at the start, so the system can work. As the first result,
Prolog found L=[+], so it recognized that SWAP + is equivalent to +
(based on the stack effect of SWAP and the two stack effects of +).
A more complex case:
?- find([dup,'>r',+,'r>'],[a,b,c,d],[],X,[]), findbest(L,[a,b,c,d],[],X,[]).
X = [a, a+b, c, d],
L = [tuck, +, swap] .
Here I find that a shorter way to write DUP >R + R> is TUCK + SWAP.
For a better answer to the original poster, I also added a way to
specify that one is reading a local, and a predicate for directly
querying for the equivalence we want.
?- loc_stack([l(b),l(d),+,l(a),l(c),+],L,[a,b,c,d],X).
L = [rot, +, '>r', +, 'r>'],
X = [c+a, d+b] .
Here I asked the system to give me a locals-less sequence L that is
equivalent to the sequence with locals "b d + a c +", and for L the
starting stack is "d c b a", while for the locals sequence it is
empty; X is the stack contents of both sequences at the end.
Here's the enhanced program:
%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,[_|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,_|D],R,[A|D],R).
eff(tuck,[A,B|D],R,[A,B,A|D],R).
eff(+,[A,B|D],R,[A+B|D],R).
eff(+,[A,B|D],R,[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).
findloc([],D,R,D,R).
findloc([l(V)|Words],Din,Rin,Dout,Rout):-
findloc(Words,[V|Din],Rin,Dout,Rout).
findloc([Word|Words],Din,Rin,Dout,Rout):-
eff(Word,Din,Rin,D1,R1),
findloc(Words,D1,R1,Dout,Rout).
findbest(L,Din,Rin,Dout,Rout):-
genlist(L),
find(L,Din,Rin,Dout,Rout).
loc_stack(L1,L2,Din,Dout):-
findloc(L1,[],[],Dout,[]),
findbest(L2,Din,[],Dout,[]).
genlist([]).
genlist([_|T]):- genlist(T).
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How do you remember the stack? laheadle@gmail.com - 2016-02-12 13:57 -0800
Re: How do you remember the stack? Paul Rubin <no.email@nospam.invalid> - 2016-02-12 14:08 -0800
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-16 13:35 +1100
Re: How do you remember the stack? Julian Fondren <julian.fondren@gmail.com> - 2016-02-15 19:28 -0800
Re: How do you remember the stack? Whammo <sidciavic@gmail.com> - 2016-02-15 19:54 -0800
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-16 07:28 +0000
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-15 22:03 -1000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-16 13:30 +0000
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-16 08:20 -1000
Re: How do you remember the stack? dunno <dunno@dunno.dunno> - 2016-02-16 20:48 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-17 15:42 +0000
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-18 18:48 +1100
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-18 12:27 -0800
Re: How do you remember the stack? Julian Fondren <julian.fondren@gmail.com> - 2016-02-18 14:53 -0800
Re: How do you remember the stack? Julian Fondren <julian.fondren@gmail.com> - 2016-02-18 15:18 -0800
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-21 13:32 +1100
Re: How do you remember the stack? Chris Curl <ccurl609@gmail.com> - 2016-02-20 20:57 -0800
Re: How do you remember the stack? Ron Aaron <rambamist@gmail.com> - 2016-02-21 07:23 +0200
Re: How do you remember the stack? Chris Curl <ccurl609@gmail.com> - 2016-02-21 08:54 -0800
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-21 22:05 -0800
Re: How do you remember the stack? Lars Brinkhoff <lars.spam@nocrew.org> - 2016-02-22 16:20 +0100
Re: How do you remember the stack? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-02-22 09:47 -0600
Re: How do you remember the stack? Whammo <sidciavic@gmail.com> - 2016-02-23 16:51 -0800
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-28 15:22 +1100
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-27 21:30 -0800
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-27 21:33 -0800
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-27 21:39 -1000
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-29 13:47 +1100
Re: How do you remember the stack? Paul Rubin <no.email@nospam.invalid> - 2016-02-28 19:02 -0800
Re: How do you remember the stack? Julian Fondren <julian.fondren@gmail.com> - 2016-02-28 22:26 -0800
Re: How do you remember the stack? Paul Rubin <no.email@nospam.invalid> - 2016-02-28 22:37 -0800
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-28 19:11 -0800
Re: How do you remember the stack? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-02-29 11:55 -0600
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-29 19:30 -1000
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-03-02 00:49 +1100
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-03-01 13:50 -1000
Re: How do you remember the stack? Paul Rubin <no.email@nospam.invalid> - 2016-03-01 16:49 -0800
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-03-01 18:04 -0800
Re: How do you remember the stack? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-03-02 02:53 -0600
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-02 09:57 +0000
Re: How do you remember the stack? Pablo Hugo Reda <pabloreda@gmail.com> - 2016-03-02 03:21 -0800
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-02 11:49 +0000
Re: How do you remember the stack? Pablo Hugo Reda <pabloreda@gmail.com> - 2016-03-02 04:23 -0800
Re: How do you remember the stack? stephen@mpeforth.com (Stephen Pelc) - 2016-03-02 18:32 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-02 18:41 +0000
Re: How do you remember the stack? stephen@mpeforth.com (Stephen Pelc) - 2016-03-02 20:36 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-03 07:38 +0000
Re: How do you remember the stack? stephen@mpeforth.com (Stephen Pelc) - 2016-03-03 09:26 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-03 11:15 +0000
Re: How do you remember the stack? stephen@mpeforth.com (Stephen Pelc) - 2016-03-03 15:35 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-03 15:56 +0000
Re: How do you remember the stack? stephen@mpeforth.com (Stephen Pelc) - 2016-03-03 17:04 +0000
Re: How do you remember the stack? Whammo <sidciavic@gmail.com> - 2016-03-01 19:29 -0800
Re: How do you remember the stack? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-28 18:52 +0000
Re: How do you remember the stack? Whammo <sidciavic@gmail.com> - 2016-02-28 13:30 -0800
Re: How do you remember the stack? Lars Brinkhoff <lars.spam@nocrew.org> - 2016-02-29 07:55 +0100
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-29 19:34 -1000
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-03-01 20:40 -0800
Re: How do you remember the stack? Unknown <dog@gmail.com> - 2016-06-02 05:46 +0000
Re: How do you remember the stack? Lars Brinkhoff <lars.spam@nocrew.org> - 2016-06-02 08:48 +0200
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-06-02 00:17 -0700
Re: How do you remember the stack? Michael Barry <barrym95838@yahoo.com> - 2016-06-02 19:48 -0700
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-06-02 20:34 -0700
Re: How do you remember the stack? "WJ" <w_a_x_man@yahoo.com> - 2016-02-22 19:23 +0000
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-25 20:31 +1100
Re: How do you remember the stack? Julian Fondren <julian.fondren@gmail.com> - 2016-02-25 07:44 -0800
Re: How do you remember the stack? Lars Brinkhoff <lars.spam@nocrew.org> - 2016-02-25 20:22 +0100
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-28 13:43 +1100
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-27 21:43 -1000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-28 14:53 +0000
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-28 15:27 -0800
Re: How do you remember the stack? humptydumpty <ouatubi@gmail.com> - 2016-06-02 02:02 -0700
Re: How do you remember the stack? JennyB <jennybrien@googlemail.com> - 2016-06-03 05:57 -0700
Re: How do you remember the stack? Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-01 16:38 +0000
Re: How do you remember the stack? Chris Curl <ccurl609@gmail.com> - 2016-02-12 16:31 -0800
Re: How do you remember the stack? Whammo <sidciavic@gmail.com> - 2016-02-12 17:31 -0800
Re: How do you remember the stack? Lars Brinkhoff <lars.spam@nocrew.org> - 2016-02-13 08:03 +0100
Re: How do you remember the stack? dunno <dunno@dunno.dunno> - 2016-02-13 08:06 +0000
Re: How do you remember the stack? minforth@arcor.de - 2016-02-13 01:50 -0800
Re: How do you remember the stack? mhx@iae.nl - 2016-02-13 03:22 -0800
Re: How do you remember the stack? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-13 17:09 +0000
Re: How do you remember the stack? mhx@iae.nl - 2016-02-13 03:39 -0800
Re: How do you remember the stack? mhx@iae.nl - 2016-02-13 03:42 -0800
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-13 11:27 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-13 12:33 +0000
Re: How do you remember the stack? minforth@arcor.de - 2016-02-15 01:05 -0800
Re: How do you remember the stack? dunno <dunno@dunno.dunno> - 2016-02-14 19:34 +0000
Re: How do you remember the stack? Julian Fondren <julian.fondren@gmail.com> - 2016-02-13 06:43 -0800
Re: How do you remember the stack? minforth@arcor.de - 2016-02-15 01:22 -0800
Re: How do you remember the stack? dunno <dunno@dunno.dunno> - 2016-02-15 09:48 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-15 09:53 +0000
Re: How do you remember the stack? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-15 11:26 +0000
Re: How do you remember the stack? minforth@arcor.de - 2016-02-15 04:53 -0800
Re: How do you remember the stack? dunno <dunno@dunno.dunno> - 2016-02-15 17:06 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-16 14:57 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-16 14:14 +0000
Re: How do you remember the stack? Ron Aaron <rambamist@gmail.com> - 2016-02-15 12:31 +0200
Re: How do you remember the stack? Jan Coombs <jenfhaomndgfwutc@murmic.plus.com> - 2016-02-18 22:53 +0000
Re: How do you remember the stack? Doug Hoffman <glidedog@gmail.com> - 2016-02-13 10:51 -0500
Re: How do you remember the stack? "HAA" <someone@microsoft.com> - 2016-02-14 10:18 +1100
Re: How do you remember the stack? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-02-14 04:21 -0600
Re: How do you remember the stack? Whammo <sidciavic@gmail.com> - 2016-02-20 14:36 -0800
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-21 16:35 +0000
Re: How do you remember the stack? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-21 18:34 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-22 09:52 +0000
Re: How do you remember the stack? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-22 13:07 +0000
Re: How do you remember the stack? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-22 15:41 +0000
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-22 08:24 -1000
Re: How do you remember the stack? "Elizabeth D. Rather" <erather@forth.com> - 2016-02-22 08:21 -1000
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-22 17:51 -0800
Re: How do you remember the stack? hughaguilar96@gmail.com - 2016-02-22 18:15 -0800
Re: How do you remember the stack? "WJ" <w_a_x_man@yahoo.com> - 2016-02-29 06:20 +0000
Re: How do you remember the stack? "WJ" <w_a_x_man@yahoo.com> - 2016-03-02 20:42 +0000
Re: How do you remember the stack? "WJ" <w_a_x_man@yahoo.com> - 2016-06-02 20:13 +0000
Re: How do you remember the stack? humptydumpty <ouatubi@gmail.com> - 2016-02-22 01:46 -0800
csiph-web