is quasiquotation correct?

[dragoncoder047]

I implemented quasiquotation using the MAL tutorial, which is based off of Clojure... Clojure is most definitely not Common Lisp... are the behavior of nested quasiquotes correct/compliant with Common Lisp?

@technoblogy if you have a quasiquote test suite I'd be happy to try it out.

[technoblogy]

I can put something together for you, probably tomorrow.

[technoblogy]

Have you implemented , (comma) and @ too?

[dragoncoder047]

I did all 3 reader macros (`, ,, and ,@) but if you're basing anything off of Dave Astel's code do note that he couldn't figure out how to parse ,@ and so he just used @ instead.

Once I know that quasiquotes work, I'm going to try to add macros.

Do you think this kind of thing would be something you would want to add to uLisp in a new version (maybe not available for arduino uno and low-flash platforms)?

[technoblogy]

but if you're basing anything off of Dave Astel's code do note that he couldn't figure out how to parse ,@ and so he just used @ instead.

I couldn't get Dave Astel's code to give sensible results, so I didn't get very far with that.

Do you think this kind of thing would be something you would want to add to uLisp in a new version (maybe not available for arduino uno and low-flash platforms)?

Definitely!

[technoblogy]

Here are some tests:

(defvar ers 0)

(defun aeq (tst x y)
  (unless (equal x y)
    (incf ers)
    (format t "~a = ~a / ~a~%" tst x y)))

(aeq 'quasiquote 'cat `cat)

(aeq 'quasiquote '(cat 3 dog) `(cat ,(+ 1 2) dog))

(aeq 'quasiquote '(cat 3 4 dog) `(cat ,@(list 3 4) dog))

(aeq 'quasiquote '(unless 23 (return)) (let ((me 23)) `(unless ,me (return))))

(aeq 'quasiquote '(cat 6) `(cat ,(+ `,(+ 3 2) 1)))

(aeq 'quasiquote '(unless 23 (return)) (let ((me 23)) `(unless ,me (return))))

(aeq 'quasiquote '(cat (+ 3 ((+ 4 12)))) (let ((me 23)) `(cat (+ 3 ,(list `(+ 4 ,(* 3 4)))))))

The function aeq takes three arguments: a label for the test, the required result, and the form to be evaluated. It returns nil if the test passes, or prints the mismatch if it fails.

[technoblogy]

Also, here's an example to show why it would be nice to have macros in uLisp. By the way, the usual term in Lisp is backquote rather than quasiquote.

A C programmer would like to extend Lisp with a for-loop construct so they could write something like:

(defun test ()
  (for ((i 0) (< i 10) (incf i))
    (format t "~a ~a~%" i (* i i))))

Here's the Lisp macro that would achieve this:

(defmacro for ((init condition increment) &body body)
  `(let (,init)
     (loop
      (unless ,condition (return))
      ,@body
      ,increment)))

It could also be written slightly less elegantly without backquote like this:

(defmacro for ((init condition increment) &body body)
  (list 'let (list init)
        (append
         (list 'loop (list 'unless condition '(return)))
         body
         (list increment))))

Just to clarify: the above code doesn't currently work in uLisp!

[technoblogy]

Another couple of interesting ones:

(aeq 'quasiquote '(a b c . 43) (let ((foo 43)) `(a b c . ,foo)))

(aeq 'quasiquote '(a b c . 43) (let ((foo 43)) `(a b c ,@foo)))

[dragoncoder047]

Here are some tests:

They all pass! 👏

Another couple of interesting ones:

These two fail. The first one winds up with (a b c unquote foo), the second one fails with Error: 'append' argument is not a list: 43. I suppose that the approach I took is at fault here. The MAL page had two algorithms, a recursive one (which I feared would blow up the stack for large quasibackquoted S-expressions) and an iterative one, which apparently borks when it isn't a proper list.

Just to clarify: the above code doesn't currently work in uLisp!

I do plan to implement macros!

[dragoncoder047]

Another fun one (it passes):

(aeq :quine
  '(let ((let '`(let ((let ',let)) ,let))) `(let ((let ',let)) ,let))
   (let ((let '`(let ((let ',let)) ,let))) `(let ((let ',let)) ,let))
)

I got this from https://3e8.org/pub/scheme/doc/Quasiquotation%20in%20Lisp%20(Bawden).pdf.

[dragoncoder047]

Going to close this now, backquotes appears to be working good enough to call them done. Macros would be a separate issue.

[technoblogy]

Look forward to playing with your macros!

[dragoncoder047]

Look forward to playing with your macros!

Unfortunately they don't work quite yet... here's the current state of the macros:

> (defmacro for ...) ; from above
for
> (macroexpand '(for ((i 0) (< i 10) (incf i)) (princ "foo")))
((for ((i 0) (< i 10) (incf i)) (princ "foo")))

Not sure what the hangup in macroexpand is...

[technoblogy]

Yes, you should get this:

> (macroexpand '(for ((i 0) (< i 10) (incf i)) (princ "foo")))
(let ((i 0)) (loop (unless (< i 10) (return)) (princ "foo") (incf i)))
T

[dragoncoder047]

Macros are sorta working now as of dd0f3f8. I got this to expand properly:

> (macroexpand '(for ((i 0) (< i 10) (incf i)) (princ "foo")))
(let ((i 0)) (loop (unless (< i 10) (return)) (princ "foo") (incf i)))

Destructuring lambda params aren't supported so I used this definition:

(defmacro for (ici &rest body)
  (unless (= 3 (length ici)) (error "(for) header must be 3 elements (init condition increment)"))
  `(let (,(car ici))
     (loop
      (unless ,(cadr ici) (return))
      ,@body
      ,(caddr ici))))

However, they are behaving a little strange:

> (defmacro foo (x) (foo x))
foo

> (foo 1)
Error: infinitely recursive macro detected

That was expected.

> (defmacro foo (x) `(foo ,x))
foo

> (foo 1)
Error: 'cons' too many arguments

Super weird error. I was just expecting it to hang. Maybe it has something to do with the GCStack?

[technoblogy]

Cool! I'll take a look at it.

[technoblogy]

By the way, the GCStack is only needed to prevent corruption during a garbage collection. If the problem still occurs when no garbage collection has happened it's something else. To test it uncomment:

// #define printgcs

and comment out this line in repl():

gc(NULL, env);

Do a manual (gc) before starting. If you've got enough workspace you should be able to test everything without a gc occurring.

[dragoncoder047]

By the way, the GCStack is only needed to prevent corruption during a garbage collection.

macroexpand1() calls closure() and eval(), which may invoke the garbage collector. As of the latest commit I did add some GCStack protections around the calls to eval in the macro-expanding functions, but I still got the weird "'cons' too many arguments" error nonetheless.

Also, the macro expansion code isn't properly tail-recursive. In macroexpand1() it eval's the result before returning it, which blows up the stack even on tail-calls of macros. I used the macro (defmacro foo (x) (foo x)) to test this. Without any protection you will get a C stack overflow and a coredump. I initially added some code in macroexpand1() that checked to see if the previous macro is equal to the current, and bail if it is, but that blocked more macro calls than it was supposed to and so I removed that. The final fix was manually adding a stack overflow check in eval (which conveniently protects against recursion in non-tail positions such as (defun x () (x) (x))). I'm hoping to be able to make this more tail-recursive optimized to go along with uLisp (but then again how often are you going to get a recursive macro).

[technoblogy]

which may invoke the garbage collector

Unless you are explicitly calling gc() in your C code, the garbage collector will not get called unless you're running low on workspace.