practical functional programming

practical functional programming

[Chris Hecker]

So, I've been reading some papers by Okasaki on functional data structures, and I've ordered his book.  I have some questions, and I don't mean these to be flame bait; they're honest questions from an imperative programmer trying to grok this functional thing.

First, let me say that I love the idea of higher order functions, currying, closures, variant types, pattern matching, gc, and the like.  I think I understand some of the power that comes with those techniques, and I'm eager to try them in a real sized project.

However, after reading Okasaki's papers about functional datastructures, I'm not sure I get why someone would go to all that trouble.  In other words, I can trivially write an O(1) queue using imperative languages (or imperative features of a funcional lanugage, like caml's queue.ml).  Okasaki goes to a _lot_ of trouble to implement an O(1) queue in a pure functional way, using all sorts of lazy optimizations and scheduling and whatnot.  He acheives O(1), but the constant is going to be rather large compared to shuffling a pointer/ref around in C/caml.

So, what does all this trouble buy you?  I vaguely understand how a purely functional language like Haskell might be more amenable to analysis and proof than C, but people jump through hoops to get that (read: IO monads in Haskell, Okasaki's datastructures).  Is it worth it?  Clearly the caml folks didn't think so because the standard library datastructures are destructively modifying.

I'm open minded, so I'm genuinely interested to know if the work of making something like a simple datastructure purely functional is more than an academic exercise, or if it pays back in real-sized production software.

Chris

Re: practical functional programming

[Chet Murthy]

Don't read Okasaki's book.  Read the first chapter of Xavier Leroy's
thesis.  First.

I don't mean to be flaming, and certainly, what I say, I'm sure, comes
from me, and not from Xavier, so please don't impute to him any of my
heat.

But there's a place for purity, and a place for impurity.  Sometimes,
pure code is _more_ complex and difficult-to-understand than impure
code.  It all depends.

And none of the arguments about how pure programs are easier to
analyze have ever held up, unless you're talking about "append".
Otherwise, well, complex programs solving complex problems are hard to
analyze.  Period.

I've built mission-critical transaction-processing systems in Perl and
Java, and I've debugged them in C/C++.  I've written _large_ CAML
programs, as well as even _larger_ SML programs.

There's no difference.  Just that in CAML, you can use purity more
easily, when yuou want, and often, purity makes for faster programs.

No hard and fast rules.  Just rules of thumb.  Experience.  Taste.
Discipline.

--chet--

Re: practical functional programming

[John Max Skaller]

Chris Hecker wrote:

> I'm open minded, so I'm genuinely interested to know if the work of 
> making something like a simple datastructure purely functional is more 
> than an academic exercise, or if it pays back in real-sized production software.

Depends on the application. Consider for example a browser in which
when you hit the 'back' button, you want to go back to the same
state as previously: with purely functional data structures attached
to a state object, going back is a simple matter of popping the state
object from a stack (and re-rendering :-)

This is not so easy to do with a more extensively mutable state object.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: practical functional programming

[Francisco Reyes]

On Fri, 03 Nov 2000 14:44:41 -0800, Chris Hecker wrote:

>I'm open minded, so I'm genuinely interested to know if the work of making something like a simple
>datastructure purely functional is more than an academic exercise, or if it pays back in real-sized
>production software.

I will be waiting to see what kind of responses you get but
wanted to add my own feedback.
I got looking at Ocaml because a program I use was written on
it, Unison.

I ordered a book, The Functional Approach to Programming, and
although it does help somewhat it is too theoretical/math
oriented. So are most of the docs and examples I have seen. 

I don't see many pratical-simple examples of Ocaml and so far
the things I have thought of trying Ocaml took me too long to
figure them out. Even with no pratical previous perl experience
using a Perl book in less than a day I had got the basics and
was on my way to been productive. I am not sure this could be
possible with Ocaml.

Is Ocaml best for larger more complex tasks?



francisco
Moderator of the Corporate BSD list
http://www.egroups.com/group/BSD_Corporate

Re: practical functional programming

[Jean-Christophe Filliatre]

In his message of Fri November 3, 2000, Chris Hecker writes: 
> However, after reading Okasaki's papers about functional
> datastructures, I'm not sure I get why someone would go to all that
> trouble. In other words, I can trivially write an O(1) queue using
> imperative languages (or imperative features of a funcional
> lanugage, like caml's queue.ml). Okasaki goes to a _lot_ of trouble
> to implement an O(1) queue in a pure functional way, using all sorts
> of lazy optimizations and scheduling and whatnot. He acheives O(1),
> but the constant is going to be rather large compared to shuffling a
> pointer/ref around in C/caml.
> 
> So, what does all this trouble buy you?  

The answer to your question is "persistence".

Indeed, there is no need  using a purely functional datastructure when
there  is  an  easy  imperative   solution.  And  I  think  that  most
programmers  on  this  mailing  list  are  not  extremists  of  purely
functional programming and will agree with me on that point.

But there  is sometimes  a need for  persistence when  programming. As
explained  in  Okasaki's  book,  persistence  is  the  property  of  a
structure to remain valid after  an operation (e.g. an insertion) have
been performed on it. Purely functional datastructures are persistent.
(The  converse is  not true:  you may  have  persistent datastructures
which are implemented in a purely functional way.)

Consider for instance  the problem of traversing the  syntax tree of a
program to  do type  checking. If  the language require  the use  of a
symbol table, you may choose  between a persistent or a non-persistent
implementation. With  a non-persistent implementation,  you are likely
to add things in your table  before going into a deeper subterm and to
remove them when done with the subterm, like this:

  | Let (x,e1,e2) -> 
      let ty1 = typecheck e1 in
      add x ty1;
      let ty2 = typecheck e2 in
      remove x;
      ty2

With a  persistent datastructure, you  only have to carry  the current
symbol table along and you never have to undo anything:

  | Let  (x,e1,e2) -> 
      let ty1 = typecheck st e1 in
      typecheck (add st x ty1) e2

This is a very silly example  but there are many real situations where
persistence is needed  (I encountered many of them  in practice). Then
you look  for efficient  persistent datastructures and  Okasaki's book
provides good  practical solutions  for some of  them and,  above all,
generic methods to build others.

Hope this helps,
-- 
Jean-Christophe FILLIATRE
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr

Re: practical functional programming

[Chris Hecker]

>This is a very silly example  but there are many real situations where
>persistence is needed  (I encountered many of them  in practice).

That may be a silly example, but it makes a lot of sense to me and I could see making use of that property.

I guess my next question then would be related to efficiency: isn't there a lot of copying going on if you've got to make a new instance of your symbol table just to add an element?  How does this work out in practice?

Again, I'm not saying efficiency is the only metric for software, but it does concern me when I see a large datastructure copied.  Is there some sort of reference counted sharing going on, or are there actually two copies of the data in memory if you wrote your example in caml?

I guess my hope would be that in the case where you didn't reference the old datastructure ever again you would get performance close to the equivalent imperative datastructure.  In the case where you did reference both old and new you'd get performance similar to writing an "undo-able" imperative datastructure from scratch, possibly with an optimization for not accessing the old datastructure until the new one had been undone (like in your example, and I would assume that's the common case for using persistence).

Chris

Re: practical functional programming

[Michael Hicks]

> Depends on the application. Consider for example a browser in which
> when you hit the 'back' button, you want to go back to the same
> state as previously: with purely functional data structures attached
> to a state object, going back is a simple matter of popping the state
> object from a stack (and re-rendering :-)
> 
> This is not so easy to do with a more extensively mutable state object.

There was a paper on just this topic in this year's ICFP.  Check out:

The Influence of Browsers on Evaluators
http://youpou.lip6.fr/queinnec/Papers/webcont.ps.gz

Mike

-- 
Michael Hicks
Ph.D. Candidate, the University of Pennsylvania
http://www.cis.upenn.edu/~mwh            mailto://mwh@dsl.cis.upenn.edu
*There was a man who entered a local paper's pun contest; He sent in ten
*different puns, in the hope that at least one of the puns would win.  
*Unfortunately, no pun in ten did.

Re: practical functional programming

[Stephan Houben]

On Mon, 06 Nov 2000, Chris Hecker wrote:
 
> I guess my next question then would be related to efficiency: isn't there a lot of copying going on if you've got to make a new instance of your symbol table just to add an element?  

Well, one of the advantages of having a purely functional data structure is
that you can freely share substructures. So there is very little copying.
Because the updated structure shares most of its memory with the original
structure, holding on to both isn't prohibitively expensive.

Again, this makes it simple to "roll back" to a previous version.

> Again, I'm not saying efficiency is the only metric for software, but it does concern me when I see a large datastructure copied.

No copying. Just pointer sharing.

>  Is there some sort of reference counted sharing going on, 

Reference counting is a (bad) substitute for real garbage collection, such as
O'Caml has. No need for refcounting, since we have GC.

> or are there actually two copies of the data in memory if you wrote your
> example in caml?  

No, this is not the case. Most of the data is shared.

> I guess my hope would be that in the case where you
> didn't reference the old datastructure ever again you would get performance
> close to the equivalent imperative datastructure.

It depends on the data structure, but some of Okasaki's data structures come
close to this ideal.

> In the case where you did
> reference both old and new you'd get performance similar to writing an
> "undo-able" imperative datastructure from scratch, 

Writing an undo-able imperative data-structure is no easy job.
Most people would probably go for a functional data structure then.

For example: the new ReiserFs in Linux (journalling filesystem) needs
for its journalling a similar commit/roll-back functionality. Therefore, it
is based on balanced trees, which are a somwehat functional data structure.
(I definitely do not want to suggest that ReiserFs is somehow a purely
functional file system, just that the basic idea is somewhat similar to some
functional data structures.)

> possibly with an
> optimization for not accessing the old datastructure until the new one had
> been undone (like in your example, and I would assume that's the common case
> for using persistence).

I am afraid that compilers aren't that smart yet.

I think the bottom line is this: imperative datastructures are often (somewhat)
faster, but purely functional datastructures are more general. This shows the
importance of Okasaki's work: sometimes it is possible to have your cake and
eat it, too.

So now it is up to you to decide whether you need a purely functional or an 
imperative data structure. There is no hard&fast rule here: it depends
completely on the application. But the nice thing of O'Caml is that it gives you
the choice. Which is also the bad thing: if we were writing Perl, we would
almost always use hashes and not have to think about these issues.

Good luck with your decision,

Stephan

--  ir. Stephan H.M.J. Houben tel.
+31-40-2474358 / +31-40-2743497 e-mail: stephanh@win.tue.nl

Re: practical functional programming

[Xavier Leroy]

> That may be a silly example, but it makes a lot of sense to me and I
> could see making use of that property.  I guess my next question
> then would be related to efficiency: isn't there a lot of copying
> going on if you've got to make a new instance of your symbol table
> just to add an element?  How does this work out in practice?

That's where you need clever algorithmicians such as Chris Okasaki to
design persistent data structures with efficient operations --
ideally, as efficient as for equivalent non-persistent data structures
(i.e. modified in place).

To continue Jean-Christophe's symbol table example, persistent
dictionaries can be implemented by balanced binary trees (as in the
OCaml library module "Map").  Then, adding an entry to a symbol table
requires at most one branch of the tree to be copied, which takes time
and space O(log n); the other branches of the tree are simply shared
between the original and the modified symbol tables.

If you have efficiency concerns, it is interesting to compare the
Hashtbl and Map modules from the OCaml library.  Both implement the
dictionary data structure, one imperatively, the other in a purely
functional way.  You'll find that Map operations are a bit slower than
Hashtbl operations, but by a factor of 2 or less.  Moreover, the worst
case for maps is still O(log n), while hash tables can degrade to O(n).

For other data structures, it is much harder to achieve good
asymptotic complexity for persistent data structures; that's where the
kind of "tours de force" you see in Okasaki's book come into play.

> Again, I'm not saying efficiency is the only metric for software,
> but it does concern me when I see a large datastructure copied.  Is
> there some sort of reference counted sharing going on, or are there
> actually two copies of the data in memory if you wrote your example
> in caml?

Sharing is the key.  The beauty of immutable data structures is that
sharing is always safe.  With well-designed data structures, this can
lead to a lot more sharing of data in purely functional programs than
what you typically see in imperative programs.

A few more words on persistent, purely functional data structures.
They are very useful in a number of cases:

- When your application really needs to "go back in time".  Examples:
the "back" button on a Web browser; the "undo" facility of a text
editor; version control systems such as RCS or CVS; etc.  Of course,
you can implement this by state + undo logs, but after a while the
structure of the undo logs become quite complex and a purely
functional data structure starts to make a lot of sense.

- When your application needs to handle gracefully user interrupts
and unexpected exceptions.  Consider an interactive toplevel loop
such as Caml's.  In Caml Light, the symbol tables were implemented by
mutable hash tables.  Thus, the user could interrupt the system in the
middle of type-checking, when the symbol tables have been partially
updated.  I had to put a rollback mechanism to undo these changes on
user interrupt.  In effet, you need some atomic transaction mechanism.
In OCaml, the symbol tables are purely functional maps, with only one
reference holding the current stable symbol table.  The reference is
updated by one atomic assignment when the user input has been
successfully processed.  You can interrupt the processing at any time,
the system will always be in a consistent state.

- To implement a mathematical specification "to the letter".  E.g. you
have an interpreter, type-checker, proof system, program
transformation, etc, that is specified by inference rules or similar
mathematical notation, and you wish to implement the spec faithfully
and quickly.  Using purely functional data structures, the program is
often a direct transliteration of the specs.  Using imperative data
structures, you have to think more carefully about undoing
modifications at the right time, make sure that there is no sharing,
etc.

- To prove formally properties of a program, especially mechanically
checked proofs.  There are techniques to reason about imperative
programs directly, but often a rewrite to a purely functional style
makes it easier to "import" the program into a proof checker such as
Coq and prove properties about it.

This said, I agree with Chet that there is no reason to get religious
about purely functional data structures.  Use what works best for
you.  And indeed OCaml can support both styles, and its standard
library offers a mixture of functional and imperative data
structures.

- Xavier Leroy

Re: practical functional programming

[Chris Hecker]

Thanks to everybody for the great replies!

>Sharing is the key.  The beauty of immutable data structures is that
>sharing is always safe.

Ah, this makes sense.  How does the compiler "know" the datastructure is purely functional?  In other words, is there any way for me to get a type into a tree that has a mutable member (perhaps through an abstract type), and if so, what happens in that case?

Chris

Re: practical functional programming

[Thorsten Ohl]

Chris Hecker <checker@d6.com> writes:

> I guess my next question then would be related to efficiency: isn't
> there a lot of copying going on if you've got to make a new
> instance of your symbol table just to add an element?

Surprisingly little (if implemented properly, of course).  Ogasaki's
book was really a revelation for me ...

Once one has adopted the proper mindset, persistence can lead to very
concise and efficient programs.  I was amazed how well it works in a
non-trivial combinatorical applications (e.g.:
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/omega).  
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]

Re: practical functional programming

[Marcin 'Qrczak' Kowalczyk]

Mon, 06 Nov 2000 10:15:30 -0800, Chris Hecker <checker@d6.com> pisze:

> I guess my next question then would be related to efficiency:
> isn't there a lot of copying going on if you've got to make a new
> instance of your symbol table just to add an element?  How does
> this work out in practice?

It depends on how the symbol table is implemented.

With balanced binary trees element search costs log(N) and obtaining
an updated mapping costs log(N). Updating must copy the path from
the root to the place where the change is being made.

With hash tables search costs a constant time but obtaining an updated
mapping costs N.

There is a tricky idea providing fast arrays with a functional
interface. A mutable array is kept under a mutable reference.
Obtaining an updated array does the update in place and then replaces
the contents of the old reference by a data structure which refers
to the new copy and tells which element to replace by which old
value. So values from which other versions were derived behave as
before, even though their representation changes. Accessing older
versions becomes slower and slower as more updates are being made.

There is a complex imperative implementation here, especially as we
must deal with cases when the updated version is no longer used and
there is a chain of updates starting from an older copy. When versions
diverge too much, probably it's time to make separate copies. I'm
not sure how all details should be done. But once it is done, usage
of these arrays is completely functional.

> Is there some sort of reference counted sharing going on, or are
> there actually two copies of the data in memory if you wrote your
> example in caml?

Everything not explicitly copied is shared, but OCaml's implementation
of the garbage collector does not use reference counting.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

Re: practical functional programming

[Stephan Houben]

On Tue, 07 Nov 2000, Chris Hecker wrote:
 
> How does the compiler "know" the datastructure is purely functional?

It doesn't. Why would it have to?

> In other words, is there any way for me to get a type into a tree that has a
> mutable member (perhaps through an abstract type),

Yes there is. You can make a map that contains, for example,  
values of type `int ref' or `int array'.

> and if so, what happens in
> that case?

Well, as you already might know, O'Caml *never* copies anything unless
you explicitely tell it to. For example, the following session:

# let ar1 = [|1|];;
val ar1 : int arr# ar1.(0) <- # ar2;;
- : int array = [|2|]2;;
- : unit = ()  ay = [|1|]
# let ar2 = ar1;;
val ar2 : int array = [|1|]
# ar2;;
- : int array = [|1|] 
# ar1.(0) <- 2;;
- : unit = ()  
# ar2;;
- : int array = [|2|]

So I mutated ar1, but the update is reflected in ar2. In C++ speech, all
variables are implicitely "references" to the underlying object. ar1 and ar2
refer to the same object. If you want ar2 to be a new array, then you
have to use Array.copy to explicitely tell O'Caml that you want a new
array.

So yes, if I have a map map1, and I get an "updated" map2 from that, then
mutations to the objects held in map1 will be reflected in map2.

Stephan
-- 
ir. Stephan H.M.J. Houben
tel. +31-40-2474358 / +31-40-2743497
e-mail: stephanh@win.tue.nl

Re: practical functional programming

[Chris Hecker]

>> How does the compiler "know" the datastructure is purely functional?
>It doesn't. Why would it have to?

Right, I was being an idiot.  If it's got a ref in there that's ever updated, it just isn't functional.  I was somehow thinking...well, I don't know what I was thinking.  :)

Chris

Re: practical functional programming

[John Max Skaller]

Stephan Houben wrote:
> Reference counting is a (bad) substitute for real garbage collection, such as
> O'Caml has. No need for refcounting, since we have GC.

	I can't quite agree with that: reference counting is
a _different_ technique with different properties. In the right
circumstances it is faster than garbage collection, and permits
synchronous, well ordered finalisation. But it is only appropriate
where the 'skeleton' of the data structure is heirarchical, whereas
garbage collection works in general.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: practical functional programming

[Ken Wakita]

A circumstance where reference counting outperforms modern trace-based
collectors is where memory access cost is much higher than the
conventional memory system and thus memory access required for tracing
is much higher than the cost for counter maintenance.  One such example
is distributed environment.  Another maybe systems with very, very slow
memory such as file systems, persistent object systems, and PDAs.  I am
curious if there are other circumstances using conventional memory
system where reference counting is faster.

Ken Wakita
Tokyo Institute of Technology

John Max Skaller wrote:
> 
> Stephan Houben wrote:
> > Reference counting is a (bad) substitute for real garbage collection, such as
> > O'Caml has. No need for refcounting, since we have GC.
> 
>         I can't quite agree with that: reference counting is
> a _different_ technique with different properties. In the right
> circumstances it is faster than garbage collection, and permits
> synchronous, well ordered finalisation. But it is only appropriate
> where the 'skeleton' of the data structure is heirarchical, whereas
> garbage collection works in general.
> 
> --
> John (Max) Skaller, mailto:skaller@maxtal.com.au
> 10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
> checkout Vyper http://Vyper.sourceforge.net
> download Interscript http://Interscript.sourceforge.net

Re: practical functional programming

[John Max Skaller]

Ken Wakita wrote:
> 
> A circumstance where reference counting outperforms modern trace-based
> collectors is where memory access cost is much higher than the
> conventional memory system and thus memory access required for tracing
> is much higher than the cost for counter maintenance.  One such example
> is distributed environment.  Another maybe systems with very, very slow
> memory such as file systems, persistent object systems, and PDAs.  I am
> curious if there are other circumstances using conventional memory
> system where reference counting is faster.

I don't know how a trace-based collector works. Can you explain?
[Does this have something to do with a write barrier on pointer
stores?]


-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: practical functional programming

[Ken Wakita]

In message (<3A0EF904.C65AC976@ozemail.com.au>)
from John Max Skaller <skaller@ozemail.com.au>,
talking about "Re: practical functional programming",
on Mon, 13 Nov 2000 07:09:40 +1100

skaller> Ken Wakita wrote:
skaller> > 
skaller> > A circumstance where reference counting outperforms modern trace-based
skaller> > collectors is where memory access cost is much higher than the
skaller> > conventional memory system and thus memory access required for tracing
skaller> > is much higher than the cost for counter maintenance.  One such example
skaller> > is distributed environment.  Another maybe systems with very, very slow
skaller> > memory such as file systems, persistent object systems, and PDAs.  I am
skaller> > curious if there are other circumstances using conventional memory
skaller> > system where reference counting is faster.
skaller> 
skaller> I don't know how a trace-based collector works. Can you explain?
skaller> [Does this have something to do with a write barrier on pointer
skaller> stores?]

Trace-based collector (or tracing collector) is a name given to a
class of garbage collection algorithms that trace the object graph in
the heap.  It covers most of the garbage collection algorithms,
mark&sweep and copying.  If you incorporate generational techniques
probably you need to use write barrier.

Ken Wakita
Tokyo Institute of Technology

Re: practical functional programming

[STARYNKEVITCH Basile]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1287 bytes --]

>>>>> "John" == John Max Skaller <skaller@ozemail.com.au> writes:

    John> Stephan Houben wrote:
    >> Reference counting is a (bad) substitute for real garbage
    >> collection, such as O'Caml has. No need for refcounting, since
    >> we have GC.

    John> 	I can't quite agree with that: reference counting is a
    John> _different_ technique with different properties. In the
    John> right circumstances it is faster than garbage collection



Actually I will be picky and disagree with both John and
Stephan. Reference counting is a (generally poor) garbage collection
technique. See Lins and Jones' book on "Garbage Collection".

The appropriate mailing list is the garbage collection list
"http://www.iecc.com/gclist/" also archived at
"http://lists.tunes.org/mailman/listinfo"

Regards.

N.B. Any opinions expressed here are only mine, and not of my organization.
N.B. Les opinions exprimees ici me sont personnelles et n engagent pas le CEA.

---------------------------------------------------------------------
Basile STARYNKEVITCH   ----  Commissariat à l Energie Atomique 
DTA/LETI/DEIN/SLA * CEA/Saclay b.528 (p111f) * 91191 GIF/YVETTE CEDEX * France
phone: 1,69.08.60.55; fax: 1.69.08.83.95 home: 1,46.65.45.53
email: Basile point Starynkevitch at cea point fr 

Re: practical functional programming

[Hao-yang Wang]

>Haskell is a lazy language, with which we are supposed to ignore when (or 
>whether) an expression is going to be evaluated, at least most of the 
>time. As the result we have to give up all the side effects (i.e., I/O and 
>destructive data updates), because we have no idea on the order in which 
>these side effects occur. On the other hand, the ML family is strict.

People who complain that o'caml does not have a fixed evaluation order on 
function arguments should take a look at Haskell, things are much worse 
there. :-)

Hao-yang Wang

Re: practical functional programming

[Hao-yang Wang]

When you need to preserve the mutation history (or multi-history) of the 
data, Okasaki's data structures are useful. For other cases, I see 
nothing wrong in using mutable data structures.

>So, what does all this trouble buy you?  I vaguely understand how a purely 
>functional language like Haskell might be more amenable to analysis and 
>proof than C, but people jump through hoops to get that (read: IO monads 
>in Haskell, Okasaki's datastructures).  Is it worth it?  Clearly the caml 
>folks didn't think so because the standard library datastructures are 
>destructively modifying.

Haskell is a lazy language, with which we are supposed to ignore when (or 
whether) an expression is going to be evaluated, at least most of the 
time. As the result we have to give up all the side effects (i.e., I/O 
and destructive data updates), because we have no idea on the order in 
which these side effects occur. On the other hand, the ML family is 
strict.

I do not shy away from using side effects with o'caml. However, when I 
look back to the o'caml programs I wrote, I am always surprised in how 
pure they turned out to be: The side effects flock to a few places, 
usually at the top-most functions.

For a nice example on how the imperative features can help in writing a 
correct o'caml program, look at <http://caml.inria.fr/icfp99-contest/>.

Cheers,
Hao-yang Wang