4 ms·

I think this is partly Stockholm syndrome. Having a finite stack will cut off infinite recursion before it consumes the whole memory, and infinite recursion is

I think this is partly Stockholm syndrome. Having a finite stack will cut off infinite recursion before it consumes the whole memory, and infinite recursion is often an error (e.g. if we get some branching logic wrong, our base case may never be taken). Over time this has become self-reinforcing: - Recursive algorithms may hit stack limits, which makes them less attractive, so programmers are less likely to choose them - Error rates presumably remain pretty constant, so this avoidance decreases the proportion of recursive programs that are deliberately so, and increases the proportion of recursive programs that are accidentally so - Stack limits remain justified, due to how rarely programmers are choosing recursive approaches, and how often stack overflows help us to stop buggy programs I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction (e.g. we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute, to stop buggy programs, those which need more time can spawn children; etc.). I appreciate that low-level languages are operating under some pretty tight constraints (both in what's available to them, and the performance their users expect). What I find very strange is how many high-level scripting languages impose such stack limits, and don't even eliminate tail-calls. The raison d'etre for such languages is to be more ergonomic and powerful than bare-metal languages, and they don't mind sacrificing a lot of performance to do so (using interpreters, boxed values, dynamic dispatch, etc.); yet they're somehow fine with inheriting these weird restrictions from C & co.?

Someone 6y ago
“we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute” In JCL (https://en.wikipedia.org/wiki/Job_Control_Language https://en.wikipedia.org/wiki/Job_Control_Language), you can specify how much CPU time a program can spend, how many pages it can output before the OS kills it, and have to specify what files it reads and writes. That was useful at a time when CPU time, memory and disk space were scarce and expensive, and still would be useful when sandboxing untrusted code.
- chriswarbo 6y ago
  > you can specify It's nice to have the option of specifying such limits, but not all programs are batch jobs. For example, the correct CPU time cap for a HTTP server is infinity. Likewise, if that server were written as a recursive function then the correct stack size would be infinity: def serve(request): response = process(request) socket.send(response) serve(socket.receive())
ufo 6y ago
> I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction This is the part that irks me the most. If I have an algorithm that is neatly written as a recursive algorithm and mechanically rewrite it to use an explicit stack, that doesn't change the fact that an infinite loop is still a bug. It's just that it's going to manifest as the process using all the available RAM instead of as a stack overflow. > yet they're somehow fine with inheriting these weird restrictions from C & co.? Sometimes that's because the interpreter itself uses recursion. That can be convenient for whoever is implementing the interpreter, at the cost of inheriting the stack limit from C. That said, there are also languages that enforce a recursion limit even when they don't use the C stack at all. In which case I ask the exact same question as you do.
recursivecaveat 6y ago
I tend to think of it as a handy feature of recursive algorithms that encourages me to use them. Just twice in my life have I wanted to exceed the default stack size in Python, but many times have my programs crashed with a helpful stack trace when they would otherwise have locked up in an infinite loop. I do however work in a subfield where it's pretty acceptable to just say "yaaa, don't do that" to unbounded input sizes, so ymmv.
- chriswarbo 6y ago
  There are many situations where we want infinite recursion. A simple example is a server: def serve(request): response = process(request) socket.send(response) serve(socket.receive()) The same thing applies to anything which 'handles events', including servers, games, GUIs, CLIs, etc. In general, any time we might write a "main loop" like: foo = lambda z: .... bar = lambda x: .... baz = lambda y: .... def main(): z = init while true: x = foo(z) y = bar(x) z = baz(y) This is equivalent to having each step perform a tail-call to the next one: foo = lambda z: bar(....) bar = lambda x: baz(....) baz = lambda y: foo(....) main = lambda : foo(init) The latter form has better encapsulation, requires no mutable state, doesn't have stale/out-of-date variables, etc. The fact that infinite recursion is seen as a bug, yet "while true:" loops are common, is a symptom of this negative feedback loop which keeps people from learning and using recursive solutions.

Someone 6y ago

“we could limit RAM usage to 64K to prevent buggy programms allocating too much, those which want more can edit files in a tempfs; processes should run for no longer than 1 minute” In JCL (https://en.wikipedia.org/wiki/Job_Control_Language https://en.wikipedia.org/wiki/Job_Control_Language), you can specify how much CPU time a program can spend, how many pages it can output before the OS kills it, and have to specify what files it reads and writes. That was useful at a time when CPU time, memory and disk space were scarce and expensive, and still would be useful when sandboxing untrusted code.

chriswarbo 6y ago
> you can specify It's nice to have the option of specifying such limits, but not all programs are batch jobs. For example, the correct CPU time cap for a HTTP server is infinity. Likewise, if that server were written as a recursive function then the correct stack size would be infinity: def serve(request): response = process(request) socket.send(response) serve(socket.receive())

ufo 6y ago

> I don't think the 'stops buggy programs' argument is particularly compelling, since that could apply to pretty much any restriction This is the part that irks me the most. If I have an algorithm that is neatly written as a recursive algorithm and mechanically rewrite it to use an explicit stack, that doesn't change the fact that an infinite loop is still a bug. It's just that it's going to manifest as the process using all the available RAM instead of as a stack overflow. > yet they're somehow fine with inheriting these weird restrictions from C & co.? Sometimes that's because the interpreter itself uses recursion. That can be convenient for whoever is implementing the interpreter, at the cost of inheriting the stack limit from C. That said, there are also languages that enforce a recursion limit even when they don't use the C stack at all. In which case I ask the exact same question as you do.

recursivecaveat 6y ago

I tend to think of it as a handy feature of recursive algorithms that encourages me to use them. Just twice in my life have I wanted to exceed the default stack size in Python, but many times have my programs crashed with a helpful stack trace when they would otherwise have locked up in an infinite loop. I do however work in a subfield where it's pretty acceptable to just say "yaaa, don't do that" to unbounded input sizes, so ymmv.

chriswarbo 6y ago
There are many situations where we want infinite recursion. A simple example is a server: def serve(request): response = process(request) socket.send(response) serve(socket.receive()) The same thing applies to anything which 'handles events', including servers, games, GUIs, CLIs, etc. In general, any time we might write a "main loop" like: foo = lambda z: .... bar = lambda x: .... baz = lambda y: .... def main(): z = init while true: x = foo(z) y = bar(x) z = baz(y) This is equivalent to having each step perform a tail-call to the next one: foo = lambda z: bar(....) bar = lambda x: baz(....) baz = lambda y: foo(....) main = lambda : foo(init) The latter form has better encapsulation, requires no mutable state, doesn't have stale/out-of-date variables, etc. The fact that infinite recursion is seen as a bug, yet "while true:" loops are common, is a symptom of this negative feedback loop which keeps people from learning and using recursive solutions.