Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Calculate the difference and intersection of any two regexes

phylactery.org

Post reply on HN
Print view View original

61–70 of 127 posts

Re: Calculate the difference and intersection of any two regexes

#61

Post by alexeldeib »

1-more wrote: post #58
oever wrote: post #40

This library can be used to create string class hierarchies. That, in turn, can help to use typed strings more. For example, e-mails and urls are a special syntax. Their value space is a subset of all non-empty string which is a subset of all strings. An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty…

In languages with tagged union types you do this a lot! Some Haskell pseudocode for ya module Email (Address, fromText, toText) where -- note we do not export the constructor of Address, just the type data Address = Address Text fromString :: Text -> Maybe Address fromString = -- you'd do your validation in here and return Nothing if it's a bad address. -- Signal validity out of band, not in band with the data. toTex…

> Signal validity out of band, not in band with the data.

Could you expand on this?

Re: Calculate the difference and intersection of any two regexes

#62

Post by rntz »

noduerme wrote: post #57
d66 wrote: post #46

Earlier quoted context omitted.

expressions like (...){1,256} are very heavyweight and the scala JS code ends up timing out or crashing the browser. if you replace that with (...)+ then it seems to work (at least for me). smaller expressions like (...){1,6} should be fine.

Just wondering, what is it about testing repetition [a-z]{1,256} with an upper bound that's so heavy? Intuitively it feels like greedy testing [a-z]+ should actually be worse since it has to work back from the end of the input.

This depends heavily on how repetition is implemented.

With a backtracking-search implementation of regexes, bounded iteration is pretty easy.

But the linked webpage appears to compile regexes to finite state machines (it shows you their finite-state-machine, for instance), and eg [a-z]{1,256} will have 256 states: 256 times the 1 state needed for [a-z]. If [a-z] were a complex regex, you could get a combinatorial explosion.

This alone probably isn't the issue? 256 is not a very large number. But I suspect there are follow-on algorithmic issues. This is just speculation, but I wouldn't be surprised if that 256-state machine were computed by applying DFA minimization, an algorithm with worst-case exponential running time, to a more naively generated machine.

Re: Calculate the difference and intersection of any two regexes

#63

Post by _a_a_a_ »

oever wrote: post #40

This library can be used to create string class hierarchies. That, in turn, can help to use typed strings more. For example, e-mails and urls are a special syntax. Their value space is a subset of all non-empty string which is a subset of all strings. An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty…

> Their value space...

wossis mean? TIA

Edit: instread of downvoting try answering. I'd like to know. TIA{2}

Re: Calculate the difference and intersection of any two regexes

#64

Post by d66 »

rntz wrote: post #62
noduerme wrote: post #57

Earlier quoted context omitted.

Just wondering, what is it about testing repetition [a-z]{1,256} with an upper bound that's so heavy? Intuitively it feels like greedy testing [a-z]+ should actually be worse since it has to work back from the end of the input.

This depends heavily on how repetition is implemented. With a backtracking-search implementation of regexes, bounded iteration is pretty easy. But the linked webpage appears to compile regexes to finite state machines (it shows you their finite-state-machine, for instance), and eg [a-z]{1,256} will have 256 states: 256 times the 1 state needed for [a-z]. If [a-z] were a complex regex, you could get a combinatorial ex…

you're right. inclusion/intersection/etc. aren't actually computed via DFA but instead are computed directly on the regular expression representation itself. and large disjunctions (with 256 branches) are what is very heavy.

