corvara@ztivax.UUCP (Dr Gerd Venzl) (06/11/91)
Here is my summary of responses on functional programming of graph algorithms. To remind you, in article <5332@ztivax.UUCP> I wrote: > Some months ago somewhere in the literature I found a statement like > > "Functional programming is not well suited for algorithms of graph > theory as these usually make frequent use of side effects." > > When I tried to write down a purely functional formulation of some > manipulations on binary decision diagrams I found that indeed to be > quite a difficult and unnatural task. Are there really fundamental > reasons for these difficulties to arise or is my vision and understanding > of graph algorithms just too imperative? Are there any published attempts > to give functional formulations of graph algorithms? Any opinions from > netland? As some people wondered where I found the above statement: it's in the concluding remarks of the following German (I'm sorry, netters) book on automatic complexity analysis of functional programs: @book(Zimmermann90a, author = {W. Zimmermann}, title = {Automatische Komplexit\"atsanalyse funktionaler Programme}, publisher = {Springer}, year = {1990}, volume = {261}, series = {Informatik-Fachberichte}, address = {Berlin} ) Below you find the (partially commented) responses I received. Thanks to anyone who replied. More answers have been posted to the net by U.S. Reddy (reddy@reddy.cs.uiuc.edu, article <REDDY.91May28195125@reddy.cs.uiuc.edu>) and T.M. Breuel (tmb@ai.mit.edu, <TMB.91May29174602@volterra.ai.mit.edu>). I do not repost these. While I received quite some hints and opinions there were (almost) no references given to related work. One might conclude that here we found a topic that is still worth publishing on. Torsten Roessel Siemens Corporate Research & Development Design Automation Department InterNet: roessel@ztivax.siemens.com ------------------------------------------------------------------------------ From: tmb@ai.mit.edu (Thomas M. Breuel) ------------------------------------------------------------------------------ Well, that statement was probably made by someone who didn't have much experience with functional programming. If you represent your graph as a "mess of pointers" and you don't have lazyness or side-effects in your language, you are in trouble. (In SML, you can use "ref" types to build mess-of-pointer data structures, if you really want to.) In a purely functional setting, you should take a more abstract approach: think about what the operations are you want to use and then about how to represent them. For example: signature GRAPH = sig type Graph type Node val nodes: Graph -> Node list val neighbors: Node -> Node list val with_edge: Graph * Node * Node -> Graph val without_edge: Graph * Node * Node -> Graph val without_node: Graph * Node -> Graph end Internally, you could represent graphs as adjacency matrices, sparse adjacency matrices, etc. No need to use a "mess-of-pointers" representation. COMMENT: as you use SML in your example, how would you implement these matrices efficiently in SML? Using functions of type Node * Node -> bool ? Using (nested) lists ? And then: the binary decision diagrams I was working on are very regular graphs (almost tree-like). It seems to me, that adjacency matrices are a too general and inefficient representation for these. ------------------------------------------------------------------------------ From: rmz@ifi.uio.no (Bjorn Remseth) Organization: University of Oslo, Institute of Informatics ------------------------------------------------------------------------------ It isn't really that difficult. A graph can be thougth of as a relation between nodes. Most graph algorithms work by either adding new relations (new edges) or modifying old ones. This is basically array updating. The trouble with pure functional programming languages is that an entire array has to be sent as an argument, mofigirf a little, and then sent on to the next part of the algorithm. When done stupidly this is very inefficient because the entire array has to be copied every time it is applied, this is why the array updates in graph algorithms are usually implemented with side effects. However, it is possible to determine when an array is not needed elsewhere and in those cases not do a copy but instead send the only array as the argument.. If you are a bit careful when designing your algorithms, it turns out that you in many cases can get away with almost no copying and thus quite effective code. So, essentially this boils down to a problem of efficient code generation for functional languages. A good book to check out for a general introduction to this field is "Functional Programming" by Anthony J. Field and Peter G. Harrision (ISBN 0 201 19249 7). You might also want to check out what the SISAL people at Livermore has done. SISAL is a functional programming language designed for numerical work. It generates very efficient code due to a small set of clever optimizations. You should contact John Feo (feo@lll-crg.llnl.gov) for more information about SISAL. ------------------------------------------------------------------------------ From: rockwell@socrates.umd.edu (Raul Rockwell) ------------------------------------------------------------------------------ Well, I'd call J a functional programming language, and it allows you to do a lot of "graph theory" work. Basically, you can represent a graph as a square two-dimensional array. I guess, I could say Aij is 0 for the case where there is no arc from i to j, and is 1 for the case where there is an arc from i to j. The binaries come with several pages of examples of this kind of stuff. (Not that the documentation that you can get via ftp is adequate). COMMENT: J version 2.9 for Sun-3, Sun-4 and a couple of other machines is available by anonymous ftp from watserv1.waterloo.edu (129.97.129.140) in directory languages/apl/j . ------------------------------------------------------------------------------ From: mmh@dcs.qmw.ac.uk (Matthew Huntbach) ------------------------------------------------------------------------------ I am not sure about functional programming, but a particular interest of mine is representing graph algorithms in parallel logic languages. You need to think of each vertex in the graph as a process and the edges as communication channels. You can then develop some very elegant declarative programs. Two references to papers of mine: Implementing a Graph-Colouring Algorithm in Parlog SIGPLAN notices, 24, 10 pp.80-85 Sep. 1989. A single-message distributed algorithm for minimal spanning trees. To appear in the First International Conference of the Austrian Centre for Parallel Computing, 1991. ------------------------------------------------------------------------------ From: S.R.Adams@ecs.southampton.ac (Stephen Adams) ------------------------------------------------------------------------------ I am interested in this problem. I have had many problems trying to rewrite algorithms in a functional style. Many of the algorithms are not graph algorithms as such, just clever imperative algorithms. I would like to see functional, *declarative* versions of these algorithms: 1. Closure of a set under a relation 2. Traversal of a graph 3. A functional solution to the O(nG(n)) union-find problem. [Robert Sedgewick, Algotithms 2ed, Addison Wesley 1988, p441-449] 4. A functional solution of Hopcroft & Tarjan's O(V) planarity test [Efficient Planarity Testing, J.ACM 21(4) Oct. '74 549-568] In one sense these problems are all easy. It is simply a matter of passing the mutable data structures as parameters. By writing one function for each control point in the imperative program it can be arranged that the variables used for the mutable data structures are suitable for in-place-update optimization. Programs written like this are using the functional paradigm as a poor tool for expressing an imperative algorithm and are consequently not very easy to read and understand. They are hardly declarative. ------------------------------------------------------------------------------ From: m89mph%ecs.oxford.ac.uk (Mark P. Harrison) ------------------------------------------------------------------------------ I don't know about the difficulty of functional languages and graph theory. I'm an undergraduate at Balliol College, Oxford, and thus was brought up with my first programming lessons on Orwell (Wadler, Bird : like Miranda), and would prefer to do my current (Modula-2) practicals in a functional language. If you mail me the problem you did on graphs, I'll see what I make of it, from the perspective of a functional programmer with MUCH LESS imperative experience COMMENT: Have a look at the algorithms in the following paper and try to reformulate them in a functional language (SML or at least non-lazy/eager evaluation scheme preferred): @article(Bryant86a, author = {R.E. Bryant}, title = {Graph-Based Algorithms for Boolean Function Manipulation}, journal = {IEEE Trans. on Computers}, year = {1986}, volume = {C-35}, number = {8}, pages = {677-691} ) ------------------------------------------------------------------------------ From: jl@cs.glasgow.ac.uk (John Launchbury) ------------------------------------------------------------------------------ A couple of years ago, I coded the double DFS algorithm for finding strongly-connected components algorithm in Lazy ML (Aho, Hopcroft and Ullman, in ``Data Structures and Algorithms'', describe it on page 224 and attribute it on page 229 to R. Kosaraju (1978, unpublished) and Sharir (1981, ``A Strong Connectivity Algorithm & its Application in Data Flow Analysis'', in Computers and Mathematics with Applications 7:1, pp. 67-72)). It took me a few hours to re-express it functionally, but I was very pleased at how concisely the algorithm may be expressed. Even more pleasing, however, is the fact that it enables us to pinpoint exactly the parts that need `imperative-like' features to be fully efficient. The algorithm is as follows. let rec cyclic es vs = snd (span (range (map swap es)) ([],[]) (snd (dfs (range es) ([],[]) vs))) and range [] w = [] || range ((x,y).xys) w = if x=w then y.range xys w else range xys w and dfs r (vs,ns) [] = (vs,ns) || dfs r (vs,ns) (x.xs) = if member vs x then dfs r (vs,ns) xs else let (vs',ns') = dfs r (x.vs,[]) (r x) in dfs r (vs',x.ns'@ns) xs and span r (vs,ns) [] = (vs,ns) || span r (vs,ns) (x.xs) = if member vs x then span r (vs,ns) xs else let (vs',ns') = dfs r (x.vs,[]) (r x) in span r (vs',(x.ns').ns) xs The function `cyclic' is given a list of edges and vertices (defining the graph). The complexity is O(n.n). To achieve O(n.log n) you need to do two things: first, represent the `visited' list as a tree. However this is not of itself enough: the functions `ins' and `outs' are linear to use and so they also cause the complexity to be O(n.n). In an implementation with finite functions (i.e. arrays with constant access time e.g. Haskell) these functions could be generated once (linear) and access would be constant thereafter. (In the imperative case, this corresponds to constructing an actual node in the heap from the abstract description of the graph). If both of these are done we get O(n.log n) for the whole thing. If we had updateable arrays to use instead of a `visited' list (single-threading analysis and all that jazz) then we can get O(n) as in the imperative case. In case you are not overly familiar with LML, here is an almost equivalent version in Orwell (very like Miranda): > cyclic es vs = snd (span ins ([],[]) (snd (dfs outs ([],[]) vs))) > where ins w = [x | (x,y) <- es; y=w] > outs w = [y | (x,y) <- es; x=w] > dfs = foldl . df > df r (vs,ns) x = (vs,ns), if x $in vs > = (vs', x:ns'), otherwise > where (vs',ns') = dfs r (x:vs,ns) (r x) > span = foldl . sp > sp r (vs,ns) x = (vs,ns), if x $in vs > = (vs', (x:ns'):ns), otherwise > where (vs',ns') = dfs r (x:vs,[]) (r x) Thus, the marking of the graph is the *only* place where the imperative algirithm wins. Hope this is of some use. ------------------------------------------------------------------------------- From: louk%tslwat@watmath.waterloo.edu (Lou Kates) Organization: Teleride Sage, Ltd., Waterloo ------------------------------------------------------------------------------- Could you please tell me what you find out. By the way, I find this hard to believe. For example, if you represent a graph by its adjacency matrix then the graph algorithm will be transformed into a matrix algorithm and functional languages like APL are very good at matrix manipulation. ------------------------------------------------------------------------------- From: mcphee@cs.utexas.edu (Nic McPhee) Organization: U. Texas CS Dept., Austin, Texas ------------------------------------------------------------------------------- Programming with graphs can actually be quite interesting and easy, especially if you are using a lazy langauge. The trick is building the graph in the first place, but once that's done everthing else is a piece of cake. Most people are familiar with circular lists (a simple form of graphs), e.g., ones = 1:ones (using Miranda) and the question is how to generalize this to more interesting graphs. I did this a few years ago when doing some work with circuits (the gates were the nodes and the wires the edges). My solution was to put the nodes in a list and include in each node its index in that list. This index could then be "dereferenced" to generate an "edge". As an example take the following definition of a fully connected graph with n nodes: node :: Node num [ node ] graph n = the_graph where the_graph = map build_graph [0..n-1] build_graph i = Node i [ the_graph!j | j<-[0..n-1]; j != i ] There very well may be even better ways of doing this. If this isn't terribly clear I apologize; it's been quite a while and I'm doing this from memory. If you'd like more (or clearer) information just poke me and I'll hunt up the old source code and try to be more coherent. ------------------------------------------------------------------------------- From: Jeremy.Gibbons@prg.oxford.ac.uk ------------------------------------------------------------------------------- Please summarize! COMMENT: Well, that's it all. Hope you're satisfied.
tmb@ai.mit.edu (Thomas M. Breuel) (06/19/91)
In article <5495@ztivax.UUCP> corvara@ztivax.UUCP (Dr Gerd Venzl) writes: Here is my summary of responses on functional programming of graph algorithms. >>> From: tmb@ai.mit.edu (Thomas M. Breuel) In a purely functional setting, you should take a more abstract approach: think about what the operations are you want to use and then about how to represent them. For example: signature GRAPH = sig type Graph type Node val nodes: Graph -> Node list val neighbors: Node -> Node list val with_edge: Graph * Node * Node -> Graph val without_edge: Graph * Node * Node -> Graph val without_node: Graph * Node -> Graph end Internally, you could represent graphs as adjacency matrices, sparse adjacency matrices, etc. No need to use a "mess-of-pointers" representation. COMMENT: as you use SML in your example, how would you implement these matrices efficiently in SML? Using functions of type Node * Node -> bool ? Using (nested) lists ? And then: the binary decision diagrams I was working on are very regular graphs (almost tree-like). It seems to me, that adjacency matrices are a too general and inefficient representation for these. The method of reverse diffs that I described in my previous posting is applicable to most data structures (remember: for algorithms converted from imperative languages, you pay only O(1) overhead using reverse diffs if you use data structures based on reverse diffs and a fully functional programming style). Probably, the simplest and most flexible data structure for computing the "neighbors" functions is a hash table that maps from nodes to node lists and is maintained using reverse diffs. Thomas.
kondoh@harl86.harl.hitachi.co.jp (Hidetaka KONDOH) (06/20/91)
In article <5495@ztivax.UUCP> corvara@ztivax.UUCP (Dr Gerd Venzl) writes: >> Here is my summary of responses on functional programming of graph algorithms. >> To remind you, in article <5332@ztivax.UUCP> I wrote: >> >> > Some months ago somewhere in the literature I found a statement like >> > >> > "Functional programming is not well suited for algorithms of graph >> > theory as these usually make frequent use of side effects." >> > >> > When I tried to write down a purely functional formulation of some >> > manipulations on binary decision diagrams I found that indeed to be >> > quite a difficult and unnatural task. Are there really fundamental >> > reasons for these difficulties to arise or is my vision and understanding >> > of graph algorithms just too imperative? Are there any published attempts >> > to give functional formulations of graph algorithms? Any opinions from >> > netland? Here is another paper discussing the way to formulate graph algorithms using a lazy functional language (Haskell) in fairly general setting: Yugo Kashiwagi & David S. Wise "Graph Algorithms in a Lazy Functional Programming Language" Technical Report No. 330, Computer Science Dept., Indiana University (April, 1991). And here I quote its abstract: Solutions to graph problems can be formulated as the fixed point of a set of recursive equations. Traditional algorithms solve these problems by using pointers to build a graph and by iterating side effects to arrive at the fixed point, but this strategy causes serious problems of synchronization under a parallel implementation. In denying side-effects, functional progamming avoids them, but it also preludes known algorithms that are uniprocessor-optimal. Functional programming provides another, translation scheme that computesthe fixed point without relying on the operational concept of "store". In this approach, laziness plays an essential role to build a cyclic data structure, a graph, and to implement iteration as streams. The resulting algorithm is not optimal on uniprocessors but, avoiding side-effects, the algorithm suggests a promising, more general approach to multiprocessor solutions. This paper might give the very just answer to your initial question and can be easily obtained through the report secretary of the department. The e-mail address of the first author is: kasiwagi@hcrlgw.crl.hitachi.co.jp And here is another paper relating your question: F. Warren Burton & Hsi-Kai Yang "Manipulating Multilinked Data Structures in a Pure Functional Language", Software Practice-Experience, Vol. 20, No. 11, 1167-1185 (November, 1990). This paper collects case studies of description of graph-like data structures in functional setting. -- Hidetaka KONDOH (kondoh@harl.hitachi.co.jp) Advanced Research Laboratory Hitachi, Ltd. Voice: +81-492-96-6111/6112 (Ext. 6328) Hatoyama, Saitama 350-03 Fax: +81-492-96-6005 JAPAN -- Hidetaka KONDOH (kondoh@harl.hitachi.co.jp) Advanced Research Laboratory Hitachi, Ltd. Voice: +81-492-96-6111/6112 (Ext. 6328) Hatoyama, Saitama 350-03 Fax: +81-492-96-6005 JAPAN
barth@au-bon-pain.lcs.mit.edu (Paul Barth) (06/21/91)
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. Barthswarup@mitre.org (Vipin Swarup) (06/25/91)
You might also look at the following paper: @InProceedings(Imperative-lambda-calculus, Author = "Swarup, V. and Reddy, U.S. and Ireland, E.", Title = "Assignments for applicative languages", BookTitle = "Proc. Conf. on Functional Programming Languages and Computer Architecture", Note = "(To appear)", Month = "August", Year = "1991" ) The paper proposes a framework for adding references and assignments to pure, strongly-typed functional languages without violating the semantic properties of the languages. Expressions do not have side-effects, and the extended languages are proper extensions of the assignment-free languages. That is, the denotational and operational semantics of lambda-abstraction/application and pairing/projection are exactly the same before and after the extension. References may be used to construct arbitrary data structures (including graphs). Shared data may be destructively modified, and the modifications are visible to other parts of the program without having to explicitly pass the new values to those program points. This is demonstrated by a program for unification. The formal language considered in the paper is called "Imperative Lambda Calculus" (ILC for short). The type system of ILC ensures that state-oriented computation is combined linearly, allowing an implementation in terms of a global store. Evaluation of well-typed programs is Church-Rosser. Thus, programs produce the same results whether an eager or lazy evaluation order is used (assuming termination). The benefits of this work include greater expressive power and efficiency (compared to applicative languages), while retaining simplicity of reasoning. ========================================================================== Vipin Swarup, MS A156 The MITRE Corporation Burlington Road Bedford, MA 01730. E-mail : swarup@mitre.org ==========================================================================