On Wed, Sep 21, 2011 at 20:05, Edward Kmett ekm...@gmail.com wrote:
I usually enforce constraints like this with ! patterns in the
constructors, which lets me enforce the fact that at least I know that any
attempt to define a cycle like this will bottom out, so I can safely think
only
On 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
* 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
* 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
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
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
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
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
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
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.
On Sat, 2011-09-17 at 22:11 -0400, Anton Tayanovskyy 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
If you are worried about Denial Of Service attacks then you are worried about
(1) memory explosion, and (2) long runtime. Long runtime can and should be
solved by running a timeout connected to a thread killer, not at the level of
the regular expression engine. The memory explosion is more
* Eugene Kirpichov ekirpic...@gmail.com [2011-09-14 08:38:10+0400]
Hi,
I don't see how fallback to NFA simulation is really a failure wrt DoS
attacks. It's not exponential in time or memory, just linear memory
(in size of regex) instead of constant, and slower than DFA.
Hi Eugene, thanks for
I wrote regex-tdfa, the efficient (though not yet lightning fast) Posix-like
engine.
You are not the first to want an efficient Perl-like engine. The answer you
seek flows from Russ Cox (though in C++):
http://google-opensource.blogspot.com/2010/03/re2-principled-approach-to-regular.html
* Chris Kuklewicz hask...@list.mightyreason.com [2011-09-13 08:21:55+0100]
I wrote regex-tdfa, the efficient (though not yet lightning fast) Posix-like
engine.
You are not the first to want an efficient Perl-like engine. The answer you
seek flows from Russ Cox (though in C++):
* Roman Cheplyaka r...@ro-che.info [2011-09-14 00:29:55+0300]
Then there's another issue: I specifically want a combinator library,
and not every automaton-based algorithm can serve this purpose in a
statically typed language (unless there's some clever trick I don't
know).
Just to clarify:
Hi,
I don't see how fallback to NFA simulation is really a failure wrt DoS
attacks. It's not exponential in time or memory, just linear memory
(in size of regex) instead of constant, and slower than DFA.
On Wed, Sep 14, 2011 at 1:29 AM, Roman Cheplyaka r...@ro-che.info wrote:
* Chris Kuklewicz
Please help make the regex-based parsing library efficient!
https://github.com/feuerbach/regex-applicative/wiki/Call-For-Help
--
Roman I. Cheplyaka :: http://ro-che.info/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
18 matches
Mail list logo
