Re: abstract interpreter for GHC Core or STG
IMO supercompilation is related to abstract interpretation. In fact an abstract interpreter can behave as a concrete interpreter until multiple program states merge into a single state. In that case the interpreter has to give up precision and introduce abstract values. This technique is called abstract counting, see: https://matt.might.net/papers/might2006gcfa.pdf So it seems that GHC's supercompiler related work is relevant to what I'd like to do. (i.e. Supercompilation by Evaluation <https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/supercomp-by-eval.pdf> ) What primops and RTS/FFI features were supported by the GHC Core supercompiler? On Wed, Jun 9, 2021 at 12:26 AM Csaba Hruska wrote: > The external STG interpreter implements the RTS semantics and features, so > if we apply the calculating correct compiler method to the external STG > interpreter code then we should get an IR that will include the RTS code > also. > > On Wed, Jun 9, 2021 at 12:21 AM Carter Schonwald < > carter.schonw...@gmail.com> wrote: > >> How would this be used to generate the rts automatically? I’m intrigued / >> would like to understand what you’re envisioning design wise for that leg. >> >> On Tue, Jun 8, 2021 at 5:34 PM Csaba Hruska >> wrote: >> >>> Cmm is too low level, I've implemented the primops in haskell in a high >>> level way, including the out of line primops with the rts related parts >>> (scheduler, io manager). >>> see: >>> >>> https://github.com/grin-compiler/ghc-whole-program-compiler-project/blob/master/external-stg-interpreter/lib/Stg/Interpreter/ThreadScheduler.hs >>> >>> https://github.com/grin-compiler/ghc-whole-program-compiler-project/tree/master/external-stg-interpreter/lib/Stg/Interpreter/PrimOp >>> >>> STM is still missing though, but IMO it would be similar to >>> concurrency/exception related primops. >>> Regarding the ghcjs STM implementation, IMO the primops needs to be >>> implemented at least in Haskell in a pure way with ADTs to be easy for >>> reasoning. >>> But thanks for the reference. >>> >>> Currently, I'm in the design phase. I.e. I need to design the abstract >>> domain of the STG machine values. >>> >>> If this approach succeeds then it would be interesting to apply the >>> calculating correct compilers method on the stg interpreter to get a >>> compiler form it. >>> With this level of automation it would be extremely easy to support new >>> target platforms, because the RTS would be generated automatically. >>> >>> On Tue, Jun 8, 2021 at 10:51 PM Carter Schonwald < >>> carter.schonw...@gmail.com> wrote: >>> >>>> The stm impl In ghcjs might be a helpful comparative example on that >>>> front. >>>> >>>> Though I guess more broadly does this necessitate having a model of the >>>> Cmm semantics for the out of line primops ? >>>> >>>> On Tue, Jun 8, 2021 at 5:10 AM Simon Peyton Jones via ghc-devs < >>>> ghc-devs@haskell.org> wrote: >>>> >>>>> I wonder if there was an attempt in the past to create an abstract >>>>> interpreter for GHC Core or STG to approximate the program runtime >>>>> behaviour? >>>>> >>>>> >>>>> >>>>> No, not that I know of. Because of all the primops, concurrency, >>>>> STM, etc, it would be something of a challenge. The AAM story could be >>>>> interesting… >>>>> >>>>> >>>>> >>>>> Simon >>>>> >>>>> >>>>> >>>>> *From:* ghc-devs *On Behalf Of *Csaba >>>>> Hruska >>>>> *Sent:* 07 June 2021 15:18 >>>>> *To:* GHC developers >>>>> *Subject:* abstract interpreter for GHC Core or STG >>>>> >>>>> >>>>> >>>>> Hello, >>>>> >>>>> >>>>> >>>>> I wonder if there was an attempt in the past to create an abstract >>>>> interpreter for GHC Core or STG to approximate the program runtime >>>>> behaviour? >>>>> >>>>> I'm curious because I'd like to turn my external STG interterpreter to >>>>> an abstract interpreter using the AAM (Abstracting Abstract Machines) >>>>> method. >>>>> >>>>> This approach seems promising to me because a single Haskell code base >>>>> (ext STG interpreter) could be the specification of the Haskell >>>>> operational >>>>> semantics and also be a detailed static analyzer that could help >>>>> optimization transformations. >>>>> >>>>> I'm interested in any attempt that happened during GHC/Haskell >>>>> evolution. >>>>> >>>>> >>>>> >>>>> Regards, >>>>> >>>>> Csaba Hruska >>>>> ___ >>>>> ghc-devs mailing list >>>>> ghc-devs@haskell.org >>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >>>>> >>>> ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: abstract interpreter for GHC Core or STG
The external STG interpreter implements the RTS semantics and features, so if we apply the calculating correct compiler method to the external STG interpreter code then we should get an IR that will include the RTS code also. On Wed, Jun 9, 2021 at 12:21 AM Carter Schonwald wrote: > How would this be used to generate the rts automatically? I’m intrigued / > would like to understand what you’re envisioning design wise for that leg. > > On Tue, Jun 8, 2021 at 5:34 PM Csaba Hruska > wrote: > >> Cmm is too low level, I've implemented the primops in haskell in a high >> level way, including the out of line primops with the rts related parts >> (scheduler, io manager). >> see: >> >> https://github.com/grin-compiler/ghc-whole-program-compiler-project/blob/master/external-stg-interpreter/lib/Stg/Interpreter/ThreadScheduler.hs >> >> https://github.com/grin-compiler/ghc-whole-program-compiler-project/tree/master/external-stg-interpreter/lib/Stg/Interpreter/PrimOp >> >> STM is still missing though, but IMO it would be similar to >> concurrency/exception related primops. >> Regarding the ghcjs STM implementation, IMO the primops needs to be >> implemented at least in Haskell in a pure way with ADTs to be easy for >> reasoning. >> But thanks for the reference. >> >> Currently, I'm in the design phase. I.e. I need to design the abstract >> domain of the STG machine values. >> >> If this approach succeeds then it would be interesting to apply the >> calculating correct compilers method on the stg interpreter to get a >> compiler form it. >> With this level of automation it would be extremely easy to support new >> target platforms, because the RTS would be generated automatically. >> >> On Tue, Jun 8, 2021 at 10:51 PM Carter Schonwald < >> carter.schonw...@gmail.com> wrote: >> >>> The stm impl In ghcjs might be a helpful comparative example on that >>> front. >>> >>> Though I guess more broadly does this necessitate having a model of the >>> Cmm semantics for the out of line primops ? >>> >>> On Tue, Jun 8, 2021 at 5:10 AM Simon Peyton Jones via ghc-devs < >>> ghc-devs@haskell.org> wrote: >>> >>>> I wonder if there was an attempt in the past to create an abstract >>>> interpreter for GHC Core or STG to approximate the program runtime >>>> behaviour? >>>> >>>> >>>> >>>> No, not that I know of. Because of all the primops, concurrency, STM, >>>> etc, it would be something of a challenge. The AAM story could be >>>> interesting… >>>> >>>> >>>> >>>> Simon >>>> >>>> >>>> >>>> *From:* ghc-devs *On Behalf Of *Csaba >>>> Hruska >>>> *Sent:* 07 June 2021 15:18 >>>> *To:* GHC developers >>>> *Subject:* abstract interpreter for GHC Core or STG >>>> >>>> >>>> >>>> Hello, >>>> >>>> >>>> >>>> I wonder if there was an attempt in the past to create an abstract >>>> interpreter for GHC Core or STG to approximate the program runtime >>>> behaviour? >>>> >>>> I'm curious because I'd like to turn my external STG interterpreter to >>>> an abstract interpreter using the AAM (Abstracting Abstract Machines) >>>> method. >>>> >>>> This approach seems promising to me because a single Haskell code base >>>> (ext STG interpreter) could be the specification of the Haskell operational >>>> semantics and also be a detailed static analyzer that could help >>>> optimization transformations. >>>> >>>> I'm interested in any attempt that happened during GHC/Haskell >>>> evolution. >>>> >>>> >>>> >>>> Regards, >>>> >>>> Csaba Hruska >>>> ___ >>>> ghc-devs mailing list >>>> ghc-devs@haskell.org >>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >>>> >>> ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: abstract interpreter for GHC Core or STG
How would this be used to generate the rts automatically? I’m intrigued / would like to understand what you’re envisioning design wise for that leg. On Tue, Jun 8, 2021 at 5:34 PM Csaba Hruska wrote: > Cmm is too low level, I've implemented the primops in haskell in a high > level way, including the out of line primops with the rts related parts > (scheduler, io manager). > see: > > https://github.com/grin-compiler/ghc-whole-program-compiler-project/blob/master/external-stg-interpreter/lib/Stg/Interpreter/ThreadScheduler.hs > > https://github.com/grin-compiler/ghc-whole-program-compiler-project/tree/master/external-stg-interpreter/lib/Stg/Interpreter/PrimOp > > STM is still missing though, but IMO it would be similar to > concurrency/exception related primops. > Regarding the ghcjs STM implementation, IMO the primops needs to be > implemented at least in Haskell in a pure way with ADTs to be easy for > reasoning. > But thanks for the reference. > > Currently, I'm in the design phase. I.e. I need to design the abstract > domain of the STG machine values. > > If this approach succeeds then it would be interesting to apply the > calculating correct compilers method on the stg interpreter to get a > compiler form it. > With this level of automation it would be extremely easy to support new > target platforms, because the RTS would be generated automatically. > > On Tue, Jun 8, 2021 at 10:51 PM Carter Schonwald < > carter.schonw...@gmail.com> wrote: > >> The stm impl In ghcjs might be a helpful comparative example on that >> front. >> >> Though I guess more broadly does this necessitate having a model of the >> Cmm semantics for the out of line primops ? >> >> On Tue, Jun 8, 2021 at 5:10 AM Simon Peyton Jones via ghc-devs < >> ghc-devs@haskell.org> wrote: >> >>> I wonder if there was an attempt in the past to create an abstract >>> interpreter for GHC Core or STG to approximate the program runtime >>> behaviour? >>> >>> >>> >>> No, not that I know of. Because of all the primops, concurrency, STM, >>> etc, it would be something of a challenge. The AAM story could be >>> interesting… >>> >>> >>> >>> Simon >>> >>> >>> >>> *From:* ghc-devs *On Behalf Of *Csaba >>> Hruska >>> *Sent:* 07 June 2021 15:18 >>> *To:* GHC developers >>> *Subject:* abstract interpreter for GHC Core or STG >>> >>> >>> >>> Hello, >>> >>> >>> >>> I wonder if there was an attempt in the past to create an abstract >>> interpreter for GHC Core or STG to approximate the program runtime >>> behaviour? >>> >>> I'm curious because I'd like to turn my external STG interterpreter to >>> an abstract interpreter using the AAM (Abstracting Abstract Machines) >>> method. >>> >>> This approach seems promising to me because a single Haskell code base >>> (ext STG interpreter) could be the specification of the Haskell operational >>> semantics and also be a detailed static analyzer that could help >>> optimization transformations. >>> >>> I'm interested in any attempt that happened during GHC/Haskell evolution. >>> >>> >>> >>> Regards, >>> >>> Csaba Hruska >>> ___ >>> ghc-devs mailing list >>> ghc-devs@haskell.org >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >>> >> ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: abstract interpreter for GHC Core or STG
Cmm is too low level, I've implemented the primops in haskell in a high level way, including the out of line primops with the rts related parts (scheduler, io manager). see: https://github.com/grin-compiler/ghc-whole-program-compiler-project/blob/master/external-stg-interpreter/lib/Stg/Interpreter/ThreadScheduler.hs https://github.com/grin-compiler/ghc-whole-program-compiler-project/tree/master/external-stg-interpreter/lib/Stg/Interpreter/PrimOp STM is still missing though, but IMO it would be similar to concurrency/exception related primops. Regarding the ghcjs STM implementation, IMO the primops needs to be implemented at least in Haskell in a pure way with ADTs to be easy for reasoning. But thanks for the reference. Currently, I'm in the design phase. I.e. I need to design the abstract domain of the STG machine values. If this approach succeeds then it would be interesting to apply the calculating correct compilers method on the stg interpreter to get a compiler form it. With this level of automation it would be extremely easy to support new target platforms, because the RTS would be generated automatically. On Tue, Jun 8, 2021 at 10:51 PM Carter Schonwald wrote: > The stm impl In ghcjs might be a helpful comparative example on that > front. > > Though I guess more broadly does this necessitate having a model of the > Cmm semantics for the out of line primops ? > > On Tue, Jun 8, 2021 at 5:10 AM Simon Peyton Jones via ghc-devs < > ghc-devs@haskell.org> wrote: > >> I wonder if there was an attempt in the past to create an abstract >> interpreter for GHC Core or STG to approximate the program runtime >> behaviour? >> >> >> >> No, not that I know of. Because of all the primops, concurrency, STM, >> etc, it would be something of a challenge. The AAM story could be >> interesting… >> >> >> >> Simon >> >> >> >> *From:* ghc-devs *On Behalf Of *Csaba >> Hruska >> *Sent:* 07 June 2021 15:18 >> *To:* GHC developers >> *Subject:* abstract interpreter for GHC Core or STG >> >> >> >> Hello, >> >> >> >> I wonder if there was an attempt in the past to create an abstract >> interpreter for GHC Core or STG to approximate the program runtime >> behaviour? >> >> I'm curious because I'd like to turn my external STG interterpreter to an >> abstract interpreter using the AAM (Abstracting Abstract Machines) method. >> >> This approach seems promising to me because a single Haskell code base >> (ext STG interpreter) could be the specification of the Haskell operational >> semantics and also be a detailed static analyzer that could help >> optimization transformations. >> >> I'm interested in any attempt that happened during GHC/Haskell evolution. >> >> >> >> Regards, >> >> Csaba Hruska >> ___ >> ghc-devs mailing list >> ghc-devs@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >> > ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: abstract interpreter for GHC Core or STG
The stm impl In ghcjs might be a helpful comparative example on that front. Though I guess more broadly does this necessitate having a model of the Cmm semantics for the out of line primops ? On Tue, Jun 8, 2021 at 5:10 AM Simon Peyton Jones via ghc-devs < ghc-devs@haskell.org> wrote: > I wonder if there was an attempt in the past to create an abstract > interpreter for GHC Core or STG to approximate the program runtime > behaviour? > > > > No, not that I know of. Because of all the primops, concurrency, STM, > etc, it would be something of a challenge. The AAM story could be > interesting… > > > > Simon > > > > *From:* ghc-devs *On Behalf Of *Csaba > Hruska > *Sent:* 07 June 2021 15:18 > *To:* GHC developers > *Subject:* abstract interpreter for GHC Core or STG > > > > Hello, > > > > I wonder if there was an attempt in the past to create an abstract > interpreter for GHC Core or STG to approximate the program runtime > behaviour? > > I'm curious because I'd like to turn my external STG interterpreter to an > abstract interpreter using the AAM (Abstracting Abstract Machines) method. > > This approach seems promising to me because a single Haskell code base > (ext STG interpreter) could be the specification of the Haskell operational > semantics and also be a detailed static analyzer that could help > optimization transformations. > > I'm interested in any attempt that happened during GHC/Haskell evolution. > > > > Regards, > > Csaba Hruska > ___ > ghc-devs mailing list > ghc-devs@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs > ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
RE: abstract interpreter for GHC Core or STG
I wonder if there was an attempt in the past to create an abstract interpreter for GHC Core or STG to approximate the program runtime behaviour? No, not that I know of. Because of all the primops, concurrency, STM, etc, it would be something of a challenge. The AAM story could be interesting… Simon From: ghc-devs On Behalf Of Csaba Hruska Sent: 07 June 2021 15:18 To: GHC developers Subject: abstract interpreter for GHC Core or STG Hello, I wonder if there was an attempt in the past to create an abstract interpreter for GHC Core or STG to approximate the program runtime behaviour? I'm curious because I'd like to turn my external STG interterpreter to an abstract interpreter using the AAM (Abstracting Abstract Machines) method. This approach seems promising to me because a single Haskell code base (ext STG interpreter) could be the specification of the Haskell operational semantics and also be a detailed static analyzer that could help optimization transformations. I'm interested in any attempt that happened during GHC/Haskell evolution. Regards, Csaba Hruska ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: abstract interpreter for GHC Core or STG
Yes, I've read Thomas Schilling's PhD thesis (Trace-based Just-in-timeCompilation for Lazy Functional Programming Languages) a couple of times. My STG interpreter almost supports all kinds of primops that GHC does, and I plan to add the missing ones in the future. I'd like to use literally the same source code for the concrete and the abstract interpretation. So IMO this would mean that all kinds of runtime properties would be approximated by the abstract interpreter. But the most important property would be the control flow information. On Mon, Jun 7, 2021 at 5:58 PM Carter Schonwald wrote: > Correction it was Thomas schilling !! > And you can Google his Phd thesis trace based just in time compilation for > lazy functional programming languages > > And the associated code is on his GitHub nominolo/ lambdachine though I > think it was last touched 7 years ago > > On Mon, Jun 7, 2021 at 11:54 AM Carter Schonwald < > carter.schonw...@gmail.com> wrote: > >> I’m not aware of any currently. >> >> I would be curious about the now relatively old work that Max bolingbroke >> did for his PhD (I think it was sortah a ghc to Lua JIT?!?) >> >> An important question is : what questions do you want the abstract >> interpreter to suport? >> >> On Mon, Jun 7, 2021 at 10:19 AM Csaba Hruska >> wrote: >> >>> Hello, >>> >>> I wonder if there was an attempt in the past to create an abstract >>> interpreter for GHC Core or STG to approximate the program runtime >>> behaviour? >>> I'm curious because I'd like to turn my external STG interterpreter to >>> an abstract interpreter using the AAM (Abstracting Abstract Machines) >>> method. >>> This approach seems promising to me because a single Haskell code base >>> (ext STG interpreter) could be the specification of the Haskell operational >>> semantics and also be a detailed static analyzer that could help >>> optimization transformations. >>> I'm interested in any attempt that happened during GHC/Haskell evolution. >>> >>> Regards, >>> Csaba Hruska >>> ___ >>> ghc-devs mailing list >>> ghc-devs@haskell.org >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >>> >> ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: abstract interpreter for GHC Core or STG
Correction it was Thomas schilling !! And you can Google his Phd thesis trace based just in time compilation for lazy functional programming languages And the associated code is on his GitHub nominolo/ lambdachine though I think it was last touched 7 years ago On Mon, Jun 7, 2021 at 11:54 AM Carter Schonwald wrote: > I’m not aware of any currently. > > I would be curious about the now relatively old work that Max bolingbroke > did for his PhD (I think it was sortah a ghc to Lua JIT?!?) > > An important question is : what questions do you want the abstract > interpreter to suport? > > On Mon, Jun 7, 2021 at 10:19 AM Csaba Hruska > wrote: > >> Hello, >> >> I wonder if there was an attempt in the past to create an abstract >> interpreter for GHC Core or STG to approximate the program runtime >> behaviour? >> I'm curious because I'd like to turn my external STG interterpreter to an >> abstract interpreter using the AAM (Abstracting Abstract Machines) method. >> This approach seems promising to me because a single Haskell code base >> (ext STG interpreter) could be the specification of the Haskell operational >> semantics and also be a detailed static analyzer that could help >> optimization transformations. >> I'm interested in any attempt that happened during GHC/Haskell evolution. >> >> Regards, >> Csaba Hruska >> ___ >> ghc-devs mailing list >> ghc-devs@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >> > ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: abstract interpreter for GHC Core or STG
I’m not aware of any currently. I would be curious about the now relatively old work that Max bolingbroke did for his PhD (I think it was sortah a ghc to Lua JIT?!?) An important question is : what questions do you want the abstract interpreter to suport? On Mon, Jun 7, 2021 at 10:19 AM Csaba Hruska wrote: > Hello, > > I wonder if there was an attempt in the past to create an abstract > interpreter for GHC Core or STG to approximate the program runtime > behaviour? > I'm curious because I'd like to turn my external STG interterpreter to an > abstract interpreter using the AAM (Abstracting Abstract Machines) method. > This approach seems promising to me because a single Haskell code base > (ext STG interpreter) could be the specification of the Haskell operational > semantics and also be a detailed static analyzer that could help > optimization transformations. > I'm interested in any attempt that happened during GHC/Haskell evolution. > > Regards, > Csaba Hruska > ___ > ghc-devs mailing list > ghc-devs@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs > ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
abstract interpreter for GHC Core or STG
Hello, I wonder if there was an attempt in the past to create an abstract interpreter for GHC Core or STG to approximate the program runtime behaviour? I'm curious because I'd like to turn my external STG interterpreter to an abstract interpreter using the AAM (Abstracting Abstract Machines) method. This approach seems promising to me because a single Haskell code base (ext STG interpreter) could be the specification of the Haskell operational semantics and also be a detailed static analyzer that could help optimization transformations. I'm interested in any attempt that happened during GHC/Haskell evolution. Regards, Csaba Hruska ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
