# How to keep track of changes done to concurrent stacks?

I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions:

add-int(a: int, b: int): a b +
add-float(a: float, b: float): a b +


and I have two stacks with the following:

Int [1 2 3]
Float [4.0 5.5]


I can just do:

add-int add-float


and the new stacks will be:

Int [1 5]
Float [9.5]


Everything works well there, but if I were to add parametric polymorphism with this function:

add-num(a: num, b: num): a b +


Then it would not work as one would expect. Is it going to add the two integers or the two floats? or perhaps one from each?

To solve the issue, I added a new stack Num that keeps the address of every number pushed into the other stacks to keep a sense of history, but it created two new issues.

First, memory addresses take a lot of space, sometimes more than the data itself, and this would only get worse if I were to add new number types like ratios and complex.

Second, what if I wanted to pop a number that is on top of the stack for its type but way behind in the Num stack.

For example:

> 1 2 3.14 4.0 5/5  -- This is the expression.
Int [1 2]  -- These are the stacks.
Float [3.14 4.0]
Ratio [5/5]
Num [&Int &Int &Float &Float &Ratio]

> add-int  -- Then I do this.


If I call the function above, there is no issue popping the two integers, but what about deleting the two pointers in the Num stack? It can get pretty expensive to look for the element and remove it every single time a number is popped.

I have realized that this approach is not pretty effective in terms of space consumption and performance, so is there an alternative, more efficient way of keeping track of the changes done to these stacks?

• Your add-num function isn't parametrically polymorphic which is part of why you are having the problem. If you really wanted to pursue this, you could use Haskell-like type classes at which point add-num would become add-int or add-float as appropriate based on the (static) type. Jun 2, 2018 at 2:02
• @DerekElkins what if the function were to take an int and a float? Jun 3, 2018 at 13:54
• It would fail to type check at "compile"-time. At least if you defined the type class in the most straightforward way. Unless you have an add-int-float function, this is what you want. Jun 3, 2018 at 18:50

Node = {
type : "INT" or "FLOAT"
value : int or float
prev-generic : pointer to Node
next-generic : pointer to Node
prev-specific : pointer to Node
next-specific : pointer to Node
}


Now you can keep three lists: a list of ints (using the specific pointers), a list of floats (using the specific pointers), and a list of both (using the generic pointers). If you keep track of the head of each list, you can treat them as stacks (pushing and popping in $O(1)$), and a popped node can also be deleted from both stacks in $O(1)$ just like in a normal doubly-linked list.

• I ended up using singly-linked lists and an external counter. Your example works, but it takes too much memory per node. Jun 3, 2018 at 13:58