Grokbase Groups Perl ai May 2001
FAQ
TITLE
Lisp vs Perl Round One: Operator Associativity and Manipulation

BACKGROUND
In the process of converting a general pattern matcher (regular
expressions are pattern matchers limited to processing strings)
discussed in Peter Norvig's "Paradigms of Artificial Intelligence:
Case
Studies in Common Lisp", I ran into a doosy. Something was a snap to
do
in Lisp, but far from trivial in Perl. First the lisp code:

(defun match-if (pattern input bindings)
"Test an arbitrary expression involving variables. The pattern
looks
like ((?if lisp-code) . rest)."
(and (progv (mapcar #'car bindings)
(mapcar #'cdr bindings)
(eval (second (first pattern))))
(pat-match (rest pattern) input bindings)))

What this code is doing is taking some lisp code and evaluating it
within a certain context. What is a context? A context is a set of
variable bindings. What the mapcar statement above is doing is
setting
up a set of variable bindings so that when the lisp-code is
evaluated,
it is evaluated in the context of those bindings. Then what happens
is
the eval evauluates the lisp code with the variable bindings from
the
context as a frame of reference.

The difficulty in converting this to Perl lies in the fact that
operators are not first class. Let's see an example of this lisp
pattern-matcher in action:
(pat-match '(?x ?op ?y is ?z (?if (eql (?op ?x ?y) ?z)))
'(3 + 4 is 7))
((?z . y) (?y . 4) (?x . 3))
What happened is that ?x got bound to 3, ?op got bound to + and ?z
got
bound to 7 and then the pattern matcher called the if-block based on
the
context formed by the earlier matches in the pattern.

Note how easily Lisp took an operator and stored it in a variable
just
like anything else in Lisp. Second (though not the focus of this
paper),
note how easy it was for the if block to receive and use a context.
In
Perl, operators and contexts are not truly first class, meaning you
can't pass them around and you can't assign them to variables...
easily.
They are in fact available to the Perl parser and a complicated set
of
parsing modules, but such Herculean efforts appear ridiculous
compared
to the expressive ease shown above.

In order for you to see firsthand what I am talking about with
respect
to Perl, let's take a stab at writing that powerful little Lisp
snippet
in Perl. First what would our pattern look like:

$pattern = [qw(X OP Y is Z),
'IF',
sub {$_[0]->{X} $_[0]->{OP} $_[0]->{Y} ==
$_[0]->{Z}} ];
$input = [ 3 '+' 4 is 7 ] ;

And here is our call to get the ball rolling:

pat_match ($pattern, $input, $bindings) ;

## And our desired output:

{ X => 3, Y => 4, Z => 7, OP => '+' }

sub match_if { my ($pattern, $input,$bindings) = @_ ;

$pattern->($bindings) ;
}

The above subroutine would work well, but it has a problem. There is
no
way to assign the '+' to $_->{OP} ; Also, the actual if subroutine
reference must pander to Perl's complex associativity rules. In both
respects, Lisp is easier. As stated earlier playing with Lisp
operators
is a snap:

(setq op '+)
(funcall op 2 2)

and associativity is a snap: just follow the parentheses.

The only way to handle a problem like this in Perl is to resort to
source filtering or parsing. And then you must make sure that your
minilanguage emulates the associativity semantics of Perl as well as
Perl in all respects...

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

People

Translate

site design / logo © 2021 Grokbase