5 ms·

> Lisp code is written in a simpler notation than ASTs, it's written as nested lists of objects. That is exactly what a simple AST is: A tree structure represe

> Lisp code is written in a simpler notation than ASTs, it's written as nested lists of objects. That is exactly what a simple AST is: A tree structure representing the semantics of the code you wrote with no syntax info. > Hierarchical data-structure: the s-expressions are based on nested lists of arbitrary data. Like symbols, numbers, strings and many others. This is exactly what AST’s do as well. Whether it contains the semantics of Lisp code or (say) C code. > S-expressions are no abstract syntax trees, since they capture no syntax information about the meaning of the symbols. This is a misunderstanding. AST’s capture semantics not syntax. You can pretty print AST’s into a different semantically equivalent syntax if you want. That is what some compilers do: Lisp syntax -> AST -> C syntax. > That gives an extra degree of freedom: the input to the Lisp evaluator is not an AST (either read or generated by a parser), it's just nested lists of symbols and other objects. This is not correct. The input to Lisp macros are runtime data structures. Not syntax. Different Lisp interpreters/compiles use different runtime representations. Typically linked lists. The nodes in the linked list typically have a lot of additional information like type information, column/line data for error reporting etc. > That means for example that Lisp macros accept code in an arbitrary syntax. Nope. As I said above, macros accept runtime data. You need to clearly separate syntax from semantics/runtime in your head to understand what is really going on. > For example this is valid Lisp code when LOOP is a macro and implements its own syntax. Macros are runtime code executed during the parser stage. It has nothing to do with syntax. Other languages execute macros the same way. That’s why I said above that macros aren’t unique to Lisp. > The s-expression does not encode basic information like what the meaning of the identifier is. That is correct. You can define different semantics to the same S-expression. However for the S-expression to be interpreted as Lisp you need to use the Lisp semantics to run it. I use S-expressions all the time for configuration files etc. However I use a different semantics. So the S-expression might look like Lisp but it isn’t Lisp in those cases. > An AST would encode what the construct is: operator, variable, class, ... Lisp s-expressions don't do that. Nope that is not true. A typical AST for Lisp would have the following semantics categories: List, Symbol, Integer, Float, String. That’s it. There aren’t many. That’s what makes Lisp so easy to implement. In other languages you might have 20+. That’s exactly what I mean when I say that the Lisp syntax directly represents the AST. And no other language does. That is the one feature that makes Lisp unique.

lispm 4y ago
> That is exactly what a simple AST is: A tree structure representing the semantics of the code you wrote with no syntax info. That what I say: the s-expression does not represent the semantics. It does not know much about Lisp: no syntax and no semantics. It mainly uses similar data structures for the code: lists, symbols, numbers, etc. See this for an AST: https://upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Abstract_syntax_tree_for_Euclidean_algorithm.svg/800px-Abstract_syntax_tree_for_Euclidean_algorithm.svg.png https://upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Ab... In Lisp the s-expression does not say that 'a' is a variable name. We don't know that '>' is a compare op. (+ 1 a) would be written as an AST maybe like: (function-call :operator (built-in-variadic-function cl:+) :arguments ((numeric-constant 1) (variable a))) > As I said above, macros accept runtime data. No, macros are also expanded before runtime. > Macros are runtime code executed during the parser stage. The s-expression is unparsed. The macro has to do the parsing. > Other languages execute macros the same way. No, in most languages macros get an AST, where syntax is represented and pre-parsed. For example the macro gets pre-parsed code, where the syntactic categories are determined. + is an operator. In Lisp + is just a symbol and that is no specific syntactic category. Thus most macro systems in languages, the code is pre-parsed and the result is given to the macro expansion. That means a use of the identifier + is an infix function. Not so in Lisp. + is just a symbol and we don't know yet what it is: data, operator, variable, lexical variable, etc. > You can define different semantics to the same S-expression. And also syntax. (+ + +) -> is that postfix, prefix or infix? Lisp does have prefix syntax, but the macro can assume anything. > However for the S-expression to be interpreted as Lisp you need to use the Lisp semantics to run it. And the syntax. > A typical AST for Lisp would have the following semantics categories: List, Symbol, Integer, Float, String. That does not describe Lisp, that describes S-expressions. S-expressions are not Lisp, they are just a syntax for data. The Lisp program has simply a different notation in the form of s-expressions, but no syntactically or semantically representation. An AST would be already representing syntactical information like the syntactical categories of the identifiers present. 1 + 1 is just another notation, like (+ 1 1) is another one. It's not yet the a new quality. The main difference is that in the case of Lisp, s-expressions are backed by a simple data structure, nested lists, which provides some hierarchy, but no representation of syntax. I would think of it as a token tree output of some kind of lexer. If I have (let ((a (+ b 10))) (* a b)), then in Lisp LET is a special operator, A is a lexical variable, b is a variable, 10 is an integer constant, * is a built-in function, etc. The syntax for above LET is: let ({var | (var [init-form])}*) declaration* form* > That’s exactly what I mean when I say that the Lisp syntax directly represents the AST. And no other language does. That is the one feature that makes Lisp unique. Yeah, but that's wrong. The Lisp syntax is on top of s-expressions. You seem to believe that s-expressions represent Lisp syntax. They can't s-expressions is a format to represent data, not a specific programming language. Thus they have no idea of syntactic categories or anything like the information which would be in an Abstract Syntax Tree.

