[ruby-talk:16340] Lisp vs. Perl Round 3: Operator Associativity and Manipulation

Thought the list might find this of interest.

Ken
---------------------- Forwarded by Ken LaCrosse/FOL/CDI/CHI/US on 06/08/2001
12:12 PM ---------------------------


Terrence Monroe Brannon <[e-mail]> on 06/08/2001 10:20:35 AM

To:   [e-mail]
cc:    (bcc: Ken LaCrosse/FOL/CDI/CHI/US)
Subject:  Lisp vs. Perl Round 3: Operator Associativity and Manipulation



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