3 ms·

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 w

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
Lisp nested expressions are AST. A CLOS-sified representation of the program with additional semantic info is more of an IR: intermediate representation.
- lispm 8y ago
  > Lisp nested expressions are AST. No, they are nested lists of tokens.
  - kazinator 8y ago
    Note that you also aren't using "token" in the usual way it appears in computer science. ANSI Lisp's Glossary gets it right: > token n. a textual representation for a number or a symbol. See Section 2.3 (Interpretation of Tokens). "1234" and "A1234" are tokens: chunks of accumulated token-constituent characters inside the reader. These are turned into values, which are no longer tokens. We never have a "tree of tokens"; for that to be true you have to abuse the word "token" to denote "Lisp value". The Lisp AST consists of nodes which are typed values. (Some of those values are aggregates that are not lists: let's not forget vectors and structure literals.) When non-Lisp-programmers write parsers for non-Lisp-languages, they crank out AST's which imitate the concept. A typical approach is for the parser rules to produce nodes based on a discriminated union of types: in its essence, an implementation of dynamically typed objects. What can we look at for a real example? How about GNU Awk. This has a Yacc grammar: http://git.savannah.gnu.org/cgit/gawk.git/tree/awkgram.y http://git.savannah.gnu.org/cgit/gawk.git/tree/awkgram.y in which the YYSTYPE is of type "INSTRUCTION *", a pointer to the structure defined here: http://git.savannah.gnu.org/cgit/gawk.git/tree/awk.h?id=e24c77ba17714d5c5253ad5f284e709abd66e1a2#n745 http://git.savannah.gnu.org/cgit/gawk.git/tree/awk.h?id=e24c... Okay, so that would be our GNU AWK AST node. What is it? Why, just a grotesque Greenspunning of some dynamic typing. The two unions in there are like car and cdr. The semantics actions of the Yacc parser do a whole lot of list_create and list_append involving this INSTRUCTION type, often behind various wrapper functions like mk_assignment or mk_expression_list and whatnot, The main difference is that the Lisp way of representing AST's is just cleaner and smarter, like the Lisp way of doing pretty much anything.

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

Lisp nested expressions are AST. A CLOS-sified representation of the program with additional semantic info is more of an IR: intermediate representation.

lispm 8y ago
> Lisp nested expressions are AST. No, they are nested lists of tokens.
- kazinator 8y ago
  Note that you also aren't using "token" in the usual way it appears in computer science. ANSI Lisp's Glossary gets it right: > token n. a textual representation for a number or a symbol. See Section 2.3 (Interpretation of Tokens). "1234" and "A1234" are tokens: chunks of accumulated token-constituent characters inside the reader. These are turned into values, which are no longer tokens. We never have a "tree of tokens"; for that to be true you have to abuse the word "token" to denote "Lisp value". The Lisp AST consists of nodes which are typed values. (Some of those values are aggregates that are not lists: let's not forget vectors and structure literals.) When non-Lisp-programmers write parsers for non-Lisp-languages, they crank out AST's which imitate the concept. A typical approach is for the parser rules to produce nodes based on a discriminated union of types: in its essence, an implementation of dynamically typed objects. What can we look at for a real example? How about GNU Awk. This has a Yacc grammar: http://git.savannah.gnu.org/cgit/gawk.git/tree/awkgram.y http://git.savannah.gnu.org/cgit/gawk.git/tree/awkgram.y in which the YYSTYPE is of type "INSTRUCTION *", a pointer to the structure defined here: http://git.savannah.gnu.org/cgit/gawk.git/tree/awk.h?id=e24c77ba17714d5c5253ad5f284e709abd66e1a2#n745 http://git.savannah.gnu.org/cgit/gawk.git/tree/awk.h?id=e24c... Okay, so that would be our GNU AWK AST node. What is it? Why, just a grotesque Greenspunning of some dynamic typing. The two unions in there are like car and cdr. The semantics actions of the Yacc parser do a whole lot of list_create and list_append involving this INSTRUCTION type, often behind various wrapper functions like mk_assignment or mk_expression_list and whatnot, The main difference is that the Lisp way of representing AST's is just cleaner and smarter, like the Lisp way of doing pretty much anything.