elm-in-elm / compiler Goto Github PK

cool project!!

in the readme, it mentions this project unlocks new kinds of Elm applications, like Slack bots. i don't understand!

wouldn't it already be feasible to write a Slack bot in Elm, compile it with the standard compiler, and run the JS in node? what am i missing?

Should be similar to how Plus is done. Keep it a separate case in the Frontend.Expr - later we can try to think of a way to abstract all binary operators into something dynamic, read from source instead of baked into the compiler.

• add parser tests
• add a parser
• add optimization tests
  • if the right item (the list) is a literal list (not a variable for example), put the left item into it:
  • myStuff :: [1, 2] should become [myStuff, 1, 2]
• add optimization
• change how Lists are emitted: instead of [1,2,3] do something like List$fromJSArray([1,2,3])?
• add emit tests - (::) should be just a call of Elm function with those two params
• add emit

(EDITED after comments from Jakub)

Ideally we'd like to create an elm-in-elm/core package that does everything elm/core does but in pure Elm (without kernel modules). That won't be entirely possible but we can try and minimize the amount of "magic" Elm needs the underlying platform to support.

Go through all the kernel modules in elm/core and create a table, say in notes/elm-core.md or xls or whatever, documenting which of those can be done in pure Elm. ("Don't know" is OK too!)

In case of any doubts, ask here / in your PR / on Discord!

A compiler needs to read source files and write output files. Practical compilers will also read and write a number of intermediate files, caching build artifacts for incremental compilation reasons.

Elm code cannot interact with the file system; we have to use ports for that. However, the elm code does have to tell the javascript subscribed to the port where to save the file to.

We need to be able to join paths (i.e. add '/' or '' depending on unix/windows), check if files are the same, get the file name from a path, get paths relative to other paths. I think the best way to achieve this is to write an elm-in-elm/path package.

This means:

