Quasiquote within quasiquote appears to be broken

[gilch]

Here's a simplified example in Common Lisp of what I'm trying to do.

* (let ((foo 2)) (eval `(let ((foo 1)) (eval `(print ,foo)))))

1
1
* (let ((foo 2)) (eval `(let ((foo 1)) (eval `(print ,,foo)))))

2
2

The equivalent in mal:

user> (let* [foo 2] (eval `(let* [foo 1] (eval `(prn ~foo)))))
2
nil
user> (let* [foo 2] (eval `(let* [foo 1] (eval `(prn ~~foo)))))
[long traceback omitted]
Exception: 'unquote' not found

The first case gets the wrong value at the wrong time. And the second case just fails altogether. Nested quasiquotes are not unusual in macros, but I can't seem to make them work in mal. Is there a different syntax for this I'm not seeing?

I've tested this in the python implementation, but since the code seems to follow the guide, I have to assume it's broken in the other implementations too.

[kanaka]

@gilch I'm not too surprised that nested quasiquote is broken. For the most part, mal syntax/features are based on Clojure, so this site is probably a good reference: https://blog.8thlight.com/colin-jones/2012/05/22/quoting-without-confusion.html

From that page, here is a simpler issue with nested quasiquote

user> `(list 1 `(2 ~~(- 9 6)) 4)
Error: 'unquote' not found

If you want to take a stab at figuring out the issue with the current quasiquote algorithm in one implementation, I could probably port it to most of the other implementations. However, I won't have time to actually figure out the issue any time in the next few months.

[dubek]

I modified the Ruby impl to include quasiquoting nesting level. Here's the modified quasiquote function code:

def quasiquote(ast, nesting = 0)
    if not pair?(ast)
        return List.new [:quote, ast]
    elsif ast[0] == :quasiquote
        return quasiquote(ast[1], nesting + 1)
    elsif ast[0] == :unquote
        if nesting == 0
            return ast[1]
        else
            return quasiquote(ast[1], nesting - 1)
        end
    elsif pair?(ast[0]) && ast[0][0] == :"splice-unquote"
        expanded_list = nesting == 0 ? ast[0][1] : quasiquote(ast[0][1], nesting - 1)
        return List.new [:concat, expanded_list, quasiquote(ast.drop(1), nesting)]
    else
        return List.new [:cons, quasiquote(ast[0], nesting), quasiquote(ast.drop(1), nesting)]
    end
end

Here it is in action:

user> `((+ 1 7) is ~(+ 1 7))
((+ 1 7) is 8)
user> `(list 1 `~~(list 2 3 4))
(list 1 (2 3 4))
user> `(list 1 `(2 ~~(- 9 6)) 4)
(list 1 (2 3) 4)

user> `(exploded (list 1 2 3) results in ~@(list 1 2 3))
(exploded (list 1 2 3) results in 1 2 3)
user> `(begin `(list ~@(1 ~@(list (+ 1 1) 3) 4)) end)
(begin (list 1 2 3 4) end)

user> (let* [foo 2] (eval `(let* [foo 1] (eval `(prn ~foo)))))
1
nil
user> (let* [foo 2] (eval `(let* [foo 1] (eval `(prn ~~foo)))))
2
nil

I'm not sure this is the algorithm you had in mind, and maybe I missed some cases.

[kanaka]

It's doesn't quite have the same behavior as some of the examples at the 8thlight link, for example:

