Hacker News Reader

Comment by sebcat | Hacker News Reader

One could argue that. One could also argue that it should be possible to collect any garbage successfully created.

Nope; worse is better. It has to be recognized that a garbage collection scheme which can satisfy this idealist requirement has some disadvantages relative to one which doesn't.

Should it also be possible to successfully read any well-formed S-expression that we can create in a text stream? Oops, don't use recursion in the reader, then.

It doesn't have disadvantages apart from the code to manually manage an explicit stack. The actual space used will be reduced.

And yes, it should be possible to successfully read any well formed sexp that can be created in a text stream and held in memory. That's why quality parsers use an explicit stack as well.

Recursion is a useful development tool in some cases, but when iterative algorithms fail because they use it, the implementations are buggy.

I rewrote the JSC parser to be mostly iterative many years ago - for a “real” language making an iterative parser that is readable is incredibly challenging. Especially in something like js where an expression could actually contain a statement. The current state is “as iterative as is sanely understandable” and handles all real (and some insane) programs fine. I suspect similar is true for other production hand written parsers.

Your alternative is table based parsers which can only reasonably be implemented with generators. The problem is that table based parsers are slower than hand rolled recursive descent parser by a fairl large margin, and general purpose generators (bison, yacc , etc) tend to have difficulty with the quirky syntax of large languages. Note there have been a number of papers over the years that demonstrated 2x perf improvements in yacc/bison by switching from indexed state transitions to computed go to, but even that leaves them slower than hand rolled.

> for a “real” language making an iterative parser that is readable is incredibly challenging.

Not to mention if it is defined in terms of a character-classifying read-table which dispatches functions, which can be patched by the user program (as in Common Lisp).

You can hold a S-exp in memory such that you don't have anywhere near enough memory left to scan it with even your condensed explicit stack.

> That's why quality parsers use an explicit stack as well.

Observation: that rules out the entire description of the ANSI CL reader from being quality, haha.

Reply on news.ycombinator.com