Lambda the Ultimate

inactiveTopic A Reduction Semantics for Array Expressions
started 1/28/2002; 12:24:20 PM - last post 1/29/2002; 12:23:32 AM
Noel Welsh - A Reduction Semantics for Array Expressions  blueArrow
1/28/2002; 12:24:20 PM (reads: 1961, responses: 1)
A Reduction Semantics for Array Expressions

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

Ehud Lamm - Re: A Reduction Semantics for Array Expressions  blueArrow
1/29/2002; 12:23:32 AM (reads: 852, responses: 0)
Noel, it seems you forgot to post this message to the home page, so I posted it for you.