🚀 go-pugleaf

In article <TMB.91May29174602@volterra.ai.mit.edu> 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.