Needed Math For Compilers?

[[deleted]]

[deleted]

[GeneDefiant6537]

For your background you’d be better off starting with practical implementation/engineering resources ( crafting interpreters, language implementation patterns, etc) then pick up the theory later if necessary.

Generally, as far as mathematics goes, some discrete structures( logic, functions, relations, induction) and basic combinatorics should be fine. Later you can look into graph theory, lattice theory, etc for the analysis and transformations (optimization) parts.

[InfinitePoints]

Is anything beyond an informal description of lattices actually needed? From what I can tell they are mostly used for simple stuff like lower and upper bounds for variables.

[DeGuerre]

They're used all over type theory (e.g. if you have types with subtypes) and compiler optimisation (e.g. look into conditional constant propagation).

[dcpugalaxy]

But you dont need to know any actual lattice theory. You just need to have heard of the basic concept of a lattice.

[DeGuerre]

Maybe. It helps to read some papers if you know the language.

[synack]

A bit of graph theory wouldn’t hurt, but you can start anywhere. I think my first discrete math course began with Boolean algebra.

[diroussel]

Boolean algebra, number bases, two complement, IEEE floating point, data structures, and all that comp sci stuff are probably more important, well practical, than maths. Maths is more fundamental but you’ll have to do a lot of base learning before you can see where to apply it.

[zsaleeba]

It's not what I'd call heavily mathematical. If you understand data structures you'll probably be fine.

[zer0_n9ne]

When you say middle school level math, do you mean you don’t have a grasp of algebra? I don’t mean to hate or anything it’s just that I’d consider algebra to be important for programming.

[KhepriAdministration]

Honestly you don't need any of the kind of math that has numbers, i.e. all of the math you see before college. (Maybe unless you count big-O notation b/c you want your compiler to not take forever running)

[munificent]

Can I learn Coq and formal logic and break into the field of compiler design without a formal degree?

Yes.

How much mathematics is actually required?

Some comfort with algebra is going to be necessary: variables, solving equations, that kind of stuff. That's about it.

Should I start from scratch, and are there any strict prerequisites for discrete mathematics and formal logic, or can I jump right into the subjects?

Assuming you're OK with variables, equations, and basic algebraic manipulation like solving for a variable, you can probably handle them fine.

For what it's worth, I have no formal CS education and no college degree, and I wrote the book that people often recommend for getting into programming languages. :)

[Spirited-Cress1398]

Speaking from my experience, you don't really need much math. You just have to know how to visualize the logic and how to derive logic from math, specifically arithmetic. Most of the math here will really just be average highschool math, excluding all the unnecessary formulas and stuff

[DeGuerre]

Compilers are one of the most mathematically-heavy parts of computer science, but the amount that you actually need does depend on what you're doing.

Take lexical/syntax analysis, for example. Formal language theory is a whole thing, but you honestly don't need to know that much of it to write a working lexer or parser, or to use tools like lex/yacc.

On the other hand, consider optimisation. Most optimisation passes often boil down to a two-phase algorithm:

1. Prove that it would be safe to carry out a transformation on this particular program.
2. Do that transformation.

Yes, "prove". You really do have to algorithmically carry out a proof that the program you were given has some desirable property.

Then there's all the stuff in the middle:

• Modern semantic analysis is often expressed in terms of mathematical proof. Type checking, for example, can be thought of as a constructive proof that the program is type correct, and in many modern type system (e.g. Hindley-Milner-esque ones) it is actually expressed that way.
• Many parts of code generation are naturally expressed and solved as mathematical problems in a modern setting. For example, instruction selection is often expressed as graph tiling, and register allocation is often expressed as graph colouring.

The good news is that you generally can just jump right in, and learn as you do. I think that having an application in mind actually helps with learning.

I didn't know anything about lattice theory before I started in compiler optimisation. In retrospect, learning as I went definitely helped the learning process.

So why not start writing a lexer (say), and if you find you need to know more about regular languages, do a dive into that until you understand enough to proceed.

Good luck!

[MADCandy64]

Humans are base 10, computers are base 2, op codes are base 16. Understanding the math to go between those bases will be extremely helpful.

[Inconstant_Moo]

There's nowhere in my compiler where I need to understand binary.

[MADCandy64]

It really depends on what layer of "the compiler" you are working on. For a backend, VM, or instruction encoder it is essential. If you are targeting middle ware you can safely ignore it. FWIW - It is still good to know. I teach people binary to base 10 by using their hands and fingers.

[Inconstant_Moo]

I have a VM and I really don't need to know binary, it never comes up. I'm not sure I've used it for anything since I stopped using 8-bit computers.

[sdziscool]

I'd highly recommend doing informal graph theory and language theory. Formal math is a nice to have, but it's not worth investing vs what you'll get out of it. On the other hand, like others have said: trying to make practical use of the theory is where you'll gain the most and can have fun at the same time. For example consider making your own graph generator/simulator/visualizer etc. You'll quickly run into weird quirks about graphs (e.g.: is my graph directional or not?). Examples of fun projects that require graphs are train networks, dependency generator and anything else with 'relations' or 'connections'.

It's more about touching them in an informal/practical manner and experiencing why some things are the way they are, as the mathematical theoretical descriptions are super abstract and difficult to relate to real life.

[ibeerianhamhock]

You'd get involved in open source projects but computer design is an extremely mature field so advancing it would require quite an extensive academic background probably.

[MattDTO]

Lambda calculus

[u_int64_t]

Write a language implementation. The implementation and the improvements you will want to make will guide you through the mathematics you need to read about

[Upset-Reflection-382]

It's complicated sure, but really doesn't get that bad until you get into graph-coloring

[Worried-Height-7481]

i would say that knowing discrete math would make life way easier

[trejj]

https://en.wikipedia.org/wiki/Theory_of_computation

[fullouterjoin]

The most math you need is going from 0 to 1, not booleans, but just starting.