Hacker News new | past | comments | ask | show | jobs | submit login
Rebol vs. Lisp Macros (hostilefork.com)
117 points by vanderZwan on April 28, 2016 | hide | past | favorite | 38 comments



So this was a very interesting post. I would like to note that we can actually do something like definitional scoping in CL too :), but we need to write it ourselves!

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)


I have tried to use SBCL's code walker on a pet project and so far I have no problem with it; in fact it is surprisingly easy to use. By the way, the following post is a good introduction to it: http://christophe.rhodes.io/notes/blog/posts/2014/naive_vs_p...


See FEXPRs in Lisp.

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))))
Calling (print-reverse (+ 1 2)) does print (2 1 +)


@lispm see the reference I made to FEXPRs in reply below (http://axisofeval.blogspot.co.id/2011/07/meaning-of-forms.ht...)

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.


Perhaps I am missing something/unable to interpret the article properly.

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"


I am not familiar with Rebol but from what I gathered from the "So...What Can't Be Done?" section of the article is that `use` is more like a code walker that does lexical binding before the given expression is expanded and evaluated (hence the need for `compose`).

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)))
Where foobar is something like:

    (defmacro foobar (x)
      `(let ((msg "abc"))
         ,x))
And a Common Lisp `use` might be something like:

    (defmacro use (var binding expression)
      (let ((var1 (gensym)))
        `(let ((,var1 ,binding))
           ,(subst var1 var expression))))


You should find this of interest because this is how USE is written in Rebol:

  >> 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] []
  ]]


SBCL has EVAL-IN-FRAME, which, used in conjunction with FIND-CALLER-NAME-AND-FRAME, can be used to access variables by name at runtime. The variables may or may not actually be there depending on the OPTIMIZE settings. SBCL removes unreferenced variables. Here's how to implement LEXICAL-EVAL, which evaluates its argument in the current lexical scope instead of in the toplevel environment:

    (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))
    
