boyle@ANTARES.MCS.ANL.GOV (10/02/89)
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. 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. I would call such a demonstration a "demonstration of parity" between functional and conventional programming. I believe that several demonstrations of parity on programs for solving real problems would remove a large barrier to the use of functional programming, and encourage applications scientists and programmers to consider fp on its (obvious) merits. How about some discussion on this topic? Does anyone out there agree or disagree with these sentiments? Is anyone out there working on demonstrations of parity, or better yet, has anyone achieved some? 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. Jim Boyle boyle@mcs.anl.gov
grunwald@foobar.colorado.edu (Dirk Grunwald) (10/02/89)
Luddy Harrison at the University of Illinois, CSRD, has a parallelizing and vectorizing scheme compiler. There's a couple of tech reports describing his techniques. It's not functional, but it's certainly interesting. Dirk Grunwald -- Univ. of Colorado at Boulder (grunwald@foobar.colorado.edu)
wlm@archet.UUCP (William L. Moran Jr.) (10/03/89)
Unfortunately, it is (in general) not true that functional programs are as efficient as procedural programs. This is one of the problems with functional programs - not that they are less efficient than programs written in more common languages - but that the proponents of functional programs try to claim that they are not. The other advantages more than outweigh this, and the difference gets less and less every day (and may well eventually be zero). I would agree that a demonstration that functional programs are as efficient in some areas as other programs is a good idea, but do not oversell - in the short run it may help, but in the long run it will only discourage people. Bill -- arpa: moran-william@cs.yale.edu or wlm@ibm.com uucp: uunet!bywater!acheron!archet!wlm or decvax!yale!moran-william ------------------------------------------------------------------------------- An audience of teen-age boys naturally likes the idea of running around with naked women and doing LSD while listening to Hendrix and The Who. The Wall Street Journal 8/17/89
markv@phoenix.Princeton.EDU (Mark T Vandewettering) (10/03/89)
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)
ted@nmsu.edu (Ted Dunning) (10/04/89)
In article <10684@phoenix.Princeton.EDU> markv@phoenix.Princeton.EDU (Mark T Vandewettering) writes:
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.
could you post something on this? say some code/discussion on how you
did it?
--
ted@nmsu.edu
remember, when extensions and subsets are outlawed,
only outlaws will have extensions or subsets