3 ms·

I prefer looping constructs over recursion, almost every single time. Loops are closer to what CPU actually does. A compiler is therefore simpler to implement

I prefer looping constructs over recursion, almost every single time. Loops are closer to what CPU actually does. A compiler is therefore simpler to implement and will likely contain less surprises. It’s easier to use a debugger on procedural-style or OO code (step in/over/out, local variables) compared to recursive functional style advertised by SICP. In most runtimes, call stack is limited to a small size, couple of megabytes. Stack overflow exception is hard to handle in reasonable way. When instead using a loop with a stack container for state, it can be much larger, also easier to handle overflows i.e. implement soft and hard limits.

deleted 8y ago
[deleted]
mrami 8y ago
To be fair, Scheme implements tail recursion, which converts properly prepared recursion into an iterative loop. Usually converting the recursive call into a GOTO. So if used correctly, recursion in scheme isn't a stack issue. That said, I love my for loops, too.
- Const-me 8y ago
  > which converts properly prepared recursion into an iterative loop It only works if you are using recursion in place of a simple loop. Many algorithms traditionally implemented with recursion (e.g. various tree searches) need that stack somewhere. Technically it’s probably possible to “properly prepare” that, but practically both alternatives (recursion + built-in call stack, or loop + separate stack) are much easier to implement.
willtim 8y ago
Explicit recursion is really a foundational primitive upon which other abstractions should be built, including looping constructs. It is similar to goto, in that it is a form of unstructured programming. Functional programmers prefer using maps and folds. Loops are not necessarily close to what a CPU actually does either, especially one supporting vector operations or out-of-order execution. Loops imply an ordering which may or may not be actually exist and many compilers are complicated by their presence. Debuggers are a problem for any suitably high-level abstract code. Would a step-by-step word-at-a-time debugger help to debug a SQL query or even a complex arithmetical expression from Fortran? There is no getting away from the fact that high-level domain-specific code needs high-level domain-specific debuggers to be built alongside.
- lucio 8y ago
  In current hardware, recursion is far from a "primitive". jump is a primitive. Looping is above that, and recursion is way above iteration in a "foundational vs. composed" hierarchy. https://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping/28033212#28033212 https://stackoverflow.com/questions/2651112/is-recursion-eve...
  - willtim 8y ago
    I was advocating recursion as a foundational primitive for a compiled high-level or intermediate language, not as part of some hardware instruction set. Current hardware is a bit of a legacy mess, we should resist the temptation to take on its baggage.
- Const-me 8y ago
  > functional programmers prefer using maps and folds. I know and I don’t think these are always good things. > Loops are not necessarily close to what a CPU actually does either Indeed, not necessarily, but very often. Unless automatic vectorization is involved, long loops are very often quite close to the machine code uploaded to CPU. Inside the CPU it’s free to do whatever, but on the public API, it’s still loop instructions. > the fact that high-level domain-specific code needs high-level domain-specific debuggers to be built alongside. That’s not a fact, that’s your opinion. I don’t code SQL nor Fortran, mostly C++ and C#, sometimes Python and others. The debuggers I have in corresponding IDEs are already built, they are sufficiently high-level for domain specific code, but the debuggers themselves aren’t domain specific, they are pretty general purpose.
  - willtim 8y ago
    > I know and I don’t think these are always good things. Maps and folds do make structure explicit though. For example, it is very easy for a compiler to vectorise a "map" operation. Folds will always terminate. > The debuggers I have in corresponding IDEs are already built, they are sufficiently high-level for domain specific code. But does your debugger allow you to visualise the intermediate steps of an arithmetic expression? Does it understand Iterables/Enumerables and allow you to capture and inspect them? Can it handle concurrency and parallelism, or help you make sense of callbacks for non-blocking IO etc? My point is that the debugger is simply not as general purpose as most claim it to be. It sees the world word-at-a-time and only allows you to step statement-by-statement. It does not understand the composite data structures or control structures that you have built. This is less of a problem with low-level code, as typically there is limited abstraction. But it will be a problem for any sufficiently high-level abstract code (functional or otherwise).
