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

coredump · Answer 1 · 2020-04-10T08:04:41.440

4

"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.

edited Apr 10 '20 at 08:04

answered Apr 06 '20 at 14:30

coredump

37,664
5
43
77

Thank you, but I suppose I am asking how it could be implemented in Clojure. The original question in that paper was: Suppose we want to define a function subst, which takes an expression x, an atom y and a list z and returns a list like z but with each instance of y (at any depth of nesting) in z replace by x. I appreciate your help and points - – tweeterist Apr 06 '20 at 15:29
3

@tweeterist Your followup question ignores much of coredump's answer. You can't implement it, because you haven't specified it yet. The original idea makes sense in common lisp, but the data structures it operates on are not the same as those in clojure, and you have to decide what it should actually do. Clojure values are not usefully partitioned into "lists" and "non-lists" like lisp values. – amalloy Apr 06 '20 at 17:31
@amalloy I think you are patently wrong, as the answer below this one shows. I just want a close enough implementation, not someone to remind me that it can't be done. And I did not ignore his answer, I just refused to take it that it cannot be done - and I am not sure what you mean by specify. Anyhow, let me study the answer below as it is a better use of my time - – tweeterist Apr 06 '20 at 18:12
1

@tweeterist Just to clarify the part about "specifiy": I am not saying it cannot be done, I am asking what "it" means when we say "can "it" be done'? (1) the definition from the book can be replicated in Clojure, you'll end up with a "subset of Lisp implemented in Clojure" (2) the Common Lisp version of "subst", translated in a useful way in Clojure needs a different approach (see other good answers). That's all. – coredump Apr 06 '20 at 22:59
That is what I was looking for. I am well aware that implementations cannot be ported verbatim into different languages owing to different axioms in different languages. Again, like I said, I have gotten what I wanted, thank you for you efforts. – tweeterist Apr 07 '20 at 08:53

score 3 · Answer 2 · answered Apr 06 '20 at 19:08

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}]

This is a niftier solution – tweeterist Apr 06 '20 at 19:49 — tweeterist, Apr 06 '20 at 19:49

Alan Thompson · Accepted Answer · 2020-04-22T03:54:45.083

-2

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.

Scheme to Clojure Function (subst)

3 Answers3

"Traduttore, traditore"

Update