Comment by matheusmoreira | Hacker News Reader

Comment by matheusmoreira | Hacker News Reader

> I used an S-expression syntax, instead of designing my own syntax and writing a parser for it.

> This meant I was able to experiment with the semantics and virtual machine of the language, instead of worrying over what keyword to use for function definitions.

Yeah. I see a lot of people asking why people are so fascinated by lisp and why there are so many lisps out there. I think this is a huge reason. It certainly was for me.

I just wanted to get some ideas working as soon as possible. Lisp is the easiest language to parse that I've ever seen, managed to write a parser by hand. And yet it's a fully featured programming language. It just gives you huge power for very low effort. It took a single bit to add metaprogramming to my lisp:

  if (function.flags.evaluate_arguments) {
    arguments = evaluate_all(interpreter, environment, arguments);
  }

I see it as a little frontend for my data structures. I get to work on them endlessly and everything I do improves something.

> Lisp is the easiest language to parse that I've ever seen, managed to write a parser by hand.

I've written a dozen or so parsers for different languages by hand: the parser is easy regardless of the syntax you choose. The complicated bit is always compilation/interpretation.

The biggest value I see to using S-expressions isn't the time saved in writing a parser, it's reducing the amount of bikeshedding you'll be tempted to do fiddling with syntax.

Aren't languages like C notoriously difficult to parse? I've read that they're actually context sensitive. IIRC much of Go's syntax was designed to avoid parsing complexity.

See the clockwise/spiral rule!

Type syntax started pretty easy to parse, basically just parse a C expression. It became more complex and inconsistent later (when for example types for function parameters were added), but IIRC the clockwise/spiral rule is nothing like the idea behind the syntax. I think it is too complicated / not getting the gist of it.

I suspect that the interpretation of C cannot be specified in a brief page of C code. For one thing, the language doesn't supply the data structures for representing any aspec of itself; the code will have to invent those: declarations, definitions, statements, types. Then handle a ton of cases.

It will not be obvious that what the C code is doing is C interpretation, because all those data structures don't resemble the C syntax.

The Lisp meta-circular interpreter side-steps that; the issue is settled elsewhere. It exists against a backdrop where the easy correspondence between the printed syntax and the data structure being handled by the interpreter is taken for granted.

The C would need the same kind of backdrop; and that would be a lot of documentation.

> Aren't languages like C notoriously difficult to parse? I've read that they're actually context sensitive.

All programming languages with identifiers are context-sensitive if you put well-formedness into the grammar. C is not exactly difficult to parse, rather it just needs some specific approach compared to most other languages. The biggest (and technically the only [1]) ambiguity is a confusion between type-specifier and primary-expression, which is a roundabout way to say that `(A) * B` is either a multiplication or a dereference-then-cast expression depending on what `A` is in the current scope. But it also has a typical solution that works for most parsers: parser keeps a stack of scopes with contained identifiers, and lexer will distinguish type identifiers from other identifiers with that information. This approach is so popular that even has a name "semantic feedback".

[1] As an example, the notorious pointer and array declaration syntax is actually an unambiguous context-free grammar. It is notorious only because we humans can't easily read one.

> IIRC much of Go's syntax was designed to avoid parsing complexity.

Go's semantics (in particular, name resolution and module system) was designed to avoid complexity. Its syntax is quite normal, modulo personal and subjective bits which all languages have. I can't see any particular mention of syntax decision to performance in the initial spec document [2].

[2] https://github.com/golang/go/blob/18c5b488a3b2e218c0e0cf2a7d...

For the context sensitive part, all you need is a symbol table to check which names are for types. I haven't actually done it but I don't think it is hard.

The real problem is the preprocessor, it's very hard to implement, and implement in a standards-compliant way. (haven't finished one either, but everybody says so). And without preprocessor and proper include processing, you simply can't parse correctly because you lack the context of which types are defined (besides missing preprocessor symbols).

Another problem that comes with that is that you always have to parse everything from beginning to end -- including the include files, which can easily be 10s or 100s of thousands of lines of code. I haven't seen a real performant and always correct parser for C IDEs, not sure if one exists.

That rings untrue in the face of how John MacCarthy specified Lisp interpretation, on paper, in Lisp itself, quite briefly, and didn't even suspect it would be executable. Then Steve Russel comes along, and bootstraps it by hand-translating it to code.

I found that a naive frontend for a language is not that big of a deal with something like ANTLR. The benefit is that you have a formal grammar syntax description, and you can iterate on that endlessly without too many code changes down the line.

It isn't with a handwritten lexer/parser either, the real work starts after the parsing is complete. Of course, there are two possibilities: often changing them can either result in a cleaner, more readable result or a _real_ mess ;) But you have to rewrite it by hand anyways if you want to get better (or usable) error messages and incremental parsing for a LSP.

I see lisp as sort of "no syntax". It's basically the AST. Which is a good thing, you can concentrate on the compiler and add syntax later. If you are working on a compiler for a non lisp PL, it makes sense to log the AST after parsing, as a lisp, as a readable AST.

Reply on news.ycombinator.com