Give me swap and dip and I will bury the world (… and then dig it up again)
To permute (shuffle) a stack in any way possible I only need two operations “dip” and “swap”. Using these functions I can construct a “bury” instruction for placing an item from the top under any number of items. I can also create a “dig” instruction for taking the item under top X items in the stack and placing it on the top.
April 8th, 2007 at 9:01 pm
I think you misunderstood the point of that paper you referenced. dign and buryn can only do the equivalents of Factor’s swap, rot, -rot, roll, -roll, etc. They cannot change the depth of the stack, so alone, they’re not very useful. Generally, the term “stack shuffling” is used to mean not only permuting but also duping and dropping.
Also, even though they can be implemented easily with dip and swap, it’d still be nice to have dig1-3 and bury1-3 in the standard library because they make it easier to write code. But you may have already done this.
Something interesting that you can do with digN and buryN in some stack languages is make it act sort of like a macro: 1 digN could, at parse- or compile-time, be converted into swap, which can then be safely type checked.
April 8th, 2007 at 10:17 pm
> I think you misunderstood the point of that paper you referenced.
I understood the paper very well, I have studied it at great depth. Clearly it covers much more than what I posted here, but it was the motivator for what I presented, therefore it merits being referenced.
> dign and buryn can only do the equivalents of Factor’s swap, rot, -rot, roll, -roll, etc. They cannot change the depth of the stack, so alone, they’re not very useful.
That’s silly, of course they are very important. Just because dup and pop is also important doesn’t take away from the importance of “dig” and “bury”.
> Generally, the term “stack shuffling†is used to mean not only permuting but also duping and dropping.
I am unaware of such a convention. It is a corruption of what “shuffling” means in plain english. Do you shuffle a deck of cards by adding or removing cards? I only do when I am cheating ;-)
> Also, even though they can be implemented easily with dip and swap, it’d still be nice to have dig1-3 and bury1-3 in the standard library because they make it easier to write code. But you may have already done this.
Yes, see: http://cat-language.googlecode.com/svn/trunk/cat/standard.cat
> Something interesting that you can do with digN and buryN in some stack languages is make it act sort of like a macro: 1 digN could, at parse- or compile-time, be converted into swap, which can then be safely type checked.
Yes I agree this is very useful, and I hope to add something similar to Cat. This requires that the value is determinable at compile-time. Compile-time values are like C++ constants. It significantly improves the expressive abilities of a type-system if you can pass compile-time values. Consider fixed size arrays for example.
The challenge is to distinguish between values known at run-time and values known at compile-time. I don’t know of any language that does a good job of distinguishing between these kinds of values without confusion In Heron I classified them as values and meta-values.
Anyway it is a feature needed in Cat, but I fear confusing people by saying “N dup” only works if N is determinable at compile-time. There may be no other choice though.