davdar
Joined 16 years ago
Karma
13
Submissions
11
Member since
Nov 2
Recent submissions
Comment · 11 years ago
I'm curious, what do you mean they compose better and allow for analysis [better than monads]?
Comment · 12 years ago
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.
Comment · 12 years ago
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
Comment · 12 years ago
Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.
Comment · 16 years ago
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.
Comment · 16 years ago
Here is my latest Haskell implementation that Matt is referring to (git repo):
Comment · 16 years ago
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):
Comment · 16 years ago
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...
david.darais.com