8 ms·

This, together with taeric's question about tokenization made me realize that we can think of it this way: Macros are not receiving AST nodes [1]. They are not

This, together with taeric's question about tokenization made me realize that we can think of it this way: Macros are not receiving AST nodes [1]. They are not receiving tokens either, though. But something in-between: how many tokens it receives is strictly delimited (by the end paren which ends the macro form, but the macro doesn't see an end paren token, just doesn't get more items in the list, thus can't violate the scoping). Lisp forces open and end parens to be understood as hierarchical grouping indicators for (any kind of) syntax. This simple change over a stream of tokens seems to happen to simplify language creation via macros a lot. [1] quite definitely not before macro-expanding their arguments. After macro-expansion, by grouping the resulting s-expr with a context and a correct tree-walker, I guess it could be said to be one.

kazinator 8y ago
Macros are expanded by a correct tree walker: the macro expander. It recognizes all special forms, and maintains an environment representing information about the lexical scope (at least in any Lisp dialect worth a damn, with lexical macros that can shadow lexical functions and variables and vice versa). Macros can also receive that environment as an argument, which provides the possibility that there can be an API by which macros can query the lexical environment. Furthermore, if macros are given an API for fully expanding an expression, with detailed information about what free references occur in that form, that creates a lot of possibilities for macros to do all sorts of clever things correctly, far beyond just "sticking pieces into a code template with a sprinkling of gensyms".
- pflanze 8y ago
  I was talking about macro-expanding the form first so that the result to be walked consists of only "core" lisp forms. Do you mean that there are macro-expander APIs in CL that offer all ingredients to do the derivation as part of the macro-expansion step? (I'd welcome some pointer to study.)
  - kazinator 8y ago
    The macro expander is a code walker. Whenever it encounters a macro, it expands it (repeatedly, if necessary). Then when all that is left is a special form or function call, or when such a thing is encountered in the first place, it walks that form in the manner appropriate to that form. So by the time macros are expanded, a code walk has taken place over all the special forms and function calls that have emerged. CL doesn't standardize any API for doing anything with the &environment parameter, other than using it as an argument in macroexpand and macroexpand-1, which is a pity. There is information in there such as "is this symbol a lexical variable in this macro's scope". Steele's Cltl2 describes such features, but these didn't make it into ANSI CL. It describes accessors variable-information, function-information and declaration-information. Also an augment-environment function and some other things like enclose.
lispm 8y ago
> After macro-expansion macros just return s-expressions - no AST data
- pflanze 8y ago
  I know. Sorry for my messy terminology. (Not sure whether the points I'm making here are useful or just wasting your time, I'll try to explain just to clarify what I meant.) I didn't mean calling the individual functions implementing macros (apparently called "macro functions"), but something like macroexpand-all (I didn't realize that this is apparently not portable). What I am thinking of is something like: (defmacro foo (expr var &environment env) (let ((expr* (macroexpand-all expr env)) (var* (macroexpand-all var env))) (derive-by expr* var*))) where derive-by is a code walker that understands core CL, and does derivation as part of the walk (perhaps implemented with the help of one of the code walker libraries). expr* (same for var* ) is not an AST in the sense of e.g. a tree of CLOS objects where each one determines a syntactical construct even when standing by itself; only together with env and a walker that understands the "core" CL syntax correctly, it could, "I guess", be considered an AST--sure, maybe let's avoid confusion and call it proto-AST instead. (let* ((protoAST (cons expr* env)) ;; could do: (AST (protoAST->AST protoAST))) ..) where protoAST->AST is a code walker that converts expr* to a tree of objects from a CLOS hierarchy representing each kind of node unambiguously without the need for env. protoAST and AST hold the same information content, which is why I said "could be said to be the same".
  - lispm 8y ago
    > protoAST and AST hold the same information content Not really. protoAST lacks the knowledge the specific code walker adds. For example there is no way to find out whether FOO is a variable or a function without actually 'parsing' the code. If one uses a different syntax in the code walker, then the conversion generates a different parse.
    - pflanze 8y ago
      > protoAST lacks the knowledge the specific code walker adds Yes, that's why I actually had said "by grouping the resulting s-expr with a context and a correct tree-walker". True, you could make that (let* ((protoAST (list expr* env core-CL-walker)) ..) ...) to be explicit. core-CL-walker changes only when the definition of the "core-CL" [1] changes, though, so it's probably a constant for practical purposes. [1] I don't know whether there is any standardization of such a thing. Probably not since macroexpand-all also isn't standard.

