Rebol vs. Lisp Macros
blog.hostilefork.com
blog.hostilefork.com
We would do this using CLOS and its MOP, more precisely by using the FUNCALLABLE metaclass and having a class with an environment slot, source slot and effective function slot which both would be altered by some convention (USE, COMPOSE and FUNCTION it seems?).
Then you'd SET-FUNCALLABLE-INSTANCE-FUNCTION to a lambda that invalidates the efficient function when source or environment has changed and composes a new function with (compile `(let((,@environment(( ,@source)).
Voila, you now have a type of function that carries with it an environment and its source code.
Now I don't know if this fully satisfies what REDBOL is doing to be honest, because the post talks about "deep walking" and that sounds like code walking, which is a scary place to go to in CL.
EDIT: Yeah, it seems like USE would do a full code walk(?) Code walking really sucks, because you need to recognise the special forms of CL and deal with them appropriately. This doesn't apply if the list of vars used is always passed to USE (just let LET take over binding the lexical environment)
https://en.wikipedia.org/wiki/Fexpr
and
http://www.nhplace.com/kent/Papers/Special-Forms.html
Passing unevaluated code into Lisp functions was widely used in Lisp. Long ago.
It is no longer, since macros are typically simpler to understand and easier to integrate into a compilation model.
In Symbolics Genera, which has weak support for FEXPRs:
(defun print-reverse zl:fexpr (form)
(print (reverse (first form))))
You seem to be a lot more knowledgeable than I on Lisp. It seems there's a divide on FEXPRs and macros when I look into further references. What's your take on it aside from the Pitman paper you cited? Is is possible something useful was thrown away from CL, or Pitman's argument holds? PicoLisp seems to implement FEXPRs a bit from my limited knowledge. I am currently in a death spiral of LFE, Chez Scheme, PicoLisp, Extempore (xtlang), and Shen, not to mention my necessary forays into elisp, since I use spacemacs! I need to choose one, only one. Thanks.
I remember there was a day when it clicked in my head that the way the lexical scope/compiler in common lisp works means that the variable names don't stick around at run-time, but are compiled away. So of course, using the lexical scope of (let) forms in lisp means that yes, it is quite impossible to have a naive variable symbol passed into a let form and looked up at run time as though it were still around.
But does that mean its not possible? I mean...doesn't Common Lisp at least have both lexical and dynamic scope? What if there was some kind of primitive function or form available that told lisp that you actually want to keep the names around and use that name to do run time environment/variable lookup instead. Then you could pass in such a quoted form and evaluate it and it would work.
Hang on a second...
Lets see if we can re-write that form from the article that "doesn't work" in lisp...in an easy and convenient fashion.
Here's his function definition:
(defun greater10 (value code) (if (> value 10) (eval code)))
And now lets set up a dynamic binding/evaluation using the less common progv form:
(progv '(msg) '("Hello") (greater10 20 '(print msg)))
And the result:
"Hello"
If I understand things correctly this is a lot like the `defmacro!` and sub-lexical scoping that Doug Hoyte writes about in _Let Over Lambda_. There the intention of code walking and rewriting is to prevent unwanted variable capture (walking over the code and replacing certain names with unique ones that have their own unique locations is basically implementing lexical scoping).
So where `progv` might run into trouble is:
(progv '(msg) '("Hello") (greater10 20 '(foobar msg)))
(defmacro foobar (x)
`(let ((msg "abc"))
,x))
(defmacro use (var binding expression)
(let ((var1 (gensym)))
`(let ((,var1 ,binding))
,(subst var1 var expression)))) >> source use
use: make function! [[
"Defines words local to a block."
vars [block! word!] "Local word(s) to the block"
body [block!] "Block to evaluate"
][
apply make closure! reduce [to block! vars copy/deep body] []
]] (defpackage :lexical-eval
(:use :common-lisp :sb-kernel :sb-di))
(in-package :lexical-eval)
(defmacro second-value (form)
`(multiple-value-bind (a b)
,form
(declare (ignore a))
b))
(defun lexical-eval (form)
(eval-in-frame (second-value (find-caller-name-and-frame))
form))
(let ((x 2))
;; Prevent X from getting optimized out:
(setf *some-global-var* x)
(lexical-eval 'x))
[1] http://axisofeval.blogspot.co.id/2011/07/meaning-of-forms.html (let ((msg "Hello"))
(eval `(print ,msg)))
(let ((msg "Hello"))
(declare (special msg))
(eval '(print msg)))
;; -> "Hello"
either 1 = 1 [print "true!"] [print "false!"]
if-then-else: function [
cond [logic!]
true-block [block!]
false-block [block!]
][
switch cond [
#[true] [do true-block]
#[false] [do false-block]
]
]
>> if-then-else 1 = 1 [print "true!"] [print "false!"]
true!
>> if-then-else 1 = 2 [print "true!"] [print "false!"]
false!Bzzt, no. "Context dependent code fragments" are "lambdas" in mainstream Lisp dialects, which carry the environment (i.e. bindings of symbols) via lexical closure.
Now, indeed, one of the uses of macros is to provide some (usually mild) sprinkling of syntactic sugar to conceal lambda syntax.
> But packing code into a [functional/lambda] "black box" creates barriers to transformations that are a big part of the appeal of using a homoiconic language.
The history of Lisp has recorded considerable experience with the FEXPR approach to language extension. Lispers had worked out decades ago that this largely sucks, and so interest in FEXPRs waned. They do not appear as a feature in Scheme or Common Lisp, and it's not for lack of knowledge or experience.
Essentially, Lisp performed a "Rebol-ectomy" on its semantics by the end of the 1960's or thereabouts.
Anyway, to understand macros fully, you have to step out of the role of language user and put on a "compleat hacker" hat. Suppose you have complete control at your disposal: you can hack any aspect of the language, as deeply in the implementation as you want. You can add new features that cannot be made out of anything which is already there. In spite of that control, you still want macros. Because macros let you separate the concern of designing the low-level abstractions that are the most convenient for a given feature, and a user interface to them which is nice for the user. (Without macros, you face the annoyance of having to extend the repertoire of special operators, even in situations when it is obvious that these new ones should just expand to some other syntax in terms of functions, plus the old ones).
If I'm extending a language deeply at the implementation level, I'm doing something that can't be done with macros or functions anything else; yet macros help in a specific way that other things don't. I still want them in spite of having total control. If I add non-strict evaluation into the language core, I want macros. If I add continuations, I want macros. If I add functional reactive programming, I still want macros, etc. Macros mean I don't have to go into the compiler, or code walker or elsewhere and add new cases to handle special operators. I don't have to go into the grammar of some parser generator to add the syntax, where the parser action is just "construct a node for this new syntax, exactly like some equivalent longer expression would generate".
(If you say you already have all the syntax you would ever need and everything else is just done with that syntax, then you are not wearing the "compleat hacker" hat.)
I was not familiar with Rebol before this article, but this author shows a very good understanding of metaprogramming and homoiconicity, if they picked up this much about lisp macros without having used lisp previously.
Something that throws a lot of people new to common lisp is that macros are so powerful that they seem like magic, when they are probably the simplest metaprogramming tool around. In fact a big part of why I find CL to be such a high local maxima is the very high power/complexity ratio.
Complicated metaprogramming techniques tend to have either high compile-time overhead, high run-time overhead, or both. Sometimes efficient implementations can be discovered with the application of a large number of PhDs.
Lastly, I want to point out that bolting on a full-code walker to Common Lisp is not possible to do in a fully portable way (and by "fully portable" I mean "will run on any future conformant CL implementation"). This is due to the fact that conforming implementations are allowed to expand macros (and even special forms) from the standard into code that contains non-standard symbols.
Obviously you can do code walkers that are portable across N existing implementations with O(N) amount of programming effort; see cl-cont[1] for an example of this.
On the other hand, it would be very doable (if not quite trivial) to implement something in CLOS that works like a code-carrying closure that allows recompilation with declarative scope.
I do sometimes miss the fact that EVAL doesn't take an environment. The upside is that judging by questions I've seen in #lisp, if it did have such a construct, there would be a lot of fairly spaghetti-like EVAL code when a two-line macro would do the trick, as EVAL is the more obvious tool for code-as-data when macros are simpler and easier to understand.
I don't see a use case where I would like eval to capture the lexical environment. If I need to provide bindings, just define them explicitely:
(eval `(let ((msg "Hello")) ,code))
Alternatively, (define-symbol-macro msg "Hello") could work too, but that would be ugly.
We do not have to invoke Turing equivalence.
The simpler proof is that all combinations of macros expand to code which no longer contains any macros. That code by definition does whatever the code-with-macros specifies.
(The exception might be some weird code that keeps expanding while it executes, and never finishes expanding. Then we appeal to Turing equivalence.)
Are your two sentences intentionally opposite?
Why? Because macros are the best way to implement simple, nice, clean, maintainable eDSLs. And any problem is best solved with its most natural language, where the very problem description is already a working solution.
Unfortunately, most people do not understand what macros are, and how they should be used to build multi-stage, simple DSL compilers. They're using macros to implement obscure syntax instead, all that awful LOOP macros, anaphoric ifs, etc., which was exactly what resulted in the bad reputation of the compile-time metaprogramming.
One big advantage of a DSL is that it limits complexity so that it's easier to predict what code will do, even if you haven't read it yet. With a macro-based DSL, you can know exactly what functionalty expressed in the DSL can and cannot do, which makes it easier to reason about without studying the code for hours.
Say you want to model option contracts. They can get crazy complicated. most DSLs will have things that are AND like and things that are OR like. In C you're stuck with something like this for the and case:
all = 1;
for(int i = 0; i < clause_count; i++){
if(eval(clause[i]) == 0){
all = 0;
break;
}
}
return all;
with a macro, you just expand out all of the eval'ing of the clauses in place. you can't just map over the list of clauses, because we want the early exit.
my lisp is rusty, but i think it'd look kinda like
(defmacro optionand (&rest clauses)
`(and ,@(map (lambda (c) (list 'eval c) clauses)))
(and
(eval google-at-700)
(eval oil-at-50))
in haskell, you can play a very cute game. since functions are lazy, you get full control over evaluation - you don't need a special form to implement if, for example.
So, the very cute trick is to make your dsl out of ordinary functions, that use typeclasses for implementation. in the above case eval would be a method in a typeclass. (you can do the very same thing in lisp, it just seems like a bit more effort to carry around the specific implementation of eval, haskell will just figure it out with the typechecker).
The thing that's great about the trick, you can write multiple implementations of eval, and not rewrite all your contracts. One implementation could just straight up evaluate it. Another version could do some fuzzier math with variance of the underlying price, and return a gaussian rather than a number.
Again, the key is controling the actual evaluation i think there's some bits and pieces about it in _on lisp_ which i think pg made available online. haskell's bracket function is a great example and would be a nice macro candidate
(bracket obtain-resource do-stuff release-resource)
(bracket get-socket talk close-socket) ; for example
it's possible (even easy?) to do scary stuff with controlling the order of evaluation, but when you see code with those complicated breaks and continues, it's often a side effect of not having good macros.
edit
i learned the haskell trick from Oleg Kiselyov's papers - http://okmij.org/ftp/tagless-final/ He uses it to make an interpreter into a compiler, and very clever stuff with partial evaluation. That guy is really smart.
Although pg doesn't call out DSL's specifically, the macro chapter is good. http://unintelligible.org/onlisp/onlisp.html#SEC49 and indeed you can get the whole book here http://www.paulgraham.com/onlisp.html
Firstly, macros must be simple and must essentially correspond to compiler passes.
E.g., if you're implementing an embedded DSL for regular expressions, one macro expansion pass should lower your DSL down to a syntax-expanded regular expression, the second macro would lower it into an NFA, another one would construct an optimised DFA, and then the next one (or more) would generate the actual automaton code in Lisp out of the DFA.
The best possible case is when your macro pass can be expressed as a set of simple term rewriting rules. And most of the transforms you'd find in DSL compilers can actually be represented as such.
Of course, there is also an alternative style, which may be preferable if you have debugging tools for designing your compiler passes at least equivalent to the Lisp macro expansion debugging. You can simply write your entire DSL compiler as a single function, and then wrap it into a macro, as `(defmacro mydsl (&rest args) (mydsl-compiler args))`.
This way, the same compiler infrastructure can be reused for an interpreted or partially interpreted version of your DSL, if you need it. Still, all the same rules apply to how the passes are implemented in that compiler function.
Another very useful trick is to make your DSLs composable, which is easy if you split your compilation pipeline into separate macro expansion passes. Multiple DSLs may easily share features of their internal IRs or even front-end languages, so any new DSL would simply cherry-pick features from a number of existing DSLs and wrap them into a simple front-end. This degree of composability is simply impossible with the function-based interpreted eDSLs.
A can recommend taking a look at the Nanopass [1] framework, which is built around this very ideology, or at my own DSL construction framework [2].
[1] http://andykeep.com/pubs/np-preprint.pdf
And some examples:
https://github.com/cisco/ChezScheme
> Because using macros is one way to implement simple, nice, clean, maintainable eDSLs.
FTFY