Arc Forumnew | comments | leaders | submitlogin
1 point by Pauan 4721 days ago | link | parent

So, it looks like you've stumbled upon the hygienic macro technique that Arc/Nu uses, which is to unquote the macros/functions, thus relying upon the standard lexical scope of functions. It's the same technique that Kernel uses, but it doesn't actually require first-class macros at all, and so it's trivial to add it to Arc 3.1.

In any case, I would suggest that quasiquote by default unquotes things rather than quoting them:

  `(foo bar qux) -> (list foo bar qux)
This makes writing hygienic macros a lot easier:

  (define if
    (macro (lambda (condition true-case false-case)
      ; Anything not false is considered 'true'
      `((lambda (#f) false-case
                 _   true-case)
        condition))))
Notice that I didn't use any unquotes in the above code. If you ever want to break hygiene, just use unquote + quote:

  `(foo ,'bar qux) -> (list foo 'bar qux)
Over the course of the past few years, I've been slowly coming to the conclusion that hardcoding any name (whether it's a symbol or a string) is a code smell and that quote should only be used for intentionally breaking hygiene, like with Arc's "aif" or "afn".

Taken to the extreme, this also suggests not hardcoding the symbols 'unquote and 'unquote-splicing in the 'quasiquote form... instead, I would make that a part of the syntax itself.

But hey, take what I say with a grain of salt: if you listened to me, you'd wind up with an alternate version of Nulan! Your approach is traditional: it's mostly the same approach taken by most Lisps. Whether you consider that good or bad is up to you.

---

Pattern matching looks good, and that's definitely a good way to go about it, if you want a more traditional Lisp.



2 points by Patient0 4720 days ago | link

Thanks for the solid feedback Pauan (and akkartik!) with some very good insights there! This sort of feedback is exactly what I was looking for when I posted this on the Arc forum, because I haven't actually done much Lisp before this

On to the specifics:

For quasiquote... yeah it had occured to me that almost every time I am not 'unquoting' a symbol then this is a mistake... but only when writing a macro. Outside a macro it's less clear that this is what someone would want.

And to clarify, you mean that :

    `(one two (three))
would expand into

    (list one two (list three))
NOT

    (list one two (three))
So maybe a "define-hygienic" macro could re-define quasiquote in this fashion - but elsewhere it would work as normal.

