Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to compile Haskell into the untyped lambda calculus (or GHC core)?

I'm looking for ways how to convert a simple Haskell program (no imported libraries, just data types and pure functions) into a term of the untyped lambda calculus. A promising approach seems to be to use GHC API to compile a program into GHC core, which can be then converted into the untyped lambda calculus.

How to use GHC API to load a Haskell program and compile it into Core?

like image 372
Petr Avatar asked Dec 24 '14 10:12

Petr


1 Answers

From the GHC module documentation in the ghc docs:

compileToCoreModule :: GhcMonad m => FilePath -> m CoreModule

This is the way to get access to the Core bindings corresponding to a module. compileToCore parses, typechecks, and desugars the module, then returns the resulting Core module (consisting of the module name, type declarations, and function declarations) if successful.

compileToCoreSimplified :: GhcMonad m => FilePath -> m CoreModule

Like compileToCoreModule, but invokes the simplifier, so as to return simplified and tidied Core.

I found this by looking through the list of GHC modules, noticing the Desugar module, noticing ModGuts in the result of deSugar, downloading all of the documentation, and searching the text for ModGuts.

Minimal Example

Our example will compile a simple module so we can see what the core looks like. It uses ghc-paths to provide the location of the ghc libs directory. The core will be represented in memory by a CoreModule containing a list of CoreBinds. We can't dump the AST directly because there aren't Show instances for the AST described in CoreSyn, however the Outputable instance for CoreModule will pretty-print the core so we can see that we compiled to core.

import GHC
import DynFlags
import Outputable (Outputable, showPpr)
import qualified GHC.Paths as Paths

import Data.Functor

runGhc' takes care of all the setup needed for compiling to core a module with no imports and no TemplateHaskell. We completely turn off the linker with NoLink and tell the compiler to produce nothing with HscNothing.

runGhc' :: Ghc a -> IO a
runGhc' ga = do
    runGhc (Just Paths.libdir) $ do
        dflags <- getDynFlags
        let dflags2 = dflags { ghcLink   = NoLink
                             , hscTarget = HscNothing
                             }
        setSessionDynFlags dflags2
        ga

Compiling a module to core consists of setting the target with guessTarget and addTarget, optionally loading dependencies with load, building the module graph with depanel, finding the correct ModSummary in the module graph, parsing the module with parseModule, type checking it with typecheckModule, desugarring it with desugarModule, converting it to ModGuts with coreModule from the DesugaredMod instance for the result of desugarring, and extracting the core from the ModGuts. All of this is wrapped up in a nice package by compileToCoreModule.

compileExample :: Ghc CoreModule
compileExample = compileToCoreModule "prettyPrint2dList.hs"

Our whole example program will output the core with showPpr.

showPpr' :: (Functor m, Outputable a, HasDynFlags m) => a -> m String
showPpr' a = (flip showPpr) a <$> getDynFlags

main = runGhc' (compileExample >>= showPpr') >>= putStrLn

Compiling the above example requires the -package ghc flag to expose the normally hidden ghc api package.

The example module we'll compile to core, "prettyPrint2dList.hs", contains a data type and a bit of code that uses functions from the prelude.

data X = Y | Z
         deriving (Eq, Show)

type R = [X]
type W = [R]

example = map (\x -> take x (cycle [Y, Z])) [0..]

main = undefined

Which produces a slew of pretty-printed core.

