AUTOMAP

[salva]

One of the key points of languages like APL or J is that, when a function is called with data of more dimensions than those declared in the function definition, it just adds maps until both dimensions match (the PDL devs call that threading - not related to processor threading).

After being playing with Futhark for some time this is something I really miss.

For instance, in Futhark, the * operator takes two numbers. So in order to implement the scalar product for vectors I have to write:

let dot(u: [n]i32, v[n]i32) : i32 = reduce (+) 0 (map (\i -> u[i] * v[i]) (iota n))

If the auto-dimensional adjustment were done by the compiler a-la APL, I could just write:

let dot(u: [n]i32, v[n]i32) : i32 = reduce (+) 0 (u * v)

which is far easier to read.

For a more complex example, lets compare a matrix multiplication code:

let mulvv (u: [n]i32) (v: [n]i32) : i32 = reduce (+) 0 (map (\i -> u[i] * v[i]) (iota n))

let mulvmt (v: [n]i32) (at: [m][n]i32) : [m]i32 = map (mulvv v) at

let mulmmt (a: [n][m]i32) (bt: [l][m]i32) : [n][l]i32 = map (\v -> mulvmt v bt) a

let mulmm (a: [n][m]i32) (b: [m][l]i32) : [n][l]i32 = mulmmt a (transpose b)

That would become:

let mulvv (u: [n]i32) (v: [n]i32) : i32 = reduce (+) 0 (u * v)

let mulvmt (v: [n]i32) (at: [m][n]i32) : [m]i32 = mulvv v at

let mulmm (a: [n][m]i32) (b: [m][l]i32) : [n][l]i32 = mulvmt a (transpose b)

Which is much more concise and simpler to understand once one gets used to it.

[athas]

I agree, this would be nice. I've been thinking about how to generalise this a bit, as I don't want to make built-in functions and operators special.

I have been considering a "magical" operator, which I will write as an @-sign, for applying at an inner level of an array. Thus, f@0 a is equivalent to f a, f@1 a is equivalent to map f a, f@2 a is map (map f) a, and so forth. The trick is that the @N part can be elided if the type checker can determine an N such that the expression will type-check. This will let us write just f a, and have the type checker figure out how many maps to (implicitly) add to make everything type-check.

This could work for infix operators, too. u *@1 v is a mouthful, but if the @-part is inferred, then we have just u * v, as you suggest. I think Futhark is simple enough that such inference is always possible.

The reason for the @-notation is that I would like all implicit "magic" to be expressible in terms of a simpler "base" language that corresponds closely to conventional lambda calculus. Magic is great, but I want to be able to take a peek behind the curtain, too.

The only thing I'm unsure about is how to handle functions with multiple arguments. Does f@1 mean that every argument must be an array, or only the first one? I think the former is the most reasonable semantics, but I haven't given it enough thought yet.

[salva]

The only thing I'm unsure about is how to handle functions with multiple arguments. Does f@1 mean that every argument must be an array, or only the first one?

The APL (and derived languages) way to handle that is to match upper dimensions in the given data in parallel as much as possible. For instance, declaring a function with signature f (a: ta) (b: tb) : tr, is like also implicitly declaring:

let f(a: [n]ta) (b: [m]tb) : [n]tr = if (n == m) then (map (\i -> f a[i] b[i]) (iota n)) else panic
let f(a: [n]ta) (b:    tb) : [n]tr = map (\x -> f x b) a
let f(a:    ta) (b: [m]tb) : [m]tr = map (f a) b

... and then, those rules can be applied recursively.

Just guessing, because I know nothing about Futhark internals, but maybe you could use this same idea for supporting the auto-dimensional adjustment instead of a "magical" operator: just let the type checker generate those implicit functions on demand.

[athas]

Certainly, the maps will be inserted early on in the compilation. The reason I want the @ operator is that some functions (like a polymorphic reverse) can be applied any dimension, so you need a syntax to indicate which one you want. So since we need @ anyway, we might as well automatic dimensional adjustment in terms of @.

[salva]

The only issue I see is what happens with functions accepting several arguments, just having a dimensional index would not help.

