Traversing objects functionally

By: on March 7, 2011

Like Tim, I’ve been playing around with zippers recently, only I’ve been working in Smalltalk. In particular, I’m trying to explore how easy it is to work with objects in a fully functional way [1]. With that in mind, I’m working within certain constraints, most important of which is “thou shalt use immutable data structures”.

This is Smalltalk, so we can’t actually have immutable objects. Rather, we can’t enforce immutability. Some dialects do support immutability, thanks to support from the virtual machine. I’m working in Squeak, though. So what do we do?

First, no setters.

In Haskell, you might say

  let myTree = Node a b

but in Smalltalk it’s all encapsulating objects all the time. When you create a new instance you have no opportunity to directly set its instance variables, except through state-setting methods. We’re doomed to failing the “no setters” rule. So we do the next best thing: only allow private [2] state-setting methods, analogous to a constructor. You can have multiple state-setting methods, but since we’re relying on discipline to enforce functional methods, the fewer state-setting places we have to remember the better. Your other constructor methods might for instance call a canonical state-setter with default values.

For example, our to-be-zipped-on object, ZTree, has instance creation methods:

ZTree class >> value: anObject
    ^ self new value: anObject children: OrderedCollection new.

ZTree class >> value: anObject children: aCollection
        ^ self new value: anObject children: aCollection.

and the actual state-storing setter:

ZTree >> value: anObject children: aCollection
        value := anObject
        children := aCollection.

No other methods may set instance variables. Note that I opted here for a single state-setting method, and two constructors on the class side; one of the constructors supplies a default value.

Second, all “mutating methods” return mutated copies of an object. ZTree‘s so simple that it doesn’t have an example of what that looks like. So instead let’s look at the TreeZipper. The TreeZipper can navigate down, up, left and right through a tree. TreeZipper implements a handful of methods per navigation direction. The core method of each navigation is called #safeFoo. For instance:

TreeZipper >> safeDown
"Return a pair whose first element tells us whether we successfully went down
(represented by the value #success), and a Zipper. If yes, a Zipper focusing
on the first child element of this node. If not, a Zipper focused on where we

| success zipper |
success := self focus children isEmpty
    ifTrue: [ #downAtLeafNode ]
    ifFalse: [ #success ].

zipper := (success = #success)
        [self class new
            focus: focus children first
            trail: (TreeZipperNode
                path: trail
                value: focus value
               leftNodes: OrderedCollection new
                rightNodes: focus children allButFirst)]
    ifFalse: [ self ].

^ {success. zipper.}

As you can see, each #safeFoo returns a pair, the first element indicating whether navigation succeeded, and the second containing the zipper at that new position, or the original zipper. (“Down” means “focus on the left-most of my children nodes”.)

Next, we have the usual exception-raising method when you’re either (a) sure you can move in a certain direction, or (b) only care that you either move to a particular place or fail:

TreeZipper >> down
    "Return a Zipper focusing on the first child element of this node."
    ^ self move: #safeDown.

Huh? What’s that #move:? Well, it turns out that all four navigation methods have the same basic structure:

TreeZipper >> move: directionSelector
    "Move in some direction. If we fall off the data structure, raise an exception."
    | move |
    move := self perform: directionSelector.
    move first = #success ifFalse: [ ^ ZipperNavigation signal: move first ].

    ^ move second.

Note the call to #perform:. When sent to a receiver rcvr – rcvr perform: #aSelector – it means “rcvr, please run the method called aSelector“. It’s a very powerful tool, and allows one to do all sorts of nifty things (like extract the basic pattern out of a bunch of methods that vary only on the name of a particular selector) but also allows one to do really stupid things: self perform: ('this', 'Obfuscated', 'Selector) asSymbol. Now just try find all the callers of #thisObfuscatedSelector!

Lastly, as a kind of conditional, we have:

TreeZipper >> downOrElse: aBlock
    ^ self move: #safeDown orElse: aBlock.

TreeZipper >> move: directionSelector orElse: aBlock
    "Move in some direction. If we can't, run aBlock. If aBlock takes parameters,
    pass in the current focus as an argument."

    | move |
    move := self perform: directionSelector.
    ^ move first = #success
        ifTrue: [ move second ]
        ifFalse: [ aBlock cull: self focus ].

We either return self or a whole new zipper (thanks to #safeDown). Note again how #perform: allows us to abstract the essentials.

Another interesting tidbit: #cull: sent to a block means “if this block takes zero arguments, evaluate the block; if it takes more than one, evaluate the block with the parameter given.” That allows us to give #downOrElse: either a nullary block – [ Transcript showln 'Help, down failed!'] – or a unary block – [:node | Transcript showln: 'Down failed at value ', node value printString ].

With this as a base, we can then build more interesting things – traversal strategies, or binary search trees.

[1] I’m keenly aware that like most terms, “functional programming” means different things to different people. I’m going with “programming in a side-effect free way”, or “state’s stored in the stack / avoid mutable data”. I’ve found that people who think I’m crazy and that functional programming and object oriented programming are incompatible usually mean “objects are not ADTs”. William Cook writes a lot on this topic, but it doesn’t help that some academics say “functional” when they mean “ADT”.

[2] “Private method” in Smalltalk means “a method in the category called ‘private'” but it’s not any more private than any other method. That it’s in ‘private’ serves as a warning to you: “use this method, and bad things might happen to you”, but there’s nothing stopping you from using the method anyway.


Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>