dummy-link

MLStyle

ML language infrastructures in Julia that provide (generalized) algebraic data types abstraction, highly optimized and extensible pattern matching, and killer tools for meta-programming.

Readme

MLStyle.jl

Build Status codecov License Docs Join the chat at https://gitter.im/MLStyle-jl/community

Index

What is MLStyle.jl?

MLStyle.jl is a Julia package that provides multiple productivity tools from ML (Meta Language) like pattern matching which is statically generated and extensible, ADTs/GADTs (Algebraic Data Type, Generalized Algebraic Data Type) and Active Patterns.

Think of MLStyle.jl as a package bringing advanced functional programming idioms to Julia.

Motivation

Those used to functional programming may feel limited when they don't have pattern matching and ADTs, and of course I'm one of them.

However, I don't want to make a trade-off here by using some available alternatives that miss features or are not well-optimized. Just like why those greedy people created Julia, I'm also so greedy that I want to integrate all those useful features into one language, and make all of them convenient, efficient and extensible.

On the other side, in recent years I was addicted to extending Python with metaprogramming and even internal mechanisms. Although I made something interesting like pattern-matching, goto, ADTs, constexpr, macros, etc., most of these implementations are also disgustingly evil. Fortunately, in Julia, all of them could be achieved straightforwardly without any black magic, at last, some of these ideas come into existence with MLStyle.jl.

Finally, we have such a library that provides extensible pattern matching for such an efficient language.

Why use MLStyle.jl

  • Straightforward

    I think there is no need to talk about why we should use pattern matching instead of manually writing something like conditional branches and nested visitors for datatypes.

  • Performance Gain

    When dealing with complex conditional logics and visiting nested datatypes, the codes compiled via MLStyle.jl is usually as fast as handwritten code. You can check the benchmarks for details.

  • Extensibility and Hygienic Scoping

    You can define your own patterns via the interfaces def_pattern, def_app_pattern and def_gapp_pattern. Almost all built-in patterns are defined at Pervasives.jl.

    Once you define a pattern, you're tasked with giving some qualifiers to your own patterns to prevent visiting them from unexpected modules.

  • You can use MLStyle in development via Bootstrap mechanism:

    Now there's a code generation tool called bootstrap available at MLStyle/bootstrap, which you can take advantage of to remove MLStyle dependency when making distributions.

    Also, MLStyle is implemented by itself now, via the bootstrap method.

  • * Modern Ways about AST Manipulations

    MLStyle.jl is not a superset of MacroToos.jl, but it provides something useful for AST manipulations. Furthermore, in terms of extracting sub-structures from a given AST, using expr patterns and AST patterns could speed code up by orders of magnitude.

Installation, Documentations and Tutorials

Rich features are provided by MLStyle.jl and you can check the documentation to get started.

For installation, open the package manager mode in the Julia REPL and add MLStyle.

For more examples or tutorials, see this project which will be frequently updated to present some interesting uses of MLStyle.jl.

Preview

Rock Paper Scissors

Here's a trivial example of MLStyle.jl in action:

using MLStyle
@data Shape begin # Define an algebraic data type Shape
    Rock()
    Paper()
    Scissors()
end

# Determine who wins a game of rock paper scissors with pattern matching
play(a::Shape, b::Shape) = @match (a,b) begin
    (Paper(), Rock())     => "Paper Wins!";
    (Rock(), Scissors())  => "Rock Wins!";
    (Scissors(), Paper()) => "Scissors Wins!";
    (a, b)                => a == b ? "Tie!" : play(b, a)
end

Homoiconic pattern matching for Julia ASTs

Here's a less trivial use of MLStyle.jl for deconstructing and pattern matching Julia code.

rmlines = @λ begin
    e :: Expr           -> Expr(e.head, filter(x -> x !== nothing, map(rmlines, e.args))...)
      :: LineNumberNode -> nothing
    a                   -> a
end
expr = quote
    struct S{T}
        a :: Int
        b :: T
    end
end |> rmlines

@match expr begin
    quote
        struct $name{$tvar}
            $f1 :: $t1
            $f2 :: $t2
        end
    end =>
    quote
        struct $name{$tvar}
            $f1 :: $t1
            $f2 :: $t2
        end
    end |> rmlines == expr
end

Generalized Algebraic Data Types

@use GADT

@data public Exp{T} begin
    Sym{A}    :: Symbol                        => Exp{A}
    Val{A}    :: A                             => Exp{A}
    App{A, B, A_} :: (Exp{Fun{A, B}}, Exp{A_}) => Exp{B}
    Lam{A, B} :: (Symbol, Exp{B})              => Exp{Fun{A, B}}
    If{A}     :: (Exp{Bool}, Exp{A}, Exp{A})   => Exp{A}
end

A simple interpreter implemented via GADTs could be found at test/untyped_lam.jl.

Active Patterns

Currently, MLStyle does not have fully featured active patterns, but the subset of parametric active patterns that are implemented are very powerful.

@active Re{r :: Regex}(x) begin
    match(r, x)
end

@match "123" begin
    Re{r"\d+"}(x) => x
    _ => @error ""
end # RegexMatch("123")

Benchmark

Prerequisite

Recent benchmarks have been run, showing that MLStyle.jl can be extremely fast for complicated pattern matching, but due to its advanced machinery has noticeable overhead in some very simple cases such as straightforwardly destructuring shallow tuples, arrays and datatypes without recursive invocations.

All benchmark scripts are provided in the directory Matrix-Benchmark.

To run these cross-implementation benchmarks, some extra dependencies should be installed:

  • (v1.1) pkg> add https://github.com/thautwarm/Benchmarkplotting.jl#master for making cross-implementation benchmark methods and plotting.

  • (v1.1) pkg> add Gadfly MacroTools Match BenchmarkTools StatsBase Statistics ArgParse DataFrames.

  • (v1.1) pkg> add MLStyle#base for a specific version of MLStyle.jl is required.

After installing dependencies, you can directly benchmark them with julia matrix_benchmark.jl hw-tuple hw-array match macrotools match-datatype in the root directory.

The benchmarks presented here are made by Julia v1.1 on Fedora 28. For reports made on Win10, check stats/windows/ directory.

Visualization

Time Overhead

On the x-axis, after the name of test-case is the least time-consuming run's index in units of ns.

The y-label is the ratio of the implementation's time cost to that of the least time-consuming.

Allocation

On the x-axis, after the name of test-case is the least allocated one's index, the unit is _ -> (_ + 1) bytes).

The y-label is the ratio of the implementation's allocation cost to that of the least allocated.

Gallery

The benchmark results in dataframe format are available at this directory.

There are still some performance issues with array patterns.

  1. Time

hw-array

  1. Allocation

hw-array

  1. Time

hw-tuple

  1. Allocation

hw-tuple

  1. Time

macrotools

  1. Allocation

macrotools

  1. Time

match.jl

  1. Allocation

match.jl

  1. Time

match.jl

  1. Allocation

match.jl

Contributing to MLStyle

Thanks to all individuals referred in Acknowledgements!

Feel free to ask questions about usage, development or extensions about MLStyle at Gitter Room.

First Commit

08/12/2018

Last Touched

10 days ago

Commits

290 commits

Requires:

Used By: