Arc Forumnew | comments | leaders | submitlogin
7 points by ctdean 6098 days ago | link | parent

1. Hygienic macros are there to prevent accidental variable capture. (More precisely they prevent collisions of symbol definitions.)

In practice, it's very easy to avoid symbol collisions on local variables. In practice, it's harder to avoid collisions on global symbols like function names. (I'm using the "local" and "global" terms loosely here.)

2. Yes, syntax-case macros in Scheme are different than Arc macros. The pattern matching language is a design choice in most of the Scheme macro systems.

3. A hygienic macro system could be implemented in Arc and there are many many ways to do it. Symbol rewriting and careful namespace management are two designs that spring to mind.

The issue for me as a long time user of various Lisps is that hygiene is not a problem you can just skip. Even modest sized programs hit the collision problem fairly quickly (at least mine do!) and I want to be assured that eventually I can write code that will not have collisions.

Two quick examples. The first demonstrates variable capture. Let's swap two elements. If I was writing the by hand I'd say:

  (let temp a
    (= temp a)
    (= a b)
    (= b temp))
I can make this a macro by saying

  (mac my-swap (a b)
    `(let temp ,a
       (= temp ,a)
       (= ,a ,b)
       (= ,b temp)))
and using it like this:

  (let x 1
    (let y 2
      (prs x y)
      (prn)
      (my-swap x y)
      (prs x y)
      (prn)
      'done))
prints "1 2" and "2 1"

The problem comes when I name one of my variables temp

  (let temp 1
    (let y 2
      (prs temp y)
      (prn)
      (my-swap temp y)
      (prs temp y)
      (prn)
      'done))
prints "1 2" and "1 2"

This is easily fixed by using a uniq variable

  (mac my-swap (a b)
    (w/uniq gtemp
     `(let ,gtemp ,a
        (= ,gtemp ,a)
        (= ,a ,b)
        (= ,b ,gtemp))))
now everything works fine.

The second example is harder to fix. Lets say I want to add items to a list, so I make a macro to help:

  (mac my-push (obj place)
    `(= ,place (cons ,obj ,place)))
This macro is has a multiple-evaluation problem, but let's ignore that for now.

  (let pros '("fast")
    (my-push "cheap" pros)
    (prn pros))
prints ("cheap" "fast")

  (let cons '("out of control")
    (my-push "mole rats" cons)
    (prn cons))
gives an error.

The function CONS and the list CONS have the same name and are colliding and doing the wrong thing. This is the function collision problem. Will Arc ever fix this? I don't know the answer, but I wish I did.



2 points by greatness 6098 days ago | link

The question, of course, is why would someone be stupid enough to redefine cons. The answer being that this was merely an example and that this is more likely to happen to people using code written by 3rd party developers. Once we get a true module system this shouldn't be as much of an issue. Additionally, it shouldn't be that hard to keep yourself from overriding a function definition; you could merely enter in the name at the repl to see if it exists. It's really not that hard.

  arc> cons
  #<primitive:cons>
  arc> (gee, perhaps I better not overwrite this!)

-----

2 points by ctdean 6097 days ago | link

To answer your question, I would be stupid enough to do this because PROS and CONS seem like reasonable variable names. I would (and have) name variables first, tokens, blank, date, and many others for the same reasons. We're not talking about redefining functions, just lexical binding variables in a small scope.

In a Lisp 2 like Common Lisp it is very easy to work around name collisions problems with a module system. It's much harder to solve this problem in a Lisp 1 with just a module system. All the ways I know how to solve the collision problem in a Lisp 1 that use namespace management require integration with the macro expander. Is there a better way? I'd love to hear it.

-----

2 points by almkglor 6097 days ago | link

By taking advantage of the relation:

  (fn (x) (expression x)) == (fn (y) (expression y))
Suppose that our hypothetical 'fn builtin automatically did this:

  (mac new-fn (parms . body)
    (let ptab (fill-table (table) (mappend [list _ (parms)] parms))
      (let translate
           (afn (xs)
              (if (caris xs 'quote)
                 xs
                 (map [if (acons _) (self _) (or (ptab _) _)] xs)))
        `(fn ,@(translate (cons parms body)))))
