Multimethods and Scope

[Dave Cleaver]

So when I was writing the Sieve implementation, I encountered a
problem with redefinition. I had a val in the InfiniteRange class of
the lazy module and a method called from in the chanutils module. The
two modules could not be imported together without renaming one of
them. And yet they both define iterate, next, and current without an
issue.

Reading the code I think I know why and to prove it I did the
following experiment.

First I added two lines to chanutils
import reflection
showDoc("iterate")

then I ran the Sieve code which has the following import order:

import lazy
import chanutils

the result of the showDoc in the scope of chanutils (which does not
import lazy) is:

(this is Indexable) iterate
No documentation
(this is InfiniteRange) iterate
No documentation

So the InfiniteRange version of iterate is visible within chanutils
even though lazy is never imported there. So the reason that iterate
doesn't cause a redefinition error is that the actual multimethod
definition is contained in the scope of the standard library and
modified there by any additional definition.

Is this expected? I realize that fixing that would complicate the
multimethod lookup. Right now you only need to find THE multimethod
definition, process all the Callables to find the ones that match the
call, and then linearize to pick one.

An additional complication is redefinition errors. If you change this
behavior than a multimethod needs to be able to be extended by an
import to allow interface functions like "iterate" to be defined and
imported from other modules.

Dave

[Bob Nystrom]

On Sat, Jun 18, 2011 at 9:17 AM, Dave Cleaver <dscl...@gmail.com> wrote:

So when I was writing the Sieve implementation, I encountered a
problem with redefinition. I had a val in the InfiniteRange class of
the lazy module and a method called from in the chanutils module. The
two modules could not be imported together without renaming one of
them. And yet they both define iterate, next, and current without an
issue.

Congratulations! You found what is probably the most unintuitive part of the language. I don't know if you should feel happy about that or not. But you're bringing it up on the list where I can explain it, which is good.
 

So the InfiniteRange version of iterate is visible within chanutils
even though lazy is never imported there. So the reason that iterate
doesn't cause a redefinition error is that the actual multimethod
definition is contained in the scope of the standard library and
modified there by any additional definition.

Exactly right.
 

Is this expected? I realize that fixing that would complicate the
multimethod lookup. Right now you only need to find THE multimethod
definition, process all the Callables to find the ones that match the
call, and then linearize to pick one.

Yup, it's expected. I'll explain...

There's a couple of scenarios the language needs to support:

-- Overriding methods

Consider this:

    // library.mag
    def write(object)
        val string = object toString
        writeString(string)
    end

    // mycode.mag
    import library
    defclass MyThing
    end

    def (this is MyThing) toString
        "I'm a MyThing"
    end

    write(MyThing new())

Here, we have a write() method defined in some library. It calls toString on its argument. In another module, we define our own class, and then define a toString method on it. When we pass that object to the library, write() needs to see that version of toString even though library doesn't import mycode or know about MyClass.

-- Avoiding name collision

Now consider:

    // a.mag
    def (s is String) exclaim
        print(s + "!")
    end

    // b.mag
    def (s is String) exclaim
        print(s + "!!!")
    end

Here, we have two unrelated modules declaring a method that happens to have the same name. This shouldn't be an error, even when those methods are specialized to the same type.

-- Other languages

Those two scenarios are in opposition. Most OOP languages solve the first one by looking up methods on the receiver object itself. So when the write() method looks for toString, it gets it from object. Each object has a pointer to its class, which in turn is a table of methods.

But that solution breaks the second scenario. Since methods live in a flat namespace on each class, two modules that declare methods with the same name on the same class will collide. That's why monkey-patching is so dangerous.

-- Magpie

Magpie solves the second scenario by not attaching methods to classes. Instead, a method is looked up in lexical scope just like a variable. To make the first scenario work, it makes defining a method work like this:

When you define a method, it looks in that same scope for an existing multimethod with the same name. If it finds one, the method gets tossed in there as another specialization. A multimethod is basically a name and a bag of methods, defined in some scope.

When you import a multimethod from another module, you import the *exact same multimethod object*. So when mycode.mag imports library.mag, it gets a reference to the exact same toString multimethod object that library.mag has. When it then defines toString on MyClass, that specialization gets dumped into the same object that library is using. When library then calls it with an instance of MyClass, it can find that specialization.

So both scenarios work, which is swell! This is, for what it's worth, how Common Lisp works too, I believe.

-- Problems

Where it runs into problems is when you have two unrelated multimethods with the same name and you want to import them into the same module. Even if those methods would never collide at runtime (because they have disjoint sets of patterns), you still have to rename. The most non-obvious example is this:

    // pet.mag
    defclass Pet
        var name
    end

    // friend.mag
    defclass Friend
        var name
    end

    // main.mag
    import pet
    import friend

Here, you'll get an error because the two "name" methods collide. Field getters are just multimethods like any other, so you'd have to rename. The other solution is to let the modules share a method by having one import the other, or both import a third:

    // named.mag
    def name
        /// Gets the name of an object.
    end

    // pet.mag
    import named

    defclass Pet
        var name
    end

    // friend.mag
    import named

    defclass Friend
        var name
    end

    // main.mag
    import pet
    import friend

Now you're fine since there's only a "name" multimethod shared across all of those modules. This works things to a refinement in importing. When you import a multimethod, it's an error to have two multimethods with the same name. But, if both are the exact same multimethod object, that's OK.

I admit this is a little strange, especially coming from an OOP background, but I like that it solves the monkey-patching problem, and it's pretty simple. If you have ideas on how to improvement, I'm definitely interested.

- bob