Coder Social home page Coder Social logo

getfirefly / firefly Goto Github PK

View Code? Open in Web Editor NEW
3.6K 86.0 103.0 13.96 MB

An alternative BEAM implementation, designed for WebAssembly

License: Apache License 2.0

Rust 84.27% Erlang 2.87% C++ 8.88% CMake 0.08% C 2.35% Assembly 1.07% RenderScript 0.06% Elixir 0.11% MLIR 0.01% Python 0.02% OpenEdge ABL 0.28%
beam erlang erlang-vm virtual-machine web-assembly compiler lumen hacktoberfest

firefly's Introduction

Firefly - A new compiler and runtime for BEAM languages

x86_64-apple-darwin x86_64-unknown-linux-gnu

NOTE: This section is a placeholder for the moment until we get our toolchain packaging implemented

To use Firefly, you'll need to download our toolchain here, and install it like so:

> tar -xzf firefly.tar.gz /usr/local/

This will install the firefly executable to /usr/local/bin/firefly and various supporting files to appropriate locations under /usr/local. If you install to a different target directory, make sure you add the bin folder to your PATH, for example:

> tar -xzf firefly.tar.gz $HOME/.local/share/firefly
> export PATH=$HOME/.local/share/firefly/bin:$PATH

NOTE: This section reflects the way Firefly is supposed to work, but the current implementation may lack functionality described here. However, if you encounter something broken, feel free to open an issue if there isn't one already, and we'll ensure it gets tracked as we continue to improve the project.

You should now be able to run firefly, start by reviewing the output of the help command:

> firefly help

This will print out the various ways you can use the Firefly compiler. Obviously, the most interesting is the ability to compile some code, so let's see how that works.

Firefly can compile executables or static/dynamic libraries. By default an executable is produced which acts very similar to an OTP release, but this behavior can be customized depending on how you want the executable to be used. For example, when compiling an executable that you wish to use as a CLI tool, you might want a specific module/function to always be called with the arguments passed to the program when the system has booted. There are options to the compile command that allow you to do this, and much more. It is even possible to provide your own init, and handle everything manually, including management of the core supervision tree.

NOTE: Firefly does not do any dependency management itself, and we have not yet provided Rebar/Mix shims to integrate Firefly as a compiler with those tools, so compiling an application and all of its dependencies is still somewhat of a manual process. This will be addressed in the near future.

Firefly allows you to compile Erlang sources a couple of ways, let's take a look at each:

Compiling Files/Directories

NOTE: Since Firefly is not compiling for a virtual machine, it does not produce BEAM bytecode like erlc does. Instead, it produces either an executable or a static/dynamic library depending on the type of application being compiled, unless otherwise overridden by compiler options. By default, for OTP applications (i.e. apps which define the mod key in their application manifest), Firefly will produce an executable that runs that application much like an OTP release would. For library applications (i.e. apps that do not define the mod key in their manifest), Firefly will produce a static library which can be linked into an executable at another time. You may specify --bin to force production of an executable, or --lib to force production of a library. If you want to compile a shared library, pass --lib --dynamic.

You can compile one or more Erlang source files by specifying their paths like so:

> firefly compile src/foo.erl src/bar.erl

NOTE: Since there is no application manifest available, these sources will be treated as modules of an anonymous library application with the same name as the current working directory. As such, the output of the above command will be a static library.

Alternatively, you can compile all the files found in one or more directories, by specifying their path:

> firefly compile app1/ app2/

In this case, each directory will be treated as an application; if no .app or .app.src manifest is found in a directory, then a new anonymous library application with the same name as the directory will be used as the container for the sources in that directory. Since no root application manifest was provided, an anonymous library application with the same name as the current working directory will be used as the "root" of the dependency tree. In other words, if the name of our current directory is myapp, then in the example above, app1 and app2 will be treated as dependencies of the myapp application, and will result in a static library being produced containing all three applications.

When specifying files individually on the command line, you can control the default app properties using compiler flags, and use that to manage what type of output gets produced. For example:

> firefly compile --app-name myapp --app-module foo src/foo.erl src/bar.erl

This is equivalent to:

> firefly compile --app src/myapp.app src/foo.erl src/bar.erl

Where src/myapp.app looks like:

{application, myapp, [{mod, {foo, []}}]}.

In both cases, the result is an executable containing the myapp application, which consists of two modules: foo and bar.

Let's assume that src/foo.erl contains the following:

-module(foo).
-behaviour(application).
-export([start/2]).

start(_, _) ->
    erlang:display("hello"),
    bar:start_link().
    
stop(_) -> ok.

Then we should see the following when we run our compiled executable:

> _build/firefly/arm64-apple-macosx11.0.0/myapp
"hello"

NOTE: The directory under _build/firefly contains the target triple the executable was compiled for, and since this example was compiled on an M1, the triple reflects that.

