Stack Quarks

Rob Chapman

Abstract

This paper discusses a two-item stack model and its six fundamental operations called stack quarks. These fundamental operations are like quarks of matter, truly fundamental. They may not be factored any further. Combinations of these stack quarks can be used in a language for describing data flow. When building compilers for stack based languages, phrases of stack macros may be broken down into stack quarks and simple optimizing rules may be applied. At the end of this paper, some optimization rules are modeled in Timbre.

Quarks and Stacks

Particle scientists in the search of the fundamental pieces of matter, have found six elementary particles which when combined, form matter (basically). These elementary particles are called quarks. Given a limited number of particles, there should be a particular set of rules which describes their combinations that produce the physical world we live in.

The same factoring can be applied to a model. If we look at a two-item stack model which has a stack, a next register and a top register, we find that there are six fundamental operations. These six operations are like the matter quarks as they can be combined to form more complex stack operations for stack based algorithms. Interestingly, they can be grouped in pairs and they carry a charge.

First Things

Stacks are fundamental to us as children. As we play, we learn how many blocks we can stack up before we get an overflow, and crash. We build and operate the stack with two hands. Therefore it is natural for us to think of a two item stack model.

FIGURE 1. Two item stack model with its data flows.

Top and next may be picked off the top of the stack with both hands. They may be set back as they were, (Uncertainty Principle: now what the heck is on the stack? or, what was I doing?), swapped or coact with the stack. For instance, if we pick up top and next, put next down (store it somewhere in RAM) and then pick up an item off the stack, we have a new next and the number of items in the model has decreased by one. Same for top. Top, next, and the stack interact to execute stack-based algorithms and computations.

Stack Quarks

The stack quarks are the singular operations which describe all the operations between the stack, top and next. In considering the simplest operation, it can only be a single data movement. For certainly anything less than this would be no action.

The stack quarks are:

FIGURE 2. Six stack quarks and their associated charge and spin.

DRIP and DIP have no charge (S0) since there is no net gain or loss in the number of items kept. The other four operations carry a charge which reflects whether there is an increase (S+) or decrease (S-) in the overall numbers of items. The overall charge in each pair is zero. DRIP and DIP are the operations which may be used to copy items between top and next. NIP and NUP pop or push the stack to and from next. TAKE and TUCK pop and push the stack to and from top.

A Stack Computer

FIGURE 3. Computing unit attached to a stack to form a stack computer.

Top and next are available as input and output registers to a computing unit which can perform functions like add, subtract, multiply, shift, logic, etc.. The stack is available to top and next for keeping intermediate values in computing unit sequences.

Stack Macros

Stack macros are used as parts of a language for a stack computer to describe operand behaviour in computations and algorithms.

