3 ms·

I probably don't have the Common Lisp chops to comprehend them, but is any implementation of these macros available to browse?

Jtsummers 5y ago
Linked at the end of the blog: https://github.com/phoe/with-branching https://github.com/phoe/with-branching
kazinator 5y ago
Yes; there is a link to the github repo. The code isn't rocket science. It has a list of Boolean variables given to the macro, which has to just iterate over their combinatorial possibilities, and generate multiple copies of the enclosed code in which different combinations of values are bound to those variable symbols. E.g. along these lines: (hoist (a b) (code a b)) -> (cond ((and (not a) (not b)) (symbol-macrolet ((a nil) (b nil)) (code a b))) ((and (not a) b)) (symbol-macrolet ((a nil) (b t)) (code a b))) ((and a (not b)) (symbol-macrolet ((a t) (b nil)) (code a b))) ((and a b)) (symbol-macrolet ((a t) (b t)) (code a b)))) The macrolet will propagate the constants into the code, so that it turns into (code nil nil), (code nil t) and so on. Ordinary let could be used, since compilers can do constant propagation without macro assistance. The actual code looks overcomplicated; it's defining its own branching constructs, rather than trusting the compiler to do constant folding. Basically, unless your compiler sucks (in which case, what is the point), all you have to do is convert this: (+ x y (if huge-p 0 100)) ;; huge-p run-time value to this: (let ((huge-p t)) ... (+ x y (if huge-p 1000 0)) and trust the compiler to be smart enough to notice that huge-p is a constant, so that the expression can be folded to (+ x y 1000) There is no need to define any macros that imitate if, while, etc. Quick and dirty implementation: (defun hoist-expander (vars body) (if (null vars) `(progn ,@body) `(if ,(car vars) (symbol-macrolet ((,(car vars) t)) ,(hoist-expander (cdr vars) body)) (symbol-macrolet ((,(car vars) nil)) ,(hoist-expander (cdr vars) body))))) (defmacro hoist ((&rest bool-vars) &body body) (hoist-expander bool-vars body)) > (macroexpand '(hoist (a b) (lambda (arg) (if a (if b arg (foo arg)) (bar arg))))) (IF A (SYMBOL-MACROLET ((A T)) (IF B (SYMBOL-MACROLET ((B T)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG))))) (SYMBOL-MACROLET ((B NIL)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG))))))) (SYMBOL-MACROLET ((A NIL)) (IF B (SYMBOL-MACROLET ((B T)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG))))) (SYMBOL-MACROLET ((B NIL)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG)))))))) To be able to go into the code and conveniently disable this, we can define a no-hoist macro with the same syntax: (defmacro no-hoist ((&rest bool-vars) &body body) `(progn ,@body))
- Jtsummers 5y ago
  Except that the value of huge-p isn't known at compile time in the blog's described use-case, it's known at runtime, so constant propagation to remove the extra conditionals may or may not work. It depends on when those lambdas actually get compiled, doesn't it? If they get compiled and close over huge-p one time, then the inner conditional remains and gets executed every time. Thus moving the branch outside the lambdas and returning the correct lambda based on the value of huge-p. For a single boolean this is trivial to do by hand. For n booleans and 2^n combinations, it's less trivial to do by hand, thus the macro. EDIT: Nevermind, with what you added and rereading I get what you're talking about now.
- gmfawcett 5y ago
  I know you said "quick and dirty", but the unhygienic variable capture on those args is making my parens twitch. :) This was a nice explanation.
  - kazinator 5y ago
    They have to be unhygienic because the code makes references to those specific symbols. We need to bind each of those symbols to a nil and t constant against different copies of that code, thereby shadowing the original variable, based on whose value the decision is made which way to bind the shadow. Our macrology does not introduce any hidden variables of its own; we don't have anything to hide behind gensyms. We have not even evaluated any argument material twice.
    - gmfawcett 5y ago
      Of course you're right. I read your code again, and I stand corrected. Well done.
  - phoe-krk 5y ago
    You don't need hygiene (WITH-GENSYMS and so on) in Common Lisp macros in two situations: when you do not introduce any new bindings and when you only introduce bindings that the user is allowed to name themself. That's why the following code: (with-open-file (my-super-stream #p"/tmp/foo" ...) ...) Can expand into something like this: (let ((my-super-stream (open #p"/tmp/foo" ...))) ...) Note that the variable name, MY-SUPER-STREAM, is provided by the user, so if there is any variable capture/shadowing present then it is of the user's own making and they can reap the benefits and costs of doing so.
phoe-krk 5y ago
Author here. The repo link and simpler implementations were linked in sibling comments, so I'll just add a bit more explanation. The whole thing relies on the idea that Lisp macros can communicate: the outer macros can, via their expansion, pass information to the inner macros via the compilation environment, and these inner macros can then use that information to decide how they should expand. This information is available at compile-time only, but that's enough for the macros to decide what kind of code to generate - in this particular case, the choice is whether some body of code should be included in the expansion or not. This mechanism is known in the Lisp world as the SYMBOL-MACROLET trick and was described well in the article at [0] - except I think that that article could use a slightly better example, which my repository is happy to provide. [0] https://etc.ruricolist.com/2020/03/15/the-symbol-macrolet-trick/ https://etc.ruricolist.com/2020/03/15/the-symbol-macrolet-tr...
- deleted 5y ago
  [deleted]

Jtsummers 5y ago

Linked at the end of the blog: https://github.com/phoe/with-branching https://github.com/phoe/with-branching

kazinator 5y ago

Yes; there is a link to the github repo. The code isn't rocket science. It has a list of Boolean variables given to the macro, which has to just iterate over their combinatorial possibilities, and generate multiple copies of the enclosed code in which different combinations of values are bound to those variable symbols. E.g. along these lines: (hoist (a b) (code a b)) -> (cond ((and (not a) (not b)) (symbol-macrolet ((a nil) (b nil)) (code a b))) ((and (not a) b)) (symbol-macrolet ((a nil) (b t)) (code a b))) ((and a (not b)) (symbol-macrolet ((a t) (b nil)) (code a b))) ((and a b)) (symbol-macrolet ((a t) (b t)) (code a b)))) The macrolet will propagate the constants into the code, so that it turns into (code nil nil), (code nil t) and so on. Ordinary let could be used, since compilers can do constant propagation without macro assistance. The actual code looks overcomplicated; it's defining its own branching constructs, rather than trusting the compiler to do constant folding. Basically, unless your compiler sucks (in which case, what is the point), all you have to do is convert this: (+ x y (if huge-p 0 100)) ;; huge-p run-time value to this: (let ((huge-p t)) ... (+ x y (if huge-p 1000 0)) and trust the compiler to be smart enough to notice that huge-p is a constant, so that the expression can be folded to (+ x y 1000) There is no need to define any macros that imitate if, while, etc. Quick and dirty implementation: (defun hoist-expander (vars body) (if (null vars) `(progn ,@body) `(if ,(car vars) (symbol-macrolet ((,(car vars) t)) ,(hoist-expander (cdr vars) body)) (symbol-macrolet ((,(car vars) nil)) ,(hoist-expander (cdr vars) body))))) (defmacro hoist ((&rest bool-vars) &body body) (hoist-expander bool-vars body)) > (macroexpand '(hoist (a b) (lambda (arg) (if a (if b arg (foo arg)) (bar arg))))) (IF A (SYMBOL-MACROLET ((A T)) (IF B (SYMBOL-MACROLET ((B T)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG))))) (SYMBOL-MACROLET ((B NIL)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG))))))) (SYMBOL-MACROLET ((A NIL)) (IF B (SYMBOL-MACROLET ((B T)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG))))) (SYMBOL-MACROLET ((B NIL)) (PROGN (LAMBDA (ARG) (IF A (IF B ARG (FOO ARG)) (BAR ARG)))))))) To be able to go into the code and conveniently disable this, we can define a no-hoist macro with the same syntax: (defmacro no-hoist ((&rest bool-vars) &body body) `(progn ,@body))

Jtsummers 5y ago
Except that the value of huge-p isn't known at compile time in the blog's described use-case, it's known at runtime, so constant propagation to remove the extra conditionals may or may not work. It depends on when those lambdas actually get compiled, doesn't it? If they get compiled and close over huge-p one time, then the inner conditional remains and gets executed every time. Thus moving the branch outside the lambdas and returning the correct lambda based on the value of huge-p. For a single boolean this is trivial to do by hand. For n booleans and 2^n combinations, it's less trivial to do by hand, thus the macro. EDIT: Nevermind, with what you added and rereading I get what you're talking about now.
gmfawcett 5y ago
I know you said "quick and dirty", but the unhygienic variable capture on those args is making my parens twitch. :) This was a nice explanation.
- kazinator 5y ago
  They have to be unhygienic because the code makes references to those specific symbols. We need to bind each of those symbols to a nil and t constant against different copies of that code, thereby shadowing the original variable, based on whose value the decision is made which way to bind the shadow. Our macrology does not introduce any hidden variables of its own; we don't have anything to hide behind gensyms. We have not even evaluated any argument material twice.
  - gmfawcett 5y ago
    Of course you're right. I read your code again, and I stand corrected. Well done.
- phoe-krk 5y ago
  You don't need hygiene (WITH-GENSYMS and so on) in Common Lisp macros in two situations: when you do not introduce any new bindings and when you only introduce bindings that the user is allowed to name themself. That's why the following code: (with-open-file (my-super-stream #p"/tmp/foo" ...) ...) Can expand into something like this: (let ((my-super-stream (open #p"/tmp/foo" ...))) ...) Note that the variable name, MY-SUPER-STREAM, is provided by the user, so if there is any variable capture/shadowing present then it is of the user's own making and they can reap the benefits and costs of doing so.

phoe-krk 5y ago

Author here. The repo link and simpler implementations were linked in sibling comments, so I'll just add a bit more explanation. The whole thing relies on the idea that Lisp macros can communicate: the outer macros can, via their expansion, pass information to the inner macros via the compilation environment, and these inner macros can then use that information to decide how they should expand. This information is available at compile-time only, but that's enough for the macros to decide what kind of code to generate - in this particular case, the choice is whether some body of code should be included in the expansion or not. This mechanism is known in the Lisp world as the SYMBOL-MACROLET trick and was described well in the article at [0] - except I think that that article could use a slightly better example, which my repository is happy to provide. [0] https://etc.ruricolist.com/2020/03/15/the-symbol-macrolet-trick/ https://etc.ruricolist.com/2020/03/15/the-symbol-macrolet-tr...

deleted 5y ago
[deleted]