Steve's Tech Talk

Immutability

Functional programming is in.  There is a lot of buzz around the future of functional programming as applications look to leveraging multiple processors and multiple cores for their tasks.  One of the things that makes this easier is to work with immutable data structures.  Eric Lippert has written a number of thoughtful blog entries on immutability, in particular this entry on an immutable stack caught my eye.

In essence, if Eric had written this in Scheme (and my scheme is rusty, so bear with me), it would've been something like this:

(define empty-stack '())
(define stack empty-stack)
(define stack-push (lambda (a stack) (cons a stack)))
(define stack-pop (lambda (stack)
    (if (eq? stack empty-stack)
        (empty-stack)
        (cdr stack))))

(define stack-peek (lambda (stack)
    (if (eq? stack empty-stack)
        '()
        (car stack))))

(define x stack)
(define x (stack-push 'a x))
(define x (stack-push 'b x))
(stack-peek x)
(define x (stack-pop x))

So why am I bringing up Scheme?  Because Eric's code is starting to look hauntingly like Scheme and not like C#.  This is not necessarily a bad thing - there are a lot of great things to learn from Scheme.  By the way, here is a Java implementation of Scheme where you can try out that code.

I have an important semantic quibble, though.  Eric's Pop is not Pop.  Since it violates the Principle of Least Astonishment, it should have a different name.  The history of Pop indicates that two things happen - an object gets removed (and I get it) and the stack gets changed (and I get that too).  I would suggest Drop instead.  I do question the usefulness of this definition, though.  Here is some code that I have in production that is run on a stack machine:

        private void SetColorRGB()
        {
            double c3 = ((Number)stack.Pop()).Value;
            double c2 = ((Number)stack.Pop()).Value;
            double c1 = ((Number)stack.Pop()).Value;
            _g.SetColor(c1, c2, c3);
        }
So this code reads three numbers of the stack and calls a library routine to set the color.  My changed code would have to look like this:

        private void SetColorRGB()
        {
            double c3 = ((Number)stack.Peek()).Value;
            stack = stack.Drop();
            double c2 = ((Number)stack.Peek()).Value;
            stack = stack.Drop();
            double c1 = ((Number)stack.Peek()).Value;
            stack = stack.Drop();
            _g.SetColor(c1, c2, c3);
        }
 which is starting to get a little ugly.  In reality, it doesn't have to be so bad.  In my own case, I don't actually have an unprotected call to Pop in my code.  Since this is part of a stack machine, it has protective wrapping to make sure unexpected things happen and handles them with aplomb.  Therefore I could hide the lower-level implementation of IStack from the world and use wrapper methods.

Things that need to be in the definition of stack, however, include some more real-world usage methods:

• dup (duplicate the top most entry) - in Eric's definition, this will be return Push(Peek());
• Swap (swap the top two items) - in Eric's definition, this is more difficult - you'd need a peek, a pop, a peek, a pop and two pushes.
• Depth (returns the total number of items) - this is easy you would have an immutable int which is incremented on push
• Index (get the nth item) - you have rip n Pops then a peek

There are some more esoteric ones like Roll, Over and so on.  The problem I see is that anything that is beyond the simplest definitions starts to get disproportionately complicated.

Yes, there are clear benefits to the immutability, but we start to get further and further from the world where push and pop were a single instruction and that bothers me. It's also the reason why languages like Scheme even have back doors to allow coders to violate immutability via set!, set-car! and set-cdr!