Pathologically Eclectic Rubbish Lister PerlMonks

### Recursive substitution

 on Nov 10, 2009 at 04:10 UTC Need Help??
JadeNB has asked for the wisdom of the Perl Monks concerning the following question:

Is it possible to perform a s///g substitution in such a way that the substituted text is itself recursively parsed? That is, can I mangle the code

```\$_ = 'ab';
s/^(a{1,3})(?=b)/\$1a/g; # => \$_ = 'aab'
so that I wind up instead with \$_ = 'aaaab'? (I don't mean by taking \$_ = 'aaab' to begin with, either. :-) )

The problem, as I understand it—and this is probably either over-simplified or blatantly wrong—is that pos is set to point just after the substitution; but something silly like setting pos manually doesn't seem to help either:

```\$_ = 'ab';
s/^(a{1,3})(?=b)/pos = 0, \$1 . 'a'/eg; # still, \$_ => 'aab'

UPDATE: By the way, I know that I could just do something like 1 while s///, but I'm curious—purely for academic reasons (or, really, if you must know, because of moritz)—if it can be done entirely inside the regex itself; that is, if regexes can provide the necessary control structure. (Sorry, I unfairly added this while bobf and ikegami were replying.)

Replies are listed 'Best First'.
Re: Recursive substitution
by bobf (Monsignor) on Nov 10, 2009 at 04:27 UTC

I like to take a very simple approach to such things, since the tricky methods usually confuse me when I come back to it 6 months later and have to modify it somehow. :-)

```my \$s = 'ab';
my \$pat = qr/^(a{1,3})(?=b)/;

while( \$s =~ m/\$pat/ )
{
\$s =~ s/\$pat/\$1a/g;
}

Or, if you prefer more of the 1-liner feel:

```my \$s = 'ab';
my \$pat = qr/^(a{1,3})(?=b)/;

do{ \$s =~ s/\$pat/\$1a/g } while \$s =~ m/\$pat/;

I'm sure it is possible to do this in the regex itself (probably with /e). I'm sure other monks will enlighten both of us.

Update: I changed approaches mid-code and forgot to remove the superfluous m//. These solutions are not very perlish.

Thanks very much. I realised shortly after posting that I hadn't explained why I didn't want the most natural answer (current explanation: because I don't, that's why), but didn't update my post in time.

By the way, I think that s/\$pat/\$sub/ is (effectively) a no-op unless m/\$pat/, so I think that it's redundant to do a separate m/\$pat/ check.

it's redundant to do a separate m/\$pat/ check
You are absolutely correct, of course. I started playing with patterns that would have required the extra check (because the ones used in s/// and m// were different), but I failed to remove the extra code after changing my approach. I added a note to my original reply but left the crufty code to avoid confusing future readers of this thread.

Re: Recursive substitution
by ikegami (Pope) on Nov 10, 2009 at 04:30 UTC

There's

```1 while s/^(a{1,3})(?=b)/\$1a/;

but I'm sure you're going to say that's no good.

As you can see, what you're trying to do is a loop, not recursion.

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. :-)

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.

I'm sure you're going to say that's no good.
Spot on. Sorry about that. :-)
Re: Recursive substitution
by johngg (Abbot) on Nov 10, 2009 at 11:12 UTC
Yes, that looks like it's a much clearer version of the question that I was trying to formulate. Thanks!
Re: Recursive substitution
by ikegami (Pope) on Nov 10, 2009 at 04:39 UTC

if it can be done entirely inside the regex itself;

If what can be done? Change the position at which it will continue matching? Why don't you try it?

```>perl -le"\$_='abc'; /(.)(?{ pos = 0 })(.)/; print for \$1,\$2"
a
b

Guess not.

As indicated in my post (even the first version, not one updated out from under you—sorry), I did try modifying pos, to (as you point out) no avail. My question was just whether there was some other clever approach that I was missing.

I did try modifying pos

Yes, but not within the regex. Whatever it is you want to do, you said you wanted to do it within a regex.

My question was just whether there was some other clever approach that I was missing.

Again, another approach to do what?

Re: Recursive substitution
by grizzley (Chaplain) on Nov 10, 2009 at 08:34 UTC
Is it possible to perform a s///g substitution in such a way that the substituted text is itself recursively parsed?

I don't find any use for it. The way I always think of regexes is

s/find some text/react to this text/somehow;

If you find text, the 'react' part has enough information to build any replace string you want. There you can use another regex (nested) to do something (and I can provide examples if you want). And this can be useful.

But the approach:

s/find some text, replace it, find more text in replaced string/react to second finding/

? Not good: first part of s/// is to find something, second is to replace. For analysing text not for changing it.

While I agree that your approach to s/// is the most common, and probably the best, if we wanted there to be only one way to do things then we'd be using Python the principle that TIMTOWTDI can surely be extended to TIMTORTDI (there is more than one reason to do it!). :-)

As an illustration of the use of recursive substitution, consider macro-expansion languages. Recursion means the difference between a language that is Turing complete and one that is not. (Note that the latter article is quoted approvingly—sometimes totality is better than Turing completeness.)

Create A New User
Node Status?
node history
Node Type: perlquestion [id://806115]
Approved by bobf
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (6)
As of 2017-08-17 11:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (286 votes). Check out past polls.

Notices?