You can systematically calculate such an approach. For simplicity, I'll consider evaluating arithmetic expressions, but the transforms are completely mechanical. I'll use Haskell as the language.
data Expr = Const Int -- This type represents the abstract syntax tree.
| Add Expr Expr
| Mul Expr Expr
-- A straight forward recursive implementation.
eval (Const n) = n
eval (Add l r) = eval l + eval r
eval (Mul l r) = eval l * eval r
Transformation 1: CPS transform
evalCPS (Const n) k = k n
evalCPS (Add l r) k = evalCPS l (\x -> evalCPS r (\y -> k (x + y)))
evalCPS (Mul l r) k = evalCPS l (\x -> evalCPS r (\y -> k (x * y)))
eval1 e = evalCPS e (\x -> x)
Already this has eliminated the need for a run-time stack. All the calls in this code are tail calls (assuming we treat + and * as primitive operations). If your implementation language supports higher-order functions, you can already use these continuations as your "stack", and you can rewrite the straight tail recursion as a while loop. However, we can apply another transformation to get a data structure which will look more like a stack.
Transformation 2: Defunctionalization
This is another mechanical transformation. We go through and replace each anonymous function (lambda) with a data constructor which will hold the free variables, and then write an apply function to interpret that data constructor as the body of the lambda it replaced. There are five lambdas, so we'll end up with five data constructors.
data Cont = Done -- This type represents the stack.
| LeftAddCont Expr Cont
| RightAddCont Int Cont
| LeftMulCont Expr Cont
| RightMulCont Int Cont
applyCont Done n = n
applyCont (LeftAddCont r k) x = evalD r (RightAddCont x k)
applyCont (RightAddCont x k) y = applyCont k (x + y)
applyCont (LeftMulCont r k) x = evalD r (RightMulCont x k)
applyCont (RightMulCont x k) y = applyCont k (x * y)
evalD (Const n) k = applyCont k n
evalD (Add l r) k = evalD l (LeftAddCont r k)
evalD (Mul l r) k = evalD l (LeftMulCont r k)
eval2 e = evalD e Done
As is always the case when you defunctionalize code in continuation-passing style, the type of continuations is isomorphic to a list. So just refactoring the above gives:
data StackFrame = LeftAdd Expr
| RightAdd Int
| LeftMul Expr
| RightMul Int
type Stack = [StackFrame]
consumeStack [] n = n
consumeStack (LeftAdd r:stk) x = evalS r (RightAdd x:stk)
consumeStack (RightAdd x:stk) y = consumeStack stk (x + y)
consumeStack (LeftMul r:stk) x = evalS r (RightMul x:stk)
consumeStack (RightMul x:stk) y = consumeStack stk (x * y)
evalS (Const n) stk = consumeStack stk n
evalS (Add l r) stk = evalS l (LeftAdd r:stk)
evalS (Mul l r) stk = evalS l (LeftMul r:stk)
eval3 e = evalS e []
Finally, refactoring to a while-loop. We can think of the two arguments of evalS and of consumeStack as being mutable variables that are being updated as we go around a loop. Haskell doesn't have mutable variables or while-loops, so I'll switch to Python.
class Const:
def __init__(self, n):
self.value = n
self.isConst = True
class Op:
def __init__(self, l, r, isAdd):
self.left = l
self.right = r
self.isConst = False
self.isAdd = isAdd
def Add(l, r): return Op(l, r, True)
def Mul(l, r): return Op(l, r, False)
class LeftFrame:
def __init__(self, expr, isAdd):
self.expr = expr
self.isRight = False
self.isAdd = isAdd
class RightFrame:
def __init__(self, n, isAdd):
self.value = n
self.isRight = True
self.isAdd = isAdd
def eval(expr):
e = expr
stk = []
n = None
while n is None or len(stk) != 0:
if not e.isConst:
stk.append(LeftFrame(e.right, e.isAdd))
e = e.left
continue
n = e.value # e is a Const
while len(stk) != 0:
f = stk.pop()
if f.isRight:
if f.isAdd:
n = n + f.value
else:
n = n * f.value
else:
e = f.expr
stk.append(RightFrame(n, f.isAdd))
break
return n
# (2+3)*((4*4)+5)
print(eval(Mul(Add(Const(2), Const(3)), Add(Mul(Const(4), Const(4)), Const(5)))))
If you really wanted to, you could add a Boolean to track whether you were in the evalS loop or the consumeStack loop and combine the two while-loops into one.
Of course, you don't have to write out each of the intermediate steps or be so mechanical about it.
