5 ms·
Why would there be one malloc() per iteration if you have tail-recursion? Also, isn't malloc() a misnomer for stack allocations?
by Peaker 15y ago
Why would there be one malloc() per iteration if you have tail-recursion?
Also, isn't malloc() a misnomer for stack allocations?
- jules 15y agoTail recursion has nothing to do with garbage collection in F#. You're going to have one allocation per iteration if you do e.g. a map over a list. In an imperative language you'd probably mutate the collection in place.
- eru 15y agoUnless, and I guess that's what ColinWright alluded to, you have extensive stream fusion that will get rid of intermediate data structures.
- jules 15y agoThat's something else entirely compared to tail call optimization, but yes some functional languages (e.g. Haskell) do this. I don't think F# does stream fusion though.
- loup-vaillant 15y agoI'd be surprised if the current implementation of F# didn't do anything of this sort. But as a language, I understand fusion is more difficult in ML than in Haskell: that's because ML is strict and non pure. Therefore, some of the assumptions you could do in a non-strict, pure language don't hold, and it may not be unconditionally true that ∀f, ∀g, map g ∘ map f == map (f ∘ g) because f or g could perform some side effect, or fail to terminate. (My example may be bogus, but I'm sure we can find some real one.)
- eru 15y agoFailure to terminate exists in Haskell, too.
- loup-vaillant 15y agoSure, but the order of evaluation do change something. For instance, infinite lists won't ever terminate, but taking the first 42 elements of an infinite list will terminate in Haskell, and not in ML. If you want to fuse the whole thing, it won't change the Haskell program, but it may change the ML one, by making it terminate an return the correct result! That's not an optimization any more, that's a language feature.
- eru 15y agoYes. Though the situation is only that rosy in Haskell under some circumstances. It's easy to get space leaks that make your program use O(run-time) memory, if you are not careful with the laziness.
- loup-vaillant 15y agoAgreed. My only point is that automatic fusion (stream, shortcut, and even inlining in general) "works" more often in a pure and lazy setting.
- gaius 15y agoIn this case, I believe not: http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.html#6654 http://java.sun.com/docs/books/jvms/second_edition/html/Over... You would not be using the stack for this.