Compiling Projects

Firefly also recognizes the conventional Erlang project structure. For example, let's say you have an application called hello:

hello/
|-include/
|-src/
  |-hello.app.src
  |-hello.erl
  |-hello_sup.erl

Where hello.app contains:

{application, hello, [{vsn, "1.0"}, {mod, {hello, []}}]}.

and hello.erl contains:

-module(hello).
-behaviour(application).
-export([start/2]).

start(_, _) ->
  erlang:display(<<"hello world!">>),
  hello_sup:start_link().

From the root of the hello/ directory, you can compile this to an executable like so:

> firefly compile

If we run it, it should print our greeting:

> _build/firefly/arm64-apple-macosx11.0.0/hello
<<"hello world!">>

NOTE: The directory under _build/firefly contains the target triple the executable was compiled for, and since this example was compiled on an M1, the triple reflects that.

If you instead wish to compile hello as a library, you can compile with:

> firefly compile --lib

This will produce the static archive _build/firefly/<target>/hello.a.

If you want to compile an application and link in a previously-compiled library, you can do that like so:

# Assume we previously compiled an app called `foo` as a static archive and moved it to `_build/firefly/<target>/foo.a`
> firefly compile -L _build/firefly/<target>/ -lfoo

This tells the compiler to use _build/firefly/<target>/ as a search path for the linker, and to link the library named foo.

Replacing Erlc

Now that you've learned how to use Firefly to compile Erlang sources, what's the best approach for compiling a real world Erlang project?

Let's assume you are in a directory containing a standard Erlang project called myapp, and all of your dependencies are located in the _build/default/lib (the default for rebar3), then the following will compile your application and all its declared dependencies (based on the app manifest) into an executable:

> firefly compile --bin

This works because Firefly has an application manifest to work from, and can infer the location of the sources for the dependencies.

However, if your project is less conventional, then you might want to follow a different approach instead, by compiling each application to a library, and then compiling the root application as an executable while linking in all of the dependencies:

> firefly compile --lib -o foo.a deps/foo
> firefly compile --lib -o bar.a deps/bar
> firefly compile --bin -L. -lfoo -lbar src/

The above assumes that deps/foo and deps/bar are directories containing application manifests, and compiles both to static libraries in the current working directory. The last line will create an executable containing the foo and bar applications, as well as the application contained in src.

This method is more manual, but provides a lot of flexibility for those who need it.

Barebones

NOTE: This is primarily for experimentation and development work, but might be of interest to those interested in implementing inits, or even alternative Erlang standard libraries.

To compile an executable which simply invokes init:boot/1 and leaves the definition of that function up to you, you can use the following:

> firefly compile -C no_default_init --bin init.erl

The resulting executable performs none of the default initialization work that the standard runtime normally does, i.e. there is no init, so no application master/controller, and as a result, none of the normal OTP startup sequence occurs. This does however provide you an opportunity to handle this yourself, however you like; albeit with the major caveat that using any standard library modules without doing the proper initialization or providing the things needed by those modules will almost certainly fail. Erlang without the default init is a very interesting environment to play in!

As an example, consider if init.erl above is defined as the following:

-module(init).
-exports([boot/1]).

boot(Args) ->
    erlang:display(Args).

Running the resulting executable will print the default arguments the runtime provides to the init and then exit.

In order to build Firefly, or make changes to it, you'll need the following installed:

First, you will need to install rustup. Follow the instructions at that link.

Once you have installed rustup, you will need to install the nightly version of Rust (currently our CI builds against the 2022-08-08 nightly, specifically). We require nightly due to a large number of nightly features we use, as well as some dependencies for the WebAssembly targets that we make use of.

# to use the latest nightly
rustup default nightly

# or, in case of issues, install the specific nightly to match our CI
rustup default nightly-2022-11-02
export CARGO_MAKE_TOOLCHAIN=nightly-2022-11-02

In order to run various build tasks in the project, you'll need the cargo-make plugin for Cargo. You can install it with:

cargo install cargo-make

You can see what tasks are available with cargo make --print-steps.

You may also want to install the following tools for editor support (rustfmt will be required on all pull requests!):

rustup component add rustfmt clippy

Next, for wasm32 support, you will need to install the wasm32 targets for the Rust toolchain:

rustup target add wasm32-unknown-unknown --toolchain <name of nightly you chose in the previous step>

LLVM

LLVM is used internally for the final code generation stage. In order to build the compiler, you must have our expected version of LLVM (currently LLVM 15) installed somewhere locally.

LLVM releases are posted here.

Linux (x86_64)

Follow the install instructions here for Debian or Ubuntu. For other distros, you are going to have to check whether our required LLVM version is available via your package manager, and either use that, or build LLVM from source. Ideally you won't need to do the latter, but you can also try slightly newer LLVM releases as well, if they are available, which may also work, but is not a supported configuration.

