Fellow monks,

As I mentioned here, I want to practice taking good, elegant Lisp code and re-writing it in Perl. And the first opportunity for this came today.

While browsing Peter Norvig's website, I came upon this - a primer in Python for Lisp programmers. In the end, in a section called "Comparing Lisp and Python Programs", Norvig takes an excerpt from his Paradigms of Artificial Programming (one of the best programming book in the world, IMHO) - generation of random sentences from defined grammars, and implements a Python version for it.

So, I decided to employ Perl to compete in this task as well...

Here is an implementation I came up with (only generate, as generate_tree is the same idea):

use warnings; use strict; my %dict = ( sentence => [[qw/ noun_phrase verb_phrase /]], noun_phrase => [[qw/ Article Noun /]], verb_phrase => [[qw/ Verb noun_phrase /]], Article => [qw/ the a /], Noun => [qw/ man ball woman table/], Verb => [qw/ hit took saw liked /] ); sub rand_elt { return $_[rand scalar @_]; } sub listp { return ref($_[0]) eq "ARRAY"; } sub generate { my $phrase = shift; if (listp $phrase) { return [map {@{generate($_)}} @{$phrase}]; } elsif (exists $dict{$phrase}) { return generate(rand_elt(@{$dict{$phrase}})); } else { return [$phrase]; } } print join(' ', @{generate("sentence")}), "\n";

Overall I'm satisfied with the result - it's an elegant functional code that represents the solution in an intuitive recursive way, without too much overhead.

Some observations:

  1. Note that Lisp also doesn't have the random-elt function built-in, it's defined by Norvig elsewhere.
  2. In the attempt to "transliterate" the Lisp code, Perl succeeds nicely. Interestingly, the elegant mappend construct that's defined in the Lisp/Python versions is implemented trivially with Perl's native map.
  3. Perl also allows to avoid defining the rewrites the Lisp version defines, since it has easier hash access.
  4. In Lisp, all objects are pointers and the data they point to has a type. Thus, you can ask (listp foo). In Perl it doesn't work - arrays/lists and scalars are very different. Hence, in my implementation a "list" is an array ref, it allows to define $phrase as a scalar. The listp function I defined helps spot the difference. In general, Lisp's handling of lists is much cleaner, since Perl requires @{$..} sugar.

Generally, this code is "the Lisp way", or rather "the functional programming way". There may be more "perly" solution that are more succinct (I don't mean golf !), efficient and so on. You are welcome to propose other methods and / or observations.

P.S: implementations in Perl 6 will be also most welcome !

In reply to Perl can do it, take 1 (sentence generation) by spurperl

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":