The "hashtable problem" in Magpie
Joe Groff
for example, a hashtable with values of type T instantiated in a scope
with one method for hash(T) active that is then passed to a definition
for which a different hash(T) method is in scope? Are values or types
able to capture their original lexical scope for the purposes of
method lookup?
-Joe
Bob Nystrom
This is a great question! This has actually been the single biggest
challenge for me with multimethods in Magpie. I've gone back and forth
over a couple of approaches.
The first approach, like you describe, was that all multimethods were
lexically scoped. However, when you imported a multimethod and then
added a new specialization, that would be added to the same
multimethod *object* that all other modules that imported that
multimethod would share.
So that fixes the hash() problem here. As long as there is a canonical
"first" hash() method that everyone who defines a hash() method
imports first (i.e. likely one defined in the same module as the hash
table type), then this works fine.
What it doesn't fix is cases like this:
// pet.mag
defclass Pet
val name
end
// person.mag
defclass Person
val name
end
// main.mag
import pet
import person
def sayName(who)
print(who)
end
sayName(Pet new())
sayName(Person new())
With my original semantics, the second import is an error because it's
trying to create a colliding multimethod named "name". Ouch.
The current approach I'm playing with is radically simple. Possibly
too simple. By default, all multimethods are globally scoped. Name
collisions are avoided by the fact that they are *multi*methods: you
rely on the parameter patterns for the methods to make them
unambiguous.
In practice, I believe that won't cause any more collisions that in
typical OOP languages. So I figured I'd try that out for a while and
see how it goes.
Thoughts?
Cheers!
- bob
Dave Cleaver
in the classes that make up their argument patterns? Resolve the
arguments then use them to find multimethod instances. I'm just
throwing that out there. I haven't fully thought through the
implications yet.
Dave
Joe Groff
> The current approach I'm playing with is radically simple. Possibly
> too simple. By default, all multimethods are globally scoped. Name
> collisions are avoided by the fact that they are *multi*methods: you
> rely on the parameter patterns for the methods to make them
> unambiguous.
>
> In practice, I believe that won't cause any more collisions that in
> typical OOP languages. So I figured I'd try that out for a while and
> see how it goes.
That makes sense. I was intrigued, though, by the possibility of
intentionally providing alternative implementations for an interface
in a controllable way. When I originally read "methods are lexically
scoped" I was under the impression you could do something like:
---
def printDecimal(Number x)
import decimal # defines print(Number) to print in decimal
print x
end
def printHex(Number x)
import hex # defines print(Number) to print in hexadecimal
print x
end
---
which would be cool, although when you pass datastructures through
different import scopes, it then invites the hashtable problem I
mentioned originally. Do you have any thoughts about how to manage
scoped interface implementations or monkey-patching without confining
values to their original scope?
-Joe
Bob Nystrom
> Reading this I had a thought. What if the multimethods were associated
> in the classes that make up their argument patterns?
I believe that's what Atomo/Atomy does/do. I considered that, but the
problem, of course, is that not all patterns in Magpie are class ones.
You can do:
def (1) isOne
true
end
def (any) isOne
false
end
In both of these, there's no obvious class we could hang the method
off of. For value patterns (1), we could conceivably put the method on
the value's type, but that feels kind of arbitrary to me.
- bob
Bob Nystrom
> That makes sense. I was intrigued, though, by the possibility of
> intentionally providing alternative implementations for an interface
> in a controllable way. When I originally read "methods are lexically
> scoped" I was under the impression you could do something like:
>
> ---
>
> def printDecimal(Number x)
> import decimal # defines print(Number) to print in decimal
> print x
> end
>
> def printHex(Number x)
> import hex # defines print(Number) to print in hexadecimal
> print x
> end
Exactly right. You could, but I broke that use case when I made
multimethods global.
> which would be cool, although when you pass datastructures through
> different import scopes, it then invites the hashtable problem I
> mentioned originally. Do you have any thoughts about how to manage
> scoped interface implementations or monkey-patching without confining
> values to their original scope?
What I'm thinking right now (and it will take implementation and usage
to see how well it works) is that multimethods are globally scoped by
default. That makes things like overriding and duck typing work like
users would expect coming from other languages. It doesn't solve the
extension method / monkey patching use case.
For that case, I'm thinking we will also add support for lexically
scoped methods like Magpie used to have. So when you define a method
at the top level of a module, there would be some syntax to indicate
if you want it to be global, or not. If not, you have to import that
module directly to see the method (and it would completely shadow a
global one of the same name in modules that do import it).
So methods where you want them to be "monkey patched" or where
name+pattern collisions are likely could be made local with the
understanding that you give up overriding (i.e. the hashtable problem)
in return for that safety.
- bob
Dave Cleaver
Bob Nystrom
like questions about what identity means. Is every 2 the same 2? Is
every string "blah" the same one?
- bob
Dave Cleaver
Does magpie use equals to determine a match on value patterns? I can't
remember if that's user overridable. Could I create a class that
"equals" 2?
I've clearly had this on a low simmer in the back of my brain since we
first talked about multimethods and import.
Bob Nystrom
> Yeah I agree.
>
> Does magpie use equals to determine a match on value patterns?
Yes, it does.
> I can't
> remember if that's user overridable. Could I create a class that
> "equals" 2?
Yup. You could also create a value that equaled 2, or any other random
pattern. Just add another specialization for ==.
- bob
Mike Austin
// main.mag
import pet
import person
def printDecimal(Number x)
import decimal # defines print(Number) to print in decimal
print x
end
Maybe I'm not seeing the whole problem?
Mike
Cheers!
- bob
Bob Nystrom
> On Monday, April 2, 2012 4:01:52 PM UTC-7, munificent wrote:
> Could you merge multimethods if they are defined in the same scope, and
> lexically create new multimethods when in a new scope?
That's what it used to do. The tricky part is defining what "merge" means.
> // main.mag
> import pet
> import person
>
> These are being imported into the same scope. They aren't "global", they
> are being added to the current scope, right?
Up until recently, yes, that was how it worked. I even implemented
merging support for a bit and it would do some relatively complicated
shenigans to try to make stuff work.
> This is importing into a new scope, so creates a new multimethod object. If
> I import person here, it will shadow the multimethod outside this scope.
>
> Maybe I'm not seeing the whole problem?
The other use case to keep in mind is Magpie's answer to "overriding"
in other languages. Consider:
// foo.mag
defclass Foo
end
def (is Foo) toString
"I am a Foo!"
end
// main.mag
import foo
print(Foo new())
When you run main.mag, you probably want it to print "I am a Foo".
There's a challenge there. print() is defined in some other module.
Internally, it calls toString. When foo.mag defines a toString
multimethod in its module, how does the module containing print() see
it?
There's some action at a distance here. In single-dispatch languages,
this works by looking up methods on the objects themselves. print()
gets a Foo, so it finds toString directly on that object.
Magpie doesn't work that way, but we want to preserve this
functionality. (You may ask why we do. All I can say was that my first
implementation of multimethods didn't do this and the whole tiny
standard library crashed and burned without it. Overriding like this
is fundamental, I think.)
The way it *used* to work is that when foo.mag defined toString, it
would define it on the same multimethod object that the module that
defines print() had bound to toString. This works fine.
What it breaks is importing colliding names (the first example in this
thread). Between:
1. Overriding
2. Merging (importing methods with the same name and different
patterns from different modules and having them both work)
3. Scoped methods (i.e. two methods with the same names and patterns
in different modules working without collision)
I've spent a ton of time trying to come up with a simple semantics
that gets all three. My first try gave 1 and 3 but broke 2. I
temporarily had a solution that sort of did all three but it was weird
and complex. The current implementation gives 1 and 2 (like almost
every mainstream language). I think we can then layer on 3 pretty
simply by allowing users to define multimethods that do *not* go into
the global method pool. If you import one of those methods it will
*not* give you 1 or 2.
I think that's a reasonable trade-off but it will take some experience
to see how it feels. I do like that it's really simple and ends up
working similar to conventional single-dispatch languages (while
still, of course, allowing actual multiple dispatch!).
- bob
Michael Burgess
Thanks,
Bob Nystrom
> Could you create a context for each scope which has copy-on-(merge/override)
> semantics for methods. So that a method is bound to the global context by
> default then copied into a lexical context when imported there? That should
> give you 1,2,3 effectively ?
Sorry for the loooong delay. I'm not sure I understand what you're
describing here, but I don't think that would help. I believe you need
to copy *up*, and *over* too. For any set of modules that may be
passing objects around to each other (either directly or indirectly),
I think you want them to more or less share the same multimethods that
specialize on those objects.
Some of those sets may be disjoint in a program, but actually figuring
that out is kind of a pain. I had that semantic more or less
implemented once and it felt overly complex.
The latest semantics where top-level multimethods get defined in a
global pool actually seems to work out pretty well. It's trivial to
show that it's no more "global" than every other single-dispatch
language out there and is actually less likely to cause collisions
because you can specialize on all of the arguments.
I think that still leaves a window open for non-global methods later
that must be directly imported and work like extension methods without
too much difficulty too.
- bob