lecture in color

Functional Programming

In Perl, one is always torn between efficiency of runtime and efficiency of implementation and maintenance
The "clearest" implementation is almost always too slow.
The "fastest" implementation is almost always unreadable.
In the last lecture, we covered techniques for increasing runtime efficiency.
In this lecture, we cover the opposite: techniques for making programming more efficient and reliable.
Sometimes, we get lucky, and both coincide!

Problems in normal Perl

Too many darn variables.
Side-effects.
Overly complex namespace.

Functional programming in perl

Really a way of thinking differently about perl programming.
Create a program as a result of function composition.
Each function:
- is free of side-effects.
- never modifies its inputs.
- uses value return as its sole mechanism for returning results.

First, a few dirty tricks

Can't safely modify something without copying it over:

contents of perl_func/Copy.pm...
#! /var/local/couch/bin/perl 

package Copy; 

require Exporter; 

BEGIN { 
    @Copy::ISA = qw(Exporter); 
    @Copy::EXPORT = qw(copy); 
    @Copy::EXPORT_OK = qw(); 
} 

# Deep copy operator copies everything 
# in a structure, presuming that every 
# module knows how to copy itself. 
# This produces a completely autonomous 
# copy with the exact same values. 
sub copy { 
    my $thing = shift; 
    if (ref $thing eq 'HASH') { 
	my ($key,$value); 
        my $result = {}; 
	while (($key,$value) = each %$thing) { 
	   $result->{$key} = copy($value); 
        } 
        return $result; 
    } elsif (ref $thing eq 'ARRAY') { 
	my $result = []; 
        # don't copy uninstantiated cells
        for (my $i=0; $i<@$thing; $i++) { 
	    $result->[$i]=$thing->[$i] if exists($thing->[$i]); 
        } 
#	foreach my $key (@$thing) { 
#	    push(@$result,copy($key)); 
#       } 
	return $result; 
    } 
    elsif (ref $thing eq 'CODE'
     ||    ref $thing eq 'GLOB'
     ||    ref $thing eq 'REF'
     ||    ref $thing eq '') { return $thing; } 
    else { return $thing->copy; } # hope that $thing knows how to copy itself
} 

1; 
...end of perl_func/Copy.pm

This is a deep copy: result is completely decoupled from original.
This makes it so that modifications of a thing don't have side-effects elsewhere.
It is also very expensive and perhaps unnecessary for other reasons.

Mapping: how to perform the same operation on every element of an array:

contents of perl_func/map1.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Copy; 

my $a = [[1,2,3],[4,2],[5,6,7]]; 

sub sum { 
    my $sum = 0; 
    foreach my $t (@_) { $sum+=$t; } 
    return $sum; 
} 

print "sum of 1,2,3 is " . &sum(1,2,3) . "\n"; 

my $b = [ map { &sum(@$_) } @$a ]; 

print Dumper($b); 
...end of perl_func/map1.pl

This prints:

contents of perl_func/map1.pl.out...
sum of 1,2,3 is 6
$VAR1 = [
          6,
          6,
          18
        ];
...end of perl_func/map1.pl.out

What a mess!

map takes a function block and an array as arguments.
Within the function block, $_ is set to each element of the array in turn.
The result is an array of results of applying the function.
Since we're dealing with references, @$_ treats a reference as an array, while @$a treats the scalar $a as a reference to array.

Concatenative collapse: simply stated, takes advantage of the fact that () drops out of any array into which it's placed.
```
contents of perl_func/cat1.pl...
#! /var/local/couch/bin/perl 

@stuff = (2,2,6,9,2,1,3,6); 
@filtered = map { $_>5 ? ($_) : () } @stuff; 
print join (' ',@filtered) . "\n"; 
...end of perl_func/cat1.pl
```
This prints:
```
contents of perl_func/cat1.pl.out...
6 9 6
...end of perl_func/cat1.pl.out
```
Whoa there! What the heck happened?
- a?b:c (otherwise known as an inline-if) is b if a is true, c otherwise.
- So $_>5?($_):() is ($_) if $_>5, () otherwise.
- So the result of the map is ((),(),6,9,(),(),(),6) which we know is just the same as (6,9,6)

