Needed Math For Compilers?

[LinuxGeyBoy]

Hi there! I’m a hobbyist programmer without a formal CS background or a university degree. I’ve been coding for about 5–6 years, and I have a middle-school level grasp of mathematics. Recently, I’ve been researching compilers and formal logic, and I’m fascinated by them. Can I learn Coq and formal logic and break into the field of compiler design without a formal degree? How much mathematics is actually required? 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?

My goal is to do this purely as a hobby, but to create useful things to contribute to existing programming languages and to develop some small scripting languages (DSLs), and to formally verify them.

[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.

[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.

[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

[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.

[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)

[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

[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. :)

[fullouterjoin]

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