2 ms·

> Basically your argument boils down to No, my argument boils down to that an Abstract Syntax Tree must represent Abstract Syntax. A stream/list/tree of tokens

by lispm 7y ago

> Basically your argument boils down to No, my argument boils down to that an Abstract Syntax Tree must represent Abstract Syntax. A stream/list/tree of tokens isn't a tree of syntax elements. In Lisp (+ a b) and (a b +) are valid token lists and we have no idea what these tokens are other than symbols. In an abstract syntax tree we would represent syntactic categories like operation, variable, constant, function call, etc. and it would be the result of a parse of a particular syntax. The Lisp reader is not a Lisp parser. It doesn't know if (+ a b), ((a) (+) (b)), (a (b) +) or (a b +) are valid Lisp constructs. The Lisp reader is an S-Expression parser. Its input is a s-expression and the syntax of s-expressions. Thus the result of its parse can't be an abstract syntax tree for a Lisp program - it simply can't assign any syntactic information: neither implicit, nor explicit. Definitions (stolen): Abstract Syntax is a model consisting of the language constructs from which a language is composed. Abstract Syntax Tree is a directed acyclic graph (DAG) consisting of instances of Abstract Syntax language constructs.

kazinator 7y ago
Because Lisp uses a flexible representation, the representation has to be validated to see that it conforms to a given syntax (such as that of Lisp source). This can happen naturally in a code-expanding tree walk. The subsequent structure can then be processed without additional validation; every form has the right kinds of pieces in the right positions. If (1 a) or ((a) b) are not valid forms, their presence can be diagnosed at that stage. Subsequent processing stages, can trust that the pieces are where they are supposed to be. The invalid forms like (1 a) and ((a) b) are assumed not to occur, just like any bad inputs to a module that have been checked away. You're arguing for a definition of AST that basically coincides with "decorated AST": AST plus some semantic attributes, and that a generalized tree form that encodes supersets of a syntax cannot be an AST.
- lispm 7y ago
  > This can happen naturally in a code-expanding tree walk just because something can be interpreted as a tree, it's not suddenly an Abstract Syntax Tree. It's mainly nothing more than a hierarchical tokenizer format. A flexibility of the Lisp source representation comes because it is NOT an AST and thus not bound to a particular correctly represented syntax. A macro for example can turn any wild combination of tokens into more wild combination of tokens - regardless of what the symbols/numbers/lists/strings, ... actually might 'mean'.

by lispm 7y ago

kazinator 7y ago

Because Lisp uses a flexible representation, the representation has to be validated to see that it conforms to a given syntax (such as that of Lisp source). This can happen naturally in a code-expanding tree walk. The subsequent structure can then be processed without additional validation; every form has the right kinds of pieces in the right positions. If (1 a) or ((a) b) are not valid forms, their presence can be diagnosed at that stage. Subsequent processing stages, can trust that the pieces are where they are supposed to be. The invalid forms like (1 a) and ((a) b) are assumed not to occur, just like any bad inputs to a module that have been checked away. You're arguing for a definition of AST that basically coincides with "decorated AST": AST plus some semantic attributes, and that a generalized tree form that encodes supersets of a syntax cannot be an AST.

lispm 7y ago
> This can happen naturally in a code-expanding tree walk just because something can be interpreted as a tree, it's not suddenly an Abstract Syntax Tree. It's mainly nothing more than a hierarchical tokenizer format. A flexibility of the Lisp source representation comes because it is NOT an AST and thus not bound to a particular correctly represented syntax. A macro for example can turn any wild combination of tokens into more wild combination of tokens - regardless of what the symbols/numbers/lists/strings, ... actually might 'mean'.