Can you tell me what mathematical background (concrete themes) should I have for

Question

Can you tell me what mathematical background (concrete themes) should I have for studying and doing some investigations (in future) in programming languages, compilers and formal methods in software engineering? For instance, discrete mathematic course contains combinatorics, numbers theory, graphs and etc. But I think not all themes are needed to me at the first step. Can you highligh concrete themes of mathematics which are needed for programming languages, compilers and formal methods in software engineering? And may recommend some books and articles about this themes.

Explanation / Answer

Off the top of my head:

Stuff covered in a typical discrete mathematics course; you'll need a bit of everything. Sets, graphs, combinatorial algorithms, and so on, are all part of the modern modern compiler writer's experience. Denotational semantics, for example, is very heavily based on the language of lattice theory. The good news is that a brief overview will do it, and most of the rest can be learned as needed.
Formal language theory, automata, etc. You'll need a thorough grounding in this. You'll probably never be called upon to, say, write an LR parser generator, but you'll need to know what it does to a) know what to feed such a generator, and b) diagnose when something goes wrong. Also, many production compilers use hand-crafted parsers these days for better error reporting.
Category theory, modern logic, lambda/pi calculus, type theory. This is much more important than it used to be, as modern languages often specify their semantics in this notation. Again, the good news is that you only need a basic grounding and can learn the rest as needed. If you're at the point where sequent calculus notation isn't scary, the rest is detail.
Modelling languages: Petri nets, state transition systems, UML statecharts, abstract virtual machines for specific languages (e.g. SECD, WAM), etc. You know the drill.

Specific books I would recommend:

General computer science: Concrete Mathematics by Knuth, Graham, and Patashnik. These are the basic mathematical prerequisities for any career in computer science. Follow-up book is The Art of Computer Programming by Knuth.
Programming language semantics: Structure and Interpretation of Computer Programs by Abelson and Sussman. It's free online, so you have no excuse. Follow-up book is Types and Programming Languages by Benjamin C. Pierce. (There is also Advanced Topics in Types and Programming Languages by the same author; definitely read this if the first book got you hooked.)
Compilers: Compilers: Principles, Techniques, and Tools by Aho, Lam, Sethi, and Ullman. But you already knew this! Followup books which are well worth reading include Modern Compiler Implementation by Appel (there are C, Java and ML versions; the ML version is easily the best) and Advanced Compiler Design & Implementation by Muchnik.
Formal languages and automata: I think you can't go past Introduction to Formal Languge Theory by Harrison here, but a more general book like Automata and Languages by Howie, or Languages and Machines by Sudkamp, might be better first. Honourable mention: LR Parsing: Theory and Practice by Chapman.
Category/type/etc theory: As well as TaPL (mentioned above), to get into this deep but increasingly important area, start with Conceptual Mathematics by Lawvere and Schanuel if you want a very gentle introduction, then move to something like Categories, Types, and Structures by Apserti and Longo, or Basic Category Theory for Computer Scientists by Pierce, or Category Theory for the Working Computer Scientist by Barr & Wells.
Abstract virtual machines for specific kinds of programming language: There's a lot of possibilities here and it's very easy to get lost. There is an extensive bibliography by Diehl et al; they did the world a great service here. My personal highlights include The UCSD Pascal Handbook by Clark and Koehler (don't let the title fool you; the full compiler source with explanation, including a description of the P-machine, is all here), Compiling with Continuations by Appel, Warren's Abstract Machine: A Tutorial Reconstruction by Ait-Kaci, and The Implementation of Functional Programming Languages by Peyton-Jones. Plus, of course, there's the ubiquitous JVM. Many of these books are out of print, and available for free online.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.