I had also realised that the "hygiene" is currently broken by the fact that, in FirstClass Lisp, "quasiquote", "quote", "unquote", "unquote-splicing", "dot" and "slash" are all "special" in terms of what the reader reads in, so something like the following:

    (lambda (quote phrase)
        ('quote-tag quote phrase))
will not do what the author probably intended. It's easy enough to work around it - but it's unsatisfactory.

It seems to me that the correct resolution is to have the reader itself also have a lexical environment which it refers to when generating these special symbols - although you would then have the problem of how to supply this environment to the reader. Something like:

    (define quasiquote ...)
    (set-reader-environment! (env))
    `(a list)
would work... although the mutation is inelegant.

By far the most interesting statement you've made is that making the macros first class isn't actually necessary for this hygiene trick anyway! That's a very interesting statement... I need to think about this. What I most wanted was a "simple" concept of hygienic macros - that is, simple in understanding how they work: that they are just functions which happen to operate on the unevaluated source tree and return a source tree to be evaluated. Once we have that, I think the next most important thing is that there is no performance cost to using them. If what you're saying is true then it might be possible to expand all of the "non" first class macros in a pre-compilation step anyway.

I'd really like to get the Sudoku solver at least at the same level of performance as the Python one.

One area in which the first class nature of the macros was particularly elegant was in the implementation of an "amb" macro. All of the classic examples of amb require some sort of global state to keep all of the continuation instances. But this is inelegant if you wanted to have multiple usages of (amb) which don't interfere with each other: suppose for example you want to create two threads - one for solving each Sudoku puzzle.

The conventional examples always add some sort of "amb-reset!" function to say "forget about everything you tried to solve before" - but this is inelegant and wouldn't work for multiple threads.

At the same time, you want (amb) to be a macro which lazily evaluates the possibilities, so that you can write code such as:

    (define (anything-starting-from n)
            (amb n (anything-starting-from (+ n 1))))

Having amb be a first-class macro allows the following pattern, which solves both of these problems:

    (define (solve puzzle failure-continuation)
        (with* (amb (make-amb-macro failure-continuation)
                assert (make-assert amb))
        ... stuff requiring amb and assert
    )
So we have a "solve" function whose use of 'amb' is entirely an implementation detail, which means you're guaranteed that it won't interfere with anyone else's use of the amb macro.

Here's the way I defined "make-amb-macro" and "make-assert":

    ; A hygienic 'amb' macro.
    ;
    ; Using a factory function allows us to maintain
    ; the hygiene of 'amb-fail'.
    ; Use 'make-amb' to make an
    ; amb macro that you know won't interfere
    ; with anyone else's amb macro.

    ; The ability to do this - return a hygienically
    ; scoped 'amb' macro from a
    ; function, is something that is only possible
    ; in a Lisp with First Class macros and continuations
    ; (i.e. First Class Lisp!)
    (define (make-amb-macro exhausted)
        (define amb-fail exhausted)
        (define (set-fail thunk)
            (set! amb-fail thunk))
        (define (get-fail)
            amb-fail)

        ; Based on
        ; http://c2.com/cgi/wiki/?AmbSpecialForm
        (define amb
            (define expand-amb (lambda
                ()  (list force (get-fail))
                (x) x
                (x y)
                    (with* (old-fail (gensym)
                            c (gensym))
                    `(,let ,old-fail (,get-fail)
                        (,force
                            (,let-cc ,c
                                (,set-fail
                                    (,make-thunk
                                        (,set-fail ,old-fail)
                                        (,c (,make-thunk ,y))))
                                (make-thunk ,x)))))
                (x . rest)
                    `(,amb ,x (,amb ,@rest))))
         (macro expand-amb))
        amb)

    ; Given an amb macro, make an appropriate
    ; assert function. Once again, this sort of
    ; thing is only possible with first-class macros.
    (define (make-assert amb)
        (lambda
            (#f) (amb)
            (condition) #t))

And to top it off: it looks like a forgot a "," before a make-thunk in there. Yes, a "quasiquote" which by default unquotes is a good idea!

-----

3 points by rocketnia 4718 days ago | link

"All of the classic examples of amb require some sort of global state to keep all of the continuation instances. But this is inelegant if you wanted to have multiple usages of (amb) which don't interfere with each other: suppose for example you want to create two threads - one for solving each Sudoku puzzle."

Woo! A kindred spirit! I scratched the same itch right when I was getting started with Arc:

https://github.com/rocketnia/lathe/blob/master/arc/amb.arc

I haven't ended up using this code, mainly because Arc isn't a great ecosystem for reentrant continuations. Arc's looping utilities use mutation, and one of the implementations of Arc which I like to support, Jarc, doesn't support reentrant continuations at all. Maybe you can give 'amb a better home.

---

"At the same time, you want (amb) to be a macro which lazily evaluates the possibilities"

Not me. My version of (make-amb) simply returns a procedure that chooses one of its arguments. Given that, we can get by with just one global macro for laziness:

  (lazy-amb my-amb (foo a b c) (bar d e f) (baz g h i))
  ==>
  ((my-amb (fn () (foo a b c)) (fn () (bar d e f)) (fn () (baz g h i))))
If you can stand to define a separate macro like 'lazy-amb and use it at each call site, it's a design pattern that obviates most use cases for fexprs.

-----

2 points by Pauan 4718 days ago | link

"If you can stand to define a separate macro like 'lazy-amb and use it at each call site, it's a design pattern that obviates most use cases for fexprs."

Indeed. You and I had discussed this quite some time ago, about having convenience macros that expand into thunks. This thunkification is clunky and awful, but it does indeed give many of the benefits of vau.

I still think any new Lisp should use vau, but thunkification is a great way to retrofit many of the benefits of vaus into older (?) Lisps like Arc.

-----

1 point by Pauan 4720 days ago | link

"Outside a macro it's less clear that this is what someone would want. [...] So maybe a "define-hygienic" macro could re-define quasiquote in this fashion - but elsewhere it would work as normal."

I don't see why... have you ever needed the normal quasiquote outside of macros? No? It's quite rare for me to want quasiquote outside of macros.

But the new quasiquote I'm proposing is useful outside of macros, precisely because it doesn't quote: it's a short version of list/cons:

  (cons a b)
  `(a . b)

  (list a b c)
  `(a b c)

  (list* a b c)
  `(a b . c)

  (list* a (list b c) d)
  `(a (b c) . d)
Then you could actually get rid of the "cons", "list" and list* functions and just use quasiquote instead.

---

"(list one two (list three))"

That is correct. If you want to express (list a b (c)) you can use `(a b ,(c))

---

"I had also realised that the "hygiene" is currently broken by the fact that, in FirstClass Lisp, "quasiquote", "quote", "unquote", "unquote-splicing", "dot" and "slash" are all "special" in terms of what the reader reads in, so something like the following:"

How I would handle this is to make the syntax expand to global values rather than symbols. So, for instance, I would define quote using vau[1] (or a macro, whatever):

  (define quote (vau _ (x) x))
And then I would have 'foo expand to (#<vau:quote> foo) where #<vau:quote> is the actual value of the global quote vau, not the symbol "quote". This avoids the redefinition problem you pointed out, because it doesn't use symbols, it uses values. Like I already said, I believe that any time you use symbols, you're hosed. Symbols are only useful for easily referring to values: it's the values that are important.

---

"If what you're saying is true then it might be possible to expand all of the "non" first class macros in a pre-compilation step anyway."

Various people (including rocketnia) are working on ways to inline vau, effectively turning them into compile-time macros. This is probably possible with the kind of immutable environments that Nulan has, but much much harder with mutable envs, because you need to rollback things if anything the vau depends on changes, as you already noted.

Personally, what I would do is provide full-blown Kernel-style vaus, including first-class environments:

  (vau env
    (a b c) (eval env `(...))
    _       (eval env `(...)))
Note that in the above version of vau, the environment argument comes first, and the remaining arguments are the pattern matching/body pairs, just like in your "lambda", except that it's a vau, obviously.

Then I would provide a way to tag a vau saying, "treat this vau like a macro". When the compiler sees something that's tagged as a macro, it will always macro-expand it at compile-time. Something like this:

  (define foo
    (macro (vau _
             (x y z) `(x y z)
             _       `())))
Of course, you should also define a "defmacro" or whatever to make the above shorter:

  (define defmacro
    (macro (vau env (name . bodies)
             `(define name
                (macro (vau _ . bodies))))))
        
  (defmacro foo
    (x y z) `(x y z)
    _       `())
 
I'd like to note that the above is a lot like the hygienic pattern matching macros found in Scheme... except it doesn't need a massively unbelievably horrifically bloated system: it's built on the very simple concept of tagging vaus with a type.

---

Depending on how you implement it, macros in the above system may or may not be first-class, but even if they're not first-class, they're still built on top of the first-class vau. So, most code would use macros for speed, but your amb could use a raw vau.

If macros were no longer first-class, then the performance of the program is now clearer: macros are always expanded at compile-time, so they're always as fast as macros in other Lisps.

But vaus are slower because they're always run at runtime, so this serves as a red flag that says, "hey man, this is slow!". This also suggests a simple rule: "never use a vau when a macro will do". This complements the rule of "never use a macro when a function will do".

---

I would also build "lambda"[2] on top of vau by using a tagging mechanism (like Kernel's wrap/unwrap):

  (defmacro lambda bodies
    `(wrap (vau _ . bodies)))
Basically, I believe the idea of tagging vaus to provide different callable behavior is extremely useful, and I prefer to see vau as the center of everything, with macros and functions being a subset of vaus (but with orthogonal purposes).

---

* [1]: I use the word "vau" to refer to "fexprs" because it's shorter, nicer looking, easier to say, it has an analog to "lambda", and it's what Kernel uses.

* [2]: Except I would call it "fn" rather than lambda, but that's just bike-shedding:

http://bikeshed.com/

http://en.wikipedia.org/wiki/Parkinsons_Law_of_Triviality

-----

1 point by Pauan 4719 days ago | link

Oops, I accidentally put in an unnecessary "env". defmacro should be like this:

  (define defmacro
    (macro (vau _ (name . bodies)
             `(define name
                (macro (vau _ . bodies))))))

-----

1 point by akkartik 4721 days ago | link

"So, it looks like you've stumbled upon the hygienic macro technique that Arc/Nu uses.."

Was Arc/Nu[1] really the first, not the link he referred to (http://matt.might.net/articles/metacircular-evaluation-and-f...), or something else?

We're all stumbling around here, discovering and rediscovering things.

[1] http://github.com/Pauan/ar/tree/arc/nu

-----

1 point by Pauan 4721 days ago | link

Arc/Nu definitely wasn't the first: Kernel used the technique before Arc/Nu did. And in fact, Arc/Nu actually took the idea directly from ar: http://arclanguage.org/item?id=14507

I was merely pointing out that 1) the technique isn't new, and 2) it doesn't require first-class macros, so it's usable in Arc 3.1, etc. Sorry if I gave the impression that Arc/Nu was the first to come up with the idea.

When multiple people independently come up with the same idea, I see that as evidence that the idea is good, not that people are a bunch of thieving stealers. I don't believe in the idea of "stealing an idea", since ideas can only be copied, not stolen. Unfortunately, in the past I've used the word "stealing" to mean "copying". I'll stop doing that.

In any case, I don't think people should be penalized in any way shape or form for copying ideas from others. What matters is whether the idea is good or not, not who came up with it first. At the same time, pointing out that an idea has been invented in the past means that:

1) It can give extra validation to it, based on the assumption that if an idea is independently invented multiple times, it's probably a good idea

2) It suggests further research that you can do, to contrast how these other people tweaked the idea for their own uses. Whereas, if an idea is original, you're completely on your own, without much help.

While developing Nulan, it's been a lot of help for me to research how Arc, Clojure, Racket, etc. handle things like immutability, types, laziness, etc. In that case, having existing ideas to draw from is a plus not a minus.

---

"[...] not the link he referred to [...]"

At a quick glance, that link doesn't seem much like the technique that Kernel or Arc/Nu uses... it's more complicated and seems to be more like rocketnia's latemac: http://arclanguage.org/item?id=14521

---

"We're all stumbling around here, discovering and rediscovering things."

That's right, and there's nothing wrong with that. Nulan is almost entirely based on copying the good ideas from other languages: pattern matching, syntax, immutability, variables, vau... it's all been done elsewhere, in some cases long before. What's unique about Nulan is how all the ideas blend together, not the ideas themself. The same is true of Patient0's Lisp, and wart, and indeed most languages.

-----