4 ms·
To relate this topic back to Computer Science and Math, the linked list traversal problem can be related back to Proof by Induction -- There's a base case (a st
by bfung 6y ago
To relate this topic back to Computer Science and Math, the linked list traversal problem can be related back to Proof by Induction -- There's a base case (a starting condition) and then the inductive steps: "...proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1"
We can prove using proof by induction that Linus's implementation works because of the base case "indirect = &head", and the inductive step which is the rest of the program.
It'd take a lot more work to mathematically prove that the branching program "works" due to the if statement -- you'd have to construct a proof of each branch and prove that the combination works.
I'm not a mathematician, but this was a major point in CS courses at university. Being able to prove an algorithm works can extend into automated program checking / auditing, etc.
It's not just "taste" -- there's a lot of practical theory to be applied.
https://en.wikipedia.org/wiki/Mathematical_induction https://en.wikipedia.org/wiki/Mathematical_induction
- landhar 6y agoI think this hits the nail in the head. Lots of comments here seem to dislike option 2 on the basis that it’s a “clever trick” and that those should be avoided for reasons of readability and maintainability. But this second approach would be the _right_ answer in a exam about algorithms, and that’s what Linus is really hinting at here.
- Rexxar 6y agoIndeed. It also show us that using "good taste" or "code smell" arguments are wrong because there should always be good technical reason to justify the choice. Sometimes we have the good intuition and the technical is hard to express but we have to try understand why we think something is good taste and express it in a technical way. Arguments on good taste will always finish in ego fight when people disagree.