Scheme to Clojure Function (subst)

Question

I am reading Paul Graham's The Roots of Lisp

I have tried converting the function subst on page 5, which is defined like this:

(defun subst (x y z)
  (cond ((atom z)
         (cond ((eq z y) x)
               ('t z)))
        ('t (cons (subst x y (car z))
                  (subst x y (cdr z))))))

To its corresponding Clojure implementation. I do not have production experience in either languages (I have been reading Clojure), so any help would be appreciated since I am reading this to understand the roots of LISP. The closest I came to was this (but it is horribly wrong):

(defn subst
 [x y z]
 (if (not (nil? z)) z x)
     (if (= z y) x z)
    (cons (subst x y (first z))
          (subst (x y (rest z)))))

Answer 1

"Traduttore, traditore"

(This can be translated as "translator, traitor", but doing so ruins the pun, which is fun in itself)

It is hard to hint at possible fixes in your Clojure code because the specification is unclear: if you follow the The Roots of Lisp to the letter, you are going to implement a Lisp on top of Clojure, and subst might be similar to the one in the book. But if you want to implement subst as commonly used in Lisp, the code shown here won't do it.

Even though Clojure has cons and nil? functions, they do not mean the same as in Common Lisp (resp. cons and null): See clojure: no cons cells for details. Before you can translate subst, you have to determine what is the idiomatic thing to do in Clojure.

Typically subst is used to transform a tree, made of cons cells; note for example that subst does not recurse into vectors, strings, etc. Among those trees, a particular subset of trees are those which are Lisp forms. In fact, one important use case for subst is to search-and-replace forms during code generation.

If you restrict yourself to the Clojure Cons type, you won't support code as data, as far as I know. Since Clojure code also uses vectors and maps, you probably need to recurse into such objects. So, how to translate subst is not an easy problem to specify.

A possible starting point is to read LispReader.java to determine the set of objects that constitute an AST, and see what kind of code walking you want to do.

My advice would be to study those languages independently first. With a bit of experience with each, you will have a better way to see how similar and how different they are with each other.

Answer 2

the translation of the scheme version could possibly look like this:

(defn my-subst [new old data]
  (when-not (nil? data)
    (cond (sequential? data) (cons (my-subst new old (first data))
                                   (my-subst new old (next data)))
          (= data old) new
          :else data)))

user> (my-subst 1 :x '(1 2 :x (:x 10 :x [:x :z :x])))
;;=> (1 2 1 (1 10 1 (1 :z 1)))

this is quite close (though not exactly the same, since there are more than one native collection type, which makes you face the choice: which ones should be considered to be the targets to substitution). This example handles 'listy' (sequential) structures, while omitting hash maps and sets. Another problem is retaining the type AND form of the original sequence, which is not really as trivial as it sounds (e.g (into (empty (list 1 2 3)) (list 1 2 3)) => (3 2 1)

So what you have to do, is to first decide the semantics of the substitution, while in scheme it is just a natural list processing.

As of clojure.walk which has already been mentioned, the simplest way to use it for substitution could be

(defn subst [new old data]
  (clojure.walk/prewalk-replace {old new} data))

user> (subst :z :x [1 :x 3 '(:x {:a :x}) #{:x 1}])
;;=> [1 :z 3 (:z {:a :z}) #{1 :z}]

Answer 3

This is how I would do it, including a unit test to verify:

(ns tst.demo.core
  (:use tupelo.core tupelo.test)
  (:require [clojure.walk :as walk]))

(defn subst
  [replacement target listy]
  (walk/postwalk (fn [elem]
                   (if (= elem target)
                     replacement
                     elem))
    listy))

(dotest
  (is= (subst :m :b [:a :b [:a :b :c] :d])
    [:a :m [:a :m :c] :d]))

However, I would not spend a lot of time reading 40-year old texts on Common Lisp, even though I think Paul Graham's book Hackers & Painters is quite mind blowing.

Clojure has evolved the state-of-the-art for lisp by at least one order-of-magnitude (more like 2, I would say). Major improvements include the use of the JVM, persistent data structures, concurrency, syntax, and data literals, just to name a few.

Please see this list of Clojure learning resources, and maybe start with Getting Clojure or similar.

---

Update

More from Paul Graham on Clojure