cdiggins.com

Most of a stack program involves the manipulation of the order of elements on the stack, so it can make programs pretty involved. For example if we were to emulate the effect:

abc -> abac

It would require a sequence of operators such as: 

[[dup] dip swap] dip]

Looking at the code snippet, it is not clear what is happening without some kind of comment. This can make stack-based programs exhausting to read.

One solution is to use a set of functions with a particular naming convention that represents what happens. For example the code snippet above would be defined as:

def abac { [[dup] dip swap] dip }

Notice that the name represents what the operation to a stack containing the elements a, b, and c, on top. Interestingly consider:

def aba { [dup] dip swap }

Which would alternatively allow the definition:

def abac { [aba] dip }

That being said, this naming convention is only unambiguous when the operation are assumed to either shuffle and/or duplicate stack items.

Here is a list of operations and their definitions for rearranging two or three stack items (*warning* these haven’t been tested yet)

def aa { dup }

def ab { [id] dip }
def bb { pop dup }
def ba { swap }

def aaa { pop dup dup }
def aab { [dup] dip }
def aba { [dup] dip swap }
def baa { swap dup }
def bba { swap [dup] dip }
def bab { dup rot3up }
def abb { ab dup }
def bbb { [pop] dip dup dup }

def abc { [[id] dip] dip }
def acb { abc swap }
def bca { rot3down }
def bac { [swap] dip }
def cab { rot3up }
def cba { swap rot3down }

def aabc { [aab] dip }
def aacb { acb aabc }
def bbac { bac aabc }
def bbca { bca aabc }
def ccab { cab aabc }
def ccba { cba aabc }

def abac { [aba] dip }
def acab { acb abac }
def babc { bac abac }
def bcba { bca abac }
def cacb { cab abac }
def cbca { cba abac }

def abcc { abc dup }
def acbb { acb dup}
def bcaa { bca dup }
def bacc { bac dup }
def cabb { cab dup }
def cbaa { cba dup }

def abca { [[dup] dip] dip] rot4down }
def cabc { cab abca }
def bacb { bac abca }
def cbac { cba abca }
def bcab { bca abca }
def acba { acb abca}

def abbc { [dup] dip  }
def bcca { bca abbc }
def cbba { cba abbc }
def caab { cab abbc }
def accb { acb abbc }
def baac { bac abbc }

Of course, many of these have more efficient implementations, but optimizing stack shuffling operations is probably a job best left to a compiler.

 

This entry was posted on Tuesday, January 9th, 2007 at 4:33 pm and is filed under Everything. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.