Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Using functional abstraction in Perl

by spurperl (Priest)
on Jul 01, 2005 at 11:09 UTC ( [id://471653]=perlmeditation: print w/replies, xml ) Need Help??

Dear monks,

I'm carrying on with my quest (as told here and here) to understand what makes Lisp so attractive and how we can use/implement these features/paradigms in Perl.

Today, I want to talk about "functional abstraction" - a way to program that I'm most fond of, and that comes naturally in Lisp.

What I mean by functional abstraction is hiding away the implementation details of some data structure, using a set of functions. Consider, for example, the following:

(This is taken from Peter Norvig's PAIP)

I want to use "bindings", that is, key -> value pairs where the key represents a variable and the value represents what this variable is "binded" to. Say I choose the idiomatic Lisp representation of an "association list", which is just a list of key, value pairs (essentially ((key . value) (key2 . value2)).

A Lisp programmer would immediately bang the following functions to abstract the "bindings" concept:

(defconstant no-bindings '((t . t))) (defun get-binding (var bindings) "Find a (var . value) pair in a binding list" (assoc var bindings)) (defun binding-val (bindings) "Get the value part of a single binding" (cdr binding)) (defun lookup (var bindings) "Get the value part (for var) for a binding list" (binding-val (get-binding var bindings)) (defun extend-bidings "Add a (var . value) pair to a binding list" (cons (cons var val) (if (eq bindings no-bindings) nil bindings)))
Now, this may not seem like much, but think about how convenient this approach makes the later programming using bindings. Lisp gurus usually say that "if you want to program X in Lisp, you first create a programming language suitable for things like X and then implement X on top of it", and the code example I showed is an important foundation of this approach (in reality, macros are usually heavily employed for the more hairy tasks).

The current "bindings" implementation is a list of pairs, but the "user" (the higher abstraction level) should know nothing about it. Underneath, the implementation can be changed to hashes, vectors, binary trees, whatever.

The important thing is the definition of a new "data type" - bindings, that can be used on the upper abstraction level just like another type, using all the auxiliary functions provided with it.

In Perl, complex data structures are even more common. Since the introduction of references, many hackers use hashes of arrays of hashes, etc, we even have names for them: AoAoH, HoH, etc.

Choosing to implement "bindings" as a hash table of key -> value pairs, this could be abstracted in Perl as follows:

sub no_bindings { return not keys %{$_[0]}; } sub is_variable { return substr($_[0], 0, 1) eq '?'; } sub get_binding { my ($var, $bind) = @_; defined($bind->{$var}) ? [$var, $bind->{$var}] : undef; } sub binding_val { defined($_[0]) ? $_[0]->{1} : undef; } sub lookup { my ($var, $bind) = @_; return $bind->{$var}; } sub extend_bindings { my ($var, $val, $bind) = @_; $bind->{$var} = $val; return $bind; }

But somehow, I see too much "plain" code around. Code that accesses these data structures directly, assuming their implementation is fixed. I'd wish to see more "functional abstraction" in Perl - new "types" created above all those AoAoHs, with appropriate functions/constants to use them.

In my opinion, such code will be much more understandable, easier to debug and more fun to write. Programming bottom up is fun - at each level you have more power, and since each level is only an abstraction above a lower level, the debugging task is neatly broken into easy-to-handle layers/chunks.

P.S. Naturally, such a thing can be also done with OOP, but many people would prefer not to do it. Lisp gurus often say that Lisp + functional programming techniques "supercede" OOP (although Lisp has a powerful OO library - CLOS).

Replies are listed 'Best First'.
Re: Using functional abstraction in Perl
by BrowserUk (Patriarch) on Jul 01, 2005 at 20:40 UTC

    It's strange, but I'd rather go the other way and define most things that use a name to access a value using the tie interface. Everyone who uses Perl rapidly learns how to use hashes and what methods (exists, each slices etc.) are available to operate upon them.

    That means that if I present a tree or trie or Bag or map or whatever using the tied hash interface, then every Perl programmer familiar with hashes instinctively knows how to use (and read) code that uses this new data type with the familair interface.

    The alternatives, whether OO or functionally abstracted, require them to ponder the documentation to find out how to use them.

    Whilst the tie interface has its limitation, especially with respect to nesting, that (as far as I understand them) are limitations of the implementation rather than the concept, the simplicity of

    tie %trie, 'Tie::Trie'; $trie{ fred } = 10; $trie{ bill } = 20; $trie{ total } = sum values %trie;

    versus

    my $trie = Trie->new(); $trie->add( 'fred', 10 ); $trie->add( 'bill', 20 ); my $temp = sum map{ $trie->lookup( $_ ) } 'fred', 'bill'; $trie->add( 'total', $temp );

    or

    my $trie = maketree(); extend-trie( $trie, 'fred', 10 ); extend-trie( $trie, 'bill', 20 ); ## Does your lisp stuff define a way of iterating the keys? my $temp = sum lookup( $trie, 'fred' ), lookup( $trie, 'bill' ); extend-trie( $trie, 'total', $temp );

    Is self evident (to me).

    If the autovivification of nested tied structures wasn't buggy, I could see myself defining whole OO-style inheritances using this kind of notation. I haven't seen an OO implementation that really worked well with collections of objects rather than individual instances.

    $collection->set( 3, $collection->get( 3 ) + 1 );

    Is just no substitute at all for

    $collection[ 3 ]++;

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.
Re: Using functional abstraction in Perl
by revdiablo (Prior) on Jul 01, 2005 at 17:14 UTC
    But somehow, I see too much "plain" code around. Code that accesses these data structures directly, assuming their implementation is fixed.

    I'd argue that Perl's powerful standard data structures are a good thing and using them "plainly" is usually the best option. The semantics and syntax are well-known. You can look at someone's code, see $values{one} = "somevalue", and almost always know exactly what that will do (of course things are a bit more complicated with tie in the picture, but let's just ignore that for now).

    If everybody always abstracted this kind of thing away in a function, that certainty would rapidly disappear. Sure, you could reasonably assume that store_value(one => "somevalue") is doing something very hash-like. But why should people have to assume, when you can use the direct approach and ensure they will know?

    In my opinion, such code will be much more understandable, easier to debug and more fun to write.

    Perhaps this would make Perl easier to understand and more fun to write for Lisp programmers, but hashes are fundamental things to Perl programmers. They do not usually need to be abstracted away. When they do, it should only be for a good reason. I have to wonder if you would also rather we avoid using scalars and arrays directly, because they could be abstracted into functions that do the same thing?

      The has is only an example, a demonstration of a broader concept. I tried to make it as simple as possible, but often this approach is used to hide more complex data structures than plain hashes. For example, I was referring to HoAoHs or something like that.

      It's OK to use hashes directly. It's not OK, IMHO to use HoAoHs directly, but better abstract this usage away.

      Even in the small example I presented, the implementer of the binding abstraction may decide that (for some reason) it will be better done with an array or a tree (perhaps the typical data will make it more efficient). The abstraction allows to hide it from the "user code".

        The has is only an example, a demonstration of a broader concept.

        Fair enough, but as you can probably see by the replies, your broader concept got lost in the example.

        It's OK to use hashes directly. It's not OK, IMHO to use HoAoHs directly, but better abstract this usage away.

        That would be more reasonable. I certainly would understand more readily if I saw code that did this. Though, I'm still not buying it 100%. I see a lot of code that handles these type of data structures "raw", and I don't think it's really that bad. For instance, I wouldn't blink twice if I saw something like:

        my %thread = ( title => 'Using functional abstraction in Perl', participants => [ { nickname => 'revdiablo', status => 'replying', replies => 3, }, { nickname => 'spurperl', status => 'unknown', replies => 4, }, ... ], ); do_something(with => %thread);
        the implementer of the binding abstraction may decide that (for some reason) it will be better done with an array or a tree

        As BrowserUk aptly explained, this type of thing can be abstracted in a different way in Perl. Rather than forcing users to make function calls that do hash-like things, we can have hashes that trigger function calls. I'm not saying tie is the right option in every case, but it's certainly a nice alternative.

        A quick side note, related to the other thread about OO. I'd like to point out that -- though you may not be willing to accept the terminology -- what you're doing is very OO-ish. You're passing a chunk of data (an "object") around to various functions ("methods"). This is essentially how OO works in Perl; the object is passed as the first argument to the methods. (Of course, there's no inheritance or polymorphism here, but those are only another aspect of OO, not the defining characteristics.)

Re: Using functional abstraction in Perl
by Forsaken (Friar) on Jul 01, 2005 at 20:45 UTC
    in response to your latest remark, this is *exactly* the kind of thing I would use OO Perl for. What I don't see in your meditation is what you think makes a functional Lisp approach actually superior to using an OO Perl approach in this specific instance, aside from the Lisp gurus saying so.


    Remember rule one...
      As I said, this can be done with OO. But in many cases OO is less elegant and is an overkill.

      In the given example, would an OO solution suit better ? A Java-school person would probably define a class for "variable", a class for "binding" and a class for "bindings", all interrelated. So much complexity and code for such simple a mission.

      OO is nice in many situations, but it's not as nice in others. Sometimes the OO technique of "data and the actions taken on it" aren't justified as the data + actions are not as tightly coupled. It is also a leftover from a too strict typesystem, which Perl (like Lisp) fortunately lacks. In Perl a reference can be any data you can imagine. It can be a reference to a scalar, it can be a reference to a HoAoH. Only the functions working on this data know its internal structure. In Java, a class is necessary to define a new type for the data, in Perl there are other (often better) ways.

Re: Using functional abstraction in Perl
by etcshadow (Priest) on Jul 01, 2005 at 14:55 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://471653]
Approved by Mutant
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (3)
As of 2024-03-29 05:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found