Lisp vs. Perl Round 3: Operator Associativity and Manipulation

[princepawn]

---

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

Operator manipulation, associativity are first-class and easy to use at program-level in Lisp. Operator manipulation in Perl is an advanced topic and all aspects of it are not available even at advanced level... thus Damian Conway's Quantum::Superpositions module could only overload certain certain operators. On the other hand all Lisp operators are available for novice programmer inspection, manipulation and alteration.

Perl associativity is highly complex, but geared towards making programming Perl more English-like. However, this same degree of complexity makes it much more difficult to synthesize the syntax for complicated program-level semantics involving operators.

A final point of interest, undetermined as of yet, is whether or not all the added linguistic arcana of Perl makes for a language which runs considerably faster than Perl.

update (broquaint): dropped non-PM compatible tags

[Sifmole]

This is all only true if you decide to go out of your way to make it obscure and convoluted. Of course I am probably only taking the bait, but here goes....

#!/usr/bin/perl -w

use strict;

my $pat = '"%d %s %d is %d" if (%d %s %d == %d)'; 

matchIf($pat, 3, '+', 4, 7);
matchIf($pat, 5, '*', 4, 20);
matchIf($pat, 5, '%', 4, 20);
matchIf($pat, 5, '-', 4, 20);

sub matchIf {
    my ($pat, $x, $op, $y, $z) = @_;
    my $foo =  sprintf($pat, $x, $op, $y, $z, $x, $op, $y, $z);
    print eval ($foo),"\n";
}

Not even golfed.

Not nearly as wacky as you made it out to be. BTW, I spent 3 semesters doing Artificial intelligence work with Lisp in college and I actually love working with it; But your arguement here just shows that either you didn't bother to learn the tool (Perl) well enough to do the job right, or you intentionally misrepresented things to serve your point.

And as a note: Most people do not consider the Lisp method of using Reverse Polish notation for conditionals and mathmatics particularly simple. Most people would understand "x op y = z" but only a programmer (or maybe a mathematician) could love "op op x y z".

Update Figured I would add that the development time on this was ~5 minutes.

Update And just a couple more showed that we can do this....

#!/usr/bin/perl -w

use strict;

my $pat = '"%d %s %d is %d" if (%d %s %d == %d)'; 
my $order = '[$_[0], $_[1], $_[2], $_[3]]';

matchIf($pat, $order, 3, '+', 4, 7);
matchIf($pat, $order, 5, '*', 4, 20);
matchIf($pat, $order, 5, '%', 4, 20);
matchIf($pat, $order, 5, '-', 4, 20);

sub matchIf {
    my ($pat, $order) = (shift, shift);
        print eval sprintf($pat, @{eval $order}, @{eval $order}), "\n"
+;

}

To make the ordering configurable as well.
Update Got rid of the maps, because well.... they were complete useless.

[hding]

Just a nit: the Lisp notation for math would be described as Polish (function before arguments) rather than Reverse Polish (function after arguments).

[princepawn]

Thank you for taking the bait. First of all, your example does not support unification. I assume you know what this is and why your example does not support it. If not, read Norvig for details.

Most people do not consider the Lisp method of using Reverse Polish notation for conditionals and mathmatics particularly simple.

But would you agree that it is consistent and that one does not have to refer to a manual to know whether an operator associates to the left, to the right or not at all?

But your arguement here just shows that either you didn't bother to learn the tool (Perl) well enough to do the job right, or you intentionally misrepresented things to serve your point.

How does your example "do the job right?" Please read the title of the post. You created a telegraphed example which only supports binary infix operators. It won't work for unary ops and it will fail on more complex ops where you must know Perl prcedences rules.

And finally, the use of strings is very slow.

[Sifmole]

But would you agree that it is consistent and that one does not have to refer to a manual to know whether an operator associates to the left, to the right or not at all?

Consistency is not the be-all end-all goal. I personally am very comfortable sacrificing some consistency for greater flexibility to write easier to read and maintain code. You however, as evident from several posts, have a bit of a fetish for it. However, as before, your claim of inconsistency wrong.
Perl is consistent, just on a more granular level; There is an order of precedence, and it is always followed. I extremely rarely find myself refering to a manual to figure out how to put together an expression ( I say rarely, because I never say never. ).

How does your example "do the job right?" Please read the title of the post. You created a telegraphed example which only supports binary infix operators. It won't work for unary ops and it will fail on more complex ops where you must know Perl prcedences rules.

You example only used '+' and 'eql' so I followed suit. I only invested 5 minutes in putting it together. You show me yours and I will show you mine.

And finally, the use of strings is very slow

And when did Lisp become blindingly fast?

[princepawn]

And when did Lisp become blindingly fast?

I quote from Lisp as an Alternative to Java

Our results show that Lisp's performance is comparable to or better than C++ in terms of execution speed, with significantly lower variability which translates into reduced project risk. Furthermore, development time is significantly lower and less variable than either C++ or Java. Memory consumption is comparable to Java. Lisp thus presents a viable alternative to Java for dynamic applications where performance is important.

[tilly]

As I have commented before, the general opinion is that Lisp is bloated and slow. This opinion was formed on hardware with 1% of the memory and speed of current PC hardware.

Additionally there has beeen a lot of research into how to optimize Lisp. It turns out that Lisp can be optimized very well. If you are willing to give it the right declarations, amazingly so. Most of the ideas that people have for how to make Perl 6 optionally fast? Well Lisp had those ideas ages ago and standardized it into ANSI Common Lisp. And vendors have had years to implement it then fine tune the results...