One nasty corner case fixed?

[Bob Nystrom]

For me, the nastiest corner of Magpie is that if you import two
classes that each have a field with the same name, they collide and
it's an import error. In other words, you can't do this:

// a.mag
defclass A
var foo
end

// b.mag
defclass B
var foo
end

// c.mag
import a
import b // ERROR

The problem is that field accessors are just multimethods like any
other, which means they are lexically scoped. When you import a class,
you're importing a variable bound to the class object, and a bunch of
methods for each field.

Up until now, you could not import two multimethods with the same
name. This was true even if there weren't any methods in them that
would actually collide. In the above example, you'd never get an
"ambiguous method" error at runtime because the two foo() methods are
specialized to different types (A and B).

I think I have this fixed. Woo!

With the latest code, when you import multimethods, you get your own
local multimethod that merges in all of the methods that you've
imported with that name. So the above example works fine now. The
tricky part is that overriding also needs to work:

// a.mag
def foo()
"a"
end

def callFoo(arg)
foo(arg)
end

// b.mag
import a

def foo("b")
"b"
end

// c.mag
import a
import b

callFoo("b")

Here, b.mag is basically "overriding" a method that it imports in a.
Module 'a' doesn't know about 'b' at all, but when 'c' imports both
and then calls callFoo("b") the expectation is that it would be able
to see the new specialization that 'b' defined for it.

Getting that to keep working while also allowing multimethods to merge
on import was tricky for me to wrap my head around (but strangely
ended up not being that much code). As far as I can tell, this is
still working too.

The idea is that when you import a multimethod, you get your own local
one. But you wire the two together. Any time you add a new method to
either one after that, it will also be added to the other. So in the
above example, when 'b' imports foo from 'a' it also establishes a
link from b's foo back to a's. When it later adds its own foo("b")
specialization, it pushes it back up to 'a' too.

I'll have to beat on this some more to see if it causes other
problems, but so far it's promising. All of the existing tests pass
and some new tests for merging and overriding do too. This is really
exciting to me. Magpie isn't totally novel, but it is unusual in some
ways and I'm always wondering if I'll paint myself into a corner with
it and end up with some critical flaw that unravels the whole
language. This colliding multimethods problem was frustrating enough
in practice to make me wonder if I had. It's a huge relief to think
there may be a solution.

Woo!

- bob

[Joe Groff]

On Fri, Nov 11, 2011 at 11:55 PM, Bob Nystrom <munifi...@gmail.com> wrote:

For me, the nastiest corner of Magpie is that if you import two
classes that each have a field with the same name, they collide and
it's an import error. In other words, you can't do this:

// a.mag
defclass A
   var foo
end

// b.mag
defclass B
   var foo
end

// c.mag
import a
import b // ERROR

Maybe simply importing ambiguous names shouldn't be an error, and it should only be an error if you actually reference an ambiguous name. You could refer to a.foo and b.foo unambiguously by qualified name, or eliminate the ambiguity with the itemized imports suggested by a few other people.

 

The idea is that when you import a multimethod, you get your own local

one. But you wire the two together. Any time you add a new method to
either one after that, it will also be added to the other. So in the
above example, when 'b' imports foo from 'a' it also establishes a
link from b's foo back to a's. When it later adds its own foo("b")
specialization, it pushes it back up to 'a' too.

Making a merged method lexically local to the importer sounds good, but I don't think you want the import to have any effects outside the importer's lexical scope. Linking the imported generics together sounds like spooky action at a distance. Maybe I'm missing something; why is that necessary?

-Joe

[Bob Nystrom]

On Sat, Nov 12, 2011 at 10:05 AM, Joe Groff <arc...@gmail.com> wrote:
>
>
> On Fri, Nov 11, 2011 at 11:55 PM, Bob Nystrom <munifi...@gmail.com>
> wrote:
>>
>> For me, the nastiest corner of Magpie is that if you import two
>> classes that each have a field with the same name, they collide and
>> it's an import error. In other words, you can't do this:
>>
>> // a.mag
>> defclass A
>>    var foo
>> end
>>
>> // b.mag
>> defclass B
>>    var foo
>> end
>>
>> // c.mag
>> import a
>> import b // ERROR
>
> Maybe simply importing ambiguous names shouldn't be an error, and it should
> only be an error if you actually reference an ambiguous name. You could
> refer to a.foo and b.foo unambiguously by qualified name, or eliminate the
> ambiguity with the itemized imports suggested by a few other people.

You could do that, but it ends up looking really weird. In the above
example, using A and B in c.mag would look like:

var a = A new(foo: "a")
var b = B new(foo: "b")

