Packrat Parser combinators for haXe.

Hi!

Last time I presented you Monax (http://lambdabrella.blogspot.com/2012/01/monax-crossplatform-monads-via-haxe.html), a compiler macro that brings monadic syntactic sugar (ala haskell) to haXe and enables defining your own monads (and hooks to optimize their compositions).

I said I had several other projects waiting to be released.

So I'm proud to release now Parsex, a parser combinator which started as a side project effort to ease working with external DSLs and to which I've decided to bring some additional love by making it a packrat parser (this is largely motivated by the awesome packrat parsers which are part of the awesome Scala language libraries).

You may found some information about packrat parsers here:
http://bford.info/packrat/

The important aspect of it is that a packrat parsers memoize their results in a context (based on parsing position), lowering backtracking cost *a lot*.

Thanks to this memoization, there's no more real need to separate the lexer and the parser (it's usually the case only for performance reasons).

We're also able to detect left recursive grammars and handle them properly.

This is at the time of writting, the first general purpose Parser API in haXeland.


Here's an exmaple from the test to parse a Json array:


Combinatorial style:

static var jsonArrayP =   leftBracketP._and(jsonValueP.repsep(commaP).and_(rightBracketP)).then(JsArray);

Monadic style (using monax and which perform slighty faster):

static var jsonArrayP =
  ParserM.dO({
    leftBracketP; // Parses '['
    jsons <= jsonValueP.repsep(commaP); // Parses json values separated by some commas
    rightBracketP; // Parses ']'
    ret(JsArray(jsons)); // returns the result wrapped in a JSArray enum (case classes in Scala)
  });

I'll not enter into the details as it speaks for itself.

Speed wise, it's not as fast as hand written parser; the additional cost may be aleviated with future versions of haXe with better expression generation (JS) and more inlining control.

But I think it's the fastest path for developpement speed.

Available on my github: https://github.com/sledorze/Parsex

and released on haxelib (the haXe libraries repository): http://lib.haxe.org/p/Parsex

Enjoy!

Monax - crossplatform Monads via haXe.

Monax

Motivation

If, like me, you code on NodeJs; you may find it is easy to make spaghetti code. Even properly written, a library smell too much..

Another problem is how to make sure you did not forgot a use case while writting your code.. ?
It would be nice to have a rock solid safe code composition capability; requiering less test code.

Every seasonned statically typed functionnal programmer will tell you to build up an abstraction for that and I'm pretty sure they mean Monads!
I really invite you to read more about them.

Now, that's a good idea but not all languages provides the so usefull syntactic sugar that make Monads really very clean to read / write.

I've missed too much Monads in haXe so I've decided to unleash macro capabilities to get them working - now, it is here, for your pleasure:

Monax on gitHub!

Introducing the Monax macro library

This library, built on top of haXe macros give the user the possibility to define specific Monad instance and get automatically access to a haskell like sugared syntax.
About monad: Monads on Wikipedia

The syntactic sugar rely on the existence 'ret' and 'flatMap' in the Monad instance.
It also requiers the existence of 'map' to provide automatic optimisations.

Learn the (not so) hard way - Defining a Monad instance.

class OptionM {
    
  @:macro public static function dO(body : Expr) return // the function to trigger the Monad macro.
    Monad.dO("OptionM", body, Context)

  inline public static function ret(x : T) return // creates an element
    Some(x)
  
  inline public static function map < T, U > (x : Option, f : T -> U) : Option {
    switch (x) {
      case Some(x) : return Some(f(x));
      default : return None;
    }
  }

  inline public static function flatMap(x : Option, f : T -> Option) : Option {
    switch (x) {
      case Some(x) : return f(x);
      default : return None;
    }
  }
}

Using a Monad instance (Option here)

OptionM.dO({
          value <= ret(55);
          value1 <= ret(value * 2);
          ret(value1 + value);
        });

Due to optimisations; this code reduce to Some(165), those optimisations are applied by default.
One can define his own optimisations (feeding the Monad.dO method its last parameter)

@:macro public static function dO(body : Expr) return
    Monad.dO("OptionM", body, Context, myCustomTransformation)

(please refer to the default function code to make sense of how to make optimization - macro knowledge requiered).

or using no optimisation at all:

@:macro public static function dO(body : Expr) return
    Monad.dO("OptionM", body, Context, Monad.noOpt)

Next..

Now I've this up and running; I plan to release a packrat parser combinator which is waiting on my github - accompagnied with his own Monad instance.

Later, I'll also release some abstractions for NodeJs.