Re: practical functional programming

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

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