Once installed, make sure you export LLVM_PREFIX in your environment when working in the Firefly repo, e.g. building the compiler.

macOS (arm64 and x86_64)

Go to the releases page mentioned above, and follow the download link to the GitHub releases page. From here, you'll want to select the clang+llvm package which matches your platform, then follow the instructions below. NOTE: The following instructions use the arm64 release for the example:

mkdir -p $XDG_DATA_HOME/llvm/
cd $XDG_DATA_HOME/llvm/
wget 'https://github.com/llvm/llvm-project/releases/download/llvmorg-15.0.7/clang+llvm-15.0.7-arm64-apple-darwin22.0.tar.xz'
tar -xzf clang+llvm-15.0.7-arm64-apple-darwin22.0.tar.xz
mv clang+llvm-15.0.7-arm64-apple-darwin22.0.tar.xz firefly
rm clang+llvm-15.0.7-arm64-apple-darwin22.0.tar.gz
cd -
export LLVM_PREFIX="${XDG_DATA_HOME}/llvm/firefly"

Once LLVM is installed, you can build the firefly executable!

NOTE: Firefly has components that need to be compiled with clang; On Linux, the default compiler is generally gcc. You'll need to make sure to use clang instead. The LLVM toolchain should include clang, but you may need to install it separately from your package manager. Then, export the following environment variables when building Firefly:

export CC=$XDG_DATA_HOME/llvm/firefly/bin/clang
export CXX=$XDG_DATA_HOME/llvm/firefly/bin/clang++

To build Firefly, run the following:

LLVM_PREFIX=$XDG_DATA_HOME/llvm/firefly cargo make firefly

NOTE: If you have .direnv installed, run direnv allow in the project root, and you can omit all of the above environment variables, and instead modify the .envrc file if needed.

This will create the compiler executable and associated toolchain for the host machine under bin in the root of the project. You can invoke firefly via the symlink bin/firefly, e.g.:

bin/firefly --help

You can compile an Erlang file to an executable (currently only on x86_64/AArch64):

bin/firefly compile [<path/to/file_or_directory>..]

This will produce an executable with the same name as the source file in the current working directory with no extension (except on Windows, where it will have the .exe extension).

NOTE: Firefly is still in a very experimental stage of development, so stability is not guaranteed.

Firefly is currently divided into three major components:

Compiler

The Firefly compiler is composed of many small components, but the few most interesting are:

  • firefly is the crate for the firefly executable itself, but it is largely empty, most of the meat is in other crates
  • compiler/driver, handles driving the compiler, i.e. parsing arguments, handling commands, and orchestrating tasks; it also defines the compiler pipeline. It currently also contains the passes which perform code generation.
  • compiler/syntax_base, contains common types and metadata used in many places across the compiler
  • compiler/syntax_*, these crates implement the frontend and middle-tier of the compiler. Each one provides an intermediate representation, semantic analysis, transforms to other representations, output to a textual format, and in some cases, parsing.
    • syntax_erl is the primary frontend of the compiler, which handles Erlang sources
    • syntax_pp, is a frontend for Abstract Erlang Format, and converts to the AST from syntax_erl
    • syntax_core is a high-level intermediate representation to which the AST is lowered after some initial semantic analysis. Core is an extended form of lambda calculus, so is highly normalized, and is where we do the remaining semantic analysis tasks. Core is also where comprehension and receive expressions are transformed into their lower level representations. Core is logically split into two forms, "internal" and regular. The internal form is used during initial lowering, before certain transformations have been applied. The regular form of Core has certain properties which must be upheld, and the internal form does not enforce them.
    • syntax_kernel is a specialized intermediate representation to which Core is lowered. It is completely flat, i.e. no nested scopes, variables are unique, all function calls are resolved, dynamic apply is converted to a call to erlang:apply/2,3, and all closures have been lifted. During the lowering from Core, pattern matching compilation is performed, and some liveness analysis is performed.
    • syntax_ssa is a low-level SSA IR to which Kernel is lowered. While Kernel is flat, it is still expression based, SSA breaks things down further into blocks, jumps, and instructions for a register-based machine. From here, we can perform code generation either to native code, or bytecode.
  • compiler/linker, performs all the work needed to link generated code into objects/libraries/executables.

The remaining crates under compiler/ are support crates of some kind.

Libraries

