Re: [Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)
* Anton Tayanovskyy anton.tayanovs...@gmail.com [2011-09-17 21:46:57-0400]
So you want to encode priorities efficiently as far as I understand
from [1]? Could bit-packing combined with prefix elimination do the
trick? Choice boils down to binary choice. Attach a number N to every
execution thread that sits in a given NFA state. When the thread moves
through a binary choice state, it splits into two threads with
N_{left} = 2 * N + 1 and N_{right} = 2 * N. When two threads arrive at
the same NFA state, the machine picks one with greater N and discards
the other, thus giving priority to early over late and left over
right. This makes these numbers grow quickly, but at any point in the
simulation one can identify the common binary prefix of all the thread
numbers and remove it, because it will not be relevant for comparison.
If this is too costly, amortize and do it every K steps instead of on
every step.
Anton
[1] https://github.com/feuerbach/regex-applicative/wiki/Call-For-Help
Just common prefix elimination is not sufficient to put a hard bound on
the memory usage. For example, something like /(a*)|((aa)*)/ would still
require an amount of space linear in the string length (if the string
consists of many a's).
More clever techniques that I tried (monotonically map lists to
smaller lists) are hard to make correct.
I like the approach of Russ Cox[2]. One of the great ideas there (which I
think he didn't emphasize enough) is to have a queue which allows O(1)
testing whether an element is already there [3]. This solves the problem
with priorities -- the states are guaranteed to be enqueued in the order
of their priorities, and there are no repetitions.
To be able to process the states in the proper order I'll have to give
up Glushkov automaton and probably use something similar to your
construction [4].
[2] http://swtch.com/~rsc/regexp/regexp2.html
[3] http://code.google.com/p/re2/source/browse/util/sparse_array.h
[4] http://t0yv0.blogspot.com/2011/07/combinatory-regular-expressions-in.html
--
Roman I. Cheplyaka :: http://ro-che.info/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)
* Anton Tayanovskyy anton.tayanovs...@gmail.com [2011-09-17 22:11:00-0400] By the way, can Haskell have a type that admits regular expression and only those? I mostly do ML these days, so trying to write up a regex types in Haskell I was unpleasantly surprised to discover that there are all sorts of exotic terms inhabiting it, which I did not have to worry about in ML. Besides `undefined` you can have for terms that try to define a grammar with nested parentheses. Using regex-applicative syntax: expr = ... | pure (\ _ x _ - x) * sym ( * expr * sym ) Is this the so-called 'paucity of types' [1]? What do you do, as a library designer? Return bottom or try to detect and error out for these kind of values? Thanks, A [1] http://existentialtype.wordpress.com/tag/recursion/ Essentially, this is an infinite regular expression. I think it'd be possible to enforce this on the type level. (There was a thread here some time ago about a type of finite lists.) If a library can work with such infinite trees, and the user is happy with resulting performance, then, why not. For example, this is the case with weighted-regexp library, and also with the first (and buggy) version of regex-applicative [2]. Otherwise, just let the user know that this function doesn't work with infinite data structures. Note that in the presence of referential transparency (i.e. without StableNames or similar tools) it is not possible to decide at runtime if a value is circular or not. [2] https://github.com/feuerbach/regex-applicative/commit/95ddfbbfb01c47e292dc7f03069eefe8907f -- Roman I. Cheplyaka :: http://ro-che.info/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)
Chris,
Thank you for an interesting overview.
However, I'm not worried directly about DoS. I just want to build a
regex library which would be convenient to use for parsing regular
languages (by providing applicative interface and Perl semantics), and
not worse than alternatives performance-wise (including worst-case time
and space complexity).
(3) Building an NFA from your regular expression can be cheap, but you would
have be more clever than expanding a(b{2,99}c){100}d to have 100 copies of
99
copies of b.
Are there any known algorithms more clever than that?
--
Roman I. Cheplyaka :: http://ro-che.info/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)
On Sat, Sep 17, 2011 at 22:11, Anton Tayanovskyy anton.tayanovs...@gmail.com wrote: By the way, can Haskell have a type that admits regular expression and only those? I mostly do ML these days, so trying to write up a regex types in Haskell I was unpleasantly surprised to discover that there are all sorts of exotic terms inhabiting it, which I did not have to worry about in ML. Besides `undefined` you can have for terms that try to define a grammar with nested parentheses. Using regex-applicative syntax: expr = ... | pure (\ _ x _ - x) * sym ( * expr * sym ) The general case for this is solving the Halting Problem, so neither Haskell nor any other language can do it. You can disallow infinite values by encoding the length into the type, but (a) in Haskell this is painful and (b) runtime values now require runtime types, which you can accommodate but at the price of reintroducing the problems you are trying to prevent. (Dependently typed languages work better for this, but I suspect the result is rather more draconian than you intend.) -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: usb-1.0, bindings-libusb-1.4.4 and usb-iteratee-0.4
Fellow Haskellers, I would like to announce the 1.0 release of the usb library! This library lets you to communicate with USB devices from userspace. It is implemented as a high-level wrapper around bindings-libusb[1] which is a low-level binding to the portable C library: libusb-1.0 ( http://libusb.org ). I think a 1.0 release is warranted since I have been successfully using the library in an industrial application at Sensor Sense for some time now. This release also adds the last piece of functionality that was missing from previous releases: isochronous transfers. These let you communicate with USB video or audio devices for example. A second major change is that all I/O functions, while still having a synchronous interface (they block), are now implemented asynchronously. This makes them more efficient (no busy-loops) and interruptible (just throw an asynchronous exception to the thread executing a transfer and the transfer is automatically canceled). The implementation uses the GHC event manager for event handling. If the event manager is not available, because you're either: not using GHC, building your program without -threaded or you're on Windows the implementation degrades gracefully to the synchronous implementation. Other changes: * Added writeControlExact :: DeviceHandle - ControlAction WriteExactAction. * All I/O functions which previously returned the boolean TimedOut now return a: data Status = Completed | TimedOut. * Added the timeout constant: noTimeout :: Timeout. * Added function: maxIsoPacketSize :: EndpointDesc - Size Which calculates the maximum packet size which a specific endpoint is capable of sending or receiving in the duration of 1 microframe. This function is mainly useful for setting up isochronous transfers. * Added some specific IOExceptions: ioException :: USBException incompleteReadException :: USBException incompleteWriteException :: USBException * Renamed System.USB.IO.Synchronous to just System.USB.IO. * Renamed System.USB.Unsafe to System.USB.Internal and exported more functions from it which are primarily needed in the usb-iteratee package. * Fixed some bugs. * Switched from darcs to git and hosted the project on github: https://github.com/basvandijk/usb/ API Docs: http://hackage.haskell.org/package/usb-1.0 Installing: $ cabal update $ cabal install usb I would like to thank John Obbele for pushing me to write the asynchronous implementation and for testing the library. Also thanks to Joris Putcuyps for testing the library on Windows. Unfortunately the library doesn't yet work on that platform due to a weird segmentation fault: http://hackage.haskell.org/trac/ghc/ticket/5254. Hopefully we will solve it in the near future. bindings-libusb === The usb library is based on bindings-libusb which is a low-level binding to the libusb C library. I recently took over maintenance of this package from Maurício Antunes. Maurício, thanks for creating and maintaining this package! It greatly simplified the task of writing the high-level wrapper. API Docs: http://hackage.haskell.org/package/bindings-libusb-1.4.4 usb-iteratee I also released a new library: usb-iteratee which provides iteratee enumerators for the usb package. Note that this package was previously called usb-enumerator. However I'm planning to rewrite the latter to offer enumerators for the enumerator package instead. API Docs: http://hackage.haskell.org/package/usb-iteratee-0.4 Regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Function code generation (Template Haskell).
The task is that I have some function and I need to create another function alongside with it. The second function is based on first one. As a matter of fact, I already did this with Template Haskell. TH is quite good at that task, because I can load my module in ghci and have both functions available for experiments. I just wondering, is it possible to use newly introduced ghc plugins to do something like that? Could I create new functions while inspecting defined ones? Will they be visible in ghci? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Enumeratees are killing me
I am waiting for a web service where I can enter the type I want to process, the iterator package to use, and which will spit out the types and an example. Then life will be good. Alexander On 16 September 2011 22:46, tsuraan tsur...@gmail.com wrote: Well, I got it working. It seems to behave sanely when put in a chain with other Enumeratee/Iteratee combinations, so I'm happy. My solution is posted on hpaste: http://hpaste.org/51430 . I'd love any criticism that anybody has, especially since it seems to me to be an ideal building block for the sorts of Enumeratees that I'm building. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)
I like the approach of Russ Cox[2]. One of the great ideas there (which I think he didn't emphasize enough) is to have a queue which allows O(1) testing whether an element is already there [3]. This solves the problem with priorities -- the states are guaranteed to be enqueued in the order of their priorities, and there are no repetitions. Hm, this sounds great! So then the number of states is just the size of the NFA, so the memory does not depend on the input string length? Have you tried this approach yet? I wouldn't vouch for my code in that gist, I kind of remember trying to eliminate the duplicates while preserving order buy not sure if I did it correctly there. To be able to process the states in the proper order I'll have to give up Glushkov automaton and probably use something similar to your construction [4]. [2] http://swtch.com/~rsc/regexp/regexp2.html [3] http://code.google.com/p/re2/source/browse/util/sparse_array.h [4] http://t0yv0.blogspot.com/2011/07/combinatory-regular-expressions-in.html -- Roman I. Cheplyaka :: http://ro-che.info/ -- Kind Regards, Anton Tayanovskyy WebSharper™ - type-safe JavaScript in F# http://intellifactory.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)
Chris, Brandon, thank you for the input. I believe I understand what you are saying; to reiterate, yes, in the *general case*, neither ML nor Haskell types outrule nastiness such as non-termination. Yes I know about and use Coq a bit. However, ML has an important *special case*: not using functions. Chris, using bang patterns in Haskell do not quite help to statically rule out recursive terms, do they? They just make for a different runtime error. If I said: data Regex = ... | Seq !Regex !Regex Will it actually give the user who tries to construct a recursive value a compile-time error? I suspect not, I'll try it myself to make sure. Roman, thanks, I will try to look that thread up - this is what I am indeed curious about - how to enforce this at the type level. Yes, with a vanilla interface sharing is not observable; some libraries work with it and some do not. I am spooked out by this though: performance guarantees are very different for regular terms and terms with sharing. Consider the regex engine. The infinite regular expressions (well, they are not really regular), may suddenly produce an infinte NFA, so memory use may become linear in the input string. Yes, a smart user will understand this, especially in an area that is relatively well-understood such as regular expressions. However I find it extremely disturbing that library designers do not communicate requirements through the type system, and make performance guarantees for all well-typed programs. ML makes it easy, I guess I am just an ML convert :) Thanks, Anton On Sun, Sep 18, 2011 at 11:28 AM, Brandon Allbery allber...@gmail.com wrote: On Sat, Sep 17, 2011 at 22:11, Anton Tayanovskyy anton.tayanovs...@gmail.com wrote: By the way, can Haskell have a type that admits regular expression and only those? I mostly do ML these days, so trying to write up a regex types in Haskell I was unpleasantly surprised to discover that there are all sorts of exotic terms inhabiting it, which I did not have to worry about in ML. Besides `undefined` you can have for terms that try to define a grammar with nested parentheses. Using regex-applicative syntax: expr = ... | pure (\ _ x _ - x) * sym ( * expr * sym ) The general case for this is solving the Halting Problem, so neither Haskell nor any other language can do it. You can disallow infinite values by encoding the length into the type, but (a) in Haskell this is painful and (b) runtime values now require runtime types, which you can accommodate but at the price of reintroducing the problems you are trying to prevent. (Dependently typed languages work better for this, but I suspect the result is rather more draconian than you intend.) -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms -- Kind Regards, Anton Tayanovskyy WebSharper™ - type-safe JavaScript in F# http://intellifactory.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