print(a a.foo) // strange
print(b b.foo) // and ugly

Qualifying the names here feels redundant when the user already knows
that the patterns are enough to disambiguate. Disambiguating calls
based on the arguments is core to Magpie so it feels weird that it
matters which modules they happen to come from.

>
>>
>> The idea is that when you import a multimethod, you get your own local
>>
>> one. But you wire the two together. Any time you add a new method to
>> either one after that, it will also be added to the other. So in the
>> above example, when 'b' imports foo from 'a' it also establishes a
>> link from b's foo back to a's. When it later adds its own foo("b")
>> specialization, it pushes it back up to 'a' too.
>
> Making a merged method lexically local to the importer sounds good, but I
> don't think you want the import to have any effects outside the importer's
> lexical scope.

Imports don't. But defining a new method with the same name *after*
you import that name does.

> Linking the imported generics together sounds like spooky action at a distance.

Exactly right. That's the balance I'm trying to find. Strict lexical
scope makes it really easy to reason about stuff. At the same time,
every language out there does have *some* kind of action at a distance
because it's critical to code reuse. (Even Scheme has closures which
means you have objects that can wander around the codebase while still
pointing back to the environment from whence they came.)

> Maybe I'm missing something; why is that necessary?

It's needed to get the same behavior that overriding gives you in
single-dispatch languages. The second example shows this, but it isn't
very clear. Here's a more concrete one. Let's say you want to make a
generic min function. You do something like:

// minimum.mag
def compareTo()
/// Compares the left and right argument. Returns > 0 if the right
argument comes after the left.
end

def (a is Int) compareTo(b is Int)
/// Allow comparing ints.
a - b
end

def min(a, b)
if a compareTo(b) > 0 then b else a
end

The idea is that any type that specializes compareTo() can then be
passed min(). You want to use it for strings, so in your module, you
do:

// string.mag
import minimum

def (a is String) compareTo(b is String)
// code to compare strings...
end

print(min("banana", "apple")) // should print "apple"

If there was no action at a distance, this wouldn't work. minimum.mag
would be oblivious to the compareTo() you defined in string.mag, so
when min() called it with two strings, it doesn't find it and fails.

So the way it works now is that when string.mag imports minimum.mag,
it creates a min() and compareTo() multimethod in string.mag and
populates it with the methods that minimum.mag defines. It also adds a
reference back to minimum.mag in each of them. Later, when string.mag
defines compareTo() on strings, it adds it to that local method, and
it also sees the pointer back to minimum.mag and adds it there too.

In general, I'm trying to minimize non-local shenanigans like this but
a certain amount of it is necessary to make generic reusable code like
this work.

- bob

[Joe Groff]

On Sat, Nov 12, 2011 at 3:13 PM, Bob Nystrom <munifi...@gmail.com> wrote:

// minimum.mag

def compareTo()
   /// Compares the left and right argument. Returns > 0 if the right
argument comes after the left.
end

def (a is Int) compareTo(b is Int)
   /// Allow comparing ints.
   a - b
end

def min(a, b)
   if a compareTo(b) > 0 then b else a
end

The idea is that any type that specializes compareTo() can then be
passed min(). You want to use it for strings, so in your module, you
do:

// string.mag
import minimum

def (a is String) compareTo(b is String)
   // code to compare strings...
end

print(min("banana", "apple")) // should print "apple"

Sorry for being thick, but I'm missing where the magic is necessary here. string.mag imports compareTo from minimum.mag, so it will already extend minimum.compareTo, right? Even if you break it into three modules it will still work:

// comparison.mag

def compareTo

// minimum.mag

import comparison

def min(a,b)

    if a compareTo(b) > 0 then b else a

end

// string.mag

import comparison

def (a is String) compareTo (b is String)

     //...

end

// main.mag

import string

import minimum

"black bears" min "brown bears"

min imports and is defined in terms of comparison.compareTo, string imports and implements comparison.compareTo, and Bob's your uncle. Why wouldn't this just work?

-Joe

[Mike Austin]

I agree - on one hand, it's nice that the problem has been solved, but on the other, it does seem like magic to get it to work.  Do the methods not just merge?

Mike
 

-Joe

[Mathnerd314]

I don't know what you call the collection of multimethods available in a
given file; I call it the "environment" of that file. My idea of how the
call to min works is that:
1) the method is looked up in string.mag's environment, resolving to
minimum.mag's min()
2) minimum.mag's min() is executed in string.mag's environment
3) compareTo is looked up in string.mag's environment, resolving to the
correct method

Does this match up with your implementation?