There are a number of core libraries that are used by the runtime, but are also in some cases shared with the compiler. These are designed to either be optional components, or part of a tiered system of crates that build up functionality for the various runtime crates.

  • library/system, provides abstractions over platform-specific implementation details that most of the runtime code doesn't need to know about. This primarily handles unifying low-level platform APIs.
  • library/alloc, provides abstractions for memory management
  • library/arena, this is a helper crate that provides an implementation of both typed and untyped arenas
  • library/rt, this is the primary core runtime library, hence the name, and provides the implementations of all the term types and their native APIs, as well as establishing things like the calling convention for Erlang functions, exceptions and backtraces, and other universal runtime concerns that cannot be delegated to a higher-level runtime crate.
  • library/binary, this crate provides all the pieces for implementing binaries/bitstrings, including pattern matching primitives and constructors.
  • library/number, this crate provides the internal implementation of numeric types for both the compiler and runtime
  • library/beam, this crate provides native APIs for working with BEAM files
  • library/bytecode, this crate defines the opcodes for the bytecode emulator, as well as support for the binary bytecode format

Runtimes

The runtime is intended to be pluggable, so it consists of a "wrapper" crate that provides the entry point for executables, and a specific runtime implementation. Currently there is only one of the latter.

  • runtimes/crt, plays the role of crt0 in our system, i.e. it provides the entry point, initializes the function and atom tables, and invokes the main function of the linked-in runtime.
  • runtimes/emulator, provides a runtime which operates on the output of the bytecode compiler

At this stage of the project, it is important that any changes you wish to contribute are communicated with us first, as there is a good chance we are working on those areas of the code, or have plans around them that will impact your implementation. Please open an issue tagged appropriately based on the part of the project you are contributing to, with an explanation of the issue/change and how you'd like to approach implementation. If there are no conflicts/everything looks good, we'll make sure to avoid stepping on your toes and provide any help you need.

For smaller changes/bug fixes, feel free to open an issue first if you are new to the project and want some guidance on working through the fix. Otherwise, it is acceptable to just open a PR directly with your fix, and let the review happen there.

Always feel free to open issues for bugs, and even perceived issues or questions, as they can be a useful resource for others; but please do make sure to use the search function to avoid duplication!

If you plan to participate in discussions, or contribute to the project, be aware that this project will not tolerate abuse of any kind against other members of the community; if you feel that someone is being abusive or inappropriate, please contact one of the core team members directly (or all of us). We want to foster an environment where people both new and experienced feel welcomed, can have their questions answered, and hopefully work together to make this project better!

Firefly is not only a compiler, but a runtime as well. It consists of two parts:

  • A compiler for Erlang to native code for a given target (x86, ARM, WebAssembly)
  • An Erlang runtime, implemented in Rust, which provides the core functionality needed to implement OTP

The primary motivator for Firefly's development was the ability to compile Elixir applications that could target WebAssembly, enabling use of Elixir as a language for frontend development. It is also possible to use Firefly to target other platforms as well, by producing self-contained executables on platforms such as x86.

Firefly is different than BEAM in the following ways:

  • It supports compilation to standalone executables
  • It is designed to support targeting WebAssembly, as well as many other types of targets.
  • It is designed to support both ahead-of-time compilation to machine code, and compilation to bytecode
  • It sacrifices some features to enable additional optimizations, in particular we don't have plans currently to support hot code reloading.
  • It is written as a way to better understand the BEAM itself, and one of its goals is to provide a more accessible means of learning how the BEAM works internally, to the degree that we provide the same functionality as the BEAM. By implementing it in Rust, we also hope to learn how implementing something like the BEAM in a much more restrictive, but safe language impacts its development.
  • Support WebAssembly/embedded systems as a first-class platforms
  • Produce easy-to-deploy static executables as build artifacts
  • Integrate with tooling provided by BEAM languages
  • Feature parity with mainline OTP (with exception of the non-goals listed below)
  • Support for hot upgrades/downgrades
  • Support for dynamic code loading

Firefly is an alternative implementation of Erlang/OTP, so as a result it is not as battle tested, or necessarily as performant as the BEAM itself. Until we have a chance to run some benchmarks, it is hard to know what the difference between the two in terms of performance actually is.

Firefly is not intended to replace BEAM at this point in time. At a minimum, the stated non-goals of this project mean that for at least some percentage of projects, some required functionality would be missing. However, it is meant to be a drop-in replacement for applications which are better served by its feature set.

Compiler

The compiler frontend accepts Erlang source files. This is parsed into an abstract syntax tree, then lowered through a set of intermediate representations where different types of analysis, transformation, or optimization are performed:

  • Core IR (similar to Core Erlang)
  • Kernel IR (similar to Kernel Erlang)
  • SSA IR (a low-level representation used to prepare for code generation)
  • Bytecode/MLIR (where final optimizations and code generation are performed)

The final stage of the compiler depends on whether compiling to bytecode or native code, but in both cases the output produces LLVM IR that is then compiled to one or more object files, and linked via our linker into an executable.

Runtime

