This is ridiculous. How does one go about deriving something like this? Really impressive.
Once you've seen the trick for making quines you can apply it to any language.
Regex that only matches itself
41–50 of 66 posts
Re: Regex that only matches itself
#42Earlier quoted context omitted.
And monads.
My suspicion is that no one wants to explain monads because if they did it would be painfully obvious that they're a purgatorial way of getting around the basic mismatch between functional purity and actual computers.
Monads for all your I/O yeah, probably kind of dumb. Monads as a tool for dealing with cross-cutting concerns? Ridiculously useful. http://reasonablypolymorphic.com/blog/ideas-and-men has some basic examples.
Re: Regex that only matches itself
#43Earlier quoted context omitted.
What do you mean?
Regex libraries often distinguish between a string containing a regex, and matching it. The string "aaaa" is a Regular Expression that describes a language with exactly one string: "aaaa". Some regular expression libraries have two operations: They can tell you if a string contains a match somewhere within it, or is exactly a match. Some other libraries only do the first operation, and you need to explicitly ask for…
Yeah. I want trying to be a jerk. Pedantic some, but I thought the difference between match and find was pretty general in regex land.
Re: Regex that only matches itself
#44This is ridiculous. How does one go about deriving something like this? Really impressive.
If you think that's crazy, check out https://www.infoq.com/presentations/miniKanren at the 31:30 mark. These two guys teach their logic programming system a subset of scheme, then they can run it "backwards" to find quines - programs that evaluate to themselves.
That is amazing. I don't want to spoil the fun but I highly recommend that video!
Re: Regex that only matches itself
#45Reminds me of a quine - a non-empty computer program which takes no input and produces a copy of its own source code as its only output https://en.m.wikipedia.org/wiki/Quine_(computing)
Stubbornness and vanity. Except in code form.
Re: Regex that only matches itself
#46Earlier quoted context omitted.
My suspicion is that no one wants to explain monads because if they did it would be painfully obvious that they're a purgatorial way of getting around the basic mismatch between functional purity and actual computers.
Actually, it's the other way around. Monad tutorials are so frequent that it's become a meme among Haskellers that everyone will eventually write a monad tutorial to relay his own mental model of monads.
Sorry -- you're right. I should have said "explain monads well."
Re: Regex that only matches itself
#47Earlier quoted context omitted.
> the list monad is used to model non-determinism See this is the kind of thing that made learning Haskell so hard for me. I'm not a math guy, I'm terrible at math. I have no idea what "non-determinism" means, and I'd venture to guess that list monad is used to model "ordered collections of things".
"non-determinism" implies unordered.
See, to me, the sequence of keypresses I make while banging on my keyboard seem like it could be represented as an ordered list. I may be missing something, though.
Re: Regex that only matches itself
#48Mostly unrelated, but I use the opposite trick to ensure that the "grep" process itself doesn't show up when I "ps | grep" for a process.
Something like:
ps -ef | grep "myprogra[m]"
Re: Regex that only matches itself
#49Mostly unrelated, but I use the opposite trick to ensure that the "grep" process itself doesn't show up when I "ps | grep" for a process. Something like: ps -ef | grep "myprogra[m]" Is still a regex that matches the string "myprogram", but it doesn't match itself , so the "grep myprogram" doesn't show up in the output. Easier than doing " | grep -v grep" or similar.
Wow, thanks. I've been doing the pipe trick for 15 years.
Sokath, his eyes open
Re: Regex that only matches itself
#50This is probably a stupid question but what is the minimal formal language that has an accepting path as a statement in the language?
A formal language is basically just a mathematical set of acceptable strings made up of symbols in a (typically finite) alphabet; thus the smallest is probably the empty set, or if you insist on an accepting path, a set containing only the empty string.
The interesting part comes up when you want to match an infinite set of strings with an algorithm. Probably the simplest such algorithm would be "regardless of input, accept" which isn't exactly useful but would suffice.
It's dissatisfying to have an algorithm that puts weird, arbitrary restrictions on composing languages; for example it's usually the case that if you take a language L1 and a language L2 that are both acceptable to the algorithm, the concatenation (for every string in L1 and every string in L2, the concatenation of their strings is in the new language) language is usually acceptable to the algorithm.
Some commonly used languages do not have all of these properties; in particular the intersection of two context-free languages may not be a CFL, nor the complement. Deterministic context free languages are even more restrictive. You seem to need to give some things up as you move up the language hierarchy in power; in particular string homomorphism and intersection seem to be mutually exclusive in languages more powerful than regular expressions.
If you're interested, the theory of abstract families of languages has been studied, although I do not know a lot about it myself.