You can make these environments somewhat first-class by allowing
qualified imports and selective imports, and even more first-class by
considering them to be equivalent to objects that can be passed around.
If you wrote out the above explicitly with first-class environments, it
would be lexically scoped (every method would be of the form "def f(env)
{ env.foo (env.bar, env.baz) }"); instead, the environment is being
implicitly threaded through the method calls, so there appears to be
action at a distance. (This is very similar to how Scheme's closures
work; they implicitly capture their environments and use it when they
are executed - Scheme says this is indeed strict lexical scoping,
although from above you don't appear to agree)

-- Mathnerd314

[Bob Nystrom]

// a.mag
def method("a")
"in a"
end

// b.mag
def method("b")
"in b"
end

// c.mag
import a
import b

print(method("a")) // want "in a"
print(method("b")) // want "in b"

What does "import b" do here? Module c already has a reference to
method() that it's sharing with a. We can't just ditch that reference
and replace it because then the call to method("a") won't work any
more.

Ideally, we want to merge those definitions so that in c we can see
both versions of method(). But if a and c are sharing the same
multimethod object, when we merge in the stuff from b, then a will see
it too which is probably not what we want.

- bob

[Bob Nystrom]

On Sat, Nov 12, 2011 at 3:43 PM, Mike Austin <mike.aus...@gmail.com> wrote:
> I agree - on one hand, it's nice that the problem has been solved, but on
> the other, it does seem like magic to get it to work.  Do the methods not
> just merge?

The tricky question is what does it mean to merge two multimethods
when either or both of them may also be shared across multiple
modules?

There's two simple mental models I can think of for importing and
extending multimethods. In both of these models you can think of a
"multimethod" as a bag that has a name and holds a collection of
method specializations. Given an argument, it will pick the best
method from the collection.

1. Shared multimethod object.

In this model, when you import a multimethod blah() from module "foo"
into "bar", both foo and bar will share a reference to the exact same
object. When either of those modules adds another specialization for
blah(), the other sees it too since it's going straight into the same
object they both share.

If "bar" later imports another blah() from "baz", there's a problem.
bar already has a blah() multimethod (that it shares with foo). What
do we do with that one? We can't just ditch it because bar is
presumably using it. I don't think we want merge the two because that
would mean that foo would see baz's methods which seems wrong.

This is how Magpie worked until a couple of days ago.

2. Module-local multimethods.

In this module, each module owns its own multimethod for a given name.
When you import blah() from "foo" into "bar", bar gets its *own*
blah() multimethod and we copy all of the method's from foo's one and
dump them into bar's. No two modules can ever see the same multimethod
object. If bar later imports blah() from "baz", we can merge in those
methods by just dumping the ones from baz into bar's already existing
blah() multimethod. This doesn't affect foo at all, which is good.

Both models are nice and simple. Each is good for one use case but
doesn't handle the other. Shared multimethods make overriding work
(when bar defines a new blah(), foo gets it too). Module-local
multimethods make merging work (when bar imports blah() from both foo
and baz, we can just dump all of their methods into bar's one).

But I want *both* to work. So the current model is, unfortunately,
more complex than either of those, but it's also more expressive. It's
a hybrid of the two:

Each module does have its own local multimethod. When you import, we
just copy the methods from the imported module into the module's local
multimethod. So merging just works without any difficulty.

Then we extend that a little bit to also make overriding work. The
refinement is that if you then define a specialization of a method,
we'll also push it back over to the modules where you originally
imported that multimethod from. So if bar imports blah() from "foo"
and "baz", when it later defines a new blah() specialization, we'll
push it back to those modules too so that they see it.

Hopefully that makes some sense? It still feels a bit fishy, but I
think it's a step in the right direction. At the very least, I'm
convinced that neither of the two above simpler solutions is
expressive enough.

- bob

[Bob Nystrom]

There's two levels of lookup here: finding the multimethod itself
(i.e. the thing about to the name "min") and then finding which
specialization within that best matches the argument. The first part
just uses straight lexical scoping. The second is the multimethod
dispatch.

> 2) minimum.mag's min() is executed in string.mag's environment

Yup. Every method closes over the environment where it was defined,
regardless of where you invoke it from.

> 3) compareTo is looked up in string.mag's environment, resolving to the
> correct method

Nope. min() is defined in minimum.mag and closes over that
environment. Since multimethod names are lexically scoped, it looks
for compareTo() in minimum.mag.

This is where the difficulty comes in. How do we make it so that the
compareTo() in minimum.mag sees the definition we added in
strings.mag?

> You can make these environments somewhat first-class by allowing qualified
> imports and selective imports, and even more first-class by considering them
> to be equivalent to objects that can be passed around. If you wrote out the
> above explicitly with first-class environments, it would be lexically scoped
> (every method would be of the form "def f(env) { env.foo (env.bar, env.baz)
> }"); instead, the environment is being implicitly threaded through the
> method calls, so there appears to be action at a distance. (This is very
> similar to how Scheme's closures work; they implicitly capture their
> environments and use it when they are executed - Scheme says this is indeed
> strict lexical scoping, although from above you don't appear to agree)

I agree that Scheme has strict lexical scoping. "Action at a distance"
is a bit fuzzy but my intent was to show that even a language like
Scheme still has some non-local effects when it comes to variable
references, since a closure retains a reference to its environment and
can be passed around. The closest language I can think of with very
very little action at a distance with C, and you end up reinventing it
there by making little "objects" that contain function pointers and
the captured arguments you want to pass to them.

- bob

[Mathnerd314]

I'm just going to throw (pseudo-)code at you:

class Environment {

// Map from qualified name to collection of methods (Multimethod == List<Method>)

private Map<QualifiedName, List<Method>> e;

// Examples of environments

// env("minimum.mag") -> {minimum.min -> [min(_,_)], minimum.compareTo -> [compareTo(), compareTo(Int, Int)]}

// env("string.mag") -> {minimum.min -> [min(_,_)], minimum.compareTo -> [compareTo(), compareTo(Int,Int),compareTo(String,String)], string.foo = [...], string.bar = [...], ...}

// These can be cached after a module is loaded.

// The "lookup" I referred to above
List<Method> lookup(QualifiedName qn) {

return e.get(qn);

}
}

>
>> 2) minimum.mag's min() is executed in string.mag's environment
> Yup. Every method closes over the environment where it was defined,
> regardless of where you invoke it from.

This doesn't make any sense, so more Java (pseudo-)code: (BTW I always
consider writing code to be explaining things to a really dumb person;
is your intelligence feeling insulted yet? :-) )

