davdar

I'm curious, what do you mean they compose better and allow for analysis [better than monads]?

That's like saying "your program is more elegant if it has no monads". It's an incorrect statement. The monadic version is perfectly elegant. Even better: it's the right one.

In the non-continuous FRP literature[1], i.e. the kind you actually implement, SF a b = [a] -> [b], which is isomorphic to: Fold a -> Fold b, where Fold a = (exists s. (s, s -> (a, s))), which isomorphic to the type the author writes for transducer:

  ;;transducer signature
  (whatever, input -> whatever) -> (whatever, input -> whatever)

[1]: Nilsson, Courtney and Peterson. Functional Reactive Programming, Continued. Haskell '02. http://haskell.cs.yale.edu/wp-content/uploads/2011/02/worksh... (see section 4)

edit: formatting

Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.

Yes, breadth first traversal of the solution space is very similar in spirit to our approach.

I have since completely rewritten the Haskell implementation. You should really check it out, especially if you are thinking about writing one of your own.

(git repo) http://david.darais.com/git/research/der-parser-3

This implementation no longer requires a special coded repetition operator to get good complexity for regular and LL(k) grammars. This is a result of our progress w.r.t. performance of the theory since the paper's submission. My technique to achieve this uses structure derivatives (context based derivatives, or pseudo-equivalently, continuations) to avoid taking unnecessary parser derivatives. It in a sense "focuses" the parser computation on a small sub-parser.

Ping me if you have any questions; this paper has been getting passed around quite a bit lately and Matt and I have made progress on certain areas since the writing of the paper -- like that of the Rep hack.

Here is my latest Haskell implementation that Matt is referring to (git repo):

http://david.darais.com/git/research/der-parser-3/

I have since rewritten the Haskell implementation to compute fixed points on cyclic graphs without using pointers or Monads. Check it out if it interests you (git repo):

http://david.darais.com/git/research/der-parser-3/

Here is the git repo (over http) for my Haskell implementation which exploits the technique to be linear for LL(k) (the Zip module is where this technique is implemented). The constant overhead for the implementation is still extremely high because we need to compute a fixed point computation on the whole parse graph for every input token. I'm working on getting all that down...

http://david.darais.com/git/research/der-parser-3/