5 ms·
That all makes sense, and I tried to talk towards this when I referred to putting the rest of the syntax required to define a function. That is, I have fallen
by taeric 8y ago
That all makes sense, and I tried to talk towards this when I referred to putting the rest of the syntax required to define a function.
That is, I have fallen to the trap of claiming lisp has little syntax before. The idea being that I can walk the tree, so I'm walking an AST. But i realize now that is abusing the S in AST. There is plenty of syntax there that can be checked.
I would like to not steer others down that trap. Thanks for expanding in it here!
- kazinator 8y agoLisp languages have lots of abstract syntax. What is lacking is the proliferation of surface syntax. Typically, programming languages have some dedicated phrase structure rule for recovering each kind of AST node shape out of tokens. Moreover, AST node shapes for which there is no phrase structure in the grammar cannot be instantiated from source text. Lisp languages tend to have a small surface syntax that is general, and expresses all possible AST node shapes, including ones that have no assigned meaning. So, Lisps have plenty of abstract syntax; but abstract syntax is better because it is a data structure that usually no longer exhibits representational issues that require parsing. Sometimes it does. Lisp parameter lists like (a b &optional c &key d e) require a bit of parsing; they are a flat list that has to be scanned for the lambda list keywords like &optional and &key. Nothing stops Lisp programmers from creating similar parsing problems of their own, in the arguments of a macro. Usually it's a far cry from having to deal with a full blown grammar.
- lispm 8y agoThere are many cases where parsing of Lisp code is necessary. A compiler will need to parse it. A compiler might even generate an internal AST representation (Example: https://github.com/clasp-developers/clasp/blob/master/src/lisp/kernel/cleavir/ast.lisp https://github.com/clasp-developers/clasp/blob/master/src/li... ). An interpreter will need to understand the syntax, to be able to traverse code. A tool like a code walker will need to understand Lisp syntax and even may create an AST representation (https://gitlab.common-lisp.net/cl-walker/cl-walker/blob/master/src/handlers.lisp https://gitlab.common-lisp.net/cl-walker/cl-walker/blob/mast...).
- kazinator 8y agoRecovering an AST representation from the source code doesn't require parsing in general, only in some specific cases. By parsing I mean "recovering of nested syntactic units from a flat stream of tokens". E.g. when a compiler is processing let, it doesn't have to first process phrase structure rules to obtain let as a unit out of a stream of tokens, and identify its constituent pieces like the bindings and body. It has those pieces already in a fixed tree shape. In some constructs, the arguments of a form do have to be treated like tokens and subject to parsing actions to identify the constituent pieces, though usually nothing like a full blown LALR(1) grammar. loop has to parse its clauses; lambda lists have to be parsed; CL's defun needs some light parsing due to some design quirks in the syntax; formatter has to parse the format string and such. Identifying the optional declarations at the start of a body is a piece of light parsing.
- lispm 8y ago> fixed tree shape But it does not know what it is. It has to know the structure of the LET. The LET expression has no tagging of the parts. Is that list after the binding list a declaration or not? How many of them? Is the symbol in the list after a LET a variable? The s-expression does not say what a symbol is: a variable or not. We also don't know what the relationship of the declaration to this variable is: is there a declaration for this variable? The relatively simple syntax of LET: let ({var | (var [init-form])}) declaration form* We then see that the syntax for 'declaration' is quite a bit more complex. An AST will usually represent such information. > parsing I mean "recovering of nested syntactic units from a flat stream of tokens in Lisp this is: recovering of nested syntactic units from a nested list of tokens.
- pflanze 8y agoThis, 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.