How to implement a basic Dhall-to-JS (or any non-config lang) compiler?

[NickSeagull]

Continued from this Twitter thread.

My idea is to be able to output code that can have scoped variables, and to be able to typecheck at Dhall level that the variables exists before using them.

My initial idea was to have code like:

let env1 = Const 'x' 1 emptyEnv
let env2 = Const 'y' 2 env1
let res = Call 'add' [Get 'x' env2, Get 'y' env2]
let env3 = Const 'z' res env2
in print (Get 'z' env3)

to output

const x = 1
const y = 2
const z = add(x, y)
print(z)

and of course to fail when attempting to:

Get 'foo' env3

---

At this point @Gabriel439 suggested that it could be possible to implement a Dhall-to-JS compiler that could compile Dhall code like:

let x = 1
let y = 1
let z = x + y
in  JavaScript/print z

into the output example above.

---

Note: I'm using JS as an example right now. My idea is to leverage Dhall turing-non-completeness to be able to output programs that aren't turing complete as well, that could serve as a part of a runtime or something.

[Gabriella439]

Here is an example of compiling a very limited subset of Dhall to JavaScript which shows the parts of the API that are most relevant to this task and also shows some common idioms when compiling to other languages.

Note that you can pre-normalize the Dhall expression before compiling to JavaScript, which means that you don't need to compile as many Dhall language features if you do so:

