Start / The Bike Shed / 374 discrete math

374: Discrete Math

31 min • 7 mars 2023

Joël is joined by a very special guest, Sara Jackson, a fellow Software Developer at thoughtbot.

A few episodes ago, Stephanie and Joël talked about "The Fundamentals" and how many of the fundamentals of web development line up with a Computer Science degree. Joël made a comment during that episode that his pick for the most underrated CS class that he thinks would benefit most devs is a class called
"Discrete Math." Sara weighs in!

This episode is brought to you by Airbrake. Visit Frictionless error monitoring and performance insight for your app stack.

Transcript:

AD:
thoughtbot is thrilled to announce our own incubator launching this year. If you are a non-technical founding team with a business idea that involves a web or mobile app, we encourage you to apply for our eight-week program.

We'll help you move forward with confidence in your team, your product vision, and a roadmap for getting you there. Learn more and apply at tbot.io/incubator.

JOËL: Hello and welcome to another episode of The Bike Shed, a weekly podcast from your friends at thoughtbot about developing great software. I'm Joël Quenneville. And today, I'm joined by a special guest, Sara Jackson, who is a fellow developer here at thoughtbot.

SARA: Hello.

JOËL: And together, we're here to share a little bit of what we've learned along the way. So, Sara, what's new in your world?

SARA: Actually, I recently picked up crocheting.

JOËL: That's exciting. What is the first project that you've started working on?

SARA: I don't know if you happen to be a fan of animation or cartoons, but I love "Gravity Falls." And there's a character, Mabel, who wears many sweaters. I'm working on a sweater.

JOËL: Inspired by this character.

SARA: Yes. It is a Herculean endeavor for my first crochet project, but we're in it now.

JOËL: That does sound like jumping into it and picking a pretty hard project. Is that the way you typically approach new hobbies or new things, you just kind of jump in and pick up something challenging?

SARA: Yeah. I definitely think that's a good description of how I approach hobbies. How about you?

JOËL: I think I like to ease into things. I'm the kind of person who, if I pick up a video game, I will play the tutorial.

SARA: It's so funny you say that because I'm definitely the type of person who also reads manuals. [chuckles]

JOËL: [laughs] I'm sure you've probably, at this point, read many sections of the Unix manual. Longtime listeners might recognize you from a previous episode we did on the history of operating systems.

SARA: Yes, I am an avid reader of the man pages. In fact, I wish every command-line tool had man pages or at least more detailed man pages. Reading man pages, reading technical documentation, really, I feel like goes right in line with things like needlework, knitting, crocheting. You're following a very technical pattern description of what you should be doing, how many stitches. It's almost algorithmic.

JOËL: Do you feel like the fact that you've read a lot of man pages and now that you're getting into reading crochet patterns, do you feel like that's helped you maybe become a better technical writer when you write documentation?

SARA: Definitely. Yes. [laughs] There's a common meme going around on the internet of how to make a peanut butter and jelly sandwich: open jar, put knife in jar. And you see somebody putting the knife in handle first because it wasn't specific enough. When you're looking at a crochet pattern, it needs to be written very explicitly, and in the same way, technical documentation needs to be like that too. It needs to be accessible for every audience, well, most audiences.

JOËL: That's a big challenge because you want to give enough detail that, like you said, you don't accidentally use the wrong end of the knife to spread your peanut butter. But at the same time, if you give all the little details, you lose the forest for the trees. And people who know how to use a knife are going to struggle to use your documentation.

SARA: That is true. That's why I think it is very valuable to do something that you recommend very often, especially when writing blog posts or call for papers is, defining the audience. Who's this for?

JOËL: Yeah, knowing your audience is so important when it comes to any kind of media, even if it's a talk or an article, or I guess, a crochet pattern.

SARA: Precisely.

JOËL: Does the crochet world have sort of the concept of patterns aimed at beginners versus patterns aimed at a more advanced audience?

SARA: I would definitely say that is the case. There are more advanced stitches and techniques that you would generally not see in a more beginner pattern. And in more advanced patterns, at least speaking from a knitting perspective...I'm pretty new to crocheting, but I've been knitting for a while. In knitting patterns, simpler techniques might not be described in such detail in a more advanced pattern.

JOËL: So a couple of weeks ago, Stephanie and I were discussing the fundamentals, how much of the fundamentals of web development line up with a computer science degree. I had made this comment on that episode that my pick for most underrated CS class that I think would benefit most developers is a class called discrete math.

SARA: I remember this class. It was a love-hate relationship. I am a big fan.

JOËL: Would you describe yourself as a math person?

