Recently I have been trying to distill a base set of stack operators - a small set from which everything else derives. A few questions bug me, on how to access elements deeper on (in) the stack.
My set of absolutely necessary operators are DIG and BURY (those are my provisional names, they may already exist under other names).
DIG ( n -- d ) ( consumes 'n', copies the value from the cell at depth 'n' to the top ) so : DUP 0 DIG ; : OVER 1 DIG ; etc.
BURY ( d n -- ) ( consumes 'n', copies the top of stack to the cell at depth 'n+1', then drops the top of stack ) so : NIP 0 BURY ; : DROP 1 DIG 0 BURY 0 BURY : SWAP 1 DIG 1 DIG 2 BURY 0 BURY ; etc., efficiency notwithstanding.
I have no definite conclusion as yet, so, could someone please kindly comment on these?
> Recently I have been trying to distill a base set > of stack operators - a small set from which everything > else derives. A few questions bug me, on how to access > elements deeper on (in) the stack.
> My set of absolutely necessary operators are DIG and BURY > (those are my provisional names, they may already exist under > other names).
> DIG ( n -- d ) ( consumes 'n', copies the value from the cell at depth > 'n' to the top ) > so > : DUP 0 DIG ; > : OVER 1 DIG ; > etc.
> BURY ( d n -- ) ( consumes 'n', copies the top of stack to the cell at > depth 'n+1', then drops the top of stack ) > so > : NIP 0 BURY ; > : DROP 1 DIG 0 BURY 0 BURY > : SWAP 1 DIG 1 DIG 2 BURY 0 BURY ; > etc., efficiency notwithstanding.
> I have no definite conclusion as yet, > so, could someone please kindly comment on these?
I'm too sleepy to grok BURY right now. Your DIG is called PICK .
Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
> Recently I have been trying to distill a base set > of stack operators - a small set from which everything > else derives. A few questions bug me, on how to access > elements deeper on (in) the stack.
> My set of absolutely necessary operators are DIG and BURY > (those are my provisional names, they may already exist under > other names).
> DIG ( n -- d ) ( consumes 'n', copies the value from the cell at depth > 'n' to the top ) > so > : DUP 0 DIG ; > : OVER 1 DIG ; > etc.
> BURY ( d n -- ) ( consumes 'n', copies the top of stack to the cell at > depth 'n+1', then drops the top of stack ) > so > : NIP 0 BURY ; > : DROP 1 DIG 0 BURY 0 BURY > : SWAP 1 DIG 1 DIG 2 BURY 0 BURY ; > etc., efficiency notwithstanding.
> I have no definite conclusion as yet, > so, could someone please kindly comment on these?
It's usually considered bad style to access items deep in the stack. If you're doing it, you probably need to factor more.
As I see it there are three fundamental types of operation on the stack 1. Duplicate an item (DUP, OVER) 2. Discard an item (DROP, NIP) 3. Reorder the stack (SWAP, ROT) You've sort of combined the last two in BURY.
Charles Moore's colorforth www.colorforth.com has 5 stack operators DUP, DROP, OVER, PUSH and POP (those last two are the same as >R and R> in the standard).
-- George Morrison | george morrison gedamo demon co uk Aberdeen, Scotland | . @ . . .
Playing with words that have different stack effects, chosen at runtime, makes code difficult to read, analyse, and write. It's also not needed.
The Yahoo group "concatenative" has discussed this issue in the past; the question is, what is the minimal set of dataflow combinators that can generate all the others?
What you need is DROP, SWAP, >R, and R>. You can dive to any depth on the stack by shoving things onto the return stack, then grab the thing you want and come to the surface. You can make runtime effects using loops, if you want.
> Playing with words that have different stack effects, chosen at > runtime, makes code difficult to read, analyse, and write. It's also > not needed.
> The Yahoo group "concatenative" has discussed this issue in the past; > the question is, what is the minimal set of dataflow combinators that > can generate all the others?
> What you need is DROP, SWAP, >R, and R>. You can dive to any depth on > the stack by shoving things onto the return stack, then grab the thing > you want and come to the surface. You can make runtime effects using > loops, if you want.
> -Billy
How do you move n things to the return stack using a loop in a standard way? I belive you can use the return stack in a loop, but that makes the loop variables inaccessible, further the return stack must be restored to its original state before reaching the end of the loop, so you can't use it for storage between iterations.
I looked at this long and hard when I was defining my CPU instruction set. I eventually decided that implementing PICK and ROLL in an efficient way was not required. But in analyzing the problem, I did decide that it was important to optimize looping and found a simple way.
--
Rick "rickman" Collins
rick.coll...@XYarius.com Ignore the reply address. To email me use the above address with the XY removed.
Arius - A Signal Processing Solutions Company Specializing in DSP and FPGA design URL http://www.arius.com 4 King Ave 301-682-7772 Voice Frederick, MD 21701-3110 301-682-7666 FAX
Jeff wrote: > Le Sun, 29 Aug 2004 10:46:52 -0700, billy a écrit :
>>What you need is DROP, SWAP, >R, and R>.
> How do you make a DUP using these ? > I actually would replace your DROP (you drop with >R) by a DUP
> no?
R@ is a great help. DUP could be >R R@ R> . But isn't it a rather academic discussion? Wouldn't you do all those words as primitives?
Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
> Le Sun, 29 Aug 2004 10:46:52 -0700, billy a écrit :
>> What you need is DROP, SWAP, >R, and R>.
> How do you make a DUP using these ? > I actually would replace your DROP (you drop with >R) by a DUP
If you drop with >R, all you've done is move the hot potato to the return stack. How do you DROP it from the return stack? -- Roger Ivie ri...@ridgenet.net http://anachronda.webhop.org/ -----BEGIN GEEK CODE BLOCK----- Version: 3.12 GCS/P d- s:+++ a+ C++ UB--(++++) !P L- !E W++ N++ o-- K w O- M+ V+++ PS+ PE++ Y+ PGP t+ 5+ X-- R tv++ b++ DI+++ D+ G e++ h--- r+++ z+++ ------END GEEK CODE BLOCK------
Jeff wrote: > Le Mon, 30 Aug 2004 01:23:14 +0000, Roger Ivie a écrit :
>>>>What you need is DROP, SWAP, >R, and R>.
>>>How do you make a DUP using these ? >>>I actually would replace your DROP (you drop with >R) by a DUP
>>If you drop with >R, all you've done is move the hot potato to the >>return stack. How do you DROP it from the return stack?
> I don't drop it from the rstack, I let it there ;)
Then what do you return to? In some implementations, R> DROP exits the calling word. In most implementations, unbalanced return-stack operations between colon and semicolon will crash. On processors without an instruction that jumps to the address in a register, the affect can be achieved by pushing an address onto the stack and executing subroutine return.
> what about dup ? How do you dup with only drop swap >r and r> ?
> You can't I guess
You need R@ , as I wrote earlier.
Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
>> DIG ( n -- d ) ( consumes 'n', copies the value from the cell at >> depth 'n' to the top ) >> so >> : DUP 0 DIG ; >> : OVER 1 DIG ; >> etc.
>> BURY ( d n -- ) ( consumes 'n', copies the top of stack to the cell at >> depth 'n+1', then drops the top of stack ) >> so >> : NIP 0 BURY ; >> : DROP 1 DIG 0 BURY 0 BURY >> : SWAP 1 DIG 1 DIG 2 BURY 0 BURY ; >> etc., efficiency notwithstanding.
> PICK is the same as your DIG.
I realise that, however, I deliberately wanted to give "new" names, to make a sort of separation.
> It's usually considered bad style to access items deep in the stack. If > you're doing it, you probably need to factor more.
It is not so much a case for factoring, but to find a base for stack operators similar to, say, nor being a base for all (1 and 2 argument) boolean functions: : not dup nor ; : or nor not ; : and not swap not nor ; etc.
Can something similar be done with stack operators? Are PICK and ROLL (and perhaps DROP) a base? What is the smallest base? What is the richest or most efficient base, in the sense that it gives most of useful stack operators with least effort either programming or computational?
Judges1318 <acco...@beaurat.at.hotpop.stop.com> wrote: > George Morrison wrote:
>> It's usually considered bad style to access items deep in the stack. If >> you're doing it, you probably need to factor more.
> It is not so much a case for factoring, but to find a > base for stack operators similar to, say, nor being a > base for all (1 and 2 argument) boolean functions: > : not dup nor ; > : or nor not ; > : and not swap not nor ; > etc. > Can something similar be done with stack operators?
Yes, certainly.
> Are PICK and ROLL (and perhaps DROP) a base? > What is the smallest base?
SWAP, DUP, DROP, R> and >R.
: pick ?dup if swap >r 1- recurse r> swap else dup then ; : roll ?dup if swap >r 1- recurse r> swap then ;
> What is the richest or most efficient base, in the sense that it > gives most of useful stack operators with least effort either > programming or computational?
You'd perhaps want to add OVER and R@ to the above set for efficiency's sake.
ROT is trivially >R SWAP R> SWAP so there's no need to define it as a primitive.
Eventually, probably yes. But during development of a new target it's useful to just have to define a minimum set of primitives, and be able to test that. Once the Forth system works with that, you can add more primitives for better efficiency. Since you can add and remove them one at a time, finding bugs is relatively easy.
Or at least that's what the Gforth EC people tell me. However, AFAIK they cheat and use sp@.
> Recently I have been trying to distill a base set > of stack operators - a small set from which everything > else derives. A few questions bug me, on how to access > elements deeper on (in) the stack.
> My set of absolutely necessary operators are DIG and BURY > (those are my provisional names, they may already exist under > other names).
Judges1318 <acco...@beaurat.at.hotpop.stop.com> wrote in message <news:413174C0.9000200@beaurat.at.hotpop.stop.com>... > My set of absolutely necessary operators are DIG and BURY > DIG ( n -- d ) ( consumes 'n', copies the value from the cell at depth > 'n' to the top ) > so > : DUP 0 DIG ; > : OVER 1 DIG ; > etc.
> BURY ( d n -- ) ( consumes 'n', copies the top of stack to the cell at > depth 'n+1', then drops the top of stack ) > so > : NIP 0 BURY ; > : DROP 1 DIG 0 BURY 0 BURY > : SWAP 1 DIG 1 DIG 2 BURY 0 BURY ; > etc., efficiency notwithstanding.
I choose to use a variation of PICK , but allowing negative parameters by parameterizing the stack elements from 1 instead of 0.
Call the operator S . S takes an integer n as an argument, where abs(n) =< DEPTH .
So " -n S " is actually a shorhand for " n -S " . S substitutes DIG and BURY .
My motivation for doing this has been to unify stack operation names. If I write
... : -1S -1 S ; : 0S 0 S ; : 1S 1 S ; ...
then
' nip alias -2S ' drop alias -1S ' noop alias 0S ' dup alias 1S ' over alias 2S ' pluck alias 3S
in which the S-names are arguably easier to remember and to operate upon than the original names in the same way as the month names are easier in Chinese (1-month, 2-month, ...) than in English.
Likewise I define " n T " to mean " 1- roll " if n is positive and " negate 1- -roll " if n is negative so that
' -rot alias -3T ' swap alias -2T ' noop alias -1T ' abort alias 0T ' noop alias 1T ' swap alias 2T ' rot alias 3T
> > My set of absolutely necessary operators are DIG and BURY
> > DIG ( n -- d ) ( consumes 'n', copies the value from the cell at depth > > 'n' to the top ) > > so > > : DUP 0 DIG ; > > : OVER 1 DIG ; > > etc.
> > BURY ( d n -- ) ( consumes 'n', copies the top of stack to the cell at > > depth 'n+1', then drops the top of stack ) > > so > > : NIP 0 BURY ; > > : DROP 1 DIG 0 BURY 0 BURY > > : SWAP 1 DIG 1 DIG 2 BURY 0 BURY ; > > etc., efficiency notwithstanding.
> I choose to use a variation of PICK , but allowing negative parameters > by parameterizing the stack elements from 1 instead of 0.
> Call the operator S . > S takes an integer n as an argument, where abs(n) =< DEPTH .
> So " -n S " is actually a shorhand for " n -S " . > S substitutes DIG and BURY .
> My motivation for doing this has been to unify > stack operation names. > If I write
> ... > : -1S -1 S ; > : 0S 0 S ; > : 1S 1 S ; > ...
> then
> ' nip alias -2S > ' drop alias -1S > ' noop alias 0S > ' dup alias 1S > ' over alias 2S > ' pluck alias 3S
> in which the S-names are arguably easier to remember and to operate > upon than the original names in the same way as the month names are > easier in Chinese (1-month, 2-month, ...) than in English.
> Likewise I define " n T " to mean > " 1- roll " if n is positive and " negate 1- -roll " if n is negative > so that
> ' -rot alias -3T > ' swap alias -2T > ' noop alias -1T > ' abort alias 0T > ' noop alias 1T > ' swap alias 2T > ' rot alias 3T
Ok, I'll bite. How exactly is "0T" easier to remember than "abort"? I would never consider coding *unrelated* operations in this way. I see little relation between dup, drop or rot and I see *no* relation between any stack op and noop or abort that would make me even consider a notation like this. What exactly is the advantage?
Your analogy to the Chinese calendar is not valid because all months are pretty equivalent to the others. So most names are very arbitrary and the numbers are only a slight improvement. But most of the functions you are combining are very distinct. Combining them with this sort of nomenclature obfucates their function and makes them *harder* to remember in my opinion.
--
Rick "rickman" Collins
rick.coll...@XYarius.com Ignore the reply address. To email me use the above address with the XY removed.
Arius - A Signal Processing Solutions Company Specializing in DSP and FPGA design URL http://www.arius.com 4 King Ave 301-682-7772 Voice Frederick, MD 21701-3110 301-682-7666 FAX
> I choose to use a variation of PICK , but allowing negative parameters > by parameterizing the stack elements from 1 instead of 0.
I see the word PLUCK below and that gives me hope that you didn't change the function without changing the name.
...
Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
> > Likewise I define " n T " to mean > > " 1- roll " if n is positive and " negate 1- -roll " if n is negative > > so that
> > ' -rot alias -3T > > ' swap alias -2T > > ' noop alias -1T > > ' abort alias 0T > > ' noop alias 1T > > ' swap alias 2T > > ' rot alias 3T
> Ok, I'll bite. How exactly is "0T" easier to remember than "abort"? I > would never consider coding *unrelated* operations in this way. I see > little relation between dup, drop or rot and I see *no* relation between > any stack op and noop or abort that would make me even consider a > notation like this. What exactly is the advantage?
I think the intent is that 0T is supposed to be an error, and hence abort. But I completely agree that these names are really obfuscating what's going on, and make code lots harder to read.
Cheers, Elizabeth
-- ================================================== Elizabeth D. Rather (US & Canada) 800-55-FORTH FORTH Inc. +1 310-491-3356 5155 W. Rosecrans Ave. #1018 Fax: +1 310-978-9454 Hawthorne, CA 90250 http://www.forth.com
"Forth-based products and Services for real-time applications since 1973." ==================================================
Thank you; I missed the word DUP (or one could use R@, as others have observed).
There may be more efficient combinator sets; I forget the results of the discussion. It's notable that the most efficient set we found for Joy (a functional Forthlike) was not only capable of forming any stack arrangement, it was actually computationally complete.
It is neat if I can put everything onto the data stack, so to my preference, PICK and ROLL (actually DIG and BURY) take priority over R> and >R, and they both take priority over allocating a VARIABLE. I find VARIABLEs so unforthly.
Judges1318 <acco...@beaurat.at.hotpop.stop.com> wrote: > Julian V. Noble wrote: >> My general advice re: deep stacks is "Don't". > Well, it is "don't unless you have to", really. > It is neat if I can put everything onto the data stack, so to my > preference, PICK and ROLL (actually DIG and BURY) take priority over > R> and >R, and they both take priority over allocating a VARIABLE. > I find VARIABLEs so unforthly.
They are. However, putting a lot of variables on the stack is also unforthly,
an...@mips.complang.tuwien.ac.at (Anton Ertl) wrote in message <news:2004Aug30.142454@mips.complang.tuwien.ac.at>... > Jerry Avins <j...@ieee.org> writes: > [minimal set of stack words] > >But isn't it a rather > >academic discussion?
> No.
> >Wouldn't you do all those words as primitives?
> Eventually, probably yes. But during development of a new target it's > useful to just have to define a minimum set of primitives, and be able > to test that. > Once the Forth system works with that, you can add more > primitives for better efficiency. Since you can add and remove them > one at a time, finding bugs is relatively easy.
As to new targets, I usually debug data stack operators first, then look at the return stack ones.
If data stack primitives may be done without return stack access, they should be done this way.
(BTW, there are "underwater stones" with the implementation of PICK/ROLL via r-stack access: theoretically correct code may break when shallow return stack overflows.)
rickman <spamgoeshe...@yahoo.com> wrote in message <news:413388D5.4FB3604@yahoo.com>... > How exactly is "0T" easier to remember than "abort"?
Assuming that someone knows the definition of T, that person can easily guess that "0 T" should mean to ABORT . That means at least one less word name to remember.
> Your analogy to the Chinese calendar is not valid because all months are > pretty equivalent to the others.
Whether things are alike or not depends on the viewpoint. The S operator provides a viewpoint such that many stack operations with different names look "pretty equivalent to" each other.
> Jerry Avins <j...@ieee.org> writes: ... > >Wouldn't you do all those words as primitives?
> Eventually, probably yes. But during development of a new target it's > useful to just have to define a minimum set of primitives, and be able > to test that. Once the Forth system works with that, you can add more > primitives for better efficiency. Since you can add and remove them > one at a time, finding bugs is relatively easy.
Well, we start with the stack operations as primitives because that helps us adapt the model to the architecture we're doing the implementation for. We pick register allocations, for example, and then test that design by writing the primitives. Occasionally we'll realize that a different allocation will make the primitives better, and it's good to know that sooner rather than later.
Cheers, Elizabeth
-- ================================================== Elizabeth D. Rather (US & Canada) 800-55-FORTH FORTH Inc. +1 310-491-3356 5155 W. Rosecrans Ave. #1018 Fax: +1 310-978-9454 Hawthorne, CA 90250 http://www.forth.com
"Forth-based products and Services for real-time applications since 1973." ==================================================
> > How exactly is "0T" easier to remember than "abort"?
> Assuming that someone knows the definition of T, > that person can easily guess that "0 T" should mean to ABORT . > That means at least one less word name to remember.
Ok, what is the definition of "T"? If you just list a table, like in the other post, then I don't see how this is "easy" to remember, rather it is just arbitrary. Even if "0 T" represents an error, I don't see how this implies an abort rather than just an error which will produce incorrect operation.
> > Your analogy to the Chinese calendar is not valid because all months are > > pretty equivalent to the others.
> Whether things are alike or not depends on the viewpoint. > The S operator provides a viewpoint such that many stack operations > with different names look "pretty equivalent to" each other.
I am not trying to be arguementative about this, but I really don't see the advantage unless you are writing some sort of program generating program. I don't think the S operator is any more intuitive or easier to remember than the few stack words. Are there any programmers who do not know what NOOP means? Is DUP a difficult thing to remember? On the other hand, the two functions of S, duplicating and deleting, are not automatically intuitive from the + and - number supplied. If this replaced a dozen words, then I would agree with you. But from what I have read here and elsewhere when I did a survey, of the words you equate to an S operation, only DROP, DUP and OVER are frequently used in Forth programs. I guess NIP may have some useage, but I have not seen it much and there was a recent discussion about PLUCK, ROLL and PICK where examples were given showing that they are very seldom used and mostly considered to have been used poorly.
Do I misunderstand your intent? Are you thinking in terms of a standard form to be used by software, or is this intended to help people use these stack operations?
--
Rick "rickman" Collins
rick.coll...@XYarius.com Ignore the reply address. To email me use the above address with the XY removed.
Arius - A Signal Processing Solutions Company Specializing in DSP and FPGA design URL http://www.arius.com 4 King Ave 301-682-7772 Voice Frederick, MD 21701-3110 301-682-7666 FAX