• add an InferTypesTest.elm in the test project. (You can skip that if it's already done. #39 might do that)
• add a typedExprFuzzer : Type -> Fuzzer Expr function. This should generate a random expression that conforms to the type.
• add the above to write a fuzzInference : Type -> Test function. This should use typedExprFuzzer to test that the random expressions have the input type inferred.
• add type inference tests of the form fuzzInference someTypeToCheck. You can put them in a nested describe for grouping.

The idea is that generating expressions that fit a type should be easier than inferring the type of an expression.

If you get stuck on anything, ask here or on Discord! We'll help you 🙂

Out of scope ❌ ❌ ❌

• Error cases: we are not testing when inference fails and what it reports yet.
• Configuring the depth of the fuzzed expressions.

Kernel functions are defined in JavaScript (no static typing) but can be called from elm (static typing) and thus have some sort of implicit type signature.

For example the kernel function

https://github.com/elm/core/blob/665624859a7a432107059411737e16d1d5cb6373/src/Elm/Kernel/Basics.js#L17

var _Basics_remainderBy = F2(function(b, a) { return a % b; });

is called in elm

https://github.com/elm/core/blob/665624859a7a432107059411737e16d1d5cb6373/src/Basics.elm#L533-L535

remainderBy : Int -> Int -> Int
remainderBy =
  Elm.Kernel.Basics.remainderBy

and so we deduce that a and b must have type Int and the function returns an Int*.

However, other functions have much stranger signatures. For example, what is the type signature for stepperBuilder here?

https://github.com/elm/core/blob/665624859a7a432107059411737e16d1d5cb6373/src/Elm/Kernel/Platform.js#L35

function _Platform_initialize(flagDecoder, args, init, update, subscriptions, stepperBuilder)

It is far from clear. Looking at the use of stepperBuilder

var stepper = stepperBuilder(sendToApp, model);

stepperBuilder is function that takes two arguments (which is not allowed in elm) but what are the types of those arguments? What is the return type?

If elm-in-elm is able to implement kernel code for targets other than javascript, or move logic from "kernel space" into "elm space" then we first need to solidly document all these implicit type signatures.

I am proposing an effort to compliment the documentation written as part of #57 with type signatures.

• There is no checking (neither compile time or run time) that an elm function does not pass a String, List etc to this function. There is no checking that the javascript function actually returns an Int. This is why folk see 96 \= 0 having a type of Bool and a value of 0 (elm/core#1022).

Order of optimizations matters.

It should be possible to look at the list of optimizations in Stage.Optimize.optimizeExpr and either experimentally or in some more scientific way find a better permutation of them.

This will probably need a corpus of programs or an expression fuzzer to evaluate the different orders on.

The result of this issue should be something reproducible, runnable on different inputs and with different set of optimizations to choose from. (ie. if we add a new optimization pass, we should be able to run this to find a new optimal order.)

This Reddit comment in particular seems like a great place to read up on various ways to do this, should you want to.

let
    x = 1
in
    2 + x

can become

2 + 1

(which the plus optimization will then pick up and create 3 from it).

Let's keep it at let inlinings, not top-level inlinings just yet.

It makes sense to me to optimize piece-wise first, then try to inline the optimized stuff, then try optimizing again after inlining. That probably can't be done with what we have now - we'll have to split optimization stage into three: "piece-wise before inlining", "inlining", "piece-wise after inlining".

The workflow deploy-to-gh-pages.yml is referencing action JamesIves/github-pages-deploy-action using references 3.4.9. However this reference is missing the commit 661e33871bce8107c9af083f7415176608dce40e which may contain fix to the some vulnerability.
The vulnerability fix that is missing by actions version could be related to:
(1) CVE fix
(2) upgrade of vulnerable dependency
(3) fix to secret leak and others.
Please consider to update the reference to the action.

Technically an argument is what you pass in, and the parameter defines the var in the function definition. I know people use these as synonyms, but it might make some code cleaner when you can distinguish parameter names (i.e. Lambda) from args (i.e. Call).

Records shouldn't support multiple fields of the same name:

{ a = 123
, a = ()
}

Official Elm compiler says:

This record has multiple `a` fields. One here:

12|     { a = 123
          ^
And another one here:

13|     , a = ()
          ^
How can I know which one you want? Rename one of them!

Currently we don't raise any error and silently drop all but the last field when we transform the List into Dict. Return a DesugarError instead!

Currently if you try to put

module Main exposing (main)

main =
    let
        x = 2
    in
        1 + x

into example-project/src/Main.elm and run it with make, it complains about x not being visible in the body. Make it so!

Depending on where the fix is, it might be a good idea to also add a regression unit test somewhere.

Feel free to discuss/ask how to solve this on our Discord!

Add parser tests for custom types:

type Foo
    = Bar
    | Baz Int
    | Quux (Foo, Foo)

This will most likely not go through Frontend.Expr (as those aren't expressions), but somewhere alongside top-level definitions. Maybe TopLevelDefinition needs to distinguish between expressions and custom types / aliases / port definitions / ...?

❌ NOT IN SCOPE:

• parameterized custom types (let's do that in some other ticket, keep this as small as we can)

This means:

• find all the ways integers can be written in Elm (hex? negative hex? something even more exotic?)
• add those as tests to the "literal int" section of ParserTest.elm so that the tests exercise all the possibilities and truthfully tell us what's done and what's not
• update the "what's done" table in README - parser tests for integers

Blocked by #27

• Make the list parser tests green!

Hi, I'm looking forward to use parts of your libraries (AST, type infer, optimize) to implement my elmsl compiler (elm serverless), which will be implemented in rust and create rust code.

This means:

• add Float constructor to the Literal type... solve any compiler errors that arise as a result (emitExpr etc - look at the Int cases for inspiration, it should be pretty similar)
• find all the ways floats can be written in Elm (1.2? 1.? scientific notation like 2e10? maybe stuff like NaN, Infinity etc? (probably not))... go see official Elm's parser to be sure!
• add those as tests as a "literal float" section of ParserTest.elm (probably doesn't exist yet) so that the tests exercise all the possibilities and truthfully tell us what's done and what's not...
• add emit tests too
• update the "what's done" table in README - parser tests for floats, but probably also optimizations (none), desugaring, typechecking and emitting

When we try to infer the type for the list [ [ "" ], [ "" ] ] we would expect to get List (List String). Instead we get an error complaining about not bein able to unify two type variables:

↓ InferTypesTest
↓ Stage.InferType
↓ fuzz exprInfer
✗ List List String

Given List [List [Literal (String "")],List [Literal (String "")]]

    Err (TypeMismatch (List (Var 7)) (List (Var 6)))
    ╷
    │ Expect.equal
    ╵
    Ok (List (List String))

It seems like we might be missing some equations. Try looking in the list case inside Stage.InferTypes.GenerateEquations.generateEquations.

Fix the string parser implementation such that the string tests pass.

It probably will be a good idea to separate (with P.oneOf) the string parser into normal "..." and multiline """...""" string parsers.

Also, use the unicode and escaping logic that's already in the Char parser!

Elm.Compiler.parseModule produces a parse error on the following valid Elm code:

module Target exposing (..)

something =
    { a = 1
    , b = 2
    }

The error being:

    Err
        (ParseError
            (ParseProblem
                [ { col = 1
                  , contextStack = []
                  , problem = ExpectingModuleKeyword
                  , row = 1
                  }
                , { col = 1, contextStack = [], problem = ExpectingPortKeyword, row = 1 }
                , { col = 1, contextStack = [], problem = ExpectingEffectKeyword, row = 1 }
                ]
            )
        )

SSCCE:

module Main exposing (main)

import Elm.Compiler
import Html


code =
    """
module Target exposing (..)

something =
    { a = 1
    , b = 2
    }
"""


main =
    { filePath = "Target.elm"
    , sourceCode = code
    }
        |> Elm.Compiler.parseModule
        |> Debug.toString
        |> Html.text

We'd like to have some performance tracking over time, similar to https://arewefastyet.com/

Probably don't bother with setting up a webpage that will hold the historic data and add to them - as a first iteration, let's just have a script (possibly in a different repo) that:

• runs the benchmarks suite on all commits in this repo
• outputs values for each commit (those can be N/A if that particular revision didn't support that Elm input and it errors out - that's to be expected)
• and then generates some graphical representation (plaintext generation of SVG? D3? terezka/line-charts / elm-plot / ...? Feel free to choose the easiest solution) or at least a table with the numbers.

We'll need:

• a corpus of interesting projects / modules / expressions to run the benchmarks on
• the ways to run elm-in-elm on each input - possibly this:
  • parse
  • parse + desugar
  • parse + desugar + typecheck
  • parse + desugar + typecheck + optimize
  • parse + desugar + typecheck + optimize + emit
  • maybe with some numerical trickery we can separate those cases from each other so that we know "the desugar phase took this long"
• a script to run benchmarks on each of these
• a script to convert the raw numbers to a graphical representation

The output files should also have some metadata about the machine they were run on (Node version, OS, CPU, memory, etc?)

We can hook you up with a new repository (say elm-in-elm/benchmarks) when needed.

This means:

• add List (List Expr) constructor Frontend.Expr type... solve any compiler errors that arise as a result (emitExpr etc)
• add tests that show all the various ways lists can be written work. For example:
  • [], [ ]
  • [1], [ 1 ]
  • [1,2], [ 1, 2 ]
  • I can't think of any more. Let's not deal with newlines right now as that will be more tricky and done in another issue.
• partially implement type inference - focus on the items: all items inside list have to have the same type. Should be enough to eg. for list [A,B,C] do equals typeA typeB, equals typeA typeC. Don't have to do all the combinations. This will leave us to do the type of the actual list itself in a later issue after we implement type parameters.
• add emit tests too:
  • Elm's [ 1, 2, 3 ] ➡️ JavaScript's [1, 2, 3]
  • [] ➡️ []
• implement emitting to pass the emit tests above
• update the "what's done" table in README for lists: parser tests, desugaring (none), type inference (only partially = ⚠️), emit and emit tests... but not parsers and optimizations.

If you get stuck on anything, ask here or on Discord! We'll help you 🙂

Out of scope ❌ ❌ ❌

• tests for newlines support in lists
• parser for lists
• optimizations (they'll become available with the operators but not sooner I think ... at least I can't think of any)
• type inference of list itself
• (::) operator
• (++) operator

This means:

• add tests to "literal string" section of ParserTest.elm about
  • multiline string ("""abc""")
  • how do escapes work in normal vs multiline strings ("{\"foo\":1}" vs """{"foo":1}""")
  • that multiline strings actually parse newlines!
• update the "what's done" table in README - parser tests for strings

Some of the tests should fail - not implemented yet.
Fixing the parser is not needed in this ticket (can be in a separate one)

See notes/AssignIdsAbstraction.elm for some notes on a possible solution.

Essentially this function is giving us trouble - in case of recursive calls it nests Result.andThens and it doesn't look very nice. That's a consequence of doing the monadic style with no do notation in the language (which would essentially make it not indent further and further to the right).

notes/AssignIdsAbstraction.elm is an attempt to imagine a better API than Result.andThen. I'm not yet sure if something like this is possible, but we can try! 💪

For some more context, the underlying problem is turning stuff like this (ignore the nonsense AST)

If 
  { test = Plus (Literal (Int 1)) (Literal (Int 2))
  , then_ = Unit 
  , else_ = Literal (Bool True)
  }

into

( If 
    { test = 
        ( Plus
            ( Literal (Int 1)
            , Var 0
            )
            ( Literal (Int 2)
            , Var 1
            )
        , Var 2
        )
    , then_ = ( Unit, Var 3 )
    , else_ = ( Literal (Bool True), Var 4 )
    }
, Var 5
)

ie. giving every subexpression an unique ID.

This module here parses pretty much all types already. Why not re-use the code?

https://github.com/dkodaj/decgen

Should be similar to how Plus is done. Keep it a separate case in the Frontend.Expr - later we can try to think of a way to abstract all binary operators into something dynamic, read from source instead of baked into the compiler.

• add parser tests
• add a parser
• add optimization tests
  • if both of the items are literal lists (not a variable for example), combine them into one list:
  • [1, 2] ++ [3, 4] should become [1, 2, 3, 4]
• add optimization
• add emit tests -- TODO rethink this similar to #29
  • [1] ++ [2] should become [1].concat([2])
  • stuff ++ [1] should become stuff.concat([1])
  • [1] ++ stuff should become [1].concat(stuff)
• add emit

Not in scope ❌ ❌ ❌

• appendable typeclass
• (++) for strings

Right now type variables get emitted this way:

• Type.Var 123 -> "t123"

It would be great to print them like a and b, like we're used to from the official Elm compiler.

Gotchas

Note that toString for one Type is not enough. In the error messages you sometimes compare two types together, so something like toStringHelper : Dict Int String -> Type -> (String, Dict Int String) might be needed to allow you to thread names from one type into the other.

Eg. if the first Type is Function (Var 1) (Function (Var 2) Int) and the second one is Function (Var 2) Bool, they should be consistent with each other: a -> b -> Int and b -> Bool (not a -> Bool, which would probably happen if you'd just call toString without context and without threading the Dict through)

Hey. Cool project!

I wanted to play with it but wanted to know if you could add emit test. It would be great if it just feeds the elm code string and asserted that result matched expected.

I currently don't have a clear idea on how to do this. I'd start with this:

• add the number type to Type
• make integers implicitly numbers instead of straight-up Ints
• create some additional typing rule about number and Int/Float behaviour (maybe in the unification phase?)
  • Ints can be used in place of numbers
  • Floats can be used in place of numbers

This means:

• find all the ways characters can be written in Elm (\u{...}? \x{...}? straight-up emoji in the source code? something else?)
• add those as tests to the "literal char" section of ParserTest.elm so that the tests exercise all the possibilities and truthfully tell us what's done and what's not
• update the "what's done" table in README - parser tests for characters

Implement parser for tuples and 3-tuples so that the tests created in #34 are green! 💚

I created a fresh Nix installation, and attempted to build the project, getting an elm version mismatch error. Am I missing something?

[nix-shell:~/dev/compiler]$ make
rm -rf build/elm.js elm-stuff
cd cli && npx elm make Main.elm --output ../build/elm.js
-- ELM VERSION MISMATCH ----------------------------------------------- elm.json

Your elm.json says this application needs a different version of Elm.

It requires 0.19.1, but you are using 0.19.0 right now.

make: *** [Makefile:26: build] Error 1

[nix-shell:~/dev/compiler]$

() should be a valid Elm syntax. What we emit it as is probably not that important right now (we will find out later!) - let's emit as {"type": "unit"}

That means we need to implement:

• parser tests
• emit tests (if done after #7 )
• new AST.Frontend.Expr case
• parser
• new type (treat it similarly to literals in type inference)
• JS emit case

No optimizations needed (or at least I can't think of any), no desugaring needed either.

The compiler errors will probably guide you 😅 Ask here or on Discord if anything is unclear!

Jakt is an imperative language (from the SerenityOS project) that compiles to C++ (and thus to native binaries), with a few charaacteristics that make it nice to use from Elm backend perspective:

• managed memory (no malloc and free needed)
• has ADTs

Here's a translation example of an ADT:

type Foo a
  = Bar
  | Baz a
  | Quux
      { x : String
      , y : Int
      }
  | Quz Int a

⬇️

enum Foo<A> {
  Bar
  Baz(A)
  Quux (
    x: String
    y: i64
  )
  Quz(a1: i64, a2: A)
}

I am writing this up as an issue just because it seemed like a good place to write up something kind of long form. It's sort of an enhancement request, but I don't even want it to be as strongly worded as "request"; it's more just a data point.

So meta-elm is my project, and it's an expression evaluator for an AST that is similar in nature to elm-in-elm's AST. There's a pretty close-to-1:1 mapping between the two.

I have another project called mini-elm that uses elm-in-elm to parser Elm expressions and then hands off to meta-elm to parse them.

Right now meta-elm is strong in these areas:

• basic support for ints, floats, tuples
• full mapping of List.elm
• support for pipelines (foo |> bar |> baz)

It's also missing lots of very fundamental stuff like strings, records, custom types, etc. Also, it never intends to do things like parsing or deep type checking. For that it wants to play nice with elm-in-elm!

I know that elm-in-elm's evolution is gonna be driven 99.99% of the time by its own concerns, and not meta-elm. And of course that's reasonable. But to the extent I can influence things, here are my would-be-nice things:

• pipe operator (|>): I would really like this! It just makes it a lot easier to write sample code.
• basic arithmetic operators (+/-/*/div) - these would really make meta-elm feel "complete" for a subset of problems (manipulating lists of ints)
• Order support (EQ/LT/GE)

For meta-elm the only thing I care about at the moment is front-end parsing. So if I were king of the world, I'd say just parse |> and don't worry about de-sugaring it. (It might be good to have a dev process for that kinda stuff, anyway--be able to write parsers and have downstream stages just gracefully deal with "unknown" things--that probably already sorta happens?).

I am happy to elaborate on any of this in Discord; I just thought it's good to write it up here to avoid repeating myself.

For what should be in them: don't check that it "does nothing". Check the interesting stuff that happens in the desugarExpr function. Eg.:

• Var: finds the module according to the surrounding context (imports and other top level definitions)
• Lambda: gets curried, ie. \a b -> c becomes \a -> \b -> c
• List: keeps the original order

With Pratt parsing, a common bug is that you can successfully parse f a b c and x < 5, but you can't parse f a b c < 5. We should try adding tests that put somewhat complicated expressions on either sides of the operators. I quickly skimmed the tests, and I don't believe the tests do much coverage of edge cases.

If you add tests and they pass, then great, leave them in, and we'll have more robust coverage.

If tests fail, either try to make a quick fix (if possible) or open an issue and/or discuss on Discord.

Would a PR adding elm format tooling be accepted?

I guess with the current tooling that should mean:

• user can run nix-shell inside the project and get a shell with elm, elm-format, elm-test, node (v10+) and make ready to use. (Bonus points for elm-analyse)

If you know more about Nix (I know awfully little about it) and think it should / can do more, I'm all ears!

We have a whole lot of types like:

• Elm.Data.Exposing.Exposing
• Elm.Data.ModuleName.ModuleName

where there is a module fundamentally there to define a type and some helper functions. My idea would be to rename the type defined by this module to T. Therefore we would have:

• Elm.Data.Exposing.T
• Elm.Data.ModuleName.T

and we would not have to write import Elm.Data.Exposing exposing (Exposing) but could instead use Elm.Data.Exposing.T directly. Definitely, cons to this idea but I thought worth throwing it out.

We have multiple elm.json files and the versions of the dependencies are not the same.

Find a solution that complains in CI when they get misaligned.

(At work we have a Haskell script that checks the various versions and tells you the discrepancies; I've talked to @jhrcek about open-sourcing it 🙂 I'll update this issue if/when that happens.)

This means:

• add Tuple (Expr, Expr) and Triple (Expr, Expr, Expr) constructors to Frontend.Expr type... solve any compiler errors that arise as a result (emitExpr etc)
• add tests that show all the various ways these can be written in. Don't think about newlines for now (those will be dealt with later), but write tests to see tuples work with and without spaces in between. Eg.:
  • (1,2), ( 1, 2 )
  • (1,2,3), ( 1, 2, 3 )
• implement type inference - it should be pretty straighforward:
  • if items have types A and B, the tuple has type (A, B). (Yeah, you'll have to create new Type constructors to account for this)
  • similarly for 3-tuples ("triples" - I don't like that name though 🙁 ) - items with types A, B, C ➡️ 3-tuple has type (A, B, C)
• add emit tests too:
  • Elm's (1, 2) ➡️ JavaScript's [1, 2], similarly with the 3-tuples
• implement emitting (emitExpr) to pass the emit tests above
• update the "what's done" table in README for tuples and 3-tuples: parser tests, type inference, emit and emit tests... but not parsers.

If you get stuck on anything, ask here or on Discord! We'll help you 🙂

Out of scope ❌ ❌ ❌

• tests for newlines support in tuples and 3-tuples
• parser for tuples and 3-tuples

Bonus points 🏆

• think of a better name for the 3-tuple constructor than Triple

Running make for the first time in the root directory of this repo:

Compiled in DEV mode. Follow the advice at https://elm-lang.org/0.19.0/optimize for better performance and smaller assets.
---------------------------
-- STARTING THE COMPILER --
---------------------------
(node:4519) ExperimentalWarning: The fs.promises API is experimental
Main.main: Let { bindings = [{ body = Literal (Int 1), name = VarName "x" }], body = Var { name = VarName "x", qualifier = Nothing } }


---------------------------
-- COMPILER ERROR ---------
---------------------------
Can't find the variable `x` in the module `Main`. Have you imported it?

I'm using node v10.15.3 and elm 0.19.0.

Standard elm uses a syntax borrowed from Haskell to define new operators.

I propose that elm-in-elm should hard code operators into the compiler. The main advantage of this is approach is that we avoid having to define a kernel function for each arithmetic operator: instead the compiler can generate code directly*.

Only standard packages can define operators and they do so very rarely so I think it would be feasible to handle all elm operators in the compiler.

*: The standard compiler also generates code directly as an optimsation.

Given

module Meh exposing (..)

meh = \a b -> 3 + a

someFunction = meh 5

The correct inferred type for someFunction should be a -> Int but instead is a.

ie, the parsed AST declarations are:

    [ { body =
            Value
                ( Lambda
                    { argument = "a"
                    , body = ( Lambda { argument = "b", body = ( Plus ( Int 3, Int ) ( Argument "a", Int ), Int ) }, Function (Var 6) Int )
                    }
                , Function Int (Function (Var 6) Int)
                )
      , module_ = "Meh"
      , name = "meh"
      }
    , { body =
            Value
                ( Call
                    { argument =
                        ( Int 5
                        , Int
                        )
                    , fn = ( Var { module_ = "Meh", name = "meh" }, Function Int (Var 2) )
                    }
                , Var 2
                )
      , module_ = "Meh"
      , name = "someFunction"
      }
    ]