3 ms·
> False; the syntax before expanding macros is an AST, so is the one after. It's an AST-AST transformation. I mean, yes, in the same vacuous sense that the fla
by derefr 9y ago
> False; the syntax before expanding macros is an AST, so is the one after. It's an AST-AST transformation.
I mean, yes, in the same vacuous sense that the flat stream of tokens output by a lexer technically qualifies as an AST. If you like, your lexer could output a "tree" of 1+N nodes: a Parse node, and within it, a list of N arguments (the lexer-tokens.) You would then apply an AST-AST transformation that responds to the "parse" node by parsing its contents.
When we talk about an AST in the context of programming, we usually mean to refer not to any airy CS concept, but specifically to the output of an LR(k) parser—that is, a bottom-up, context-free parser. To parse the lexer-token stream in an LR(k) parser, you need to be able to output ("produce") a structure given a sequence of tokens, without having any context of the greater rule you're executing "within" (i.e. above on the call-stack) other than the fact of what the current rule is.
Homoiconicity is exactly the property of a programming-language grammar that allows code containing macros to pass cleanly through this initial "lexical parsing" step. Usually, this requires a separation of the grammar from the syntax of the language, such that the "lexical parsing" grammar will no longer directly produce any of the "special forms" of the language itself, but these will rather be later handled by a similar (or the same!) process as macro-expansion—consuming AST subtrees to produce other, more specialized AST subtrees.
Or, to put that another way: macros require top-down parsing. If you want to avoid using a full-on top-down parser, you can instead apply a traditional bottom-up context-free parser followed by applying a folding transformation to the generated tree to do "the rest" of the parsing. But, to achieve this parsing strategy, the property you have to imbue your language grammar with is called "homoiconicity."
- benlorenzetti 9y agoI'm a little rusty remembering my compilers course, but do you mean separating syntax from inflection? So that you can parse just based on a "syntax grammar" and then you can trivially assume the inflection based on where things fell in the AST? Can you explain more why this makes macros AST -> AST transformation only vacuously true? I didn't follow the argument. Also why macros require top down parsing? Perhaps more interesting, would the property you described still be called homoiconic if the the parser were context sensitive?
- kazinator 9y agoLisp macros (that the article is talking about) work with the same input and output language, not with two different languages/representations as is written. Macros can expand to other macros and even to themselves. It's an iterative process in which the intermediate pieces of tree have fewer and fewer macros until none are left. Other than not using macros, the target code is in the same language. (In C, the preprocessing phase also works with the same input and output language. It's not a tree data structure, but rather a sequence of preprocessor tokens. Tokens in, tokens out. Parsing is then done in the next phases of translation. Macros have to do some light parsing in order to delimit the argument lists, of course, and to identify the operators like the token pasting ##, stringification # and whatever, plus to handle the preprocessing directives and #if expressions with arithmetic.)