Hacker News Reader

Comment by baddox | Hacker News Reader

A language's grammar wouldn't necessarily be a good indicator of implementation size, would it?

Pascal's grammar is so simple by design that it can be parsed and codegenned in a single recursive descent pass. Not many languages are like that, especially these days.

There are a billion Lisp parsers in a few lines of Python, C, Lisp, etc. Any Pascal ones like that?

Edit; not meant sarcastic, I would really like to see such a simple parser as was implied.

"parsed and codegenned" he said. Any Lisp compilers like that?

No, but only by definition. Passing through an s-expression representation is a requirement for a lisp compiler, because the tree to be compiled might have been built at runtime. Certainly lisp's grammar is no more complicated than pascal's.

Nor, frankly, is K&R C, which is is also a very simple representation. The ANSI process added some edge cases that complicated it, but really it's pretty simple.

I don't know any practical algorithm for handling closures that'll let you code-gen Lisp in one pass, but in general writing Lisp compilers is frightfully easy: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

I believe that's how the Clojurescript compiler currently works (though I haven't looked at the code in detail). Compilers that don't do it that way usually have optimizations going on in between the parse and codegen phases, not because it's impossible to do with Lisp syntax.

"because it's impossible to do with Lisp syntax."

The problem is not with Lisp syntax. The problem is with Lisp's semantics, which makes it much more difficult (if at all possible) to compile in one pass. Things like closures, conditions or macros are absent in Pascal.

ClojureScript has a two-pass compiler; more if you consider GClosure a step.

No, but Lua works that way.

It's easy to write very small interpreters, even ones that JIT code. So much so that some approaches to shrinking software have historically been to write a little VM interpreter, and compile the source code to target that rather than the actual CPU. A compiler that produces code that no longer requires a runtime (in the VM sense - inverted control) is slightly more work.

Turbo Pascal's code generation was simple and naive. It had little optimization. It literally output the machine code as it parsed. There was no AST, not even an expression tree.

(I have the source code to the final version of the Turbo Pascal compiler on my disk. It was used for Delphi 1.)

>(I have the source code to the final version of the Turbo Pascal compiler on my disk. It was used for Delphi 1.)

Is that still under copyright? And chance it could be released?

As far as I know it is still under copyright. Anders Hejlsberg's name is in the comment headers; it was largely rewritten in 1986 and 1987 for TP4. I believe it belongs to Embarcadero, the company I work for, after they bought the developer tools division from Borland.

I have no idea about releasing it. I'm entirely the wrong end of the company to ask about it.

Those billion Lisp implementations primarily exist because Lisp is fashionable; Pascal is not. In the past, toy Pascal compilers have actually been a popular project (especially in introductory compiler courses).

Go can be parsed in one pass without a symbol table.

Here's a Pascal-ish parser: http://compilers.iecc.com/crenshaw/

Not necessarily. Some grammars can be parsed with simpler code than others, but optimizations can make a compiler larger. Also of note is that Turbo Pascal was written by hand in assembly language, and the executable wasn't likely to have been linked with any libraries.

Indeed TP did not have any linking step. I still recall trying to fruitlessly find "Link" on the menu for quite some time until it hit me -- oh, no linking needed. But TP did include a run-time with each of the generated executable. This run-time was part of the compiler and it was approximately 10K (from memory, so I could be wrong). That makes the compiler about 22Kbytes worth of code, which is even more impressive.

I wasn't aware that the runtime was included in the executable. Oh, the things we did in the DOS days!

Interesting, I didn't know this but Turbo Pascal was written by Anders Hejlsberg (of Delphi and C# fame).

Yes it would. Not a bullet proof one (is there any?) but a good indicator.

Reply on news.ycombinator.com