[Prev][Next][Index][Thread]
Update on FISh and shape
The FISh homepage
http://www-staff.socs.uts.EDU.AU:8080/~cbj/FISh/
has a lot of new material. Here are a couple of pages.
Barry Jay
| Associate Professor C. Barry Jay http://www-staff.socs.uts.edu.au/~cbj
| Reader in Computing Sciences FISh homepage .../~cbj/FISh
What's New!
===========
Polymorphic quicksort in FISh is faster than in C for quicksort (see below).
Download FISh-1.5. Check the list of new features.
The formal language definition for FISh is based on the original design.
Versions since 1.4 have been checked for compliance.
Source code for FISh is also available with the distribution.
Now you can compile your own executables,
or try out your own language design ideas.
Poly-dimensional array programming (revised 4/8/98)
Costing Parallel Programs as a Function of Shapes (revised 29/9/98)
A simple example of polydimensionality in solving difference equations.
A new function "selfmap" in standard_prelude.fsh gives more efficient
mapping algorithms for idempotent functions.
Mail list for FISh users - sign up now!
Sometimes FISh faster than C
============================
Shape analysis in FISh allows polymorphic functions to be specialised
to the exact shape of their arguments, so that it is never necessary
to box data structures. This can have a significant impact when the
cost of pointer-chasing is high compared to the operation being
performed.
This is illustrated by polymorphic quicksort. The FISh program looks
like a standard recursive functional program of type [a] -> [a]. Here
is the corresponding C code using C's standard polymorphic quicksort
in C, called qsort. FISh takes less than half the time on large arrays
of integers. Details of the tests can be found in the Benchmarks page.
The reason is that the C program achieves polymorphism by requiring
the comparison function to act on pointers, rather than values. The
actual comparison function for floats is
int comp(const void *i, const void *j) {
int res ;
if (*(double*)i - *(double*)j > 0.0 )
{res = 1 ;}
else {res = -1 ;}
return res;
}
As well as slowing down the program, these pointers are a source of
program clutter, potential errors, and
type violations.