SARA: I don't think so. No.

JOËL: Because I know I hated math for the longest time. And I don't really find that math, in general, has been that helpful for software. There's kind of the stereotype that I'll sometimes hear from people when they find out that I write code for a living. They'll say things like, "Oh, you must be so good at math." And it's like, no, calculus was really hard for me, and I struggled and did not like it.

SARA: I feel like that's a big reason why folks go into programming; the computer can do the math for you.

JOËL: Right? It is a computer. It is a math machine.

SARA: I mean, how many folks in computer-related fields got their start on a TI-83, programming in that thing?

JOËL: A lot of people. Someday it might be fun to do an episode on the sort of common origin stories that you hear from people in the software industry, a lot of people programming a calculator, a lot of people I hear coming from Neopets.

SARA: Yeah, Neopets and MySpace, editing the profile pages with CSS, HTML.

JOËL: But that's an episode for another time. I think, in my experience, discrete math was not like all the other math that I did. It felt so practical, like, this is math for programmers is how I felt it was even though that's not how it's sold in university. What was your experience?

SARA: My concept was very much like, this is logic. This is very hard. By hard, I mean firm way of looking at the world and defining the logic behind things when you think about proofs and set theory.

JOËL: So we've been throwing around the term discrete math, and many of our listeners might not be familiar with what it is. If you had to describe discrete math to someone who is not familiar with it, what would you say?

SARA: Math that's discrete. [laughter] Sorry, sorry.

JOËL: What does discrete mean?

SARA: When I think of discrete math, I think of logic, definitions, how data relates to each other, that sort of thing, as opposed to ones and zeros.

JOËL: Yeah, discrete math; it felt like it was very much like a grab-bag class. It just involved so many different branches of math, and you kind of get a little bit of an intro of like ten different topics, all of which apply and are helpful when you're writing software. So I got a little intro to a couple of different forms of logic, propositional logic, and predicate logic. I got an intro to Boolean algebra.

I got an intro to set theory, an intro to combinatorics, talked about recursive functions from a mathematical perspective, an intro to graph theory. Probably like a few more. There are like ten different things. You just got a little intro to them, spent a couple of weeks on each topic. But I felt like that was enough to give me a lot of value that I still reference on a daily basis in my work.

SARA: Absolutely. One of the parts of discrete math that really stuck with me are computational models like Turing machines, pushdown automaton, finite-state machines. Learning about those, analyzing them really helped me break down algorithms and break down my code and look at, okay, for this specific input that I have for each of these variables, what are we doing?

JOËL: So what does that look like in your daily work? You've got a complex card, and you see that it's a difficult feature to implement. And in your mind, you say, okay, let me try to describe this as a finite-state machine, and maybe you draw a diagram or something like that.

SARA: Yeah, I will, actually. I'll draw a diagram, or I'll draw like a pseudocode out on paper. I'll think about all the different kinds of inputs that I would expect or not expect, which itself is not finite, but we try. And then what is the output that I would expect? What is the outcome that I would expect from, say, a user enters one, a user enters Sara, a user enters purple? What would the outcome be? Do I have those vectors captured in my code? And that also goes into TDD.

JOËL: Do you feel like knowing about Turing machines or finite-state machines has made it easier for you to PDD? That's a connection I haven't heard before.

SARA: Yeah, I think so because a Turing complete computational model is deterministic. That means that every possible path that could be got into from where you're at any path exists between the two. Sometimes it might mean rejection or an error, but the path has been defined. And thinking about that when it comes to tests, I feel like has been so helpful for me of like, I can't just think about the happy path. I can't just think about it's exactly what it needs to be. It's also what if it's not there? What if it doesn't exist? What if it's 0? What if it's empty? What if it's a different data structure?

JOËL: That's really fascinating to me because I feel like I encountered some of these practical applications of it much later when I was learning about types and learning about Elm and sort of that community's approach to designing data structures. And one thing that they say a lot is that you should make impossible states impossible when you design a type, and the way that they tend to approach that is thinking of types as if they were sets.

And so you think of a set of...the Boolean type is a set that has two elements because there are true and false. An enum might have, you know, if it's a three-element enum, that is, three elements. But then you start having things like records which are kind of like a hash in Ruby, which might have, let's say, two elements in them. And if it has a Boolean and an enum value, now those two multiply times each other. And so now you have two times three, six possible states. And maybe the problem you're trying to model only has five, and so you've sort of inadvertently added an extra state.

