5 ms·

I'm seeing stack overflows (not a problem with tail-call optimization) as the biggest problem here. There are equally dangerous problems, though. Buffer overflo

I'm seeing stack overflows (not a problem with tail-call optimization) as the biggest problem here. There are equally dangerous problems, though. Buffer overflows are a very real concern, especially in embedded software; but that doesn't mean that people don't ever use pointers. Everything about software has risks. Yes, they probably shouldn't have used recursion there in that car; but honestly, it's just a stack. Enough calls and some state could have been frozen. They should have put mitigations in place to stop the potential for a stack overflow to have actual, detrimental results. Do you refuse to ever make a function call for fear that you might be at the top of the stack somehow? After all, how can you know that you haven't accidentally created a state machine with function calls and are at the peak of it now, and end up causing the same problem. Recursion may have been the final manifestation, but it's certainly not the only place that failed. I argue against your thought that recursion is useless, as well. It's a natural and intuitive solution for a lot of problems. The very concept of a dynamic programming solution starts with a recurrence relationship. It starts with recursion. Sorting algorithms are intutively recursive in many cases, Quicksort and Mergesort are just two examples. And, 'dangerous' is an interesting term. I understand you've worked in embedded systems and hardware, and so those things are often critical systems that have to be super secure and completely bug free. Not every system is like that, though. I want to understand why you believe that recursion is both useless and dangerous. Could you give some broad examples of the dangers of recursion from your years of experience?

Retric 12y ago
It's trivial to blow the stack even on languages with tail call optimization.
- mytochar 12y ago
  By writing incorrect recursion? Or in some other way?
  - Retric 12y ago
    Both, the obvious example is the fibinatchi sequence f(x) = f(x-1) + f(x-2). There are lots of efficient ways of coding it but the most obvious O(n^2) approch is n depth and it can't be tail-call optimized. Granted, you can write much more efficient code that can be tail call optimized, but there complex and less obvious. There are also languages which cache previous results so the native approch becomes O(n) with fairly elegant code that's still depth n. PS: Anyway, tail call optimization only works when you can rewrite the code as a loop for more complex structures it's less useful.
    - sklogic 12y ago
      > Anyway, tail call optimization only works when you can rewrite the code as a loop You cannot turn a virtual tail call into a static jump.
      - Retric 12y ago
        Sure, it needs bookkeeping but it's still trivial to create a loop equivalent of any tail call optimizable code that your compiler recognizes. PS: Feel free to look for any counter example.
        sklogic 12y ago
        > PS: Feel free to look for any counter example. Ok, create a loop equivalent for `(define (f g x) (g x))`.
        Retric 12y ago
        x Though the mechanical equivalent would be something like: huge(input) { output, continue, current_function = f; do{ if (current_function == f) {input = x ; continue = true; current_function=g} if (current_function == g) { output = input; continue = false;} }while(continue); return output; } You would then add any function you would tail call optimize into that function. Granted, with the right structure (inside > outside >... > inside) it can show up more than once on the stack but the same thing can happen despite tail call optimization.
- sklogic 12y ago
  Ok, try to blow the stack in a stackless language implementation.
  - Retric 12y ago
    F(x) = F(x) + F(x) Eventually you hit OOM or some death limit even on a stackless language.
    - sklogic 12y ago
      This is a memory leak now, not a stack overflow.
      - Retric 12y ago
        Thus demonstrating a finite stack. "Stackless" just a more efficent way to use memory. You could get the same things from dynamicly allocating and dealocating stack space as needed. Put another way, allocating 1GB of stack space on a machine with 2GB of RAM is at worst the equivelent of using a stackless lanugage on a machine limited 1 GB of RAM. PS: It's actually worse as stackless languages are stricly slower than actually having the equivelent stack space pre alocated and you need to put an pointer for each stack call pluss overhead for alocating memory.

Retric 12y ago

It's trivial to blow the stack even on languages with tail call optimization.

mytochar 12y ago
By writing incorrect recursion? Or in some other way?
- Retric 12y ago
  Both, the obvious example is the fibinatchi sequence f(x) = f(x-1) + f(x-2). There are lots of efficient ways of coding it but the most obvious O(n^2) approch is n depth and it can't be tail-call optimized. Granted, you can write much more efficient code that can be tail call optimized, but there complex and less obvious. There are also languages which cache previous results so the native approch becomes O(n) with fairly elegant code that's still depth n. PS: Anyway, tail call optimization only works when you can rewrite the code as a loop for more complex structures it's less useful.
  - sklogic 12y ago
    > Anyway, tail call optimization only works when you can rewrite the code as a loop You cannot turn a virtual tail call into a static jump.
    - Retric 12y ago
      Sure, it needs bookkeeping but it's still trivial to create a loop equivalent of any tail call optimizable code that your compiler recognizes. PS: Feel free to look for any counter example.
      - sklogic 12y ago
        > PS: Feel free to look for any counter example. Ok, create a loop equivalent for `(define (f g x) (g x))`.
        Retric 12y ago
        x Though the mechanical equivalent would be something like: huge(input) { output, continue, current_function = f; do{ if (current_function == f) {input = x ; continue = true; current_function=g} if (current_function == g) { output = input; continue = false;} }while(continue); return output; } You would then add any function you would tail call optimize into that function. Granted, with the right structure (inside > outside >... > inside) it can show up more than once on the stack but the same thing can happen despite tail call optimization.
sklogic 12y ago
Ok, try to blow the stack in a stackless language implementation.
- Retric 12y ago
  F(x) = F(x) + F(x) Eventually you hit OOM or some death limit even on a stackless language.
  - sklogic 12y ago
    This is a memory leak now, not a stack overflow.
    - Retric 12y ago
      Thus demonstrating a finite stack. "Stackless" just a more efficent way to use memory. You could get the same things from dynamicly allocating and dealocating stack space as needed. Put another way, allocating 1GB of stack space on a machine with 2GB of RAM is at worst the equivelent of using a stackless lanugage on a machine limited 1 GB of RAM. PS: It's actually worse as stackless languages are stricly slower than actually having the equivelent stack space pre alocated and you need to put an pointer for each stack call pluss overhead for alocating memory.