The Fantastic SUBST Function (part 4)

This post is the final part of a series of articles about LISP, a function called SUBST, Clojure, and other interesting stuff. You probably want to read the previous posts before continuing with this.

Part 1: Introducing LISP
Part 2: Walking through SUBST
Part 3: Clojure version of SUBST

In part 1 of this series, we learned about the nine special forms of LISP, the building blocks that make up the language. In part 2, we went through how the SUBST function works on a small tree. In part 3, we rewrote SUBST in Clojure. In this part, we will look at how we can move from a recursive implementation to a sequence-based.

John McCarthy presented in 1960 his new programming language LISP. He used the SUBST function to illustrate what you could do with the language. The function performed search-and-replace in a tree. It looked something like this in traditional LISP:

(label subst
       (lambda (to from tree)
               (cond ((atom? tree) (cond ((eq? tree from) to) ('t tree)))
                     ('t (cons (subst to from (car tree))
                               (subst to from (cdr tree)))))))

The Clojure version of SUBST that we ended up with in part 3 was:

(defn subst [to from tree]
      (if (not (coll? tree))
          (if (= tree from) to tree)
          (cons (subst to from (first tree))
                (subst to from (next tree)))))

We can perform one tiny little improvement by removing the not and switching places of the clauses, like so:

(defn subst [to from tree]
      (if (coll? tree)
          (cons (subst to from (first tree))
                (subst to from (next tree)))
          (if (= tree from) to tree)))

That’s as far as I will bring the recursive version. However, if we take another look at the tree structure, we can see that it’s really just a sequence of leaves or subtrees:

(1 2 (1 2 3) 4)

If we provide a function that can handle a subtree or a leaf, we can just map that function over the sequence. If the element is a leaf, we perform the substitution, just as before. If the element is a subtree, we call the subst function again, but now with the subtree. It looks like this:

(defn subst [to from tree]
      (map (fn [subtree]
               (if (coll? subtree)
                   (subst to from subtree)
                   (if (= subtree from) to subtree)))

Let’s run through this. The anonymous function will be called once for each element of the list. First with 1, then with 2, then with the list (1 2 3), and finally with 4. When subtree is 1, line 3 says it’s a leaf and the result will be 1, according to line 5. When subtree is 2, it matches the from parameter and will be replaced with 5, also according to line 5. OK, so far we have a sequence like this:

(1 5 ...)

Now subtree is (1 2 3), so line 3 says that line 4 will be evaluated: the anonymous function makes a recursive call to subst with 2, 5, and (1 2 3). subst will now map the anonymous function over (1 2 3), resulting in the sequence (1 5 3), which is returned to the anonymous function. We now have this sequence:

(1 5 (1 5 3) ...)

Finally, the anonymous function is called with 4, which is returned unchanged. The final sequence is:

(1 5 (1 5 3) 4)

That’s all I can squeeze out of the good old SUBST function, that saw the light of day over fifty years ago. I hope you found it an interesting journey.

This Post Has One Comment

Leave a Reply