Arc Forumnew | comments | leaders | submitlogin
Noobish questions about unhygienic vs. hygenic macros
8 points by bramsundar 6158 days ago | 19 comments
Unlike many on this site, I'm not a long time lisper, so I'm still trying to develop a feel for what macros are and how they work. Unfortunately, I'm kind of confused about the differences between hygienic and unhygienic macros. I have a number of questions and I hope that those more experienced than me can enlighten me with their responses:

1) As I understand it, unhygienic macros are somewhat dangerous because the don't do any checking for the cases where a special form/macro/function used in the macro-expansion has been shadowed by something weird. For example:

> (mac dumb (x) `(* ,x ,x))

#<procedure>

> (let * 'foo (dumb 3))

Error!!!

Is this the general idea? Are there any underlying subtleties in this situation?

2) Scheme's macros appear to work differently from arc and CL's macros. Scheme macros use a special pattern language to describe the code transformations. Is the use of this type of pattern language something required to make hygienic macros work or is it just a design choice that the Scheme implementors made?

3) How could a hygienic macro system be implemented on top of Arc? Are there any features of Arc that make such a system currently impossible?



6 points by kennytilton 6158 days ago | link

"Is the use of this type of pattern language something required to make hygienic macros work or is it just a design choice that the Scheme implementors made?"

Great minds wonder alike. Check out the "What's up with Scheme macros?" thread I kicked off on comp.lang.lisp. I do believe you will like I be sorry you asked. :)

I think somewhere in the dozens of treatises is the response "design choice", but I also think that response was challenged (surprise! surprise!). But I am just a working application programmer and I could not understand very much of what they were saying.

I did get a kick out of one shocked Schemer insisting something was trivial and then posting a twenty-line solution which at one point had a form beginning with four (!) left parens.

-----

6 points by Jekyll 6158 days ago | link

Kenny's right.

Pattern matching is completely orthogonal to hygiene.

You could add in another operator, %, that performs exactly the same as ` but hygienically. Personally I'd settle for just being able embed procedures in code trees like you can in common lisp. Being able to write.

  (let this (fn (x) x)
     (mac na-na-na(y)
      `(,this ,y))) ;Can't touch "this". It's lexically bound.
Allows you to fake hygiene in the common cases where it's needed most often.

-----

2 points by nlavine 6157 days ago | link

Hygienic macros do not require pattern-matching, as proven by the example of MIT scheme. Basically, macros in their system take three arguments - an s-expression, the environment the s-expression is being evaluated in, and the environment the macro is written in - and return syntax, which is an s-expression where you've chosen explicitly for each variable what environment it should be evaluated in. (More or less. If you're interested, it's called syntactic closures and you can probably find stuff about it online, or I can just write more here if people want.) I don't remember any way to insert a free identifier, but it might be there.

By the way, arc can already do half of that if you put (procedure? x) into literal.scm. The harder part is making variable references to things that aren't procedures, and I'm not quite sure how you'd do that (except the really annoying way, by wrapping everything in a procedure application).

SRFI-72 is another proof, as someone posted below, and might be better than syntactic closures (I don't know).

-----

1 point by akkartik 6157 days ago | link

http://groups.google.com/group/comp.lang.lisp/browse_thread/...

-----

7 points by ctdean 6157 days ago | link

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 6157 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 6157 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 6157 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 6157 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 6157 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 6157 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 6157 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 6157 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 6156 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 6156 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 6156 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.

-----

3 points by soegaard 6158 days ago | link

I recommend

"Syntactic Abstraction: the syntax-case expander" by Kent Dybvig. It appeared in the book "Beautiful Code"

http://www.cs.indiana.edu/~dyb/pubs/bc-syntax-case.pdf

-----

2 points by sacado 6158 days ago | link

1) It's hard to guess what you're trying to do, maybe you could do (let * foo (dumb 3)) : 'foo seems strange

for example : (let * + (dumb 3)) ==> 6 (let * '+ (dumb 3)) ==> error

In this example, + is a function and can thus be applied, but '+ is a symbol and cannot.

-----

1 point by ms 6158 days ago | link

ad 2), SRFI 72 presents a hygienic macro system for Scheme that basically works like CL macros.

http://srfi.schemers.org/srfi-72/srfi-72.html

-----