DEV Community: Robin Heggelund Hansen

Play: A new programming language that targets Web Assembly, based on Forth

Robin Heggelund Hansen — Mon, 23 Nov 2020 11:15:58 +0000

Today marks the first release of Play, a new programming language inspired by Forth.

Play might look a lot like Forth, but improves on the language in several ways. Play includes a strong static type system like the ones found in Elm and Haskell. All data structures are immutable, and side effects are tightly controlled, which leads to code that is easy to reason about.

Code written in Play is compiled to web assembly, which means it can run pretty much everywhere, even in browsers.

The goal of today's release is not to present a finished product, but rather give people an idea of what writing code in Play would be like.

To learn more, you can take a look at the website and toy with some examples at the playground.

Getting started with Elm Warrior

Robin Heggelund Hansen — Mon, 14 Sep 2020 10:40:15 +0000

You wake up in a dungeon. You're alone, freezing and nearly starved to death. In the darkness ahead, you can hear footsteps and the sharpening of blades. The only weapon at your disposal is Elm, the programming language. Will you find your way out alive?

Elm-warrior is a programming game created to answer the question: Ok, now I know basic Elm syntax, what do I do next?

Over the course of several levels of ascending difficulty, you'll program the intelligence of At, a slow but strong-willed warrior, trying to get him out of the dungeon alive.

When you've successfully escaped the dungeon, you can compare your solution with others in a free-for-all deathmatch, or continue challenging yourself by creating your own maps.

Are you ready?

Getting started

You're going to need to have git and node installed.

After that, you can clone the elm-warrior-starter repo. The starter repo contains the minimal amount of boilerplate required to start playing, while the elm-warrior repo contains the actual framework and documentation you'll use.

To clone the starter-repo, you can run the following command in your command line.

git clone https://github.com/robinheghan/elm-warrior-starter

When done, you're going to need to download elm and parcel for your code to compile and run. We can do this using node's package manager, npm, as those dependencies are already declared in the repo:

cd elm-warrior-start
npm ci

You should now have everything setup, ready to begin coding.

Solving the first level

As a first step, we're going to compile the code and spin up a web server to see how our code affects the elm warrior:

npm start

This should start a web server at http://localhost:1234, so enter that address in your web browser. You should see the following:

The goal is to have the warrior reach the other side of the room. Since we've yet to write a single line of code, the warrior just does nothing. Let's fix that!

Using your prefered IDE or text editor, open src/elm/Player.elm. This file should contain the following code:

module Player exposing (takeTurn)

import Warrior exposing (Warrior)
import Warrior.History exposing (History)
import Warrior.Map exposing (Map)


takeTurn : Warrior -> Map -> History -> Warrior.Action
takeTurn warrior map history =
    Warrior.Wait

Implementing the intelligence of an elm warrior is as simple as implementing a function. The function is called once every turn, and is required to return an action that specifies what the warrior should do next. As you can see, this function simply returns the Wait action, and so our warrior will always stand still.

To get past the first level, we need to return an action that makes the warrior move to the right. To figure out which actions our warrior can take, we need to consult the documentation. Here we can see that there is a Move action which takes a Direction.

If we change the function to return a move action, like so:

module Player exposing (takeTurn)

import Warrior exposing (Warrior)
import Warrior.History exposing (History)
import Warrior.Map exposing (Map)
import Warrior.Direction as Direction


takeTurn : Warrior -> Map -> History -> Warrior.Action
takeTurn warrior map history =
    Warrior.Move Direction.Right

Our warrior should now move right every single turn. Just save the file and refresh the browser, you do not need to run npm start again. The warrior should now reach the exit point quite easily.

Once the warrior reaches the exit point, it will transition to a new level of greater difficulty, requiring more intelligence in your turn function. Can you get through all the levels and escape the dungeon?

Solving the next levels

You may have noticed that the turn function takes three arguments.

The first argument contains information about the warrior itself. Its current health, current position, current items in the inventory, and so forth.

The second argument contains information about what the warrior can see. You can use this to look for the exit, or possible obstacles and dangers in its path.

The final argument contains information about all previous actions the warrior has taken, and the state of the warrior and map at those times. You can use this information to figure out if the warrior has been somewhere before, or remember where the warrior has seen something.

You'll need to make use of all these arguments to help the warrior escape the dungeon, and the operations you can perform on them is listed in the documentation, so make sure to read this carefully.

Debugging

You might have noticed a little Elm logo at the bottom right of the browser window. Clicking this opens up the time-travelling Elm debugger.

The debugger allows you to step backwards in time to see what the state of the program was at a particular turn, which might make it easier to figure out why your function returned the action it did.

Speeding things up, or slowing things down

After a couple of runs, you might wish that the warrior moved a little faster, or a little slower. You can change this by opening src/elm/Main.elm.

module Main exposing (main)

import Player
import Warrior.Map.Progression as Progression
import Warrior.Maps as Maps
import Warrior.Program as Warrior


main : Program () Warrior.Model Warrior.Msg
main =
    Warrior.program
        { maps = Maps.all
        , players = [ ( "Player", Player.takeTurn ) ]
        , msPerTurn = 500
        , progressionFunction = Progression.reachExitPoint
        }

