Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

How A Function Becomes Higher Order

by Limbic~Region (Chancellor)
on Sep 16, 2005 at 15:51 UTC ( #492651=perltutorial: print w/ replies, xml ) Need Help??

All:
Higher Order Perl, by Dominus, has become a very popular book. It was written to teach programmers how to transform programs with programs. Many of us who do not have familiarity with Functional Programming are not aware of what a Higher Order function is. It is a function that does at least one of the two following things:
  • Accepts a function as input
  • Returns a function as output

For some, you can stop reading here because you already know what Higher Order functions are - you just didn't know that's what they were called. In Perl terminology, we often refer to them as callbacks, factories, and functions that return code refs (usually closures). Even if you are familiar with those terms, you may not be familiar with how to use them.

This tutorial is an illustration of how a simple every day function may become higher order, increasing its usefulness in the process. Along the way we will pick up other tricks that can make our code more flexible.

Problem: We have a file containing a list of scores and we need to determine the highest score.

Using the principal of code reuse and not reinventing the wheel, we turn to our trusty List::Util.

use List::Util 'max'; my @scores = <FH>; my $high_score = max(@scores);

Unfortunately, this requires all of the scores to be held in memory at one time and our file is really big. Just this once, we decide to break the rules and roll our own.

my $high_score; while ( <FH> ) { chomp; $high_score = $_ if ! defined $high_score || $_ > $high_score; }

As time goes by "just this once" has happened many times and we decide to make our version reuseable.

sub gen_max { # Create an initial default value (or undef) my $max = $_[0]; # Create an anonymous sub that can be # dereferenced and called externally # but will still have access to $max return sub { # Process 1 or more values for ( @_ ) { $max = $_ if ! defined $max || $_ > $max; } return $max; }; } my $max = gen_max(); while ( <FH> ) { chomp; # Dereference and call the anonymous sub # Passing in 1 value at a time $max->($_); } # Get the return value of the anonymous sub my $high_score = $max->();

This is our first step into Higher Order functions as we have returned a function as the output for the sake of reusability. We also have a few advantages over the original List::Util max function.

  • Does not require all values to be present at once
  • Ability to define a starting value
  • Ability to process one or more values at a time

Unfortunately, our function breaks the second we start comparing strings instead of numbers. We could make max() and maxstr() functions like List::Util but we want to use the concept of Higher Order functions to increase the versatility of our single function.

sub gen_reduce { my $usage = 'Usage: gen_reduce("initial" => $val, "compare" => $co +de_ref)'; # Hashes need even number of arguments die $usage if @_ % 2; my %opt = @_; # Verify that compare defined and a code reference die $usage if ! defined $opt{compare} || ref $opt{compare} ne 'COD +E'; my $compare = $opt{compare}; my $val = $opt{initial}; return sub { for ( @_ ) { # Call the user defined anonymous sub # Passing in two parameters using the return $val = $_ if ! defined $val || $compare->($_, $val); } return $val; }; } # Create an anonymous sub that takes two arguments # A true value is returned if the first is longer my $comp = sub { return length($_[0]) > length($_[1]); } my $maxstr = gen_reduce(compare => $comp ); while ( <FH> ) { chomp; $maxstr->($_); } my $long_str = $maxstr->();

Now our function takes a function as input and returns a function as output. In addition to the previous functionality, we have added a few more features.

  • Named parameters - allows flexibility in ordering and presence of arguments as well as ease in extensibility
  • User defined comparator - our max function has now become a reduce function

This does not have to be the end of the journey into Higher Order functions, though it is the end of the tutorial. Whenever you encounter a situation where two programs do nearly identical things but their differences are enough to make using a single function impossible - consider Higher Order functions to bridge the gap. Remember - it is important to always document your interface and assumptions well!

I open the floor to comments both on the advantages and disadvantages of Higher Order functions. As they say, there is no such thing as a free lunch and there are always cases in which it makes sense to use distinct routines for distinct problems.

Cheers, L~R

Updates: The second paragraph regarding terminology was added at the suggestion of diotalevi in the CB. Comments have been added to the code at the suggestion of several monks in the CB.

Note: List::Util is a great module and the limitation of requiring all the values to be present at once is usually made up for by the fact that it also provides a reduce() function, has both C and Perl implementations, and syntactic sugar. The limitations were highlighted here for illustration purposes though I recommend using it when and where it does the job you need it to.

Comment on How A Function Becomes Higher Order
Select or Download Code
Re: How A Function Becomes Higher Order
by jkva (Chaplain) on Sep 16, 2005 at 17:09 UTC

    Brilliant. Simply brilliant.

    This has propelled me into a flurry of thoughts about the things I can do with Perl. Higher Order indeed.
    The code is here and there somewhat complicated but the added comments have clarified it somewhat and confirmed suspected code meanings.
    It explains a way of using flexibility in your code - I'm not too good in explaining this I'm afraid. But it's one of those reads that make you 'get' things. At least for me.

    I'm looking forward to the sequel - maybe a tutorial explaining callbacks, closures and factories? Or who knows, self-modifying code ;)

Re: How A Function Becomes Higher Order
by jdporter (Canon) on Sep 16, 2005 at 18:10 UTC
    Since closures are just another way of implementing encapsulation and re-use, I think it would behoove the programmer to choose the most appropriate elements of the program to refactor using this technique. In the case of your example, I think a better choice would be to "higher-order"ify the file accessing bits, since that's the most general-purpose part, and is likely to have the greater pay-off in terms of re-use. That's not to say that a max() function couldn't as well, but it seems to me to be the more application-specific algorithmic part.
    sub with_file_do { my( $filename, $each_line_cb ) = @_; my $fh = new IO::File "< $filename" or die "read $filename - $!"; chomp, $each_line_cb->($_) while <$fh>; } my $max; with_file_do( $scores_file, sub { my( $score ) = @_; !defined $max || $max < $score and $max = $score; } ); print "max=$max\n";
    Btw - I don't get the argument that named parameters aid extensibility. I frankly don't see any extensibility in this mechanism. Can you show how it would be done?
      jdporter,
      I agree that good judgement needs to be employed when deciding how to use this technique to solve a problem or if to use it at all. Perl does a great job of providing us many tools so that we can choose the right tool for the job. This basic tutorial was intended to introduce the concept and illustrate a basic example of the steps taken to transform a basic function into a Higher Order one.

      With regards to extensibility and named parameters, the advantage is clear when you consider optional parameters using the positional approach. Imagine your function starts out accepting 3 parameters. You then add an optional parameter which you stick on the end. Now if you want to add a 5th parameter you need to change the ordering of the parameters which will break backwards compatability. The issue gets even more complicated if you have more than one optional parameter.

      If this doesn't make my position clear, let me know and I will provide a concrete example using Tie::SortHash and Tie::Hash::Sorted.

      Cheers - L~R

        O.k., you're talking about extending the one function in situ, not the kind of extension that subclassing or aggregation gives.

        And that's essentially my complaint about this technique: it's nearly impossible to build large, extensible frameworks with. In my experience, functional programming works great at small levels of granularity; for anything larger, OO is far more useful. (Of course, the FP purists will disagree, and I'm not saying they're wrong.)

      We're getting warmer. What we'd really like to do is reuse the abstractions and functions we've already got available. So you tie a file to an array, and use the standard collection traversal functions (map, grep, foreach, reduce, etc.) to do the dirty work. And be sure to make it lazy (demand driven) just like our familiar unix command line utilities. (see Chapter 9, pg. 142 of Advanced Perl Programming (the Panther)).
Re: How A Function Becomes Higher Order
by liverpole (Monsignor) on Sep 16, 2005 at 23:46 UTC
    A really superb job, limbic~region.  This is the kind of cogent article which makes for enlightening, enjoyable reading about Perl.  I will be looking forward to more such inspiring tutorials from you!
Re: How A Technique Becomes Over-rated
by Ctrl-z (Friar) on Sep 22, 2005 at 13:13 UTC
    Closures are cool, but I dont really see any practical or theoretical benefit to what you are tutoring:
    package Max; sub new { my $class = shift; my $max = undef; return bless \$max, $class; } sub compare{ return $_[1] > $_[2]; } sub max{ my $self = shift; for ( @_ ) { $$self = $_ if $$self == undef || $self->compare($_, $$self); } return $$self; } package StringMax; our @ISA = ('Max'); sub compare { return length($_[1]) > length($_[2]); } package main; my $max= new StringMax(); while ( <FH> ) { chomp; $max->max($_); } my $long_str = $max->max();
    The same functions, the same number of lines - better organized for applying to real problems.



    time was, I could move my arms like a bird and...
      Ctrl-z,
      Perhaps you mistook my tutelage for advocacy.

      Did you realize that your StringMax doesn't produce the largest string (gt) but the longest string (length)? The function in the tutorial got renamed at the end because it became an all-purpose reduce function. In your re-write, you would have to create a new kind of compare package/function combo for every single type of comparison you wanted before you could use it.

      There are of course more ways to do it. The point of the tutorial was to take some scary magic from Functional Programming Land (Higher Order Functions) and demystify it. Jargon aside, the majority of Perl programmers I have seen only know 1 or 2 paradigms (imperative & OO). They try to fit everything they see into one of them. By providing an introductory lesson, I hoped to expose some people to a new way of doing things which they could determine for themselves if it was a good fit.

      This isn't about OOP vs FP vs IP. This is about having a big toolbox and knowing how to use the tools inside.

      Cheers - L~R

        I didnt, and apologies if i came across as an OOP-advocate on the defense. My point was that eventually, you get the computer to execute some machine instructions - everything else is organization. Higher-Order functions just dont seem that organized.

        In your re-write, you would have to create a new kind of compare package/function combo for every single type of comparison you wanted before you could use it.

        Of course, but the functional approach still requires creating the function. In Perl, if you are using closures to do this, then they too are static comparisons created before you use them. If your using eval, then all bets are off...
        The package is a limit in Perl's implementation. In Java you might approach this by defining the subclasses algorithm during its instanciation, eg:

        // not as useful as closures, not even 'close'... Max max = new Max(){ boolean compare(Object a,Object b){ ... } }; while(...){ .... }
        or more likely, just assume types need to be compared in general
        class Whatever implements Comparable { // used by generic sort (or max) routines public int compareTo(Object o){....} }

        All of these do a similar thing - accomodate abstracting the 'flavour' of an algorithm while allowing the programmer to customize the relevent parts. The Object Oriented ones do so in an explicit, structured way, requiring very little additional documentation or conceptual leaps.

        Really, Im no OOP advocate. But I am inclined to accept the 50 years of engineering experience that has passed since LISP was invented.




        time was, I could move my arms like a bird and...
TIMTOWTDI, synergy
by John M. Dlugosz (Monsignor) on Jun 02, 2009 at 18:49 UTC
    Reading this thread (years after it was started), I reflected on the differences in approaches advocated in the replies. OO, with a derived class used to specialize on the type involved, is certainly the way to go if the objects will be persistent, or if a number of functions are created that work together. I quickly change my design from a callback function to a callback object instead of N callback functions.

    It is also very familiar to people from more ordinary experience, and in many languages it is really the only choice.

    You can also use a class with a virtual function to substitute for a closure if that's what you really wanted. In languages where I wish for the latter, I see that it is indeed a substitution.

    In the case discussed about specializing the algorithm (or object) to compare different kinds of objects in a type-suitable manner, I think of overloading. Virtual functions give you that, but actual overloading of the desired function would be easier. In particular, the max function should know what to do for any kind of argument. In many languages, that's fine, and overloading takes care of it. In Perl, it is difficult specifically for strings, because strings might really be numbers. But avoid the issue and look at comparing Dogs. Clearly the max function can know what to do with Dogs, if Dogs are set up in a standard manner to be ordered.

    In Perl, > is for numbers and gt is for strings. In Perl 6, after is for "canonical ordering" native to the type. So, if we were writing the max function, using after for the comparison will work natively on whichever type was passed.

    In some languages, you would define a template function in such a way that it took two arguments of the same class. Or in this case we want one or more arguments, of the same type. In Perl 6 you can do that:

    sub max (::Type *$first, Type *@rest --> Type) { ... }
    But, we still run into the issue that we don't always want to use canonical comparisons. In the original example, we were not interested in string comparisons, but in comparing the lengths of the strings. So, next take a page from the C++ STL book. Many algorithms take a comparison operator that defaults to the standard ordering. But you can pass in something else!

    Write the max function to take such an extra argument, and still take any number of value arguments, by making this one named.

    sub max ( ::Type *$first, Type *@rest # one or more values in list context :&compare:(Type $, Type $ --> Bool) = &[less] # function, with de +fault --> Type) # returns the same type as the arguments { ... }
    Now you can pass in the function to use. And a small function is fine. It doesn't need to close over any local variables.
    my $comp = { length($^left) > length($^right) } my $result = max @values :compare<$comp>; # use adverb syntax
    And that makes me hope that the built-in max function has such a feature too. In any case, I used a single function to customize the logic. Why a function instead of a whole object? Well, the object itself also customizes the normal comparison operators. This immediate custom thing only needed a single simple function, so why go overboard?

    Now you can also bind parameters to functions to get another function, in a simple way. So you might not have to wrap it in another trivial function. So if I was passing my max function as another argument, but really wanted the customized comparsion, just use &max.assuming(:compare $comp) for that function. The point here is that state information doesn't require "objects", but might be done using closures, or even a tamed specialized form of closure, which is the ability to create new functions on the fly at run time.

    In a wood working or repair project, I may pick out a very sharp chisel, a hand scraper, some sandpaper, a rasp, and play with each one a bit on the work at hand to decide on the final approach. I may end up going to get the dremmel tool instead. Each tool has overlapping capabilities, and often the one at hand is "better" than going to get a different one that might have been the better choice. I spoke with someone yesterday who was scared of TIMTOWDI. He didn't call it that, but explained that having more than one way to do simple things scared him away from Perl. But it's not a Frankenlanguage (well...), it's just like these wood tools: nobody thinks it odd that there are different ways to do it. There are just different tools and techniques.

    For a library design, I would hopefully study the issue and come up with the optimum blend of overloading, derived classes, parameters, and callbacks. For a one-off, I'll just use whatever I grab first.

    —John

      Let me continue by pointing out that in Perl 6 you would not write max as a list operator or function. Rather, write it as an infix (2-argument) function, and the system will automatically generate the matching reduction operator. Or, write the reduction operator yourself if that's more efficient, but use the reduction syntax:
      sub infix:<max> (::Type $left, Type $right --> Type) { return $left after $right ?? $left !! $right; } sub prefix:<[max]> (::Type *$first, Type *@rest --> Type) { ... }
      That leaves off the details of how to make it a chaining operator (I guess max chains through normal association) and declaring its level of precedence and associativity, etc.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perltutorial [id://492651]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (13)
As of 2014-07-23 10:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (139 votes), past polls