Whenever somebody does an analysis of coding standards like this (see also the JSF coding standards) they always lock in on how these rules are written to enforce "correctness", but they frequently gloss over an extremely important part of what it means to be correct in a complex control system like a jet fighter or a space craft, and that is deterministic execution.
"Correct" execution doesn't just mean error free, but it also means that code needs to execute deterministically both in terms of near-complete referential transparency as well as execution time. This is what is referred to as "real time computing" in CS, a term that has recently been made homonymous by UI/UX/front-end designers to describe responsiveness in high-latency systems like the web.
All of the inferences about how these rules aid static analyzers are good and correct, but a lot of these rules are also important to achieving deterministic execution time; memory management being the big one due to its complete lack of determinism both in computation result and computation time. Sticking code in a real-time OS doesn't really matter unless the code itself is also real-time kosher.
I don't bring this up to gripe, but only bring it up because it wasn't something I was familiar with until I started working on torque controlled walking robots a few years ago where the feedback loop has a real-time constraint, and it has since taken over my life and I find it to be a very fascinating aspect of computer science that almost nobody ever talks about. Achieving real-time deadlines in a program can be quite challenging and very often making something "faster" than its deadline is not even close to the same thing as making sure it always makes its deadline. It really changes the way you think about performance, execution time, program optimization, etc.
... referred to as "real time computing" in CS, a term that has recently been made homonymous by UI/UX/front-end designers to describe responsiveness ...
And to add to the confusion, the term "responsive" was co-opted to mean "adaptive layout".
So now it's perfectly possible to have this conversation:
- This site is not responsive.
- Sure it is, try resizing your browser.
- No, I mean that it takes too long to react to user input.
- Oh, you mean it should be real time?
- No, nothing even close to real time -- I'd be happy if something happened in less than 1 second when I click this button...
Right, 'real-time' vs. 'real-fast'. Control systems for electro-mechanical devices is the primary domain for this type of software. It is required for any motion control where missing a timing mark can cause an undesired physical event. Imagine a walking robot that missed a motor position adjustment during garbage collection. It might mean the robot itself is headed to the garbage ;-)
I always thought the traditional distinguishing terms here were "hard realtime" (e.g. control software) versus "soft realtime" (e.g. games). Are those not widely used any more?
They are used, but hard vs. soft realtime is tangential to the broader discussion here.
If we stick with the video game example, it has a real time goal: having frames displayed at the target framerate. The "soft" aspect comes from the fact it's tolerable for a game to fail some deadlines. It's certainly undesirable, but a few minutes of frame-y gameplay is not game-breaking.
Depending on the particular system, there will be tolerances of how frequently and in which ways a realtime deadline can be missed without constituting an overall failure of the system.
Hard, Firm, and Soft real-time are all classifications in real-time computing. They are measurements of how detrimental it is to the system if they miss a deadline. Control systems can still be soft real-time.
And those terms may be used not to refer to the system as a whole, but particular tasks within it. Hard constraints on tasks that can never miss a (often nanosecond resolution) time point, firm real-time that can't be missed but which can be delayed, soft real time that can be missed (but only a certain number or percentage of times, or can't be missed twice in a row, etc). Different systems and teams may use those categories differently. For example, the AGC alarms that nearly caused the Apollo 11 Eagle landing to abort were for tasks in the last category, so they were able to continue. There were other tasks on that same real-time system for which missing the timing would have required an abort (or triggered a lot of very loud noises followed by silence).
Correct. Real time doesn't mean "as fast as possible" in embedded systems. It can mean anything from "within a specified time after a given condition is met" to "it must happen at precisely this time, every time, after this condition is met" and a bunch of permutations between and outside those two.
The idea of deterministic jitter might be foreign to those who've never done real time embedded work. By this I mean the idea that, for example, a certain output or result is specified to happen at 100us +/- 1.2us from a condition being met. Here +/- 1.2us being the acceptable response jitter. Very often you find yourself using NOP's to balance both sides of a conditional in machine language in order to control jitter.
From experience I'd say that the exact definition of "real time" is project dependent. This definition is very different in, for example, a control panel processor vs. a 5 axis milling machine capable of rigid tapping.
I had my first exposure to this "deterministic" execution concept when I was writing the data collection part of a computer-based electrocardiogram interpretation service. the ECG cart hooked up to the patient at a hospital somewhere in the US would call our service located near Chicago. The front end would answer the phone and present three analog signals to the analog to digital converter which would sample each channel every 2 milliseconds, and write chunks of digitized samples to disk.
The trick was we noticed that the OS (RBM or Real-Time Batch Monitor from SDS, later Xerox) would mask all interrupts for short periods of time. This would delay the timer interrupt by an amount that would lead to an error in the voltage read (e.g., the rapid upward spike of the QRS wave) that would be significantly more than the quantization error.
Thus, with each release of the OS, I would have to track down the instructions that would mask the three classes of interrupts, and change the code so as not to mask the timer interrupt. This was, of course, delivered in a form of 80 column cards.
Not everyone gets to work on problems of this sort. To adapt the NASA list to JS seems a bit of a stretch.
Could you go into more detail on where I could learn more about this / where I could work on such types of systems? (outside of high frequency trading)?
I've started working on similar types of technology recently, but purely by wandering into it by accident.
I don't really know of any good general resources; they're often pegged to a specific programming language because the ways in which you have to achieve real-time compatibility differ depending on how the language and its runtime behave. We do all of our work in Java, which is definitely not a great candidate for real-time in most cases, so a lot of what I've learned about real-time programming has come from having to wrangle the JVM in to doing what we need it to do.
The fields that come to mind when I think of real-time outside of HFT, though, are control systems and digital signal processing (DSP). While DSP doesn't necessarily need to be real-time if you're doing it for analysis, doing DSP live definitely requires real-time programming knowledge since signals are often expressed in the time domain and any delay in computation of a discrete element will propagate in how the signal is interpreted. For example, if the signal you're processing is a sound signal (like music), and you are doing software-based DSP on the signal before it reaches the playback device, it better be real-time or any delay spikes will ruin the playback. This is why OS X is so popular with the music industry and especially DJ's; the Mach kernel has really good real-time support and a pretty good real-time software based DSP library for building apps.
We have some contacts at Aicas, and we've used both the original RTSJ in the past as well as evaluating Jamaica. Myself and a colleague recently attended JTRES and spoke to Dr. Hunt about where Aicas fell short for our specific use case, and in the very near term it won't be usable for us. We're looking in to re-evaluating it around summertime.
Most of these things I do on a regular basis, but #7 sounds rather stressing and code cluttering to me. Maybe these new Proxies of ES6 could ease that pain.
"but what is wrong with recursion? Why NASA guidelines prescribe to avoid simple technique we were studying as early as in school? The reason for that is static code analyzers NASA use to reduce the chance for error. Recursions make code less predictable for them. JavaScript tools do not have such a precept so what we can take out of this rule?"
This is of course, wrong. Javascript has not solved the problem of making recursion easy or sane to analyze. It is quite literally the same problem you have with C.
In fact, most javascript tools are way less useful at recursion analysis (IE they produce a much higher rate of false positives) than C tools.
"9.The use of pointers should be restricted. Specifically, no more than one level of dereferencing is allowed. Function pointers are not permitted.
This is the rule JavaScript developer can not get anything from.
"
Except that javascript developers use function pointers like they were going out of style ...
I suspect issue isn't that recursion is hard to analyze, but that non-tail-call-optimized recursion has unbounded memory usage.
In fact, what makes you say that recursion is difficult to analyze? Inductive proofs over recursive algorithms are generally much nicer than proofs over iterative algorithms.
"In fact, what makes you say that recursion is difficult to analyze? Inductive proofs over recursive algorithms are generally much nicer than proofs over iterative algorithms."
For static analysis purposes, it is not great.
Particularly if it is inside conditionals.
Either you eat exponential path blowup (assuming bounded recursion and context-sensitivity) and fix-point it, or collapse the whole call graph cycle starting at the recursion into a single result (which generates false positives).
This assumes a single-thread.
Concurrent javascript code, with recursion, does not even have a decidable reachability problem, which makes it very difficult to get good answers.
Suffice to say, what is easy/hard for humans to prove is not the same as computers.
You would have a much harder time getting good static analysis results from a recursive fibonacci function than an iterative one (and this is simple tail recursion)
Exactly right. Recursion is the easiest way to blow up the stack (with alloca a distant second). NASA stacks tend to be small, static, and can produce physical harm when damaged.
Why avoid recursion entirely? Because it's too easy for another programmer to accidentally convert tail-call optimized recursion into full recursion. That mistake is harder to make on code written as a loop.
You nailed it. Tail calls have constant memory footprints, non-tail-call recursion (assuming the language runtime and/or compiler are able to recognize these situations and convert the tailcall into an adjustment of the variables in scope in the current stack frame followed by a jump).
If we'd be worried about our ability to analyze these then we wouldn't be able to optimize away that special case to begin with.
I do find that to my imperatively trained eyes it always screams 'stack overflow' at me and then I have to remind myself that will be optimized away.
It'd be nice if environments that provide tail call optimizations could be set to fail compilation if any non-tail-call recursion is detected.
"If we'd be worried about our ability to analyze these then we wouldn't be able to optimize away that special case to begin with.
"
Most compilers require you tell them, specifically, that it can tail call everything, before it will do it (i'm talking more about GCC and LLVM here, which are generic compiler frameworks). It will do some tail call optimization, but only fairly basic cases, exactly because it can't analyze what will happen.
Exactly. I create an array of functions one week ago. Not that it's usual: I had to google how to .call() them :-)
Anyway, .call is pretty much used inside many libraries. I just checked the ones in a project I'm working on. It's in jquery, bootstrap, store.js
"Why NASA guidelines prescribe to avoid simple technique we were studying as early as in school?"
Because recursion in the languages they are using involves allocating stack frames for the recursion, which means they can't predict stack depth, which means they can't predict the amount of memory the stack will consume, which means they may run out of memory, which means their spaceship may be destroyed.
Which, incidentally, here on step two indicates why the NASA standards are from such a different world from the web browser that they don't much matter. Now, I'm not saying that memory use doesn't matter, just go nuts, but JS is generally running in an environment with wildly more memory than those restrictions were meant for (yes, even on cell phones nowadays), and generally you're looking at "annoying a user and they go away" being the worst case rather than "losing a billion-dollar spacecraft".
JS is not even capable of following #3 about memory allocation.
NASA: "6. Data objects must be declared at the smallest possible level of scope."
Commentary: "This rule have simple intention behind – to keep data in private scope and avoid unauthorized access. Sounds generic, smart and easy to follow."
No, that's not what that rule is for. By keeping the data objects at the smallest possible scope level, it makes it as likely as possible that it can be stack-allocated, which means the lifetime of the object can be easily understood, guaranteed not to proliferate due to a leak (see rule about not recursing), etc. Again, this has little to do with a language that decides for you whether it will stack or heap allocate.
#8, again, has nothing to do with Javascript.
"When started to write this article I could not imagine how much web world could get from NASA and how much is similar."
No, it really isn't. Unfortunately, and I don't know how to effectively soften this, you don't understand enough about their world to understand what the rules are for, so you brought your own conceptions about JS to what the rules were saying. In fact they're really specific to a certain type of resource-restricted real-time programming that has very little to do with a web browser, and which you could not follow with JS even if you somehow wanted to, and for those you could, the cost/benefit tradeoff for following NASA's suggestions are awful. If you're interested in improving your JS quality, focus on more extensive automated testing, focus on more profiling, and focus on general software engineering principles like single-responsibility and DRY. Don't even worry about these rules.
> Because recursion in the languages they are using involves allocating stack frames for the recursion, which means they can't predict stack depth, which means they can't predict the amount of memory the stack will consume, which means they may run out of memory, which means their spaceship may be destroyed.
Thank you. It is trivial to turn a recursive function into a loop. Trivial especially compared to running through all the stack space (1MB on Windows) and crashing the process in some runtime environments[1]. Or your space ship. Either way: recursion belongs in academics. I don't care if you are using JS or ASM, learn how to avoid using it.
> Manage your variables with respect. Regularize variables declaration by putting them in the top of scope
That really isn't what is meant by "Do not use dynamic memory allocation after initialization." Memory is allocated on the stack the second you enter the frame, no matter where you declare the variable. That is a style recommendation.
> JS is not even capable of following #3 about memory allocation.
Not to mention that the wrong definition of a GC is used.
> I don't care if you are using JS or ASM, learn how to avoid using it.
It's a bad idea for a class of languages. Functional languages implementing TCO are a different kettle of fish (especially if your function is tail-recursive). It's an extremely common pattern in these languages.
Indeed, however, understanding why it's a bad idea in imperative languages is important when using functional languages. You have to know how what qualifies a function as tail-recursive (and why that is important). You'll only learn that from experience with both classes of languages and most importantly, getting burned due to abusing the stack.
I'd rather people learn from the other direction, you know? I'm not sure how that would be implemented, but I see recursion abuse far too often and few seem to understand how that could be a bad thing.
All those crash prone (not!) Ericsson phone switches beg to differ.
Recursion does not belong just in Academics. But just like any other tool it requires some level of understanding and when you use it naively it will bite you. To avoid such complications NASA attempts to get rid of the problem entirely. But when properly used recursion has its place, provided both the language and the programmer are aware of its limitations and pitfalls.
> Which, incidentally, here on step two indicates why the NASA standards are from such a different world from the web browser that they don't much matter.
Other than the mention of recursion, everything else is about predictable and visible program flow. If you were to carry this forward to JavaScript you would want to avoid `throw` for application control for example.
I agree with you, but I don't think it's a bad exercise at all to apply the rules to a different domain and see how they make you feel. If they challenge your assumptions, why? What are your assumptions based on?
Creating a framework within which to challenge your assumptions can be useful.
"focus on more extensive automated testing, focus on more profiling, and focus on general software engineering principles like single-responsibility and DRY" - this is exactly what was suggested in article. Except may be DRY which is more about design.
Of course the article wasn't suggesting manual testing and avoid profiling, but it MOSTLY recommended techniques and tips that do not apply to the web. That's what jerf spent three paragraphs outlining.
Any help on making text better is appreciated. Blogspam... May be, but consider that PDF were published a long time ago and not that many Web people were interested until there came a way to use it in everyday practice.
I can tell you put a lot of effort into the article. Heck, it got a decent amount of upvotes - which is a good thing. Thing is, there are a few veterans hanging around here. They're really don't take factual errors lightly. I have had my run-ins with them too.
Your first mistake?
> web people
You are not web people. You are a developer. Broaden your horizons and stop restricting your experience to the microcosm that is JS and the web in general. Once you do that you'll start to understand why the folks here have some issues with some of the suggestions you put forward.
Avoiding dynamic memory allocation and recursion are typical rules for embedded scenarios, where programs run in safety critical contexts on tiny microcontrollers. These rules are not for easy static analyzation but for having a deterministic memory usage. In the best case one where you can proof that your application will in no state exceed the available memory. Similar rules are also enforced in automotive scenarios.
Allowing recursion allows to blow the stack. Allowing malloc/free might blow the heap. Even when it does not do it immediatly it might do it over time due to heap fragmentation.
Really depends on your language. Also, I find (though rarely) that it sometimes help to keep most of the pieces of a given algorithm in the same place rather than splitting it in small functions.
I really like this. I especially like how the author(s?) didn't make the Assertions -> Unit Tests leap. Assertions are much more powerful, even if they aren't executed in production.
I feel like a few of these are glossed over. #7 implies that error conditions should be handled. #8 precludes transcompilers since they are also just glorified preprocessors. #10 means use "use strict"
yeah I agree #8 in particular should elicit a lot more debate in the js community. Back when I used to be into RoR I would get a ton of flack in interviews for writing pure js rather than Coffeescript, pure css rather than Sass.
There are legitimate cases where a pre-processor is useful (Coffeescript demos show several cases where a lot of code can be simplified) but unless you are writing a math/list-heavy app, I feel these advantages don't apply so much. I don't perceive a need for these tools in most projects that are about dom manipulation, it can instead be achieved through pure libs (jQuery) which will eliminate a build step and should allow for some easier testing.
This is a fundamental programming debate that I don't see a lot of discussion of... since I like CLojure I see some talk of how "transparent" it is as a wrapper over JVM types but a lot of the pre-processor style of transcompilers gloss over this idea (I guess just preferring 2 independent stages of static/lint analysis?).
Firstly, I don't pool LESS/SASS with Coffescript and the like because CSS is a content description language, not a programming language, though as someone who is an expert on none of the above, I would hear arguments against them.
Secondly, most people wouldn't. If someone is using Coffeescript they don't want to hear that they shouldn't be using Coffeescript because they want to use Coffeescript, and most people (and in 2014 "most programmers" are a microcosm of "most people") don't like listening to opinions that deviate from their own. All of the "great" parts of Coffeescript can be implemented in JavaScript with a library like underscore.
Clojure is a bit different since it is interacting directly with the JVM.
good points, but yeah the reason i lump them together (even though I agree that C preprocessors vs. css vs. js vs. jvm abstraction are obviously very different technologies) is that in the context of this discussion, i see them as a layer of abstraction that basically mangles the ability for code analysis (whether it be static or in debugging) to happen in a way that feels comprehensive
for some technologies this is being alleviated with source maps, but it still feels like over-complication when there are library alternatives available (Underscore, as you point out). Because when it comes down to it you will need to debug & understand some language paradigms/quirks of the language you are transcompiling to, so it would behoove the developer to be as fluent in the target language as possible (& of course, coding natively in it to begin with promotes fluency...)
as the tools become stronger the danger disappears, yet the base language has simultaneously matured to the point where this extra technology may be nearing obsolescence... i understand in js there is some lag with web standards boards etc., but taking Java as an example, annotations and other language functions were added while simultaneously the libraries/containers (web frameworks, Spring, EE) got more powerful. It is a pretty strong & mature toolset probably mainly due to the language evolution always being forced back toward the core.
From the limited amount I know, the other JVM languages are implemented against the JVM spec which is matured in a similar way, thus facilitating easier implementation of language features & interoperability.
This was done by default in QuakeC (a pretty great DSL I think). I was amazed the first time I made an infinite loop and it detected it. (It stopped after a large number of iterations, maybe 10000).
"9.The use of pointers should be restricted. Specifically, no more than one level of dereferencing is allowed. Function pointers are not permitted."
I disagree that JS developers can't get anything out of this. The rule clearly states that first-class functions (function pointers in C) should not be used. Whether that's a good or bad idea to follow is another matter, but the author's interpretation that it doesn't apply to JS is wrong. IMO, it's likely to reduce complexity and bugs quite a bit so it seems like the rule should be generally followed if one follows the rest of the rules, despite giving up such a powerful and flexible feature.
Once again this has more to do with the idea that everything must be deterministic. Using a pointer when it's not absolutely needed is just one more place where a non-deterministic runtime issue can crop up.
Perhaps I'm misunderstanding you, but it sounds like you're saying that you'll reduce complexity by avoiding jquery, underscore, and half of the built in API. This is the opposite of my experience.
Implying that execution complexity is increased? Is a function not dynaically bound at the last moment anyway, regardless of how it is called? Where is the increased complexity?
Yes. Every time you introduce a new library, the deterministic nature of a system is challenged. It's kind of a silly point, though - the browser itself introduces more execution complexity than any JavaScript library could.
Oh, I see what you mean now. I was referring to those libraries as an example of a useful application of the pattern. My point was, if you disallow passing functions, you disallow those patterns.
"Correct" execution doesn't just mean error free, but it also means that code needs to execute deterministically both in terms of near-complete referential transparency as well as execution time. This is what is referred to as "real time computing" in CS, a term that has recently been made homonymous by UI/UX/front-end designers to describe responsiveness in high-latency systems like the web.
All of the inferences about how these rules aid static analyzers are good and correct, but a lot of these rules are also important to achieving deterministic execution time; memory management being the big one due to its complete lack of determinism both in computation result and computation time. Sticking code in a real-time OS doesn't really matter unless the code itself is also real-time kosher.
I don't bring this up to gripe, but only bring it up because it wasn't something I was familiar with until I started working on torque controlled walking robots a few years ago where the feedback loop has a real-time constraint, and it has since taken over my life and I find it to be a very fascinating aspect of computer science that almost nobody ever talks about. Achieving real-time deadlines in a program can be quite challenging and very often making something "faster" than its deadline is not even close to the same thing as making sure it always makes its deadline. It really changes the way you think about performance, execution time, program optimization, etc.