4 ms·

Ask HN: What are some non-intuitive but useful CS facts in programming?

23 points by akkad33 3y ago

mikewarot 3y ago
A computer program is a theory of how to solve a problem, written by humans, in a format readable by machine. Most of the time, it will be humans doing the reading, the compiler only sees it sporadically. The run-time executable is a crystallization of the source code, freezing its structure for all time. (In the ideal case) Since the audience is mostly human, write for them. Future you, who has forgotten the context, will likely be the largest fraction of that audience, be kind to them.
- Cerium 3y ago
  Yep, past self was an asshole. Working on the same code base for an extended time is great since there are plenty of humbling instances where you go "wtf" and git blame only to find your own name.
  - hnfong 3y ago
    Yeah, this is not precisely a "CS fact", but "you will git-blame a piece of shitty code and find a N-year old commit with your own name on it" is probably an unintuitive fact of programming that you only get to experience when you have a couple solid years under your belt.
SillyUsername 3y ago
Don't get stuck in code optimising it. Typically the few ms you gain using a hash Vs an if/else is negligible to the read/write operation over a network or db that you may also have. Optimise those instead with a cache and/or CQRS. I've had quite a few junior devs ask me the above, so it's not always intuitive.
ashton314 3y ago
Types correspond to propositions in formal logic, and programs satisfying that type are proofs of those theorems. This is called the Curry-Howard Correspondence. That might not sound particularly interesting, but here’s one of the ramifications: if you need to prove that your program follows some spec for eg avionics software or reactor control software, then one tack is to encode that protocol/spec in a type (usually an extremely expressive type system called a “dependent type” system) then you can prove a program correct to that spec and generate a program that is correct by construction. This has been done. There’s a C compiler called CompCert where the optimization passes have been proven to not alter the meaning of the program. A tool called CSmith was used to fuzz gcc, clang, and CompCert and found dozens of bugs—but none in CompCert.
- compacct27 3y ago
  It's been amazing learning about this. From "The Little Typer" book to Computerphile's videos on dependent (and homotopy, somewhat related?) type theory, to discovering Lean for interactive (math) proof construction, the history of it all dating back to Bertrand Russel trying to explain math from first principles, just wow. So lucky to live in a world where this is true.
- akkad33 3y ago
  Can this me applied to everyday software development to ensure correctness? If so do you know of any resources on this?
082349872349872 3y ago
Looking up a small key in a table to get a value is easy. Looking up a big key can be done by looking up part of the key to get a second lookup table, in which the rest of the key is then looked up to get the value. If the set of values is finite, the set of keys can be infinite by using a suitable graph of lookup tables. (this /!\ is the non-intuitive step) If one can find a suitable compact set of functions, it's even possible to "look up" an infinite set of values: look up the right function for the key, then apply it to produce the corresponding value.
laszlojamf 3y ago
1. Anonymizing PII data is way harder than you first might think. 2. Users will do _anything_ you let them do 3. The customer almost never knows what they actually want
- rrr_oh_man 3y ago
  3b. But it's definitely not that!
  - red-iron-pine 3y ago
    but only after you build to that, and they don't stop you for 3+ months.
mikewarot 3y ago
When you introduce threading or multiple processors, you change the laws of physics for software. You remove causality, this is not a trivial matter.
jeffrallen 3y ago
No matter how many debug printfs you add to a program, they won't help you if you're editing a different copy than you are running. You will make this mistake and you will learn from it, but even reading this warning will not teach you, you must make the mistake yourself. If you are lucky, you'll lose only an hour. If not you'll lose a week.
jeffrallen 3y ago
It's never a compiler bug. Until it is. Unless it's a hardware bug instead.
- 082349872349872 3y ago
  Corollary: there are 0000 0010 types of programmers — those who have never had to use an oscope for debugging, and those who have.
aristofun 3y ago
Real world programming is not a math. Real world challenges are not theorems. Anyone who tries to fit it into narrow math concepts thinks he’s doing good, because math looks beautiful and intuitively beautiful == good. But in reality (counter intuitive point) any formal and rigid system creates pain and suffering down the line when real programmers try apply those beautiful systems to real world _ugly_ problems. One good example of such an overengineering is a Scala language. Its features and elaborate typing system looks great on paper and artificial examples.
- ashton314 3y ago
  Do you have anything to support the claims you've made here?
  - aristofun 3y ago
    yes, Flink is dumping scala support and returning back to Java just one of few such decisions in big projects I know of https://cwiki.apache.org/confluence/display/FLINK/FLIP-265+Deprecate+and+remove+Scala+API+support https://cwiki.apache.org/confluence/display/FLINK/FLIP-265+D... others I can't mention because not sure if I break NDA... And if you work with scala on a big enough project - you'd know yourself the kind of pain I mean here. Everything else in my comment is just a common sense (do you need any prove that the world is an "ugly" complex system that doesn't fit perfect math or functional programming picture?)
    - akkad33 3y ago
      What about all those big projects like spark that use Scala ? Just because one company dropped Scala does not prove anything
      - aristofun 3y ago
        Flink also is one of those big projects. Im not proving anything. Im just giving examples of problems. If scala were that good - wed see more and more people migrating to it. But it’s not the case - more and more teams prefer good old java (with all its own problems and legacy).
