Re: Separating algorithms from implementations (long)

Dara Gallagher <dara_gallagher@my-deja.com>
9 Sep 2000 13:18:56 -0400

          From comp.compilers

Related articles
Seprerating algorithms from implementations (long) TSharp@Serif.com (Toby Sharp) (2000-08-27)
Re: Separating algorithms from implementations (long) westin@graphics.cornell.edu (2000-09-07)
Re: Separating algorithms from implementations (long) mal@bewoner.dma.be (Lieven Marchand) (2000-09-07)
Re: Separating algorithms from implementations (long) noelw@dai.ed.ac.uk (Noel Welsh) (2000-09-08)
Re: Separating algorithms from implementations (long) joachim_d@gmx.de (Joachim Durchholz) (2000-09-08)
Re: Separating algorithms from implementations (long) toon@moene.indiv.nluug.nl (Toon Moene) (2000-09-08)
Re: Separating algorithms from implementations (long) dara_gallagher@my-deja.com (Dara Gallagher) (2000-09-09)
Re: Separating algorithms from implementations (long) jthorn@galileo.thp.univie.ac.at (2000-09-09)
Sv: Separating algorithms from implementations (long) anitac@heaven.dk (Anita Christensen & Jacob Andresen) (2000-09-11)
Re: Separating algorithms from implementations (long) dara_gallagher@my-deja.com (Dara Gallagher) (2000-09-13)
Re: Separating algorithms from implementations (long) fjh@cs.mu.OZ.AU (2000-09-13)
Re: Separating algorithms from implementations (long) nr@labrador.eecs.harvard.edu (2000-09-23)
| List of all articles for this month |

From: Dara Gallagher <dara_gallagher@my-deja.com>
Newsgroups: comp.graphics.algorithms,comp.compilers,comp.dsp
Date: 9 Sep 2000 13:18:56 -0400
Organization: Deja.com - Before you buy.
References: 00-08-124
Keywords: design, functional

Hi,


Toby Sharp <TSharp@Serif.com> wrote:
> We might be able to solve this problem if there were some way to
> describe algorithms apart from their implementations.


I think functional and logical languages come closest in this
regard. Unfortunately there are some disadvantages; space and time
complexity is very difficult to calculate for functional programs.
(This crops up on comp.lang.functional frequently.)


Also, I remember hearing (from at least 10 years ago) claims to the
effect that the high-level and abstract nature of modern functional
programming languages (i.e. after ML) would allow compilers to
perform highly extensive optimization which would be impossible
with imperative languages. Unfortunately these "wonder compilers"
still haven't appeared.


However, there was a FPL (now defunct as far as I know) called
Sisal which apparently could challange and often outperform hand
crafted Fortran for various types of multiple processor and vector
architectures. Note that unlike the Fortran compilers for high
performance computing, Sisal didn't allow the programmer to express
explicit paralellism; in other words the Sisal compiler often did
a better job of parallelizing algorithms than humans. Surprisingly
even for more vanilla configurations outside of high performance
computing (i.e. single CPU) it could often outperform hand-crafted C.




As an aside, to illustrate how declarative these languages are,
here is a popular example of Quicksort in two lines (using Haskell
like notation);


qsort [] = []
qsort (p:x) = [ e | e <- x, e <= p ] ++ [ p ] ++ [ e | e <- x, e > p ]


("[]" is the empty sequence, "(p:x)" is a pattern for non-empty
sequences where p is bound the head and x is bound to the tail, "++"
appends sequences, "[ e | e <- x, e <= p ]" reads as "the sequence
containing each e where e is drawn from the sequence x and e is less
than or equal to p.)


Cheers,
Dara.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.