Stack Algebra

November 21, 2026 Forth Day!

Brad Nelson / @flagxor

Motivation

  • Inspired by Back and Forth - Hans Bezemer (thanks Martin Andronikos!)
  • Locals don't fit Forth
  • Shallow stacks are best
  • But we should be able to reason about stacks better
  • Are we missing an "algebra" of stack manipulation?

How to Build an Algebra

  • Find a set of "atomic" objects
  • Propose a set of rules describing how they can be manipulated while maintaining equivalence
  • Rules might require arithmetic for non-trivial algebras
  • Key Open Question: Can a small set of substitution rules connect all equivalent Forth expressions?

Which stack words are "atomic"?

I propose: DUP SWAP DROP >R R>



OVER ↔ >R DUP R> SWAP

 NIP ↔ SWAP DROP
TUCK ↔ SWAP OVER

 ROT ↔ >R SWAP R> SWAP
-ROT ↔ SWAP >R SWAP R>

RDROP ↔ R> DROP
   R@ ↔ R> DUP >R

DUP DROP ↔ OVER DROP ↔ >R R> ↔ NOP

Notation for repetition

nDROP ↔ DROPn

: nDROP 0 ?DO DROP LOOP ;  ( gets harder with other words! )

PICK and ROLL

0 PICK ↔ DUP
1 PICK ↔ OVER
n PICK ↔ >Rn DUP ( R> SWAP )n

0 ROLL ↔ NOP
1 ROLL ↔ SWAP
2 ROLL ↔ ROT
n ROLL ↔ >Rn ( R> SWAP )n

n-Operations

nDUP ↔ ( n-1 PICK )n
nSWAP ↔ ( 2n-1 ROLL )n
nDROP ↔ DROPn
n>R ↔ >Rn
nR> ↔ R>n

Doubling Operations

2DUP ↔ OVER OVER

2SWAP ↔ ROT             >R ROT             R>
      ↔ >R SWAP R> SWAP >R >R SWAP R> SWAP R>
      a b c d -- a c d b -- c d a b

2DROP ↔ DROP DROP

2>R ↔ >R >R

2R> ↔ R> R>

Build up by 2x

 2DUP ↔ OVER  OVER
2nDUP ↔ nOVER nOVER

2OVER ↔ 2>R 2DUP 2R> 2SWAP
nOVER ↔ n>R nDUP nR> nSWAP

 2SWAP ↔ >R  SWAP  R>  SWAP   >R  >R  SWAP  R>  SWAP  R>
2nSWAP ↔ n>R nSWAP nR> nSWAP   n>R n>R nSWAP nR> nSWAP nR>

2SWAP Equivalence?

nSWAP ↔ ( 2n-1 ROLL )n

2SWAP ↔ 3 ROLL 3 ROLL                        n ROLL ↔ >Rn ( R> SWAP )n
      ↔ >R >R >R R> SWAP R> SWAP R> SWAP
        >R >R >R R> SWAP R> SWAP R> SWAP
      ↔ >R >R       SWAP R> SWAP R> SWAP
        >R >R       SWAP R> SWAP R> SWAP
      ↔ >R ROT                   R> SWAP
        >R ROT                   R> SWAP
                  ?
      ↔ ROT             >R ROT             R>
2SWAP ↔ >R SWAP R> SWAP >R >R SWAP R> SWAP R>

What if we alway empty the rstack?

>R >R SWAP R>         SWAP R>   SWAP
>R >R SWAP R>         SWAP R>   SWAP

             ↔

>R >R SWAP R> R>   >R SWAP R>   SWAP
>R >R SWAP R> R>   >R SWAP R>   SWAP

             ↔

SWAP2              SWAP1        SWAP0

Layer Notation

SWAPn ↔ >Rn SWAP R>n
DUPn ↔ >Rn DUP R>n
DROPn ↔ >Rn DROP R>n
Rule S1: Swap Canceling
SWAPn SWAPn ↔ NOP
↔
Rule S2: Swap Passing
SWAPk SWAPn ↔ SWAPn SWAPk if |k-n| > 1
↔
Rule S3: Swap Flipping Doubles
SWAPk SWAPn ↔ SWAPn SWAPk SWAPn SWAPk if |k-n| = 1
↔

2SWAP Problem again

2SWAP ↔ 3 ROLL 3 ROLL                        n ROLL ↔ >Rn ( R> SWAP )n
      ↔ >R >R >R R> SWAP R>       SWAP R> SWAP
        >R >R >R R> SWAP R>       SWAP R> SWAP
      ↔ >R >R       SWAP R>       SWAP R> SWAP
        >R >R       SWAP R>       SWAP R> SWAP
      ↔ >R >R       SWAP R> R> >R SWAP R> SWAP
        >R >R       SWAP R> R> >R SWAP R> SWAP
      ↔ SWAP2                  SWAP1       SWAP0
        SWAP2                  SWAP1       SWAP0

        ...???...

      ↔ SWAP1      SWAP0 SWAP2            SWAP1
      ↔ >R SWAP R> SWAP >R >R SWAP R> R> >R SWAP R>
