tail tuple support

[melsman]

Aplt now generates programs with TAIL tuples. An example is the program mandelbrotN.apl, which now generates the following TAIL code (and output from the TAIL interpreter):

bash-3.2$ ../aplt -silent -p_tail mandelbrotN.apl 
../aplt -silent -p_tail mandelbrotN.apl 
Compiling powerN: DOUBLE_C; DOUBLE_C; DOUBLE_C
let v7:[double]1 = drop(2,[-2.0,0.75,-0.75,0.75]) in
let v8:[double]0 = divd(subd(0.75,-2.0),20.0) in
let v9:[double]0 = divd(subd(idxS(1,2,v7),idxS(1,1,v7)),12.0) in
let v13:[double]2 = reshape([12,20],each(fn v12:[double]0 => addd(-2.0,v12),each(fn v11:[double]0 => muld(v8,v11),each(i2d,iota(20))))) in
let v17:[double]2 = transp(reshape([20,12],each(fn v16:[double]0 => addd(idxS(1,1,v7),v16),each(fn v15:[double]0 => muld(v9,v15),each(i2d,iota(12)))))) in
let v18:[bool]2 = reshape([12,20],[ff]) in
let v109:([double]2 * [double]2 * [double]2) = power(fn v73:([double]2 * [double]2 * [double]2) => let v74:[double]2 = reshape([12,20],Prj(0,v73)) in
      let v75:[double]2 = reshape([12,20],Prj(1,v73)) in
      let v76:[double]2 = reshape([12,20],Prj(2,v73)) in
      let v85:[double]2 = zipWith(addd,v13,zipWith(subd,zipWith(muld,v74,v74),zipWith(muld,v75,v75))) in
      let v94:[double]2 = zipWith(addd,v17,zipWith(addd,zipWith(muld,v74,v75),zipWith(muld,v74,v75))) in
      let v102:[bool]2 = each(fn v101:[double]0 => gtd(4.0,v101),zipWith(addd,zipWith(muld,v85,v85),zipWith(muld,v94,v94))) in
      let v108:[double]2 = zipWith(addd,v76,each(fn v105:[double]0 => subd(1.0,v105),each(i2d,each(b2i,v102)))) in
      (v85,v94,v108),90,(each(i2d,each(b2i,v18)),each(i2d,each(b2i,v18)),each(i2d,each(b2i,v18)))) in
let v111:[double]2 = reshape(transp(vreverseV([20,12])),each(fn v110:[double]0 => divd(v110,90.0),Prj(2,v109))) in
let v119:[char]2 = prArrC(each(fn v116:[int]0 => idxS(1,addi(v116,1),['$','#','O','o','*','=','+',':','-',' ']),each(ceil,each(fn v112:[double]0 => muld(9.0,v112),v111)))) in
0.0

       +$$$$ -   
      -$$$$$$-   
   -  $$$$$$$$   
  +$:-$$$$$$$$   
 -$$$:$$$$$$$$   
 $$$$$$$$$$$$$$$$    
 -$$$:$$$$$$$$   
  +$:-$$$$$$$$   
   -  $$$$$$$$   
      -$$$$$$-   
       +$$$$ -   
     $$      

[](0.0)

The mandelbrotN.apl program is available from https://github.com/melsman/apltail/blob/master/tests/mandelbrotN.apl.

Notice that tuples are not yet supported by the Aplt C-backend.

[melsman]

Who wants to add tuple-support to tail2futhark? ;)

[athas]

The big problem is that tail2futhark depends upon the "instance declarations" that are generated by the p_types flag. Unfortunately, this does not work with tuples yet. I fear it is beyond my capabilities to extend aplt as necessary.

\ Troels /\ Henriksen

[melsman]

Ahh - forgot about this... Will look at it later tonight... Sitting in the metro...

[melsman]

Here is the program with type annotations:

