ogogmad

How are people finding Fil-C? It's designed to avoid things like this.

What if people become increasingly dependent on their government’s spending beyond its means - so that they suffer more harm once the deficit is reduced than had it never been raised in the first place - making it impossible to rein in the deficit when borrowing costs rise and the debt is high?

They are controversial because supporting them raises matching time to O(2^n) in the worst case - which is dangerous - while not supporting them enables matching time to be O(n) in the worst case. And a user might not be aware of that danger.

Also, I think it's misleading to mention NFAs and DFAs alone, like there's no deeper reason. The deeper reason is that:

  Regexes (or NFAs, or DFAs) classify exactly the properties of strings which can be checked in constant space.

It turns out that any such string property can also be checked in O(n) time, and in one single left-to-right pass.

Briefly returning to backreferences, supporting them makes constant space unachievable. They also make linear time unachievable, since matching them becomes NP-COMPLETE.

Also, no regex implementation actually uses DFAs. NFAs yes, but DFAs no. The point of NFAs is that they're easy to execute in constant space and linear time, while also making concatenation and Kleene star easy to implement. It seems much harder to implement concatenation and Kleene star using most other constant-space automata - like DFAs - which is what actually forced people to invent NFAs.

I think some languages do have a library-style version of regex. But the function names aren't consistent between the different libraries. Maybe then we need to put on special goggles to make them look the same.

Backreferencing inside of a regex (which is a way to find repeat occurrences of a substring) is a very controversial feature that some regex engines intentionally omit, while most others support it only grudgingly. Supporting backreferences opens up a big can of worms: Most regex engines will fall back to a slow, poorly optimised algorithm if they ever encounter backreferences.

Also, it's important for people not to confuse backreferences with capture groups. They look a bit similar, but capture groups are actually fine.

In fact, backreferencing is such a footgun that I don't see it as a possible regex feature. It's a PCRE feature - perhaps even the core distinguishing feature. While all regexes are PCREs, not all PCREs are regexes. It's simply not possible to create a consistently performant implementation of PCRE.

Autodidact here. Beyond just the five core quantifiers

  .
  |
  ?
  *
  +

regex only has capture groups

  ()

and lazy variants of the core quantifiers "?", "*" and "+", which are helpfully called:

  ??
  *?
  +?

The rest is just shorthands.

So while I think it's a worthwhile suggestion not to show people the whole thing the first time round, I doubt that the whole thing is really that complicated.

Really cool. Do you teach people the mechanics, like what the app shows? Because I wonder if that actually makes it harder. I'm wondering about where the hard bits are, given that it all boils down to just:

  "|", which means "or"
  ".", which means "any symbol"
  "?", which means "at most once",
  "*", which means "however many times"
  "+", which means "at least once"

Maybe encountering it next to PEG scrambles your brain.

It's code golf played with Turing machines. The game is: Make the smallest Turing machine whose runtime is bigger than Graham's number, but still terminates. The record right now is 10 states. At least 6 states are needed because any Turing machine with at most 5 states, that finishes running, has a runtime of at most 47,176,870, which is less than Graham's number. In summary:

  BB(10) > G > BB(5) = 47,176,870.

Dijkstra's jeremiads were about promoting "formal methods" as the One True Method for software construction. Maybe there's a future for formal methods, but it wasn't ready in the past. No one was arguing about semaphores.

Dijkstra was an academic with no skin in the game.

If Dijkstra was so confident that he was right, he should have started a business and put his money where his mouth was. Hell, any True Believer of Dijkstra's could have done the same in the last 60 years. The fact that they haven't - or they've never succeeded enough for me to know of any - speaks volumes about their effectiveness.

The constants can be made lower. If we didn't know about the galactic algorithm beforehand, we couldn't begin to do that.