4. Example 1: A stack machine

A: Consider a stack machine for computing expressions given in reverse Polish notation, or RPN. An expression (1 + 23) * (45 + 6) written in RPN would appear as

1 23 + 45 6 + *

Q: Are you talking about arithmetical operations over integers?

A: Not necessarily. Suppose we have a nonempty set Data and a nonempty set Oper of (for simplicity) total binary operations on Data. For example, Data may be the set of integers and Oper may be {+, *}. We suppose that the RPN expression is given to us in the form of a list where each entry denotes a datum or an operation. The stack machine reads one entry of the list at a time from the input file. If the entry denotes a datum, it is pushed onto the stack. If the entry denotes an operation, the machine pops two items from the stack, applies the operation and pushes (the notation for) the result onto the stack. At the beginning, the stack is empty. In the case of the RPN expression above (with the usual operations), the stack goes through the following states: (), (1), (23 1), (24), (45 24), (6 45 24), (51 24), (1224).

The desired evolving algebra has Data and Oper as universes. Arg1 and Arg2 are distinguished elements of Data. To handle operations in Oper, the EA has a ternary function Apply such that Apply(f,x,y) = f(x,y) for all f in Oper and all x, y in Data. To handle the input, the EA has a universe List of all lists composed of data and operations. The basic functions Head and Tail have the usual meaning. If L is a list then Head(L) is the first element of L and Tail(L) is the remaining list. EmptyList has the obvious meaning. F is a distinguished list. Initially, F is the input. Finally, the evolving algebra has a universe Stack of all stacks of data with the usual operations Push (from Data x Stack to Stack), Pop (from Stack to Stack) and Top (from Stack to Data). S is a distinguished stack. Initially, S is empty.

Q: Since the stack machine deals with only one list and has only one stack, I do not understand why you need the universes List and Stack.

A: The EA should be on the abstraction level of the given algorithm. Operations like Push and Pop should be provided with their natural environment. We can manage without the universes List and Stack by implementing the input and the stack as arrays, but this would be a lower level of abstraction. Here are the transition rules.

if Head(F) is a datum then
   S := Push(Head(F),S)
   F := Tail(F)
endif

if Head(F) is an operation then
   if Arg1 = undef then
      Arg1 := Top(S)
      S := Pop(S)
   elseif Arg2 = undef then
      Arg2 := Top(S)
      S := Pop(S)
   else 
      S := Push(Apply(Head(F),Arg1,Arg2),S)
      F := Tail(F)
      Arg1 := undef
      Arf2 := undef
    endif
endif

The phrase ``Head(F) is a datum'' means of course that Head(F) belongs to Data, i.e., Data(Head(F)) = true. The meaning of the phrase ``Head(F) is an operation'' is similar.

Q: You suppose that the input file contains a legal RPN expression.

A: That is true. When a given algorithm has an error handling routine, it can be formalized as well.

Q: Assume that there is a bound Max on the depth of the stack. What changes should be made?

A: Let me suppose for simplicity that the machine simply freezes if it attempts to push a datum onto a stack of the maximal depth. Then you may want to introduce a universe of natural numbers with successor operation n+1 and predecessor operation n-1 and distinguished natural numbers Depth and Max. Initially, Depth is zero. Augment the guard of the first of the two rules above by the conjunct Depth <Max and add updates Depth := Depth + 1 or Depth := Depth - 1 in appropriate places.