Stack Manipulation

obvious things out of the way: forth is a stack-based language^{[citation needed][citation no longer needed]} the stack usually consists of cells and the cells are usually 16-bit but are sometimes wider than 16 bits. there are typically two stacks: a parameter/data stack (the top of which is pointed to by S) and a return stack (the top of which is pointed to by R). the data stack is unchanged by the nesting/unnesting of words, while the return stack gains data (usually 1 cell but could be more or less or fractional or even a new isolated stack). the top of the stack is called the TOS, the next element on the stack being called NOS, and then the rest are referred to by number (3OS, 4OS, &c). i will extend this convention to call the top of the return stack TOR and similar. we write stack comments like ( a b c ) where the last element is the TOS, second-to-last is NOS, &c. for entire words we may write ( a b c -- a+c b ), where the left part is the stack before the word is executed, and the right part is the resulting stack after the word is executed. for space-efficiency when describing stack-shuffling words i will remove spaces (instead of (a b -- b a) i may write ab-ba. borrowed from colorForth). i will also borrow dot notation for explaining the return stack (so ( a b -- a ) ( R: c -- c b ) is ab.c-a.cb) and use an asterisk to represent an arbitrary number of elements.

Standardized Words

here's a table of all the forth-2012 standard (core + core ext + double) data stack manipulation words.

each group is roughly ordered in my subjective estimation of frequency. immediately, a few things jump out: there's no word to permute the top element of the stack, because there's nothing to permute it with; that most words only deal with the top two elements of the stack, with the exceptions being ROT, double-cell words, PICK, and ROLL, the most egregious one being 2ROT; and there are far, far fewer double-cell words than single-cell words.

PICK and ROLL are peculiar words because they change how far down into the stack they access depending on TOS. 0 PICK is equivalent to DUP, 1 PICK is OVER, and then the only alternative to 2 PICK would be something like >R OVER R> SWAP. similarly, 1 ROLL is SWAP, 2 ROLL is ROT, and 3 ROLL is something like >R ROT R> SWAP. ?DUP is a lot less weird but substantially worse, because it is the only word in this entire list that makes the stack a different size depending on what it contains! if TOS is nonzero, ?DUP acts like DUP, otherwise it is a no-op. this is primarily to allow one to do ?DUP IF ... ELSE ... THEN without having to write DUP IF ... ELSE DROP ... THEN repeatedly. again, "?DUP is a nasty word because it leaves a variable number of things on the stack and that is not a wise thing to do". please don't use ?DUP, it's not worth it.

fun fact: nearly all of these words (drop PICK ROLL ?DUP) can be written entirely in terms of >R R> DUP DROP SWAP! doing so is left as an exercise for the reader.

right. that about sums it up for standard words. now all that's left to talk about is.

...

oh, right, i nearly forgot to mention: the nastiest word to implement on this list is not ?DUP, however. ?DUP is very easy to implement. ROLL, on the other hand, requires implementing a literal memory move operation. the proposed reference implementation in the Forth-2012 standard consists of a recursive definition! which, although recursion is ordinary in other programming languages, it is most unusual in forth!

   \ EASY
: ?DUP   DUP IF DUP THEN ;

   \ HARD
: ROLL   IF SWAP >R 1- RECURSE R> SWAP ELSE DROP THEN ;

   \ HARDER (MORE EFFICIENT, IMPL-DEPENDENT. THIS WORKS ON GFORTH)
: ROLL   DUP 1+ PICK >R CELLS >R SP@ DUP CELL+ R> MOVE DROP R> ;

okay. now we have to talk about.

...

the floating-point stack! right. optionally, if implementations choose so, they can support a separate floating-point stack in addition to the data and return stacks. this provides a new suite of words!

it is also permitted for the implementation to simply put floats on the data stack as well.

there's also the control flow stack! this is used to create "intertwining" control flow structures by switching around what pairs with what, allowing you to pull off the world's sickest möbius double-reacharound. unfortunately it's cringe because it only has CS-PICK and CS-ROLL so i have nothing else to say about it.

