Intermediate language for APL 
Author Message
 Intermediate language for APL

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).

[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
Timothy A. Budd
Department of Computer Science
Oregon State University
Corvallis, Oregon 97331

An APL Compiler
Timothy A. Budd
Springer-Verlag, 1988

Jonathan Burns        |

Computer Science Dept |          
La Trobe University   |

Wed, 17 Feb 1993 01:40:00 GMT  
 [ 1 post ] 

 Relevant Pages 

1. Intermediate languages: P-code/U-code

2. SISAL as Intermediate Language for parallel compilers

3. P-code, T-code, and Uni-Code Intermediate Languages

4. P-code, T-code and Uni-Code Intermediate Languages

5. Looking for anything on intermediate languages...

6. Machine-independent intermediate languages

7. Machine-independent intermediate languages

8. Decompiler/intermediate language

9. Tcl's virtual machine and intermediate language

10. Use of assembler as intermediate language in POPLOG

11. I-APL, Vanguard APL, and APL.68000

12. APL language FAQ


Powered by phpBB® Forum Software