And didn't tail call optimization only become standard in Lisps with the advent of Scheme?
In any case, at Standard Chartered we didn't have tail call optimization with our Haskell dialect either. It didn't matter too much in practice, because you should be using combinators anyway. And when you are calling foldr or map, you do not care that somewhere hidden away they are implemented with a loop in C++, as long as they behave right.
Well SC's proprietary compiler is probably different, but GHC is self-hosted (the runtime system is C but the compiler is implemented in Haskell) and the map and fold functions in Prelude are recursive. Here's the source code for `map` in Prelude:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
But it is definitely still true that explicit recursion is discouraged as being too 'low-level' for most Haskell code and it's preferable to use higher-order functions instead.
Indeed, and as far as I know Scheme JVM implementations, which I haven't looked at in a long while, either do it per the spec and are slow, SISC reputedly, died about the time I might have started using it, or go through contortions like Kawa to do the best you can. Don't know about JScheme, it was dead before then, and I just noticed Bigloo will compile to the JVM, adding one to the list of 4.
I seem to recall it depending on compiler settings whether sbcl does tco. Which means you probably don't want to rely on it in general unless you are okay being locked to a specific implementation and specific optimization settings that may-or-may not seem magical to the uninformed user.
And really i think the "Classic" lisp way to loop is loop, not recursion.
Both, I think (from long ago memories). The "modern" loop macro (which is probably Turing complete like I seem to remember people saying format is :-) is I think a relatively new thing, I overhead a lot of discussion about its design in the early '80s.
Although it probably had precursors, mainline Lisp, now Common Lisp, is decidedly multi-paradigm, there were even sops thrown to FORTRAN programmers as I recall, probably back from when there were only a very few computer languages in existence (heck, LISP's first implementation, on a vacuum tube computer, was as FORTRAN subroutines). So overt things like loop are in theory idiomatic as well as recursion.
Comments
And didn't tail call optimization only become standard in Lisps with the advent of Scheme?
In any case, at Standard Chartered we didn't have tail call optimization with our Haskell dialect either. It didn't matter too much in practice, because you should be using combinators anyway. And when you are calling foldr or map, you do not care that somewhere hidden away they are implemented with a loop in C++, as long as they behave right.
Well SC's proprietary compiler is probably different, but GHC is self-hosted (the runtime system is C but the compiler is implemented in Haskell) and the map and fold functions in Prelude are recursive. Here's the source code for `map` in Prelude:
But it is definitely still true that explicit recursion is discouraged as being too 'low-level' for most Haskell code and it's preferable to use higher-order functions instead.Yes, Standard Chartered's compiler a bit different from ghc. That's mostly for historical reasons.
Yes, GHC can and does just use the recursive goodness, and compile it away to no-stackframe-adding jumps.
Indeed, and as far as I know Scheme JVM implementations, which I haven't looked at in a long while, either do it per the spec and are slow, SISC reputedly, died about the time I might have started using it, or go through contortions like Kawa to do the best you can. Don't know about JScheme, it was dead before then, and I just noticed Bigloo will compile to the JVM, adding one to the list of 4.
Yup. The CL spec does not require TCO. Some implementations only do TCO on self calls, so no mutual recursion.
And really i think the "Classic" lisp way to loop is loop, not recursion.
Scheme forces the point and requires full TCO.
Most CL implementations will do more TCO than on self calls or mutual recursion. Most support full TCO, with language limitations.
The ones that don't provide any form of TCO are old Lisp Machine implementations and ABCL on the JVM.
SBCL, OTOH, provides full TCO.
Some older overview about Common Lisp implementations and their TCO support:
http://0branch.com/notes/tco-cl.html
I seem to recall it depending on compiler settings whether sbcl does tco. Which means you probably don't want to rely on it in general unless you are okay being locked to a specific implementation and specific optimization settings that may-or-may not seem magical to the uninformed user.
There is Common Lisp software which needs TCO and only runs in TCO supporting implementations.
And really i think the "Classic" lisp way to loop is loop, not recursion.
Both, I think (from long ago memories). The "modern" loop macro (which is probably Turing complete like I seem to remember people saying format is :-) is I think a relatively new thing, I overhead a lot of discussion about its design in the early '80s.
Although it probably had precursors, mainline Lisp, now Common Lisp, is decidedly multi-paradigm, there were even sops thrown to FORTRAN programmers as I recall, probably back from when there were only a very few computer languages in existence (heck, LISP's first implementation, on a vacuum tube computer, was as FORTRAN subroutines). So overt things like loop are in theory idiomatic as well as recursion.