They tend to talk about it a little bit more through the lens of sets and the lens of combinatorics, which are other elements of discrete math that give you mental models to deal with this. And so talking about all the different possibilities, that's combinatorics. Thinking of a type as a set and talking about its cardinality, that's set theory. So those were things that I would do when I was writing Elm programs on a daily basis, but I never made the connection back to finite-state machines.

SARA: I feel like those marry so well together, those concepts. You can see combinatorics and set theory of objects and of where they can go. And that goes right into graph theory.

JOËL: Oooh, I love me some graphs.

SARA: [laughs]

JOËL: Listeners of the show will know that I am a huge fan of dependency graphs and as a tool and as a model that can be applied to a lot of things, so thinking in terms of maybe the dependencies of your program like packages. But it can also be in terms of tasks to be done and so thinking in terms of a larger feature, breaking it down into smaller features, all of which depend on each other. And depending on how that dependency graph is structured, what order do you need to complete them in order to ship them independently?

SARA: I love that. And it reminds me of graphs that represent state, like, finite-state machines sort of things where you can actually infer where you're going to end up based on where you are for certain types of graphs. And I feel like you can use that in programming. You can use that in proofs where you have the, okay, you've solved for the zero case. You've solved for the one case. Now let's solve for N+1 anytime in the future. This all feels very full circle in my mind. [chuckles]

JOËL: I think that's very apt. And a really powerful thing that I've noticed is having different mental models to approach the same problem or different logical or analysis techniques to interact with the same problem. And so when you look at something through the lens of a finite-state machine, or through the lens of a graph, or through the lens of a set, or through the lens of combinatorics, you might be looking at the same problem. But by having different perspectives to look at it, you gain different insight and hopefully helps you come to a better solution.

SARA: Absolutely. And I love that discrete math gives us those different tools to be better programmers. It's something that I enjoy. And I enjoyed the classes as much as they were extremely difficult. And I love the idea of being able to share those tools with other people that might not have learned about them.

JOËL: You were talking about seeing things from different perspectives and how they kind of line up. There are some equivalences that I found were really fun between, let's say, sets and Boolean algebra, the operations that you can do. So things like ANDing two values is similar to doing an intersection on two sets, and ORing two values is similar to doing a union. Interestingly, we have preserved that in Ruby. Array has operators where you can combine arrays using set operations, and it has the single pipe, which we typically read as OR to union two arrays. I want to say it has a single AND that you can use. It's used to intersect two arrays.

SARA: I actually used that sometime within the last year, I remember.

JOËL: So, if you've ever wondered why those two particular operators to do set operations instead of a union method, now you know.

SARA: I love set operations. I recently made an update to thoughtbot's internal tool hub, and I used set unions there. [laughs]

MID-ROLL AD:

Debugging errors can be a developer’s worst nightmare...but it doesn’t have to be. Airbrake is an award-winning error monitoring, performance, and deployment tracking tool created by developers for developers that can actually help cut your debugging time in half.

So why do developers love Airbrake? It has all of the information that web developers need to monitor their application - including error management, performance insights, and deploy tracking!

Airbrake’s debugging tool catches all of your project errors, intelligently groups them, and points you to the issue in the code so you can quickly fix the bug before customers are impacted.

In addition to stellar error monitoring, Airbrake’s lightweight APM helps developers to track the performance and availability of their application through metrics like HTTP requests, response times, error occurrences, and user satisfaction.

Finally, Airbrake Deploy Tracking helps developers track trends, fix bad deploys, and improve code quality.

Since 2008, Airbrake has been a staple in the Ruby community and has grown to cover all major programming languages. Airbrake seamlessly integrates with your favorite apps to include modern features like single sign-on and SDK-based installation. From testing to production, Airbrake notifiers have your back.

Your time is valuable, so why waste it combing through logs, waiting for user reports, or retrofitting other tools to monitor your application? You literally have nothing to lose. Head on over to airbrake.io/try/bikeshed to create your FREE developer account today!

JOËL: If you had to sell a colleague on the value of discrete math, what would be the example that you would use?

SARA: What if I told you that you would never have to wonder what the results might be in a given situation of true and false?

JOËL: That's deep. Do you want to know all the secrets of the universe?

SARA: Let me introduce to you truth tables.

JOËL: Oh, I love a good truth table. Yes, such a simple tool, but it pays so much.

SARA: Absolutely, especially in a world where we have unless as an operator.

JOËL: Unless gets me so much in Ruby, especially when there are compound expressions. So you say do something unless condition one or condition two, and then I have to think, wait, when does this happen?

SARA: I have to read it to myself in English, not this and not that. [chuckles]