%module main:Main (Safe-Inferred) [01D :-> Identifier `:Main.main',
                                   a1f2 :-> Identifier `$c==', a1f5 :-> Identifier `$c/=',
                                   a1fb :-> Identifier `$cshowsPrec', a1fh :-> Identifier `$cshow',
                                   a1fk :-> Identifier `$cshowList',
                                   r0 :-> Identifier `Main.$fShowX', r1 :-> Identifier `Main.$fEqX',
                                   r2 :-> Type constructor `Main.R',
                                   r3 :-> Type constructor `Main.X', r4 :-> Identifier `Main.main',
                                   rqS :-> Type constructor `Main.W',
                                   rrS :-> Data constructor `Main.Y', rrV :-> Identifier `Main.Y',
                                   rrW :-> Data constructor `Main.Z', rrX :-> Identifier `Main.Z',
                                   rL2 :-> Identifier `Main.example']
Main.example :: [[Main.X]]
[LclIdX, Str=DmdType]
Main.example =
  GHC.Base.map
    @ GHC.Types.Int
    @ [Main.X]
    (\ (x :: GHC.Types.Int) ->
       GHC.List.take
         @ Main.X
         x
         (GHC.List.cycle
            @ Main.X
            (GHC.Types.:
               @ Main.X
               Main.Y
               (GHC.Types.: @ Main.X Main.Z (GHC.Types.[] @ Main.X)))))
    (GHC.Enum.enumFrom
       @ GHC.Types.Int GHC.Enum.$fEnumInt (GHC.Types.I# 0))
Main.main :: forall t. t
[LclIdX, Str=DmdType]
Main.main = GHC.Err.undefined
$cshowsPrec :: GHC.Types.Int -> Main.X -> GHC.Show.ShowS
[LclId, Str=DmdType]
$cshowsPrec =
  \ _ [Occ=Dead] (ds_d1gG :: Main.X) ->
    case ds_d1gG of _ [Occ=Dead] {
      Main.Y ->
        GHC.Show.showString
          (GHC.Types.:
             @ GHC.Types.Char
             (GHC.Types.C# 'Y')
             (GHC.Types.[] @ GHC.Types.Char));
      Main.Z ->
        GHC.Show.showString
          (GHC.Types.:
             @ GHC.Types.Char
             (GHC.Types.C# 'Z')
             (GHC.Types.[] @ GHC.Types.Char))
    }
Main.$fShowX [InlPrag=[ALWAYS] CONLIKE] :: GHC.Show.Show Main.X
[LclIdX[DFunId],
 Str=DmdType,
 Unf=DFun: \ ->
       GHC.Show.D:Show TYPE Main.X $cshowsPrec $cshow $cshowList]
Main.$fShowX =
  GHC.Show.D:Show @ Main.X $cshowsPrec $cshow $cshowList;
$cshowList [Occ=LoopBreaker] :: [Main.X] -> GHC.Show.ShowS
[LclId, Str=DmdType]
$cshowList =
  GHC.Show.showList__
    @ Main.X
    (GHC.Show.showsPrec @ Main.X Main.$fShowX (GHC.Types.I# 0));
$cshow [Occ=LoopBreaker] :: Main.X -> GHC.Base.String
[LclId, Str=DmdType]
$cshow = GHC.Show.$dmshow @ Main.X Main.$fShowX;
$c== :: Main.X -> Main.X -> GHC.Types.Bool
[LclId, Str=DmdType]
$c== =
  \ (ds_d1gB :: Main.X) (ds_d1gC :: Main.X) ->
    let {
      fail_d1gD :: GHC.Prim.Void# -> GHC.Types.Bool
      [LclId, Str=DmdType]
      fail_d1gD = \ _ [Occ=Dead, OS=OneShot] -> GHC.Types.False } in
    case ds_d1gB of _ [Occ=Dead] {
      Main.Y ->
        case ds_d1gC of _ [Occ=Dead] {
          __DEFAULT -> fail_d1gD GHC.Prim.void#;
          Main.Y -> GHC.Types.True
        };
      Main.Z ->
        case ds_d1gC of _ [Occ=Dead] {
          __DEFAULT -> fail_d1gD GHC.Prim.void#;
          Main.Z -> GHC.Types.True
        }
    }
Main.$fEqX [InlPrag=[ALWAYS] CONLIKE] :: GHC.Classes.Eq Main.X
[LclIdX[DFunId],
 Str=DmdType,
 Unf=DFun: \ -> GHC.Classes.D:Eq TYPE Main.X $c== $c/=]
Main.$fEqX = GHC.Classes.D:Eq @ Main.X $c== $c/=;
$c/= [Occ=LoopBreaker] :: Main.X -> Main.X -> GHC.Types.Bool
[LclId, Str=DmdType]
$c/= =
  \ (a :: Main.X) (b :: Main.X) ->
    GHC.Classes.not (GHC.Classes.== @ Main.X Main.$fEqX a b);
:Main.main :: GHC.Types.IO GHC.Prim.Any
[LclIdX, Str=DmdType]
:Main.main =
  GHC.TopHandler.runMainIO
    @ GHC.Prim.Any (Main.main @ (GHC.Types.IO GHC.Prim.Any))
like image 94
Cirdec Avatar answered Sep 26 '22 07:09

Cirdec