GHC to GRIN?

[grin-compiler]

GHC to GRIN?

[csabahruska]

Hi,

The ghc-grin repository was my first attempt to use GHC Haskell as language frontend for the GRIN optimizer. You are right, the grin repository does not contain any language frontend code. It only implements the GRIN intermediate representation (IR for short) related things: tooling, analysis, optimization and LLVM codegen.

Currently there is no supported way to convert GHC Haskell to GRIN IR, however this approach was my first attempt to implement. The ghc-grin repository contains the code of this experiment.
The lesson of this experiment was that first I have to learn the semantics of STG, GHC primops and GHC runtime system (RTS).
Otherwise I would not know how to translate GHC Core or STG to GRIN correctly. And of course I should test the correctness somehow.
The problem is complex, because GHC has more than 400 primops and the runtime system is feature rich.
So instead of the (obvious/naive) compilation approach I decided to learn the STG/primop/RTS in depth with writing an interpreter for STG, supporting all GHC primos and RTS features. With the interpreter approach I can easily validate my assumptions about the semantics, I just need to run real Haskell programs in the STG interpreter.
So this is the thing that I did instead of the implementing ghc-grin.
The STG interpreter is available in this repository: https://github.com/grin-compiler/ghc-whole-program-compiler-project

My ultimate goal is to use GHC as a Haskell language frontend for the GRIN optimizer, but I'll reach this goal in smaller steps. I also target the problem from two directions:

1. implement the GRIN optimizer
2. understand the GHC backend semantics
3. connect the two worlds

GHC Haskell programs have lots of C code dependencies, either via the RTS or via some cabal packages.
What kind of Haskell programs would you like to compile to hardware?
Can you give an example?

[Tiltedprogrammer]

Hi!

Actually, my programs are in Haskell only due to the current workflow, but essentially they are more like simplified Haskell Core, since I need only case, constructors, variables, function application, and recursion optionally with some integer arithmetics. So, I guess I can implement a corresponding frontend for such a language myself. I've also seen some lambda utilities among the repositories, is there a lambda frontend?

Also, I have a more specific off-topic question. To translate a program to hardware (namely System Verilog) the program should not contain any higher-order functions which at the moment is achieved through defunctionalization. As far as I can tell GRIN does not provide defunctionalization, but am I right that inlining applied to the whole program provides something similar to this?

[csabahruska]

If you want to avoid C-land dependencies then you should not use GHC's Prelude at all. Even the String type (alias [Char]) introduces heavy Unicode related C code dependency. So basically you have to build your own Prelude and base libraries from scratch. I know it sounds bad, but at least it is possible.

Yes the ghc-grin contains some code for lambda frontend, but it does not work. It was just an experiment to explore the design space and try various approaches, but eventually I went to focus on the external STG IR. I did not clean the code, I just left it as it was. After I complete the external STG related things, I'll implement a higher order lambda calculus like IR as a convenience layer for GRIN. But this does not exist now.

GRIN does not implement defunctionaliation transformation. GRIN is a first order IR, so any higher order code should be defunctionalized before the GRIN conversion. BTW, this is why I'd like to implement the lambda calculus like convenience IR. It would provide the defunctionalization transformation for free. But that is future work.

Inlining is orthogonal to defunctionalization.

[Tiltedprogrammer]

BTW, this is why I'd like to implement the lambda calculus like convenience IR. It would provide the defunctionalization transformation for free.

Could you please elaborate about how one would get defunctionalization for free?

There is a procedure in Boquist's thesis about how to translate higher-order functions to GRIN where the apply function quite resembles what one gets with defunctionalization

[csabahruska]

The Boq thesis describes how to convert a closure converted and lambda lifted higher order IR to GRIN.
You're right the 2.5.5 chapter: GRIN code generation describes the defunctionalization step as well when doing conversion from lambda IR to GRIN.

If my lambda IR implementation would include the defunctionalization transformation then the users would get this feature for free.