This solves two problems currently in Arc: local variables can override function names used by macros, and macro names always override local variables.

-----

1 point by ctdean 6097 days ago | link

Unfortunately I have no idea what that macro is supposed to do since it won't run for me. Perhaps you could post a different version?

-----

1 point by almkglor 6097 days ago | link

Sorry, not on my hacking computer right now, so I'm not sure. Will check later what the problem is, in the meantime, what's the error?

-----

2 points by almkglor 6097 days ago | link

Aw nuts, missing parenthesis, then realized that Arc parameter forms aren't straightforward lists but have a nasty (o ...) syntax. Here's a more complex form:

   (mac new-fn (parms . body)
    (let ptab
      (fill-table (table)
        (mappend [list _ (uniq)]
          (accum add
            (withs
              (optionalp [caris _ 'o]
               optional-var cadr
               traverser
               (afn (x)
                 (if (optionalp x)         (add (optional-var x))
                     (acons x)             (do (self (car x)) (self (cdr x)))
                     (and x (isa x 'sym))  (add x))))
              (traverser parms)))))
      (let translate
           (afn (xs)
              (if (caris xs 'quote)
                 xs
                 (map [if (acons _) (self _) (or (ptab _) _)] xs)))
        `(fn ,@(translate (cons parms body))))))

-----

2 points by ctdean 6097 days ago | link

Now I see -- that's great, thanks. (It was the missing UNIQ that got me, I can add parens :))

I think that if we kept going down this direction we would eventually come up with a macro system that was "hygienic in practice". Building a good and simple hygienic macro system is a very achievable goal.

All I really want to say is that there isn't a trivial silver bullet solution: A simple module system doesn't fix name collision. A simple code walker doesn't fix it (it needs integration with the environment.)

I eagerly await the version of Arc that has a macro system where name collision can be avoided.

-----

1 point by ctdean 6097 days ago | link

BTW, some comments on the code walker solution:

These are very hard to get right without hooks into the Lisp environment (at least they are for me!). For example, we always uniqify the variable names, but sometimes that doesn't do what we want. Consider:

  (mac my-assert (val)
    `(unless ,val
       (prn "Assertion failed for " ',val)))

  (new-let wallet 'no-money
    (prn "wallet => " wallet)
    (my-assert (positive wallet))
    wallet)
Where NEW-LET is defined using your NEW-FN. This gives "Assertion failed for (positive gs1449)" when I want "Assertion failed for (positive wallet)".

Also, I don't know if Arc has dynamic variables or not, but if if does those should also not be uniqified.

I'm going to exit this thread now, thanks for the code.

-----

1 point by almkglor 6097 days ago | link

On assertions: it would really be nice to have at least just one extra namespace for local variables, I suppose, with printnames that are the same as the global namespace. new-fn then translates from symbols in the global namespace (which is what read should always emit) to local variable namespace. Aw crick, it's a hard problem.

Also, current bug with this implementation: (fn (do) `(do ,do)) will fail, I'll need to analyze do. And stuff like (fn (b) (tag b (prn "foo"))).

-----

2 points by PieSquared 6096 days ago | link

Question: Could this, perhaps, be solved by making the variable and function namespaces the same?

(I'm probably misusing terminology here, but what I mean is that you can't have a function and a variable named the same yet still stand for different things when used in code)

-----

2 points by cooldude127 6096 days ago | link

actually, arc does use the same namespace, that is most of the cause of this problem. if they were in different namespaces, there would be no problem with variables shadowing built-in functions. you still have to worry about variable capture, but it's a much less significant problem.

note: i'm not saying i don't like the same namespace thing. it actually shortens a great deal of code, and eliminates CL's stupid ass #' garbage.

-----