dope vector transpose without copy

[luserdroog]

I was reading the old pamphlet Whizbangs! and turned to the
article about Sharp APL, and even knowing that it was Iverson's
et al's work my mind immediately suspected a puff prop piece.
But although it was that too, it also listed situations which
any APL implementation could adopt optimizations for.

Like if omega is a temp and the right size for z, use it
instead of allocating a new temp.

But ignoring further actual details, I cast my subconscious
upon the task of obvious optimizations that I could do.
One idea that floated up is to perform transposes by operating
on the polynomial of the array-indexing formula itself,
like I seem to remember from one of those 70s Discrete Math
books.

Already I've exploited the indirection in the AK() abstract
array member to build the frame and cell vectors very cheaply,
by using .k to hold the ptrdiff_t between the arguments'
dimension vector and the address of the (stack-allocated)
abstract array. It's just an encoding of a relative pointer.

So, combining these three ideas, if the abstract array were
augmented with another vector the same size as the dimension
vector, the "dope vector" which represents the weighting
applied (multiplied) to a vector of indices before summation
yields the ravel position. For other normal indexing this
could also potentially factor-out some multiplies.

A similar idea is already in the original 62 APL book,
in the Representation chapter. But that sh is dense, you know?

--
you know.

[Lobachevsky]

Have a look at Timothy Budd's book, An APL Compiler. In Chapter 6, Structural Functions, he talks about "stepper values" for transpose, take, drop, and reverse.

[luserdroog]

On Monday, May 25, 2015 at 1:04:39 PM UTC-5, Lobachevsky wrote:
> Have a look at Timothy Budd's book, An APL Compiler. In Chapter 6, Structural Functions, he talks about "stepper values" for transpose, take, drop, and reverse.

Thanks. Added to cart.

Meanwhile, I have had some success in writing a prototype
with the dope vector structure.
https://github.com/luser-dr00g/inca/blob/master/arrind.c

And a brief tour of the idea and the code is here:
http://stackoverflow.com/questions/30409991/use-a-dope-vector-to-access-arbitrary-axial-slices-of-a-multidimensional-array

But now I'm led to a dilemma. Part of me wants to rewrite
all of inca3 to use the arrind.c functions, rather than
graft yet another "overlay" on the existing set of
structures to add dope-vector powers. Both ways sound
like tedious work. :( And I still haven't finished
multiprecision integers.

[luserdroog]

On Tuesday, May 26, 2015 at 3:37:16 AM UTC-5, luserdroog wrote:
> On Monday, May 25, 2015 at 1:04:39 PM UTC-5, Lobachevsky wrote:
> > Have a look at Timothy Budd's book, An APL Compiler. In Chapter 6, Structural Functions, he talks about "stepper values" for transpose, take, drop, and reverse.
>
> Thanks. Added to cart.
>

Alright, it arrived and I'm up to chapter 6 and there
are some amazing ideas here. And an added point of
interest is frequent mention of a paper co-authored
by a certain Douglas Wyatt who co-authored a certain
paper with a certain John Warnock which described
what became known as the Adobe Image Model. So I
definitely perked up when I saw that name. :)

I think a lot (possibly most) of the ideas can be
applied to an interpreter. But I don't if I really
have the chops to design and build such a monster.

My own efforts have resulted in a C demo of Inner
Product using "dope vectors" which Budd describes in
chapter 4 as "extension vectors" with a note that
they're also sometimes called "power vectors" and
there's no real standard nomenclature here.
Linked elsethread.

Having done that, I decided to check my work and
go back to A Programming Language and rereread the
chapter on representations where he describes several
options for representation of vectors where the
version I've implemented corresponds most closely
to the Linear representation. But other tantalizing
choices are Chained and Partitioned.

With a chained vector, each element is in a node
structure which also contains a pointer to the next
element (duh), but the "pointer" can be any kind of
variable-sized variable-based numerical entity (which
of course, we knew, but this observation I think is far
less deserving of 'duh').

With a partitioned vector, elements are "typed-out"
linearly with sentinel values (called "partition
symbols"). This mostly closely models the final printed
appearance of an array, except for extra padding (but you
could do that if you want to).

So, now I want to build a structure that can have a
variable representation. At first a language could
be implemented by always converting arguments to a
convenient type for each function's algorithm. Later,
algortihms for all representations can be written,
profiled, and then more powerful strategies for rep-
coercion could be devised (or so I pipe-dream).

Incorporating this with some magical JIT tech and you
could compile each line before executing (duh).

So, I kind of want to go back to my Lisp interpreter
code and build-up my compiler chops. I'll be sure to
report any results pertinent to APL implementation.

[asetof...@gmail.com]

Yes it is possible to have a language
without types...
Than how easy represent
struct name{
Type1 name;
Type2 name2;
Etc
};
And find the errors in wrong type
operator= call?