Ciaran McCreesh’s Blag

Now with 17% more caffeine

Recursive Lambdas in Ruby using Object#tap

Paludis represents an ebuild’s homepage as a dependency-style heirarchy, since PMS allows use-conditional blocks like:

HOMEPAGE="http://example.org/foo gtk? ( http://example.org/foo-gtk )"

Given this, we want a quick way of extracting the URLs using the Ruby bindings. One could of course use a function:

def extract_homepage_recursively(spec)
    case spec
    when AllDepSpec, ConditionalDepSpec
        spec.each { | child | extract_homepage_recursively(child) }
    when SimpleURIDepSpec
        puts spec
    end
end

extract_homepage_recursively(id.homepage_key.value) if id.homepage_key

But that’s rather crude. It would be much nicer to use a lambda, since we don’t need a new name for something we’re only using once.

Unfortunately, recursive lambdas are sometimes rather pesky. There are various solutions, most of which involve passing the lambda as a parameter to itself. In the general case, there’s the infamous Y combinator, but since Ruby has language-level recognition for recursion there’s no need to resort to that kind of silliness. We could just use a variable:

recurse = lambda do | recurse, spec |
    case spec
    when AllDepSpec, ConditionalDepSpec
        spec.each { | child | recurse.call(recurse, child) }
    when SimpleURIDepSpec
        puts spec
    end
end

recurse.call(recurse, id.homepage_key.value) if id.homepage_key

But that’s still a pointless waste of a name. We can do better than that.

Ruby 1.9 adds an Object#tap method, which is rather nifty. Ruby 1.8 doesn’t have it, but we can provide it easily:

if not Object.respond_to? :tap
    class Object
        def tap
            yield self
            self
        end
    end
end

Then, we don’t need a variable or a horrid untyped lambda calculus construct at all:

lambda do | recurse, spec |
    case spec
    when AllDepSpec, ConditionalDepSpec
        spec.each { | child | recurse.call(recurse, child) }
    when SimpleURIDepSpec
        puts spec
    end
end.tap { | r | r.call(r, id.homepage_key.value) } if id.homepage_key
About these ads

8 responses to “Recursive Lambdas in Ruby using Object#tap

  1. Andy Keep November 30, 2008 at 4:46 pm

    If you assign a name to the lambda (as you did in the second example) you also don’t need to pass in the lambda… so you can say:


    rec = lambda do | spec |
    case spec
    when AllDepSpec, ConditionalDepSpec
    spec.each { |child| rec.call(child) }
    when SimpleURIDepSpec
    puts spec
    end
    end


    rec.call(id.homepage_key.value) if id.homepage_key

    Of course then you don’t get to use the nifty tap method :)

  2. Ciaran McCreesh November 30, 2008 at 5:05 pm

    Hrm, I didn’t realise Ruby let you get away with that. But apparently it does, with the rather bizarre result that a = a initialises a with nil.

  3. Andy Keep November 30, 2008 at 10:26 pm

    Yep, lambda’s create lexical closures (sort of) just like in other functional programming languages, so if you name the lexical closure it give you recursive access to it.

    I agree with you on the a = a initializing to a to nil though, since if you instead said x = y and neither were defined you’d get an error (or if just y wasn’t defined).

  4. Ciaran McCreesh November 30, 2008 at 10:33 pm

    The reason I wasn’t expecting it to work is that the local name rec doesn’t exist at the time the lambda is created. This gives an error:


    x = lambda { puts y }
    y = 1
    x.call()

    because y doesn’t exist at the time the lambda is created. But there seems to be a horribly weird special case for assigning an rvalue mentioning the lvalue to an lvalue.

  5. Mike December 2, 2008 at 9:45 pm

    Isn’t the “puts” slightly iffy? Try defining

    class Proc
    def selfcall(*args)
    self.call(self, *args)
    end
    end

    Then you can define and call an anonymous recursive lambda and have it return a useful result.

    Enjoy, Mike

  6. Daniel Spiewak December 3, 2008 at 9:28 am

    Strictly speaking, the Y-combinator doesn’t have to be untyped, it’s just that most type systems aren’t powerful enough to handle it in its conventional, anonymous form. Adding equi-recursive types to System-F gives us this definition (call-by-name since it’s simpler):

    fix = All T . lambda f: T -> T .
    ((lambda x: (Rec X . X -> X -> T) . f (x x))
    (lambda x: (Rec X . X -> X -> T) . f (x x)))

    There you have it: a type-safe Y-combinator. The call-by-value version is left as an exercise to the reader; it isn’t too different. Likewise, conversion to iso-recursive types (much more common in real languages) also requires a little extra effort.

  7. Daniel Spiewak December 3, 2008 at 9:30 am

    Correction:

    sed s/Rec X . X -> X -> T/Rec X . X -> T/g

    Guess I got a little carried away…

  8. Pingback: Dando um “tapa” no Ruby: o m├ętodo tap | Ruby Brasil

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.