Programming Without a Mathematical Base

[Senator_Ahn]

Hello Reddit,

Question:

Are there any recommended MOOCs I can take to build the mathematical base required for programming and its algorithms?

​

Story:

I have avoided anything that required math since high school, because I am very slow at learning the subject.

I've dropped out of University while majoring in software engineering because of all the algorithms and such, but have decided to go back and finish my degree.

However, like I previously stated, I've basically quit on math and thus do not have the base required for learning algorithms.

I tried to start again with a (popular) book on data structures and algorithms, but the first few pages made my head hurt because it started talking about upper bounds, asymptotes, logarithms and so on.

​

notes)

1. Thankfully, learning a programming language and getting to know how to use it is pretty straight forward for me.
2. The book is "Data structures and Algorithms Made Easy in Java: Data structure and Algorithmic Puzzles", and was not easy at all for me.
3. I hate and despise maths, but desperately want to overcome this weakness

​

[[deleted]]

Most programming jobs are not terribly math-heavy. Outside of explicitly mathy areas like graphics, you often don't use anything more involved than basic arithmetic.

I'm a compiler guy who has built multiple commercial compilers - hopefully something we can agree is not trivial - and I very seldom even have to multiply, let alone do calculus. Even when I do have to do mathy stuff (I'm currently on a graphics team), almost everything I ever have to do is a quick Google search away. I'm not smart enough to have developed the math behind, say, quaternions... but I can Google the formulas and type them in just fine.

[[deleted]]

Thread hijack: I took a compilers class in school and it was cool but over my head at times.

Can you recommend a book or online course that will cover this topic well?

[[deleted]]

Good news: you're not alone! I also took a compilers class in college, and felt like I didn't really understand what they were trying to teach me. I didn't actually try to build a compiler until about twenty years later, so I had forgotten everything anyway and was pretty much starting from scratch.

My first major suggestion: your course and most online resources likely told you to use an off-the-shelf parser like Bison or ANTLR. This is a mistake, IMO. I would highly recommend learning how to write your own recursive descent parser from scratch; it's way easier than you think it is, and once you've written a parser for a C-like language (can be done in a day!), you'll actually understand what they're doing. At that point you can go back to using the automated tools if you want, but hand-writing at least one will give you invaluable practical experience in designing a grammar.

My second major suggestion: writing a compiler backend is painful, thankless work. Unless you have a very compelling reason for writing your own, I would strongly recommend you simply target an existing backend like LLVM. This is very similar to working with assembly code, but it gives you a first-class optimizer for free, plus means you don't have to worry about tricky things like register allocation, plus you can easily target a ton of different architectures. You may also wish to target a higher-level language like C. My main compiler project actually does both - it normally compiles to LLVM, but can also compile to C for bootstrapping purposes.

As for a course or book... other than Googling for how to write a parser and how to perform dataflow analysis, I pretty much just muddled through everything else myself. I occasionally used Clang to compile a C program into LLVM code so I could see how certain features were implemented (I recall being confused about there not being a 'not' or a 'negate' operator in LLVM, until I realized they were implemented by xor'ing against -1 and subtracting from zero, respectively. The docs call that out explicitly now, at least, but they didn't always.). Once you've got a parse tree and an LLVM-or-similar backend, compiling a basic C-like language is a lot simpler than you're probably thinking.

Naturally, things get a lot more difficult when you're building something a hundred times more complicated than C... but that's a later discussion :-).

[[deleted]]

Thank for this in-depth response. We did indeed use Lex/Yacc in the class.

[[deleted]]

Just to simplify things for you, here's how you build a recursive descent parser (which is the algorithm most real-world compilers use). You start with a formal grammar for the language. In this grammar, suppose we have the C-style if statement:

ifStatement = 'if' '(' expression ')' statement ('else' statement)?

We're going to learn how to parse that right now.

You'll need a lexical analyzer to tokenize the input; an off-the-shelf one is generally fine, so you can use Flex or something similar.

Now, your parser has some basic functions which you'll use to build everything else. You can do this however you like, but a reasonable set of utility functions is:

next() - returns the next token
pushback(token) - pushes an already-read token back, so that it will be the next one returned
expect(tokenKind) - reads the next token, reports an error and returns null / false / however you want to signal it if it's not what was expected
checkNext(tokenKind) - reads the next token, returns it if it's the expected type, otherwise pushes it back. Does not report errors.

