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

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:
Studies in Common Lisp", I ran into a doosy. Something was a snap to
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
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
up a set of variable bindings so that when the lisp-code is
it is evaluated in the context of those bindings. Then what happens
the eval evauluates the lisp code with the variable bindings from
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
bound to 7 and then the pattern matcher called the if-block based on
context formed by the earlier matches in the pattern.

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

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

$pattern = [qw(X OP Y is Z),
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
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
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


Follow ups

Related Discussions



site design / logo © 2021 Grokbase