class Method {

private Expression expr;

private List<UnqualifiedName> argNames;

Value apply(Environment env, List<Argument> args) {

e = substituteArguments(argNames, args, expr);

return e.eval(env);

}

}

abstract class Expression {

abstract Value eval(Environment e);

}

class Apply extends Expression{

private Expression method;

private List<Expression> args;

Value eval(Environment e) {

List<Value> evaluatedArguments = map(_.eval(e), args);

List<Method> ms = (List<Method>) method.eval(e);
// The "resolve" step I referred to above
return executeAppropriateMethod(ms, e, evaluatedArguments);

}

}

class Identifier extends Expression {

private QualifiedName qn;

Value eval(Environment e) {

return e.lookup(qn);

}

}

A trace of the execution:

apply(<main>, env("string.mag"), [])

<Continue> <Breakpoint hit>
env("string.mag").lookup('minimum.min')
<Continue> <Breakpoint hit>
apply(<Method min(_,_)>, env("string.mag"), ["apple","banana"])
<Continue> <Breakpoint hit>
env("string.mag").lookup('minimum.compareTo')
<Continue> <Breakpoint hit>
apply(<Method compareTo(String,String)>, env("string.mag"), ["apple","banana"])
...
"apple"

As you can see, env("minimum.mag") is never used (except implicitly since env("string.mag") is a superset of env("minimum.mag") )

>> 3) compareTo is looked up in string.mag's environment, resolving to the
>> correct method
> Nope. min() is defined in minimum.mag and closes over that
> environment. Since multimethod names are lexically scoped, it looks
> for compareTo() in minimum.mag.

Lexical scoping is about naming and ensuring that names are always
qualified, not about which environment things are run in. Since you want
to allow extensible multimethods, the environment cannot be closed. Thus
it needs to be passed around as a parameter during the course of evaluation.

>
> This is where the difficulty comes in. How do we make it so that the

(call to)

> compareTo() in minimum.mag sees the definition we added in
> strings.mag?

By making it look the definition up in the environment you passed to
apply()!

