3 ms·

> If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. The recursive P

> If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.

eru 6y ago
I just tried it out, I didn't manage to get GHC to compile the equivalent of the code I've given into something that runs in constant memory. (I did the calculations modulo some number, to keep the numbers themselves bounded.) GHC is sometimes able to do some of those transformations. > The recursive Python version above didn't use tail calls. Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.
- tom_mellior 6y ago
  > Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls. I was talking about this code: def fib(n): if n =< 0: return (0, 1) else: a, b = f(n-1) return (b, a + b) Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.
  - eru 6y ago
    The last call (to a function or operator) is in the tail position. In this case, it is tuple packing. Why wouldn't the tuple packing be in tail position in the Python code?
    - tom_mellior 6y ago
      Because after tuple packing returns (a C return) you still need to perform a Python return. The C tuple packing function cannot return directly from the Python function. Looking at https://github.com/python/cpython/blob/master/Python/ceval.c https://github.com/python/cpython/blob/master/Python/ceval.c, here is the code that needs to be executed after the tuple is constructed: case TARGET(RETURN_VALUE): { retval = POP(); assert(f->f_iblock == 0); assert(EMPTY()); f->f_state = FRAME_RETURNED; f->f_stackdepth = 0; goto exiting; } // ... exiting: if (tstate->use_tracing) { if (tstate->c_tracefunc) { if (call_trace_protected(tstate->c_tracefunc, tstate->c_traceobj, tstate, f, PyTrace_RETURN, retval)) { Py_CLEAR(retval); } } if (tstate->c_profilefunc) { if (call_trace_protected(tstate->c_profilefunc, tstate->c_profileobj, tstate, f, PyTrace_RETURN, retval)) { Py_CLEAR(retval); } } } /* pop frame */ exit_eval_frame: if (PyDTrace_FUNCTION_RETURN_ENABLED()) dtrace_function_return(f); _Py_LeaveRecursiveCall(tstate); tstate->frame = f->f_back; return _Py_CheckFunctionResult(tstate, NULL, retval, __func__); I guess you could duplicate all this code in a special "pack tuple and return from Python function" C function which you could then really tail call.
      - eru 6y ago
        Oh, yes, I was only saying that as far as the Python language is concerned the tuple packing is in the tail position. Any specific implementation, and in this case cpython, could do arbitrary weird things after. Thanks for looking up the code!

eru 6y ago

I just tried it out, I didn't manage to get GHC to compile the equivalent of the code I've given into something that runs in constant memory. (I did the calculations modulo some number, to keep the numbers themselves bounded.) GHC is sometimes able to do some of those transformations. > The recursive Python version above didn't use tail calls. Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.

tom_mellior 6y ago
> Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls. I was talking about this code: def fib(n): if n =< 0: return (0, 1) else: a, b = f(n-1) return (b, a + b) Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.
- eru 6y ago
  The last call (to a function or operator) is in the tail position. In this case, it is tuple packing. Why wouldn't the tuple packing be in tail position in the Python code?
  - tom_mellior 6y ago
    Because after tuple packing returns (a C return) you still need to perform a Python return. The C tuple packing function cannot return directly from the Python function. Looking at https://github.com/python/cpython/blob/master/Python/ceval.c https://github.com/python/cpython/blob/master/Python/ceval.c, here is the code that needs to be executed after the tuple is constructed: case TARGET(RETURN_VALUE): { retval = POP(); assert(f->f_iblock == 0); assert(EMPTY()); f->f_state = FRAME_RETURNED; f->f_stackdepth = 0; goto exiting; } // ... exiting: if (tstate->use_tracing) { if (tstate->c_tracefunc) { if (call_trace_protected(tstate->c_tracefunc, tstate->c_traceobj, tstate, f, PyTrace_RETURN, retval)) { Py_CLEAR(retval); } } if (tstate->c_profilefunc) { if (call_trace_protected(tstate->c_profilefunc, tstate->c_profileobj, tstate, f, PyTrace_RETURN, retval)) { Py_CLEAR(retval); } } } /* pop frame */ exit_eval_frame: if (PyDTrace_FUNCTION_RETURN_ENABLED()) dtrace_function_return(f); _Py_LeaveRecursiveCall(tstate); tstate->frame = f->f_back; return _Py_CheckFunctionResult(tstate, NULL, retval, __func__); I guess you could duplicate all this code in a special "pack tuple and return from Python function" C function which you could then really tail call.
    - eru 6y ago
      Oh, yes, I was only saying that as far as the Python language is concerned the tuple packing is in the tail position. Any specific implementation, and in this case cpython, could do arbitrary weird things after. Thanks for looking up the code!