(it's possible to instead do these operations on DFAs but at the time i found it hard to get from an automata back to a reasonable-looking regular expression.)

Re: Calculate the difference and intersection of any two regexes

#65

Post by _a_a_a_ »

Any def for 'difference and intersection of regexes' might actually mean?

I guess for regexes r1 and r2 this means the diff and intersect of their extensional sets, expressed intensionally as a regex. I guess. But nothing seems defined, including what ^ is, or > or whatever. It's not helpful

Re: Calculate the difference and intersection of any two regexes

#66

Post by haltist »

vore wrote: post #54
haltist wrote: post #52

Can LLMs do this?

I wouldn't use an LLM for anything that can be done 100% precisely, like this.

OK, just curious how LLMs are stacking up in logical tasks like this. I kept hearing we were close to AGI so just wondering how far there is to go.

Re: Calculate the difference and intersection of any two regexes

#67

Post by [deleted] »

vintermann wrote: post #4
posco wrote: post #2

The amazing page computes binary relations between pairs of regular expressions and shows a graphical representation of the DFA. It’s a really incredible demonstration of some highly non-trivial operations on regular expressions.

It's very cool, but also no wonder that it doesn't support all those features of regexes which technically make them not regular expressions anymore. Though, I would have thought ^ and $ anchors shouldn't be a problem?

[deleted]

Re: Calculate the difference and intersection of any two regexes

#68

Post by oever »

_a_a_a_ wrote: post #63
oever wrote: post #40

This library can be used to create string class hierarchies. That, in turn, can help to use typed strings more. For example, e-mails and urls are a special syntax. Their value space is a subset of all non-empty string which is a subset of all strings. An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty…

> Their value space... wossis mean? TIA Edit: instread of downvoting try answering. I'd like to know. TIA{2}

Value space is the set of values a type can have. A boolean has only two values in its value space. An unsigned byte has 256 possible values, so does a signed byte.

A string enumeration has a limited number of values. E.g. type A ("Yes" | "No" | "Maybe") has three values and is a superset of type B ("Yes" | "No"). A function that accepts type A can also accept type B as valid input.

If the value space is defined by a regular expression, as is often the case, the mentioned library could be used to check, at compile-time, which type are subsets of others.

Re: Calculate the difference and intersection of any two regexes

#69

Post by 1-more »

alexeldeib wrote: post #61
1-more wrote: post #58

Earlier quoted context omitted.

In languages with tagged union types you do this a lot! Some Haskell pseudocode for ya module Email (Address, fromText, toText) where -- note we do not export the constructor of Address, just the type data Address = Address Text fromString :: Text -> Maybe Address fromString = -- you'd do your validation in here and return Nothing if it's a bad address. -- Signal validity out of band, not in band with the data. toTex…

> Signal validity out of band, not in band with the data. Could you expand on this?

Sure! Sorry that was a little too obtuse. So in this case we can imagine an app where we don't use any tagged unions and just use primitive types (your strings, booleans, integers, things of that nature). And we want to signal the validity of some data. Say a user ID and an email address. We store the User ID as an integer to keep space down and store the email address as a string. We use semaphore values: if the user ID is invalid we store -1 (it's JS and there are no unsigned numbers) and if the email address is invalid we store the empty string.

Whenever we consume these values, we need to make sure that userId > 0 and email != "" I mean email !== "". We are testing for special values of the data. Data and "this is for sure not meaningful data" are the same shape! So your functions need to handle those cases.

But with tagged unions you can check these things at the edge of the program and thereafter accept that the contents of the tagged data are valid (because you wrote good tests for your decoders).

So your data is a different shape when it's valid vs when it's invalid, and you can write functions that only accept data that's the valid shape. If you got Json that was hit by cosmic rays when trying to build your User model, you can fail right then and not build a model and find a way to handle that.

It's out of band because you don't guard for special values of your morphologically identical data.

If you want examples of any specific part of this let me know. IDK your level of familiarity and don't want to overburden you with things you already get.

Re: Calculate the difference and intersection of any two regexes

#70

Post by _a_a_a_ »

oever wrote: post #68
_a_a_a_ wrote: post #63

Earlier quoted context omitted.

> Their value space... wossis mean? TIA Edit: instread of downvoting try answering. I'd like to know. TIA{2}

Value space is the set of values a type can have. A boolean has only two values in its value space. An unsigned byte has 256 possible values, so does a signed byte. A string enumeration has a limited number of values. E.g. type A ("Yes" | "No" | "Maybe") has three values and is a superset of type B ("Yes" | "No"). A function that accepts type A can also accept type B as valid input. If the value space is defined by a…

Thank you. I guess I misread.

"For example, e-mails and urls are a special syntax. Their value space..." seemed to talk about the 'value space' of strings (these being e-mails and urls), not types (of e-mails and urls), which confused me.

Post reply on HN