|
Arrays are one of the most important data structures in computing. They are also one of the most fun; if you're into sound or graphics you will almost certainly do some array processing at some time. Unsurprisingly there are many languages around that focus on array manipulation. Broadly speaking they are divided into two camps: rubbish languages that produce fast code (think Fortran and derivatives) and good languages that produce slow code (think APL and derivatives). Wouldn't it be nice to have a decent language that produced fast code?
Well the state of the art is getting there. Single Assignment C produces extremely fast code and uses a pleasant declarative form to specify array manipulation. It's based on a calculus of arrays called the Mathematics of Arrays. This paper has the details of the reduction rules used to perform these optimisations. It's worth reading if you're interested in getting fast array code out of a functional language; hopefully something functional compiler authors will turn to.
Posted to implementation by Noel Welsh on 1/29/02; 12:22:25 AM
|
A Reduction Semantics for Array Expressions
