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))

    (list one two (list three))

    (list one two (three))

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))

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)

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))))

    (define (solve puzzle failure-continuation)
        (with* (amb (make-amb-macro failure-continuation)
                assert (make-assert amb))
        ... stuff requiring amb and assert
    )

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))

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))))

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 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)

---

"(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))

---

"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 `(...)))

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)
             _       `())))

  (define defmacro
    (macro (vau env (name . bodies)
             `(define name
                (macro (vau _ . bodies))))))
        
  (defmacro foo
    (x y z) `(x y z)
    _       `())
 

---

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)))

---

* [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/

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