Arc Forumnew | comments | leaders | submitlogin
Problem with auto-uniqs
2 points by malisper 3805 days ago | 6 comments
I realized there is a problem with how the auto-uniqs are generated. They are generated only once when the macro is defined, instead of being generated every time the macro is executed. I am currently trying to figure out how we can fix this. It looks like defmacro! from Let Over Lambda would be a good place to start.

Edit: Here's what I have so far

  (let uniqs (map (fn (v) `(,v (uniq ,v)))
                  (keep auto (flat body)))
     `(defmacro ,name ,args
        (let ,uniqs
	     ,@(subst auto
	              [alref uniqs _]
		      (tree body)))))
The problem I am running into is the variables need to be unquoted the same number of times they are backquoted. Does anyone have any ideas on how to fix this?

Edit:

I believe I have discovered why Clojure makes the auto-gensyms as part of the backquote. The macro is only executed once so it is impossible for every symbol to be replaced within each execution of the code when the implementation of the autos are through a macro. OTOH the backquote is executed every time new code is generated. This makes it possible to have every place the generated code is used, to have its own unique set of symbols. If anyone has any ideas about how this could be done differently, feel free to explain.



2 points by malisper 3805 days ago | link

I may have figured out a possible way to implement backquoting in such a way based off of Steele's implementation[0]. All that is needed is an addition macro that will be put outside of each backquote expansion. When that macro finally is expanded (when all of the other backquotes have been used up), it would go through and replace all of the specified symbols with a uniq symbol up to any further backquotes. This would make it possible to have the uniqs generated every time each backquote is executed.

The only problem I can think of is something like this:

  `(x@ `(x@))
How would one specify for the generated symbols for both x@ to be the same. There might already be a way to do it through use of unquoting but I'm not sure how that would interact with the backquote implementation.

[0] http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node367.html#S...

-----

1 point by akkartik 3805 days ago | link

Hmm, I've never seen this idea before and haven't seen any system supporting it. Does clojure?

Can you give an example where it's useful?

-----

2 points by malisper 3805 days ago | link

The idea behind autouniqs is that they remove some boilerplate code (ie w/uniq). The current implementation of autouniqs[0] is actually broken. The problem boils down to the fact that with the current implementation, macros will wind up using the same uniqs every time they are expanded. Say accum was implemented using autouniqs.

  (mac accum (accfn . body)
    `(withs (acc@ nil ,accfn [push _ acc@])
       ,@body
       (rev acc@)))
The intention is acc@ will be replaced with a uniq every time accum is expanded. With the current implementation of autouniqs, acc@ will be replaced with a single uniq in accum's definition. This leads to problems with nested use of accum.

  (accum a
    (accum b
      (...)))
What clojure does to solve the problem is combine "autogensyms" with its implementation of backquote. All the symbols ending in '#' inside of the same backquote are replaced with gensyms when the backquote is evaluated. While clojure's implementation is good for most things, it breaks down with any kind of nested backquotes [including `(... ,(... `(...)))] since the autogensyms will not be the same inside all of the backquotes. I think tying the autogensyms to backquote is a requirement due to the fact that every time the backquote is evaluated new gensyms would have to be put in to replace all of the autouniqs/gensyms (feel free to prove me wrong). This becomes obvious when one starts thinking about macros with nested backquotes and how they would expand. What I want is some version of autouniqs such that they completely eliminate the need for w/uniq.

[0] http://www.arclanguage.org/item?id=18235

-----

2 points by akkartik 3804 days ago | link

Yeah, I actually thought about this use case back when I wrote accum for wart. But there's no problem here since the two expansions also create lexical scopes. In unmodified anarki:

  arc> (mac foo (accfn . body)
         `(withs (acc@ nil ,accfn [push _ acc@])
            ,@body
            (rev acc@)))
  #(tagged mac #<procedure: foo>)
  arc> (foo a
         (each l '(1 2 3)
           (a:foo b
             (each m (list l (+ l 1) (+ l 2))
               b.m))))
  ((1 2 3) (2 3 4) (3 4 5))
Is there some other scenario that I'm not considering?

(I hadn't realized that w/uniq is superior to implicit gensyms in this regard. Thanks.)

-----

2 points by malisper 3804 days ago | link

Okay, so the example with accum actually does work fine, but, only due to lexical scoping. I'm still afraid of the possibility of macros using the same symbols and causing a collision. While it looks like it would be an extremely rare bug to find, it would be one of those bugs that are a real pain to debug.

-----

2 points by akkartik 3804 days ago | link

Agreed. Which is why we should pool resources and share the first time we encounter such a bug. Or even a possible such bug that we can then debug together.

For my part, I have had an eye out for it for three years and have yet to encounter such a bug. Here's my hand-wavy reasoning for why I think it can't happen: for it to happen, an outer macro would have to rely on a use of a specific gensym inside a nested macro. I can't imagine how that could happen short of actually trying to use a gensym:

  (macro1
    (macro1
      ..x23..))  ; brittlely relying on the gensym turning into *x23*
And if we are to worry about this we can worry about all gensyms anyway.

-----