3 ms·
Good question. One hacky way of detecting TCO could be to cause a stack overflow: var supportsTco = false; try { (function rec(n) { if(n) rec(n - 1) })
by epidemian 11y ago
Good question. One hacky way of detecting TCO could be to cause a stack overflow:
var supportsTco = false;
try {
(function rec(n) { if(n) rec(n - 1) })(20000);
supportsTco = true;
}
catch (e) { /* Ignore stack overflow error */ }
This works for me on Firefox and Chrome (by "works" i mean it doesn't, because no browser implements TCO yet, but the code detects it). But it's not bullet-proof: it would fail on a JS runtime with no TCO but a higher stack size limit, or on a runtime that detects this specific case of recursion and optimizes into a loop (or completely eliminates the innocuous function call).
A side-question: does anybody else feel that stack overflows just don't belong in high level languages? I mean, most high level languages remove the distinction between stack-allocated values and heap-allocated ones: it's all references. It doesn't make sense to worry about whether a Ruby (or JS, or Python, etc) object lives on the heap or on the stack. But yet, you still have to worry about the function call stack on these languages, and they all have tiny limits (in the order of the thousands stack frames) compared to the heap size limit.
Wouldn't it be possible for a language to make the stack grow without an arbitrary limit (besides the limit of physical memory)? And if so, why do these high level languages that focus on ease of use not implement the stack that way?
- chimeracoder 11y ago> One hacky way of detecting TCO could be to cause a stack overflow You can do this to test your own browser, but it's rather pointless in practice unless you can do it at runtime without crashing the browser or causing it to become unresponsive. Otherwise, you'll have to manually keep track of which (browser, version) combination supports it and which ones don't. > Wouldn't it be possible for a language to make the stack grow without an arbitrary limit (besides the limit of physical memory)? Yes, some languages already do this. For example, you'll never get a literal "stack overflow" error in Go[0]. (You'll never get one in Java either - it'll be an OutOfMemoryException or whatever they call it) [0] http://dave.cheney.net/2013/06/02/why-is-a-goroutines-stack-infinite http://dave.cheney.net/2013/06/02/why-is-a-goroutines-stack-...
- epidemian 11y ago> [...] it's rather pointless in practice unless you can do it at runtime without crashing the browser or causing it to become unresponsive. The snippet i posted doesn't crash the browser and seems to take around 1 or 2 milliseconds to run. Considering usual page load times, and if detecting whether TCO works is important for an application, it doesn't seem like an unreasonable solution (albeit pretty ugly hehe). Thanks for the pointers about languages that don't have this limitation. Unfortunately, it doesn't seem to be the case for Java. This simple recursive function throws a StackOverflowError in less than 100,000 iterations: http://ideone.com/Tf4n3I http://ideone.com/Tf4n3I, and it's not because the program is consuming all physical memory: /usr/bin/time -v java StackOverflowExample Exception in thread "main" java.lang.StackOverflowError at StackOverflowExample.rec(StackOverflowExample.java:7) at StackOverflowExample.rec(StackOverflowExample.java:8) at StackOverflowExample.rec(StackOverflowExample.java:8) ... Command exited with non-zero status 1 Command being timed: "java StackOverflowExample" User time (seconds): 0.13 System time (seconds): 0.01 ... Maximum resident set size (kbytes): 27000 ...
- braythwayt 11y agoI would use two mutually recursive functions rather than a single recursive function, as it’s possible for an implementor to implement TCE for recursive functions, but not for the general case. I’d also up the number. That code runs fine in Safari for 20,000, I had to use 200,000 to get it to break.