Support nested quasiquote unquote. (#15)

BowenFu · web-flow · commit 9a4c3dcc23a4 · 2021-12-14T00:02:59.000+08:00
Co-authored-by: Bowen Fu &lt;missing&gt;
diff --git a/include/lisp/evaluator.h b/include/lisp/evaluator.h
@@ -219,20 +219,6 @@ class Cons final: public Expr
     }
 };
 
-class Unquote final: public Expr
-{
-    MExprPtr mInternal;
-public:
-    explicit Unquote(MExprPtr const& mexpr)
-    : mInternal{mexpr}
-    {}
-    ExprPtr eval(std::shared_ptr<Env> const& /* env */) override;
-    std::string toString() const override
-    {
-        return mInternal->toString();
-    }
-};
-
 template <typename Iter>
 ExprPtr vecToCons(Iter begin, Iter end)
 {
diff --git a/include/lisp/parser.h b/include/lisp/parser.h
@@ -97,7 +97,7 @@ inline ExprPtr or_(MExprPtr const& mexpr)
     return std::make_shared<Or>(parseActions(mexpr));
 }
 
-inline auto parseAsQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr;
+inline auto parseAsQuoted(MExprPtr const& mexpr, std::optional<int32_t> quasiquoteLevel) -> ExprPtr;
 
 inline MExprPtr assertIsLastAndGet(MExprPtr const& mexpr)
 {
@@ -113,12 +113,12 @@ inline MExprPtr assertIsLastAndGet(MExprPtr const& mexpr)
 
 inline ExprPtr quote(MExprPtr const& mexpr)
 {
-    return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasi = */ false);
+    return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasiquoteLevel = */ {});
 }
 
 inline ExprPtr quasiquote(MExprPtr const& mexpr)
 {
-    return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasi = */ true);
+    return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasiquoteLevel = */ 1);
 }
 
 inline ExprPtr definition(MExprPtr const& mexpr)
@@ -321,10 +321,10 @@ inline auto atomicToQuoted(ExprPtr const& expr)
 
 inline ExprPtr unquote(MExprPtr const& mexpr)
 {
-    return ExprPtr{new Unquote{assertIsLastAndGet(mexpr)}};
+    return parse(assertIsLastAndGet(mexpr));
 }
 