The runtime design is mostly the same as OTP, but varies a bit on what type of codegen backend was used. In general though:

  • The entry point sets up the environment, and starts the scheduler
  • The scheduler is composed of one scheduler per thread
  • Each scheduler can steal work from other schedulers if it is short on work
  • Processes are spawned on the same scheduler as the process they are spawned from, but a scheduler is able to steal them away to load balance
  • I/O is asynchronous, and integrates with the signal management performed by the schedulers

The initial version is quite spartan, but should be easy to grow now that we have some of the fundamentals built out.

NIFs

Currently it is straightforward to extend the runtime with native functions implemented in Rust, without all of the extra stuff that goes into port drivers and erl_nif. Currently we have some of the baseline infrastructure in place to support port drivers, but none of the necessary pieces to support erl_nif as of yet. We'll need to start adding some of that in short order however, so it is on our roadmap to support NIFs to at least a minimum degree needed for things required by the standard library.

History

Firefly previously had the name "Lumen". This was intended to be a temporary name and it was changed in 2022, partly due to there being numerous other projects also named Lumen.

License

Apache 2.0

firefly's People

Contributors

bitwalker avatar blatyo avatar bryanjos avatar dependabot[bot] avatar felix-alonso avatar gemantzu avatar hansihe avatar hwood-sp avatar kronicdeth avatar kuzeyardabulut avatar lawik avatar lpil avatar mlwilkerson avatar oskar1233 avatar quinnwilton avatar shaheenery avatar takasehideki avatar tatsuya6502 avatar tuxified avatar xtian avatar zachdaniel avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

firefly's Issues

Implement binary matching/construction

Erlang's bit/binary syntax for matching and construction relies on a combination of runtime support and associated BEAM instructions. Like OTP, our implementation will also rely on runtime support, but will instead compile such expressions directly to invocations of those runtime functions.

The design of binary matching/construction is based on the following pieces:

Data Representation

A binary consists of the following structure:

  • A data block (header, size, binary data)
  • A header block (header, pointer to data block, offset O, size S, bit offset BO, and bit size BS)

The above represents a binary of size (S * 8 + BS) and offset at (O * 8 + BO), in the data block. BS and BO both have values in the range of 0-7. To be clear, both O and BO, and S and BS are needed to calculate sizes/offsets.

The following runtime support functions are needed:

  • binary_start_match calculates metadata needed before matching begins
  • binary_skip_bits used during matching when the segment to match involves a variable
  • binary_get_<type> used during matching to read a number of bits and construct a term of type <type> from them, e.g. binary_get_integer
  • binary_put_<type> like binary_get_<type>, but constructs a number of bits from a term of type <type>, e.g. binary_put_integer
  • binary_put_any, dynamically determines the runtime type of its value and performs the actions of binary_put_<type>
  • binary_init allocates memory for the data block, returns the pointer and an initial offset of 0
  • binary_final creates binary header from the data block pointer and final offset, giving the total size of the binary

Matching

The following pseudocode represents how the above pieces are used to perform matching:

{Offset0, BinSize, Ptr} = binary_start_match(Bin),
EffSize1 = Size1 * Unit1,
%% Specifiers determines how binary data is transformed to term of type <type>
{X1, Offset1} = binary_get_Type1(Specifiers1, EffSize1, Offset0, BinSize, Ptr),
Value1 = X1,
%% EffSizeN = SizeN * UnitN,
%% ...
case OffsetN - 1 of
  BinSize -> Success;
  _Other -> Failure
end

Construction

The following pseudocode represents how the above pieces are used to perform binary construction:

ValueN = ExprN,
EffSizeN = SizeN * UnitN,
BinSize = lists:sum([EffSize1, .., EffSizeN]),
{Offset0, Ptr} = binary_init(BinSize),
OffsetN = binary_put_TypeN(SpecifiersN, EffSizeN, ValueN, OffsetN-1, Ptr),
NewBin = binary_final(OffsetN, Base)

Comprehensions

The Construction section also illustrates the pattern for compiling bit comprehensions with known sizes (i.e. the maximum effective size is determined statically, then allocated all at once, after which each segment is written to it). In the case of non-constant size expressions, it is necessary to fall back to a less efficient algorithm which builds each segment, and then at the very end, copies them all to a new memory area which will hold the finished binary. In LLVM we can do this more efficiently, but ideally we will find ways to always determine the size statically, so we can take the more efficient route.

Implementation

My feeling is that the runtime support for this should probably be implemented directly in LLVM IR, rather than implementing in Rust and using FFI calls. The reason being that I think we will benefit from additional optimizations that LLVM can provide, as well as avoid the extra boilerplate needed when crossing the FFI barrier. This does mean writing LLVM IR by hand, but for this specific algorithm, I think it is actually very straightforward, as the IR has all the functions we need to do bitmasking and the like. The primary thing we will likely still need runtime support for is determining the size of things we are trying to encode to binary, but we may be able to get that in LLVM as well, I haven't gotten to that point yet in the compiler.

