Nested quasiquotation forms are not handled properly

[justinethier]

Nested ` forms must be handled properly, as per spec:

• Quasiquote forms may be nested.
• Substitutions are made only for unquoted components appearing at the same nesting level as the outermost backquote.
• The nesting level increases by one inside each successive quasiquotation, and decreases by one inside each unquotation.

For example, the form

`(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f)           

Should evaluate to the following, because (+ 1 3) is at the same depth level as the outer backtick:

(a `(b ,(+ 1 2) ,(foo 4 d) e) f)

However, this form throws an error instead because husk does not presently respect depth level when evaluating quasi-quoted forms.

[justinethier]

Here is a more complex example of the same problem:

(define-syntax define-config-primitive
  (er-macro-transformer
   (lambda (expr rename compare)
     `(define-syntax ,(cadr expr)
        (er-macro-transformer
         (lambda (expr rename compare)
           (let ((this-module (rename '*this-module*)))
             `(set! ,this-module (cons ',expr ,this-module)))))))))
(define-config-primitive import)

[justinethier]

Noticed the following when quasiquotation is defined as a macro. Could be a problem with expanding an ER macro:

huski> (expand (quasiquote (1 2 (unquote (list 1 2 3)))))
(quasiquote (1 2 (unquote (list 1 2 3))))

Also, this test case is still broken:

(assert/equal (let ((name1 'x) (name2 'y)) `(a `(b ,,name1 ,',name2 d) e))
         '(a `(b ,x ,'y d) e))

[justinethier]

These broken test cases are due to quasiquotation logic in the Macro module. Trouble is, removing that logic makes the macro expander perform horribly when running the first part of the test suite. Need to get to the bottom of that. Anyway, here is the diff:

diff --git a/hs-src/Language/Scheme/Macro.hs b/hs-src/Language/Scheme/Macro.hs
index d3c37a6..1528899 100644
--- a/hs-src/Language/Scheme/Macro.hs
+++ b/hs-src/Language/Scheme/Macro.hs
@@ -634,7 +634,7 @@ walkExpanded defEnv useEnv divertEnv renameEnv cleanupEnv dim startOfList inputI

  -- If a macro is quoted, keep track of it and do not invoke rules below for
  -- procedure abstraction or macro calls
- let isQuoted = inputIsQuoted || (a == "quote") || (a == "quasiquote")
+ let isQuoted = inputIsQuoted || (a == "quote") -- || (a == "quasiquote")

  isDefinedAsMacro <- liftIO $ isNamespacedRecBound useEnv macroNamespace a

@@ -895,7 +895,7 @@ walkExpandedAtom defEnv useEnv divertEnv renameEnv cleanupEnv dim _ _ (List resu
     a
     ts
     True _ apply = do
-    let isQuasiQuoted = (a == "quasiquote")
+    let isQuasiQuoted = False -- (a == "quasiquote")
     -- Cleanup all symbols in the quoted code
     List cleaned <- cleanExpanded
                       defEnv useEnv divertEnv renameEnv cleanupEnv
@@ -979,16 +979,6 @@ cleanExpanded defEnv useEnv divertEnv renameEnv cleanupEnv dim _ isQQ (List resu
 cleanExpanded defEnv useEnv divertEnv renameEnv cleanupEnv dim startOfList isQQ (List result) (List (Atom a : ts)) apply = do  
   expanded <- tmpexpandAtom cleanupEnv $ Atom a
   case (startOfList, isQQ, expanded) of
-    -- Unquote an expression by continuing to expand it as a macro form
-    --  
-    -- Only perform an unquote if (in order):
-    --  - We are currently at the head of the list
-    --  - Expression is quasi-quoted
-    --  - An "unquote" is found
-    --
-    (True, True, Atom "unquote") -> do
-        r <- walkExpanded defEnv useEnv divertEnv renameEnv cleanupEnv dim True False (List $ result ++ [Atom "unquote"]) (List ts) apply
-        return r
     _ ->
         cleanExpanded defEnv useEnv divertEnv renameEnv cleanupEnv dim False isQQ (List $ result ++ [expanded]) (List ts) apply
  where
@@ -1373,7 +1363,7 @@ transformDottedList defEnv outerEnv divertEnv localEnv renameEnv cleanupEnv dim
    buildTransformedCode results ps p = do
      case p of
         [List []] -> List $ results ++ [List ps]         -- Proper list has null list at the end
-        [List l@(Atom "unquote" : _ )] -> List $ results ++ [DottedList ps $ List l] -- Special case from parser.
+--        [List l@(Atom "unquote" : _ )] -> List $ results ++ [DottedList ps $ List l] -- Special case from parser.
         [List ls] -> List $ results ++ [List $ ps ++ ls] -- Again, convert to proper list because a proper list is at end
         [l] -> List $ results ++ [DottedList ps l]
         ls -> do

Should profile with/without the change on line 634 using should-be and the first test case of R5RS pitfalls.

[justinethier]

With regard to the previous comment, the main performance bottleneck seems to be all of the macro expansions within the QQ macro. This is especially bad since qq is called recursively and each iteration leads to additional expansions. Anyway, by precompiling the macro the performance of the QQ scheme code is almost as good as a Haskell special form. Here are some rough benchmarks:

master branch (QQ implemented in Haskell as a special form):

real     0m5.768s
user     0m2.668s
sys      0m0.808s

QQ branch (QQ implemented as a Scheme macro):

real     0m5.934s
user     0m2.936s
sys      0m0.728s

[justinethier]

Closing as fixed per the previous comment.