8 ms·

Regex that only matches itself

322 points by biot 10y ago

ninkendo 10y ago
Mostly 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.
- edoceo 10y ago
  Wow, thanks. I've been doing the pipe trick for 15 years. Sokath, his eyes open
- daveFNbuck 10y ago
  I just use pgrep for this now.
  - kalleboo 10y ago
    Not all platforms have pgrep, so I had to look up a trick like that in GP this weekend
usmannk 10y ago
This is ridiculous. How does one go about deriving something like this? Really impressive.
- lmm 10y ago
  Once you've seen the trick for making quines you can apply it to any language.
- jrheard 10y ago
  If you think that's crazy, check out https://www.infoq.com/presentations/miniKanren 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.
  - ndr 10y ago
    That is amazing. I don't want to spoil the fun but I highly recommend that video!
CPLX 10y ago
I wish I was as smart as these people.
- mstodd 10y ago
  I'm inclined to say that some people 'just get' certain things like this or complex SQL. How they got to 'getting it', I don't know.
  - sdegutis 10y ago
    And monads.
    - bertiewhykovich 10y ago
      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.
      - kazagistar 10y ago
        Naw, everyone who understands monads wants nothing more then to explain it. Hence the profusion of tutorials and over-focusing on the concept.
      - lmm 10y ago
        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 http://reasonablypolymorphic.com/blog/ideas-and-men has some basic examples.
      - majewsky 10y ago
        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.
zitterbewegung 10y ago
This is probably a stupid question but what is the minimal formal language that has an accepting path as a statement in the language?
- gchpaco 10y ago
  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.
- deleted 10y ago
  [deleted]
deleted 10y ago
[deleted]
jzox 10y ago
Reminds 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) https://en.m.wikipedia.org/wiki/Quine_(computing)
- totalZero 10y ago
  Stubbornness and vanity. Except in code form.
- fdej 10y ago
  It is literally a quine, viewed as a program in a language where (for example) the code consists of a regular expression and the output is the sequence of all strings matching that regular expression.
- deleted 10y ago
  [deleted]
- j4_james 10y ago
  In the esolang community, the name for this variation of Quine is a Narcissist or Narcissus program. You can see a bunch of examples in a number of different languages on the Rosetta Code website. https://rosettacode.org/wiki/Narcissist https://rosettacode.org/wiki/Narcissist
- joegreen 10y ago
  It also reminded me about quines, I especially like the Quine Relay project which uses 100 different programming languages (each producing an input for the next one) to finally produce its own code https://github.com/mame/quine-relay https://github.com/mame/quine-relay
mepcotterell 10y ago
I think I might be missing something. Wouldn't something like "a" be a valid 1-byte regular expression that only matches instances of "a"?
- deleted 10y ago
  [deleted]
- idbehold 10y ago
  > NOTE, delimiters must be included Your regex is actually /a/ which does not match the string "/a/".
  - mepcotterell 10y ago
    Ahh. Thank you.
  - takeda 10y ago
    I would say that adding slashes is quite arbitrary constraint, and it is really language specific syntax that is limited to minority of languages (I believe it was introduced in Perl). If you do regexp in Java, Python, C you don't use slashes. Edit: looks like slashes weren't even used in the example.
    - bazzargh 10y ago
      Perl's use of this syntax had ancestors in awk, sed, ed, and qed - originally just for string replacements in qed until Ken Thompson wrote a version that did regexps too. It dates back to 1967. https://www.bell-labs.com/usr/dmr/www/qed.html https://www.bell-labs.com/usr/dmr/www/qed.html Deutsch&Lampson's original paper on qed showing s/// used for string substitution prior to it gaining regexps is here: http://research.microsoft.com/en-us/um/people/blampson/04-OnlineEditor/04-OnlineEditor.htm http://research.microsoft.com/en-us/um/people/blampson/04-On... Incidentally the name 'grep' originated here, 'G/RE/P' was a qed command to do a Global Regular Expression match and Print the matches.
    - mcpherrinm 10y ago
dmalvarado 10y ago
Straight-up wizardry.
singularity2001 10y ago
Completely unrelated: http://codegolf.stackexchange.com/questions/99026/build-me-a-brick-wall http://codegolf.stackexchange.com/questions/99026/build-me-a... (using Trumpscript)
tedunangst 10y ago
funny how many times this needed to be submitted before it stuck. https://news.ycombinator.com/from?site=stackexchange.com https://news.ycombinator.com/from?site=stackexchange.com
- i336_ 10y ago
  Wow, and none of them even have [dupe] on them. HN's story ranking system is undisclosed to prevent startups and/or VCs from gaming things AFAIK, but I'm wondering if it pushes things up based on time of day. Alternatively, maybe the people who check /new are only around at certain times. In any case, I'm definitely checking /new a lot more myself. Most of the things I've posted haven't "stuck" either, I realize just how many people this seems to be hitting.
  - pbhjpbhj 10y ago
    >I'm wondering if it pushes things up based on time of day. // What do you mean by that? I don't think HN sniffs location so hour would it even work with a global audience?
    - i336_ 10y ago
      That is an incredibly good point, I certainly wasn't thinking clearly while I was figuring that out, hah I remember seeing someone do some data analysis of all of HN and noted that there was a certain time of day that always seemed to be consistently upvoted the most. I think I was overextrapolating that data, especially considering I've no idea what the article was called now so I couldn't review it.