bash-3.2$ ../aplt -p_types -p_tail mandelbrotN.apl
[Reading file: mandelbrotN.apl]
TAIL program:
let v7:[double]1 = drop{[double],[1]}(2,[-2.0,0.75,-0.75,0.75]) in
let v8:[double]0 = divd(subd(0.75,-2.0),20.0) in
let v9:[double]0 = divd(subd(idxS{[double],[0]}(1,2,v7),idxS{[double],[0]}(1,1,v7)),12.0) in
let v13:[double]2 = reshape{[double],[1,2]}([12,20],each{[double,double],[1]}(fn v12:[double]0 => addd(-2.0,v12),each{[double,double],[1]}(fn v11:[double]0 => muld(v8,v11),each{[int,double],[1]}(i2d,iota(20))))) in
let v17:[double]2 = transp{[double],[2]}(reshape{[double],[1,2]}([20,12],each{[double,double],[1]}(fn v16:[double]0 => addd(idxS{[double],[0]}(1,1,v7),v16),each{[double,double],[1]}(fn v15:[double]0 => muld(v9,v15),each{[int,double],[1]}(i2d,iota(12)))))) in
let v18:[bool]2 = reshape{[bool],[1,2]}([12,20],[ff]) in
let v109:([double]2 * [double]2 * [double]2) = power{[double,double,double],[2,2,2]}(fn v73:([double]2 * [double]2 * [double]2) => let v74:[double]2 = reshape{[double],[2,2]}([12,20],Prj(0,v73)) in
      let v75:[double]2 = reshape{[double],[2,2]}([12,20],Prj(1,v73)) in
      let v76:[double]2 = reshape{[double],[2,2]}([12,20],Prj(2,v73)) in
      let v85:[double]2 = zipWith{[double,double,double],[2]}(addd,v13,zipWith{[double,double,double],[2]}(subd,zipWith{[double,double,double],[2]}(muld,v74,v74),zipWith{[double,double,double],[2]}(muld,v75,v75))) in
      let v94:[double]2 = zipWith{[double,double,double],[2]}(addd,v17,zipWith{[double,double,double],[2]}(addd,zipWith{[double,double,double],[2]}(muld,v74,v75),zipWith{[double,double,double],[2]}(muld,v74,v75))) in
      let v102:[bool]2 = each{[double,bool],[2]}(fn v101:[double]0 => gtd(4.0,v101),zipWith{[double,double,double],[2]}(addd,zipWith{[double,double,double],[2]}(muld,v85,v85),zipWith{[double,double,double],[2]}(muld,v94,v94))) in
      let v108:[double]2 = zipWith{[double,double,double],[2]}(addd,v76,each{[double,double],[2]}(fn v105:[double]0 => subd(1.0,v105),each{[int,double],[2]}(i2d,each{[bool,int],[2]}(b2i,v102)))) in
      (v85,v94,v108),90,(each{[int,double],[2]}(i2d,each{[bool,int],[2]}(b2i,v18)),each{[int,double],[2]}(i2d,each{[bool,int],[2]}(b2i,v18)),each{[int,double],[2]}(i2d,each{[bool,int],[2]}(b2i,v18)))) in
let v111:[double]2 = reshape{[double],[2,2]}(transp{[int],[1]}(vreverseV{[int],[2]}([20,12])),each{[double,double],[2]}(fn v110:[double]0 => divd(v110,90.0),Prj(2,v109))) in
let v119:[char]2 = prArrC(each{[int,char],[2]}(fn v116:[int]0 => idxS{[char],[0]}(1,addi(v116,1),['$','#','O','o','*','=','+',':','-',' ']),each{[double,int],[2]}(ceil,each{[double,double],[2]}(fn v112:[double]0 => muld(9.0,v112),v111)))) in
0.0
Evaluating

       +$$$$ -   
      -$$$$$$-   
   -  $$$$$$$$   
  +$:-$$$$$$$$   
 -$$$:$$$$$$$$   
 $$$$$$$$$$$$$$$$    
 -$$$:$$$$$$$$   
  +$:-$$$$$$$$   
   -  $$$$$$$$   
      -$$$$$$-   
       +$$$$ -   
     $$      

Result is [](0.0)

[athas]

Sweet! I think I can get tail2futhark working now.

I use aplt -p_types -s_tail to translate APL to TAIL - is that the correct incantation? I am not sure I understand the distinction between the p and s-flags.

[athas]

Would it be possible to also get a type annotation for Prj? It would make my life ever so slightly easier. The reason is that Futhark does not have projection, so I will have to translate e.g.

Prj(0,v73)

as

let (x, _, _) = v_73 in x

Alternatively, I'll just add tuple projection to Futhark. There is no deep reason it doesn't have it, apart from me having to come up with a syntax.

[melsman]

-s_tail means "stop after tail"... Does --help help? I'll add the type annotation to Prj so that you'll see Prj3....

[melsman]

In the expression let (x, _, _) = v_73 in x, can Futhark infer the type of x or does it need to be annotated?

[melsman]

Aplt now prints Prj{3}(e) when e is a tuple of length 3 - let me know if you also need the type of the projected argument - or the type of all tuple elements...

[athas]

Nope, this is fine. I have tail2futhark generating quite nice code for mandelbrotN.apl now.

\ Troels /\ Henriksen

[athas]

The TAIL AST definition in tail2futhark would be slightly nicer if the Prj annotation was similar to other annotations. I.e, representable in the Haskell type:

type InstDecl = ([BType], [Integer])

I'll just hack it for now.

\ Troels /\ Henriksen

[athas]

I added tuple projection syntax to the Futhark compiler, so I could implement it in a different way. In fact, it would now be cleaner if Prj had no annotation, to make it more like other operations. (Sorry for the churn.)

[melsman]

Ok -I'll delete it again later tonight...

[melsman]

There is now support for dyadic each, which allows for a version of mandelbrot with an inner use of the power operator - and an outer use of each - see https://github.com/melsman/apltail/blob/master/tests/mandelbrotInnerPower.apl:

bash-3.2$ ../aplt -p_types -p_tail -s_tail mandelbrotInnerPower.apl 
[Reading file: mandelbrotInnerPower.apl]
TAIL program:
let v7:[double]1 = drop{[double],[1]}(2,[-2.0,0.75,-0.75,0.75]) in
let v8:[double]0 = divd(subd(0.75,-2.0),20.0) in
let v9:[double]0 = divd(subd(idxS{[double],[0]}(1,2,v7),idxS{[double],[0]}(1,1,v7)),12.0) in
let v13:[double]2 = reshape{[double],[1,2]}([12,20],each{[double,double],[1]}(fn v12:[double]0 => addd(-2.0,v12),each{[double,double],[1]}(fn v11:[double]0 => muld(v8,v11),each{[int,double],[1]}(i2d,iota(20))))) in
let v17:[double]2 = transp{[double],[2]}(reshape{[double],[1,2]}([20,12],each{[double,double],[1]}(fn v16:[double]0 => addd(idxS{[double],[0]}(1,1,v7),v16),each{[double,double],[1]}(fn v15:[double]0 => muld(v9,v15),each{[int,double],[1]}(i2d,iota(12)))))) in
let v73:[double]2 = zipWith{[double,double,double],[2]}(fn v46:[double]0 => fn v47:[double]0 => let v72:[double]1 = power{[double],[1]}(fn v62:[double]1 => let v64:[double]1 = reshape{[double],[1,1]}([3],v62) in
            let v65:[double]0 = idxS{[double],[0]}(1,1,v64) in
            let v66:[double]0 = idxS{[double],[0]}(1,2,v64) in
            let v67:[double]0 = idxS{[double],[0]}(1,3,v64) in
            let v68:[double]0 = addd(v46,subd(muld(v65,v65),muld(v66,v66))) in
            let v69:[double]0 = addd(v47,addd(muld(v65,v66),muld(v65,v66))) in
            let v70:[bool]0 = gtd(4.0,addd(muld(v68,v68),muld(v69,v69))) in
            let v71:[double]0 = addd(v67,i2d(subi(1,b2i(v70)))) in
            [v68,v69,v71],90,eachV{[bool,double],[3]}(fn v61:[bool]0 => i2d(b2i(v61)),[ff,ff,ff])) in
      idxS{[double],[0]}(1,3,v72),v13,v17) in
let v75:[double]2 = reshape{[double],[2,2]}(transp{[int],[1]}(vreverseV{[int],[2]}([20,12])),each{[double,double],[2]}(fn v74:[double]0 => divd(v74,90.0),v73)) in
let v83:[char]2 = prArrC(each{[int,char],[2]}(fn v80:[int]0 => idxS{[char],[0]}(1,addi(v80,1),['$','#','O','o','*','=','+',':','-',' ']),each{[double,int],[2]}(ceil,each{[double,double],[2]}(fn v76:[double]0 => muld(9.0,v76),v75)))) in
0.0
Evaluating

       +$$$$ -   
      -$$$$$$-   
   -  $$$$$$$$   
  +$:-$$$$$$$$   
 -$$$:$$$$$$$$   
 $$$$$$$$$$$$$$$$    
 -$$$:$$$$$$$$   
  +$:-$$$$$$$$   
   -  $$$$$$$$   
      -$$$$$$-   
       +$$$$ -   
     $$      

Result is [](0.0)

[athas]

I'll try to hack out some tail2futhark support for this one. Should this entirely replace the current Mandelbrot implementation?

\ Troels /\ Henriksen

[athas]

Wow, it works right now without any changes. Very cool!

[melsman]

Maybe we can use the two versions to demonstrate that, sometimes, the programmer can benefit from interchanging loops...

Den lørdag den 11. juni 2016 skrev Troels Henriksen < notifications@github.com>:

Wow, it works right now without any changes. Very cool!

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/henrikurms/tail2futhark/issues/9#issuecomment-225390528, or mute the thread https://github.com/notifications/unsubscribe/ABHRu0a5bxAHKNKVuqOKl0NOq-CArDpjks5qKxE7gaJpZM4IyPRZ .

[athas]

Works for me. I think we have room.

\ Troels /\ Henriksen

[athas]

I added numbers, exposition, and a graph to the paper. Looks good, although the hand-written version still has a solid factor 4.5 lead.

[melsman]

Cool. How do I get the figures/speedup.pdf file?

On Sat, Jun 11, 2016 at 10:55 PM, Troels Henriksen <notifications@github.com

wrote:

I added numbers, exposition, and a graph to the paper. Looks good, although the hand-written version still has a solid factor 4.5 lead.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/henrikurms/tail2futhark/issues/9#issuecomment-225393675, or mute the thread https://github.com/notifications/unsubscribe/ABHRu3bbB2N3-H9Qe38JDZrbhTAjWFL_ks5qKyDJgaJpZM4IyPRZ .

[athas]

You pull again. Sorry about that.

\ Troels /\ Henriksen