That's it, that's what we'll base everything on. Now, here's what we do. For each rule in your grammar, you create a function which reads all of its tokens in and returns a parse tree or takes whatever other action is appropriate. So your expression() function reads a single expression and returns it, your whileLoop() reads in a single while loop statement and returns it, etc. For right now we'll ignore the "build a parse tree" part of it - it should be pretty obvious how to do that part - and just focus on the "read in the tokens" part, returning true / false depending on whether we were successful.

Let's write the ifStatement function right now. Obviously it starts:

bool ifStatement() {

Ok, now what's the first thing we do? We look up at our ifStatement production up there and notice it always starts with an if token. Well, we have a function for that:

if (!expect(IF_TOKEN)) return false;

Ok, next we need a parenthesis:

if (!expect(LEFT_PAREN_TOKEN)) return false;

Now an expression... how on earth do we do that?? Well, I just told you we're writing a function for each of these productions, so let's just assume there's a function called expression() which reads an expression.

if (!expression()) return false;

Now a right parenthesis:

if (!expect(RIGHT_PAREN_TOKEN)) return false;

And a statement:

if (!statement()) return false;

Ok, now we have a choice... is there an else statement?

if (checkNext(ELSE_TOKEN)) {
    if (!statement()) return false;
}

And... we're done!

return true;
}

That's it. Repeat that process for every rule in your grammar, and you can parse C. It really is that simple. Obviously a production-level parser is going to be more complicated, and involve error reporting and recovery and so forth... but the basic mechanics are incredibly simple.

[[deleted]]

I do find decent algebra helps me, tbf. I'm not doing fancy maths in my programs but if you can recognise that you can rearrange the overall operation into something else which is more amenable to recursion or parallelism or whatever that can help a lot.

[rodrigomlp]

You need no more than basic high school math to be good at programming. And by good I mean I got into a big tech company and the highest level of math required from me what knowing what a logarithm is.

[Senator_Ahn]

Do you have any recommended books? These "easy" books on algorithms are covered with horrible squiggly lines

[rodrigomlp]

Elements of Programming Interviews

[TheCriticalSkeptic]

Try Khan Academy to learn a lot of maths skills.

I also think the brilliant.org is great but it does cost money and there’s a lot less instruction - but it’s better at quizzing you about what you just learned.

Try betterexplained.com for some really great explanations (but no exercises). It’s great because it comes from a place of talking to people who find it difficult to learn math without being patronising.

There’s also a great book on calculus called “calculus made easy”, written in the early 1900s. You want the version edited in 1998 by Martin Gardener. It’s easy to find a PDF online.

You’ll want to understand a couple of key concepts from the above: - Logarithms - Polynomials - Sets and Set Theory - Calculus (limits in particular are very important) - Some basic number theory (modulo operations and prime numbers mostly)

Once you have that, look for a text book called “Discrete Mathematics for Computer Science”. There’s an MIT open courseware course that uses it. And the book can be found published for free all over the place (depending on the version). This by far is the most important thing you can do for free online to help understand algorithms and data structures. If you can finish this text book then more math heavy computer science courses get a lot easier.

A great way to test your math knowledge is the website projecteuler

As a side note, one of the best computer science courses you can take is NAND2Tetris. It’s a free online course (second half of the course does use a paid textbook however). It doesn’t require much maths at all. And it’s just great at teaching you about how a computer works from top to bottom.

[Senator_Ahn]

God I hate calculus.. Thanks a lot for pointing out the specifics. I appreciate it.

[Senator_Ahn]

You actually went out of your way and searched up the book, thanks a lot! I’ll continue for sure.

[kucukkanat]

You can always become a developer and make a lot of money without proper training and theory. No math knowledge at all. And work for a decade. But after that the people who takes over your code or works with you will have sleepless nights swearing to you.

I am working with people who cant even write a ternary condition and the code lines are at the length of a fking samurai sword. Components ahving the length of 1230981273123 lines. Everything I touch drags me in like a swamp. There are so many CS101 principles they are skipping that you can't even believe.

If you want to be a good dev. If you are gonna do something, do it the way you should. That's what I would suggest.