4 ms·

I'm not sure I understand/agree the point about "iteration over recursion". One of my favorite aspects of Lisp is the recursive approach to writing functions. I

by mck- 14y ago

I'm not sure I understand/agree the point about "iteration over recursion". One of my favorite aspects of Lisp is the recursive approach to writing functions. It's still possible to write recursive functions that don't rely on a specific compiler's optimization: (defun sum (numbers) (labels ((helper (todo ans) (if (null todo) ans (helper (cdr todo) (+ ans (car todo)))))) (helper numbers 0))) I hope that this is what the author meant with "iterative" approach, because it is recursive by most standards.

gosub 14y ago
Without TCO, doesn't your function overflow the stack, given that "numbers" is long enough? By iterative I think they mean the use of "loop" or "iterate".
- JabavuAdams 14y ago
  I thought that Common Lisp guaranteed Tail Call Optimization (TCO), but it looks like it's actually up to the implementation: http://0branch.com/notes/tco-cl.html http://0branch.com/notes/tco-cl.html
  - Evbn 14y ago
    Nit pick: if it is guaranteed, call it Elimination, not Optimization, because it is part of the operational semantics required to reason about performance. As a compiler Optimization, you have an algorithm that is omega(n) space usage, but with Elimination as a language feature you have an O(1) space usage. Yes, you can include compiler optimizations in your model of the language, but it helps to distinguish opportunitistic speedups from guaranteed complexity class improvements.
  - bitwize 14y ago
    Scheme guarantees it; CL only provides it as an option.
ScottBurson 14y ago
I think they consider that recursive. However, all the major implementations (SBCL, Clozure CL, Franz Allegro, LispWorks, CMUCL, and I think even ECL) do tail-call elimination on local calls. (A local call is a call to a function whose definition is lexically visible, such as the calls to 'helper' in your example.) The document says that TCE depends on optimization settings, but for local calls, I'm not sure even that is true. Anyway, the practical upshot, in my experience, is that there's no reason not to write loops recursively using LABELS when that is the most elegant expression of the particular loop in question. (There was once a major implementation that never did TCE -- Genera -- but even for die-hard Lisp Machine lovers like myself, it has long since been relegated to a historical curiosity.)
- mck- 14y ago
  Thanks for that Scott, I've never heard of TCE -- learn something every day reading HN. Just did a quick comparison (SBCL) between the above and the textbook version: (defun sum (list) (if (null list) 0 (+ (car list) (sum (cdr list))))) This version quickly dumped Heap Exhaustion. The LABELS version does not, and can handle summation over lists much faster as well. What does this mean? TCE only applies applies to local calls, therefore we should never write a "raw" recursive function? (which is a tad more elegant, imo). I haven't delved into TCOs deep enough to understand, but I had hoped that a smart compiler would be able to optimize the latter?

by mck- 14y ago

gosub 14y ago

Without TCO, doesn't your function overflow the stack, given that "numbers" is long enough? By iterative I think they mean the use of "loop" or "iterate".

JabavuAdams 14y ago
I thought that Common Lisp guaranteed Tail Call Optimization (TCO), but it looks like it's actually up to the implementation: http://0branch.com/notes/tco-cl.html http://0branch.com/notes/tco-cl.html
- Evbn 14y ago
  Nit pick: if it is guaranteed, call it Elimination, not Optimization, because it is part of the operational semantics required to reason about performance. As a compiler Optimization, you have an algorithm that is omega(n) space usage, but with Elimination as a language feature you have an O(1) space usage. Yes, you can include compiler optimizations in your model of the language, but it helps to distinguish opportunitistic speedups from guaranteed complexity class improvements.
- bitwize 14y ago
  Scheme guarantees it; CL only provides it as an option.

ScottBurson 14y ago

I think they consider that recursive. However, all the major implementations (SBCL, Clozure CL, Franz Allegro, LispWorks, CMUCL, and I think even ECL) do tail-call elimination on local calls. (A local call is a call to a function whose definition is lexically visible, such as the calls to 'helper' in your example.) The document says that TCE depends on optimization settings, but for local calls, I'm not sure even that is true. Anyway, the practical upshot, in my experience, is that there's no reason not to write loops recursively using LABELS when that is the most elegant expression of the particular loop in question. (There was once a major implementation that never did TCE -- Genera -- but even for die-hard Lisp Machine lovers like myself, it has long since been relegated to a historical curiosity.)

mck- 14y ago
Thanks for that Scott, I've never heard of TCE -- learn something every day reading HN. Just did a quick comparison (SBCL) between the above and the textbook version: (defun sum (list) (if (null list) 0 (+ (car list) (sum (cdr list))))) This version quickly dumped Heap Exhaustion. The LABELS version does not, and can handle summation over lists much faster as well. What does this mean? TCE only applies applies to local calls, therefore we should never write a "raw" recursive function? (which is a tad more elegant, imo). I haven't delved into TCOs deep enough to understand, but I had hoped that a smart compiler would be able to optimize the latter?