elm-in-elm

Elm compiler written in Elm!

Goals

1. :book: compiler as Elm library: so that we can publish it on https://package.elm-lang.org/ and unlock new kinds of Elm applications (like Elm-evaluating Slack bots, Klipse integration, stepping debuggers, ...)!
2. :children_crossing: learning friendly: so that folks can learn how to write a compiler in Elm (similarly to Richard Feldman's elm-spa-example). This means

   elm-in-elm

   is focused on readability, beauty, approachability, simplicity, great docs and great tests first, and only then completeness and speed.
3. :bulb: exploration ready: the first two points enable folks to hack on the compiler (as it's written in Elm, which they know, and the code is new-people-friendly) and answer some questions! (For example, what's the best order of optimizations? How would emitting to JavaScript have to look like to make it extra amenable to Google Closure Compiler's advanced optimizations?)
4. :wrench: extensible: again, the first two (three?) points make it easy and invite extending the compiler in various ways, eg. a native binary target, different type inference algorithm, new optimizations,

   where

   syntax, etc.

In short,

elm-in-elm

:tv: For more context and information, you can watch Martin Janiczek's talk from Elm Europe 2019 which served as an unveiling of

elm-in-elm

Non-goals :negativesquaredcross_mark:

1. To dethrone or replace the official Elm compiler written in Haskell.

This is :negativesquaredcrossmark::negativesquaredcrossmark::negativesquaredcrossmark: NOT THE REASON and NOT THE GOAL :negativesquaredcrossmark::negativesquaredcrossmark::negativesquaredcrossmark: of

elm-in-elm

elm-in-elm

What?

elm-in-elm

• a compiler implementation
• a library
• a CLI tool
• and a test suite.

It is written in Elm, and compiles Elm to JavaScript, but lays the foundation to be able to compile to different targets in the future.

:warning: Warning!

elm-in-elm

is definitely not ready for usage yet, even though its library is published already. The main blocker is the parsers for expressions not being all implemented yet. See the

parse

column in the table below.

Contributing

Please yes! :heart: Feel free to look around the help wanted or good first issue issues, have a look around the codebase for some general nitpicks or refactorings, or hit us up on Discord!

Roadmap

| | parser tests | optimize tests | emit tests | parse | desugar | infer types | optimize | emit | | ----------------- | -------------------- | -------------------- | -------------------- | -------------------- | ------------------ | -------------------- | -------------------- | -------------------- | | integers | :heavycheckmark: | :warning: [2] | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :warning: [2] | :heavycheckmark: | | floats | :heavycheckmark: | :x: [5] | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :x: [5] | :heavycheckmark: | | characters | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | strings | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | booleans | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | variables | :warning: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | lists | :heavycheckmark: | :x: [6] | :warning: [1] | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :x: [6] | :warning: [1] | | binary operators | :warning: [3] | :heavycheckmark: | :heavycheckmark: | :warning: [3] | :heavycheckmark: | :x: | :warning: | :warning: | | lambdas | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :warning: | :heavycheckmark: | | function calls | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | if...then...else | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | let..in | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :warning: | :heavycheckmark: | :warning: | | case...of | :warning: [4] | :x: | :x: | :warning: [4] | :x: | :x: | :x: | :x: | | records | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | record accessors | :x: | :x: | :x: | :x: | :x: | :x: | :x: | :x: | | record updates | :x: | :x: | :x: | :x: | :x: | :x: | :x: | :x: | | unit type | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | tuples, 3-tuples | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | type annotations | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | | type aliases | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :heavycheckmark: | :warning: [7] | :heavycheckmark: | :heavycheckmark: | | custom types | :heavycheckmark: | :x: | :x: | :heavycheckmark: | :x: | :x: | :x: | :x: | | custom operators | :x: | :x: | :x: | :x: | :x: | :x: | :x: | :x: | | shaders (?) | :x: | :x: | :x: | :x: | :x: | :x: | :x: | :x: |

1. Lists'

   emit

   will have to change a bit: conversion from target platform lists to Elm "custom type" lists is now missing; tracked in #29
2. To be optimized with multiplication, subtraction, division, modulo, exponentiation... maybe more?
3. Multi-line binops (probably) don't work correctly now
4. Custom type patterns aren't supported yet
5. To be optimized the same way Ints are
6. Not implemented; partially tracked in #29
7. We're currently doing nothing about the type parameters in the type aliases.

FAQ

1. • Q: Why not use

     stil4m/elm-syntax

     for the parsers?
   • A: We'd love to use

     elm-syntax

     - it would save us so much trouble. But that would not be ideal in some regards:
     • less flexibility wrt. how our types look
     • would be less educational (compare with the learning resource goal) - would skip parsers entirely
     • even if we didn't use it as a library but copypasted the parsers code, those are written in the 0.18

       elm-community/parser-combinators

       style - we'd like, again because of the learning resource goal, to have the parsers written in idiomatic

       elm/parser

       style

   But yeah, there's definitely a little bit of NIH syndrome happening :wink:

Prerequisites

The easy way: if you have Nix installed, run

$ nix-shell

Alternatively, this is what the project needs.

• make

  for the Makefile
• NodeJS 10+ for the CLI tool

• elm

  ,

  elm-test

  and

  elm-format

Running the compiler

$ make

Essentially compiles the compiler (using the official Elm compiler :wink: ) to a

build/elm.js

node

Very handy for running the whole compiler pipeline on an example project living in

example-project/

example-project/src/Main.elm

Debug.log

make

So absolutely feel free to go bonkers on that

example-project/

Running the tests

$ make test

Runs

elm-test

Formatting code

$ make format 

Runs elm-format. Make sure to format code before submitting a pull request!

Small TODOs

This is a brain-dump of some low-level stuff. (High-level stuff should be in the roadmap.) My apologies if it's hard to make sense of this! ~janiczek

Project management

• [ ] @janiczek: Share your Firefox bookmarks relevant to

  elm-in-elm

  (ie. talks about Haskell hierarchical optimizations etc.)
• [ ] Add tests for stages other than parsing and emit into the matrix above

General

• [ ] Compare our

  Main.compile

  with official compiler's

  Compile.compile

  - is that a better API?
• [ ] Types module: remove, refactor into "module per datastructure" style?
• [ ] Deal with kernel modules
• [ ] Deal with ports
• [ ] Deal with effect modules
• [ ] Deal with typeclasses (number, comparable, ...)
• [ ] Deal with pattern matching
• [ ] Deal with custom binary operators

Type inference

• [ ] Try the Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism and see where that leads
• [ ] Let polymorphism :no_mouth::

  Stage.InferTypes.generateEquations

  , the

  Typed.Let

  case. This paper might have a parable written well enough that we might actually understand type schemes from this. Otherwise, "Write you a Haskell" for the rescue! There is also the Damas and Milner paper proving the inferred type is the most general one.
• [ ] Extensible records (link):

  D. Leijen, “Extensible records with scoped labels,” in Revised Selected Papersfrom the Sixth Symposium on Trends in Functional Programming, TFP 2005,Tallinn, Estonia, 23-24 September 2005.(M. C. J. D. van Eekelen, ed.), vol. 6 of Trends in Functional Programming, pp. 179–194, Intellect, 2005.

• [ ] Typecheck across modules, not each module separately. This will probably be clearer after we try and implement the library.
• [ ] Annotate type errors with position in source code (for better error messages)
• [ ] Try to find a better name for "occurs check" and make the error message easier to understand
• [ ] Document the typechecking stages better (ie. at all)
• [ ] Rename types to be able to show nice type variables (ie. the classic

  a

  instead of

  type #0

  or something).

  Stage.InferTypes.getType

Optimizations

• [ ] Experiment with Prepack-like optimization: compute everything you can in the compile-time instead of runtime
• [ ] Implement constant propagation?
• [ ] Implement inlining (maybe it will need some heuristic? Look at how other langs do it?)
• [ ] Implement

  ( and 
  (|>)
   fusion (eg. transform both 
  x |> f
   and 
  f  into 
  f x
  )

PrepareForBackend

• [ ] Check that the

  Lambda

  case of

  Stage.PrepareForBackend.findDependencies

  works correctly

Emit

• [ ] Native binary target (x86_64), possibly through LLVM?
• [ ] WebAssembly?
• [ ] Would this simplify / be a good fit for Elchemy (Elm -> Elixir)?
• [ ] Would this simplify / be a good fit for philip2 (Elm -> OCaml)?
• [ ] Would it be worth concatenating single-arg lambdas back to multi-arg ones (so that we emit eg.

  (a,b) => a+b

  instead of

  (a) => (b) => a+b

  )?
• [ ] How to emit

  let

  ? How does official compiler do it? Seems the dependency graph will have to be computed for its binidng too, similarly to how the path to

  main

  gets computed for the program itself.

  Stage.Emit.emitExpr

  , the

  Let

  case.
• [ ] Do we need to mangle variable names? (ie. do what the official compiler does) Maybe not! Check
• [ ] What's good JS style for Google Closure Compiler's advanced optimizations?
• [ ] What's good JS style for UglifyJS?
• [ ] What's good JS style for modern JS engines?

Tests

• [ ] Test

  Common.unalias

• [ ] Test

  Stage.Desugar.findModuleOfVar

Contributors

<a href="https://github.com/Janiczek">Martin Janiczek</a> </td> <td align="center"> <img width="150" height="150" src="https://avatars2.githubusercontent.com/u/5399281"> <a href="https://github.com/rlefevre">Rémi Lefèvre</a> </td> <td align="center"> <img width="150" height="150" src="https://avatars0.githubusercontent.com/u/16308754"> <a href="https://github.com/harrysarson">Harry Sarson</a> </td> <td align="center"> <img width="150" height="150" src="https://avatars0.githubusercontent.com/u/197573"> <a href="https://github.com/Warry">Maxime Dantec</a> </td> <td align="center"> <img width="150" height="150" src="https://avatars0.githubusercontent.com/u/16829510"> <a href="https://github.com/aaronjanse">Aaron Janse</a> </td> </tr> <tr> <td align="center"> <img width="150" height="150" src="https://avatars1.githubusercontent.com/u/3983879"> <a href="https://github.com/halfzebra">Eduard Kyvenko</a> </td> <td align="center"> <img width="150" height="150" src="https://avatars3.githubusercontent.com/u/6839698"> <a href="https://github.com/sebsheep">Sébastien Besnier</a> </td> <td align="center"> <img width="150" height="150" src="https://avatars3.githubusercontent.com/u/12603666"> <a href="https://github.com/sgdan">sgdan</a> </td> <td align="center"> <img width="150" height="150" src="https://avatars0.githubusercontent.com/u/15112020"> <a href="https://github.com/pablohirafuji">Pablo Hirafuji</a> </td> <td align="center"> <img width="150" height="150" src="https://raw.github.com/elm-in-elm/compiler/master/assets/user-placeholder.png"> You? </td> </tr>

License

BSD-3-Clause

Attribution

• "person using laptop" icon created by alvaro_cabrera