Primitive operations in functional programming

Construction: making a structure from another.
Distribution: distributing a constant argument within a structure.
Filtering: constructing a new thing from an old one, selecting some part.
Projection and selection: selecting one part of a structure (and ignoring another).

Construction

Built-in: [...], {...}, etc.
Plus constructors for objects.

Distribution

Consider the code:

contents of perl_func/Distribute.pm...
#! /var/local/couch/bin/perl 

package Distribute; 

require Exporter; 

BEGIN { 
    @Distribute::ISA = qw(Exporter); 
    @Distribute::EXPORT = qw(distr distl trans project); 
    @Distribute::EXPORT_OK = qw(); 
} 

# left and right distribution of things
sub distr { [map { [$_ , $_[1]] } @{$_[0]}] } 
sub distl { [map { [$_[0] , $_] } @{$_[1]}] } 

# grab a column from a two-dimensional vector 
sub project { [ map { $_->[$_[0]] } @{$_[1]} ] }

# transpose a list of vectors. 
sub trans { 
    my $result = [];
    my $longest = 0; 
    foreach my $t (@{$_[0]}) { 
	my $len = @$t; 
	$longest = $len if $longest<$len; 
    } 
    for (my $i=0; $i<$longest; $i++) { 
        push(@$result,project($i, $_[0])); 
    } 
    return $result; 
} 

1; 
...end of perl_func/Distribute.pm

This implements the primitives of left distribution, right distribution, and transposition.

Here's a really bizarre way to multiply an array of numbers by a constant:

contents of perl_func/distr.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Distribute; 

my $numbs = [2,5,8,2,3]; 
my $dist = distr($numbs,5); 
print Dumper($dist); 
my $muls = [ map { $_->[0] * $_->[1] } @$dist ] ; 
print Dumper($muls); 
...end of perl_func/distr.pl

This prints

contents of perl_func/distr.pl.out...
$VAR1 = [
          [
            2,
            5
          ],
          [
            5,
            5
          ],
          [
            8,
            5
          ],
          [
            2,
            5
          ],
          [
            3,
            5
          ]
        ];
$VAR1 = [
          10,
          25,
          40,
          10,
          15
        ];
...end of perl_func/distr.pl.out

The key is to express the problem of multiplying as a composition of distributing the factor and then mapping a function onto the result.

Let's go completely insane and use distribution to construct a set.

contents of perl_func/distr2.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Distribute; 

sub cat { [ map { (@$_) } @{$_[0]} ] } 
sub toSet { return { @{cat(distr($_[0],1))} } } 

my $set = toSet(['1','2','a','b']);
print Dumper($set); 
...end of perl_func/distr2.pl

This prints:

contents of perl_func/distr2.pl.out...
$VAR1 = {
          '1' => 1,
          'a' => 1,
          'b' => 1,
          '2' => 1
        };
...end of perl_func/distr2.pl.out

What in heck is going on here? Let's explore it by "exploding" the execution as it occurs.

Consider the code:

contents of perl_func/distr3.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Distribute; 

sub probe { 
    for (my $i=0; $i<@_; $i++) { 
        my $d = new Data::Dumper([$_[$i]], [sprintf("arg%02d",$i)]); 
	$d->Indent(0); 
	print $d->Dump() . "\n"; 
    } 
    @_; 
} 
sub cat { [map { (@$_) } probe(@{$_[0]})] } 
sub toSet { return { @{cat(distr($_[0],1))} } } 

my $set = toSet(['1','2','a','b']);
print Dumper($set); 
...end of perl_func/distr3.pl

This prints:

contents of perl_func/distr3.pl.out...
$arg00 = ['1',1];
$arg01 = ['2',1];
$arg02 = ['a',1];
$arg03 = ['b',1];
$VAR1 = {
          '1' => 1,
          'a' => 1,
          'b' => 1,
          '2' => 1
        };
...end of perl_func/distr3.pl.out

Specialized form of distribution: transposition converts a set of parallel arrays into arrays of elements. Consider:

contents of perl_func/trans.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Distribute; 

sub sum { 
    my $addends = shift; 
    my $sum = 0; 
    foreach my $a (@$addends) { $sum += $a; } 
    return $sum; 
} 