Comparison BIFs

  • /=/2 (#93 as are_not_equal_after_conversion_2)
  • </2 (#94 as is_less_than_2)
  • =/=/2 (#91 as are_exactly_not_equal_2)
  • =:=/2 (#90 as are_exactly_equal_2)
  • =</2 (#97 as is_equal_or_less_than_2)
  • ==/2 (#92 as are_equal_after_conversion_2)
  • >/2 (#95 as is_greater_than_2)
  • >=/2 (#96 as is_greater_than_or_equal_2)
  • min/2 (#98)
  • max/2 (#99)

Halt BIFs

These halt the entire VM, so not needed for WASM on the Web, but needed for other targets and WASM outside the web potentially.

  • halt/0
  • halt/1
  • halt/2

Implement Erlang Type struct

Implement some Rust struct that can hold all Erlang types and can be translated over FFI to JS types when needed.

Implement Compiler

This is a meta issue for tracking the components needed to implement a complete compiler frontend+backend for converting Erlang Abstract Format to a generated executable:

  • Basic CLI tooling
  • Parser from Erlang source to Abstract Syntax Tree
  • Parser from debug info chunk in BEAM to Abstract Syntax Tree
  • Linter pass
  • Abstract->Core pass
  • Pattern compilation
  • Core->CPS transform
  • Closure Conversion
  • CPS->LLVM IR pass
  • LLVM IR->Object File
  • Linker

MD5 BIFs

  • md5/1
  • md5_final/1
  • md5_init/0
  • md5_update/2

Binary BIFs

  • Binaries
    • bit_size/1 (#21)
    • bitstring_to_list/1 (#21)
    • binary_part/2(#70)
    • binary_part/3 (#21)
    • byte_size/1 (#21)
    • is_binary/1 (#21)
    • is_bitstring/1 (#71)
    • list_to_binary/1 (#72)
    • list_to_bitstring/1 (#74)
    • split_binary/2 (#76)
    • Parsing to Term
      • binary_to_atom/2 (#21)
      • binary_to_existing_atom/2 (#21)
      • binary_to_float/1 (#21)
      • binary_to_integer/1 (#21)
      • binary_to_integer/2 (#21)
      • binary_to_list/1 (#21)
      • binary_to_list/3 (#21)

Implement ETS runtime support

The importance of ETS in OTP cannot be overstated - it is critical to being even remotely compatible with Erlang and other BEAM languages. As a result, getting this implemented is one of the first runtime features we need to implement.

The design of ETS is based on the concept of tuplespaces, IIRC originating from the Linda programming language, but further explored elsewhere. It may be worth catching up on the research to see what the best implementation strategy may be.

OTP Implementation

In OTP itself, ETS is primarily implemented in C, in the following places:

There is also some handling of some ETS BIFs in the bytecode handling.

ETS has a dedicated allocator, ets_alloc, where all tables and terms stored in tables are allocated.

Lumen Implementation

This is up in the air. The runtime will mimic OTP with multiple allocators which are specialized for certain classes of objects, so we should follow suit and build an ETS allocator like OTP. The actual structure of ETS could be a more or less straight port from OTP, but since there are some differences between Lumen and OTP, perhaps there are better approaches which are unclear at this time.

Implement memory allocators/garbage collection

Like ETS, getting allocation and garbage collection implemented is critical.

More details will be forthcoming, but the gist is that this is another area with close interaction between the compiler and the runtime. The compiler needs to know the nature of the garbage collection technique, so we can insert appropriate metadata and safepoints during execution for performing collection, and invoke the right allocators as necessary.

I'm still exploring the various options, unfortunately while OTP provides a nice high-level design, its specific implementation is too intertwined with how OTP works to port it; we'll have to model our own design after it, but pave our own way in implementation.

On the garbage collection front, we'll want to follow OTPs example, namely a per-process, generational, copying collector. We will likely avoid using LLVMs stack, and instead manage the stack/heap as part of the runtime, rather than the compiler (i.e. from the compilers perspective, everything is allocated either in registers or on the heap). Luckily, we don't need to perform any manual memory management in the Rust runtime, as its automatic memory management via lifetimes ensures that anything allocated in Rust, will be deallocated properly, automatically. For things we allocate in Rust, but for Erlang, that memory will be managed by one of the allocators, and not tracked in Rust.

Tuple BIFs

  • append_element/2 (#21)
  • delete_element/2 (#21)
  • element/2 (#21)
  • insert_element/3 (#21)
  • is_tuple/1 (#21)
  • list_to_tuple/1 (#46)
  • setelement/3 (#49)
  • size/1 (#21)
  • tuple_size/1 (#45)
  • tuple_to_list/1 (#48)
  • Records
    • is_record/2 (#38)
    • is_record/3 (#40)

Atom BIFs

  • Atoms
    • atom_to_binary/2 (#21)
    • atom_to_list/1 (#21)
    • is_atom/1 (#21)
    • list_to_atom/1 (#52)
    • list_to_existing_atom/1 (#53)

Offline Distribution BIFs

Distribution BIFs that are stubbed out to work without distribution working. They should return what is returned when the node is not alive.

  • is_alive/0 (needs to be stubbed to return false for now) (#60)
  • node/0 (stub to return :nonode@nohost) (#61)

Garbage Collection BIFs

These are meant for debugging, so they may never be needed, but I think recon uses them to find binary leaks, so they might be necessary if we support recon over a remote shell when distribution is implemented.

  • garbage_collect/0
  • garbage_collect/1
  • garbage_collect/2
  • garbage_collect_message_area/0
  • gather_gc_info_result/1

Implement scheduler

The scheduler is a critical component of the runtime, and requires tight integration with the compiler (#9). Critically, the compiler must inject yield points based on reduction counting in all non-atomic functions. Due to the CPS representation we are using in the compiler, this is actually rather simple, since we must also perform checks like these for both garbage collection and resetting the stack to support proper tail calls - all of which branch to constructing the current continuation if the check fails, and then performing a jump to transfer control back to the scheduler trampoline.

In the near term, WebAssembly will effectively be restricted to single-threaded execution; but other platforms, and eventually WebAssembly as well, will be multi-threaded. This is a tricky aspect of the implementation in Rust, since there are heavy constraints imposed on data which can be handed off or stolen by other threads. In our case, each thread runs a single scheduler, which also acts as the entry point for the program. Each scheduler maintains multiple local run queues (one for max priority tasks, one for high/normal priority, and one for low priority). If a scheduler runs out of work, it can steal tasks from other schedulers. These tasks are processes, and all of the data associated with the process are stored in the struct representing the process.

Rust places a restriction on references which are owned by a given thread, they must implement either Send (which indicates that ownership can be transferred safely across threads) or Sync (which indicates that borrowing is safe across threads), or both. Critically, Sync generally implies the use of atomics, or mutexes/locks to acquire exclusive access to the borrowed reference, which is significant overhead, and Send is rarely ever derived by default. To work around this, our implementation of how schedulers interact with processes must take this into consideration and ensure that accessing a process is always safe, so that we can provide the necessary unsafe implementations of Send for when a task is stolen and Sync for when one thread needs to send a message to a process on another thread. The way this is handled in BEAM is with a series of hierarchical locks, and I think it is the model we should follow.

In addition, threads must be able to interact with the various heaps in which data accessible to processes may be allocated. In most cases, these heaps will be owned by a process itself, but there are some shared heaps (for large binary data, messages, and more). We need a solution for accessing
these from any thread without global synchronization.

Design Sketch

  • A scheduler per thread
  • One scheduler thread per core
  • Multiple I/O scheduler threads per core (maybe 10x)
  • Processes performing I/O are moved to I/O schedulers
  • I/O eventing managed via tokio (?) or some other library
  • Each scheduler has a maximum priority queue, high priority queue, and mixed normal/low priority queue; work is grabbed from maximum first, then high, then each pass over the normal/low queue increments a counter in each process, and after the counter reaches 3, a low priority task will be scheduled; each pass over the queue schedules normal tasks as usual
  • Each scheduler is work-stealing, meaning that when it is out of work to do, it will check each scheduler for work in its queues, grabbing the highest priority work first, and taking a minimum of half a queue; if a queue is too small, grab work from the next highest priority, then the next scheduler
  • Each scheduler has a dedicated allocator for non-global data (such as ETS), namely an allocator for processes, allocators for small and large types, and for binary data; which will be split into two heaps, a scheduler-local one for small binaries which are not stack-allocated, and a global one which is reference counted.

The compiler will be built under the assumption that the scheduler itself acts as a trampoline for the program (i.e. returning to the scheduler will require the scheduler to invoke the next continuation to resume execution of the program). To keep this simple, it is likely that I will implement the core trampoline in LLVM IR, and call into the scheduler to do its work, and expect it to return the next continuation to invoke so that the scheduler does not need to manage the trampoline itself, only pop a process of the run queue and return control to the trampoline.

Once the compiler is implemented, this will be the next step towards a full implementation of Erlang

Trace BIFs

  • trace/3
  • trace_delivered/1
  • trace_info/2
  • trace_pattern/2
  • trace_pattern/3

Implement WebAssembly backend

  • Tooling to generate browser bundle (everything needed to run in the browser) from compiled WASM module
  • Flesh out runtime support (via web-sys/js-sys)

Code Reloading BIFs

Lumen being Ahead-of-Time compiled will likely never support code reloading, but we may need to stub this out to at least return exceptions or errors with code that expects then to exist.

  • call_on_load_function/1
  • check_old_code/1
  • check_process_code/2
  • check_process_code/3
  • delete_module/1
  • finish_after_on_load/2
  • finish_loading/1
  • has_prepared_code_on_load/1
  • load_module/2
  • loaded/0
  • module_loaded/1
  • pre_loaded/0
  • prepare_loading/2
  • purge_module/1

Provide Elixir frontend

In order to have a way to compile a Mix project via Lumen in the near term, we are going to use a Mix task which compiles the Elixir source via BEAM, converts the compiled code to Erlang source using the Erlang compiler API, and places it in an incremental compilation directory under _build. This will then be fed to Lumen as the input for compilation to native code.

The code for this initial tooling is located at https://github.com/lumen/lumen_elixir, it is currently in a draft state.

In the long term, we will ultimately want the Lumen compiler to be bootstrapped with its own OTP standard library, with a compiler module that invokes the Lumen compiler infrastructure instead. This would then be used to build a version of the compiler that can build from Elixir source directly, without requiring the BEAM at all. Unfortunately there are a lot of technical challenges involved here, so we need to use the above workaround until we have time to dedicate to the bootstrapping process.

Programming Elixir Process Overhead Demo

@pragdave's Programming Elixir was the first Elixir book I read and I still use the Process Overhead demo with 1,000,000 processes to show off that new Elixir programmers shouldn't be worried about making Processes the way they would be with threads. Showing we can compile spawn/chain.ex and run it Chain.run(1_000_000) would be a good MVP target for us.

spawn/chain.ex

defmodule Chain do
  def counter(next_pid) do
    receive do
      n ->
        send next_pid, n + 1
    end
  end

  def create_processes(n) do
    last = Enum.reduce 1..n, self,
                       fn (_, send_to) ->
                         spawn(Chain, :counter, [send_to])
                       end

    send last, 0 # start the count by sending a zero to the last process

    receive do # and wait for the result to come back to us
      final_answer when is_integer(final_answer) ->
        "Result is #{inspect(final_answer)}"
    end
  end

  def run(n) do
    IO.puts inspect :timer.tc(Chain, :create_processes, [n])
  end
end

The book has the 1,000,000 processes run like this: elixir --erl "+P 1000000" -r chain.ex -e "Chain.run(1_000_000)".

RFC: Exposing WASM runtime to Erlang applications

This issue is for discussing how we can expose the Wasm runtime to Erlang applications.

The Wasm runtime is an extension of the core runtime with APIs which match the browser APIs, so things like alert, document.getElementById, etc. These APIs will be primarily generated via something like wasm-bindgen, and should ideally be callable from LLVM IR.

There are non-trivial issues to be sorted out here though:

  • Calling DOM APIs generally requires support for events/callbacks
  • Calling these APIs also requires us to convert Erlang terms to the types expected by the APIs

In particular, the handling of events/callbacks requires careful planning. In Wasm we are planning to dedicate the main thread "scheduler" as more of an event loop that yields back to the JS runtime like a typical JS application would, while the more traditional scheduler threads would run in one or more WebWorkers.

In order to call DOM APIs, it is then necessary for a process wishing to perform such a call, to dispatch a request to the main thread, which would then be suspended by its scheduler, while the main thread would then take responsibility for calling the API, yielding to the JS runtime, and then once the result is received, ensure that the process is woken up so that it can resume execution where it left off. I'm not yet sure whether or not we should try and mimic the continuation-passing style common to JS, or whether we should transparently convert these to await/async equivalents, where calling an API will appear to be blocking, but under the covers constructs a continuation which is then invoked with the result of the call once received.

Related to that, callbacks could then be implemented transparently, either as a continuation, or by constructing a closure which is called with the arguments given to the callback. The main thread will have a generic callback handler which will be the "real" function pointer passed to the JS API, so that it is invoked by the JS side when the callback is invoked. This handler will then construct the closure/continuation value for the origin process, which will be resumed using that value.

Events would more than likely work on a similar mechanism - a subscription would be set up by sending the request to the main thread, which would track the requesting PID, and as part of its event loop, would then dispatch any received events to subscribers by looking up the relevant PIDs and pushing messages onto their signal queue.

In short, the task list is basically these items:

  • Design/sketch out the mechanism by which callbacks will be handled
  • Design/sketch out the mechanism by which events will be handled
  • Design/sketch out the semantics of invoking DOM/browser APIs, using the design of the above two points to ensure we have a complete specification of how we interface with JS APIs.
  • Implement each of the above

Display BIFs

These are low-level output functions meant for debugging directly to STDIO without going through the group leader. We may not need to ever implement these.

  • display/1
  • display_nl/0
  • display_string/1

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.