home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.lang.functional
- Path: sparky!uunet!mcsun!sunic!diku!bombadil
- From: bombadil@diku.dk (Kristian Nielsen)
- Subject: Re: Maturing implementations of functional languages (and religion)
- Message-ID: <1992Jul19.151418.16386@odin.diku.dk>
- Sender: bombadil@ask.diku.dk
- Date: Sun, 19 Jul 1992 15:14:18 GMT
- References: <TMB.92Jul14175723@arolla.idiap.ch>> <NICKH.92Jul14151920@VOILA.VENARI.CS.CMU.EDU> <farrell.711165248@coral.cs.jcu.edu.au> <rk+mqkm@lynx.unm.edu> <farrell.711246506@coral.cs.jcu.edu.au>
- Organization: Department of Computer Science, U of Copenhagen
- Lines: 45
-
- farrell@coral.cs.jcu.edu.au (John Farrell) writes:
-
- > Certainly, functional languages have some properties which look like they
- >will slow the language down no matter what. On the other hand, we can write
- >functional and FORTRAN programs which produce exactly the same results on
- >exactly the same machine, so why shouldn't they both run in the same time.
- >While a functional program is slower than an equivalent procedural program, we
- >have to acknowledge that we haven't got the compiler technology right yet.
-
- I think there is another aspect that is often overlooked when lazy
- functional programs are deemed slower than en equivalent program in a
- more traditional language such as C or Pascal. I often find myself
- writing 'better' programs in say Haskell to solve a particular problem
- than I would have done otherwise. A very common example of this is the
- tendency to have artificial constrains on the size of data structures
- used in programs, like the dreaded maximum identifier length in
- compilers or 256 character limit on input lines. In functional
- languages (eager and lazy alike) the natural use of dynamic data
- structures avoids this. Another example more related to laziness would
- be a binary tree implementation. In a straitforward implementation in
- an eager language the time complexity of m insertions followed by n
- lookups would be O((m+n)log(m)). In a lazy implementation the
- complexity might be somewhat better, since the insertions are not
- taking place until/unless actually needed by the lookup operations.
-
- The point is that a lazy program that is seemingly equivalent to
- another (efficient) program may in fact not be quite equivalent. While
- using dynamic data structures is probably at least as efficient in C
- as in functional languages, I would think that the true equivalent of
- the Haskell binary tree would be quite difficult to write as efficient
- in C. The code would certainly be an order of magnitude more complex.
- Anyway, such subtle differences will make it very difficult for a
- compiler to reach the efficiency of todays compilers for traditional
- languages, since it would have to outguess the programmer as to
- his/her intention. In the binary tree example, a transformation to
- strict evaluation would probably seem 'wrong', even though it might be
- faster in most cases.
-
- My personal feelings about this is that the lazy formulation is
- usually the 'right', or most elegant, way to formulate the solution
- (as likely as not steaming from my matematical background), causing me
- to delight in the added power of expression provided by these
- languages.
-
- - Kristian.
-