http://www.perlmonks.org?node_id=806255


in reply to Re: Recursive substitution
in thread Recursive substitution

When you replied, my first thought—and rightly so, I think—was “Oh no, I've under-specified the problem again”, and I'm sorry for that.

However, I'd like now to offer a less panicked reply. You are certainly correct that I can do what I want with a loop, but we know that recursion can do whatever iteration can; and, in a sense, I'm trying to make that abstract understanding concrete in this particular sense. Sure, I could just say

sub f; sub f { $_[0] =~ s/^(a{1,3})(?=b)/$1a/ ? goto &f : return $_[0]; }
to get something that only a functional programmer could love; but I'm wondering if I can make the regex perform (or ‘simulate’, of whatever) the recursion for me, without explicit function calls.

‘Regular’ regexes don't have this power, but Perl regexes are, of course, not regular; and so I could have phrased my question vaguely as: is there any way for back-references and other assorted Perl tricks to let us get around this limitations of ‘regular’ regexes?

In order to avoid under-specifying again, let me give the real question that I am trying to answer, because of moritz's post: Are Perl regexes Turing complete without (?{}) and (??{})? If not, can I get by with some minimal amount of embedded code (like (?{pos = 0}), as you suggested)?

This started off as a reply to the parent, but, while I was (slowly) composing it, you posted another node. This is my response to that node, too. :-)

Replies are listed 'Best First'.
Re^3: Recursive substitution
by ikegami (Patriarch) on Nov 10, 2009 at 16:43 UTC
    You say want a regex to do something, but all of your examples place a loop outside of a substitution. Regex can't do substitutions. There's some disconnect in your explanation.

    we know that recursion can do whatever iteration can;

    Yes, a loop can be implemented using recursion. That doesn't mean you need recursion to count from 1 to 10. You need a loop, no matter how it's implemented.

      You say want a regex to do something, but all of your examples place a loop outside of a substitution. Regex can't do substitutions. There's some disconnect in your explanation.
      Yes, you're right. I am using regex (improperly) to mean regex-with-substitution, i.e., s/// (with whatever non-/e switches and internal decorations you like, but as little /e, (?{}), and (??{}) as possible).
      That doesn't mean you need recursion to count from 1 to 10. You need a loop, no matter how it's implemented.

      I know I don't need recursion. I want recursion.

      I think it's reasonable to say “The problem can't be solved under these stupid restrictions”, or “I don't care to try to solve the problem under these stupid restrictions”, but not “Problems with stupid restrictions are wrong problems”. The drive to minimalism (of axioms) is, I think, at the heart of computer science; it's certainly at the heart of mathematics, and, as I am a mathematician, it's what drives me.

      UPDATE: On re-reading, that was an over-reaction to something that probably wasn't your position at all. Anyway it was more than a bit rude, so I apologise.

        I want recursion.

        Sorry, but you can't execute another s/// without /e, (?{}) or (??{}). Recursion is out.

        As for a solution without recursion, I don't know of any.