Re: Parity with conventional programs

[Mark T Vandewettering <phoenix!markv@princeton.edu>]

In article <8910020245.AA06270@solaria.mcs.anl.gov> boyle@ANTARES.MCS.ANL.GOV writes:
>It seems to me that one barrier to the wider acceptance of functional
>programming methodology, especially by scientists and programmers
>interested in applications, is the perception that functional programs 
>*necessarily* sacrifice efficiency for simplicity, clarity,
>adaptability, etc.

This is indeed ironic, because it is precisely the qualities of
simplicity, and clarity which allow optimizations to take place.  It is
far easier to reason about the meaning of programs and their correctness
in a functional language than it is in more traditional super computer
languages such as FORTRAN.

>I also believe that the time is ripe to attempt to demonstrate that
>this is NOT the case--that one can write in the functional style and
>still obtain programs that execute as fast (or faster) and that use as
>little storage as do well-written procedural programs on the same
>hardware.  

This thesis has gone along way towards being proven, but as you say,
more work could be done.  I see two major hindrances against using
functional programming in a scientific or industrial setting.

	1.	There are few good implementations of functional
		programming environments.  While the languages
		themselves are simple and elegant, often using them is
		not.  Alot of work remains to be done with these.

	2.	There is a lack of practical experience in developing
		solutions to problems.  Algorithm books are often
		expressed solely in terms of solutions that utilize 
		side effects, and there are certainly no great stores
		of subroutines for reuse as there is in FORTRAN.

There have been some results which have been encouraging with regards to
comparing space/time complexity of functional solutions to those
requiring arrays (primarily with sorting) but many open problems remain.
A non-tremendously recent SIGPLAN gave a list of several open problems
for which efficient (as efficient as traditional languages) solutions
were not known to exist for functional programming languages.  Most of 
the problems boiled down to simulating a ram memory, with update and 
access operations in constant time.  A demonstration of how these might 
be accomplished would be a good start...

>Terence Harmer (now at Queens University, Belfast) and I have been
>working toward this goal at Argonne over the past year using
>automated program transformation techniques.  We are within sight of
>the goal for several specifications for numerical and non-numerical
>problems of practical interest.  We express these specifications in
>pure Lisp (lambda calculus); some use higher order functions.  We
>transform them into Fortran or C programs for sequential, vector,
>and/or parallel computers.  We'd like to hear from others working
>along similar lines.

The work sounds interesting.  One of the major hindrances to overcome
for many problem is to find effective alternatives to using arrays, or 
to demonstrate how "functional arrays" can be effectively used for a 
wide variety of problems.  An interesting problem that I recently
"rediscovered" was to implement Conway's "life" cellular automaton in a
functional language.  Using program transformations, it is a very
interesting problem, with many possible solutions that are interesting 
to parallelize.

I think the one big contribution of functional programming will be a
practical system for parallelizing programs, and providing a basis 
for machine scheduling and partitioning of programs that operate at
levels which were previously hard to attain.

More discussion folks?  I think alot could be said here...

Let me plug a fun book for a second:

	"Functional Programming for Loosely-coupled Multiprocessors"
	Paul Kelly, MIT Press

I find Kelly's approach interesting and intuitive, and yet I feel that
more practical work needs to be done to demonstrate the applicability of
the system.  I would also see more solutions to the problems of implicit
parallelism, allowing compilers to do task assignment and scheduling.

Mark VandeWettering (markv@acm.princeton.edu)