The following rules are part of a Timbre1 script which will translate stack macros into fundamental quarks of the two item stack model and then do some peephole optimization.

 
( ==== Stack macros ==== )
      1)  { DUP2   }{ NUP  DRIP }         ( net stack increase, S+ )
      2)  { DROP2  }{ DIP  NIP }          ( net stack decrease, S- )
      3)  { SWAP2" }{ DIP || DRIP }       ( || means in parallel; )
      4)  { SWAP3  }{ DUP  TAKE }         ( no net stack change, S+  S- )
      5)  { SWAP3  }{ TUCK  DROP }        ( yet another similar definition )
      6)  { OVER4  }{ NUP  SWAP }         ( net stack gain, S+ )
      7)  { OVER3" }{ NUP || DIP || DRIP } ( or in parallel )

    Script 1. These Timbre rules are the definitions of the four stack macros in terms of the stack quarks. The superscript number signifies the quarks needed to define the macro. The quote signifies that they run in parallel. Some rules are redundant but are there for interest to describe other ways of creating the same macro.

( form: { Phrases }{ to match }{ replacement }   ( originally ; after )
      8)   { SWAP SWAP }                                ( 6 )
      9)   { OVER DROP }                                ( 6 )
      10)  { NUP  NIP  }                                ( 2 )
      11)  { TUCK TAKE }                                ( 2 )
      12)  { DUP  DROP }{ }                             ( 2 ; 0 )
      13)  { DIP  DIP  }                                ( 2 )
      14)  { DIP  DRIP }{ DIP  }                        ( 2 ; 1 )
      15)  { DRIP DRIP }                                ( 2 )
      16)  { DRIP DIP  }{ DRIP }                        ( 2 ; 1 )
      17)  { SWAP DROP }{ NIP }                         ( 5 ; 1 )
      18)  { SWAP OVER }{ TUCK }                        ( 7 ; 1 )
      19)  { SWAP DUP  }{ TUCK DIP }                    ( 5 ; 2 )
      20)  { OVER SWAP }{ NUP }                         ( 7 ; 1 )
      21)  { OVER OVER }                                ( 8 )
      22)  { 2DUP      }{ NUP TUCK }                    ( 8 ; 2 )
      23)  { OVER DUP  }{ NUP TUCK DIP }                ( 6 ; 3 )
      24)  { DUP  DUP  }                                ( 4 )
      25)  { DUP  OVER }{ NUP DRIP NUP }                ( 6 ; 3 )
      26)  { DUP  SWAP }{ DUP }                         ( 5 ; 2 )
      27)  { DROP DROP }                                ( 4 )
      28)  { 2DROP     }{ TAKE NIP }                    ( 4 ; 2 )
      29)  { DROP SWAP }{ TAKE }                        ( 5 ; 1 )
      30)  { DROP OVER }{ TAKE TUCK }                   ( 6 ; 2 )
      31)  { NIP  DUP  }{ DRIP }                        ( 3 ; 1 )

    Script 2. These Timbre rules are some optimizations to improve the code production. The numbers at the end of the line represent how many quarks are used by the initial phrase and what it is reduced to.

When running source code through the translation rules, the stack macros are reduced to quarks and then any quark sequences which appear in the optimization rules, executes, further simplifying the source code. Finally, the quarks will have rules to translate them into target code, whether it is logic, symbolic, binary or another programming language.

An Example

If we take the sequence DROP DUP, and expand it into its quark sequence, we will see how it can be reduced to something simpler (if we only had the stack macros, then we would not be able to reduce the phrase any further since this simplification ends up as a stack quark).

FIGURE 4. Phrase reduction of DROP DUP produces DIP. The shaded ones are in identical stack situations. Pictorially, it is easy to see what to factor out.

The rules in script 1 and 2 are used to illustrate the optimization of the phrase DROP DUP. Rule 2 executes to translate the DROP into DIP NIP. Rule 31 execute to translate NIP DUP into DRIP and we are left with DIP DRIP. Then rule 14 executes to reduce the phrase to just DIP.

Code Generation

The outcome of the translation could be to a target language or machine. We will define the quarks for the case of the target language C. We will assume a two-item stack model:

    Cell top, next, *sp;    /* two item push-down stack model */

The following six Timbre translations will be used to map the stack quarks:

      32)  { DIP  }{ top   = next  ; }
      33)  { DRIP }{ next  = top   ; }
      34)  { NUP  }{ *--sp = next  ; }
      35)  { NIP  }{ next  = *sp++ ; }
      36)  { TUCK }{ *--sp = top   ; }
      37)  { TAKE }{ top   = *sp++ ; }

    Script 3. Stack quarks defined in target generation language, C.

Musings

We have seen how we can take a two-item stack model and break it down into its simpler quarks and then use quarks in the defining and optimization process for translating source code.

Interestingly, the quarks may be defined by the macros. In essence, this makes them a complete set, nothing can be created out of the set, which is not already in it.

This paper sparked a working group on finding other quarks for the rest of the computing unit. It was felt that these new quarks held the same power in terms of defining higher order operations and allowing for efficient compilation as the ones in this paper.

As we try to understand what is around us, we play with different factoring so that we can better grasp the whole and the pieces.

A PDF version of the original paper is also available.


1. "It Has Timbre", Rob Chapman, Rochester conference 1994.