sub prod { 
    my $multiplicands = shift; 
    my $prod = 1; 
    foreach my $a (@$multiplicands) { $prod *= $a; } 
    return $prod; 
} 
sub dot { sum( [map { prod($_) }  @{trans(@_)}] )  } 

print "project(0,[[1,2,3],[4,5,6]])=".Dumper(project(0,[[1,2,3],[4,5,6]])); 
print "project(1,[[1,2,3],[4,5,6]])=".Dumper(project(1,[[1,2,3],[4,5,6]])); 
print "project(2,[[1,2,3],[4,5,6]])=".Dumper(project(2,[[1,2,3],[4,5,6]])); 
print "trans([[1,2,3],[4,5,6]])=".Dumper(trans([[1,2,3],[4,5,6]])); 
print "dot product = " . dot ([[1,2,3],[4,5,6]]) . "\n"; 
...end of perl_func/trans.pl

This prints:

contents of perl_func/trans.pl.out...
project(0,[[1,2,3],[4,5,6]])=$VAR1 = [
          1,
          4
        ];
project(1,[[1,2,3],[4,5,6]])=$VAR1 = [
          2,
          5
        ];
project(2,[[1,2,3],[4,5,6]])=$VAR1 = [
          3,
          6
        ];
trans([[1,2,3],[4,5,6]])=$VAR1 = [
          [
            1,
            4
          ],
          [
            2,
            5
          ],
          [
            3,
            6
          ]
        ];
dot product = 32
...end of perl_func/trans.pl.out

Collection

Often, we need to change the shape of an array.

Consider the code:

contents of perl_func/Collect.pm...
#! /var/local/couch/bin/perl 

package Collect; 

require Exporter; 

BEGIN { 
    @Collect::ISA = qw(Exporter); 
    @Collect::EXPORT = qw(collect pair concat); 
    @Collect::EXPORT_OK = qw(); 
} 

# an array into n-tuples in preparation for a mapping operation 
sub collect { 
    my $n = shift; 
    my @out = (); 
    for (my $i=0; $i<@_; $i+=$n) { 
        my $tuple = []; 
	for (my $j=0; $j<$n; $j++) { 
	    push(@$tuple,$_[$i+$j]); 
        } 
	push(@out,$tuple); 
    } 
    return @out; 
} 

# pair up things in an array
sub pair { &collect (2,@_) } 

# concatenate things that have been collected
sub concat { map { (@$_) } @_ } 

1; 
...end of perl_func/Collect.pm

This allows us to convert between kinds of arrays for mapping.

Test this with

contents of perl_func/Collect.pl...
#! /var/local/couch/bin/perl 

use Collect; 
use Data::Dumper; 
my $out = [ collect(3,(1,2,3,4,5,6)) ]; 
print Dumper($out); 
$out = [ pair(1,2,3,4,5,6) ]; 
print Dumper($out); 
$out = [ concat([1,2],[3,4,5]) ]; 
print Dumper($out); 
...end of perl_func/Collect.pl

This prints:

contents of perl_func/Collect.pl.out...
$VAR1 = [
          [
            1,
            2,
            3
          ],
          [
            4,
            5,
            6
          ]
        ];
$VAR1 = [
          [
            1,
            2
          ],
          [
            3,
            4
          ],
          [
            5,
            6
          ]
        ];
$VAR1 = [
          1,
          2,
          3,
          4,
          5
        ];
...end of perl_func/Collect.pl.out

Using this, we can freely convert from arrays to arrays of n-tuples, as needed.

Filtering

Construct an array of possible candidates (in any way whatsoever).
Use an inline if to convert undesirable elements to ().
Result is an array containing only the desired elements!

Consider the code:

contents of perl_func/Filter.pm...
#! /var/local/couch/bin/perl 

package Filter; 

require Exporter; 

BEGIN { 
    @Filter::ISA = qw(Exporter); 
    @Filter::EXPORT = qw(filter); 
    @Filter::EXPORT_OK = qw(); 
} 

# return an array, filtered by a criterion you specify. 
# only elements for which the criterion is true will be preserved. 
sub filter (&@) { 
    my $code = shift;
    return map { &$code?($_):() } @_; 
} 