You can change the msPerTurn setting to whatever value you'd like. Setting it to 100 will speed things up significantly. Setting it to 0 will speed it up even more, but it might be difficult to see the individual actions the warrior takes. Slowing it down is just a matter of increasing the value.

Focusing on a single level

You might have seen that there is a maps setting in Main.elm as well.

At some point, you might not wish to run through every single map when you know that the warrior struggles with one in particular. You can see a list of all available maps in the documentation. If you make a list containing just the map you'd wish to run, and pass that to the maps setting, you can avoid spending time in maps you already know works well.

For instance, if you're mostly focusing on the second to last level, you can avoid having the warrior run through all the others by changing the Main.elm file to this:

module Main exposing (main)

import Player
import Warrior.Map.Progression as Progression
import Warrior.Maps as Maps
import Warrior.Program as Warrior


main : Program () Warrior.Model Warrior.Msg
main =
    Warrior.program
        { maps = [ Maps.straightGuardPickupPotion ]
        , players = [ ( "Player", Player.takeTurn ) ]
        , msPerTurn = 500
        , progressionFunction = Progression.reachExitPoint
        }

Further challenges

When you've successfully escaped the dungeon, you might wish you had more challenges. Elm warrior allows for both creating your own maps (and sharing with others) as well as a free-for-all deathmatch.

To create your own maps you can draw some inspiration from looking at the code of the maps you've just tried out as well as reading the map builder documentation.

For playing deathmatches, there is a separate multiplayer starter repo you can clone to get started. For extra fun, you can challenge your friends and see who has programmed the best warrior. May the best Elm programmer, win!

Become an Elm warrior

Robin Heggelund Hansen — Sat, 13 Jun 2020 20:53:23 +0000

In the last two years I've been given several opportunities to teach people Elm through talks and workshops. What I've come to learn is that no matter how well your talks and presentations are, people need to write Elm on their own to actually learn anything of it.

This might not be surprising to any of you, but it does present one a huge challenge: time.

You might not have time to let people write enough Elm to get comfortable. You can almost be certain that half the people that attend your workshop is going to have problems getting everything setup or, if they were kind enough to come prepared, experienced problems setting everything up before they arrived.

Then you'll find yourself answering many more questions than you'd originally hoped for, only to discover that you're not answering nearly enough of them.

Before you know it, it's the end of the day and you haven't even gotten to the point were the actual benefits of Elm begin to make themselves apparent.

If you've been given several days to teach people Elm this won't be a problem, but you won't always have that luxury.

How about a game?

For the past couple of months I've worked on a game that I hope can make it easier to teach people Elm. Why a game?

I want people to have a fun first meeting with Elm.
Any workshop assignment that feels like work won't motivate people to spend any time in Elm after the workshop ends. When our biggest adversary is time, motivating people to make time is key. It also helps if they remain motivated throughout the day, learning things is hard.
A game is complex enough that people can discover some of the benefits of Elm on their own, while simple enough to not be overwhelming, especially if we keep commands, subscriptions and html out of it.
The few people in the workshop who already know a little Elm will, hopefully, not get bored.

Announcing Elm Warrior

The game is called Elm Warrior and is in large part inspired by warrior-js.

The goal of the game is to implement the intelligence of a warrior, named at, as it navigates mazes and battles dangerous opponents.

As a player you're implementing a single pure function, which is called once every round to determine the action of your warrior. You use whatever you would use to program in Elm proper, and you don't need to learn the elm architecture or the html library to do anything useful. The API is small and simple to learn.

There are 12 builtin maps to keep you busy. Should you get bored, there are API's for making your own maps and customising the rules for when a game is won or lost. It is also possible to define a multiplayer game, where several players create their own warriors and fight to the virtual death. I recently hosted a deathmatch with some colleagues at work and it was a blast!

Elm Warrior is not enough to learn Elm on its own, but I'm hoping it will serve as a fun and simple enough tool to get people comfortable with Elm's syntax og basic constructs.

Even if that does not prove to be the case, it's still a lot of fun to play.

To get started, click this link.

Improving Elm's compiler output

Robin Heggelund Hansen — Sat, 25 May 2019 14:50:43 +0000

Elm is fast.

This is not because of any innovation in the compiler. In fact, the Elm compiler hardly does any optimization at all.

Elm is fast because it compiles to Javascript, which dedicated and talented engineers from all over the globe have been optimizing for more than a decade.

But here's a question: does the Elm compiler output Javascript which makes it easy for browsers to optimize it and, if not, is there any performance to gain by changing how the compiler outputs Javascript?

Let's have a look.

Hidden classes

Javascript is a dynamic language. Javascript allows objects to change in shape at any time. Variables and data structures can contain different values of different types at any time. In practice, however, most programs are fairly static and browsers try to take advantage of this.

