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[0] &Int[1] &Float[0] &Float[1] &Ratio[0]]

> 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?

  • $\begingroup$ 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. $\endgroup$ – Derek Elkins left SE Jun 2 '18 at 2:02
  • $\begingroup$ @DerekElkins what if the function were to take an int and a float? $\endgroup$ – Joan Vene Jun 3 '18 at 13:54
  • $\begingroup$ 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. $\endgroup$ – Derek Elkins left SE Jun 3 '18 at 18:50

I would use doubly-linked lists instead of opaque stacks for this.

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.

| cite | improve this answer | |
  • $\begingroup$ I ended up using singly-linked lists and an external counter. Your example works, but it takes too much memory per node. $\endgroup$ – Joan Vene Jun 3 '18 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.