Metaprogramming experiments in PicoLispTo follow along,
$ git clone https://github.com/erdg/pl-defmacro.git $ cd pl-defmacro/ $ pil m.l + : (mload "mac.m.l") : (load "mac.tests.l") mac.m.l -- all tests passed -> TI was playing around with Common Lisp macros in PicoLisp. It was mostly a joke, but it got me thinking. I find quasiquote to be such a wonderful DSL for list interpolation and macro writing. What would it take to implement "native" quasiquote-style macros in Picoisp? (i.e. without using transient symbols, as in the link above)
The problem is that both backquote ` and comma , are aleady read-macros in PicoLisp. So technically I don't want to be writing PicoLisp code anymore - I want to be writing code in a language that is mostly PicoLisp, except that ` and , (and consequently ,@) behave as if I was writing Common Lisp code.
The Picolisp macro languageLet's call this new language the PicoLisp macro language. Macro language code lives in .m.l files. By convention all code in an "mfile" is contained in one top-level call to m.
# 'square.m.l' (m (mac square (X) `(,X ,X)) ... )mfiles are loaded into PicoLisp with the function mload.
: (mload "square.m.l") # no need for this step -> square # if "following along" : (square 3) -> 9Here's the definition of mload:
(de mload (File) (run (cdr (transform (mread File) ) ) ) ) (def 'MREADSTRING "_-=!?<>$*") # read a macro file (".m.l" by convention) (de mread (File) (in File (make (while (read MREADSTRING) (link @) ) ) ) )mload reads a file, transforms it from PL macro language to normal PicoLisp, and evals all the forms. mread uses the "low-level" mode of the built-in read to read an mfile into PicoLisp as a list of symbols. Parens and ` and , are read in as transient-symbols, while everything else is read in as internal symbols. This list of symbols is then transformed into a list of actual PicoLisp code.
(de transform (Lst) (any (glue " " (_transform Lst) ) ) ) (de _transform (X) (recur (X Acc) (ifn X (flip Acc) (case (car X) ("`" (recurse (cdr X) (cons (sym "`") Acc)) ) ("," (if (= (cadr X) "@") (recurse (cddr X) (cons (sym ",@") Acc)) (recurse (cdr X) (cons (sym ",") Acc)) ) ) (T (recurse (cdr X) (cons (car X) Acc))) ) ) ) )_transform simply recurses over the list to create a copy. Anytime ` or , or ,@ is encountered, sym is called so it remains a transient symbol. The resulting list is glueed together with spaces to create a string. The string is converted to a list with any and all forms in the cdr (discard the dummy function m) are evaled.
To break it down:
# code in square.m.l (m (mac square (X) `(* ,X ,X)) ) # normal picolisp repl now : (mload "square.m.l") (mread "square.m.l") -> ("(" m "(" mac square "(" X ")" "`"(* "," X "," X ")" ")" ")" ) (glue " " (_transform @)) -> "(m ( mac square ( X ) "\"`\"" ( * "\",\"" X "\",\"" X ) ) )" (any @) -> (m (mac square (X) "`"(* ","X ","X))) (cdr @) -> ((mac square (X) "`"(* ","X ","X))) (mapc eval @) -> square : (square 9) -> 81
m1 - the (one-shot) macro replIf mfiles are a layer over normal PicoLisp files to allow "native" use of quasiquote forms, a "macro repl" would be a layer over the normal PicoLisp repl.
: (m1) m1 -- the macro repl : (let X 2 (quasiquote `(* ,X ,X)))^ # hat '^' to end -> (* 2 2) -> NIL # no idea why there are two "returns"The macro repl is easy to implement in PicoLisp.
(de m1 () (prinl "m1 -- the macro repl") (prin ": ") (let M (till '^) # hat '^' to end (prog (out (tmp "mrepl") (prin M)) (eval (transform (mread (tmp "mrepl"))) ) ) ) )All input till the hat ^ character is written to a temporary file. That file (one lisp form) is then read, transformed and evaluated.
Note that evaling a quasiquote form is functionally the same as the PL built-in macro,
: (m1) m1 -- the macro repl : (let X 2 (eval (quasiquote `(* ,X ,X))))^ -> 4 -> NIL : (let @X 2 (macro (* @X @X))) -> 4and using macro on a quoted list is the same as quasiquote.
: (let @X 2 (macro '(* @X @X))) -> (* 2 2) : (m1) m1 -- the macro repl : (let X 2 (quasiquote `(* ,X ,X)))^ -> (* 2 2) -> NILWith mfiles and the macro repl in place, it's time to bootstrap a useful macro-writing environment!
A macro-writing macromac is the PicoLisp (macro language) equivalent of Common Lisp's defmacro.
(de mac Lst # unevaluated args (let [(Nm Args . Body) Lst] # are destructured (eval (quasiquote # and filled in `(de ,Nm Lst (let [,Args Lst] (eval (quasiquote ,@Body) ) ) ) ) ) ) )This is fine, but there's a lot of noise in the definition. Let's clean it up a bit.
Read-macros to the rescueThe evq read-macro was created because (eval (quasiquote ...)) is such a common pattern. With evq, the definition of mac becomes:
(de mac Lst (let [(Nm Args . Body) Lst] ~(evq `(de ,Nm Lst (let [,Args Lst] ~(evq ,@Body) ) ) ) ) )Much more concise.
Here's the definition of evq:
# normal picolisp code (de eval-quasiquote Lst (macro '((eval (quasiquote ^ Lst))) ) ) (def 'evq eval-quasiquote)It transforms (evq ...) into (eval (quasiquote ...)) as the code is read. As such, the previous two definitions of mac are identical as far as the PicoLisp interpreter is concerned.
Note that evq returns a list wrapped in an extra layer of parens. This is because the tilde ~ read-macro is used to splice it in. Remember that the backquote ` read-macro has been shadowed in mfiles, so the ~ read-macro must be used.
Another common pattern is (let [...] (eval (quasiquote ...))). leq was created as an abbreviation. leq allows to concisely express quasiquote macros with variable bindings using the same syntax as let.
Here's the definition of leq:
# normal picolisp code (de let-eval-quasiquote Lst (let [(Args . Body) (leqargs Lst)] (macro '((let ^ Args (eval (quasiquote ^ Body )))) ) ) ) (de leqargs (Lst) (let [L (_leqargs Lst) I (index (find pair L) L) Args (head I L) Body (tail (- I) L)] (macro '((^ Args) ^ Body)) ) ) (de _leqargs (Lst) (if (atom (car Lst)) (cons (car Lst) (_leqargs (cdr Lst))) Lst ) )It works the same as the evq read-macro, but requires some extra processing of arguments to correctly parse the (possibly unquoted) 'let' args and body
Using leq, the definition of macro becomes:
# macro language code (de mac Lst ~(leq [(Nm Args . Body) Lst] `(de ,Nm Lst ~(leq [,Args Lst] ,@Body) ) ) )Now that is a sharp piece of code! And once again, because leq is a read-macro that transforms the raw list structure, this definition is the same as the previous few.
Writing new macrosmac can be used to define macros (in mfiles).
# macro language code (mac aif (Test Then Else) `(let it ,Test (if it ,Then ,Else) ) ) # NOTE - 'aif' is merely an example macro and would never be used in # picolisp because the same functionality exists in the built-in # 'if'aif is an "anaphoric" macro that captures the symbol it and binds it to the result of the Test expression so it can be refered to without having to explicitly create new variables.
# normal picolisp code (de add2-safe (N) (aif (num? N) (+ 2 it) (prinl "ERROR - " it " is NOT a number")) )As expected, the definition of aif has the (eval (quasiquote ...)) pattern:
# normal picolisp code, transformed from macro language : (pretty aif) (Lst (let ((Test Then Else) Lst) (eval (quasiquote "`"(let it "," Test (if it "," Then "," Else) ) ) ) ) )
mc - the macro compilerIf aif is going to be used heavily, a serious run-time performance hit will be taken. eval and quasiquote are pretty expensive operations. But there's nothing in aif's run-time code that will require quasiquote. Remember that "eval quasiquote" forms are just a different way of writing PicoLisp macros. It turns out that a "macro compiler" can be written which turns "eval quasiquote" macros into normal PicoLisp macros by "precomputing" the translation.
Well this is exactly what quasiquote does! Looking at the definition,
(de quasiquote Lst (macro (macro (^(macro (_quasiquote ^ Lst))) ) ) )the translation happens in two parts. First quasiquote passes the list to the internal function _quasiquote
(_quasiquote "`"(let it "," Test (if it "," Then "," Else) ) )_quasiquote does the actual transformation on the raw list structure. (see source or explanation) At this point nothing has been evaluated and _quasiquote returns the translation
'(let it ^ (list Test) (if it ^ (list Then) ^ (list Else)) )quasiquote then passes this list to macro to fill in the values. The translation (_quasiquote) is distinct from the execution (quasiquote), and thus can be "precomputed" and the macro can be redefined.
Which is what mc (the macro compiler) does. (see source) The idea is to pipe the macro definition
(eval (quasiquote "`"(let it "," Test (if it "," Then "," Else) ) ) )to low-level read to transform (eval (quasiquote ...)) forms into (macro `(_quasiquote ...))" forms (with a backquote ` read-macro), like so
(macro `(_quasiquote "`"(let it "," Test (if it "," Then "," Else) ) ) )bring this back to PicoLisp so the backquote read-macro fires
(macro '(let it ^ (list Test) (if it ^ (list Then) ^ (list Else)) )pipe that back to low-level read to remove the quotes from the macro lists and finally bring it back to PicoLisp again where it can run like normal
(macro (let it ^ (list Test) (if it ^ (list Then) ^ (list Else)) )
Compiled macrosmc can be used to define a compiled version of a macro
: (def 'aifc (mc aif)) -> aifc : (pretty aif) (Lst (let ((Test Then Else) Lst) (eval (quasiquote "`"(let it ","Test (if it "," Then "," Else) ) ) ) ) ) : (pretty aifc) (Lst (let ((Test Then Else) Lst) (macro (let it ^ (list Test) (if it ^ (list Then) ^ (list Else)) ) ) ) )Compiled macros are an order of magnitude faster.
: (bench (do 1000000 (aif (+ 1 2) (+ 3 it)))) 2.646 sec -> 6 : (bench (do 1000000 (aifc (+ 1 2) (+ 3 it)))) 0.308 sec -> 6The compiler could be improved by further "compiling" to more efficient forms that don't use macro, but that is beyond the scope of this article.
A moment of reflectionSo what's the point of all this? Ostensibly, it allows the use of a more convenient syntax for code transformations.
# write this (mac aif (Test Then Else) `(let it ,Test (if it ,Then ,Else) ) ) # get this (compiled) (de aif Lst (let [(Test Then Else) Lst] (macro (let it ^ (list Test) (if it ^ (list Then) ^ (list Else)) ) ) ) )While it's not much of an improvement for such a simple macro, it does make it easy to write more complex macros.
(mac defunits (Quantity Base . Units) `(mac! ,(symb 'unit-of- Quantity) (!Val !Unit) `(* ,,$Val (case ,,$Unit (,Base 1) ,@(mapcar ~(qfn (X) # read-macro for quasiquote fns `(,(car X) ,(defunits-chaining (car X) (cons (quasiquote `(,Base 1)) (groups 2 Units) ) ) ) ) (groups 2 Units) ) ) ) ) )The best part is that the whole system is just a bunch of PicoLisp functions (FEXPRS really). Everything can be debugged and stepped, traced, etc - a deep understanding of the system can be gained.
But it could be argued whether such "macros" have any place in PicoLisp...
So maybe more realistically, the point of all this is to show just how flexible and powerful PicoLisp is. A pretty impressive (toy) Common Lisp Macro System can be added to PicoLisp with roughly 300 lines of code.
(NOTE - the following sections offer PicoLisp translations of defmacro/g!, defmacro! and defunits from Doug Hoyte's book, Let Over Lambda)
Macros and multiple evaluationLet's return to our first macro, square (actually square-buggy if "following along")
(mac square (X) `(* ,X ,X))It works as expected for simple numbers,
: (square 3) -> 9but unexpected things start happening when side-effects are involved.
: (let Y 2 (square (inc 'Y))) # expect 9 -> 12 # -_-Looking at the compiled version of square,
: (pretty (mc square)) -> (Lst (let ((X) Lst) (macro (* ^ (list X) ^ (list X)))))it can be seen that X is listed (and thus evaluated) twice. So the above call was actually,
: (let Y 2 (* (inc 'Y) (inc 'Y))) # (* 3 4) -> 12instead of the expected
: (square 3)One possible solution is to introduce a new anonymous symbol (with box) and then bind the argument X to it.
(mac square (X) (let $X (box) `(let ,$X ,X (* ,$X ,$X) ) ) )This works as expected.
: (let Y 2 (square (inc 'Y))) -> 9
mac$Multiple evaluation is a pretty common problem and it would be annoying to have to manually create so many boxes. Better to write another macro. mac$ is a variation of mac that scans its Body for "$ symbols" and automatically creates boxes.
# mac$ - 'defmacro/g!' from Let Over Lambda (de mac$ Lst ~(leq [(Name Args . Body) Lst] `(de ,Name Lst (let [,Args Lst] ~(leq ,[boxes ($syms-in Body)] ,@Body ) ) ) ) ) (de boxes (Lst) (mapcan ~(qfn `(,Q1 (box))) Lst) ) (de $syms-in (L) (uniq (filter $sym (flat L))) ) (de $sym (S) (and (sym? S) (> (length S 1)) (pre? '$ S) ) )As Doug Hoyte writes in Let Over Lambda, mac$ allows us to say:
I want a [box] to be bound around this expression, and I've already given the symbol. Make it happen.
(see Section 3.5 in Let Over Lambda)
(NOTE - this macro was named mac$ because anonymous symbols (boxes) are visually represented as e.g. $177389156348275 in PicoLisp)
Nested backquotesThis idea of "automatic boxes" can be taken a step further. (see Section 3.6 of Let Over Lambda)
# mac! - 'defmacro!' from Let Over Lambda (de mac! Lst (let [(Name Args . Body) Lst] ~(leq [!Syms (!syms-in Args) $Syms (!syms-to-$syms !Syms)] `(de ,Name Lst (let [,Args Lst] ~(leq ,[boxes ($syms-in Body)] `(let ,,[letargs (list ,@$Syms) (list ,@!Syms)] ~(evq ,@Body) ) ) ) ) ) ) ) (de !syms-in (L) (uniq (filter !sym (flat L))) ) (de !sym (S) (and (sym? S) (> (length S 1)) (pre? '! S) ) ) (de !sym-to-$sym (S) (any (pack '$ (cdr (chop S)))) ) (de !syms-to-$syms (Syms) (mapcar !sym-to-$sym Syms) ) (de letargs (Xs Ys) (mapcan list Xs Ys) )mac! is used like this:
(mac! square (!X) # args prefixed with '!' are evaluated once only `(* ,$X ,$X) ) # and referred to as prefixed with '$'mac! accomplishes this by gathering the !Args and creating the corresponding $Syms. It then searches the body of the macro being defined for any additional $Syms. All the $Syms are then bound to boxes in the expansion. Finally - when the defined macro is called (hence the nested backquotes) - the result of evaluting the provided !Args are bound to the boxes.
In other words, mac! creates a bunch of variable bindings in the macro it defines (some of which are are finally filled in during that macro's run-time) to provide a convenient way of handling variable capture and execution when writing macros.
defunitsdefunits was shown earlier, but here it is again. (see Section 5.2 of Let Over Lambda)
(mac defunits (Quantity Base . Units) `(mac! ,(symb 'unit-of- Quantity) (!Val !Unit) `(* ,,$Val (case ,,$Unit (,Base 1) ,@(mapcar ~(qfn (X) `(,(car X) ,(defunits-chaining (car X) (cons (quasiquote `(,Base 1)) (groups 2 Units) ) ) ) ) (groups 2 Units) ) ) ) ) ) (de defunits-chaining (U Units) (let Spec (assoc U Units) (ifn Spec (prinl (text "Unknown unit @1" U)) (let Chain (cadr Spec) (if (pair Chain) (* (car Chain) (defunits-chaining (cadr Chain) Units ) ) Chain ) ) ) ) )defunits is a macro used to define relationships between similar types of quantities (e.g. quantities of time - seconds, minutes, days, milliseconds, etc.)
: (defunits time s m 60 # minutes h (60 m) # hours d (24 h) # days y (365 d) # years C (100 y) # centuries M (10 C) ) # millenia -> unit-of-time # 10,000 millenia is a lot of seconds : (unit-of-time 10000 'M) -> 315360000000000 : (defunits distance-lol in ft 12 yd (3 ft) fathom (2 yd) mile (5280 ft) rod (15 ft) furlong (40 rod) chain (4 rod) league (3 mile) cubit 18 ) -> unit-of-distance-lol # compile it (def 'unit-of-distance-lol (mc unit-of-distance-lol)) : (+ (unit-of-distance-lol 156 'rod) (unit-of-distance-lol 17 'league) (unit-of-distance-lol 3 'cubit) ) -> 3259494 # inchesNested backquotes allow for general patterns like this:
You're writing a macro (the parent) that writes a macro (the child) and you need to refer to the (future) run-time arguments of the child macro right now (in the definition of the parent).
More specifically, defunits is a macro that writes another macro (unit-of-[quantity]) that captures user-defined relationships as basic multiplication (using a case statement). That's a fancy way of saying there are 60 seconds in a minute and in order to find out how many seconds are in 17 minutes we need to multiply (* 17 60).
Right now, however, we're writing a macro that defines another macro which defines relationships between (as-of-now) unknown quantities. But we know that whatever they are, we want to multiply them to get to some number of some base unit. So we use nested backquotes (and "stacked" unquotes) to name these abstract somethings and write code with them now.
As a catchphrase:
"when a macro-writing (parent) macro has run-time arguments (from the child) to use, nested backquotes will do!"
Differences to Common LispRegarding (nested) backquotes - each quasiquote call "removes" only one backquote (typically the car of Lst), while processing "one level" of 'unquote' and 'unqoute-splice's (nested arbitrarily deep) in Lst.
: (m1) m1 -- the macro repl : (let X 2 (quasiquote `(* ,X `(+ ,,X ,@(3 4 5))) ) ) -> (* 2 "`"(+ ","X 3 4 5))It is what it is, I guess. Seems easy enough to reason about and still allows for nested backquote macros that work as expected (though the exact syntax differs from common lisp).