Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!mp.cs.niu.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!m!reddy From: reddy@reddy.cs.uiuc.edu (Uday S. Reddy) Newsgroups: comp.lang.functional Subject: Re: functional programming formulation of graph algorithms Message-ID: Date: 30 May 91 01:12:34 GMT References: <5332@ztivax.UUCP> Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager)) Organization: /home/reddy/reddy/.organization Lines: 57 In-Reply-To: tmb@ai.mit.edu's message of 29 May 91 21: 46:02 GMT Nntp-Posting-Host: reddy.cs.uiuc.edu In article tmb@ai.mit.edu (Thomas M. Breuel) writes: Researchers are working on notations for expressing sequentiality constraints so that compilers can update data structures in place. See the proceedings of the upcoming FPCA, for example. I think this is the wrong approach. Using data structures based on reverse diffs (as in RCS), an update involving side effects: val new_graph = (Graph.update_add_edge(graph,from,to); graph) is no more efficient (except for possibly a small, constant time overhead) than a more functional formulation: val new_graph = Graph.with_edge(graph,from,to) ---------- I just forgot how touchy this subject is. I cannot get into a long debate at this time, but some clarifications. I don't recall recommending "side effects" of any kind. The work I referred in the above quote uses pure functional languages. Additional sequentiality annotations are added so that compilers can implement them efficiently. I wasn't referring to the work of Swarup, Ireland and me, which also happens to appear in the upcoming FPCA. Our work uses a different approach with explicit assignments. But, it too does not involve "side effects". If you believe there is no problem in dealing with updates in functional languages, take a standard text book on algorithms and write the interesting algorithms in a functional language using your favorite techniques. ("interesting" means using updates in an interesting way). Then answer the following questions: - Are the data structures represented as abstractly as in the imperative programs? - Do these data structures use the language's storage management or do you need to manage the storage explicitly? - Are the algorithms as efficient as the imperative versions? - Are they as "convenient" as the imperative versions? For example, do they involve passing an inordinate number of arguments while the corresponding imperative versions don't? If you are happy with your answers to all these questions, publish your results! -- Uday Reddy Department of Computer Science University of Illinois 1304 West Springfield Avenue Urbana, IL 61801.