JOËL: So that's interesting because when you translated that in English, you changed the operator that's being used.

SARA: I totally did.

JOËL: Unless a condition or other condition. And your brain was smart enough to flip that; mine is not.

SARA: [laughs]

JOËL: But what's happening here is, and you would learn this in a discrete math class, De Morgan's Laws that say what happens when you negate compound conditions. And you have to negate each of the individual conditions and also flip all the operators, so all the ANDs turn into ORs and the ORs turn into ANDs. And so I always have to remember to do that in my mind when I see an unless or when I see someone negating a compound condition.

So now, in my mind, every time I'm reviewing code on a pull request, and I see negating a compound condition, it's just a sort of red flag for there's quite possibly a bug here. And maybe leave a comment asking the author, "Did you really mean to do this?" And like you said, maybe even write out a truth table just so that myself I know that the correct behavior is happening.

SARA: It is a good example of a code smell because if it's hard for you to understand or me to understand, sure, it made sense when it was written, but code is read more than it's written. It should be easy to read and understand. So it's definitely easy to introduce a bug at that point like you were saying, worth commenting on.

JOËL: You log on to your machine at the beginning of the day, open up a PR, and you're just like, oh yes, I love the smell of De Morgan in the morning.

SARA: [laughs] Nothing like De Morgan in your cup in the morning.

JOËL: [laughs] Yes. Oh, now I really want to --

SARA: A DeMorgan in the morgen.

[laughter]

JOËL: Now I really want to see a spoof of that Folgers ad.

SARA: [laughs] For some reason, the jingle is escaping me, but it's there.

JOËL: It's an ad for a brand of American coffee.

SARA: Yes, for those that were not in America during the '90s to see the commercial, [singing] the best part of waking up is De Morgan in your cup.

JOËL: [chuckles] That was amazing.

SARA: [laughs] Hopefully, we don't get a copyright strike for that.

[laughter]

JOËL: You know what? That is the sell for why you should learn discrete math.

SARA: Yes. What are some other ways you find discrete math around in your day-to-day life?

JOËL: I think the most practical part is working with Booleans because writing conditional code writing Boolean expressions is something that I do multiple times every day. And I think anybody who's done programming for any length of time gets some amount of intuition around working with Boolean expressions. Having spent a little bit of time studying them, you learn some patterns. You learn ways of working with them.

And a common thing that I will often see in Ruby code is people will overuse the if expression when you could have used a Boolean expression instead. So I've seen things like if condition return true, else return false, which is just identity. I've also seen more complex things which will say, "If value one is true and value two is true, return true; otherwise, return false," or some fancy things with early returns that, in the end, are just reimplementing Boolean AND.

So knowing about a little bit of basic Boolean algebra, being comfortable with combining things using AND and OR rather than just writing early returns, I think, gives a much richer toolkit and something that is much more scalable. And, of course, for those situations where there are complex conditional code, having truth tables as a tool in your back pocket is just absolutely invaluable.

SARA: 100%. When those get so complex, definitely realizing it's worth maybe breaking up a chain of Boolean logic into separate mini-methods if you need to. There's nothing like seeing a whole bunch of stuff ANDed together that are only kind of related. [laughs]

JOËL: There's a form of logic that you dig into as well called predicate logic, and there's a whole set of things you can do with it. But two things that stood out to me were these two operators that apply a condition to a whole set of values. And they either claim that a certain thing is true for at least one of the elements in a set or for every value in a set.

And the interesting thing is that if you claim that something is true for all elements, in order to falsify that claim, you only need to find one counterexample. You don't need to check every item. If I can find one, and maybe it's the first item in this set that is wrong or that contradicts the logical statement that I'm trying to make, then I've immediately disproved your entire statement because you claimed that this was true for every element.

SARA: And it's hard learning these sorts of fundamentals from computer science; it's hard to not apply that to real life and hear somebody using a statement, "Every this, all of that." I immediately come back with, "Well, some of them." [laughs] I'm that guy, yep.

JOËL: The person at the end of a conference talk who puts up their hand and says, "So this is not really a question. It's more of a statement."

SARA: [laughs] I found this one example. Yeah, I'm a stickler for specificity, for sure. Thanks, discrete math.

JOËL: It definitely helped me be much more nuanced in the way that I speak. I tend to not speak in absolutes or superlatives because of that class.

SARA: Yeah, I very frequently use the term a non-zero amount of times to describe, for example, there exists one in a set.

