Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Adventures in functional Perl programming: the Y combinator 16 Comments More | Login | Reply /

 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.

  • Can you give an example of how this might make some code cleaner or more correct?

    • I had to chuckle at your subject. I certainly know the feeling. The upshot is that you can use this to write recursive anonymous closures (avoiding all side-effects).

      I did this as an excercise. I am tiptoeing into the functional world proper lately, but my stance to it remains ambivalent. Perl isn’t quite the most beautiful language, but I find it a whoooole lot easier to read than any Lisp. I doubt that will ever change, irrespective of practice – I find your lack of syntax disturbing. This

      • You would need to do:
        my $fac = do {
            my $f;
            my $tmp = $f = sub {
                my ( $n ) = @_;
                $n < 2 ? 1 : $n * $f->( $n - 1 );
            };
            weaken($f);
            $f;
        };
        If you just weaken f without the tmp variable, you lose all references to it and it goes away before you have a chance to return it.

        • Ah yes, d’uh.

          But didn’t you mean your do {} block to return $tmp rather than $f? $f is the weak reference used inside the function, while $tmp is the strong reference you pass back out to the surrounding expression, no?

          • I don't think it matters which you return. As long as you are assigning $f to something (as above), there will still be a reference to it (from outside the scope of the do block) after $tmp goes out of scope.

            • Ah, when you copy a weak reference, the new reference is strong. Learn something new every day…

              In any case, the necessary code is rather unwieldy – enough so that I’d rather just use a Y combinator…

      • Not precisely... Weaken works on the variable, not the value. This should work:

        my $f;
        $f = sub { ... $f ... };
        weaken $f;
        return $f;
        • That doesn't work. As soon as you weaken $f, the code it refers to goes away because there are no other references to it. You need to keep another reference to it (hence the temp variable in a previous reply).

    • I have used closures + fixed point combintators several times for traversal functions when a named function just was not appropriate. I didn't know about the Y combinator at the time, but if I had, then I would have been able to clean up my code by using it to package up the closure+fixed-point combo into a single CODE ref.

      But aside from that fringe usage, it is not really that useful in day to day life. In languages like Scheme and Haskell where the purity is highly valued it tends to come in handy, b

  • Is there a reference cycle in there? Am I leaking memory every time I use that? Normally you don't give a closure access to itself because you are permanently allocating that memory.

    my $f;
    $f = sub { $f }; # immortal!
    • No, because it's never $f referring to $f - it's always a new anonymous sub.
      • A new anonymous sub that is identical in form but distinct in identity? Hmm. I suppose I don't usually care about identifying functions and could live with this.
    • Test::Memory::Cycle now checks for this =)

  • I found it was actually easier to deal with the Y combinator if you implement it in terms of the U combinator, which is just your basic fixed point combinator.

    sub U {
        my $f = shift;
        sub { $f->($f, @_) };
    }

    sub Y {
        my $f = shift;
        U(sub {
            my $h = shift;
            sub {
                $f->(U($h)->())->(@_)
            }
        })->();
    }

    I also recentl [perl.org]

    • Yes, those bits of code led to a lengthy (if anemic) discussion about Y and U a few days ago [perl.org].

      I’m still trying to wrap my head around the version you present. I think I am starting to get it, but it’s still confusing (as is any version of the Y combinator, really :-)). With the version I posted, I at least get what’s going on, even though the result is clearly much more complicated than the derivation of Y in terms of U.

      • Ah, I was not aware of the previous conversation. Of course all this is made moot by Perl 6 (IIRC the syntax correctly).

        sub ($n) {
            return 1 if $n < 2;
            return $n * $?SUB.($n - 1);
        }

        - Stevan

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.