Category Archives: Perl

Examples of recursion, in Perl, Ruby, and Bash

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 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 ;)

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/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/