davdar

vor 11 Jahrendiscuss

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

vor 12 Jahrendiscuss

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.

davdar

vor 12 Jahrendiscuss

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)

Signal functions are easy to program in Haskell using arrow syntax, and many libraries already exist for dealing with signal functions.

[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

davdar

vor 12 Jahrendiscuss

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

davdar

vor 16 Jahrendiscuss

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.

davdar

vor 16 Jahrendiscuss

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

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

davdar

vor 16 Jahrendiscuss

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/

davdar

vor 16 Jahrendiscuss

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/

Submissions

Automatic Proofs of Differential Privacy

Differentially Private Synthetic Data

comments