Path: utzoo!news-server.csri.toronto.edu!rutgers!sun-barr!cs.utexas.edu!wuarchive!udel!rochester!kodak!ispd-newsserver!atexnet!lawrence
From: lawrence@epps.kodak.com (Scott Lawrence)
Newsgroups: comp.lang.perl
Subject: recursive &func breaks s/(foo)/&func($1)/eg
Message-ID: <5128@atexnet.UUCP>
Date: 12 Mar 91 20:50:21 GMT
Sender: news@atexnet.UUCP
Organization: Atex, Inc. (A Kodak Company), Billerica, MA
Lines: 101

I think that I have discovered a problem with substitution and
recursion.  Please someone demonstrate that I am wrong.

I was working on translating simple logical expressions into perl
expressions so that I could eval them.  A simplified version of
my program is included below to demonstrate the problem.

The function Expr uses a substitution operator with both the 'e'
and 'g' modifiers to match each word in an expression, and pass
it to a function (Atom) which returns a perl fragment that could
be evaluated to a boolean value (the evaluation is not important
to the demo, so I left it out).  For simple words, Atom just
wraps the word in a subroutine invocation (as in case 'foo'
below).  If the word has been defined to be a set ( using the
associative array %Set ), Atom calls Expr with the value of the
set, having wrapped it in parens.  The problem occurs when a
member of one set is another set, so that Expr is called a third
time; the remainder of the original call is lost.

-------------- example
demo% ./demo

Case = 'foo'                # This case is simple
Expr = 'foo'                # The expression is just one atom
Atom = 'foo'                # which is not a set
Result =>  &In('foo')       # the result is correct

Case = 'test'               # Slightly more complicated because test
Expr = 'test'               # is defined as a set by:
Atom = 'test'               # $Set{ 'test' } = 'foo & bar';
Expr = '( foo & bar )'      # which works,
Atom = 'foo'                # foo and bar are not sets
Atom = 'bar'                
Result => (  &In('foo')  &  &In('bar')  ) # so the result is correct

Case = 'set'                # 'set' is defined as a set by
Expr = 'set'                # $Set{'set'} = "test | done";
Atom = 'set'                # 
Expr = '( test | done )'    # set is correctly expanded
Atom = 'test'               # but the first atom (test) is also a set
Expr = '( foo & bar )'      # which is correctly expanded here
Atom = 'foo'                # and each atom is expanded ok
Atom = 'bar'                # but result is wrong - Atom is never called
Result => ( (  &In('foo')  &  &In('bar')  ) # for 'done' 

The final result should have been:

Result => ( (  &In('foo')  &  &In('bar')  ) |  &In('done') )
                                            ^^^^^^^^^^^^^^^^- omitted

I can rewrite this so that it doesn't rely on the s///eg to work,
but if it did work it would be much more elegant.  It looks to me
as though I either have a variable scoping problem or the return
stack is getting messed up.  Any suggestions?  Perl source for
demo follows, with my perl version info...

$Header: perly.c,v 3.0.1.10 91/01/11 18:22:48 lwall Locked $
Patch level: 44

SunOS Release 4.1 (GENERIC) #1: Tue Mar 6 17:27:17 PST 1990

----------------- begin demo -----------------
#!/usr/local/bin/perl

$Set{'test'} = "foo & bar";   # one level of substitution
$Set{'set'} = "test | done";  # recursive substitution

@Cases = ( 'foo', 'test', 'set' );

test: while( $_ = shift @Cases )
{
    print "\nCase = '$_'\n";
    $Result = &Expr( $_ );
    print "Result => $Result\n";
}

sub Expr
{
    local( $Expr ) = $_[0];
    print "Expr = '$Expr'\n";

    $Expr =~ s/(\w+)/&Atom($1)/eg; # <<<<<<<<<<<<<<<< 

    return $Expr;
}

sub Atom
{
    local( $Atom ) = $_[0];
    print "Atom = '$Atom'\n";

    return defined $Set{ $Atom } 
           ? &Expr("( $Set{$Atom} )") : " &In('$Atom') ";
}
----------------------- end of demo ---------------------

--
--
Scott Lawrence             <lawrence@epps.kodak.com>  Voice: 508-670-4023
Atex Advanced Publishing Systems                        Fax: 508-670-4033
Atex, Inc; 165 Lexington St. MS 400/165L; Billerica MA 01821