5 ms·

Note that 'not requiring a parser' is only true iff you limit the expression language you transform to one that has no syntactical constructs (i.e. can't introd

Note that 'not requiring a parser' is only true iff you limit the expression language you transform to one that has no syntactical constructs (i.e. can't introduce new bindings). If you want to allow those then you need a "parser" on top of s-expressions which maintains a bindings context (usually called a code walker in the context of Lisp). So not requiring a 'parser' in that sense is not really a feature of full (modern) Lisp. (Early Lisps didn't use lexical scoping, and used f-expressions or similar i.e. less of a compile- vs. run-time separation, so it may have worked better back then for what seems to have been the original purpose of Lisp, but they may also have squinted and limited themselves via convention, not sure.) This doesn't mean that there's no usefulness for the 'first-level parsing step' that gives you s-expressions: in some cases you might be handling a context insensitive language like yours. Also, it makes extending the language much more painless (macros easily compose, or more to the point, you can easily invent ad-hoc new languages on top of s-expressions used as inputs for macros, and won't (ever, I think) have problems with their boundaries becoming ambiguous).

taeric 8y ago
I thought I was playing somewhat loose with the term parser. The code I used from SICP is walking the code, after all. More accurate to just say no lexing and tokenization?
- pflanze 8y ago
  Hmm, true you're walking the code already. What you don't do is look at the lexical context or maintain it while walking. S-expressions in full Lisp don't specify lexical constructs, it is only the pre-cursor of such (people often say that S-expressions are the AST of Lisp, that's not true if by AST one understands to mean that each element's functionality is clear, e.g. if it's a function call or function abstraction or constant etc.; an S-expression only specifies a computation given a lexical compile time context). What you (and SICP) are doing is look for symbols like +, regardless of whether + is bound to the addition function or something else. That is fine if that's your intention (it's certainly easier to implement a code walker for and you can often get away with it). If playing/deriv received (+ (flet ((* #'+)) (* x 2)) 12) instead of (+ (* x 2) 12) then it would need to be able to handle the flet form, and maintain the aliasing of * to + in a lexical context that playing/product? has to inspect to know if it's dealing with multiplication (and return false in this case). (Caveat: I'm a Scheme, not Common Lisp user, I hope I got the syntax right above.-- Edit: I didn't; this apparently violates CL because it tries to shadow a standard function name, additionally the flet form apparently requires function definition syntax not just value, i.e. (flet ((* (a b) (+ a b)))..). So, my argument becomes a bit moot in CL as the basic operators can't be shadowed anyway, except I'm told that you can define them in a new package then import them, but then I'm not sure you can rebind them lexically. Scheme is beautifully simple in comparison, it doesn't try to prevent you from shooting your foot but of course encourages to learn to deal with the consequences, which is why I wanted to write my post. It will still be true for the general case in CL, too.) Most programming languages parse from strings (possibly via tokens) to an AST. Lisp parses from strings (possibly via tokens) to S-expressions then to an AST. I just want to point out that one has to be careful here, and want to point out that Lisp isn't fully parsed in the sense that one has got an AST, when you're at the s-expression stage. > More accurate to just say no lexing and tokenization? The read function does more than tokenization, it doesn't give you a stream of tokens (that includes open and close paren token), instead it does give you a hierarchical expression representation. Yes, you don't need to tokenize, but even don't need to do more than that. I don't know if there's some CS term for that, in Lisp it's just "read".
  - pflanze 8y ago
    Here's a perhaps better CL example as it side-steps the non-shadowability of the common-lisp math operators: (+ (flet ((f (a) (* a a))) (f 10)) 2) This would, as I already mentioned, require the code walker to support flet, and also pass around a lexical context so that the additional bindings are known. (And then handle such functions, probably by inlining them.) (I had some discussion on #lisp on freenode.) Anyway, the point I wanted to make in all of this is just to remind people that the meaning of S-expressions is context sensitive, more so than ASTs in most languages. Actually Wikipedia[1] puts contextual analysis as a step after ASTs, so given that, perhaps I was wrong saying that S-expressions are not ASTs, but still it's important to keep in mind that there's a difference from ASTs in most languages. Macros do implement syntax that languages without them would need special parser support for; hence I think of macros as being kind of a continuation of parsing (first step: string to sexpr, second step: macros, then the compiler does the syntactical analysis; if you want to implement derivation of a language enriched with context dependent stuff, then you'd have to hook into the compiler, or do the same context analysis that the compiler is doing). [1] https://en.wikipedia.org/wiki/Abstract_syntax_tree https://en.wikipedia.org/wiki/Abstract_syntax_tree (Perhaps also see https://en.wikipedia.org/wiki/Abstract_semantic_graph https://en.wikipedia.org/wiki/Abstract_semantic_graph )
  - 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 ago
      Lisp 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.

taeric 8y ago

I thought I was playing somewhat loose with the term parser. The code I used from SICP is walking the code, after all. More accurate to just say no lexing and tokenization?

pflanze 8y ago
Hmm, true you're walking the code already. What you don't do is look at the lexical context or maintain it while walking. S-expressions in full Lisp don't specify lexical constructs, it is only the pre-cursor of such (people often say that S-expressions are the AST of Lisp, that's not true if by AST one understands to mean that each element's functionality is clear, e.g. if it's a function call or function abstraction or constant etc.; an S-expression only specifies a computation given a lexical compile time context). What you (and SICP) are doing is look for symbols like +, regardless of whether + is bound to the addition function or something else. That is fine if that's your intention (it's certainly easier to implement a code walker for and you can often get away with it). If playing/deriv received (+ (flet ((* #'+)) (* x 2)) 12) instead of (+ (* x 2) 12) then it would need to be able to handle the flet form, and maintain the aliasing of * to + in a lexical context that playing/product? has to inspect to know if it's dealing with multiplication (and return false in this case). (Caveat: I'm a Scheme, not Common Lisp user, I hope I got the syntax right above.-- Edit: I didn't; this apparently violates CL because it tries to shadow a standard function name, additionally the flet form apparently requires function definition syntax not just value, i.e. (flet ((* (a b) (+ a b)))..). So, my argument becomes a bit moot in CL as the basic operators can't be shadowed anyway, except I'm told that you can define them in a new package then import them, but then I'm not sure you can rebind them lexically. Scheme is beautifully simple in comparison, it doesn't try to prevent you from shooting your foot but of course encourages to learn to deal with the consequences, which is why I wanted to write my post. It will still be true for the general case in CL, too.) Most programming languages parse from strings (possibly via tokens) to an AST. Lisp parses from strings (possibly via tokens) to S-expressions then to an AST. I just want to point out that one has to be careful here, and want to point out that Lisp isn't fully parsed in the sense that one has got an AST, when you're at the s-expression stage. > More accurate to just say no lexing and tokenization? The read function does more than tokenization, it doesn't give you a stream of tokens (that includes open and close paren token), instead it does give you a hierarchical expression representation. Yes, you don't need to tokenize, but even don't need to do more than that. I don't know if there's some CS term for that, in Lisp it's just "read".
- pflanze 8y ago
  Here's a perhaps better CL example as it side-steps the non-shadowability of the common-lisp math operators: (+ (flet ((f (a) (* a a))) (f 10)) 2) This would, as I already mentioned, require the code walker to support flet, and also pass around a lexical context so that the additional bindings are known. (And then handle such functions, probably by inlining them.) (I had some discussion on #lisp on freenode.) Anyway, the point I wanted to make in all of this is just to remind people that the meaning of S-expressions is context sensitive, more so than ASTs in most languages. Actually Wikipedia[1] puts contextual analysis as a step after ASTs, so given that, perhaps I was wrong saying that S-expressions are not ASTs, but still it's important to keep in mind that there's a difference from ASTs in most languages. Macros do implement syntax that languages without them would need special parser support for; hence I think of macros as being kind of a continuation of parsing (first step: string to sexpr, second step: macros, then the compiler does the syntactical analysis; if you want to implement derivation of a language enriched with context dependent stuff, then you'd have to hook into the compiler, or do the same context analysis that the compiler is doing). [1] https://en.wikipedia.org/wiki/Abstract_syntax_tree https://en.wikipedia.org/wiki/Abstract_syntax_tree (Perhaps also see https://en.wikipedia.org/wiki/Abstract_semantic_graph https://en.wikipedia.org/wiki/Abstract_semantic_graph )
- 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 ago
    Lisp 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.