there's also the locals stack that exists in gforth and seemingly only gforth but other than that locals are kind of a massive meme.

...

...oh god, is it colloquialism time? ohh it's colloquialism ti-

Colloqiual Words

so. there are a few words that technically aren't in the forth-2012 standard but also it's really obvious what they do: 3DROP 4DROP 5DROP RDROP 2NIP RNIP RDUP ROVER RSWAP. there's also RTUCK which is used to implement locals. again. and RSWAP can be used to implement ;:/CO/EX as a secondary (in forth). the next most obvious ones are -ROT ( abc-cab ) (sometimes named RROT or NROT), THIRD ( abc-abca ) (sometimes named PLUCK) and FOURTH ( abcd-abcda ). these are equivalent to ROT ROT, 2 PICK, and 3 PICK and are occasionally seen. there's also -ROLL ( *ai-a* )? sometimes? there's also POKE ( a*bi-b* ) which is also called STICK (...supported by gforth, what. why??? bad code speedrun any%?????) and also occasionally referred to as PLACE or POST or BURY but sometimes BURY is used exclusively to refer to BURY ( abcd-dabc ), or in other words 3 ROLL. also people on the forth-2012 discussion page for PICK unironically suggested adding 2PICK which i am not going to acknowledge. i draw a fine line and this is past that line. on the topic of interstack operations, R'@ ( .ab-a.ab ) copies the second item from the return stack and R"@ ( .abc-a.abc ) copies the third item. this is partially in analogy to I' and J, words for getting loop parameters, because loop parameters are conventionally stored on the data stack. there also sometimes exists K for the third loop index. on the floating point stack, we sometimes have FEXCHANGE ( a*bi-b*a ) which swaps TOS with another element on the float stack, and consequently we also have EXCHANGE which does the same thing for the data stack.

we can also now touch upon the wonderful, wonderful Stack Quarks. the paper that inspired me to start looking for all the stack manipulation operators in colloquial use in the first place.

Stack Quarks

NUP here is particularly special, and has two alternate names: UNDER, with analogy to OVER, SHOVE, and DUPD, an abbreviation for [ dup ] dipJoy. ah shit now we have to talk about dipJoy

Concatenative Languages

so the stack quark named DIP ( ab-aa ) is not to be confused with the combinator named dip in Joy, Factor, and many other concatenative languages, which takes in a quoted program and executes it a stack element lower. in forth terms, [ ... ] dip can be thought of as >R ... R>. it just temporarily moves the top element out of the way and lets you operate a step below. often, if a particular stack operation is combined with dip enough, there will be a variant with a d suffix: take joy's pop dup swap rollup rolldown rotate (equivalents in forth: DROP DUP SWAP -ROT ROT REV), and now they're popd dupd swapd rollupd rolldownd rotated. oh yeah, while i'm here i might as well mention that REV ( abc-cba ) is also called rotateJoy, SPIN (which went on to influence Factor, i believe! (factor also confusingly uses pick for THIRD)).

on the topic of concatenative languages, Factor largely uses the same names as forth for present stack operators and provides a many new names for its unique ops. most confusingly, it uses the 2 prefix not to mean "double-cells" but to mean "two elements", and extends this to higher numbers. this means that Forth's 2NIP ( abcd-cd ) and Factor's 2nip ( abc-c ) have two entirely different effects. Factor also has Generalized Shuffle Words, or in other words,

PICK. 2.

now, in forth, this would be a catastrophe. however i'm not a factor programmer, so there's a good chance code style is just. different. in factor. who knows.