2SWAP ↔ >R SWAP R> SWAP >R >R SWAP R>       SWAP R>
2SWAP ↔ ROT             >R ROT                   R>
          
2SWAP ↔ 3 ROLL 3 ROLL                      ↔ ROT >R ROT R>
      ↔ SWAP2 SWAP1 SWAP0 SWAP2 SWAP1 SWAP0 ↔ SWAP1 SWAP0 SWAP2 SWAP1
↔ 
by Rule S3: Swap Flipping Doubles
↔ 
by Rule S2: Swap Passing
↔ 
by Rule S1: Swap Cancelling
↔ 
by Rule S3: Swap Flipping Doubles
↔ 
by Rule S2: Swap Passing
↔

3DUP Problem

3DUP ↔ 2 PICK  2 PICK  2 PICK         nDUP ↔ ( n-1 PICK )n
     ↔ >R >R DUP R> SWAP R> SWAP
       >R >R DUP R> SWAP R> SWAP
       >R >R DUP R> SWAP R> SWAP
     ↔ DUP2 SWAP1 SWAP0
       DUP2 SWAP1 SWAP0
       DUP2 SWAP1 SWAP0

( But this is shorter! )
3DUP ↔ >R  2DUP       R@         -ROT            R>
     ↔ >R  OVER OVER  R> DUP >R  SWAP >R SWAP R> R>
     ↔ >R  OVER OVER  R> DUP >R  SWAP >R SWAP R> R>
     ↔ >R  >R DUP R> SWAP
           >R DUP R> SWAP
                      R> DUP >R  SWAP >R SWAP R> R>
     ↔ DUP2 SWAP1 DUP2 SWAP1 DUP0 SWAP1 SWAP2
Rule D1: Dup Climbing
DUPk DUPn ↔ DUPn DUPk+1 if k≥n
↔
Rule D1: Dup Climbing (special case)
DUPn DUPn ↔ DUPn DUPn+1
↔
Rule M1: Overhead Passing
DUPk SWAPn ↔ SWAPn DUPk if k≥n+2
↔
Rule M2: Underneath Dipping
SWAPk DUPn ↔ DUPn SWAPk+1 if k>n
↔
Rule M3: Useless Duping
DUPn SWAPn ↔ DUPn
↔
Rule M4: Left Capping
DUPn SWAPn+1 ↔ SWAPn DUPn+1 SWAPn
↔
Rule M5: Right Capping (Derivable from M4)
SWAPn DUPn ↔ DUPn+1 SWAPn SWAPn+1
↔ 
3DUP ↔ 2 PICK  2 PICK  2 PICK
     ↔ DUP2 SWAP1 SWAP0  DUP2 SWAP1 SWAP0  DUP2 SWAP1 SWAP0
     ↔ DUP2 SWAP1 DUP2 SWAP1 DUP0 SWAP1 SWAP2 ↔ >R 2DUP R@ -ROT R>

by S3: Swap Flipping Doubles
by M1: Overhead Passing + S1: Swap Canceling
by M4: Left Capping
by S2: Swap Passing
3DUP ↔ DUP2 SWAP1 DUP2 SWAP1 DUP0 SWAP1 SWAP2
     ↔ >R 2DUP R@ -ROT R>                      by M4: Left Capping
Layer Notation Rules
SWAPn ↔ >Rn SWAP R>n
DUPn ↔ >Rn DUP R>n
DROPn ↔ >Rn DROP R>n   ( missing rules for DROPn & non-stack words! )

Rule S1: Swap Canceling -- SWAPn SWAPn ↔ NOP
Rule S2: Swap Passing -- SWAPk SWAPn ↔ SWAPn SWAPk if |k-n| > 1
Rule S3: Swap Flipping Doubles --
         SWAPk SWAPn ↔ SWAPn SWAPk SWAPn SWAPk if |k-n| = 1
Rule D1: Dup Climbing -- DUPk DUPn ↔ DUPn DUPk+1 if k≥n
Rule M1: Overhead Passing -- DUPk SWAPn ↔ SWAPn DUPk if k≥n+2
Rule M2: Underneath Dipping -- SWAPk DUPn ↔ DUPn SWAPk+1 if k>n
Rule M3: Useless Duping -- DUPn SWAPn ↔ DUPn
Rule M4: Left Capping -- DUPn SWAPn+1 ↔ SWAPn DUPn+1 SWAPn

Thank you!

  • Challenge #1: Can any of these rules be derived from the others?
  • Challenge #2: Can you find equivalent expressions not resolvable from these rules?
  • Challenge #3: What about DROPn, what are its rules?
  • Challenge #4: What about non-stack words?