>
>> You can make these environments somewhat first-class by allowing qualified
>> imports and selective imports, and even more first-class by considering them
>> to be equivalent to objects that can be passed around. If you wrote out the
>> above explicitly with first-class environments, it would be lexically scoped
>> (every method would be of the form "def f(env) { env.foo (env.bar, env.baz)
>> }"); instead, the environment is being implicitly threaded through the
>> method calls, so there appears to be action at a distance. (This is very
>> similar to how Scheme's closures work; they implicitly capture their
>> environments and use it when they are executed - Scheme says this is indeed
>> strict lexical scoping, although from above you don't appear to agree)
> I agree that Scheme has strict lexical scoping. "Action at a distance"
> is a bit fuzzy but my intent was to show that even a language like
> Scheme still has some non-local effects when it comes to variable
> references, since a closure retains a reference to its environment and
> can be passed around.

I checked Wikipedia - Action at a distance is when you have some change
in the behavior of a method in some file that didn't come from anything
obviously associated with that method. (like quantum entanglement -
there's no [classically] possible way to have an interaction, yet
somehow there is)

I wouldn't call switching around environments "action at a distance";
it's implied by the semantics and somewhat natural. I would be rather
suspicious, however, if importing a file for one method somehow broke a
call in another method; this is why I like method-local imports rather
than file-wide imports.

You might also be confusing action at a distance with side effects,
which Scheme does indeed have. (State, i.e. environments, are indeed a
side effect, since one can implement them as a Haskell monad)

> The closest language I can think of with very
> very little action at a distance with C, and you end up reinventing it
> there by making little "objects" that contain function pointers and
> the captured arguments you want to pass to them.

C isn't memory safe, so it has actions at a distance such as buffer
overflows, heap attacks, .... (which makes it very difficult to debug!)

But I think you're right otherwise; it's basically a bit-shuffling
language, with no fancy layers on top that allows changes in semantics.

-- Mathnerd314

[Bob Nystrom]

If I'm reading your code right, what you're proposing would lead to
this behavior:

// a.mag
var _text = "in a"

def say()
print(_text)
end

// b.mag
import a
var _text = "in b"
say() // in b!

do
val _text = "block scope local"
say() // block scope local!
end

That's not at all what I (or you, or anyone) would want. It's sort of
like dynamic scoping, but not really. It's definitely not lexical
scoping.

> Lexical scoping is about naming and ensuring that names are always
> qualified, not about which environment things are run in.

It's exactly about the environment that things are run in (or more
importantly, that names are resolved in). It says that the variable
that an identifier refers to can be determined statically just by
examining the program text (hence "lexical", from the Latin for
"word").

Unless I'm reading your code wrong your proposal means that not only
can identifiers not be resolved lexically, but they can change at
runtime.

>>
>> This is where the difficulty comes in. How do we make it so that the
>
> (call to)
>>
>> compareTo() in minimum.mag sees the definition we added in
>> strings.mag?
>
> By making it look the definition up in the environment you passed to
> apply()!

But then it loses its *own* environment. You've ditched the closure.

- bob

[Mathnerd314]

On 11/14/2011 12:23 AM, Bob Nystrom wrote:
> If I'm reading your code right, what you're proposing would lead to
> this behavior:
>
> // a.mag
> var _text = "in a"
>
> def say()
> print(_text)
> end
>
> // b.mag
> import a
> var _text = "in b"
> say() // in b!
>
> do
> val _text = "block scope local"
> say() // block scope local!
> end
>
> That's not at all what I (or you, or anyone) would want. It's sort of
> like dynamic scoping, but not really. It's definitely not lexical
> scoping.

QualifiedNames are qualified very strongly, down to the scope they're
defined in. From the example you gave, you're redeclaring variables
instead of modifying them, so they would be different QualifiedNames
(a._text versus b._text versus b.<block scope #1>._text), and thus say()
would always use a._text and print "in a".

The implementation strategy is indeed very similar to dynamic scoping,
but I've rigged the game so that the only names that collide will be
ones that would collide if using static (lexical) scoping. It's static
name resolution but dynamic name binding. Anyways, you definitely want
it in Magpie. :-) It's the only strategy that lets multimethods be extended.

>
>> Lexical scoping is about naming and ensuring that names are always
>> qualified, not about which environment things are run in.
> It's exactly about the environment that things are run in (or more
> importantly, that names are resolved in). It says that the variable
> that an identifier refers to can be determined statically just by
> examining the program text (hence "lexical", from the Latin for
> "word").
>
> Unless I'm reading your code wrong your proposal means that not only
> can identifiers not be resolved lexically, but they can change at
> runtime.

Practically, they could, but as long as there's no escape hatch from the
renamer (the thing that goes from bare identifiers to QualifiedNames),
there's no way to.

>
>>> This is where the difficulty comes in. How do we make it so that the
>> (call to)
>>> compareTo() in minimum.mag sees the definition we added in
>>> strings.mag?
>> By making it look the definition up in the environment you passed to
>> apply()!
> But then it loses its *own* environment. You've ditched the closure.

At runtime, there's only going to be one environment for the duration of
the program. Environments are "big"; they are large enough contain every
QualifiedName used during the execution of the program. So they're
basically global, except that you might be using a single interpreter to
run multiple programs at once and then you'd want multiple environments
to keep their executions separate.

-- Mathnerd314