5 ms·

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
        Mini-interpreter implementations do not count, for performance reasons. You could have called a VM bytecode interpreter loop a "loop alternative to tail call" here.
        Retric 12y ago
        My first example of (f x) is about as fast as you can get. The longer example is not great the point is it's a very language agnostic tradeoff of speed vs memory. Replace the ‘if’ conditionals with a case statement and its much faster you can speed it up further by using continue. You can speed it up even more by having a jump at the end of each statement, but that stops looking like a loop and is basically just the tail call optimization. Anyway, the important part is its low memory utilization and compiler independent. PS: I in no way suggest tail call optimization was not useful; just you can mechanically simulate it when not available. You can usually beat that mechanical approach if you need to speed things up further.
        sklogic 12y ago
        > as fast as you can get. But yet 10x slower than a single indirect jump. > just you can mechanically simulate it when not available. It's too slow to ever be anywhere near practical - for this reason, almost no JVM language implementation really does anything like this, besides kawa, bigloo and alike, which are slower than some of the dumb interpreters like SISC.
        Retric 12y ago
        I don't think I was clear enough, it simplifies to zero code (not even a jump) just the original input. (I thought about saying noop but even that's wasteful.) >"it's slow" Again, it's just a technique; think writing embedded code with a really dumb compiler. Anyway, saying its slow is not really a counter argument if your limited to say 2,000 bytes of ram you will make lot's of tradeoffs between efficiency and speed. Perhaps you have a select statement perhaps you don't, but starting off with pure ASM is often a pain. EDIT: This is all from the perspective of dealing with tools that don't do tail call optimization, not writing a compiler / VM etc.

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
        Mini-interpreter implementations do not count, for performance reasons. You could have called a VM bytecode interpreter loop a "loop alternative to tail call" here.
        Retric 12y ago
        My first example of (f x) is about as fast as you can get. The longer example is not great the point is it's a very language agnostic tradeoff of speed vs memory. Replace the ‘if’ conditionals with a case statement and its much faster you can speed it up further by using continue. You can speed it up even more by having a jump at the end of each statement, but that stops looking like a loop and is basically just the tail call optimization. Anyway, the important part is its low memory utilization and compiler independent. PS: I in no way suggest tail call optimization was not useful; just you can mechanically simulate it when not available. You can usually beat that mechanical approach if you need to speed things up further.
        sklogic 12y ago
        > as fast as you can get. But yet 10x slower than a single indirect jump. > just you can mechanically simulate it when not available. It's too slow to ever be anywhere near practical - for this reason, almost no JVM language implementation really does anything like this, besides kawa, bigloo and alike, which are slower than some of the dumb interpreters like SISC.
        Retric 12y ago
        I don't think I was clear enough, it simplifies to zero code (not even a jump) just the original input. (I thought about saying noop but even that's wasteful.) >"it's slow" Again, it's just a technique; think writing embedded code with a really dumb compiler. Anyway, saying its slow is not really a counter argument if your limited to say 2,000 bytes of ram you will make lot's of tradeoffs between efficiency and speed. Perhaps you have a select statement perhaps you don't, but starting off with pure ASM is often a pain. EDIT: This is all from the perspective of dealing with tools that don't do tail call optimization, not writing a compiler / VM etc.