tag:blogger.com,1999:blog-22587889.post1207804244365342664..comments2024-02-11T13:21:47.930+05:30Comments on Ruminations of a Programmer: To Tail Recurse or NotAnonymoushttp://www.blogger.com/profile/01613713587074301135noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-22587889.post-54325833962871331872008-10-10T21:13:00.000+05:302008-10-10T21:13:00.000+05:30Ricky -Only one point .. map is an order preservin...Ricky -<BR/>Only one point .. map is an order preserving transformation, i.e. the result collection needs to preserve the order of elements according to the original collection. With Scala library List.map implementation that uses ListBuffer, you cannot guarantee this order efficiently during the gathering phase of the parallel map implementation. This can be done more efficiently using Arrays. I had <A HREF="http://debasishg.blogspot.com/2008/06/playing-around-with-parallel-maps-in.html" REL="nofollow">blogged</A> on this before.Anonymoushttps://www.blogger.com/profile/01613713587074301135noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-14785227985238211212008-10-10T18:45:00.000+05:302008-10-10T18:45:00.000+05:30From what I can gather, you can already do that fo...From what I can gather, you can already do that forking. Unless the side effect escapes the implementation of map, it's quite safe to run it in parallel, i.e., it's reentrant.Ricky Clarksonhttps://www.blogger.com/profile/13845104548520132930noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-73932410765870501282008-10-10T18:00:00.000+05:302008-10-10T18:00:00.000+05:30"As a parallel map will do things in a different o...<I>"As a parallel map will do things in a different order than a sequential map, it's not generally safe to take a possibly-side-effecting mapping and make it work in parallel."</I><BR/><BR/>Are you talking about the input function of map being a side-effected one ? I think it is not a common practice - the function which you use in a map is strongly recommended to be side-effect-free. Otherwise map-reduce will not work.<BR/><BR/><I>"Also, the fact that List.map uses a ListBuffer has no bearing on what ParallelList.map (or List.parallelMap) might use."</I><BR/><BR/>The point I was trying to make is that had the implementation been functional (without any mutating data structure), I could have forked the function over the collection elements in parallel, possibly using actors. And then reduced them to a new collection. Refer to pmap implementation in Erlang. In the standard Scala List.map it is not possible, since it uses ListBuffer. It could have been possible if we used an Array instead, but in that case we would lose out on the performance, since Array.toList is O(n), as opposed to ListBuffer.toList, which is O(1).Anonymoushttps://www.blogger.com/profile/01613713587074301135noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-88444078324956839682008-10-10T17:50:00.000+05:302008-10-10T17:50:00.000+05:30As a parallel map will do things in a different or...As a parallel map will do things in a different order than a sequential map, it's not generally safe to take a possibly-side-effecting mapping and make it work in parallel.<BR/><BR/>Also, the fact that List.map uses a ListBuffer has no bearing on what ParallelList.map (or List.parallelMap) might use.Ricky Clarksonhttps://www.blogger.com/profile/13845104548520132930noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-63585687946080602172008-10-10T17:44:00.000+05:302008-10-10T17:44:00.000+05:30"when there's no benefit from writing the imperati...<I>"when there's no benefit from writing the imperative version"</I><BR/><BR/>Sure .. for Scala implementation, there were 2 forces at play :<BR/>1. JVM is not the best of the platforms for functional programming (at least not yet .. tail recursion .. will it come with Java 7 ?)<BR/>2. Extracting the max of performance with the container classes, for which they had to go the imperative way.<BR/><BR/>In that process however, they have lost on the concurrency issue. Functional implementations are more easily parallelized, e.g. pmap implementation of Joe in Erlang. Mutating ones are not. List.map in Scala uses ListBuffer - hence u cannot parallelize map easily in Scala.Anonymoushttps://www.blogger.com/profile/01613713587074301135noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-85501001225741339532008-10-10T17:32:00.000+05:302008-10-10T17:32:00.000+05:30From my observation, only poor Haskell programmers...From my observation, only poor Haskell programmers frown at monadic code. That said, when there's no benefit from writing the imperative version, there's no benefit from writing the imperative version.Ricky Clarksonhttps://www.blogger.com/profile/13845104548520132930noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-60009629769976727722008-10-10T17:21:00.000+05:302008-10-10T17:21:00.000+05:30"I think you're overestimating the cost of using s...<I>"I think you're overestimating the cost of using something like ST monad"</I><BR/><BR/>I think it is more of a mental setup working with Haskell - I have seen purists in Haskell world, frowning upon monad usage. But I do realize that the implementation cost is not much, and is statically verifiable.<BR/><BR/><I>"Don't you prefer this version of map to the first Scala version"</I><BR/><BR/>Sure I do and I like the terseness. Here is the corresponding Stream.map in Scala, not as terse, but still enough:<BR/><BR/>def map[B](f: A => B): Stream[B] =<BR/> if (isEmpty) Stream.empty<BR/> else Stream.cons(f(head), tail map f)Anonymoushttps://www.blogger.com/profile/01613713587074301135noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-46275244568409131772008-10-10T17:10:00.000+05:302008-10-10T17:10:00.000+05:30"but it does not feel idiomatic to do side-effecte...<I>"but it does not feel idiomatic to do side-effected programming in purer languages like Haskell."</I><BR/><BR/>Sure, that's the point !! We want to encourage keeping your style pure.<BR/><BR/>That said, I think you're overestimating the cost of using something like ST monad : it's just a matter of putting "runST" before monadic code that looks very much like imperative code in a traditional language.<BR/><BR/>There are some algorithms that are best written with mutable state, but they mostly use localized state that can be restricted to a ST function properly, getting the performance benefits without compromising the purity of the rest of your code.<BR/><BR/><I>"But Scala, unlike Haskell, is NOT lazy, by default."</I><BR/><BR/>I didn't say anything about the lazyness of Scala, just that one other way to get the same memory performance as tail-recursion in situation where you can't use tail-recursion can be lazy evaluation without the need for local mutation.<BR/><BR/>Don't you prefer this version of map to the first Scala version :<BR/><BR/>map f [] = []<BR/>map f (x:xs) = f x : map f xsJedaïhttps://www.blogger.com/profile/16447976353069828503noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-24277876768538167842008-10-10T16:43:00.000+05:302008-10-10T16:43:00.000+05:30"All pure languages have generally ways to do that...<I>"All pure languages have generally ways to do that too."</I><BR/><BR/>Sure .. but it does not feel idiomatic to do side-effected programming in purer languages like Haskell. OTOH in non-pure languages like Scala, you don't feel out of the way to do localized mutation, as Scala.List does for most of its functions.<BR/><BR/><I>"map in Haskell isn't written in tail-recursive style but still execute in constant stack space thanks to the evaluation model (lazy evaluation)."</I><BR/><BR/>In Scala we have scala.Stream, which is a lzy List implementation. But Scala, unlike Haskell, is NOT lazy, by default.Anonymoushttps://www.blogger.com/profile/01613713587074301135noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-17438820635289253382008-10-10T11:51:00.000+05:302008-10-10T11:51:00.000+05:30>It is not a functional implementation at all. ...<I>>It is not a functional implementation at all. In fact it adopts a clever use of localized <BR/>> mutation to achieve performance. Using mutation locally is a perfectly valid technique and a <BR/>> definite area where hybrid non-pure languages score over the purer ones.</I><BR/><BR/>All pure languages have generally ways to do that too. For instance Haskell allows you to do mutation and local state within the ST monad, a clever use of the type system ensure that the result is always externally pure (contrary to non-pure language where the proof of that is left for the developer). If you need to do really unsavory stuff, you can always revert to unsafe IO to have unrestricted side-effect (of course in this case you have to prove the external purity of your code by yourself).<BR/><BR/>It could also be noted that the map in Haskell isn't written in tail-recursive style but still execute in constant stack space thanks to the evaluation model (lazy evaluation). This is true of a lot of other interesting functions.Jedaïhttps://www.blogger.com/profile/16447976353069828503noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-62127485789886087452008-10-09T23:18:00.000+05:302008-10-09T23:18:00.000+05:30The Scala compiler optimises out tail recursion if...The Scala compiler optimises out tail recursion if it's a tail call to the same method. Most other cases are unsafe because of separate compilation, so JVM support for it is important.Ricky Clarksonhttps://www.blogger.com/profile/13845104548520132930noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-27279232132363880872008-10-09T22:59:00.000+05:302008-10-09T22:59:00.000+05:30Does the Scala compiler optimize for tail recursio...Does the Scala compiler optimize for tail recursion? Because if it doesn't, using recursion may not be a good idea actuallyRicardo Limahttps://www.blogger.com/profile/10051265214145371756noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-79194537715453683372008-10-09T18:42:00.000+05:302008-10-09T18:42:00.000+05:30If tail call optimisation could be efficiently don...If tail call optimisation could be efficiently done in the JVM, Clojure would have it.Anonymousnoreply@blogger.com