akashakya 8y ago
> Loops are closer to what CPU actually does. A compiler is therefore simpler to implement and will likely contain less surprises. I dont find the argument convincing. By that assembly is closer to what CPU actually does, why not write code using goto (or binary)? We all can agree on its easy to write reasonably good code high-level languages. I think it because high-level languages are closer to the problem domain (or our thinking), hence it's easier to define the solution in these languages. same for recursion. > It’s easier to use a debugger on procedural-style or OO code (step in/over/out, local variables) compared to recursive functional style advertised by SICP. I feel exactly opposite. OO by definition have state bound to object outside the method (not actually local variable), so you have to watch all the objects method is affecting. Not pleasant experience when you have hundreds of objects. A recursive code on the other hand usually depends only on the local arguments so you can only focus on current step. > In most runtimes, call stack is limited to a small size, a couple of megabytes. Stack overflow exception is hard to handle in a reasonable way. When instead using a loop with a stack container for the state, it can be much larger, also easier to handle overflows i.e. implement soft and hard limits. Well, depends on the platform you are working on. For desktop at least it's definitely not "a couple of megabytes". I feel that most of the time choice is between readability and performance. Sometimes maybe the solution is inherently iterative/recursive making choice easier. ymmv though.
- Const-me 8y ago
  > I think it because high-level languages are closer to the problem domain (or our thinking) Mostly agree. > same for recursion I don’t know about you, but in my problem domains loops are closer then recursion. Also loops are closer to my thinking. YMMV. > Not pleasant experience when you have hundreds of objects No one forces you to design your OO apps this way. When you only have a few objects, or when you only process them sequentially, there’s no need in complex OO model, a functional or procedural code will do fine. However, there’re apps where there’re hundreds of interacting objects, such as a web browser. > For desktop at least it's definitely not "a couple of megabytes". On Windows it’s usually (=for apps linked with default settings) 1 megabyte.
  - 8y ago
hajile 8y ago
Closer to the CPU isn't a valid argument. Most major programming concepts don't exist in a CPU. * CPUs are dynamically scoped * CPUs are weakly typed * CPUs are dynamically typed * CPUs only compare to zero * CPUs have no way to represent OOP and so on All that said, tail calls are very close to how the CPU works. They are just GOTO with additional parameters. If you implement tail calls with dynamic scoping, the parameters would be registers and the tail call would be a change to the instruction pointer. That would be very close indeed.

deleted 8y ago

[deleted]

mrami 8y ago

To be fair, Scheme implements tail recursion, which converts properly prepared recursion into an iterative loop. Usually converting the recursive call into a GOTO. So if used correctly, recursion in scheme isn't a stack issue. That said, I love my for loops, too.

Const-me 8y ago
> which converts properly prepared recursion into an iterative loop It only works if you are using recursion in place of a simple loop. Many algorithms traditionally implemented with recursion (e.g. various tree searches) need that stack somewhere. Technically it’s probably possible to “properly prepare” that, but practically both alternatives (recursion + built-in call stack, or loop + separate stack) are much easier to implement.

willtim 8y ago

Explicit recursion is really a foundational primitive upon which other abstractions should be built, including looping constructs. It is similar to goto, in that it is a form of unstructured programming. Functional programmers prefer using maps and folds. Loops are not necessarily close to what a CPU actually does either, especially one supporting vector operations or out-of-order execution. Loops imply an ordering which may or may not be actually exist and many compilers are complicated by their presence. Debuggers are a problem for any suitably high-level abstract code. Would a step-by-step word-at-a-time debugger help to debug a SQL query or even a complex arithmetical expression from Fortran? There is no getting away from the fact that high-level domain-specific code needs high-level domain-specific debuggers to be built alongside.

lucio 8y ago
In current hardware, recursion is far from a "primitive". jump is a primitive. Looping is above that, and recursion is way above iteration in a "foundational vs. composed" hierarchy. https://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping/28033212#28033212 https://stackoverflow.com/questions/2651112/is-recursion-eve...
- willtim 8y ago
  I was advocating recursion as a foundational primitive for a compiled high-level or intermediate language, not as part of some hardware instruction set. Current hardware is a bit of a legacy mess, we should resist the temptation to take on its baggage.