`{:a 1 :b '~(+ 1 2)}

However, quasiquote has never been quite the same as Clojure so these might be reasonable differences. However, the change does seem to be an overall improvement. Let's use the process we are using for native equality and add soft tests for these, and then begin checking off the list of impls.

Here is the checklist:

• awk
• bash
• c
• clojure
• coffee
• cpp
• crystal
• cs
• erlang
• elixir
• es6
• factor
• forth
• fsharp
• go
• groovy
• guile
• haskell
• java
• julia
• js
• kotlin
• lua
• make
• mal
• ocaml
• matlab
• miniMAL
• nim
• perl
• php
• ps
• python
• r
• racket
• rpython
• ruby
• rust
• scala
• swift
• tcl
• vb
• vimscript

[kanaka]

Also, it would be good to update process/guide.md and process/step{7,8,9,A}* with the changes.

[keith-rollin]

@kanaka, I've updated the Swift implementation along the lines of the Ruby change @gilch made, and it passes all current tests (native and self-hosted) and the new examples shown above under "Here it is in action". Please let me know if you'd like a PR, or if you'd like more time to be sure that that's the approach you want to take.

[dubek]

@kanaka I think that before rushing to fix all impls, we should come up with all the test cases (and expected results) we want to cover, and decide if the algorithm presented in the Ruby code example is the correct one. Also cover a few error cases (unquote with a surrounding quasiquote?). Maybe we should modify quasiquote/unquote behaviour to imitate Clojure quoting rules here (so we can refer to them instead of making our own).

[kanaka]

@dubek yes, you're right. Spending a bit more time is prudent. I think there are probably multiple "right" paths in some sense. I do want to avoid making quasiquote significantly more complicated. If we can make it behave basically like Clojure (apart from the namespace expansion) without adding too much more complexity, that would definitely be the preferred path. I would probably lean towards the current simplistic non-nested implementation rather than tripling the size of the quasiquote implementation, but if we can get near parity with less than that and it's still easy to explain in the guide, then that would be ideal.

That reminds me. We also might want to look at what it would take to implement gensym support while we are looking at this. That's probably more practically useful than nested quasiquoting (which is pretty rare IMO). There likely will be some interaction between gensym and nested quoting.

[gilch]

I'm not sure if Clojure's behavior is the best target then. Besides the mentioned namespace expansion of symbols, Clojure can also syntax-quote vectors, maps, and sets, which MAL doesn't have either. Once you take all that away, the behavior is probably more like Scheme quasiquote or Common Lisp backquote. There are implementations of these lisps with licenses even more permissive than Clojure's EPL (CMUCL, for example, is public domain.), such that we could possibly "borrow" the implementation outright, or at least adapt their test cases.

[gilch]

I found a fairly simple-looking Scheme quasiquote implementation (in Scheme) in Alan Bawden's "Quasiquotation in Lisp", which the author asserts is correct. It shouldn't be too difficult to port it to the Racket mal implementation (or mal itself for that matter). We would still need test cases, of course, but the examples from the paper might be a good start.

[gilch]

Chicken Scheme's quasiquote test cases.

[asarhaddon]

Hi.
It would be good to clarifiy the semantics of quasiquoting before attempting to nest.
(quasiquote []) has been returning () instead of [] for years despite a TODO in tests. The recursion applies the same tests to (rest ast) than to ast, causing surprising errors for (quasiquote (1 unquote)). Also, [unquote x] is, probably unwantedly, interpreted as (unquote x).
The following suggestion passes current tests and seems easy to translate in english (a loop replaces one of the two recursions).

(def! _quasiquote_iter (fn* [x acc]
  (if (if (list? x) (= (first x) 'splice-unquote)) ; logical and
    (list 'concat (first (rest x)) acc)
    (list 'cons (list 'quasiquote x) acc))))
(defmacro! quasiquote (fn* [ast]
  (if (list? ast)
    (if (= (first ast) 'unquote)
      (first (rest ast))
      (foldr _quasiquote_iter () ast))
    (if (vector? ast)
      ;; TODO: once tests are fixed, replace 'list with 'vector.
      (list 'apply 'list (foldr _quasiquote_iter () ast))
      (list 'quote ast)))))

I would even suggest to stop supporting unquote directly under quasiquote, that is only detect (unquote foo) as sequence elements. This would increase the consistency with splice-unquote, both in the source (both in iter) and in the english description. Is there a practical need for (quasiquote (unquote 7))?

[kanaka]

@asarhaddon we should definitely continue to support unquote directly under quasiquote. The tree being quasiquoted might be generated or transformed by other code (not just handwritten) in which case you wouldn't want to arbitrarily exclude unquote right under quasiquote. splice-unquote by definition must happen within a sequence but unquote can be top-level.

I agree that [unquote x] being handled like (unquote x) is a probably a misfeature and that (quasiquote []) should return the same type. This area of the process/guide/implementations is already pretty dense in terms of complexity (more than I would really like actually, it's a bit too black box). If you show me that a couple of the more complex implementations (ada, basic, objpascal, vhdl, etc) can be fixed for the two main bugs (nesting I consider extra/bonus) without increasing complexity, then I would definitely consider it. Also, this is one area where reference counting and GC is complicated for implementations. Anyways, this might be one of those areas that we just keep as "extra exercises" for the implementor (i.e. optional tests) rather than making them core to the process.