Then you can do this:

    (let ((x 2))
        ;; Prevent X from getting optimized out:
        (setf *some-global-var* x)
        (lexical-eval 'x))
In CLISP, there is EVAL-ENV and (THE-ENVIRONMENT), which can be used to accomplish the same thing.


I learned quite a bit reading this. I am just looking at RED, but I program in Lisp/Scheme. FEXPRS come to mind [1]. PicoLisp sort of has them, and I think Newlisp does too, but I don't use Newlisp. I think this addresses some of the Lisp comparisons in a different light.

  [1]  http://axisofeval.blogspot.co.id/2011/07/meaning-of-forms.html


Q. definitional scoping in CL? A1. Use a quasiquote and comma instead of a quote, which embeds the value inline. Not the direct answer though.

  (let ((msg "Hello"))
    (eval `(print ,msg)))
A2. Declare the variable as a SPECIAL variable and give it a dynamic scope (rather than lexical). Lexical environment/scope and dynamic environment/scope (resp.) are independent.

  (let ((msg "Hello"))
    (declare (special msg))
    (eval '(print msg)))
  ;; -> "Hello"
So, when people "points out" any language-level flaw in common lisp most probably s/he simply doesn't read the ANSI spec.


Non-strict (lazy) evaluation should be mentioned as another way to approach the problem.


Which problem?


Give me lazy evaluation & I can define if as a function which takes 2 expressions & evaluates only 1, whereas in an eager language I'd have to pass a hand rolled if function callbacks


For example, Haskell's ifThenElse is just a normal function of three arguments.


"IfThenElse" in Rebol (called either) is also just a function with 3 args:

    either 1 = 1 [print "true!"] [print "false!"]
Here's an example of writing this in Rebol directly:

  if-then-else: function [
      cond [logic!]
      true-block [block!]
      false-block [block!]
    ][
      switch cond [
          #[true]  [do true-block]
          #[false] [do false-block]
      ]
  ]
This works because blocks aren't evaluated until explicitly called:

  >> if-then-else 1 = 1 [print "true!"] [print "false!"]
  true!

  >> if-then-else 1 = 2 [print "true!"] [print "false!"]
  false!


Okay, but the article has almost nothing to do with that, which is a subset of what macros are used for. It is about CL lexical binding, Rebol's definitional scoping and evaluation of data as code at runtime.


> because ordinary Lisp functions are limited in how they can work with "context-dependent code fragments" passed as arguments. Rebol attacks this problem by making bindings of individual symbols "travel along" with their code fragments. The result is that many cases requiring macros in Lisp can be written as ordinary Rebol functions.

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.)


Only got one comment but this article was also posted a week ago - https://news.ycombinator.com/item?id=11541170


Reposts are fine if a story hasn't had attention yet, and it's stories like this that that rule exists for.

https://news.ycombinator.com/newsfaq.html


Ah, must have missed it. Maybe if we let this one up it might attract more discussion a second time? I posted it hoping that some fanatic Lispers had some interesting thoughts to add.


Semi-fanatic lisper here. First of all, search the other comments for a discussion of f-exprs.

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.

1: http://quickdocs.org/cl-cont/api


I am not fanatic and I liked this article because I don't know Rebol very much. Rebols quoted code and "use" remind me a little of "uplevel" in Tcl.

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))
... or use special variables.

Alternatively, (define-symbol-macro msg "Hello") could work too, but that would be ugly.


Yes the article deserves more attention so hopefully it will get much more eyeballs this time round :)


If possible, do things without macros. Problem is - it's pretty much always possible to do things without macros.


Whatever macros can do can be done by code without macros.

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.)


More like: If possible, then don't define a macro. You should use macros as much as possible.


> More like: If possible, then don't define a macro. You should use macros as much as possible.

Are your two sentences intentionally opposite?


No. If possible, do things with macros. And it is always possible to do things with macros.

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.


I have only ever heard the opposing argument, but I am interested in understanding to its fullest extent how to implement good DSLs with macros. I understand CL and defmacro; I am just looking for good patterns of use. Can you point me to any resources, documentation, or examples of this?


When you design a eDSL out of functions you get a lot of expressive power for free because you can lean on the host language's composition facilities. However this also means you have to shoehorn your semantics into an existing set of constraints (this is addressed by the "If possible" qualifier in "If possible, do things without macros") and you have to adopt all the complexity that the host language enables.

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.


so, i'm not a CL wizard, but i've spent some time with it. One cool part about macros, the part that really matters, you get to control the order of evaluation. That doesn't sound super interesting, so let's get a little more concrete.

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;
The key point here is the break. we actually want to stop evaluation of the later parts of the code.

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)))
the gist being, we leverage the built in and to do something like:

    (and
        (eval google-at-700)
        (eval oil-at-50))
so you embed right in the language itself, taking advantage of the built in short circuiting of and.

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
no matter what happens in do-stuff, release is always called.

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


All the arguments against the CL-style macros are stemming from the fact that it's far too easy to get into a total mess with them, simply because of their infinite flexibility. Yet, if you follow some very simple rules, you'll get the opposite.

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

https://github.com/eholk/harlan

[2] https://github.com/combinatorylogic/mbase


What you're talking about can still be done without macros, in fact AFAIK REBOL is known for exactly that.

> Because using macros is one way to implement simple, nice, clean, maintainable eDSLs.

FTFY


It can be done without macros, but any such solution (fexprs included) would be much worse than a macro-based one. Much more complicated, much less efficient, etc.


Meh, not necessarily. Lazy by default gives you a lot of good stuff. We shouldn't assume that macros can't be done better anyway.


It is very hard to reason about the laziness, unfortunately, so it is more of a beautiful hack most often rather than a sustainable design methodology. While with macros you've got a very simple, reproducible, verifiable design methodology for constructing arbitrarily complex DSLs.


What's the problem with anaphoric macros?


when-let and if-let are better at communicating intent through names.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: