tag:blogger.com,1999:blog-1779668156488517434.post401664390947516651..comments2017-06-19T22:10:43.052-07:00Comments on The Flying Frog Blog: Disadvantages of purely functional programmingJon Harrophttp://www.blogger.com/profile/11059316496121100950noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-1779668156488517434.post-64713902391139346972017-04-23T17:51:09.477-07:002017-04-23T17:51:09.477-07:00@erik: "I believe Chicken Scheme allocates co...@erik: "I believe Chicken Scheme allocates conses on the stack (via a cheney-on-the-mta esque compilation strategy), which would essentially be an unboxed 2-tuple."<br /><br />No it isn't! The JVM made the same mistake with escape analysis. Stack allocating temporaries turns out to be a relatively unproductive special case to optimise. It is more important to unbox data in the heap.<br /><br />@Sean Pietz: "This is confusing the concepts of purity and immutability. It's possible to use mutable data structures in purely functional code. Pure code has no "side-effects" but it can still have effects!"<br /><br />I have restricted consideration to fully persistent data structures, true. There are grey areas like Conchon and Filliatre's somewhat persistent disjoint union and that collection does offer excellent performance. So YMMV.<br /><br />@Michael Lewis: "Abstract out the interfaces that you expect from a graph and I think this becomes simpler and potentially faster depending on what underlying representation is used"<br /><br />Can you simplify the Haskell code I posted above to the point that it is as short as the Python I posted?<br />Jon Harrophttp://www.blogger.com/profile/11059316496121100950noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-14582266569398951482017-03-29T00:47:44.927-07:002017-03-29T00:47:44.927-07:00The graph argument is false, if you base algo on a...The graph argument is false, if you base algo on a particular underlying implementation. e.g. someone has written a bunch of algos that all assume a Rose-Tree. then the argument is really 'you shouldn't use a rose tree as a generic graph representation' ... which I'd agree with. Abstract out the interfaces that you expect from a graph and I think this becomes simpler and potentially faster depending on what underlying representation is used.Michael Lewishttp://www.blogger.com/profile/10292447833605301583noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-25051621613822633392016-12-07T06:24:27.483-08:002016-12-07T06:24:27.483-08:00And why is it this guy so bent on trashing haskell...And why is it this guy so bent on trashing haskell and pure fp. He seems bitter for some reason. Maybe tried to learn haskell, found it too difficult -- sour grapes?Sean Pietzhttp://www.blogger.com/profile/14807656164160758607noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-70396160988211333572016-12-06T20:53:59.537-08:002016-12-06T20:53:59.537-08:00This is confusing the concepts of purity and immut...This is confusing the concepts of purity and immutability. It's possible to use mutable data structures in purely functional code. Pure code has no "side-effects" but it can still have effects!Sean Pietzhttp://www.blogger.com/profile/14807656164160758607noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-68109159097609629402016-12-06T20:53:56.977-08:002016-12-06T20:53:56.977-08:00This is confusing the concepts of purity and immut...This is confusing the concepts of purity and immutability. It's possible to use mutable data structures in purely functional code. Pure code has no "side-effects" but it can still have effects!Sean Pietzhttp://www.blogger.com/profile/14807656164160758607noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-46604141235918568302016-12-06T05:08:54.056-08:002016-12-06T05:08:54.056-08:00@nicholas - do you mean that many operations are a...@nicholas - do you mean that many operations are associative? Unknownhttp://www.blogger.com/profile/11315548391043472529noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-20461821917106024032016-12-05T21:08:20.640-08:002016-12-05T21:08:20.640-08:00@"Jon Harrop":
You write:
> Yes. Th...@"Jon Harrop":<br /><br />You write:<br /><br />> Yes. The Haskell code is far more verbose for many reasons, one of which is that Haskell cannot express a solution to this problem succinctly.<br /><br />and then:<br /><br />> The type annotations are a major eyesore and repeating "joinAt" three times in the definition of that one function is absurd.<br /><br />The first excerpt has to be considered a kind of <i>assuming the conclusion</i>: if Haskell is incapable of succinctly expressing a solution, the result must of course be verbose.<br /><br />With regards to the types being an eyesore: Haskell has type annotations and Python until recently didn't; but if the type annotations were in Python, would they be better? If so, in what way?Jason Dusekhttp://www.blogger.com/profile/15702067426651391511noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-86410623489835162512016-12-05T21:07:32.729-08:002016-12-05T21:07:32.729-08:00This comment has been removed by the author.Jason Dusekhttp://www.blogger.com/profile/15702067426651391511noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-84137593225361161052016-12-05T21:06:24.859-08:002016-12-05T21:06:24.859-08:00This comment has been removed by the author.Jason Dusekhttp://www.blogger.com/profile/15702067426651391511noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-34484581716960628642016-12-05T14:13:50.437-08:002016-12-05T14:13:50.437-08:00Even F#, which sits on .NET which provides arbitra...<i>Even F#, which sits on .NET which provides arbitrary value types, still uses .NETâ€™s boxed tuples.</i><br /><br />F# will get value tuples soon.<br /><br />https://github.com/Microsoft/visualfsharp/pull/1043Villehttp://www.blogger.com/profile/14536129636589454560noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-84189665343295869352016-12-05T14:09:02.198-08:002016-12-05T14:09:02.198-08:00I believe Chicken Scheme allocates conses on the s...I believe Chicken Scheme allocates conses on the stack (via a cheney-on-the-mta esque compilation strategy), which would essentially be an unboxed 2-tuple.erikhttp://www.blogger.com/profile/16655394656517359717noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-32238768997888965132016-08-16T11:06:13.975-07:002016-08-16T11:06:13.975-07:00csharp codes is great coding site<a href="http://csharp.happycodings.com/" rel="nofollow">csharp codes</a> is great coding site<br />YouLoseBellyFathttp://www.blogger.com/profile/18175607118884749966noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-65893702090845294452016-06-29T05:00:30.488-07:002016-06-29T05:00:30.488-07:00That should be Choice < Bool , Int32 >.That should be Choice < Bool , Int32 >.Juleshttp://www.blogger.com/profile/15088902004921941111noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-84009653011741969082016-06-29T04:59:11.085-07:002016-06-29T04:59:11.085-07:00Is OCaml's strategy really close to optimal fo...Is OCaml's strategy really close to optimal for symbolic computing? I think it would be fairly easy to beat it with a type specialised representation. Algebraic data types are represented as a pointer to a tag (64 bit) + payload in OCaml. You can eliminate the tag by encoding the data constructor within the pointer (plenty of space on 64 bit). This eliminates 64 bits of space per value, and it gives you access to the constructor without a memory dereference, which would speed up pattern matching. This representation would not be possible with a uniform representation, as the GC wouldn't know how to scan such a pointer.<br /><br />In addition you could unbox tuples, and you could unbox algebraic data types when the payload fits directly in the remaining bits of the pointer. For example Choice would then not need any pointers on a 64 bit architecture.Juleshttp://www.blogger.com/profile/15088902004921941111noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-710063901901644412016-06-16T01:09:58.826-07:002016-06-16T01:09:58.826-07:00>> some communities (most notably Lisp) had ...>> some communities (most notably Lisp) had highly evolved (but wrong)<br />>> arguments as to why Lisp was good. It took me many years to figure<br />>> out what was wrong with these arguments.<br /><br />Can you elaborate on this? I, for one, am fascinated with this issue but haven't put in the years of thinking about it that you have.Andrew Webbhttp://www.blogger.com/profile/06437858049982584317noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-80346057153088316742016-06-10T10:33:06.632-07:002016-06-10T10:33:06.632-07:00@Jason: Yes. The Haskell code is far more verbose ...@Jason: Yes. The Haskell code is far more verbose for many reasons, one of which is that Haskell cannot express a solution to this problem succinctly. The type annotations are a major eyesore and repeating "joinAt" three times in the definition of that one function is absurd.<br />Jon Harrophttp://www.blogger.com/profile/11059316496121100950noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-8150166891349762552016-06-08T10:43:27.520-07:002016-06-08T10:43:27.520-07:00Ah, so you're removing the stuff about reading...Ah, so you're removing the stuff about reading the file and setting up the graph, the regex, &c from the Python. You have saved a few lines and I see how you get your 12 lines figure now. But we can also see the Python gains at least one line by not exporting a function; whereas the Haskell is a module intended to be re-used. To be fair you have to remove the module declaration, saving four or five lines, depending.<br /><br />There are many more characters in the Haskell answer, I suppose; but one is little accustomed to counting length of code that way.Jason Dusekhttp://www.blogger.com/profile/15702067426651391511noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-28957957618130282992016-06-08T06:16:26.802-07:002016-06-08T06:16:26.802-07:00@Jason: Here is an exact comparison showing just h...@Jason: Here is an exact comparison showing just how much longer the Haskell is.<br /><br />The Python (275 chars after trimming whitespace from the ends of lines):<br /><br />from sys import argv<br />import re<br /><br />T = set();<br />X = set();<br /><br />X.add(0);<br /><br />while len(X) != vertices:<br />crossing = set();<br />for x in X:<br />for k in range(vertices):<br />if k not in X and graph[x][k] != 0:<br />crossing.add((x, k))<br />edge = sorted(crossing, key=lambda e:graph[e[0]][e[1]])[0];<br />T.add(edge)<br />X.add(edge[1])<br /><br />and here is the 1,123 chars of Haskell):<br /><br />module Data.Graph.Inductive.Query.MST (<br />msTreeAt,msTree,<br />msPath<br />) where<br /><br />import Data.Graph.Inductive.Graph<br />import Data.Graph.Inductive.Internal.RootPath<br />import qualified Data.Graph.Inductive.Internal.Heap as H<br /><br />newEdges :: Ord b => LPath b -> Context a b -> [H.Heap b (LPath b)]<br />newEdges (LP p) (_,_,_,s) = map (\(l,v)->H.unit l (LP ((v,l):p))) s<br /><br />prim :: (Graph gr,Real b) => H.Heap b (LPath b) -> gr a b -> LRTree b<br />prim h g | H.isEmpty h || isEmpty g = []<br />prim h g =<br />case match v g of<br />(Just c,g') -> p:prim (H.mergeAll (h':newEdges p c)) g'<br />(Nothing,g') -> prim h' g' <br />where (_,p@(LP ((v,_):_)),h') = H.splitMin h<br /><br />msTreeAt :: (Graph gr,Real b) => Node -> gr a b -> LRTree b<br />msTreeAt v g = prim (H.unit 0 (LP [(v,0)])) g<br /><br />msTree :: (Graph gr,Real b) => gr a b -> LRTree b<br />msTree g = msTreeAt v g where ((_,v,_,_),_) = matchAny g<br /><br />msPath :: Real b => LRTree b -> Node -> Node -> Path<br />msPath t a b = joinPaths (getLPathNodes a t) (getLPathNodes b t)<br /><br />joinPaths :: Path -> Path -> Path <br />joinPaths p q = joinAt (head p) p q<br /><br />joinAt :: Node -> Path -> Path -> Path<br />joinAt _ (v:vs) (w:ws) | v==w = joinAt v vs ws<br />joinAt x p q = reverse p++(x:q)<br />Jon Harrophttp://www.blogger.com/profile/11059316496121100950noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-12187532647230756592016-06-08T06:03:56.842-07:002016-06-08T06:03:56.842-07:00This comment has been removed by the author.Jon Harrophttp://www.blogger.com/profile/11059316496121100950noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-54399386881366996392016-06-07T15:19:02.547-07:002016-06-07T15:19:02.547-07:00@"Sara Haberlin" If we remove the commen...@"Sara Haberlin" If we remove the comments, whitespace, module preamble and imports the Haskell implementation is just a little bit shorter -- 20 lines instead of 22.Jason Dusekhttp://www.blogger.com/profile/15702067426651391511noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-39865136495879654352016-06-06T07:57:35.419-07:002016-06-06T07:57:35.419-07:00You are very much right about many points.
At th...You are very much right about many points. <br /><br />At the risk of adding more abstract nonsense, I think there is a hidden layer of monoidal structure which is absolutely crucial and vastly underappreciated to any program. We are seeing it in the ST suggestion from Peaker to have <br /><br />forkSTArray :: STVector s a -> Int -><br /> (forall s1. STVector s1 a -> ST s1 o1) -><br /> (forall s2. STVector s2 a -> ST s2 o2) -><br /> ST s (o1, o2)<br /><br />That is a crucial point which generalizes to other problems, but I have not seen it being taken that seriouslyNicolashttp://www.blogger.com/profile/03434148024010872285noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-12594810823867720422016-06-06T06:35:16.781-07:002016-06-06T06:35:16.781-07:00Could you link to the original Quora question? I&#...Could you link to the original Quora question? I'd be curious to take a look. Thanks!Egg Syntaxhttp://www.blogger.com/profile/15885114986383394814noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-23988134783536312882016-06-05T15:05:13.424-07:002016-06-05T15:05:13.424-07:00This comment has been removed by the author.Arturo Hernandezhttp://www.blogger.com/profile/07181691728621375942noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-5625301704792219702016-06-05T14:17:48.111-07:002016-06-05T14:17:48.111-07:00On point (7) this looks to be more about lower lev...On point (7) this looks to be more about lower level languages vs higher level. Supercomputers tend to be programmed using C, C++, Fortran etc without a GC. The code is very optimised low level end of the language spectrum.<br /><br />FP languages are at a higher level. Its easier and quicker to solve more complex problems with them than low level languages. Most of the time CPU cycles are cheaper than developer cycles. Hence premature optimisation being an anti-pattern.<br /><br />I use F# rather than Haskell but I don't recognise your observation that parallelism in FP being unpredictable and often not resulting in a speedup. FP makes parallelisation easier and safer. It can produce a significant speedup especially for embarrassingly parallel problems. This helps tip the cycles balance towards FP lanaguages.Anthony Lloydhttp://www.blogger.com/profile/02809057125332985175noreply@blogger.comtag:blogger.com,1999:blog-1779668156488517434.post-53129264907224027922016-06-05T09:03:23.008-07:002016-06-05T09:03:23.008-07:00For point (3) FP has a completely different way of...For point (3) FP has a completely different way of handling shared state. Shared/global state is represented by a reference to immutable data structures which is updated atomically. After seeing the simplicity and correctness of this I begin to question that OO in memory database and caching systems are valid without a large degree of cross collection locking. These complex dependencies lead to concurrency bugs that are very hard to reason about and solve.Anthony Lloydhttp://www.blogger.com/profile/02809057125332985175noreply@blogger.com