What Hacker News says

erwanOct 2018

That's a bit unfair, Hopcroft and Ullman is extensive and detailed by design. They invented the field AFAIK so this book ought to be deep as they use it to lay its foundations. If you - or lurkers - are looking for a solid, down-to-earth exploration of automata theory - but not so much proofs, then I would recommend these in no particular order:

- "Introduction to the Theory of Computation" [Part I] by M. Sipser

- "Introduction to Compiler Design" by Torben A. Mogensen

- "An introduction to Formal Languages and Automata" by P. Linz

- "Languages and Machines" by Thomas A. Sudkamp

>Many of OP's objections come off as petty

I have had the book in my hands, I have turned the pages and seen the typesetting myself. It's not an exaggeration. It looks like one of those books written by a typewriter with some of the lines are misaligned, except it wasn't and that is overall a pain to parse. Also the pages are small and margins wide.

Why inflict that upon yourself when there are plenty of other books that show a modicum of effort in editing.

thread

teleforceApr 2026

The latest edition (3rd Edition) of Introduction to Compiler Design by Mogensen has new topics on SSA form, garbage collection, polymorphism and translation of pattern matching [1].

[1] Introduction to Compiler Design:

https://link.springer.com/book/10.1007/978-3-031-46460-7

thread

kragenAug 2022

The XSLT question is very interesting!

Usually XSLT processors interpret XSLT rather than compiling it, making them compilers rather than interpreters. You could write a compiler for XSLT, and that might be a useful thing to do, but I don't know of such a compiler. (There are several such compilers for the similar XQuery, such as XQC.) XSLT is itself a language that might be especially suitable for writing some compilers in, since it includes a built-in parser and pattern matching, although it generally wouldn't be in my top ten list. If you were running such a compiler in an XSLT interpreter, the interpreter process would be acting simultaneously as an interpreter (for your XSLT) and a compiler (because an interpreter carries out the actions of the program it interprets, like a puppet).

But that wouldn't mean that the XSLT interpreter was a compiler; that would mean the XSLT program it interprets was a compiler.

I agree that if you were to define "compiler" as "a [program] that takes input and transforms it into a different output", then TeX would qualify, as would almost all programs encountered in practice, the exceptions being those that didn't take input, didn't produce output, or that produced output that did not depend on their input. However, this is not a definition of "compiler" that has any currency, and it is well-known that you can make any statement true by redefining the terms used in it, even "TeX is a compiler". In addition to redefining "compiler" as you did, for example, we could redefine "TeX" to mean "kragen" and "a compiler" to mean "a person in the process of taking a giant stinky dump".

The usual definition of a compiler, though, is something like "a program that translates programs from one language into another," and TeX clearly does not fit that definition. For example, Wikipedia:

> In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language). The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a lower level language (e.g. assembly language, object code, or machine code) to create an executable program.

Waite and Goos (emphasis in original):

> The term compilation denotes the conversion of an algorithm expressed in a human-oriented source language to an equivalent algorithm expressed in a hardware-oriented target language.

Muchnick, Advanced Compiler Design:

> Strictly speaking, compilers are software systems that translate programs written in higher-level languages into equivalent programs into equivalent programs in object-code or machine language for execution on a computer.

Grune, Reeuwijk, Bal, Jacobs, and Langendoen, 2e, emphasis in original:

> In its most general form, a compiler is a program that accepts as input a program text in a certain language and produces as output a program text in another language, while preserving the meaning of that text.

Wirth, Compiler Construction, online revised edition, emphasis in original:

> Computers, however, interpret sequences of particular instructions, but not program texts. Therefore, the program text must be translated into a suitable instruction sequence before it can be processed by a computer. This translation can be automated, which implies that it can be formulated as a program itself. The translation program is called a compiler, and the text to be translated is called source text (or sometimes source code).

Mogensen, Introduction to Compiler Design, 2e:

> A compiler translates (or compiles) a program written in a high-level programming language, that is suitable for human programmers, into the low-level machine language that is required by computers.

Some of these definitions are broader than others (for example, many of them would exclude javac), but TeX doesn't fulfill any of them.

There are fuzzy areas between compilation and interpretation! TeX just isn't one of them. For example:

∙ a Forth or Common Lisp compiler can interpret arbitrary code in the source language at compilation time, making the compiler extensible;

∙ a Scheme compiler interprets macros at compilation time;

∙ a C++ compiler interprets templates at compilation time;

∙ as Koshkin points out in https://news.ycombinator.com/item?id=32357461, by redefining the semantics of a programming language you can justify calling any compiler an interpreter, where for example you interpret "/" as meaning "output machine code to divide two quantities" rather than "divide two quantities", but this trick doesn't work to justify calling any interpreter a compiler;

∙ many interpreters interpret some kind of bytecode for efficiency and consequently contain a compiler that compiles the source code into that bytecode;

∙ to a significant extent we can think of the runtime support library for a programming language like C or Visual Basic as "interpreting" the calls into it from the compiled program, which might be in machine code or not, particularly salient examples here being Nuitka or perl -MO=C;

∙ a common formulation of certain optimizations, such as constant folding and loop hoisting, is as abstract interpretation with non-standard semantics; and

∙ the Futamura projections formulate the whole compilation process as the currying of an interpreter with a source-program argument, followed by possible partial evaluation, and this is in fact how PyPy and a few other JIT compilers work.

In an extreme version of these last two cases, we could imagine concatenating an interpreter with the unmodified source code into an executable, like PyInstaller does, and saying that we have "compiled" the source code. In this case you have something that behaves like a compiler from the user perspective (source code in, executable out), but actually doesn't do any translation. It might be reasonable in this case to argue about whether the program is "compiled" or not, but there is still a crystal-clear distinction between the interpreter and the putative compiler: the interpreter is the thing that is bundled into the executable, and the compiler, if any, is the program that concatenates the interpreter, source code, and libraries.

thread

cedex12Feb 2020

On a related note: What's a good introduction to compiler design ? Has the dragon book been superseded by something yet? Ideally you'd be able to write a decent compiler for your own language after going through it.

thread