5 ms·

Correct NASA’s first rule isn’t absolute, it says “avoid”, but they do have a hard rule that loop (recursion) bounds must have fixed bounds, which still rules o

by dahart 2y ago

Correct NASA’s first rule isn’t absolute, it says “avoid”, but they do have a hard rule that loop (recursion) bounds must have fixed bounds, which still rules out most non-trivial recursion. > How so? Stack + function call recursion is almost always slower and more memory intensive than alternatives, not to mention risk of stack overflow, so most people who care about perf and mem will opt out anyway. Tail recursion isn’t included, because it optimizes out the function call, and tail recursion is iteration anyway. If tail recursion isn’t an option, it means a tree or multi-branch recursion, which is generally speaking difficult to reason about and difficult to bound, so error prone. People who care about safety, like NASA, avoid recursion for those reasons. I’m sure they will use recursion when it’s the only choice, or the best choice. Choice of data structure might affect whether recursion is best. > I write all my code in Prolog Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…?

YeGoblynQueenne 2y ago
What is "non-trivial" recursion? Honest question, I'm not familiar with the term. E.g. is reversing a list recursively "non-trivial"? I think the 2nd rule ("All loops must have fixed bounds. This prevents runaway code.") refers to numerical bounds, so if you take it literally it would also eliminate e.g. while loops with a boolean condition, but I don't know if that's the intention. In NASA, with very expensive equipment on the line, maybe; but for most other environments that would be an onerous requirement. In any case you can turn any recursion with non-numeric bounds to one with numeric bounds easily. You do that by adding a parameter that counts the recursion steps and exits if the count exceeds a limit. For added security, you can do this check in each "clause" (literal or figurative) of the recursive procedure, not just the boundary condition. Then you have depth-limited recursion and bobs your ankle. Or Bob is your uncle, I'm never sure about that one. >> Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…? Most of my Prolog coding has been for my PhD and post-doc research of course but I'm now in my third industry contract where I work almost exclusively with Prolog (the rest is a bit of shell scripting and the like). I don't want to say what the industry is, or the job, but as a for instance my two previous Prolog industry gigs were in an AI startup and the other working on a legacy system for management of rental car fleets, both in France two years ago. The car system was written in the '90s and it had changed many hands since then so it was a royal mess and I didn't stay long working on it but I recently spoke with one of the other devs and it's still going. There's plenty of that legacy Prolog expert system code around, all left over from the '90s, written before the winter. Sicstus, the biggest commercial Prolog vendor, used to brag on their landing page that if you've booked any air travel recently then chances are you used a Prolog-based system, which shouldn't come as a surprise. After all, every time you use online banking, you are using a system based on COBOL and running on a mainframe. That claim has recently disappeared from the Sicstus site though and I don't know what that means. Anyway Prolog coders occasionally hear about gigs working on stuff like that through the grapevine, but judging from my experience those are mainly maintained by programmers who have never seen Prolog before in their lives, until they're thrown in at the deep end an have to make do. But I see you're making a distinction between "research and education" and "production code"? Why's that? The code I write for my research is production code. I can tell you that with a straight face because I've worked in the industry many years before I did my PhD and my Prolog code is much more stable, and maintainable to boot, than 90% of the rickety, held together with bits of string and gaffer tape, "production" code I worked with as an industry code monkey. And btw I'm still a code monkey. That's what makes code "production": who writes it, not who it is for. Btw my post-doc Prolog code had to run on a robot that cost a few thousand quid (I'm in the UK) so it had to be industrial strength. I never got to test it because my funding er expired. In academia, you have to be careful who you're telling hard, technical truths to. So now I'm working in the industry.
- dahart 2y ago
  If a function calls itself exactly once, it’s a trivial recursion. Same is true if it calls itself exactly four times. If the entire problem can be reasonably inlined or “unrolled”, it’s trivial. Having to use fixed bounds and a small amount of memory might mean that all recursion is trivial. Reversing a list is a perfect example of something that is best solved without recursion. Do you really want to use as many stack frames as you have list entries? No, not really. Can you tell me off the top of your head what the limit on max list size is without looking it up for a list-reversing recursive algorithm? Yes NASA’s rule is intended to prevent loops with only boolean conditions. Everyone (i.e. people who did not write the code) should be able to know for certain by glancing at a loop whether it will finish, and fixed bounds gets you most of the way there. It is fine if you put a fixed call count on the recursion, assuming that recursion is actually the best choice. It’s just that actual recursion is almost never the actual best choice. Having a fixed call count and a fixed recursion depth nearly always suggest that the problem can be easily translated to iteration, and iteration is cheaper. Even something as simple as using a simulated stack structure to replace function calls is usually preferable to burning memory with stack frames and wasting registers and cycles passing parameters around. People who do high performance work or just care about efficiency don’t question these things. NASA’s rules aren’t weird when it comes to other organizations that do safety-critical code. Even video games, like I mentioned used to do nearly everything on NASA’s list. Embedded code on small devices still does all of this; car manufacturers follow the same rules. When memory is very small or limited, and when crashes have high consequence and are unrecoverable, the situation is completely different than a grad student sitting at a terminal. Their rules aren’t very onerous either, most of the time, they just require changing habits and thinking differently. Once you get used to them, just like with any coding practices, there are simple patterns you can follow to implement just about anything. One exercise that might(?) be fun for you is take some of your research code and port it to the smallest Arduino you can buy, and get it to run. Even if Prolog is an option on that platform, you might find that standard recursion is not. “Production code” is a fairly common/standard term (Google it and browse multiple answers) that does mean in part who it’s for. The term is meant for situations where code is usually written by teams, most often large teams, and where the code is written in service of a product, and will be run by people other than the authors of the code. Production code is not a comment on the quality of the code nor of the choice of language, but it does mean the code will be tested by a QA department and that it will be run under uncontrollable conditions by people who are not experts or coders. If you write code for your PhD and you run it yourself, it’s not production code, period, no matter how stable or high quality you believe it to be. For sure there are cases where research code and production code overlap. They are relatively rare, but you might be in that part of the Venn diagram.

by dahart 2y ago

YeGoblynQueenne 2y ago

What is "non-trivial" recursion? Honest question, I'm not familiar with the term. E.g. is reversing a list recursively "non-trivial"? I think the 2nd rule ("All loops must have fixed bounds. This prevents runaway code.") refers to numerical bounds, so if you take it literally it would also eliminate e.g. while loops with a boolean condition, but I don't know if that's the intention. In NASA, with very expensive equipment on the line, maybe; but for most other environments that would be an onerous requirement. In any case you can turn any recursion with non-numeric bounds to one with numeric bounds easily. You do that by adding a parameter that counts the recursion steps and exits if the count exceeds a limit. For added security, you can do this check in each "clause" (literal or figurative) of the recursive procedure, not just the boundary condition. Then you have depth-limited recursion and bobs your ankle. Or Bob is your uncle, I'm never sure about that one. >> Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…? Most of my Prolog coding has been for my PhD and post-doc research of course but I'm now in my third industry contract where I work almost exclusively with Prolog (the rest is a bit of shell scripting and the like). I don't want to say what the industry is, or the job, but as a for instance my two previous Prolog industry gigs were in an AI startup and the other working on a legacy system for management of rental car fleets, both in France two years ago. The car system was written in the '90s and it had changed many hands since then so it was a royal mess and I didn't stay long working on it but I recently spoke with one of the other devs and it's still going. There's plenty of that legacy Prolog expert system code around, all left over from the '90s, written before the winter. Sicstus, the biggest commercial Prolog vendor, used to brag on their landing page that if you've booked any air travel recently then chances are you used a Prolog-based system, which shouldn't come as a surprise. After all, every time you use online banking, you are using a system based on COBOL and running on a mainframe. That claim has recently disappeared from the Sicstus site though and I don't know what that means. Anyway Prolog coders occasionally hear about gigs working on stuff like that through the grapevine, but judging from my experience those are mainly maintained by programmers who have never seen Prolog before in their lives, until they're thrown in at the deep end an have to make do. But I see you're making a distinction between "research and education" and "production code"? Why's that? The code I write for my research is production code. I can tell you that with a straight face because I've worked in the industry many years before I did my PhD and my Prolog code is much more stable, and maintainable to boot, than 90% of the rickety, held together with bits of string and gaffer tape, "production" code I worked with as an industry code monkey. And btw I'm still a code monkey. That's what makes code "production": who writes it, not who it is for. Btw my post-doc Prolog code had to run on a robot that cost a few thousand quid (I'm in the UK) so it had to be industrial strength. I never got to test it because my funding er expired. In academia, you have to be careful who you're telling hard, technical truths to. So now I'm working in the industry.

dahart 2y ago
If a function calls itself exactly once, it’s a trivial recursion. Same is true if it calls itself exactly four times. If the entire problem can be reasonably inlined or “unrolled”, it’s trivial. Having to use fixed bounds and a small amount of memory might mean that all recursion is trivial. Reversing a list is a perfect example of something that is best solved without recursion. Do you really want to use as many stack frames as you have list entries? No, not really. Can you tell me off the top of your head what the limit on max list size is without looking it up for a list-reversing recursive algorithm? Yes NASA’s rule is intended to prevent loops with only boolean conditions. Everyone (i.e. people who did not write the code) should be able to know for certain by glancing at a loop whether it will finish, and fixed bounds gets you most of the way there. It is fine if you put a fixed call count on the recursion, assuming that recursion is actually the best choice. It’s just that actual recursion is almost never the actual best choice. Having a fixed call count and a fixed recursion depth nearly always suggest that the problem can be easily translated to iteration, and iteration is cheaper. Even something as simple as using a simulated stack structure to replace function calls is usually preferable to burning memory with stack frames and wasting registers and cycles passing parameters around. People who do high performance work or just care about efficiency don’t question these things. NASA’s rules aren’t weird when it comes to other organizations that do safety-critical code. Even video games, like I mentioned used to do nearly everything on NASA’s list. Embedded code on small devices still does all of this; car manufacturers follow the same rules. When memory is very small or limited, and when crashes have high consequence and are unrecoverable, the situation is completely different than a grad student sitting at a terminal. Their rules aren’t very onerous either, most of the time, they just require changing habits and thinking differently. Once you get used to them, just like with any coding practices, there are simple patterns you can follow to implement just about anything. One exercise that might(?) be fun for you is take some of your research code and port it to the smallest Arduino you can buy, and get it to run. Even if Prolog is an option on that platform, you might find that standard recursion is not. “Production code” is a fairly common/standard term (Google it and browse multiple answers) that does mean in part who it’s for. The term is meant for situations where code is usually written by teams, most often large teams, and where the code is written in service of a product, and will be run by people other than the authors of the code. Production code is not a comment on the quality of the code nor of the choice of language, but it does mean the code will be tested by a QA department and that it will be run under uncontrollable conditions by people who are not experts or coders. If you write code for your PhD and you run it yourself, it’s not production code, period, no matter how stable or high quality you believe it to be. For sure there are cases where research code and production code overlap. They are relatively rare, but you might be in that part of the Venn diagram.