1; 
...end of perl_func/Filter.pm

using function inlining, and then call this using

contents of perl_func/Filter.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Filter; 
use Collect; 

my @stuff = filter { $_ > 2 } 1,2,3,4,0,2,3; 
print "stuff=" . join(" ",@stuff) . "\n"; 

my $thing = { 'a'=> 50, 'b'=> 20, 'c'=>652 }; 
my $t2 = { concat (filter { $_->[1]>100 } pair(%$thing)) }; 
print Dumper($t2); 
...end of perl_func/Filter.pl

This produces:

contents of perl_func/Filter.pl.out...
stuff=3 4 3
$VAR1 = {
          'c' => 652
        };
...end of perl_func/Filter.pl.out

Filtering a normal array is easy.
By converting a hash to an array, it is possible to filter the hash upon either its keys or its values!

Functions

Principal idea of functional programming: functions are data that can be manipulated.
First exercise: make a data container for a function.

Consider:

contents of perl_func/Funcall.pm...
#! /var/local/couch/bin/perl 

package Funcall; 

# package allows one to delay function evaluation 
# and call several functions on the same arguments. 

sub new { 
    my $pack = shift; 
    return bless [@_]; 
} 

sub call { 
    my $self = shift; 
    my $function = $self->[0]; 
    my @args = @$self; 	# copy!
    shift @args; 
    push(@args, @_);    
    &{$function}(@args); 
} 

1; 
...end of perl_func/Funcall.pm

Call this using

contents of perl_func/Funcall.pl...
#! /var/local/couch/bin/perl 

use Funcall; 

# package allows one to delay function evaluation 
# and call several functions on the same arguments. 

sub sum { 
    my $sum = 0; 
    foreach my $s (@_) { $sum += $s } 
    return $sum; 
} 

my $f = new Funcall (\&sum, 200, 300); 
my $g = $f->call(1,2,3); 
print "g=$g\n"; 
my $h = (new Funcall(\&sum))->call(4,5,6); 
print "h=$h\n"; 
...end of perl_func/Funcall.pl

This prints

contents of perl_func/Funcall.pl.out...
g=506
h=15
...end of perl_func/Funcall.pl.out

Basic idea: encapsulate the function and the first few arguments; specify the rest later.

Functions in structures

What does a function mean if embedded in a structure?
One interpretation: apply the structure as a function, result is
- contents of the structure (if not a function).
- function return value (if a function).

Consider:

contents of perl_func/Construct.pm...
#! /var/local/couch/bin/perl 

package Construct; 

# package allows one to embed functions in a structure
# and instantiate all of them on the same arguments
# arguments are a reference to the structure as well
# as any arguments to appear prior to the others, to 
# be listed in the call. 

# my $foo = new Construct([\&sum,\&prod],10); 
# print Dumper($foo->call(1,2,4)); 
# # computes [10+1+2+4, 10*1*2*4]

sub new { 
    my $pack = shift; 
    return bless [@_]; 
}

sub call { 
    my $self = shift; 
    my @args = @$self; # copy
    my $funcstruct = shift(@args); 
    push(@args,@_); 
    return &construct($funcstruct,@args); 
} 

# apply an arbitrary structure of functions 
# and partially instantiated function calls 
# to a datum and return the result. 
sub construct { 
    my $structure = shift; 
    return $structure if ! ref $structure; 
    return &{$structure}(@_) if ref $structure eq 'CODE'; 
    return construct ($$structure,@_) if ref $structure eq 'REF'; 
    return construct (*$structure,@_) if ref $structure eq 'GLOB'; 
    return [ map { construct($_,@_) } @$structure ] 
	if ref $structure eq 'ARRAY'; 
    return { map { construct($_,@_) } (%$structure) } 
	if ref $structure eq 'HASH'; 
    # else we have a blessed reference; 
    # pray that the structure knows what to do itself.
    return $structure->call(@_); 
} 

1; 
...end of perl_func/Construct.pm

This is code that creates a structure that contains functions, and is capable of evaluating it on data.

Test this using:

contents of perl_func/Construct.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Construct; 

sub sum { 
    my $sum = 0;   
    foreach (@_) { $sum += $_ } 
    return $sum; 
} 

