Cheap and cheerful partial evaluation

Hello all, It occurred to me that it might not be too difficult to use GHC's optimization passes as a cheap and cheerful partial evaluator. Consider some function we would like to partially evaluate: f = g h Partial evaluation proceeds as follows: calculate the type of f, inline and specialize g, inline and specialize h, and then optimize. Effectively, laser-guided inlining. With this (very) heavy hammer, we can, for example, solve the problem posed in http://hackage.haskell.org/trac/ghc/ticket/1349, simply by ensuring all of our "strict functions" are partially evaluated on the continuation handler appropriately. (This is not ideal, since we ought to be able to share the strict worker/wrapper between instances, but might be a reasonable stop-gap for some use cases.) So, am I completely insane, or does this seem plausible and easy enough to implement to make it into GHC? Cheers, Edward

And no sooner do I send this email do I realize we have 'inline' built-in, so I can probably experiment with this right now... Edward Excerpts from Edward Z. Yang's message of Sun Aug 21 14:18:23 -0400 2011:
Hello all,
It occurred to me that it might not be too difficult to use GHC's optimization passes as a cheap and cheerful partial evaluator.
Consider some function we would like to partially evaluate:
f = g h
Partial evaluation proceeds as follows: calculate the type of f, inline and specialize g, inline and specialize h, and then optimize. Effectively, laser-guided inlining.
With this (very) heavy hammer, we can, for example, solve the problem posed in http://hackage.haskell.org/trac/ghc/ticket/1349, simply by ensuring all of our "strict functions" are partially evaluated on the continuation handler appropriately. (This is not ideal, since we ought to be able to share the strict worker/wrapper between instances, but might be a reasonable stop-gap for some use cases.)
So, am I completely insane, or does this seem plausible and easy enough to implement to make it into GHC?
Cheers, Edward

On 21 August 2011 19:20, Edward Z. Yang
And no sooner do I send this email do I realize we have 'inline' built-in, so I can probably experiment with this right now...
You may be interested in my related ticket #5029: http://hackage.haskell.org/trac/ghc/ticket/5059 I don't think this is totally implausible but you have to be very careful with recursive functions. Max

I think this ticket sums it up very nicely! Cheers, Edward Excerpts from Max Bolingbroke's message of Mon Aug 22 04:07:59 -0400 2011:
On 21 August 2011 19:20, Edward Z. Yang
wrote: And no sooner do I send this email do I realize we have 'inline' built-in, so I can probably experiment with this right now...
You may be interested in my related ticket #5029: http://hackage.haskell.org/trac/ghc/ticket/5059
I don't think this is totally implausible but you have to be very careful with recursive functions.
Max