kazinator 8y ago

Macros are expanded by a correct tree walker: the macro expander. It recognizes all special forms, and maintains an environment representing information about the lexical scope (at least in any Lisp dialect worth a damn, with lexical macros that can shadow lexical functions and variables and vice versa). Macros can also receive that environment as an argument, which provides the possibility that there can be an API by which macros can query the lexical environment. Furthermore, if macros are given an API for fully expanding an expression, with detailed information about what free references occur in that form, that creates a lot of possibilities for macros to do all sorts of clever things correctly, far beyond just "sticking pieces into a code template with a sprinkling of gensyms".

pflanze 8y ago
I was talking about macro-expanding the form first so that the result to be walked consists of only "core" lisp forms. Do you mean that there are macro-expander APIs in CL that offer all ingredients to do the derivation as part of the macro-expansion step? (I'd welcome some pointer to study.)
- kazinator 8y ago
  The macro expander is a code walker. Whenever it encounters a macro, it expands it (repeatedly, if necessary). Then when all that is left is a special form or function call, or when such a thing is encountered in the first place, it walks that form in the manner appropriate to that form. So by the time macros are expanded, a code walk has taken place over all the special forms and function calls that have emerged. CL doesn't standardize any API for doing anything with the &environment parameter, other than using it as an argument in macroexpand and macroexpand-1, which is a pity. There is information in there such as "is this symbol a lexical variable in this macro's scope". Steele's Cltl2 describes such features, but these didn't make it into ANSI CL. It describes accessors variable-information, function-information and declaration-information. Also an augment-environment function and some other things like enclose.

lispm 8y ago

> After macro-expansion macros just return s-expressions - no AST data

pflanze 8y ago
I know. Sorry for my messy terminology. (Not sure whether the points I'm making here are useful or just wasting your time, I'll try to explain just to clarify what I meant.) I didn't mean calling the individual functions implementing macros (apparently called "macro functions"), but something like macroexpand-all (I didn't realize that this is apparently not portable). What I am thinking of is something like: (defmacro foo (expr var &environment env) (let ((expr* (macroexpand-all expr env)) (var* (macroexpand-all var env))) (derive-by expr* var*))) where derive-by is a code walker that understands core CL, and does derivation as part of the walk (perhaps implemented with the help of one of the code walker libraries). expr* (same for var* ) is not an AST in the sense of e.g. a tree of CLOS objects where each one determines a syntactical construct even when standing by itself; only together with env and a walker that understands the "core" CL syntax correctly, it could, "I guess", be considered an AST--sure, maybe let's avoid confusion and call it proto-AST instead. (let* ((protoAST (cons expr* env)) ;; could do: (AST (protoAST->AST protoAST))) ..) where protoAST->AST is a code walker that converts expr* to a tree of objects from a CLOS hierarchy representing each kind of node unambiguously without the need for env. protoAST and AST hold the same information content, which is why I said "could be said to be the same".
- lispm 8y ago
  > protoAST and AST hold the same information content Not really. protoAST lacks the knowledge the specific code walker adds. For example there is no way to find out whether FOO is a variable or a function without actually 'parsing' the code. If one uses a different syntax in the code walker, then the conversion generates a different parse.
  - pflanze 8y ago
    > protoAST lacks the knowledge the specific code walker adds Yes, that's why I actually had said "by grouping the resulting s-expr with a context and a correct tree-walker". True, you could make that (let* ((protoAST (list expr* env core-CL-walker)) ..) ...) to be explicit. core-CL-walker changes only when the definition of the "core-CL" [1] changes, though, so it's probably a constant for practical purposes. [1] I don't know whether there is any standardization of such a thing. Probably not since macroexpand-all also isn't standard.