sub prod { 
    my $prod = 1;   
    foreach (@_) { $prod *= $_ } 
    return $prod; 
}

my $foo = new Construct([\&sum,\&prod],10); 
print Dumper($foo->call(1,2,4)); 
...end of perl_func/Construct.pl

This prints:

contents of perl_func/Construct.pl.out...
$VAR1 = [
          17,
          80
        ];
...end of perl_func/Construct.pl.out

Composition

Our last abstraction: composing a series of functions on data.

Consider:

contents of perl_func/Compose.pm...
#! /var/local/couch/bin/perl 

package Compose; 
use Data::Dumper; 

# implement the idea of composing functions and returning the 
# composite result. Input is an array of functions to compose.  

sub new { 
    my $pack = shift; 
    return bless [@_]; 
} 

sub call { 
    my $self = shift; 
    my $funcs = $self->[0]; 
    my @res = @$self; 
    shift @res; 
    push(@res,@_); 
print Dumper(\@res); 
    for( my $i=@$funcs-1; $i>=0; $i--) { 
        my $f = $funcs->[$i]; 
	if (ref $f eq 'CODE') { 
	    @res = &{$f}(@res); 
        } elsif (ref $f) { 
	    @res = $f->call(@res); # hope the function knows how to call itself
	} 
print Dumper(\@res); 
    } 
    return @res; 
} 

1; 
...end of perl_func/Compose.pm

Try this using:

contents of perl_func/Compose.pl...
#! /var/local/couch/bin/perl 

use Compose; 
use Data::Dumper; 
use Distribute; 

sub sum { 
    my $sum = 0; 
    foreach (@_) { $sum += $_; } 
    return $sum; 
} 

sub prod { 
    my $prod = 0; 
    foreach (@_) { $prod += $_; } 
    return $prod; 
} 

my $thing = new Compose (
	[\&sum, sub { map { &prod(@$_) } @{$_[0]} },\&trans]
); 
my @result = $thing->call([[1,2,3],[4,5,6]]); 
print "result=$result[0]\n"; 
...end of perl_func/Compose.pl

This prints:

contents of perl_func/Compose.pl.out...
$VAR1 = [
          [
            [
              1,
              2,
              3
            ],
            [
              4,
              5,
              6
            ]
          ]
        ];
$VAR1 = [
          [
            [
              1,
              4
            ],
            [
              2,
              5
            ],
            [
              3,
              6
            ]
          ]
        ];
$VAR1 = [
          5,
          7,
          9
        ];
$VAR1 = [
          21
        ];
result=21
...end of perl_func/Compose.pl.out

(using debugging writes inside Composition.pm to help us understand things).

What's the point?

Many really complex actions become easier to understand when expressed in terms of transformation, filtering, and composition. Consider, e.g., the following:

contents of perl_func/graph.pl...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Construct; 
use Funcall; 
use Nodes; 
use Edges; 

my $thing = new Construct (
    { 'nodes' => new Funcall (\&Nodes::new, 'Nodes'), 
      'edges' => new Funcall (\&Edges::new, 'Edges')
    } 
); 

my $tuples = [['a','b',60], 
              ['a','c',90]]; 
my $stuff = $thing->call($tuples); 
print Dumper($stuff); 
...end of perl_func/graph.pl

This prints:

contents of perl_func/graph.pl.out...
$VAR1 = {
          'edges' => bless( {
                              'a' => {
                                       'c' => 90,
                                       'b' => 60
                                     }
                            }, 'Edges' ),
          'nodes' => bless( {
                              'c' => 1,
                              'a' => 1,
                              'b' => 1
                            }, 'Nodes' )
        };
...end of perl_func/graph.pl.out

This version:
- Embodies the same idea as linear code.
- is largely declarative in nature.
- once you get used to it, is a lot easier to understand.
Once you master this concept, there is no limit to the complexity of the structures you can handle.
You declare structure functionally and Perl does the rest!

lecture in color

downloaded on Nov-23-2009 02:19:47 PM,
was last modified on Dec-31-1969 07:00:00 PM.
All lecture note content is copyright 2003 by
Alva L. Couch, Computer Science, Tufts University
(couch at cs dot tufts dot edu)