-inline auto consToQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr
+inline auto consToQuoted(MExprPtr const& mexpr, std::optional<int32_t> quasiquoteLevel) -> ExprPtr
 {
     if (mexpr == MNil::instance())
     {
@@ -334,21 +334,34 @@ inline auto consToQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr
     ASSERT(cons);
     auto car = cons->car();
     auto cdr = cons->cdr();
-    if (quasi && car->toString() == "unquote")
+    auto carStr = car->toString();
+    if (quasiquoteLevel)
     {
-        return unquote(cdr);
+        if (carStr == "unquote")
+        {
+            if ( quasiquoteLevel.value() == 1)
+            {
+                return unquote(cdr);
+            }
+            --(*quasiquoteLevel);
+        }
+        else if (carStr == "quasiquote")
+        {
+            ++(*quasiquoteLevel);
+        }
     }
-    return ExprPtr{new Cons{parseAsQuoted(car, quasi), consToQuoted(cdr, quasi)}};
+    return ExprPtr{new Cons{parseAsQuoted(car, quasiquoteLevel), consToQuoted(cdr, quasiquoteLevel)}};
 }
 
-inline auto parseAsQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr
+// TODO: change quasi to quote level.
+inline auto parseAsQuoted(MExprPtr const& mexpr, std::optional<int32_t> quasiquoteLevel) -> ExprPtr
 {
     if (auto atomic = tryMAtomic(mexpr))
     {
         return atomicToQuoted(atomic);
     }
 
     // else mexpr is cons, map quote on it
-    return consToQuoted(mexpr, quasi);
+    return consToQuoted(mexpr, quasiquoteLevel);
 }
 #endif // LISP_PARSER_H
diff --git a/sample/CMakeLists.txt b/sample/CMakeLists.txt
@@ -123,4 +123,6 @@ do_test(test_short_quote_quoted_list "''(x)" "\\\\('quote \\\\('x\\\\)\\\\)")
 do_test(test_quote_unquote_sym "(quote (unquote 'x))" "'x")
 do_test(test_quasiquote_unquote_lst "`,(+ 1 2)" "3")
 do_test(test_quasiquote_lst_unquote_lst "`(,(+ 1 2))" "(3)")
-do_test(test_quasiquote_pair_unquote_lst "`(1 . ,(+ 1 2))" "(1 . 3)")
+do_test(test_quasiquote_pair_unquote_lst "`(1 . ,(+ 1 2))" "(1 . 3)")
+
+do_test(test_quasiquote_nested_unquote "\`(1 \`,(+ 1 ,(+ 2 3)) 4)" "\\\\(1 \\\\(\'quasiquote \\\\(\'unquote \\\\(\'\\\\+ 1 5\\\\)\\\\)\\\\) 4\\\\)")
diff --git a/src/evaluator.cpp b/src/evaluator.cpp
@@ -1,5 +1,4 @@
 #include "lisp/evaluator.h"
-#include "lisp/parser.h"
 
 ExprPtr true_()
 {
@@ -29,8 +28,3 @@ ExprPtr Definition::eval(std::shared_ptr<Env> const& env)
 {
     return env->defineVariable(mVariableName, mValue->eval(env));
 }
-
-ExprPtr Unquote::eval(std::shared_ptr<Env> const& env)
-{
-    return parse(mInternal)->eval(env);
-}

Original file line number	Diff line number	Diff line change
`@@ -97,7 +97,7 @@ inline ExprPtr or_(MExprPtr const& mexpr)`
`97`	`97`	`return std::make_shared<Or>(parseActions(mexpr));`
`98`	`98`	`}`
`99`	`99`
`100`		`-inline auto parseAsQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr;`
	`100`	`+inline auto parseAsQuoted(MExprPtr const& mexpr, std::optional<int32_t> quasiquoteLevel) -> ExprPtr;`
`101`	`101`
`102`	`102`	`inline MExprPtr assertIsLastAndGet(MExprPtr const& mexpr)`
`103`	`103`	`{`
`@@ -113,12 +113,12 @@ inline MExprPtr assertIsLastAndGet(MExprPtr const& mexpr)`
`113`	`113`
`114`	`114`	`inline ExprPtr quote(MExprPtr const& mexpr)`
`115`	`115`	`{`
`116`		`- return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasi = */ false);`
	`116`	`+ return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasiquoteLevel = */ {});`
`117`	`117`	`}`
`118`	`118`
`119`	`119`	`inline ExprPtr quasiquote(MExprPtr const& mexpr)`
`120`	`120`	`{`
`121`		`- return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasi = */ true);`
	`121`	`+ return parseAsQuoted(assertIsLastAndGet(mexpr), /* quasiquoteLevel = */ 1);`
`122`	`122`	`}`
`123`	`123`
`124`	`124`	`inline ExprPtr definition(MExprPtr const& mexpr)`
`@@ -321,10 +321,10 @@ inline auto atomicToQuoted(ExprPtr const& expr)`
`321`	`321`
`322`	`322`	`inline ExprPtr unquote(MExprPtr const& mexpr)`
`323`	`323`	`{`
`324`		`- return ExprPtr{new Unquote{assertIsLastAndGet(mexpr)}};`
	`324`	`+ return parse(assertIsLastAndGet(mexpr));`
`325`	`325`	`}`
`326`	`326`
`327`		`-inline auto consToQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr`
	`327`	`+inline auto consToQuoted(MExprPtr const& mexpr, std::optional<int32_t> quasiquoteLevel) -> ExprPtr`
`328`	`328`	`{`
`329`	`329`	`if (mexpr == MNil::instance())`
`330`	`330`	`{`
`@@ -334,21 +334,34 @@ inline auto consToQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr`
`334`	`334`	`ASSERT(cons);`
`335`	`335`	`auto car = cons->car();`
`336`	`336`	`auto cdr = cons->cdr();`
`337`		`- if (quasi && car->toString() == "unquote")`
	`337`	`+ auto carStr = car->toString();`
	`338`	`+ if (quasiquoteLevel)`
`338`	`339`	`{`
`339`		`- return unquote(cdr);`
	`340`	`+ if (carStr == "unquote")`
	`341`	`+ {`
	`342`	`+ if ( quasiquoteLevel.value() == 1)`
	`343`	`+ {`
	`344`	`+ return unquote(cdr);`
	`345`	`+ }`
	`346`	`+ --(*quasiquoteLevel);`
	`347`	`+ }`
	`348`	`+ else if (carStr == "quasiquote")`
	`349`	`+ {`
	`350`	`+ ++(*quasiquoteLevel);`
	`351`	`+ }`
`340`	`352`	`}`
`341`		`- return ExprPtr{new Cons{parseAsQuoted(car, quasi), consToQuoted(cdr, quasi)}};`
	`353`	`+ return ExprPtr{new Cons{parseAsQuoted(car, quasiquoteLevel), consToQuoted(cdr, quasiquoteLevel)}};`
`342`	`354`	`}`
`343`	`355`
`344`		`-inline auto parseAsQuoted(MExprPtr const& mexpr, bool quasi) -> ExprPtr`
	`356`	`+// TODO: change quasi to quote level.`
	`357`	`+inline auto parseAsQuoted(MExprPtr const& mexpr, std::optional<int32_t> quasiquoteLevel) -> ExprPtr`
`345`	`358`	`{`
`346`	`359`	`if (auto atomic = tryMAtomic(mexpr))`
`347`	`360`	`{`
`348`	`361`	`return atomicToQuoted(atomic);`
`349`	`362`	`}`
`350`	`363`
`351`	`364`	`// else mexpr is cons, map quote on it`
`352`		`- return consToQuoted(mexpr, quasi);`
	`365`	`+ return consToQuoted(mexpr, quasiquoteLevel);`
`353`	`366`	`}`
`354`	`367`	`#endif // LISP_PARSER_H`
Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,4 @@`
`1`	`1`	`#include "lisp/evaluator.h"`
`2`		`-#include "lisp/parser.h"`
`3`	`2`
`4`	`3`	`ExprPtr true_()`
`5`	`4`	`{`
`@@ -29,8 +28,3 @@ ExprPtr Definition::eval(std::shared_ptr<Env> const& env)`
`29`	`28`	`{`
`30`	`29`	`return env->defineVariable(mVariableName, mValue->eval(env));`
`31`	`30`	`}`
`32`		`-`
`33`		`-ExprPtr Unquote::eval(std::shared_ptr<Env> const& env)`
`34`		`-{`
`35`		`- return parse(mInternal)->eval(env);`
`36`		`-}`