I'm reposting some talk from comp.parallel a little while back, because of

interest here in intermediate representations for APL compilers.

Tim Budd has sent me his papers on his lambda-form representation, which

I find very neat. I've ordered his book, in fact.

Newsgroups: comp.parallel

I received a kind of neat posting on languages for parallelism

and vectorism. Unfortunately, the author isn't able to post.

I think he makes interesting comments on APL (which perhaps

deserves a second look).

--eugene

[complete: (please reply to author or follow ups to comp.parallel)]

Subject: Parallelism/Vectorism

X-To: Eugene Miya

Organization: I. P. Sharp Associates

X-Mail: 1900/2 First Canadian Place,

Toronto, Canada, M5X 1E3

X-Telephone: +1 (416) 364-5361

X-Fax: +1 (416) 364-2910

X-Telex: 0622259

Date: 17 May 89 16:14:59 UT

I think I may be fairly accused of prejudice in favour of APL since I've

spent the last 16 Years prodding an implementation of it along (Sharp APL

in case you can't guess from my header).

No language that I know of is perfect (except perhaps CDC 6400 COMPASS :-)

but there are certainly several features of 'modern' APL that I believe at

least point the way towards effective use of scalable architectures. By

'modern' APL I mean APL as Ken (Iverson) now sees it, which is to say *not*

IBM/APL2, but the 'Dictionary' APL as the APL community usually calls it.

- Generalised operator/function syntax. This is something APL has always

had, but it's value and generality has not been fully used or recognised

until quite recently. The number of 'operators' (that is, meta-functions

whose arguments and results are functions, the architypical one being

"/", ie in "+/" the operator "/" takes "+" as it's argument, and produces

"sum reduction" (usually called "summation" by non-APLers) as it's

result) [pardon long parenthesis] has increased quite radically in the

last 5 years or so, partly to deal with the other points below -

- Boxed arrays. Since the structure of APL is embodied much more within

it's data structures than within it's programs (ie it is more like LISP

than Pascal) it made sense to extend the levels of structure for APL

objects, and general arrays essentially allow an arbitrary level of

data hierarchy orthogonal to APL's traditional n-dimensional structuring.

- Function rank. This is probably the most important change to APL formalism

in the last ten or fif{*filter*} years, and complements and completes the notion

of operators. Basically, each function is defined to have an implicit

rank, which means the shape of arguments it works on. Thus the rank of

"+" is 0, meaning it works on 0-rank operands (scalars). Iota is defined

to have right rank of 0 (ie it's right argument is a scalar) and its

left rank is 1 (it's left argument is vectors/lists). The power of this

simple notion comes from two things:

- If the rank of the argument is larger than the function rank, the

function is applied (potentially in parallel) to *each* properly-

ranked structure (which we call a cell) within the argument (ie, as

Iota's left argument, a matrix is a collection of vector cells).

- There is an operator to explicitly state the rank of a function,

which allows explicit control of the application of a function

across a structure.

All implementations of APL that I am currently aware of are (essentially)

single processor implementations (Sharp APL runs on large IBM multi-CPU

systems, but a given interpreter only uses a single CPU at a time). But

APL could be effectively used to exploit massive parallism (at least of the

MIMD sort) by at least the two following strategies:

- Each cell within any single function invocation can be done separately

- Within an expression such as foo"dual">x ("dual" is a dieresis)

requests the function "foo"

be evaluated for each sub-box of the array "x", and these evaluations

can be done independantly.

And I'm sure that, once that problem is seriously studied, there will

turn out to be lots of other opportunities.

[ Chat deleted ... JB]

Newsgroups: comp.parallel

Subject: re: APL and parallelism

Keywords: APL parallelism

Date: 23 May 89 20:52:20 GMT

Lines: 36

Regarding APL and Parallelism

I've been an advocate of APL for parallel processors for a long time

(see my TOPLAS paper in 84 and my book ``An APL Compiler'' published by

Springer in 1988), so I was interested in Leigh's comments passed on by

Eugene. Some comments on his remarks:

(1) My students and I continue to pursue approaches to generating efficient

code from APL for a variety of machines. Our latest technique involves

a nice intermediate form based on the lambda calculus. We can translate

APL (and FP too!) into this form; perform transformations and optimizations

at this intermediate form level, then generate code from the intermediate

form. The interesting thing is that the intermediate form does not

involve any explicit control flow, and thus we can introduce parallelism

during code generation in a variety of ways. This allows us to generate

fine grain SIMD (connection-machine style) code by introducing parallelism

one way, and coarse grain, MIMD (sequent-style) code by introducing

parallelism in another way. There are also interesting time/space

tradeoffs which we are treating as a *code-generation* problem and not

something the programmer needs to deal with.

If you are intersted in finding out more about

this let me know and I can send you technical reports.

(2) APL is, despite being an anathema to the academic communnity (for

reasons which I have never quite understood) still alive and well.

Following the publication of my book I was contacted by several commercial

wall street types offering to throw large sums of money my direction if I

would develop a commercial quality compiler for APL. Being a silly college

professor, I resisted these because (1) I don't think I understand the

problems well enough to make such a system yet and (2) there are a few dark

corners of the language I've been able to ignore since I'm just ``doing

research''; if I were serious about a commercial product I would have to

really look into this, and (3) if I was interested in making money I would

never have become a college professor in the first place.

Refs: [JB]

Technical papers:

A New Approach to Vector Code Generation for Applicative Languages, 1988

Composition and Compilation in Functional Programming Languages, 1988

by:

Timothy A. Budd

Department of Computer Science

Oregon State University

Corvallis, Oregon 97331

Book:

An APL Compiler

Timothy A. Budd

Springer-Verlag, 1988

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Jonathan Burns |

Computer Science Dept |

La Trobe University |

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~