Summary: functional programming of graph algorithms (long) 
Author Message
 Summary: functional programming of graph algorithms (long)

Here is my summary of responses on functional programming of graph algorithms.

Quote:
> 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:

 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


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

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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.

------------------------------------------------------------------------------

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

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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 .

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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.

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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):

 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}
)

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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 ...

read more »



Sat, 27 Nov 1993 22:07:46 GMT  
 Summary: functional programming of graph algorithms (long)

   Here is my summary of responses on functional programming of graph algorithms.


   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.



Sun, 05 Dec 1993 12:17:55 GMT  
 Summary: functional programming of graph algorithms (long)


   >> Here is my summary of responses on functional programming of graph algorithms.

   >>
   >> > 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:

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.

--

                                                Hitachi, Ltd.
Voice: +81-492-96-6111/6112 (Ext. 6328)         Hatoyama, Saitama  350-03
Fax:   +81-492-96-6005                          JAPAN
--

                                                Hitachi, Ltd.
Voice: +81-492-96-6111/6112 (Ext. 6328)         Hatoyama, Saitama  350-03
Fax:   +81-492-96-6005                          JAPAN



Mon, 06 Dec 1993 11:01:47 GMT  
 Summary: functional programming of graph algorithms (long)
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:

        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."

Quote:
}

Paul S. Barth


Tue, 07 Dec 1993 16:54:56 GMT  
 Summary: functional programming of graph algorithms (long)

You might also look at the following paper:


        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.


==========================================================================



Sat, 11 Dec 1993 22:29:16 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. functional programming formulation of graph algorithms

2. Functional I/O Summary (Long!)

3. Which algorithm description techniques are appropiate in functional programming

4. summary on developing functional parallel program

5. Functional Programming and Communicating Processes (SUMMARY)

6. Are there any archives for functional programs ? (SUMMARY)

7. SUMMARY: Debugging functional programs

8. Getting 10 year old started in programming, Summary (long)

9. Scientific programming in functional languages (LONG)

10. Lisp and Functional Programming Conference '90 (very long)

11. Lisp & Functional Programming '90 (very long)

12. functional.py 0.6 - Functional Programming in Python

 

 
Powered by phpBB® Forum Software