{-# LANGUAGE FlexibleContexts  #-}
{-# LANGUAGE NamedFieldPuns    #-}
{-# LANGUAGE OverloadedLists   #-}
{-# LANGUAGE OverloadedStrings #-}

{-# OPTIONS_GHC -Wall #-}

module Main where

import Control.Exception (Exception(..))
import Control.Monad.Except (MonadError(..))
import Control.Monad.State (MonadState(..))
import Data.Text (Text)
import Data.Void (Void)
import Dhall.Core
    ( Binding(..)
    , Const(..)
    , Expr(..)
    , FunctionBinding(..)
    , Var(..)
    )
import Language.JavaScript.Parser.AST
    ( JSAnnot(..)
    , JSAssignOp(..)
    , JSAST(..)
    , JSBinOp(..)
    , JSBlock(..)
    , JSCommaList(..)
    , JSExpression(..)
    , JSIdent(..)
    , JSStatement(..)
    , JSSemi(..)
    )

import qualified Control.Lens                       as Lens
import qualified Control.Monad.Trans.State.Strict   as State
import qualified Data.Text                          as Text
import qualified Data.Text.IO                       as Text.IO
import qualified Data.Text.Lazy.IO                  as Text.Lazy.IO
import qualified Dhall.Core
import qualified Dhall.Context                      as Context
import qualified Dhall.Import                       as Import
import qualified Dhall.Parser                       as Parser
import qualified Dhall.TypeCheck                    as TypeCheck
import qualified Language.JavaScript.Pretty.Printer as JavaScript
import qualified Options.Generic                    as Options
import qualified System.FilePath                    as FilePath

main :: IO ()
main = do
    file <- Options.getRecord
        "Convert a Dhall expression to a JavaScript expression"

    let rootDirectory = FilePath.takeDirectory file

    -- This context implements Haskell-style monadic IO.  Feel free to model
    -- JavaScript IO in a different way if you prefer
    --
    -- IO : Type → Type
    -- IO/pure : ∀(a : Type) → a → IO a
    -- IO/bind : ∀(a : Type) → ∀(b : Type) → IO a → (a → IO b) → IO b
    -- IO/print : Text → IO {}
    let context =
          ( Context.insert "IO/print"
              (Pi Nothing "_" Text (App "IO" (Record [])))
          . Context.insert "IO/bind"
              (Pi Nothing "a" (Const Type)
                  (Pi Nothing "b" (Const Type)
                      (Pi Nothing "_" (App "IO" "a")
                          (Pi Nothing "_" (Pi Nothing "_" "a" (App "IO" "b"))
                              (App "IO" "b")
                          )
                      )
                  )
              )
          . Context.insert "IO/pure"
              (Pi Nothing "a" (Const Type)
                  (Pi Nothing "_" "a" (App "IO" "a"))
              )
          . Context.insert "IO" (Pi Nothing "_" (Const Type) (Const Type))
          ) Context.empty

    contents <- Text.IO.readFile file

    parsedExpression <- Dhall.Core.throws (Parser.exprFromText file contents)

    -- Resolve imports before compiling to JavaScript (mainly, because I assume
    -- that you don't want to compile Dhall imports to JavaScript imports)
    let status =
            ( Lens.set Import.startingContext context
            ) (Import.emptyStatus rootDirectory)

    resolvedExpression <- do
        State.evalStateT (Import.loadWith parsedExpression) status

    _ <- Dhall.Core.throws (TypeCheck.typeWith context resolvedExpression)

    -- You can optionally `Dhall.normalize` the `resolvedExpression` before
    -- compiling it if you don't want to compile all of Dhall's language
    -- features to JavaScript (e.g. `let`).  This will likely generate nicer
    -- JavaScript, too.
    let normalizedExpression = {- Dhall.Core.normalize -} resolvedExpression

    jsAST <- Dhall.Core.throws (State.evalStateT (expressionToProgram (Dhall.Core.denote normalizedExpression)) 0)

    Text.Lazy.IO.putStrLn (JavaScript.renderToText jsAST)

data CompileError = CompileError Text
    deriving (Show)

instance Exception CompileError where
    displayException (CompileError message) = Text.unpack message

fresh :: MonadState Int m => m Text
fresh = do
    n <- get
    put $! n + 1
    return (Text.pack ("result" <> show n))

-- | Dhall to JavaScript compiler
expressionToProgram
    :: (MonadError CompileError m, MonadState Int m)
    => Expr Void Void -> m JSAST
expressionToProgram expression = do
    statements <- expressionToStatements expression

    return (JSAstProgram statements JSNoAnnot)

expressionToStatements
    :: (MonadError CompileError m, MonadState Int m)
    => Expr Void Void -> m [JSStatement]
expressionToStatements (Let binding body) = do
    jsBinding <- bindingToStatement binding

    statements <- expressionToStatements body

    return (jsBinding : statements)
expressionToStatements (App (App "IO/return" _) expression) = do
    jsExpression <- expressionToExpression expression

    let statement = JSReturn JSAnnotSpace (Just jsExpression) (JSSemi JSNoAnnot)

    return [ statement ]
expressionToStatements (App (App (App (App "IO/bind" _) _) m) f) = do
    jsM <- expressionToStatements m

    let block = JSBlock JSAnnotSpace jsM JSAnnotSpace

    let function = JSFunctionExpression JSAnnotSpace JSIdentNone JSNoAnnot JSLNil JSNoAnnot block

    let invocation = JSCallExpression function JSNoAnnot JSLNil JSNoAnnot

    name <- fresh

    let statement =
            JSAssignStatement (JSIdentifier JSAnnotSpace (Text.unpack name)) (JSAssign JSAnnotSpace) invocation (JSSemi JSNoAnnot)

    statements <- expressionToStatements (App f (Var (V name 0)))

    return (statement : statements)
expressionToStatements (App "IO/print" x) = do
    jsX <- expressionToExpression x

    let expression =
            JSCallExpression (JSIdentifier JSAnnotSpace "print") JSNoAnnot (JSLOne jsX) JSNoAnnot

    let statement = JSExpressionStatement expression (JSSemi JSNoAnnot)

    return [ statement ]
expressionToStatements expression = do
    jsExpression <- expressionToExpression expression

    let statement = JSExpressionStatement jsExpression (JSSemi JSNoAnnot)

    return [ statement ]

bindingToStatement
    :: (MonadError CompileError m, MonadState Int m)
    => Binding Void Void -> m JSStatement
bindingToStatement Binding{ variable, value } = do
    let jsVariable = JSIdentifier JSAnnotSpace (Text.unpack variable)

    jsValue <- expressionToExpression value

    let assignment =
            JSAssignExpression jsVariable (JSAssign JSAnnotSpace) jsValue

    return (JSConstant JSAnnotSpace (JSLOne assignment) (JSSemi JSNoAnnot))

expressionToExpression
    :: (MonadError CompileError m, MonadState Int m)
    => Expr Void Void -> m JSExpression
expressionToExpression (Var (V x 0)) = do
    return (JSIdentifier JSAnnotSpace (Text.unpack x))
expressionToExpression (Lam _ FunctionBinding{ functionBindingVariable } body) = do
    let argument =
            JSLOne (JSIdentifier JSNoAnnot (Text.unpack functionBindingVariable))

    jsBody <- expressionToStatements body

    let block = JSBlock JSAnnotSpace jsBody JSAnnotSpace

    return (JSFunctionExpression JSNoAnnot JSIdentNone JSNoAnnot argument JSNoAnnot block)
expressionToExpression (App function argument) = do
    jsFunction <- expressionToExpression function

    jsArgument <- expressionToExpression argument

    return (JSCallExpression jsFunction JSAnnotSpace (JSLOne jsArgument) JSNoAnnot)
expressionToExpression (NaturalLit number) = do
    return (JSDecimal JSAnnotSpace (show number))
expressionToExpression NaturalShow = do
    let argument = JSLOne (JSIdentifier JSNoAnnot "x")
    let toString = JSCallExpression (JSIdentifier JSNoAnnot "toString") JSNoAnnot JSLNil JSNoAnnot
    let expression = JSCallExpressionDot (JSIdentifier JSAnnotSpace "x") JSNoAnnot toString
    let statement = JSReturn JSAnnotSpace (Just expression) (JSSemi JSNoAnnot)
    let body = JSBlock JSAnnotSpace [ statement ] JSAnnotSpace
    return (JSFunctionExpression JSNoAnnot JSIdentNone JSNoAnnot argument JSNoAnnot body)
expressionToExpression (NaturalPlus left right) = do
    jsLeft <- expressionToExpression left

    jsRight <- expressionToExpression right

    return (JSExpressionBinary jsLeft (JSBinOpPlus JSAnnotSpace) jsRight)
expressionToExpression expression = do
    throwError (CompileError ("Unexpected expression: " <> Dhall.Core.pretty expression))

Note that this does not generate very pretty JavaScript code since I wrote this in a hurry, but here are some examples of progressively increasing complexity:

Before:

let x = 1
let y = 1
let z = x + y
in  z

After:

 const x = 1; const y = 1; const z = x + y; z;

Before:

let x = 1
let y = 1
let z = x + y
in  IO/print (Natural/show z)

After:

 const x = 1; const y = 1; const z = x + y; print(function(x) { return x.toString(); } ( z));

Before:

let x = 1
let y = 1
let z = x + y
in  IO/bind {} {} (IO/print (Natural/show z)) (λ(_ : {}) →
    IO/print (Natural/show y) )

After:

 const x = 1; const y = 1; const z = x + y; result0 = function() { print(function(x) { return x.toString(); } ( z)); }();function(_) { print(function(x) { return x.toString(); } ( y)); } ( result0);

With a bit of effort you can generate nicer JavaScript than that.

Also, for this example I went with a Haskell-style monadic IO embedding of JavaScript side effects in Dhall. This is not the only way to model JavaScript effects in Dhall, though.

[NickSeagull]

Thanks a lot, this is great!

[joneshf]

Here's another example of a Dhall-to-JS compiler: https://github.com/joneshf/open-source/tree/e3412fc68c654d89a8d3af4e12ac19c70e3055ec/packages/dhall-javascript.

I wrote this a few years ago, and it worked at the time, but that was against 1.21.0. I'm sure a lot of stuff is different, but the general idea is there if you'd like an additional reference.