hnfong 3y ago
1. https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem It feels the CAP theorem was more talked-about in the years of NoSQL frenzy. It is of course still highly relevant. Despite being widely known and discussed, I think it fits the "non-intuitive" description because most people really want systems to have all three (consistency, availability and partition tolerance). 2. Buridan’s Principle ( http://lamport.azurewebsites.net/pubs/buridan.pdf http://lamport.azurewebsites.net/pubs/buridan.pdf ) - A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time. This is more of a "philosophical" principle, but if you read the paper it does have practical implications.
- red-iron-pine 3y ago
  > CAP theorem the "eventual consistency" thing is what really threw me. Weak Consistency may actually be a good thing? go figure...
spdustin 3y ago
When you train your mind to see the real world around you as lists of things that you can organize (and lists of lists, etc.—it's lists all the way down), more and more of your programming tasks become intuitive. It even leads to understanding functional programming, mutability, referential passing, OOP. You discover that many terrible programming analogies actually aren't terrible at all because you intuit their application better than with the analogy alone. Why? Because CS is filled with practicable patterns that have real-world counterparts, and your brain synthesizes the complexities of the real world in myriad ways that just programming never could.
deleted 3y ago
[deleted]
rlupi 3y ago
Well-known fact: Software architecture often follows team structure, or vice versa. Why? It happens because we organize both our software and our teams based on the amount of coordination needed to succeed. Corollary: if the rates of change in your domains are accelerating and you start to accrue tech debt and cannot keep up, look for missing abstractions and the need to refactor both/either your software and/or your orgs. This tend to happen in glue roles (e.g. SRE, security), that sit at the crossroads of multiple efforts. Platform engineering is sometimes the solution for the org problems, but it requires all software components to present the same interface.
sgillen 3y ago
Floating point math is not associative, (x+y)+z != x+(y+z). Most of the time the difference is small, but in some cases not (I.E. x = 1e30, y = -1e30 and z = 1, it is 1 in the former case, 0 in the latter). Modern compilers will reorder operations depending on a whole host of factors, and this means in general unless you really go out of your way, floating point math may not even be deterministic! I've seen this happen during certain optimization algorithms, completely different results on different machines even with the same random seed and confirmed same random sequence of numbers, it was because of the floating point reordering! https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.h...

23 points by akkad33 3y ago

A computer program is a theory of how to solve a problem, written by humans, in a format readable by machine. Most of the time, it will be humans doing the reading, the compiler only sees it sporadically. The run-time executable is a crystallization of the source code, freezing its structure for all time. (In the ideal case) Since the audience is mostly human, write for them. Future you, who has forgotten the context, will likely be the largest fraction of that audience, be kind to them.

Cerium 3y ago
Yep, past self was an asshole. Working on the same code base for an extended time is great since there are plenty of humbling instances where you go "wtf" and git blame only to find your own name.
- hnfong 3y ago
  Yeah, this is not precisely a "CS fact", but "you will git-blame a piece of shitty code and find a N-year old commit with your own name on it" is probably an unintuitive fact of programming that you only get to experience when you have a couple solid years under your belt.

SillyUsername 3y ago

Don't get stuck in code optimising it. Typically the few ms you gain using a hash Vs an if/else is negligible to the read/write operation over a network or db that you may also have. Optimise those instead with a cache and/or CQRS. I've had quite a few junior devs ask me the above, so it's not always intuitive.

ashton314 3y ago

Types correspond to propositions in formal logic, and programs satisfying that type are proofs of those theorems. This is called the Curry-Howard Correspondence. That might not sound particularly interesting, but here’s one of the ramifications: if you need to prove that your program follows some spec for eg avionics software or reactor control software, then one tack is to encode that protocol/spec in a type (usually an extremely expressive type system called a “dependent type” system) then you can prove a program correct to that spec and generate a program that is correct by construction. This has been done. There’s a C compiler called CompCert where the optimization passes have been proven to not alter the meaning of the program. A tool called CSmith was used to fuzz gcc, clang, and CompCert and found dozens of bugs—but none in CompCert.

compacct27 3y ago
It's been amazing learning about this. From "The Little Typer" book to Computerphile's videos on dependent (and homotopy, somewhat related?) type theory, to discovering Lean for interactive (math) proof construction, the history of it all dating back to Bertrand Russel trying to explain math from first principles, just wow. So lucky to live in a world where this is true.
akkad33 3y ago
Can this me applied to everyday software development to ensure correctness? If so do you know of any resources on this?

082349872349872 3y ago

Looking up a small key in a table to get a value is easy. Looking up a big key can be done by looking up part of the key to get a second lookup table, in which the rest of the key is then looked up to get the value. If the set of values is finite, the set of keys can be infinite by using a suitable graph of lookup tables. (this /!\ is the non-intuitive step) If one can find a suitable compact set of functions, it's even possible to "look up" an infinite set of values: look up the right function for the key, then apply it to produce the corresponding value.

laszlojamf 3y ago

1. Anonymizing PII data is way harder than you first might think. 2. Users will do _anything_ you let them do 3. The customer almost never knows what they actually want

rrr_oh_man 3y ago
3b. But it's definitely not that!
- red-iron-pine 3y ago
  but only after you build to that, and they don't stop you for 3+ months.

mikewarot 3y ago

When you introduce threading or multiple processors, you change the laws of physics for software. You remove causality, this is not a trivial matter.

jeffrallen 3y ago

No matter how many debug printfs you add to a program, they won't help you if you're editing a different copy than you are running. You will make this mistake and you will learn from it, but even reading this warning will not teach you, you must make the mistake yourself. If you are lucky, you'll lose only an hour. If not you'll lose a week.

jeffrallen 3y ago

It's never a compiler bug. Until it is. Unless it's a hardware bug instead.

082349872349872 3y ago
Corollary: there are 0000 0010 types of programmers — those who have never had to use an oscope for debugging, and those who have.

aristofun 3y ago

Real world programming is not a math. Real world challenges are not theorems. Anyone who tries to fit it into narrow math concepts thinks he’s doing good, because math looks beautiful and intuitively beautiful == good. But in reality (counter intuitive point) any formal and rigid system creates pain and suffering down the line when real programmers try apply those beautiful systems to real world _ugly_ problems. One good example of such an overengineering is a Scala language. Its features and elaborate typing system looks great on paper and artificial examples.

ashton314 3y ago
Do you have anything to support the claims you've made here?
- aristofun 3y ago
  yes, Flink is dumping scala support and returning back to Java just one of few such decisions in big projects I know of https://cwiki.apache.org/confluence/display/FLINK/FLIP-265+Deprecate+and+remove+Scala+API+support https://cwiki.apache.org/confluence/display/FLINK/FLIP-265+D... others I can't mention because not sure if I break NDA... And if you work with scala on a big enough project - you'd know yourself the kind of pain I mean here. Everything else in my comment is just a common sense (do you need any prove that the world is an "ugly" complex system that doesn't fit perfect math or functional programming picture?)
  - akkad33 3y ago
    What about all those big projects like spark that use Scala ? Just because one company dropped Scala does not prove anything
    - aristofun 3y ago
      Flink also is one of those big projects. Im not proving anything. Im just giving examples of problems. If scala were that good - wed see more and more people migrating to it. But it’s not the case - more and more teams prefer good old java (with all its own problems and legacy).

hnfong 3y ago

1. https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem It feels the CAP theorem was more talked-about in the years of NoSQL frenzy. It is of course still highly relevant. Despite being widely known and discussed, I think it fits the "non-intuitive" description because most people really want systems to have all three (consistency, availability and partition tolerance). 2. Buridan’s Principle ( http://lamport.azurewebsites.net/pubs/buridan.pdf http://lamport.azurewebsites.net/pubs/buridan.pdf ) - A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time. This is more of a "philosophical" principle, but if you read the paper it does have practical implications.

red-iron-pine 3y ago
> CAP theorem the "eventual consistency" thing is what really threw me. Weak Consistency may actually be a good thing? go figure...

spdustin 3y ago

When you train your mind to see the real world around you as lists of things that you can organize (and lists of lists, etc.—it's lists all the way down), more and more of your programming tasks become intuitive. It even leads to understanding functional programming, mutability, referential passing, OOP. You discover that many terrible programming analogies actually aren't terrible at all because you intuit their application better than with the analogy alone. Why? Because CS is filled with practicable patterns that have real-world counterparts, and your brain synthesizes the complexities of the real world in myriad ways that just programming never could.

deleted 3y ago

[deleted]

rlupi 3y ago

Well-known fact: Software architecture often follows team structure, or vice versa. Why? It happens because we organize both our software and our teams based on the amount of coordination needed to succeed. Corollary: if the rates of change in your domains are accelerating and you start to accrue tech debt and cannot keep up, look for missing abstractions and the need to refactor both/either your software and/or your orgs. This tend to happen in glue roles (e.g. SRE, security), that sit at the crossroads of multiple efforts. Platform engineering is sometimes the solution for the org problems, but it requires all software components to present the same interface.

sgillen 3y ago

Floating point math is not associative, (x+y)+z != x+(y+z). Most of the time the difference is small, but in some cases not (I.E. x = 1e30, y = -1e30 and z = 1, it is 1 in the former case, 0 in the latter). Modern compilers will reorder operations depending on a whole host of factors, and this means in general unless you really go out of your way, floating point math may not even be deterministic! I've seen this happen during certain optimization algorithms, completely different results on different machines even with the same random seed and confirmed same random sequence of numbers, it was because of the floating point reordering! https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.h...