gensym

[dubek]

(Following discussion in #103)

Here's a pure mal gensym implementation, and an implementation of the or macro (called or2 below) with gensym:

(def! incr (fn* [x] (+ 1 x)))

(def! *gensym-counter* (atom 0))

(def! gensym
  (fn* []
    (symbol (str "G__" (swap! *gensym-counter* incr)))))

;;
;; test `or` implementation with `gensym` instead of `or_FIXME`
;;
(defmacro! or2
  (fn* (& xs)
    (if (empty? xs)
      nil
      (if (= 1 (count xs))
        (first xs)
        (let* (condvar (gensym))
          `(let* (~condvar ~(first xs))
             (if ~condvar ~condvar (or2 ~@(rest xs)))))))))

(prn (macroexpand (or2 nil "yes")))
(prn (or2 nil "yes"))

(prn (macroexpand (or2 "yes" false)))
(prn (or2 "yes" false))

Output:

(let* (G__1 nil) (if G__1 G__1 (or2 "yes")))
"yes"
(let* (G__3 "yes") (if G__3 G__3 (or2 false)))
"yes"

It relies on atom, so cannot be used in step 8 where we test the or and and macros (atom is added in step A).

Do you prefer a native impl in step 8, with all the quote special operators?

[dubek]

And here's a with-gensyms macro (adapted from Practical Common Lisp http://gigamonkeys.com/book/macros-defining-your-own.html):

(def! flatten1
  (fn* [lst]
    (if (empty? lst)
      lst
      (concat (first lst) (flatten1 (rest lst))))))

(defmacro! with-gensyms
  (fn* [tmp-vars body]
    (let* [let-args (flatten1 (map (fn* [v] (list v '(gensym))) tmp-vars))]
      `(let* ~let-args ~body))))

So if we need 3 temporary variables in a macro, we can use:

user> (macroexpand (with-gensyms [a b c] (if a b c)))
(let* (a (gensym) b (gensym) c (gensym)) (if a b c))

[kanaka]

Okay, a few options:

1. make it a native function. This would be pretty simple in most languages.
2. Move atoms and atom tests from stepA to step8.
3. Use a simpler but less efficient version of the or macro in step8 and step9, define gensym in stepA and update the definition of the or macro to use it.

I think 1 would be pretty simple in most languages (except languages like Haskell where you basically don't have globals). However I do like having "gensym-counter" as a user accessible symbol in the environment, and you certainly wouldn't want a new type to be introduced to wrap a stateful value just to avoid atoms until stepA.

For 2, step8 generally isn't that large, especially since it's fairly similar in some ways to step7. So step8 would still be inline with the size/difficulty of the other steps. So this isn't a terrible option (a lot of tedious updates though).

In the end though, I think I prefer 3. It's simple, it exposes the "gensym-counter" symbol using the standard mutable reference (atoms) and I think it also provides a good teaching opportunity (i.e. "here is a better way of writing the or macro now that we have gensym").

So for 3, here is the less efficient version of or that calls (first xs) twice:

(defmacro! or (fn* (& xs) (if (empty? xs) nil (if (= 1 (count xs)) (first xs) `(if ~(first xs) ~(first xs) (or ~@(rest xs)))))))

What do you think?

Maybe we should start a examples/macros.mal file for interesting macros (like with-gensyms)?

[dubek]

I'm good with option 3.

Just to clarify:

1. In step8, the guide says: use "rep" in the main program to define the two macros cond and or. So at this point we should modify the macros to use the simpler/inefficient version you mention above (fix the guide, and slowly fix all existing impls - in step8 and step9).
2. In stepA - add rep("defmacro! gensym .....") etc and fix the existing or macro.
3. Add a stepA test that verifies the new or macro (makes sure the arguments are only evaluated once - by checking side effects).
4. In tests of step8 don't load ../core.mal; instead, define the and macro in the tests.
5. Fix core.mal to use gensym whenever needed.

Once we have gensym, we can have the examples/macros.mal with with-gensyms and defined? macros ( (defmacro! defined? (fn* [sym](try* (do ~sym true) (catch* _ false))))` ).

If you approve, I can take try to craft a PR with those changes (probably not today).

[kanaka]

So I wrote up some notes (included below), but in thinking through it some more, I think I'm actually reconsidering the options :-( The use of gensym is specifically related to macros. So thinking more about it, I think I do want to keep it with step8.

Option 1 remains my least favorite (due to requiring a new type implementation), but I think something more like option 2 is now my preference. Since atom types are implemented in types/core modules (which are shared between steps), most implementations should be able to support atoms at an earlier step without much fuss. In fact, atom type support could could be moved even earlier than step8. I'm actually leaning towards putting them as step6 optionals. There are a couple of reasons for this. step6 is small step in terms of test size and implementation difficulty. But more importantly, step6 plus the atom type would in many ways be complete (albeit simple) Lisp. In fact, with a few additional core functions listed in later steps, step6 plus atom support could be self-hosted (the mal implementation would look somewhat different and more complicated because it wouldn't have the luxury of the "or"/"cond" macros or metadata).

As you can see, I'm still sort of mulling this over and open to any thoughts on it. Also, whatever change we make, it's not set in stone of course (I've made many restructurings in the past and I'm sure will continue to do so into the future), but with 44 implementations, it does get more tedious to change things that affect all the implementations.

If you buy into my reasons for step 2, here is what I think would be needed:

1. Move atom tests to from stepA to step6 (or step8 or a different step if we decide it makes more sense). The "Testing hash-map evaluation and atoms (i.e. an env)" tests should go to the step9 "optional but needed for self-hosting" test section.
2. Add gensym function and update "or" definition in step8,9,A and add gensym step8 tests.
3. Update core.mal definitions of "and" and "or" to use gensym
4. Update the guide and guide diagrams (I'll do this if we decide to go this route)

Sorry for going back and forth on this. Thoughts?

---

---

Original response regarding step 3:

Yep, I think that basically covers it. Additional thoughts:

1. The fixing of steps 8 and 9 could probably done all at once. I suspect a couple of sed commands (to capture differences in quoting and escaping) could translate all of them.
2. You said "defmacro! gensym" but I think you just meant for it to be a function as in your first example
3. Yep
4. I think we can just move the loading of core.mal and the "and" and "->" tests to stepA.

[dubek]

I tried the atom tests on Ruby step 6 impl. It works except:

1. quote in the last test - we need to change '(1 2 3) to (list 1 2 3)
2. tests with assoc/dissoc will not be possible because these are added in step9 (right now they pass but it's because I see the final core.rb which has assoc and dissoc).

I think your idea (moving atoms to step 6) is OK. I wonder if we lose anything in terms of "look, we have a language with almost-only immutable data types" if we introduce atoms earlier.

[kanaka]

Sorry for the slow reply.

Yep, the tests labelled ";; Testing hash-map evaluation and atoms (i.e. an env)" will need to go no earlier than step9 since that's where we add hash-map functions.

I'm not too concerned about having atoms earlier in the process. It will actually give an earlier opportunity to emphasize the importance of immutability in the guide and describe atoms as the escape hatch when you absolutely need mutable state (and also to note that only the reference to data is mutable, not the data itself).

You want to tackle a PR for that? I would do it but I'm moving and also have several school projects that I have to finish in the next 1.5 weeks.

[dubek]

I'll take it, though it'll take me a few days as well.

BTW, regarding immutability (just making sure I understand the ideas correctly): we do have def! which mutates local state/binding. It is not "write-once" - you can (def! x 7) and later (def! x 8). But def! cannot be used inside a function to modify a binding in an outer env (such as the global *gensym-counter* I declared at the top of this thread), and therefore you need to resort to atom to achieve mutation.

[kanaka]

@dubek yes, that's true that there are two different forms of mutable state supported by mal: environments (modified by def!), and atoms (modified by reset! and swap!). One place where mal diverges a bit from Clojure (and other Lisps for that matter) is that I wanted all types of mutating functions to be clearly identified with a "!" suffix. In Clojure for example, def* forms mutate the current namespace but the mutating nature is not explicitly identified with a "!". I suspect one reason that def/defines are not marked as mutating is that normal code doesn't often redefine things in a namespace after the first definition (you usually want to avoid that IMO). In Clojure atoms, refs and agents are all reference types that enable mutation but each one has different properties especially as related to concurrency. Technically vars are too, but you should really be using one of the other references types if you want mutable references. All that to say, even if there was a way to mutate outer environments in mal, I would still want to use an atom to wrap gensym-counter rather than mutating the environment.

That reminds me, if I ever get around to implementing namespaces in mal, I will probably do it by extending the environment concept rather than creating a new type of thing in the language (as with Clojure namespaces and vars). The implementation of namespaces and vars is actually one of my biggest complaints with Clojure. As an example of how namespaces could extend environments without much fuss, consider a symbol "strings/replace". The "strings/" part could basically just be an alias to the environment that contains a "replace" function. Something like Clojure's (ns strings) at the beginning of a file would set up the alias. Anyways, just another random stream of consciousness.

[dubek]

Now that #130 is done and merged, we have atoms implemented in step 6. This means we can introduce gensym at step 8 (with macros) or later as an improvement for the or macro implementation (for example in step A, which is now smaller because we removed atoms from there).

So my suggestion would be in step A, add something like this to the process guide (+ tests that show the problem with the older or macro + copy these 3 rep calls to all mal implementations):

---

gensym

The or macro we introduced at step 8 has a bug. It defines a variable called or_FIXME, which "shadows" such a binding from the user's code (which uses the macro). If a user has a variable called or_FIXME, it cannot be used as an or macro argument. In order to fix that, we'll introduce gensym: a function which returns a symbol which was never used before anywhere in the program.

Previously you used rep to define the or macro. Remove that definition and use rep to define the new counter, gensym function and or macro:

• (def! *gensym-counter* (atom 0))
• (def! gensym (fn* [] (symbol (str "G__" (swap! *gensym-counter* (fn* [x] (+ 1 x)))))))
• (defmacro! or (fn* (& xs) (if (empty? xs) nil (if (= 1 (count xs)) (first xs) (let* (condvar (gensym))(let* (~condvar ~(first xs)) (if ~condvar ~condvar (or2 ~@(rest xs)))))))))`

For extra information read Peter Seibel's thorough discussion about gensym in Common Lisp.

[kanaka]

Sorry, meant to reply earlier and it slipped my mind. I was thinking just doing the correct implementation of these in step8. However, I like the way you presented it and I think pointing out the bug and fixing it provides a good learning opportunity for stepA so let's go with your suggestion. Want to cook up a PR?

[dubek]

gensym and the clean or macro are now available in all implementations, with updates to process files and guide (see #143).