Newsgroups: comp.lang.functional Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!mintaka!barth From: barth@au-bon-pain.lcs.mit.edu (Paul Barth) Subject: Re: Summary: functional programming of graph algorithms (long) In-Reply-To: kondoh@harl86.harl.hitachi.co.jp's message of 20 Jun 91 03:01:47 GMT Message-ID: Sender: news@mintaka.lcs.mit.edu Organization: MIT Lab for Computer Science, Cambridge, Mass. References: <5495@ztivax.UUCP> <1865@harl86.harl.hitachi.co.jp> Date: 21 Jun 91 10:54:56 Lines: 48 I will present a paper at FPCA in August comparing functional and imperative solutions to a parallel graph problem. The comparison includes performance measurements taken on a variety of graphs. Our conclusions are that the imperative solution improves the functional solution in three ways: it is more storage efficient (of course); it is more declarative (surprise!); and it is more parallel (surprise!). The latter two results stem from "threading" required by functional programming: the only way to share state is for each function to return the modified state as a result. For example, the "visited" table (i.e., nodes seen so far) must be passed between each traversal function in a determinate order. However, in a traversal algorithm the order is immaterial---correctness only depends on the first process reaching a node leaving a mark. Threading forces an overspecification of the problem constraints, and thus is less declarative than imperative marking. Threading also serializes access to the visited table, even if we are marking different nodes, which, could be marked in parallel. The paper describes an extension to the functional language Id called M-structures, which allow imperative operations. To simplify programming, M-structure operations are implicitly atomic. For example, when updating a data structure (such as marking a node), the runtime system guarantees that only one function has access to the node. I am currently writing my thesis on M-structures, including programming constructs for ensuring atomicity over arbitrary expressions. The paper mentioned above includes a description of Id, M-structures, and the graph programs. It is currently available as the following tech report: @techreport{MStructures, author = "Paul S. Barth and Rishiyur S. Nikhil and Arvind", title = "{M-structures: Extending a Parallel, Non-strict Functional Language with State}", institution = "M.I.T. Laboratory for Computer Science, type = "Computation Structures Group Memo", 545 Technology Square, Cambridge, MA 02139 USA", number = 327, year = 1991, note = "To appear in Proc. Functional Programming Languages and Computer Architectures, Cambridge, MA, August 28-30, 1991." } Paul S. Barth