The interesting thing of APL is that the extra dimensions passed in every argument, besides those required by the function, can differ.

Let me illustrate it with an example, imagine a function for blending colors:

-- Blending a simple component is done as follows:
let blend (c0: f32) (c1: f32) (alpha: f32): f32 = c0 * (1.0f32 - alpha) + c1 * alpha

-- then, we can write a function to adjust 3 color components:
let blend_color (c0: [3]f32) (c1: [3][f32]) (alpha: f32) = blend c0 c1 alpha

-- now we can blend an image with a shade of blue just doing:
let img1 : [][][3]f32 = [[[0.1f32,0.1f32,0.2f32], [...], ...], ...]
let blue_img: [][][3]f32 = blend_color img1 [0.5f32, 0.5f32, 1.0f32] 0.25f32

-- but we can just blend two images using the same function:
let img2: [][][3]f32 = ...
let img3: [][][3]f32 = blend_color img1 img2 0.5f32

-- or blend and image into a video using a mask:
let video1: [][][][3]f32 = ...
let mask: [][]f32 = ...
let video2: [][][][3]f32 = blend_color video1 img2 mask

-- or blend a shade of blue into a video using a mask:
let video3: [][][][3]f32 = blend_color video1 [0.4f32, 0.4f32, 1.0f32] mask

So, well, what all that means is that instead of a simple index, probably what you need is a tuple of indexes with one element for every argument. For instance, the calls above would become...

let blue_img: [][][3]f32 = blend_color@(2,0,0) img1 [0.5f32, 0.5f32, 1.0f32] 0.25f32
let img3: [][][3]f32 = blend_color@(2,2,0) img1 img2 0.5f32
let video2: [][][][3]f32 = blend_color@(3,2,2) video1 img2 mask
let video3: [][][][3]f32 = blend_color@(3,0,2) video1 [0.4f32, 0.4f32, 1.0f32] mask

[athas]

I see. That looks rather elegant, actually. Well, typing all the explicit tuples looks ugly of course, but I like that it's possible to boil away all the magic to explain what's happening. Might be useful for debugging, too. In a way, the tuple-@s are really syntactic sugar for an even more ugly form that uses only the single-argument @. Instead of

let video3: [][][][3]f32 = blend_color@(3,0,2) video1 [0.4f32, 0.4f32, 1.0f32] mask

we could write

let video3: [][][][3]f32 = ((blend_color@3 video1)@0 [0.4f32, 0.4f32, 1.0f32])@2 mask

Although that's the kind of code only a compiler could love.

Once we've added proper higher-order functions to Futhark, I think this is definitely something we should pursue.

[salva]

BTW, I would like to add that, once you have the auto-dimensional adjustment, having an operator like reverse being able to operate at a customizable dimensions becomes much less interesting, as you could get the same functionality writing a simple wrapper. For instance, instead of...

let f (a: [n][m][l][o][p][q][r][s]f32): [n][m][l][o][p][q][r][s]f32 = g (reverse@2 a)

...you could write...

let reverse_2 (b [r][s]f32): [r][s]f32 = reverse b
let f (a: [n][m][l][o][p][q][r][s]f32): [n][m][l][o][p][q][r][s]f32 = g (reverse_2 a)

... though, probably using a better name for reverse_2, one related to the problem domain.

It seems to me that, from the list of operators on the documentation that take the dimension as a parameter, just split could not be used that way.

Anyway, I don't want too bore you further with my ideas, just that I am becoming addicted to your little language!

[salva]

we could write

let video3: [][][][3]f32 = ((blend_color@3 video1)@0 [0.4f32, 0.4f32, 1.0f32])@2 mask

Ah, but I am not sure that would be completely equivalent. Note that the dimensions should not be expanded sequentially but in parallel:

For instance, foo@(1, 1) should expand into...

let foo_1_1 (a: [n]ta) (b:[n]tb) : [n]tr = map (\i -> foo a[i] [b[i]) (iota n)

And foo@(1, 2) should expand into...

let foo_1_2 (a: [n]ta) (b: [m][n]tb) : [m][n]tr = map (foo_1_1 a) tb

[athas]

Yes, I see, you're right.