JOËL: There's also another interesting aspect of this, which is when you see a chain of ANDs, so condition, and condition, and condition, and condition, and condition, you're effectively making the assertion that something is true for all elements or that all these conditions are true. Therefore, it only takes one for the whole thing to evaluate to false. And I want to say the fancy name for this is annihilation, where you can have a giant chain of conditions that are ANDed together, and they're all true, but if any single one of them is false, then the whole chain evaluates to false.

SARA: And this is where you can get a little clever with the order in which you put those in your AND where you have the least heavy lifting checks first so that they fail first. Or if you have things that need to check for nil, check them after. Check the basic stuff first. Let it almost short circuit; let it fail fast, as they say.

JOËL: Yeah, these are all performance tricks that I think, even if you don't have a discrete math background, you might have picked up. You know about short-circuiting. You know about trying the cheap checks first. And now you know a little bit of the theoretical background of why.

SARA: [singing] Where do we go from here? [laughs]

JOËL: So we have these sort of logical operators that will claim that something is true for all elements of a set or at least one element of a set, and those are kind of theoretical. They're useful if we're trying to set up a logical proposition. But these exist in code, in Ruby, as part of the enumerable module. Enumerable has two methods; they are any and all. And you can use those methods to claim that all items in an array will evaluate to true when the given block runs or that at least one evaluates to true for items in that array.

SARA: What's the word where you're taking out some of a set? Slice but not slice. There's intersection [crosstalk 26:46] union, so not a set theory one, no.

JOËL: Like getting the inverse?

SARA: Maybe. I don't know.

JOËL: I feel like there's a term for getting the inverse of a set.

SARA: Not the inverse.

JOËL: Because you can get the inverse of the intersection or something.

SARA: Yeah. I think I'm just going to go along the lines of being able to slice out what you want with select and how you can then chain an enumerable on that.

JOËL: Okay. Okay, I see. So you're making a connection from enumerable to set theory.

SARA: Mm-hmm.

JOËL: Excellent.

SARA: Even if you don't necessarily want every item in your enumerable, your array, your hash, you can use things like select and reject to get a subset for a certain condition, and you can slice out based on a condition. And then you can then apply any or all to that. And so I want all of the even numbers, and now for all of these even numbers, such and such should be true for the set.

JOËL: So now we've made a connection between enumerable and predicate logic. And we've also made a connection to set theory.

SARA: It's coming full circle again. [laughs] Discrete math is everywhere.

JOËL: So if you use the enumerable module in Ruby, which you should be (It's one of the best parts of the language.), you're doing discrete math every day, and you didn't know it.

SARA: You're welcome.

JOËL: So we've seen that a lot of us are interacting with elements of discrete math every day and that learning a little bit about it more formally can help us be a bit more mindful in how we code every day. It can give us the mental models to solve and analyze problems that we encounter daily. For those listeners who might want to dig a little bit more deeply into discrete math, do you have any resources there that you recommend?

SARA: Well, not sponsored, but brilliant.org is a pretty good resource for things like math, computer science, for the very least. I'm sure it has other courses, but those are the ones that I've kind of looked at on some YouTubers' free trial. [chuckles] And I liked their approach to teaching, and I think it has got a low barrier to entry for learning these topics. I would definitely recommend that, so brilliant.org

JOËL: It's funny you mentioned that they sponsor a lot of technology, science, and math YouTubers. So for those listeners who are interested in checking it out, maybe look up some YouTubers and see if they have a free sign-up code.

SARA: Mayuko is a good YouTuber for that. I believe she gets sponsored by Brilliant occasionally. She's a software engineer out in California.

JOËL: Clearly, we're not sponsored because we don't have a code to give out.

SARA: [laughs] Sponsor us, Brilliant.

JOËL: [laughs] Host at bikeshed.fm

SARA: [laughs]

JOËL: All right. Well, with that, shall we wrap up?

SARA: Yeah, let's do.

STEPHANIE: Show notes for this episode can be found at bikeshed.fm.

JOËL: This show has been produced and edited by Mandy Moore.

STEPHANIE: If you enjoyed listening, one really easy way to support the show is to leave us a quick rating or even a review in iTunes. It really helps other folks find the show.

JOËL: If you have any feedback for this or any of our other episodes, you can reach us @_bikeshed, or you can reach me @joelquen on Twitter.

STEPHANIE: Or reach both of us at [email protected] via email.

JOËL: Thanks so much for listening to The Bike Shed, and we'll see you next week.

ALL: Byeeeeeeee!!!!!!!!

ANNOUNCER: This podcast is brought to you by thoughtbot, your expert strategy, design, development, and product management partner. We bring digital products from idea to success and teach you how because we care. Learn more at thoughtbot.com.