Const-me 8y ago
> functional programmers prefer using maps and folds. I know and I don’t think these are always good things. > Loops are not necessarily close to what a CPU actually does either Indeed, not necessarily, but very often. Unless automatic vectorization is involved, long loops are very often quite close to the machine code uploaded to CPU. Inside the CPU it’s free to do whatever, but on the public API, it’s still loop instructions. > the fact that high-level domain-specific code needs high-level domain-specific debuggers to be built alongside. That’s not a fact, that’s your opinion. I don’t code SQL nor Fortran, mostly C++ and C#, sometimes Python and others. The debuggers I have in corresponding IDEs are already built, they are sufficiently high-level for domain specific code, but the debuggers themselves aren’t domain specific, they are pretty general purpose.
- willtim 8y ago
  > I know and I don’t think these are always good things. Maps and folds do make structure explicit though. For example, it is very easy for a compiler to vectorise a "map" operation. Folds will always terminate. > The debuggers I have in corresponding IDEs are already built, they are sufficiently high-level for domain specific code. But does your debugger allow you to visualise the intermediate steps of an arithmetic expression? Does it understand Iterables/Enumerables and allow you to capture and inspect them? Can it handle concurrency and parallelism, or help you make sense of callbacks for non-blocking IO etc? My point is that the debugger is simply not as general purpose as most claim it to be. It sees the world word-at-a-time and only allows you to step statement-by-statement. It does not understand the composite data structures or control structures that you have built. This is less of a problem with low-level code, as typically there is limited abstraction. But it will be a problem for any sufficiently high-level abstract code (functional or otherwise).

akashakya 8y ago

> Loops are closer to what CPU actually does. A compiler is therefore simpler to implement and will likely contain less surprises. I dont find the argument convincing. By that assembly is closer to what CPU actually does, why not write code using goto (or binary)? We all can agree on its easy to write reasonably good code high-level languages. I think it because high-level languages are closer to the problem domain (or our thinking), hence it's easier to define the solution in these languages. same for recursion. > It’s easier to use a debugger on procedural-style or OO code (step in/over/out, local variables) compared to recursive functional style advertised by SICP. I feel exactly opposite. OO by definition have state bound to object outside the method (not actually local variable), so you have to watch all the objects method is affecting. Not pleasant experience when you have hundreds of objects. A recursive code on the other hand usually depends only on the local arguments so you can only focus on current step. > In most runtimes, call stack is limited to a small size, a couple of megabytes. Stack overflow exception is hard to handle in a reasonable way. When instead using a loop with a stack container for the state, it can be much larger, also easier to handle overflows i.e. implement soft and hard limits. Well, depends on the platform you are working on. For desktop at least it's definitely not "a couple of megabytes". I feel that most of the time choice is between readability and performance. Sometimes maybe the solution is inherently iterative/recursive making choice easier. ymmv though.

Const-me 8y ago
> I think it because high-level languages are closer to the problem domain (or our thinking) Mostly agree. > same for recursion I don’t know about you, but in my problem domains loops are closer then recursion. Also loops are closer to my thinking. YMMV. > Not pleasant experience when you have hundreds of objects No one forces you to design your OO apps this way. When you only have a few objects, or when you only process them sequentially, there’s no need in complex OO model, a functional or procedural code will do fine. However, there’re apps where there’re hundreds of interacting objects, such as a web browser. > For desktop at least it's definitely not "a couple of megabytes". On Windows it’s usually (=for apps linked with default settings) 1 megabyte.
- 8y ago

hajile 8y ago

Closer to the CPU isn't a valid argument. Most major programming concepts don't exist in a CPU. * CPUs are dynamically scoped * CPUs are weakly typed * CPUs are dynamically typed * CPUs only compare to zero * CPUs have no way to represent OOP and so on All that said, tail calls are very close to how the CPU works. They are just GOTO with additional parameters. If you implement tail calls with dynamic scoping, the parameters would be registers and the tail call would be a change to the instruction pointer. That would be very close indeed.