In Chrome, every object literal and class is seen as a shape. If the shape of an object or class changes, like a property being dynamicly added or removed, Chrome will see the resultant new shape and try to convert between them. In some cases, Chrome will just treat objects as hashmaps (kinda like Elm's Dict) if it has trouble figuring out the precise shape of something. We call these shapes for hidden classes.

We get the best performance when our Javascript code doesn't seem to deal with many different shapes at a time. Fortunately, Elm is a static language so this should be pretty common. There is, however, a case where Elm does produce different shapes that can pass as the same type. Let's look at an example:

type Maybe a
  = Just a
  | Nothing

This is how Elm's Maybe is defined. It is compiled into the following Javascript (using --optimized):

var elm$core$Maybe$Just = function (a) {
    return {$: 0, a: a};
};

var elm$core$Maybe$Nothing = {$: 1};

As you can see, the Javascript object literal for Just and Nothing has different shapes. As a result, every Javascript code which deals with Maybe has to be able to deal with two different shapes. But is that costly?

To measure the effect I've done two things:

1) Make a benchmark which can hopefully pick up the performance difference, then make two versions where one is handcoded to avoid the overhead.
2) Look at the assembly code which Node outputs (Node and Chrome uses the same JS engine, V8).

You can find the code for this experiment at github.

I've focused on Elm' built-in List type, as it's used in pretty much every program. A performance improvement here would be a big benefit to everyone who uses Elm.

We'll be focusing on the following benchmark:

benchmark "int +" <|
  \_ -> foldl (+) 0 intList

Simply a left fold over all the elements, adding them together. A change in performance here will tell us how quickly we can iterate through a List, the theory being that removing any overhead dealing with multiple hidden classes should increase performance.

We compile the benchmark. Looking through the compiled JS output, we can find this piece of code:

var _List_Nil = { $: 0 };
function _List_Cons(hd, tl) { return { $: 1, a: hd, b: tl }; }