lispm 4y ago

> That is exactly what a simple AST is: A tree structure representing the semantics of the code you wrote with no syntax info. That what I say: the s-expression does not represent the semantics. It does not know much about Lisp: no syntax and no semantics. It mainly uses similar data structures for the code: lists, symbols, numbers, etc. See this for an AST: https://upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Abstract_syntax_tree_for_Euclidean_algorithm.svg/800px-Abstract_syntax_tree_for_Euclidean_algorithm.svg.png https://upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Ab... In Lisp the s-expression does not say that 'a' is a variable name. We don't know that '>' is a compare op. (+ 1 a) would be written as an AST maybe like: (function-call :operator (built-in-variadic-function cl:+) :arguments ((numeric-constant 1) (variable a))) > As I said above, macros accept runtime data. No, macros are also expanded before runtime. > Macros are runtime code executed during the parser stage. The s-expression is unparsed. The macro has to do the parsing. > Other languages execute macros the same way. No, in most languages macros get an AST, where syntax is represented and pre-parsed. For example the macro gets pre-parsed code, where the syntactic categories are determined. + is an operator. In Lisp + is just a symbol and that is no specific syntactic category. Thus most macro systems in languages, the code is pre-parsed and the result is given to the macro expansion. That means a use of the identifier + is an infix function. Not so in Lisp. + is just a symbol and we don't know yet what it is: data, operator, variable, lexical variable, etc. > You can define different semantics to the same S-expression. And also syntax. (+ + +) -> is that postfix, prefix or infix? Lisp does have prefix syntax, but the macro can assume anything. > However for the S-expression to be interpreted as Lisp you need to use the Lisp semantics to run it. And the syntax. > A typical AST for Lisp would have the following semantics categories: List, Symbol, Integer, Float, String. That does not describe Lisp, that describes S-expressions. S-expressions are not Lisp, they are just a syntax for data. The Lisp program has simply a different notation in the form of s-expressions, but no syntactically or semantically representation. An AST would be already representing syntactical information like the syntactical categories of the identifiers present. 1 + 1 is just another notation, like (+ 1 1) is another one. It's not yet the a new quality. The main difference is that in the case of Lisp, s-expressions are backed by a simple data structure, nested lists, which provides some hierarchy, but no representation of syntax. I would think of it as a token tree output of some kind of lexer. If I have (let ((a (+ b 10))) (* a b)), then in Lisp LET is a special operator, A is a lexical variable, b is a variable, 10 is an integer constant, * is a built-in function, etc. The syntax for above LET is: let ({var | (var [init-form])}*) declaration* form* > That’s exactly what I mean when I say that the Lisp syntax directly represents the AST. And no other language does. That is the one feature that makes Lisp unique. Yeah, but that's wrong. The Lisp syntax is on top of s-expressions. You seem to believe that s-expressions represent Lisp syntax. They can't s-expressions is a format to represent data, not a specific programming language. Thus they have no idea of syntactic categories or anything like the information which would be in an Abstract Syntax Tree.