so we have ndup ( *n-** ), which duplicates the topmost N elements (also a block move!); dupn ( xn-* ) which seems to duplicate the top of the stack N times, almost like ?DUP but more general; npick which is what we forthists call PICK; nrot which is what we call ROLL; -nrot which is -ROLL; nnip ( *an-a ) which repeatedly invokes NIP N times; ndrop ( *n- ) which does exactly what you think it does, mnswap ( **mn-** ), which takes the top M elements and the N elements under it and swaps those two blocks (for instance, if you squint at ROT ( abc-bca ), it's swapping bc and a, or in other words the top 2 elements and the element below it. therefore, we can rewrite ROT as 2 1 mnswap!), and nweave, which. i'm not even sure how to explain. look. it's here. read it if you want. this is the most contrived stack operator of all time.

less pointlessly, factor also has ndip, which is like >R ... R> but with bigger moves (as in, [ ... ] 2 ndip is 2>R ... 2R>, [ ... ] 3 ndip is 2>R >R ... R> 2R>, &c). it also very interestingly includes nkeep, which i can best describe as -R@ ... R> with bigger moves. and if you don't recognize -R@ ( a.-a.a ) that's because i made it up the actual documented name of this operation is STHk. and if you still don't recognize it that's because it's part of

Uxntal

uxntal is a forth-descended language that is still noticably not a forth dialect. this is most obvious by the fact it is bytecode implemented as a VM and isn't interpreted at all. but it does have an instruction set, most notably an orthogonal instruction set. while this is often very useful, as it, for instance, allows you to write ADDk instead of DUP2 ADD or, worse, OVR OVR ADD, but the consequence is you end up getting utterly incomprehensible operations like ROT2k abcdef-abcdefcdefab, which is so long it's starting to look like a rhyme structure.

it ultimately only has a handful of stack operations: POP NIP SWP ROT DUP OVR STH (equivalent to DROP NIP SWAP ROT DUP OVER >R in forth). it, however, also has three modifiers: 2, which makes it operate on double-cells instead of single-cells; k, which means that it should keep the elements that used to be on the stack before they were consumed by the word (notice how the definition of ROT2k keeps all 6 elements on the stack, and pushes 6 more in a different order. this is in contrast to ROT2, which pops 6 elements and then pushes them back in a different order. NIPk is equivalent to DUP); and r, which means the word should function on the return stack (yes this means ROT2kr is a thing don't use it). more precisely, r swaps the roles of the return and data stacks. so STHr is how we write R>, and STHkr is how we write R@!

and that's where -R@ comes from: STHk means "move the top of the data stack to the top of the return stack without removing it from the data stack". it is equivalent to DUP >R.

okay, let's return back to traditional forth again. but, with a bit of a twist!

Open Interpreter

the Open Interpreter standard offers a wordset for making return stack manipulations portable across multiple systems. this is, in my opinion, one of the biggest forth gamechangers, as it formalizes the ability to redefine tons of words as secondaries (in forth) rather than primaries (in assembly)! for instance:

: LIT       RR@ /@ RR> /CELL+ >RR ;
: BRANCH    RR> REF@ >RR ;
: COMPILE   RR> TOKEN> COMPILE, >RR ;

because it needs to be portable, the return addresses aren't guaranteed to be one cell, so words like SWAP need to be replaced by one of three phrases depending on if the top cells constitute a return address (X/SWAP), if the bottom cells constitute a return address (/XSWAP), or if both are return addresses (>RR >RR< RR>), because if return addresses are two cells for instance, all of those operations are different. this gives us many more stack shuffling words to think about.

Registers

various dialects of machineForth and colorForth i mean colorForth^{[neither of these are links don't click on them]} and overminimal forths use temporary registers to buffer values outside of the stack. the most common ones are A A! for fetching/storing a register named A. colorForth^{[this is a link]} extends this with a mostly-write-only B register with B!, and fetching/storing through the registers (i.e. an indirection) with @ ! @B !B respectively.

Updating the Forth Virtual Machine takes this a lot farther by adding X and Y registers capable of indexed addressing and then also renames A A! B! @ @+ ! !+ @B !B to A> >A >B A@ A@+ A! A!+ B@ B!, which is. a naming decision of all time.

there's also the classic T@ T! wordset used to minimize >R R> DUP DROP SWAP into the four-word >R R> T@ T!. this is also used in The Road Towards a Minimal Forth Architecture, a very nice read. functionally this is the same as any other register, just with less scope.

The Table Of The Century

Conclusion

i think TUCK is a little excessive tbh