Conal Elliott | 19 Jun 21:28 2014
Picon

Monomorphizing GHC Core?

Has anyone worked on a monomorphizing transformation for GHC Core? I understand that polymorphic recursion presents a challenge, and I do indeed want to work with polymorphic recursion but only on types for which the recursion bottoms out statically (i.e., each recursive call is on a smaller type). I'm aiming at writing high-level polymorphic code and generating monomorphic code on unboxed values. This work is part of a project for compiling Haskell to hardware, described on my blog (http://conal.net).

Thanks,  - Conal
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Edward Kmett | 19 Jun 22:22 2014
Picon

Re: Monomorphizing GHC Core?

Might you have more success with a Reynolds style defunctionalization pass for the polymorphic recursion you can't eliminate? 

Then you wouldn't have to rule out things like

data Complete a = S (Complete (a,a)) | Z a

which don't pass that test.

-Edward


On Thu, Jun 19, 2014 at 3:28 PM, Conal Elliott <conal <at> conal.net> wrote:
Has anyone worked on a monomorphizing transformation for GHC Core? I understand that polymorphic recursion presents a challenge, and I do indeed want to work with polymorphic recursion but only on types for which the recursion bottoms out statically (i.e., each recursive call is on a smaller type). I'm aiming at writing high-level polymorphic code and generating monomorphic code on unboxed values. This work is part of a project for compiling Haskell to hardware, described on my blog (http://conal.net).

Thanks,  - Conal

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Conal Elliott | 19 Jun 22:49 2014
Picon

Re: Monomorphizing GHC Core?

Thanks, Ed. It hadn't occurred to me that defunctionalization might be useful for monomorphization. Do you know of a connection?

I'm using a perfect leaf tree type similar to the one you mentioned but indexed by depth:

> data Tree :: (* -> *) -> Nat -> * -> * where
>   L :: a -> Tree k 0 a
>   B :: Tree k n (k a) -> Tree k (1+n) a

Similarly for "top-down" perfect leaf trees:

> data Tree :: (* -> *) -> Nat -> * -> * where
>   L :: a -> Tree k 0 a
>   B :: k (Tree k n a) -> Tree k (1+n) a

This way, after monomorphization, there won't be any sums remaining.

  -- Conal


On Thu, Jun 19, 2014 at 1:22 PM, Edward Kmett <ekmett <at> gmail.com> wrote:
Might you have more success with a Reynolds style defunctionalization pass for the polymorphic recursion you can't eliminate? 

Then you wouldn't have to rule out things like

data Complete a = S (Complete (a,a)) | Z a

which don't pass that test.

-Edward


On Thu, Jun 19, 2014 at 3:28 PM, Conal Elliott <conal <at> conal.net> wrote:
Has anyone worked on a monomorphizing transformation for GHC Core? I understand that polymorphic recursion presents a challenge, and I do indeed want to work with polymorphic recursion but only on types for which the recursion bottoms out statically (i.e., each recursive call is on a smaller type). I'm aiming at writing high-level polymorphic code and generating monomorphic code on unboxed values. This work is part of a project for compiling Haskell to hardware, described on my blog (http://conal.net).

Thanks,  - Conal

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users



_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Edward Kmett | 19 Jun 23:27 2014
Picon

Re: Monomorphizing GHC Core?

I think the first time I saw a connection to polymorphic recursion was in Neil Mitchell's supero, which used it as a catch-all fallback plan.



On Thu, Jun 19, 2014 at 4:49 PM, Conal Elliott <conal <at> conal.net> wrote:
Thanks, Ed. It hadn't occurred to me that defunctionalization might be useful for monomorphization. Do you know of a connection?

I'm using a perfect leaf tree type similar to the one you mentioned but indexed by depth:

> data Tree :: (* -> *) -> Nat -> * -> * where
>   L :: a -> Tree k 0 a
>   B :: Tree k n (k a) -> Tree k (1+n) a

Similarly for "top-down" perfect leaf trees:

> data Tree :: (* -> *) -> Nat -> * -> * where
>   L :: a -> Tree k 0 a
>   B :: k (Tree k n a) -> Tree k (1+n) a

This way, after monomorphization, there won't be any sums remaining.

  -- Conal



On Thu, Jun 19, 2014 at 1:22 PM, Edward Kmett <ekmett <at> gmail.com> wrote:
Might you have more success with a Reynolds style defunctionalization pass for the polymorphic recursion you can't eliminate? 

Then you wouldn't have to rule out things like

data Complete a = S (Complete (a,a)) | Z a

which don't pass that test.

-Edward


On Thu, Jun 19, 2014 at 3:28 PM, Conal Elliott <conal <at> conal.net> wrote:
Has anyone worked on a monomorphizing transformation for GHC Core? I understand that polymorphic recursion presents a challenge, and I do indeed want to work with polymorphic recursion but only on types for which the recursion bottoms out statically (i.e., each recursive call is on a smaller type). I'm aiming at writing high-level polymorphic code and generating monomorphic code on unboxed values. This work is part of a project for compiling Haskell to hardware, described on my blog (http://conal.net).

Thanks,  - Conal

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users




_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
John Meacham | 21 Jun 04:11 2014
Picon

Re: Monomorphizing GHC Core?

I do that with jhc to allow compilation to bare hardware. The Grin
intermediate language is neither polymorphic nor higher order.
Basically, in involves adding a sprinkling of type coercions and
conjuring up some types that reflect the 'shape' of the data without
being self-referential. so I don't do it til fairly late in the
lambda-cube optimization passes because it loses some information. I
wonder if the explicit coercions in system Fc used by ghc now will
allow a more principled approach.

    John

On Thu, Jun 19, 2014 at 12:28 PM, Conal Elliott <conal <at> conal.net> wrote:
> Has anyone worked on a monomorphizing transformation for GHC Core? I
> understand that polymorphic recursion presents a challenge, and I do indeed
> want to work with polymorphic recursion but only on types for which the
> recursion bottoms out statically (i.e., each recursive call is on a smaller
> type). I'm aiming at writing high-level polymorphic code and generating
> monomorphic code on unboxed values. This work is part of a project for
> compiling Haskell to hardware, described on my blog (http://conal.net).
>
> Thanks,  - Conal
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users <at> haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>

--

-- 
John Meacham - http://notanumber.net/

Gmane