322 points by biot 10y ago

Mostly 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.

edoceo 10y ago
Wow, thanks. I've been doing the pipe trick for 15 years. Sokath, his eyes open
daveFNbuck 10y ago
I just use pgrep for this now.
- kalleboo 10y ago
  Not all platforms have pgrep, so I had to look up a trick like that in GP this weekend

usmannk 10y ago

This is ridiculous. How does one go about deriving something like this? Really impressive.

lmm 10y ago
Once you've seen the trick for making quines you can apply it to any language.
jrheard 10y ago
If you think that's crazy, check out https://www.infoq.com/presentations/miniKanren 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.
- ndr 10y ago
  That is amazing. I don't want to spoil the fun but I highly recommend that video!

CPLX 10y ago

I wish I was as smart as these people.

mstodd 10y ago
I'm inclined to say that some people 'just get' certain things like this or complex SQL. How they got to 'getting it', I don't know.
- sdegutis 10y ago
  And monads.
  - bertiewhykovich 10y ago
    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.
    - kazagistar 10y ago
      Naw, everyone who understands monads wants nothing more then to explain it. Hence the profusion of tutorials and over-focusing on the concept.
    - lmm 10y ago
      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 http://reasonablypolymorphic.com/blog/ideas-and-men has some basic examples.
    - majewsky 10y ago
      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.

zitterbewegung 10y ago

This is probably a stupid question but what is the minimal formal language that has an accepting path as a statement in the language?

gchpaco 10y ago
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.
deleted 10y ago
[deleted]

deleted 10y ago

[deleted]

jzox 10y ago

Reminds 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) https://en.m.wikipedia.org/wiki/Quine_(computing)

totalZero 10y ago
Stubbornness and vanity. Except in code form.
fdej 10y ago
It is literally a quine, viewed as a program in a language where (for example) the code consists of a regular expression and the output is the sequence of all strings matching that regular expression.
deleted 10y ago
[deleted]
j4_james 10y ago
In the esolang community, the name for this variation of Quine is a Narcissist or Narcissus program. You can see a bunch of examples in a number of different languages on the Rosetta Code website. https://rosettacode.org/wiki/Narcissist https://rosettacode.org/wiki/Narcissist
joegreen 10y ago
It also reminded me about quines, I especially like the Quine Relay project which uses 100 different programming languages (each producing an input for the next one) to finally produce its own code https://github.com/mame/quine-relay https://github.com/mame/quine-relay

mepcotterell 10y ago

I think I might be missing something. Wouldn't something like "a" be a valid 1-byte regular expression that only matches instances of "a"?

deleted 10y ago
[deleted]
idbehold 10y ago
> NOTE, delimiters must be included Your regex is actually /a/ which does not match the string "/a/".
- mepcotterell 10y ago
  Ahh. Thank you.
- takeda 10y ago
  I would say that adding slashes is quite arbitrary constraint, and it is really language specific syntax that is limited to minority of languages (I believe it was introduced in Perl). If you do regexp in Java, Python, C you don't use slashes. Edit: looks like slashes weren't even used in the example.
  - bazzargh 10y ago
    Perl's use of this syntax had ancestors in awk, sed, ed, and qed - originally just for string replacements in qed until Ken Thompson wrote a version that did regexps too. It dates back to 1967. https://www.bell-labs.com/usr/dmr/www/qed.html https://www.bell-labs.com/usr/dmr/www/qed.html Deutsch&Lampson's original paper on qed showing s/// used for string substitution prior to it gaining regexps is here: http://research.microsoft.com/en-us/um/people/blampson/04-OnlineEditor/04-OnlineEditor.htm http://research.microsoft.com/en-us/um/people/blampson/04-On... Incidentally the name 'grep' originated here, 'G/RE/P' was a qed command to do a Global Regular Expression match and Print the matches.
  - mcpherrinm 10y ago

dmalvarado 10y ago

Straight-up wizardry.

singularity2001 10y ago

Completely unrelated: http://codegolf.stackexchange.com/questions/99026/build-me-a-brick-wall http://codegolf.stackexchange.com/questions/99026/build-me-a... (using Trumpscript)

tedunangst 10y ago

funny how many times this needed to be submitted before it stuck. https://news.ycombinator.com/from?site=stackexchange.com https://news.ycombinator.com/from?site=stackexchange.com

i336_ 10y ago
Wow, and none of them even have [dupe] on them. HN's story ranking system is undisclosed to prevent startups and/or VCs from gaming things AFAIK, but I'm wondering if it pushes things up based on time of day. Alternatively, maybe the people who check /new are only around at certain times. In any case, I'm definitely checking /new a lot more myself. Most of the things I've posted haven't "stuck" either, I realize just how many people this seems to be hitting.
- pbhjpbhj 10y ago
  >I'm wondering if it pushes things up based on time of day. // What do you mean by that? I don't think HN sniffs location so hour would it even work with a global audience?
  - i336_ 10y ago
    That is an incredibly good point, I certainly wasn't thinking clearly while I was figuring that out, hah I remember seeing someone do some data analysis of all of HN and noted that there was a certain time of day that always seemed to be consistently upvoted the most. I think I was overextrapolating that data, especially considering I've no idea what the article was called now so I couldn't review it.