Tag Archives: Perl

Examples of recursion, in Perl, Ruby, and Bash

Image result for recursion

This article is in response to the following question posted in the Perl community group on  LinkedIn:

I’m new to PERL and trying to understand recursive subroutines. Can someone please explain with an example (other than the factorial ;) ) step by step, how it works? Thanks in Advance.

Below, are some very simplified code examples in Perl, Ruby, and Bash.

A listing of the files used in these examples:

blopez@blopez-K56CM ~/hello_scripts 
$ tree .
 ├── hello.pl
 ├── hello.rb
 └── hello.sh
0 directories, 3 files
blopez@blopez-K56CM ~/hello_scripts $


Recursion example using Perl:

– How the Perl script is executed, and it’s output:

blopez@blopez-K56CM ~/hello_scripts $ perl hello.pl "How's it going!"
How's it going!
How's it going!
How's it going!
^C
blopez@blopez-K56CM ~/hello_scripts $ 

– The Perl recursion code:

#!/usr/bin/env perl
use Modern::Perl;
my $status_update = $ARGV[0]; # get script argument

sub hello_world
{
    my $status_update = shift; # get function argument
    say "$status_update";
    sleep 1; # sleep, or eventually crash your system
    &hello_world( $status_update ); # execute myself with argument
}

&hello_world( $status_update ); # execute function with argument


Recursion example using Ruby:

– How the Ruby script is executed:

