abstract interpreter for GHC Core or STG

[Csaba Hruska]

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 <csaba.hruska at gmail.com> 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.schonwald at 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 <csaba.hruska at gmail.com>
>> 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.schonwald at 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 at 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 <ghc-devs-bounces at haskell.org> *On Behalf Of *Csaba
>>>>> Hruska
>>>>> *Sent:* 07 June 2021 15:18
>>>>> *To:* GHC developers <ghc-devs at haskell.org>
>>>>> *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 at haskell.org
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>>>>>
>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20210614/463abc2d/attachment.html>