I've had an idea for a while of a different way we could evaluate
TH-like splices which would be more lightweight and easier to work with. The idea is to create a third quotation/splicing mechanism which has no introspection (like MetaML) but then to evaluate these quotes and splices in the optimiser rather than using the bytecode interpreter. I am motivated by the many examples of recursive functions in libraries, which when given a statically known argument should be able to be unrolled to produce much better code. It is understandable that the compiler doesn't try to do this itself but there should be an easy way for the user to direct the compiler to do so. (See also https://www.reddit.com/r/haskell/comments/7yvb43/ghc_compiletime_evaluation/) An example to be concrete: Take the power function such that power k n computes k^n. power :: Int -> Int -> Int power k n = if n == 0 then 1 else k * power k (n - 1) If we statically know n then we can create a staged version. We use R to indicate that an argument is dynamically known. power :: R Int -> Int -> R Int power k n = if n == 0 then .< 1 >. else .< ~k * ~(power k (n-1)) >. One way to implement this in Haskell is to use typed template haskell quoting and splicing. The key thing to notice about why this works is that in order to splice `power k (n-1)` we need to evaluate `power k (n-1)` so that we have something of type `R Int` which we can then splice back into the quote. The way this is currently implemented is that the bytecode interpreter runs these splices in order to find out what they evaluate to. The idea is that instead, we add another mode which runs splices in the core-to-core optimiser. The optimiser performs evaluation by beta reduction, inlining and constant folding. For simple definitions on algebraic data types it does a very good job of eliminating overhead. As long as the call is not recursive. If we can just get the optimiser to inline recursive calls in a controlled manner as well, it should do a good job on the unrolled definition. The benefits of this are that it works across all platforms and fits nicely already into the compilation pipeline. It also fits in nicely with the intuition that a "quote" means to stop evaluating and a "splice" means to evaluate. A disadvantage is that the optimiser is only a *partial* evaluator rather than an evaluator. It gets stuck evaluating things containing primitives and so on. I don't forsee this as a major issue but a limitation that library authors should be aware of when writing their staged programs. To go back to the power example, the recursive condition would have to be an inductively defined natural (data N = Z | S N) rather than an Int as the comparison operator for integers can't be evaluated by the optimiser. It is already rather easy to write staged programs which loop if you don't carefully consider the staging so this seems now worse than the status quo. Does this sound at all sensible to anyone else? Matt _______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
Hi,
something like this would be great. I don’t have a sense yet of what “something” should be like. Am Dienstag, den 27.02.2018, 09:59 +0000 schrieb Matthew Pickering: > To go back to the power example, the recursive > condition would have to be an inductively defined natural (data N = Z > | S N) rather than an Int as the comparison operator for integers > can't be evaluated by the optimiser. Sure they can: $ cat ConstantFolding.hs {-# LANGUAGE TemplateHaskell #-} {-# OPTIONS_GHC -fplugin=Test.Inspection.Plugin #-} module ConstantFolding where import Test.Inspection ltInt :: Bool ltInt = (3::Int) > 2 ltInteger :: Bool ltInteger = (3::Integer) > 2 true :: Bool true = True inspect $ 'ltInt === 'true inspect $ 'ltInteger === 'true $ ghc -O ConstantFolding.hs [1 of 1] Compiling ConstantFolding ( ConstantFolding.hs, ConstantFolding.o ) ConstantFolding.hs:17:1: ltInt === true passed. ConstantFolding.hs:18:1: ltInteger === true passed. inspection testing successful expected successes: 2 As an alternative with a maybe simpler user interface (and probably less power), I wonder if we can create a magic function > compileTimeWHNF :: a -> a or > compileTimeNF :: a -> a and a GHC core plugin (or eventually built-in thing) that finds these magic functions and evaluates their arguments, using the simplifier. Cheers, Joachim -- Joachim Breitner [hidden email] http://www.joachim-breitner.de/ _______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs signature.asc (849 bytes) Download Attachment |
Hey Matt, cool idea! Also it looks like such a tool could 'solve' stream fusion: https://ghc.haskell.org/trac/2018-02-27 18:01 GMT+01:00 Joachim Breitner <[hidden email]>: Hi, _______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
In reply to this post by Joachim Breitner-2
You have identified a small inaccuracy in my original email.
It is true that ultimately 3 == 0 will be evaluated but these constant folding opportunities are only applied later after other inlining takes place. It becomes quite crucial under this scheme when different optimisations happen because when we inline a recursive function, we have to make sure to apply the right evaluation steps before trying to simplify the function body. In my hacked together implementation of this, constant folding happens too late so only the algebraic version teminated. Cheers, Matt On Tue, Feb 27, 2018 at 5:01 PM, Joachim Breitner <[hidden email]> wrote: > Hi, > > something like this would be great. I don’t have a sense yet of what > “something” should be like. > > > Am Dienstag, den 27.02.2018, 09:59 +0000 schrieb Matthew Pickering: >> To go back to the power example, the recursive >> condition would have to be an inductively defined natural (data N = Z >> | S N) rather than an Int as the comparison operator for integers >> can't be evaluated by the optimiser. > > Sure they can: > > $ cat ConstantFolding.hs > {-# LANGUAGE TemplateHaskell #-} > {-# OPTIONS_GHC -fplugin=Test.Inspection.Plugin #-} > module ConstantFolding where > > import Test.Inspection > > ltInt :: Bool > ltInt = (3::Int) > 2 > > ltInteger :: Bool > ltInteger = (3::Integer) > 2 > > true :: Bool > true = True > > > inspect $ 'ltInt === 'true > inspect $ 'ltInteger === 'true > > $ ghc -O ConstantFolding.hs > [1 of 1] Compiling ConstantFolding ( ConstantFolding.hs, > ConstantFolding.o ) > ConstantFolding.hs:17:1: ltInt === true passed. > ConstantFolding.hs:18:1: ltInteger === true passed. > inspection testing successful > expected successes: 2 > > > > As an alternative with a maybe simpler user interface (and probably > less power), I wonder if we can create a magic function >> compileTimeWHNF :: a -> a > or >> compileTimeNF :: a -> a > and a GHC core plugin (or eventually built-in thing) that finds these > magic functions and evaluates their arguments, using the simplifier. > > > Cheers, > Joachim > > -- > Joachim Breitner > [hidden email] > http://www.joachim-breitner.de/ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
> In my hacked together implementation of this, constant folding happens
too late so only the algebraic version teminated. ah, very good point! Joachim Am 28. Februar 2018 06:26:35 EST schrieb Matthew Pickering <[hidden email]>: >You have identified a small inaccuracy in my original email. > >It is true that ultimately 3 == 0 will be evaluated but these constant >folding opportunities are only applied later after other inlining >takes place. > >It becomes quite crucial under this scheme when different >optimisations happen because when we inline a recursive function, we >have to make sure to apply the right evaluation steps before trying to >simplify the function body. >In my hacked together implementation of this, constant folding happens >too late so only the algebraic version teminated. > >Cheers, > >Matt > >On Tue, Feb 27, 2018 at 5:01 PM, Joachim Breitner ><[hidden email]> wrote: >> Hi, >> >> something like this would be great. I don’t have a sense yet of what >> “something” should be like. >> >> >> Am Dienstag, den 27.02.2018, 09:59 +0000 schrieb Matthew Pickering: >>> To go back to the power example, the recursive >>> condition would have to be an inductively defined natural (data N = >Z >>> | S N) rather than an Int as the comparison operator for integers >>> can't be evaluated by the optimiser. >> >> Sure they can: >> >> $ cat ConstantFolding.hs >> {-# LANGUAGE TemplateHaskell #-} >> {-# OPTIONS_GHC -fplugin=Test.Inspection.Plugin #-} >> module ConstantFolding where >> >> import Test.Inspection >> >> ltInt :: Bool >> ltInt = (3::Int) > 2 >> >> ltInteger :: Bool >> ltInteger = (3::Integer) > 2 >> >> true :: Bool >> true = True >> >> >> inspect $ 'ltInt === 'true >> inspect $ 'ltInteger === 'true >> >> $ ghc -O ConstantFolding.hs >> [1 of 1] Compiling ConstantFolding ( ConstantFolding.hs, >> ConstantFolding.o ) >> ConstantFolding.hs:17:1: ltInt === true passed. >> ConstantFolding.hs:18:1: ltInteger === true passed. >> inspection testing successful >> expected successes: 2 >> >> >> >> As an alternative with a maybe simpler user interface (and probably >> less power), I wonder if we can create a magic function >>> compileTimeWHNF :: a -> a >> or >>> compileTimeNF :: a -> a >> and a GHC core plugin (or eventually built-in thing) that finds these >> magic functions and evaluates their arguments, using the simplifier. >> >> >> Cheers, >> Joachim >> >> -- >> Joachim Breitner >> [hidden email] >> http://www.joachim-breitner.de/ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
Free forum by Nabble | Edit this page |