blopez@blopez-K56CM ~/hello_scripts 
$ ruby hello.rb "Doing great!"
Doing great!
Doing great!
Doing great!
^Chello.rb:7:in `sleep': Interrupt
    from hello.rb:7:in `hello_world'
    from hello.rb:8:in `hello_world'
    from hello.rb:8:in `hello_world'
    from hello.rb:11:in `'
blopez@blopez-K56CM ~/hello_scripts $

Note: In Ruby’s case, stopping the script with CTRL-C returns a bit more debugging information.

– The Ruby recursion code:

#!/usr/bin/env ruby
status = ARGV[0] # get script argument

def hello_world( status ) # define function, and get script argument
    puts status
    sleep 1 # sleep, or potentially crash your system
    return hello_world status # execute myself with argument
end

hello_world status # execute function with argument

Recursion example using Bash:

– How the Bash script is executed:

blopez@blopez-K56CM ~/hello_scripts $ bash hello.sh "..nice talking to you."
..nice talking to you.
..nice talking to you.
..nice talking to you.
^C
blopez@blopez-K56CM ~/hello_scripts $ 

– The Bash recursion code:

#!/usr/bin/env bash

mystatus=$1 # get script argument

hello_world() {
    mystatus=$1 # get function argument
    echo "${mystatus}"
    sleep 1 # breath between executions, or crash your system
    hello_world "${mystatus}" # execute myself with argument
}

hello_world "${mystatus}" # execute function with argument

My Fun With Necrolinguaphilia

Last night I attended a talk given by Dr. Damian Conway (of Perl Best Practices fame) titled “Fun With Dead Languages“.  Although this is a talk that Damian had given previously, it is the first time that I heard it, and I’m so glad I did!

I was the first to arrive at the Mozilla office building at 366 Adelaide, and so was able to score a sweet parking spot right across the street (no small feat in downtown Toronto).

I arrived and introduced myself to Damian as he was preparing for his delivery shortly before a herd of approximately 70 hackers (according to Mozilla) from all language and computing backgrounds started pouring through the meeting room doors to be seated.

Damian has a very energetic style of presentation, and was able to hold our attention while covering everything from the virtual extinction of the Gros Michel Banana, to the benefits and efficiencies of stack-based programming (using PostScript as an example).  He compares many, very different languages including Befunge, Brainfuck, Lisp, and Piet, and suggests that a great place to look for new ideas is what he calls the “Language Morgue”, where he includes languages such as Awk, Prolog, Cobol… and even C++ as examples of dead languages and language paradigms.

Mr. Conway also dived into excruciating detail on how the Latin natural language can be used as an effective computer programming language, and has even gone so far as to write a module called Lingua::Romana::Perligata, which he has made available on the CPAN.

I also had the special treat of sitting right behind Sacha Chua who brilliantly sketched notes of the entire talk in real-time.  I haven’t had the pleasure of formally meeting Sacha just yet (didn’t even say “hello”, my bad!) as I didn’t want to distract her.  Aside from having my mind blown by Damian’s talk, I was also being mesmerized by Sacha’s artistic skills, and so I do feel somewhat justified in keeping my mouth shut just to absorb everything that was going on right in front of me (front-row seats FTW!).

20130806 Fun with Dead Languages - Damian Conway

Sacha has made her “Fun With Dead Languages” sketch notes publicly available on her blog for everyone to review and enjoy, and has placed it under a Creative Commons license, so please share freely (and drop her a note to say “thanks!”).

Overall, I learned a lot from this this talk and appreciate it immensely.  The energy of the audience made the discussion that much more enjoyable.  If you are interested in programming languages or language theory in general, I suggest you attend this talk the next time Damian decides to deliver it (or find a recording if one happens to be available?).  Damian Conway’s insights and humorous delivery are well worth the brainfuck ;)

Just Another Perl Hacker

Sometimes writing small snippets of code can be meditative.

The other day, I realized that, even though I happen to be, among other things, Just Another Perl Hacker, I never bothered to write my own JAPH signature.  So I went ahead and wrote up a very simple (but effective) one.  Once it was complete, it dawned on me that other perl hackers may appreciate the ability to generate a signature like my own.

Since perl is all about code reuse and sharing, I figured I would write up a JAPH signature generator so that anyone can have an awesomely obfuscated JAPH signature like I do.

Firstly here’s my JAPH signature:

$_='Kvtu!Bopuifs!Qfsm!Ibdlfs-!K/!Cpccz!Mpqf{';
@_=split//;foreach(@_){print chr(ord()-1)}

You can run the JAPH signature by copy/pasting it to a text file (e.g., japh_sig.pl), and running with

perl japh_sig.pl

Which returns:

Just Another Perl Hacker, J. Bobby Lopez

You can also run the JAPH signature straight off the command line (with ‘perl -e’), but you have to replace the single quote characters in the string with double-quote characters, for example:

perl -e '$_="Kvtu!Bopuifs!Qfsm!Ibdlfs-!K/!Cpccz!Mpqf{";@_=split//;foreach(@_){print chr(ord()-1)}'

This is all just for fun of course, but if you do end up using my JAPH signature generator, please let me know by sending me a quick message on Twitter to @jbobbylopez.

Have Fun!

The JAPH Signature Generator

#!/usr/bin/env perl
##############################################
# USAGE:
#   perl japh.pl This is my awesome signature
#
# OUTPUT:
#   Your JAPH Signature:
#       $_='Uijt!jt!nz!bxftpnf!tjhobuvsf';
#       @_=split//;foreach(@_){print chr(ord()-1)} 
#
#   Returns:
#       This is my awesome signature
#
# AUTHOR: J. Bobby Lopez <jbl@jbldata.com>
##############################################

use feature say;

my $offset = 1;
my $signature = join (" ", @ARGV);
my $obfus_sig;

my @obfus = ();
my @sig = split //, $signature;

foreach my $c (@sig)
{
    push @obfus, ( chr ( ord($c) + $offset ) );
}

$obfus_sig = join ("", @obfus);

say <<"OUT";

Your JAPH Signature:
\t\$_='$obfus_sig';
\t\@_=split//;foreach(\@_){print chr(ord()-$offset)} 

OUT
print "Returns:\n\t";
@_=split//,$obfus_sig;foreach(@_){print chr(ord()-$offset)};
say;
1;

Playing With Prime Numbers

I’ve been toying around with functional programming, and recently came across a perlmonks thread discussing multiple ways to calculate prime numbers.  One of the things I noticed about many of the examples was that almost all of them used loops of some sort (for, when, etc).  So I decided to tackle the problem without using any loops.  Instead, I’ll just use recursive functions.

Firstly, here’s the perlmonks thread: Prime Number Finder

And here’s the solution I came up with:

#!/usr/bin/env perl

use strict;
use warnings;
use 5.010;

$DB::deep = 500;
$DB::deep = $DB::deep; # Avoids silly 'used only once' warning

no warnings "recursion";

# Identify primes between ARG0 and ARG1

my ($x, $y, $re_int, $result);
my ($prime, $is_int);

$x = $ARGV[0];
$y = $ARGV[1];

$is_int = sub {
    my $re_int = qr(^-?\d+\z);
    my ($x) = @_;
    $x =~ $re_int
      ? 1
      : 0;
};

$prime = sub {
    my ( $x, $y ) = @_;
    if ( $y > 1 ) {
        given ($x) {
            when ( $is_int->( $x / $y ) ) {
                return 0;
            }
            default {
                return $prime->( $x, $y - 1 );
            }
        }
    }
    else { return 1; }
};

$result = sub {
    my ( $x, $y ) = @_;
    if ( $x <= $y ) {
        if ( $prime->($x, $x-1) ) {
            say $x;
        }
        $result->( ( $x + 1 ), $y );
    }
};

$result->($x, $y);

When running this code with larger numbers, I would eventually run into “deep recursion” warnings, which is why I’ve had to use no warnings "recursion"; and set $DB::deep to a specific value higher than 100 (which is the default). $DB::deep is a debugging variable used specifically to limit recursion depth, in order to prevent long-running or infinite recursive operations.

The method I’m using here to calculate prime numbers isn’t the most efficient, since I’m not doing anything to reduce the amount of numbers I have to test at each cycle. However, adding some extra intelligence to this, such as the filtering used by the Sieve of Eratosthenes (an “ancient Greek algorithm for finding all prime numbers up to a specified integer.”) should be doable.

I’ll be keeping an eye out for other solutions, since I’m sure there are many (especially in perl), but so far this one seems to be fairly fast and clean. I’m looking forward to what Math::BigInt can offer here as well, if anything.

Playing with Factorials, Haskell, and Perl

I’m currently making may way through a book called “Seven Languages in Seven Weeks” by Bruce A. Tate.  So far it’s been an interesting read, but I’m far from finished.

One of the things in the book that caught my eye was a recursive factorial function in Haskell, which seemed so simple, that I had to see what it would look like in perl.

So I wrote up the following perl snippets to calculate factorials.  There are, of course, multiple ways to do it as I’ll describe below.  There are also (likely) many other ways which I haven’t thought of, so if you have an interesting solution, please share.

One of the things that really caught my attention was how simplistic the syntax was for writing somthing so complex.  Recursion is a fairly simple idea once you’ve seen it in action – a function that executes itself.  However, the implementation of recursion in a given programming language can be somewhat difficult to comprehend, especially for new programmers or those without programming experience.

Although I haven’t dived into Haskell quite yet, it seems to make implementing a factorial function so simple, that I kind of stumbled when trying to understand it, thinking I was missing something.. but it was all there in front of me!

Firstly, let’s clarify what a factorial is (from wikipedia):

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5 ! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \

 

So the factorial of 5 is 120.  Or 5! = 120.   Lets look at the Haskell example from the book.

let fact x = if x == 0 then 1 else fact (x - 1) * x

The above line is saying “if x is 0, then the factorial is 1 – otherwise, call myself with (x – 1), multiplied by x”

Lets look at this in ghci (the Haskell console):

[jbl@watchtower tmp]$ ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> let fact x = if x == 0 then 1 else fact (x - 1) * x
Prelude> fact 5
120
Prelude>

After seeing how easy it was to implement the recursive factorial function in Haskell, here are my attempts in perl.

Firstly, using a loop:

#!/usr/bin/env perl

use strict;
use warnings;
use feature "say";

my $nni = $ARGV[0] ? $ARGV[0] : 5;

for my $i ( 1..($nni - 1) )
{
    $nni = $nni * $i;
    say $nni;
}

This first example doesn’t implement a function, and is really just bad (but still working) code. It requires that your base number be global and alterable, in this case $nni.

Now, lets try it with an actual function:

#!/usr/bin/env perl

use strict;
use warnings;
use feature "say";

my $nni = $ARGV[0] ? $ARGV[0] : 5;

sub fact 
{ 
    my ($nni) = @_;
    return !$nni ? 1 : fact( $nni - 1 ) * $nni;
}

say fact($nni);

This second method works similarly to the Haskell implementation. It implements a function that calls itself, without any looping required.

However, it’s still not as concise as the Haskell version, so lets try again:

#!/usr/bin/env perl

use strict;
use warnings;
use feature "say";

my $nni = $ARGV[0] ? $ARGV[0] : 5;
my $fact;
$fact = sub { my ($nni) = @_; !$nni ? 1 : $fact->( $nni - 1 ) * $nni };
say $fact->($nni);

Aha, now we’re getting somewhere. In this third example, the fact() function is anonymous, and we’re assigning it to $fact via reference. This allows us to use $fact like an object with a single method that does the factorial calculation.

Although this is pretty much as concise as I was able to get it while taking readability into account, here’s a final example that goes a step further:

#!/usr/bin/env perl

use strict;
use warnings;
use feature "say";

my ($nni, $fact);
$nni = $ARGV[0] ? $ARGV[0] : 5;
$fact = sub { !$_[0] ? 1 : $fact->( $_[0] - 1 ) * $_[0] };
say $fact->($nni);

This last example uses perl’s pre-defined variable @_ which automatically holds a list of function arguments by default. I usually avoid doing this, since it hurts readability, especially for those who don’t live and breathe perl on a daily basis.

To my surprise, it would seem that Haskell has Perl beat (at least in this example) as far as readability + conciseness is concerned.

I haven’t spent much time playing golf here to reduce the number of lines or characters beyond the last example, but if anyone does come up with a tighter solution, please let me know!


Edit (20111005T22:43:50): Here’s a version I found that uses the Math::BigInt module

#!/usr/bin/env perl

use strict;
use warnings;
use feature "say";
use Math::BigInt lib=>'GMP';

my $b = Math::BigInt->new($ARGV[0]);
say $b->bfac();

This version is likely much faster, since the Math::BigInt package is intended to be used in situations where large integers are being handled.

Here’s the post I found with examples written in other languages as well: Factorial Challenge: Python, Perl, Ruby, and C

Work on CPAN-API and Perl Modules Indexing

Since the last TPM meeting in October, some of the TPM members have been working diligently to improve the CPAN search experience by re-architecting CPAN search from the bottom up. I’ve joined the design team in the hopes of providing the Perl community a much more improved CPAN experience.

As most Perl developers are aware, search.cpan.org is great for finding useful libraries and modules, but horrible at providing any significant information which relates modules to each-other, or providing useful meta-information or statistics which can be used to make better decisions on which modules to use, let alone deploy in a production environment.

If you are interested in taking part in the CPAN-API community project, please contact me, or visit the CPAN-API project site on GitHub.

CPAN-API: https://github.com/CPAN-API/cpan-api/wiki/
Toronto Perl Mongers: http://to.pm.org/

Converting Freemind Mind-maps Directly to Perl Hash Trees

freemind

I use Freemind quite a bit for brainstorming and as an outliner.  One of it’s better uses for me is to hammer out an idea for a perl hash tree very quickly.  The problem is that once I have the hash tree exactly the way I want it in Freemind, I have to manually re-create the hash tree in perl source, with all the required formatting.

This is no longer the case, as I’ve written a quick and dirty “freemind2perl” script (below) which takes a Freemind mind-map file, and converts it into a perl hash tree automagically.  I’m not sure if it will work with all versions of Freemind, but mind-map files (.mm files) are XML based, and the format really hasn’t changed across versions.

Just save the script below as ‘freemind2perl.pl’ and run it with ‘perl freemind2perl.pl yourmap.mm’.  It requires the “XML::Simple” perl module to be installed.

Here’s the script (click here to download):

#!/usr/bin/perl -w

use strict;

use XML::Simple;
use Data::Dumper;

my $xml = new XML::Simple;
my $mm_file = shift;
my $data = $xml->XMLin("$mm_file");
my $clean;

sub prep_clean
{
    my $data = shift;
    my $clean;

    foreach my $key ( keys %{ $data } )
    {
        if ( $key eq "TEXT" )
        {
            $clean->{$data->{$key}} = 1;
        }

        if ( $key eq "node" )
        {
            if ( ref( $data->{$key} ) eq "HASH" )
            {
                $clean->{$data->{'TEXT'}} = prep_clean(\%{$data->{$key}});
            }

            if ( ref( $data->{$key} ) eq "ARRAY" )
            {
                my $sub_hashes = {};
                for ( my $i = 0; $i <= $#{$data->{$key}}; $i++)
                {
                    foreach my $sub_hash ( \%{ $data->{$key}[$i] } )
                    {
                        my $subout = prep_clean( $sub_hash );
                        $sub_hashes = { %$sub_hashes, %$subout };
                    }
                }
                $clean->{$data->{'TEXT'}} = $sub_hashes;
            }
        }
    }
    return $clean;
}

$clean = prep_clean( \%{ $data->{'node'} } );

print Dumper(\$clean);

exit;

Back to Basics – Very Simple Log Monitoring with Perl

multitail_apache

There are many many tools out there which allow you to monitor and view your system or networking logs in several different ways.  Sometimes though, you may find yourself looking for a specific feature that none of these tools currently provide.  Whenever your goals are very specific, and you don’t want to use a big feature-full program to accomplish a simple task, you may want to consider writing your own tool.

Below is a simple Perl program I wrote which does just that. All the requirements of the program are within the script itself (using the __DATA__ handle at the bottom of the file). The only thing you may need to install on your system to get this to work is the File::Tail CPAN package.

#!/usr/bin/perl -w

use strict;
use File::Tail;

my @patterns = ;
my $file = File::Tail->new ("/var/log/syslog");
while ( defined(my $line=$file->read) )
{
    my $match = &filter($line);
    if ( $match eq "no" )
    {
        print $line;
    }
}

sub filter ()
{
    my $line = $_[0];
    my $match = "no";
    foreach my $test (@patterns)
    {
        chomp($test);
        if ( $line =~ m/$test/ )
        {
            $match = "yes";
        }
    }
    return $match;
}

__DATA__
PROTO=UDP SPT=67 DPT=68
ACCEPT IN=br0 OUT=vlan1 src=192.168.0.111.*PROTO=TCP.*DPT=80
ACCEPT IN=br0 OUT=vlan1 src=192.168.0.102.*PROTO=TCP.*DPT=80
ACCEPT IN=br0 OUT=vlan1 src=192.168.0.111.*PROTO=TCP.*DPT=443
ACCEPT IN=br0 OUT=vlan1 src=192.168.0.102.*PROTO=TCP.*DPT=443
ACCEPT IN=vlan1 OUT=br0.*DST=192.168.0.101.*PROTO=UDP.*DPT=1755
ACCEPT IN=vlan1 OUT=br0.*DST=192.168.0.101.*PROTO=TCP.*DPT=1755
ACCEPT IN=br0 OUT=vlan1 src=10.100.0.1.*PROTO=UDP.*DPT=53
JBLLNXWKS dhclient

__END__

This program will monitor the end of the file (like the Unix ‘tail’ command) and check for new log entries. When it detects new lines in the log, it will filter those lines with the patterns defined at the end of the script (under __DATA__) and display anything it detects in the logs except those filter lines.

You’ll probably notice that the filter lines are regular expressions, which makes this script more powerful than doing filtering by simple full-string comparison.

Aside from simply printing the output to STDOUT, you could use regular expressions to pop pieces of each line into an array or hash, in order to do calculations, such as how many entries had a source IP of X, or destination port of Y, etc.

Its definitely a good thing to keep in mind that whatever software you could possibly need is already out there on the internet, and possibly open source. However, its also good to keep in mind that YOU can create a tool yourself to accomplish your specific task; all it takes is a little self-confidence, effort, and patience.

Braindump: WxWidgets, Version Control, and Firefox Bookmarks

WxWidgets GUI Programming

I’ve been thinking about creating an application using the WxWidgets GUI API.  I’ve read a lot about it, and many seem to really enjoy the results of the applications they’ve created with it.

For my own purposes, I’ve been looking for the ideal GUI API that would allow me to quickly create cross-platform desktop applications for Windows and Linux platforms (Mac would be a bonus).  I’ve looked at QT, GTK, and MingGW.. but I’ve been turned off because they don’t seem to have strong Perl and/or Python bindings (although Perl strong with Tk, I’ve heard).

I’ve tried a small test Python program with WxWidgets (GTK version), and was pleasantly surprised at the simplicity of the code.  I think I’m going try some other tests, this time using Perl, as I want to note the differences in complexity between Perl and Python code.  Currently, Perl is my canvas of choice ((Being that I see programming as an art, more than anything else)).

Continue reading Braindump: WxWidgets, Version Control, and Firefox Bookmarks