The empty List looks different from a List element (if you're wondering how Lists work, I explained it decently well at Elm Europe 2017).

We copy the JS file, and make the following modificaiton:

var _List_Nil = { $: 0, a: null, b: null };
function _List_Cons(hd, tl) { return { $: 1, a: hd, b: tl }; }

A List should no longer be polymorphic (of many shapes).

The result:

Firefox, before modification: 75,843 ops/sec
Firefox, after modification: 84,549 ops/sec
Safari, before modification: 248,531 ops/sec
Safari, after modification: 248,530 ops/sec
Chrome, before modification: 294,434 ops/sec
Chrome, after modification: 302,569 ops/sec

So, no difference in Safari, however both Chrome and Firefox see a pretty decent improvement: ~11% in Firefox, ~4% in Chrome. Keep in mind that this is something that can be implemented in the compiler, no Elm code would have to change, it's a performance improvement for no effort on the part of application developers.

We can also look at the code that V8 generates by running the following script:

node --print-opt-code --code-comments index.js > jit_log

By reading the jit_log for the benchmark run without modifications, we can see:

-------- Optimized code ---
optimization_id = 1
source_position = 48049
kind = OPTIMIZED_FUNCTION
name = $List$foldl
stack_slots = 10
compiler = turbofan
address = 0x28bd2bd6e9a1
Body (size = 2292)
Instructions (size = 2012)
<Assembly code>

While for the modified code we see

-------- Optimized code ---
optimization_id = 0
source_position = 48067
kind = OPTIMIZED_FUNCTION
name = $List$foldl
stack_slots = 10
compiler = turbofan
address = 0x2081135eec01
Body (size = 1848)
Instructions (size = 1600)
<Assembly code>

As expected, it generated less code when the code doesn't have to deal with polymorphism.

There is, however, something in both of this logs which give me pause:

Inlined functions (count = 1)
 0x3f2705632551 <SharedFunctionInfo A2>

This section of the log lists how many functions have been inlined. In this case, only a function which evaluates the passed in function has been inlined (I'll explain what this mean in a second). This isn't actually that surprising. foldl only contains a single function call, which is done once per loop. This function is usually never the same either, so it makes sense that it wasn't inlined. However, if you look at all the other functions that have been optimized, the only functions which are inlined are either functions which take a single argument (also called arity-1 functions) or functions called A2, A3, A4 etc.

What gives?

Inlining

Inlining function calls (replacing the function call with the implementation of the function) is one of the most important optimizations a compiler can make. This is not necessarily because function calls are all that expensive, but because it allows the compiler to better understand what the code does and perform optimizations based on that.

Let's look at our benchmark again:

benchmark "int +" <|
  \_ -> foldl (+) 0 intList

Without inlining, this would call the foldl function, which is a loop calling a function for every element in the list. Since foldl can accept any function, it would store the intermediary number value as a reference (even though it could be stored as a number on the stack), performing a lookup in memory each time the function is called. If we weren't storing ints as intermediary values, as it would be the case if we were folding over other things, the Javscript optimizer would likely treat all values as a generic hashmap inside of foldl.

With inlining, however, this function is likely to be compiled down to a single javascript loop, without any function calls at all, and with specialized code for the types actually used in the loop. This is like getting the benefits of a monomorphising compiler, without actually having a monomorphishing compiler.

But why aren't many functions being inlined, and what are all these A2 things?

Currying

Elm has this concept of currying. Given the following function:

add : Int -> Int -> Int
add a b =
  a + b

You can create a new function like this:

add2 : Int -> Int
add2 =
  add 2

So if you call a function with enough arguments, it will execute. If you call a function without all the arguments it requires, it returns a new function which accepts the missing arguments.

This is how the above add function is compiled to JS:

function F(arity, fun, wrapper) {
  wrapper.a = arity;
  wrapper.f = fun;
  return wrapper;
}

function F2(fun) {
  return F(2, fun, function(a) { return function(b) { return fun(a,b); }; })

var author$project$Main$add = F2(function(a, b) {
  return a + b;
});

Our add function, as well as every other Elm function, is wrapped in an object which contains the original function, the arity that function expects, and a curried function. Calling the function has to be done with A2, which is implemented like this:

function A2(fun, a, b) {
  return fun.a === 2 ? fun.f(a, b) : fun(a)(b);
}

So A2 takes a F2 object, and calls the function directly if the provided function actually takes two arguments, or does a curried call if not.

From the perspective of a javascript engine, this has a big problem: unless we do whole program analysis (which is too expensive) there's no way to know if the function itself should be called, or if it is to be called using currying. The A2 call itself can be inlined, but nothing more.

But what if we made the Elm compiler smarter? If the Elm compiler knew how many arguments a function required, it could re-write this:

A2(author$project$Main$add, 1, 2)

into

author$project$Main$add.f(1, 2)

We make a copy of our benchmark, and make these changes by hand for every function call in our benchmark, and in the functions called by the benchmark.

This time we're going to focus on the results for the following function:

benchmark "* 2" <|
  \_ -> map (\a -> a * 2) intList

The result:

Firefox, before modification: 24,291 ops/sec
Firefox, after modification: 50,927 ops/sec
Safari, before modification: 35,723 ops/sec
Safari, after modification: 49,029 ops/sec
Chrome, before modification: 39,253 ops/sec
Chrome, after modification: 58,491 ops/sec

Pretty good. The performance in Firefox is doubled, while we're seeing ~30% improvements in Chrome and Safari.

When looking at the inlining results of the unmodified code:

Inlined functions (count = 1)
 0x13f84c332341 <SharedFunctionInfo A2>

We can see there's been some changes after the modifications:

Inlined functions (count = 5)
 0x1f31bec396e1 <SharedFunctionInfo $map>
 0x1f31bec395a9 <SharedFunctionInfo $foldr>
 0x1f31bec39541 <SharedFunctionInfo $foldrHelper>
 0x1f31bec32049 <SharedFunctionInfo F2>
 0x1f31bec31fe1 <SharedFunctionInfo F>

However, looking over the generated assembly code I'm seeing a lot of lines containing the following:

call 0x1e5fad48abe0  (Call_ReceiverIsNotNullOrUndefined)

When we're calling functions using someObject.f(args), Chrome has to make sure that someObject isn't null or undefined.

I've run one more benchmark. This time I've placed functions outside of F wrappers, and call them directly.

The result:

Firefox, before modification: 50,927 ops/sec
Firefox, after modification: 59,632 ops/sec
Safari, before modification: 49,029 ops/sec
Safari, after modification: 43,695 ops/sec
Chrome, before modification: 58,491 ops/sec
Chrome, after modification: 63,619 ops/sec

Chrome and Firefox see some nice speedups, ~16% for Firefox and ~8% for Chrome. Safari actually sees a slowdown but I don't know why. Re-running the benchmarks several times gives wildly different results, and I don't know what to make of that.

Conclusion

Elm is fast, but there's still room to become faster. By making changes to how the Elm compiler outputs Javascript, we can increase the performance of Elm programs by a significant margin.

Language Idea: Limit custom types to three arguments

Robin Heggelund Hansen — Sun, 23 Sep 2018 19:35:20 +0000

Language Idea is a new series where I note down some ideas I have on how Elm could improve as a language. Each post isn't necessarily a fully thought out idea, as part of my thinking process is writing stuff down. This is more a discussion starter than anything else.

In Elm 0.19 you can no longer create tuples which contains more than three elements. The reasoning behind this is that it's easy to lose track of what the elements represents after that. As an example:

(0, 64, 32, 32)

Is a bit more cryptic than:

{ xPosition = 0
, yPosition = 64
, width = 32
, height = 32
}

The rule here is quite simple, if you feel yourself in need of a tuple containing more than three elements you're better of using a record with named fields.

There is, however, another way in which you can work around this restriction in Elm 0.19.

Custom Types

Yes. Custom types can still contain more than three parameters. Which is strange, as there is little to separate tuples from custom types with the exception of syntax and comparability.

Let me be clear though, you should prefer records with named fields. Names provide basic documentation, and records let you forget about what order parameters are in. I'd say that even when you're using custom types, you should always limit them to three (maybe even two) parameters and use records if you need more than that.

As to why Elm allows more than three parameters in custom types; I don't know. It might just be an oversight.

So here is a question: should Elm limit the number of parameters in custom types to three, as it does with tuples?

I think it should.

Edit: The idea here is that one can do type Person = Person { name : String, age : Int } instead of type Person = Person String Int as it would make it more obious what each parameter is. It should then be encouraged to use records within custom types if there are many fields to store within the custom type.

Elm 0.19 brings better collections

Robin Heggelund Hansen — Tue, 21 Aug 2018 19:39:22 +0000

You're probably aware of this already but Elm 0.19 has just been released. When you read through the release notes and the documentation of the core library, you might to think that nothing has changed with regards to the built-in collection types: List, Array, Dict and Set.

You'd be wrong.

While it is true that the API remains entirely the same, there are huge changes under the covers which results in more performance, and a bug-free Array implementation. Let's take a closer look.

List

List is the data structure which have changed the least. In fact, the underlying data structure hasn't changed at all. The only thing which have changed is the implementation of List.foldr which is now faster by about 30%.

This alone might not seem to be that big of a deal, but considering map, filter and append are all implemented on top of foldr, this means that List is quite a bit faster across the board.

If you want to know more about the actual implementation, you can take a look at this PR.

Dict and Set

Dict has actually been re-written from scratch while retaining the original API. The benefits of this new implementation is mostly that of performance. We're talking 170% faster inserts and about 30% faster removals.

Set is just a thin wrapper around Dict, and so Set benefits from the new implementation as well.

More info in the PR and these development updates: #1, #2.

Array

Like Dict, Array has been totally re-written. The original code was in Javascript, and suffered from grave bugs that could cause runtime crashes and mutations. The new implementation is in mostly Elm, and all known bugs are fixed.

From a performance stand point, the implementation is faster in some cases, while slower in others. More information in this development update.

Summary

The API might be the same, however, a huge amount of work has been done to make these data structures better than ever before.

There is a similar story for the Random module, which has been re-implemented by Max Goldstein to be faster and more, you know, random. You can learn more by checking out this PR.

The case for replacing Array.slice

Robin Heggelund Hansen — Fri, 10 Aug 2018 18:28:14 +0000

I recently did some work which required me to create a sub-section of an Array. This can be done by using Array.slice but doing so always gives me the feeling that there is room for improvement.

To explain why, let's start by looking at a small example:

Array.slice 2 5 someArray

It isn't immediately obvious to me what this does. I know it creates a sub section, but when reading this I always have to stop up and calculate what the result will be. Usually, because I don't use this function too often, I also have to look up the documentation to check if the from and to indices are exclusive or inclusive.

The conclusion is that this particular code will create a new array, containing the values of indices 2, 3 and 4 of someArray. This might not seem too bad when you actually want to extract a sub-section of an array from some index and to (but not including) another, but in my experience that is rarely the case.

Usually what you -- well, I -- want is either to remove the first couple of elements, or to remove the last couple of elements. Since slice is all we got, we've always got to consider what value to use for both arguments, which adds a slight, but unnecessary, mental overhead.

For instance, removing the first two elements is implemented as:

Array.slice 2 (Array.length someArray) someArray

This doesn't read as easily as Array.drop 2 someArray, but another problem is that it doesn't play well with pipelines. Removing the last element is easier as slice supports negative indices, although it is a little more cryptic than it has to be:

Array.slice 0 -1 someArray

Even if you actually want a true sub-section, I'd argue that it would be easier to understand the code if you expressed it as two separate operations, like this:

someArray
  |> Array.drop 2
  |> Array.take 3

someArray
  |> Array.drop 2
  |> Array.dropLast 2

In summary, I believe slice is a bad fit for functional programming. Using functions which have a clear intent and an intuitive usage is a better fit, and so I believe slice should be replaced with take, takeLast, drop and dropLast.

Exploring how Elm can target Web Assembly

Robin Heggelund Hansen — Mon, 28 May 2018 21:43:53 +0000

Title sounds interesting, doesn't it? Last week I got this idea into my head that wouldn't leave. And so, I'm announcing ELS.

What's ELS? It's an experimental compiler for a statically typed Lisp which compiles to Web Assembly. As to what ELS actually means... I'm not sure yet, but I'll be sure to let you know once I find a phrase it can be a fitting acronym for =)

I imagine you might be a bit confused at this point. You might even have double checked the title to make sure it actually contains the word Elm, which it does. So why am I talking about Lisp?

Web Assembly

There are several people who've asked if, or when, Elm will target Web Assembly (WASM). I do believe Elm will target WASM eventually as it will let us escape some wierd Javascript semantics (like 53-bit ints, ugh), promises smaller asset sizes and (maybe) better performance.

It's early days, however, and targeting WASM isn't as easy as targeting Javascript. There are no objects in WASM. No arrays, strings or closures. Heck, there isn't even a builtin memory allocator, let alone a garbage collector.

Now, a garbage collector will come sometime in the future. So in the meantime, the time of Evan (author of Elm) is better spent on other things.

So what's this ELS thing about?

Well. Even though adding Elm support in the compiler will be a huge effort for potentially little gain (let's be honest, there are better ways to improve Elm than what it compiles to), that doesn't mean that exploring the space is wasted effort. As Evan has said previously: "Code is the easy part."

How should ports work in a WASM world? How should strings work? Would using the future builtin GC be best, or could a language like Elm do better with a custom GC scheme? How do we compile curried functions to WASM? How would the REPL work? Could Erlang like processes be implemented?

There are a bunch of questions to answer, and there is no reason not to explore that space early on. If we're lucky, by the time Elm is ready to target WASM, some of the ground work will be done already.

But... Lisp?

So, I had a problem. I wanted to explore how Elm could compile down to WASM, but I don't really know how the Elm compiler works and, more importantly, don't know Haskell. Luckily, the important thing isn't actually to compile Elm, but compiling a language which has the same semantics as Elm. So I decided to build my own language in Javascript which meets that requirement. Since I don't really care what the language looks like, I chose syntax which was easy to parse, and that was Lisp (with type annotations, of course).

There where other considerations as well. There already are tools for WASM in Javascript, and being able to execute WASM requires a Javascript environment. Writing the compiler in JS therefore makes things a bit simpler.

The big downside is that none of the compiler work I do can be merged into the Elm compiler sometime down the road. But that's fine. This is an experiment, and I don't expect that the code I write is something one would want to re-use anyway.

What I do hope is that the experience I get from this makes it possible for me to assist with porting Elm to WASM in the future. I might even be able to write some modules which Elm can make use of when that happens, like a string library or even a basic garbage collector which can serve as a stop gap until WASM gets a GC of its own.

Can I try it out?

Sure. The code, and instructions for trying it out, are available here.

De-throning the List: Summary

Robin Heggelund Hansen — Tue, 08 May 2018 22:37:31 +0000

I've written a total of five posts (or six, including this one) about why I would like to replace the List with Array. If you'd missed one, here they all are:

These posts lists a ton of work. First we need to alter the Array implementation to improve performance in even more cases. Then we need to make it more extensible by introducing stoppable fold operations. Then we need to add functions that currently exists for List, but not for Array. Finally, we can make the Elm compiler output a literal representation of Array directly in the javascript code.

But why do all this work? Because I honestly believe Elm becomes easier to learn if the default collection type not only works similarly to the default collection type in other languages, but also provides decent performance for most cases you wish to use it with. I also believe Elm will become faster in the general case, if Array is used in all the places List is used today.

I might not be right. But I do think it will be an undertaking worth taking. Or... Uh... You know what I mean.

The next and first step of this journey will be to upgrade the Array implementation from being a HAMT to an RRB-Tree. This process will probably take a while, but expect a new blog post with benchmark results when it happens.

Thank you for reading!

De-throning the List: Part Boron

Robin Heggelund Hansen — Tue, 08 May 2018 22:35:45 +0000

In the last post of this series, we talked about extending the API for Array to make it as usable as List. In this post, we'll look at how making Array the default collection could reduce overhead, and thus improve performance.

In Elm 0.18, when the compiler sees an expression like this:

list = [1, 2, 3]

It compiles it into the following javascript code:

var _some_namespace_list = {ctor: '::', _0: 1, _1: {ctor: '::', _0: 2, _1: {ctor: '::', _0: 3, _1: {ctor: '[]'}}}};

This is actually pretty nice, though it looks ugly, as it's theoretically the fastest way of creating a List. Unfortunately, due to the way Chrome works it can also crash the browser if the List literal is big enough. This has to do with the object literals being nested, the javascript engine can only support so much nesting before it crashes. You can read more about this in the following issue.

So in Elm 0.19, to avoid this problem, it will instead compile down to this javascript code:

var _some_namespace_list = _elm_core_fromArray([1, 2, 3]);

This works, but it does mean that every time you have a List literal in your program, Elm will convert it from a javascript array at runtime. This extra conversion, could make your app a little slower.

How much slower?

I thought you'd never ask. It's benchmark time!

This benchmark compares calling List.foldl (\a b -> a + b) 0 with [1,2,3,4,5,6,7,8,9] using Elm 0.18's literal expression (nested objects) and 0.19 runtime conversion. By hand-editing the compiled output, we can get a benchmark of how the equivalent code with an Array literal performs. You can read the benchmark code here.

The benchmark was run on the latest version of Chrome (v66), running the latest version of Mac OS X (High Sierra), on a Mid-2012 Macbook Air.

List literal sum: 873,847 ops/sec
List runtime sum: 1,959,202 ops/sec (124.2% faster than list literal)
Array literal sum: 3,329,392 ops/sec (40.61% faster than list runtime)

These results are pretty interesting. You'll see that runtime conversion is actually significantly faster than having a literal representation in Chrome. This is probably tied together with the runtime crashing issue described earlier. If we were to run this benchmark through Firefox and Safari, you'd see that runtime conversion is between 10-20% slower than literal representation.

The more interesting thing is that an Array literal would be faster still. From running this benchmark on different browsers with different sizes of List literals, I think this has to do with the nesting of objects. Appearently, nested object literals are not good for performance. A List is "just" nested objects, while Array has a very flat structure.

What would an `Array` literal look like?

If Array had been the default collection type, the compiler could've have turned it into the following javascript code:

var _some_namespace_list = {ctor: 'Array', _0: 3, _1: 5, _2: [], _3: [1,2,3]};

This is shorter than the original literal representation for List. It's also less nested. A List with 1024 elements requires 1024 nested object literals when expressed as javascript, an Array would require 3 nested literals.

Summary

Although List literals in Chrome is as slow as an asthmatic ant with heavy shopping, and might even crash the Elm application altogether, Array literals are fast and safe.

Literal syntax for List is used heavily in Elm for stuff like Html nodes, so being able to construct such literals quickly is of huge value. By switching default collection type to Array there is a clear performance win to be had.

All my arguments and thoughts regarding making Array the default collection type have now been made. Read this next post for a summary of what I've written so far, and what I plan to do next.

De-throning the List: Part SC4K

Robin Heggelund Hansen — Mon, 23 Apr 2018 17:37:27 +0000

In the last post we looked at how we could make Array more expressive. By which I mean we added a way for people to extend the data structure to support more use cases. But while third parties now can add missing functionality, there are certain functions which should be supported out of the box, both for performance and convenience reasons.

Elm has four built-in collection types: List, Array, Dict and Set. With the exception of Dict, these types look similar from a birds eye view. You can insert an item into the collection, get it back out, and even perform some task for every item stored. Of course, they do have different trade-offs which make them suitable for different situations.

The List is great when adding and retrieving items at the beginning (left side) of the collection. Array is great when you need fast access to any element, and Set is good when you need a sorted collection with no duplicates.

The API for these collections are different as well. Sometimes this makes sense, but not always. For instance, there is no sort function for Set, which is reasonable as Set is a sorted collection. However, there also isn't a sort function for Array, which means that you have to convert it to a List or a Set and then back again if you want it sorted.

Converting from one collection type to another is a costly operation. If you use an Array because it suits your use case most of the time, you don't want to convert to another collection just to perform that one operation.

Let's look at how we can improve the API of List, Array and Set to reduce the need for converting from one collection type to another to support the functionality you need.

Differences which should remain

Certain operations aren't supported on a collection type with good reason. For instance, there is not get or set operation on List because the performance would be bad. If one need to get or set a random item in a collection, Array should be used. Likewise, union, intersect and diff should only be supported for Set. Here are some functions that are not supported by all three collection types, which I believe shouldn't be supported either:

get, set, insert, remove, :: and push can only be supported efficiently by their respective collections. If you're in need of one of these functions, it's a tell-tale sign of which collection you should use. However, with the improvements I've mentioned in earlier posts, Array could support all of these functions efficiently, which is yet another reason as to why Array should be the default collection type.

indexedMap and toIndexedList make no sense for Set, as it doesn't operate by indexes and doesn't retain insertion order. repeat doesn't make much sense for Set either, as it cannot contain duplicates.

union, intersect and diff can only be efficiently implemented by Set.

head can be supported efficiently by the other collections, but the operation itself really only makes sense for List. Array would use get 0, and it isn't quite clear what head means in the case of Sets, is it the first/lowest/minimal element or the root/middle element?

sort, sortBy and sortWith doesn't make sense for Set, but Array should definitely get these functions.

reverse can be implemented efficiently for Array, but makes little sense for Set.

Where we could bridge the gap

Below is a list of functions which can be easily supported across all three collections:

singleton
initialize
range
concat
intersperse
member
map2, map3, map4, map5
concatMap
filterMap
partition
take
drop
unzip
slice
sum
product
maximum
minimum
all
any
scanl

While these functions could be supported across all three collections, does that mean they should? Since we're already messing about, let's ask ourselves if there are certain functions that shouldn't be in core to begin with.

sum and product are essentially shortcuts for List.foldl (+) 0 and List.foldl (*) 1. Are those operations common enough to grant them dedicated functions in the core library? If we introduce slice for all three collections, do we need take and drop?

Do people actually use map4 and map5? How about scanl and unzip? I mean, there probably are, but are those operations so common that one would expect to find them in core? Not that it necessarily does any harm, but there is something to be said of having a small, but powerful, package where you can read the entire documentation in a short sitting.

Anyway, here's a list of which functions I, personally, see no reason for having in core. I expect people will tell me that these functions definitely belong, but I think it would be nice to at least have the discussion.

intersperse
map4
map5
concatMap
unzip
sum
product
scanl
take
drop

Finishing touches

Here are some minor things I think shouldn't be left out of a API renovation:

List and Array has a length function, Set has size. This is likely due to the fact that Set is a thin abstraction on top of Dict and so has just copied the name. I would rename Set.size to Set.length out of consistency if nothing else.

Now that I'm on the topic, since Set is thin abstraction on top of Dict, maybe everything discussed up til this point applies to Dict as well?

List has :: and tail. The analogous for Array is push and pop. pop is missing from the API, so I would add it.

I would add find for all three collections. List and Set already supports member, which is essentially find except that it returns a boolean instead of the value for which the predicate function returns true. It's a more useful function in general, and so if member should be a part of the API (which I believe it should) then find belongs as well.

For Set and Dict I would throw in min and max to retrieve the minimum/first and maximum/last element.

I think Stack is a better name than List and so would rename that type. It's a name that more clearly explains what that collection type is good at.

Finally, as mentioned in the previous post, I think stoppableFoldl and stoppableFoldr, or something with the same functionality but with better names, should be added to the API of Array. I think Dict and Set could be well served with that functionality as well.

What do you think?

The goal I'm trying to reach is to make the Array type more general purpose, but when improving the Array API, it makes sense to look at the other collection types as well. This article lays out what I believe those APIs should look like.

First, I want to say that I'm not authority on what makes it into Elm. If I actually code up the suggestions in this article and submit it as a proposal, all of it could make it in, or none of it.

Second, all these suggestions are based on my own experience. What I need is your experience. Does these suggestions make sense, or am I off my rockers? Let me know in the discussion thread on the Elm Discourse.

And now, for something quite different

So, is this the end of this series? Not quite. There's a summary left the be published, but that will have to wait until after we go over the top (you didn't think I'd forgot, did you?) in the next post, which is about the literal representation of List and Array.

De-throning the List: Part π

Robin Heggelund Hansen — Sun, 22 Apr 2018 11:49:11 +0000

In the last post, we looked at how we could alter the implementation of Array to make it a more general purpose than it already is (like, five stars). In this post, we’ll see if we can make it more extensible.

Extensible? What does that mean?

Let’s see how we would implement a function like find for Array. find takes a predicate function and a collection, and returns the first item in the collection for which the predicate returns true, or Nothing if the predicate never returns true.

The only way to implement this for Array is by using foldl or foldr:

find : (a -> Bool) -> Array a -> Maybe a
find pred array =
    Array.foldl
        (\item result ->
            if result == Nothing && pred item then
                Just item
            else
                result
        )
        Nothing
        array

While this implementation does what we want, it isn’t that efficient. When this implementation finds what we’re looking for, it will keep iterating through all the remaining items in the collection. Depending on the size of the array, this can be very slow.

Is List any better? Yes, yes it is:

find : (a -> Bool) -> List a -> Maybe a
find pred list =
    case list of
        [] ->
            Nothing

        x :: xs ->
            if pred x then
                Just x
            else
                find pred xs

This implementation does exactelly what we want. This is a benefit of List being a simple data structure, it’s easy to pattern match on it to get the functionality we want. I explained briefly in my first post why the internal structure of Array is not exposed like this, but I’ll say it again: it’s simply not simple, and it’s easy to make mistakes that can cause hard to find bugs. Now, before you go all «Off with Arrays head», let’s explore how we can get this same extensibility for Array.

Looking at the List version of find, what we need is a way to iterate through the collection but be able to say «Hey! That’s my horse!» at any point and cut the iteration short. We could borrow an idea from Common Lisp and add a new function to the Array API which allows us to signal that we’re done iterating. Such a function, called stoppableFoldl in the example below, would allow us to implement find like this:

find : (a -> Bool) -> Array a -> Maybe a
find pred array =
    Array.stoppableFoldl
        (\item result ->
            if pred item then
                Done (Just item)
            else
                Continue result
        )
        Nothing
        array

That doesn’t look so bad. Let’s see how these implementations stack up against each other, performance wise. The benchmarks below were run on a mid-2012 Macbook Air, using the latest version of Chrome. The benchmark creates a list and an array with 100 elements, and tries to find a value in the middle of the collection. The code can be found here.

List:   402,870 ops/sec
Array:  227,745 ops/sec
% diff: -43.47%

Auch. It’s seems List is still faster. It’s probably a combination of calling a function for every item in the Array, as well as performing an extra allocation per item (Done/Continue).

"But Robin," you say. "Doesn't this benchmark prove that List is better than Array? Is the reason behind this blog post taking so long to publish that you've been wandering around town soothing your bruised pride with alcohol?"

Yes. I mean no! My argument in this series has been that Array should be the default because it's a more general purpose data structure when compared to the List. This doesn't mean that Array will beat List in all benchmarks, but that it will have decent performance for most operations.

For instance, we can just as well provide a stoppableFoldr function to make it possible to implement findLast. The performance for find and findLast would be about the same. This would not be the case for List, which would have worse performance for findLast.

That’s the point I’m trying to make: List is very good at a few things, Array is fine for most things. Even Array makes use of List in it’s internal implementation (take a look at how Array.filter is implementated). For most applications, the Array is a better default. So maybe Array shouldn’t outright replace List, but simply be the data type that is constructed when literal syntax is used (like [1, 2, 3]). It might even be a good idea to rename List to Stack to signal what it really is good at.

What remains?

There are still things you cannot do with Array which are available with List. In the next part of this series, we’ll compare the API exposed by the Array and List module, and see where we need to bridge the gap, and perhaps even where the gap shouldn’t be bridged.

DEV Community: Robin Heggelund Hansen

Play: A new programming language that targets Web Assembly, based on Forth

Getting started with Elm Warrior

Getting started

Solving the first level

Solving the next levels

Debugging

Speeding things up, or slowing things down

Focusing on a single level

Further challenges

Become an Elm warrior

How about a game?

Announcing Elm Warrior

Improving Elm's compiler output

Hidden classes

Inlining

Currying

Conclusion

Further reading

Language Idea: Limit custom types to three arguments

Custom Types

Elm 0.19 brings better collections

List

Dict and Set

Array

Summary

The case for replacing Array.slice

Exploring how Elm can target Web Assembly

Web Assembly

So what's this ELS thing about?

But... Lisp?

Can I try it out?

De-throning the List: Summary

De-throning the List: Part Boron

How much slower?

What would an Array literal look like?

Summary

De-throning the List: Part SC4K

Differences which should remain

Where we could bridge the gap

Finishing touches

What do you think?

And now, for something quite different

De-throning the List: Part π

What remains?

What would an `Array` literal look like?