Edward,
On first glance at your email I misunderstood you as asking about using
GHC's optimizer as a source-to-source operation (using GHC as an optimizer,
retrieving "partially evaluated" Haskell code). That's not what you were
asking for -- but is it possible?
-Ryan
P.S. One compiler that comes to mind that exposes this kind of thing
nicely is Chez Scheme ( http://scheme.com/ ). In Chez you can get your
hands on "cp0" which does a source to source transform (aka compiler pass
zero, after macro expansion), and could use cp0 to preprocess the source and
then print it back out.
On Mon, Aug 22, 2011 at 8:48 AM, Edward Z. Yang
I think this ticket sums it up very nicely!
Cheers, Edward
Excerpts from Max Bolingbroke's message of Mon Aug 22 04:07:59 -0400 2011:
On 21 August 2011 19:20, Edward Z. Yang
wrote: And no sooner do I send this email do I realize we have 'inline' built-in, so I can probably experiment with this right now...
You may be interested in my related ticket #5029: http://hackage.haskell.org/trac/ghc/ticket/5059
I don't think this is totally implausible but you have to be very careful with recursive functions.
Max
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Since most of GHC's optimizations occur on core, not the user-friendly frontend language, doing so would be probably be nontrivial (e.g. we'd want some sort of core to Haskell decompiler.) Edward Excerpts from Ryan Newton's message of Tue Aug 23 13:46:45 -0400 2011:
Edward,
On first glance at your email I misunderstood you as asking about using GHC's optimizer as a source-to-source operation (using GHC as an optimizer, retrieving "partially evaluated" Haskell code). That's not what you were asking for -- but is it possible?
-Ryan
P.S. One compiler that comes to mind that exposes this kind of thing nicely is Chez Scheme ( http://scheme.com/ ). In Chez you can get your hands on "cp0" which does a source to source transform (aka compiler pass zero, after macro expansion), and could use cp0 to preprocess the source and then print it back out.
On Mon, Aug 22, 2011 at 8:48 AM, Edward Z. Yang
wrote: I think this ticket sums it up very nicely!
Cheers, Edward
Excerpts from Max Bolingbroke's message of Mon Aug 22 04:07:59 -0400 2011:
On 21 August 2011 19:20, Edward Z. Yang
wrote: And no sooner do I send this email do I realize we have 'inline' built-in, so I can probably experiment with this right now...
You may be interested in my related ticket #5029: http://hackage.haskell.org/trac/ghc/ticket/5059
I don't think this is totally implausible but you have to be very careful with recursive functions.
Max
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Ah, and there's no core->haskell facility presently? Thanks.
On Wed, Aug 24, 2011 at 12:14 AM, Edward Z. Yang
Since most of GHC's optimizations occur on core, not the user-friendly frontend language, doing so would be probably be nontrivial (e.g. we'd want some sort of core to Haskell decompiler.)
Edward
Excerpts from Ryan Newton's message of Tue Aug 23 13:46:45 -0400 2011:
Edward,
On first glance at your email I misunderstood you as asking about using GHC's optimizer as a source-to-source operation (using GHC as an optimizer, retrieving "partially evaluated" Haskell code). That's not what you were asking for -- but is it possible?
-Ryan
P.S. One compiler that comes to mind that exposes this kind of thing nicely is Chez Scheme ( http://scheme.com/ ). In Chez you can get your hands on "cp0" which does a source to source transform (aka compiler pass zero, after macro expansion), and could use cp0 to preprocess the source and then print it back out.
On Mon, Aug 22, 2011 at 8:48 AM, Edward Z. Yang
wrote: I think this ticket sums it up very nicely!
Cheers, Edward
Excerpts from Max Bolingbroke's message of Mon Aug 22 04:07:59 -0400 2011:
On 21 August 2011 19:20, Edward Z. Yang
wrote: And no sooner do I send this email do I realize we have 'inline' built-in, so I can probably experiment with this right now...
You may be interested in my related ticket #5029: http://hackage.haskell.org/trac/ghc/ticket/5059
I don't think this is totally implausible but you have to be very careful with recursive functions.
Max
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

I think it would be a pretty interesting project. :^) Edward Excerpts from Ryan Newton's message of Wed Aug 24 15:18:48 -0400 2011:
Ah, and there's no core->haskell facility presently? Thanks.
On Wed, Aug 24, 2011 at 12:14 AM, Edward Z. Yang
wrote: Since most of GHC's optimizations occur on core, not the user-friendly frontend language, doing so would be probably be nontrivial (e.g. we'd want some sort of core to Haskell decompiler.)
Edward
Excerpts from Ryan Newton's message of Tue Aug 23 13:46:45 -0400 2011:
Edward,
On first glance at your email I misunderstood you as asking about using GHC's optimizer as a source-to-source operation (using GHC as an optimizer, retrieving "partially evaluated" Haskell code). That's not what you were asking for -- but is it possible?
-Ryan
P.S. One compiler that comes to mind that exposes this kind of thing nicely is Chez Scheme ( http://scheme.com/ ). In Chez you can get your hands on "cp0" which does a source to source transform (aka compiler pass zero, after macro expansion), and could use cp0 to preprocess the source and then print it back out.
On Mon, Aug 22, 2011 at 8:48 AM, Edward Z. Yang
wrote: I think this ticket sums it up very nicely!
Cheers, Edward
Excerpts from Max Bolingbroke's message of Mon Aug 22 04:07:59 -0400 2011:
On 21 August 2011 19:20, Edward Z. Yang
wrote: And no sooner do I send this email do I realize we have 'inline' built-in, so I can probably experiment with this right now...
You may be interested in my related ticket #5029: http://hackage.haskell.org/trac/ghc/ticket/5059
I don't think this is totally implausible but you have to be very careful with recursive functions.
Max
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
participants (3)
-
Edward Z. Yang
-
Max Bolingbroke
-
Ryan Newton