Re: Separating algorithms from implementations (long)

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.

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