Implementing quasiquotation (qq) is challenging! The implementation of qq in LispBM is based on Bawden's paper Quasiquotation in Lisp. To understand the algorithms from Bawden's appendix and to turn them into continuation passing style C code took a lot of effort! The correctness of the implementation is a big concern of mine.
This page compares LispBM's quasiquote expansion with Guile 3 as a way to explore similarities and differences and to, perhaps, gain some confidence that LispBM quasiquotation is OK and useful.
A comparison to a more standard Scheme is also useful for people with that experience if at some point they would want to write a LispBM program.
Overview of Quasiquotation
Quasiquotation allows you to create templates where most of the structure is quoted (literal), but specific parts can be unquoted for evaluation. The three main constructs are:
`(quasiquote) - Creates a template.,(unquote) - Evaluates an expression within the template.,@(unquote-splicing) - Evaluates and splices a list into the template.
Quasiquotation Examples
The examples below compare quasiquotation expansion between LispBM and Guile. In the cases where a quasiquoted expression expands identically between LispBM and Guile, the background will be green. Sometimes the quasiquoted expression expands differently in LispBM and Guile. In these cases we follow up with a comparison of evaluating the two expressions. If two expressions are identical after evaluation the background will be blue and LispBM and Guile will be considered to semantically be identical in their handling of that expression. If the results differ both in expansion and after evaluation, the background is red.
| LispBM | Guile 3 (Scheme R5RS) |
|---|---|
`(,@(list 1 2 3)) ; Result: (1 2 3) |
`(,@(list 1 2 3)) ; Result: (1 2 3) |
`(a ,@(list 1 2) b) ; Result: (a 1 2 b) |
`(a ,@(list 1 2) b) ; Result: (a 1 2 b) |
`(,@()) ; Result: nil |
`(,@()) ; Result: ERROR or unsupported |
`(1 ,@(list 2 3) 4) ; Result: (1 2 3 4) |
`(1 ,@(list 2 3) 4) ; Result: (1 2 3 4) |
``(a ,,(+ 1 2)) ; Result: (append (quote (a)) (list 3)) ; Eval: (a 3) |
``(a ,,(+ 1 2)) ; Result: (quasiquote (a (unquote 3))) ; Eval: (a 3) |
`(quote ,@(list 1 2)) ; Result: (quote 1 2) |
`(quote ,@(list 1 2)) ; Result: (quote 1 2) |
`(,@(cdr (quote (0 1 2 3)))) ; Result: (1 2 3) |
`(,@(cdr (quote (0 1 2 3)))) ; Result: (1 2 3) |
`(list ,@(list 1 2 3)) ; Result: (list 1 2 3) |
`(list ,@(list 1 2 3)) ; Result: (list 1 2 3) |
`,'a ; Result: a |
`,'a ; Result: a |
``,a ; Result: a ; Eval: variable_not_bound |
``,a ; Result: (quasiquote (unquote a)) ; Eval: Unbound variable: a |
`,`a ; Result: a |
`,`a ; Result: a |
`(1 . 2) ; Result: (1 . 2) |
`(1 . 2) ; Result: (1 . 2) |
`',(car ()) ; Result: (quote nil) |
`',(car ()) ; Result: ERROR or unsupported |
`(,1 ,2 . ,3) ; Result: (1 2 . 3) |
`(,1 ,2 . ,3) ; Result: (1 2 . 3) |
`(,@nil ,1) ; Result: (1) |
`(,@nil ,1) ; Result: ERROR or unsupported |
`(1 2 ,@() ,@() 3) ; Result: (1 2 3) |
`(1 2 ,@() ,@() 3) ; Result: ERROR or unsupported |
``(,,@(list 0 1 2)) ; Result: (list 0 1 2) ; Eval: (0 1 2) |
``(,,@(list 0 1 2)) ; Result: (quasiquote ((unquote 0 1 2))) ; Eval: (0 1 2) |
``(,,@(cdr '(0 1 2 3)) ,4) ; Result: (append (list 1 2 3) (list 4)) ; Eval: (1 2 3 4) |
``(,,@(cdr '(0 1 2 3)) ,4) ; Result: (quasiquote ((unquote 1 2 3) (unquote 4))) ; Eval: (1 2 3 4) |
``(1 2 ,,@() ,,@()) ; Result: (append (quote (1 2)) (list) (list)) |
``(1 2 ,,@() ,,@()) ; Result: ERROR or unsupported |
``(a ,,(+ 1 2) ,(+ 3 4)) ; Result: (append (quote (a)) (list 3) (list (+ 3 4))) ; Eval: (a 3 7) |
``(a ,,(+ 1 2) ,(+ 3 4)) ; Result: (quasiquote (a (unquote 3) (unquote (+ 3 4)))) ; Eval: (a 3 7) |
`5 ; Result: 5 |
`5 ; Result: 5 |
`,5 ; Result: 5 |
`,5 ; Result: 5 |
(let ((x 5)) `(let ((x ,(+ x 10))) `(list ,,x ,x))) ; Result: (let ((x 15)) (append (quote (list)) (list 5) (list x))) ; Eval: (list 5 15) |
(let ((x 5)) `(let ((x ,(+ x 10))) `(list ,,x ,x))) ; Result: (let ((x 15)) (quasiquote (list (unquote 5) (unquote x)))) ; Eval: (list 5 15) |
`,@0 ; Result: read_error ; Eval: read_error |
`,@0 ; Result: (unquote-splicing 0) ; Eval: ERROR |
`(1 2 ,@'(3 . 4)) ; Result: (1 2 3 . 4) |
`(1 2 ,@'(3 . 4)) ; Result: (1 2 3 . 4) |
`(1 2 ,@(list 3 4 5) ,@(list 6 7 8) 9 10) ; Result: (1 2 3 4 5 6 7 8 9 10) |
`(1 2 ,@(list 3 4 5) ,@(list 6 7 8) 9 10) ; Result: (1 2 3 4 5 6 7 8 9 10) |
`(1 2 ,@'() ,@'() 3) ; Result: (1 2 3) |
`(1 2 ,@'() ,@'() 3) ; Result: (1 2 3) |
``(1 2 ,,@'() ,,@'()) ; Result: (append (quote (1 2)) (list) (list)) ; Eval: (1 2) |
``(1 2 ,,@'() ,,@'()) ; Result: (quasiquote (1 2 (unquote) (unquote))) ; Eval: (1 2) |
Important note about nil
Guile does not have a nil so some of the comparisons above are a bit unfair. Look at the example below that in Guile is an error because nil is not defined by default:
`(,@nil ,1)
Unbound variable: nil
If we define nil to be the empty list in guile then the following happens:
(define nil '())
scheme@(guile-user) [5]> `(,@nil ,1)
$1 = (1)
So in that case it behaves the same as LispBM. So let's try one more thing:
`(,@() ,1)
While compiling expression:
Syntax error:
unknown location: unexpected syntax in form ()
Here we get an error again. Let's try one more thing in guile:
`(,@'() ,1)
$2 = (1)
In this final case Guile and LispBM behave exactly the same again.
Deeply nested quasiquotes
Example: `(list 1 `(,@(list 1 2 3) `(,@(list 4 5 6))))
The example above is an expression with deeply nested quasiquotes. These do not fit the pattern used in the tests above where either the quasiquote expands equally in LispBM and Guile or we check if they are Semantically equivalent after one round of evaluation.
In this case we would need to traverse into the result and evaluate subtrees then test equality of value.
LispBM expands the example as follows: (list 1 (append (list 1 2 3) (list (quote (list 4 5 6))))).
Guile expands the same example as: (list 1 (quasiquote ((unquote-splicing (list 1 2 3)) (quasiquote ((unquote-splicing (list 4 5 6)))))))
After one round of LispBM evaluation: (1 (1 2 3 (list 4 5 6)))
After one round of Guile evaluation: (1 (1 2 3 (quasiquote ((unquote-splicing (list 4 5 6))))))
The two final expressions are semantically equivalent because in LispBM (list 4 5 6) evaluates to (4 5 6) and
in Guile (quasiquote ((unquote-splicing (list 4 5 6)))) also evaluates to (4 5 6).
LispBM Arrays vs Guile Vectors in Quasiquotation
Another difference between LispBM and Guile is how they handle array/vector data structures within quasiquotation contexts. Both languages have array-like structures, but they integrate differently with the quasiquote system.
Guile Vectors with Quasiquotation
Guile has vectors with literal syntax #(...) that integrates seamlessly with quasiquotation.
As I understand it, the # can be thought of as a ' for vectors.
;; Literal vector (no evaluation)
#(1 2 (+ 1 2)) ; → #(1 2 (+ 1 2))
;; Vector with quasiquote (selective evaluation)
`#(,(+ 1 2) 4) ; → #(3 4)
;; Vector constructor (full evaluation)
(vector (+ 1 2) 4) ; → #(3 4)
LispBM Arrays with Quasiquotation
LispBM has arrays with literal syntax [| ... |] that are always literal,
regardless of quasiquote context:
;; Literal array (no evaluation)
[| 1 2 (+ 1 2) |] ; → [| 1 2 (+ 1 2) |]
;; Array in quasiquote (still no evaluation!)
`[| ,(+ 1 2) 4 |] ; → [|([comma] (+ 1 2)) 4|]
;; Array constructor (full evaluation)
`(array ,(+ 1 2) 4) ; → (array 3 4), which evaluates to an array
The example where `[| ,(+ 1 2) 4 |] becomes [|([comma] (+ 1 2)) 4|]
is unfortunate. The [comma] is how LispBM prints the comma symbol, and this
internal symbol should not be a part of any fully parsed expression. This is
an example of where an internal implementation detail is leaking out and becomes visible to the
user. This will be fixed by in a future version of LispBM.
Explanation
LispBM is meant for systems with very limited ram and uses different memory regions for cons-cell heap
and for more array like data (array-memory). The literal syntax for arrays [| ... |], is processed
entirely in the reader and the array can be allocated and filled with data without any involvement of
the evaluator. To allow the comma , and comma-at ,@ operations inside of an
[| ... |] array would mean that the actual array in array-memory cannot be created
until evaluation time and the data will be intermediately stored on the heap as well as on the evaluation stack.
The chosen approach means that arrays specified using [| ... |] can be larger than
the evaluation stack as well as larger than the available cons-cell heap even.
Note that the [ ... ] byte array syntax in LispBM is also entirely
literal for the exact same reasons.
Conclusion
There are differences but I am not sure these are very important. LispBM seems to handle these cases of quasiquotation perfectly fine.
If you have examples of interesting quasiquotes please send me a message. I would love to expand on this comparison and to explore the limits of the quasiquoter. If we are lucky we find some bugs (hopefully fixable) along the way!