Re: MMD and VTABLE_find_method
Leopold Toetsch wrote:
pmclass default abstract noinit {
PMC* add (PMC* left, PMC* right) {
PRESERVE_CONTEXT;
add_func = mmd_find(__add...) // via VTABLE_find_method
and here it becomes horribly slow and weird. You are already in one
add. What do you want to find here?
I took your example code, almost word for word, and added approximately
three, count them three, machine instructions (not Parrot instructions,
not C statements, but machine instructions) to the path length, and now
adjectives like horribly slow and wierd come out.
It looks like this mailing list will not be suitable for civilized
discussion until Dan gets back.
Meanwhile, all existing Python tests pass:
http://www.intertwingly.net/blog/2004/12/25/Python-on-Parrot-test-status
Merry Christmas.
- Sam Ruby
Re: MMD and VTABLE_find_method
Sam Ruby writes: In the general case, a call to a subroutine with three arguments can have four possibilities: anywhere from zero to three arguments may be involved in the dispatch. I also read this to say that whatever code is generated by a subroutine call is independent of the number of arguments involved in the dispatch. If you read this differently, perhaps we can get a ruling from the Perl6 language folks. If I am correct, this will have the nice side benefit that any such methods can be invoked transparently by all languages. A ruling: The caller might not know that it's calling a multimethod at all at compile time, much less how many invocants it has. A PMC that hides the fact that we're doing a multimethod seems like the best way to allow multiple language semantics. If we were OO designers, I doubt we would have thought of any other way. Luke
MMD and pdd03 (was: MMD and VTABLE_find_method)
Luke Palmer wrote:
A ruling: The caller might not know that it's calling a multimethod at
all at compile time, much less how many invocants it has.
This seems to invalidate calling conventions aka pdd03, *if* multi subs
with native types are allowed. The register setup of calling these two
multisubs is identical:
multi sub infix:+(int $l, Int $r) {...}
multi sub infix:+(Int $l, int $r) {...}
There is no way to detect the ordering of call arguments (I5, P5).
A PMC that hides the fact that we're doing a multimethod seems like the
best way to allow multiple language semantics. If we were OO designers,
I doubt we would have thought of any other way.
Yes, basically. The question is which PMC. On the surface of a function
call there is (in Python assembly terms):
LOAD_NAME foo
CALL_FUNCTION
where the LOAD_NAME searches (lexicals, globals, builtins) for the name
foo. The question is, if Perl6 (or Parrot) can create a multi sub PMC
with the short name (S12) foo, or if only the long names exist.
The problem I see is namespace pollution, as it is totally valid that a
locally defined subroutine foo hides outer multi subs of that name.
So, where does that OOish dispatcher PMC jump in?
Luke
leo
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote:
Sam Ruby wrote:
First, a few things to note: the semantics of add vary from language
to language. In particular, add is not guaranteed to be commutative
in Python (think string addition).
Yes, of course.
It seems obvious, but it leads to surprises. Example:
'1' + '2'
The result will depend on what the actual types are of the inputs
perhaps even what the context is of the caller.
As my proposal is primarily focused on where the logic is placed in
the system, not how it works, I'll like to use your proposal
http://xrl.us/egvp as a starting point. Just to make sure that I
don't mischaracterize your proposal, can you take a look at the
attached and either agree that it represents a reasonable first
approximation of what you had in mind, or modify it so that it is?
It's a reasonable respresentation, yes. Finding the right functions is
more complex, though, as described in my proposal.
I'd just outline the functionality of the add opcode like this:
inline op add (out PMC, in PMC, in PMC) :base_core {
PRESERVE_CONTEXT;
add_func = mmd_find(__add...) // via VTABLE_find_method
REG_PMC(5) = $2;
REG_PMC(6) = $3;
VTABLE_invoke(interp, add_func, 0);
res = REG_PMC(5);
RESTORE_CONTEXT;
$1 = res;
}
Cool see below.
the basics are:
* the destination PMC $1 is created by the opcode
I don't want to dwell on this point, but it would be rather handy if the
caller were able to pass in an object which was responsible for
producing the desired destination PMC on request.
It would accept requests like give me an Integer and would respond
with things like here's a PyInt.
At the moment, we have a fairly good approximation of this with
VTABLE_morph. Make yourself a BigInt...OK, (P.S. I'm really a PyLong).
This won't work for languages which have a notion of singletons, unless
the language uses a double-reference system... like Ruby and Perl 5 do
today (per Dan's previous statements).
* no other registers are changed, nor the context
* finding the __add method uses VTABLE_find_method to
find all possible __add methods and a distance
function to get the best match
* the best matching function is invoked
The word best here should be setting off alarm bells in everybody's
head. What is the chance that we can get Larry, Guido, Matz, Brenden
and others to agree on such a thing? Particularly when they can't even
agree on what + means when dealing with strings (actually, in the list
above, Larry is the lone hold out... ;-) (and apologies to all involved
for personifying this))
Once that's done, I'll sketch out all of the changes required to
enable Perl and Python to each have their own separate semantics for
this operation, and yet be able to have meaningful interop when it
comes to adding a PerlInt and a PyInt, or vice versa.
OK, here's what the proposal would look like, hypothetically assuming
that all of your proposed changes get in:
inline op add (out PMC, in PMC, in PMC) :base_core {
$1 = VTABLE_add(interp, $2, $3);
}
pmclass default abstract noinit {
PMC* add (PMC* left, PMC* right) {
PRESERVE_CONTEXT;
add_func = mmd_find(__add...) // via VTABLE_find_method
REG_PMC(5) = left;
REG_PMC(6) = right;
VTABLE_invoke(interp, add_func, 0);
res = REG_PMC(5);
RESTORE_CONTEXT;
return res;
}
}
That's it. From an external point of view, add is called in exactly the
same way. Whether MMD is involved or not, the caller shouldn't know and
shouldn't care. A similar approach can be taken in the more general
case of the foo subroutine that we were talking about previously... no
need to introduce new opcodes or a change to the Perl6 syntax.
Now, lets take a look at a hypothetical PyString implementation of add:
pmclass PyString extends PyObject dynpmc group python_group {
PMC* add (PMC* right) {
if (!VTABLE_does(right, const_string(STRING))
real_exception(INTERP, NULL, E_TypeError,
TypeError: cannot concatenate '%Ss' and '%Ss'
objects,
SELF-vtable-whoami, right-vtable-whoami);
PMC *dest = pmc_new(INTERP, dynclass_PyString);
PMC_str_val(dest) = string_concat(INTERP,
PMC_str_val(SELF), VTABLE_get_string(INTERP, value), 0);
return dest;
}
}
Note: no MMD. In fact, no need to preserve context. Either the second
parameter does string, or a Type error is thrown. This would
presumably interoperate with PerlString, but not with PerlInt. How
would this work when called from Perl instead? Well, PyInt need to be
based on from Parrot's Integer, and the MMD implementation that Perl
settles on will need to be aware of inheritance.
Now let's look at a second hypothetical example:
pmclass PyClass dynpmc group python_group {
PMC* add (PMC*
Re: MMD and VTABLE_find_method
Sam Ruby wrote:
[ a lot - I'll split answers ]
Leopold Toetsch wrote:
Sam Ruby wrote:
It seems obvious, but it leads to surprises. Example:
'1' + '2'
The result will depend on what the actual types are of the inputs
perhaps even what the context is of the caller.
Ehem, given that and ... (from below)
Note: no MMD.
and VTABLE_add()
it seems that you are still missing the power of MMD. Just because the
result and semantics of the add operation are different, we are doing MMD.
The MMD dispatch looks at the left and right types of the infix
operation, locates a function that matches and call the function.
You can look at it like a matrix:
PyStringPyIntPyNum Integer ...
--
PyString py_add_sadd_err add_err add_err
PyInt add_err add_i add_n add_i
PyNum add_err add_n add_n add_i
Integer add_err add_i add_n add_i
...
There are four incarnation of the add multi sub:
py_add_s := concat (function name Parrot_PyString_add_PyString)
add_err:= emit a TypeError : cannot concat ...
add_i := integer add (Parrot_Integer_add_Integer)
add_n := float add (Parrot_Float_add_Float)
So what actually need to exist in Python scalar classes is a constructor
and:
in pystring.pmc
pmclass PyString extends PyObject extends String {
METHOD PMC* add(PMC *right) {
MMD_PyString: { ... do a concat }
MMD_DEFAULT: { ... emit TypeError }
}
}
in pyint.pmc (and pyfloat analog)
pmclass PyInt extends PyObject extends Integer {
// inherit add
}
The METHOD specifier shall install all given variants with
VTABLE_add_method, i.e. register the NCI functions so that
VTABLE_find_method can locate the entry.
But the matrix implementation doesn't work, because it's too static,
inheritance can't be described easily (or not at all) in terms of it.
As my proposal is primarily focused on where the logic is placed
And that's the main problem of your approach. You are forgetting MMD.
inline op add (out PMC, in PMC, in PMC) :base_core {
$1 = VTABLE_add(interp, $2, $3);
}
With that you are already calling an add function that depends on the
left type - this is not MMD and it forces the left operand to handle
all possible cases of add/concat with int/float/string ... This is
exactly the point, where interoperbility is violated. The left type
doesn't know all possible right types to deal with them correctly.
With that you get a cascade of ifs that handle the different types. We
had that earlier. It was discarded in favor of MMD.
pmclass default abstract noinit {
PMC* add (PMC* left, PMC* right) {
PRESERVE_CONTEXT;
add_func = mmd_find(__add...) // via VTABLE_find_method
and here it becomes horribly slow and weird. You are already in one
add. What do you want to find here?
REG_PMC(5) = left;
REG_PMC(6) = right;
VTABLE_invoke(interp, add_func, 0);
and redispatching - no and no - sorry.
I know that Leo keeps telling me that I need to map __add__ to __add at
compile time, but there are tests like t/pie/b3.t that indicate that
such tests need to be made at runtime.
When I say, that __add__ maps to Parrot's __add at compile time, it
doesn't preclude that you have to do something at runtime too. E.g. you
emit code for:
foo.__add__ = myadd(or __dict__.__add__)
then the user is installing an overridden version of the add method.
You have to know that, or you can't do the right thing when it comes to
foo + x
So you have to call
VTABLE_add_method(class_of_foo, __add, myadd).
If you don't do that, VTABLE_find_method(... __add) will fail later or
return the wrong function.
But and that's the big difference of our porposals: nothing more has to
be done. The MMD dispatch at the runloop (and not inside every class)
handles the selection of the correct subroutine, being it a C function
(wrapped into NCI) or PASM/PIR user code. This just doesn't matter and a
class doesn't need to know about that.
Allowing me to subclass, extend, and replace how methods like add works
gives me a place to insert any logic I find necessary.
Which logic would you insert in add(PyInt, PyInt)? What for?
... And, when I find
out that something is not as necessary as I once thought, it can be
removed just as easily.
No because you are duplicating the method dispatch. You can't remove
that. And that's the big problem with your approach - besides that it'll
be around a factor 10 slower then the dispatch at the opcode level like
now. We can't afford a factor ten in speed decrease.
Arguements can be made against each individual example (perhaps I could
create a small function that raises Type Error and register it dozens of
times to handle the PyString.add example, and yes,
Instead of the check (if right.type isnt a PyString) you are already in
the MMD method Py_String_add
MMD distance (was: MMD and VTABLE_find_method)
Sam Ruby wrote: Leopold Toetsch wrote: * finding the __add method uses VTABLE_find_method to find all possible __add methods and a distance function to get the best match * the best matching function is invoked The word best here should be setting off alarm bells in everybody's head. What is the chance that we can get Larry, Guido, Matz, Brenden and others to agree on such a thing? Particularly when they can't even agree on what + means when dealing with strings (actually, in the list above, Larry is the lone hold out... ;-) (and apologies to all involved for personifying this)) Finding the best matching function can be HLL dependent, there can be different schemes, even user code that influences it. But I think that using the function with a minimum value of left.class_search_depth**2 + right.class_search_depth**2 should do it. WRT the '+' operation: You just need a PyString_add_* and PyString_add_PyString (the same with PyList). If the class isa PyString (which includes derived classes), one of these methods will be called. It just needs a working find_method implementation not much more. leo
add (out PMC ... (was: MMD and VTABLE_find_method)
Sam Ruby wrote: Leopold Toetsch wrote: the basics are: * the destination PMC $1 is created by the opcode I don't want to dwell on this point, but it would be rather handy if the caller were able to pass in an object which was responsible for producing the desired destination PMC on request. It would accept requests like give me an Integer and would respond with things like here's a PyInt. At the moment, we have a fairly good approximation of this with VTABLE_morph. Make yourself a BigInt...OK, (P.S. I'm really a PyLong). This won't work for languages which have a notion of singletons, unless the language uses a double-reference system... like Ruby and Perl 5 do today (per Dan's previous statements). Python's None is a singleton. False and True should be, but for compatiblity reasons this wasn't changed (yet). There's old code around that does: False, True = 0, 1 Anyway disallowing singletons as return results is major drawback of the current scheme. Second: we have two different function signatures: overridden methods are returning new PMCs. Internal methods currently get the destination PMC. We'd need glue code to translate between these two schemes. And there are of course performance considerations: Px = new Undef add Px, Py, Pz If add is overridden, we are preconstructing a PMC for nothing. That increases pressure on GC. And morphing the Undef (or whatever) is a rather expensive operations - look at pmc.c:pmc_reuse(). WRT constructing the new type: Given that PyInt_add_PyInt is inherited from the Integer PMC, it should work if we do: dest = pmc_new(interp, SELF-vtable-base_type); VTABLE_set_integer_native(interp, dest, sum); return dest: When e.g. a BigInt is created due to overflow, we could to dest = pmc_new(interp, SELF-vtable-base_type); VTABLE_set_bigint(interp, dest, left); VTABLE_inplace_add(interp, dest, right); // d += r return dest; Additionally it wouldn't harm, if there is a list of basic types per supported language, so that a destination of the HLL's flavor can be constructed. leo
integer interning (was: MMD and VTABLE_find_method)
Sam Ruby wrote: Oh, well, back to coding. BTW, I'm committing the change to opcode issame to make use of the similarly named VTABLE entry as I need this in order to pass a test. Oddly, in Python: (1,2) == (1,2), (1,2) is (1,2) (True, False) 1+2 == 1+2, 1+2 is 1+2 (True, True) But: 101+2 == 101+2, 101+2 is 101+2 (True, False) Just forget it. That are CPython internals (int interning, string interning). No real code is depending on that. Even Python people often give wrong answers on c.l.p, where the actual limits of interned integers are. If there is a test for that, drop that test (one was testing the exact amount of compare operations in sort() - same weirdness). - Sam Ruby leo
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote: PyStringPyIntPyNum Integer ... -- PyString py_add_sadd_err add_err add_err PyInt add_err add_i add_n add_i PyNum add_err add_n add_n add_i ^ Sorry, typo add_n of course. leo
Re: MMD and VTABLE_find_method
Sam Ruby wrote:
Leopold Toetsch wrote:
A foo PMC could represent an entire row in a two dimensional MMD, or
an entire plane in a three dimensional MMD, ... etc.
What does it mean: represent a row...? What about the namespace
pollution? Again: where does this hypothetical MMD PMC come from?
A Perl6 compiler could translate the above to:
87 find_lex P5, a
90 find_lex P6, b
93 find_lex P7, c
96 find_global P0, foo
108 set I0, 1
111 set I1, 0
114 set I2, 0
117 set I3, 3
120 set I4, 0
126 invokecc
You seem to like double dispatching :-)
The foo PMC could know how many of the arguments are relevant for MMD
dispatch. Should only the first two arguments be relevant, this code
could be as simple as:
void* invoke(void* next) {
...
if (cache-type == (Py-vtable-base_type
16|Pz-vtable-base_type)
return VTABLE_invoke( cache-function );
...
}
Where ist the Ccache coming from? Please read again my articles WRT
*inline* cache.
Where does this hypothetical MMD PMC come from? Where is it created?
The opcode is just:
add Px, Py, Pz
Py or Pz can be plain PyInts or Integers. Where does that MMD PMC come
from?
Once MMD is solved connecting it up to the PerlScalar PMC (for example)
would be rather straightforward. Syntax like the following would result
in an appropriate entry being added to the MMD dispatch table:
How do you connect MMD to the scalar PMC? And to which scalar PMC?
Which MMD dispatch table?
multi sub infix:+ (Us $us, Us $ustoo) {...}
The Parrot_PerlScalar_add function (which would revert back to being a
vanilla vtable) would know about the portion of the MMD dispatch table
that is relevant to Perl scalar add operations, and invoke it.
So Perl is unable to add an integer that originated from Python code.
Sam that all doesn't play together.
(Note: one thing that hasn't been discussed to date is how registers
will be handled. The current add opcode doesn't have any side effects)
That's obvious: overloaded operations don't have side effects WRT
register usage, and the current implementation in Parrot core preserves
all registers.
- Sam Ruby
leo
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote: Sam Ruby wrote: Leopold Toetsch wrote: A foo PMC could represent an entire row in a two dimensional MMD, or an entire plane in a three dimensional MMD, ... etc. What does it mean: represent a row...? What about the namespace pollution? Again: where does this hypothetical MMD PMC come from? Since you are going to snip away everything, let's start all over. First, a direct quote from http://www.perl.com/pub/a/2004/04/16/a12.html?page=10: As we mentioned, multiple dispatch is enabled by agreement of both caller and callee. From the caller's point of view, you invoke multiple dispatch simply by calling with subroutine call syntax instead of method call syntax. It's then up to the dispatcher to figure out which of the arguments are invocants and which ones are just options. (In the case where the innermost visible subroutine is declared non-multi, this degenerates to the Perl 5 semantics of subroutine calls.) This approach lets you refactor a simple subroutine into a more nuanced set of subroutines without changing how the subroutines are called at all. That makes this sort of refactoring drop-dead simple. (Or at least as simple as refactoring ever gets...) In the general case, a call to a subroutine with three arguments can have four possibilities: anywhere from zero to three arguments may be involved in the dispatch. I also read this to say that whatever code is generated by a subroutine call is independent of the number of arguments involved in the dispatch. If you read this differently, perhaps we can get a ruling from the Per6 language folks. If I am correct, this will have the nice side benefit that any such methods can be invoked transparently by all languages. None of this precludes a Polymorphic Inline Cache. Or Multidimensional Multimethod Dispatch. Or 30 to 70% performance improvements. But it does constrain where the logic needs to be placed. And it does rule out syntax changes and using a different opcode for invoking MMD subroutines than non-MMD subroutines. - Sam Ruby
Re: MMD and VTABLE_find_method
Sam Ruby wrote: First, a direct quote from http://www.perl.com/pub/a/2004/04/16/a12.html?page=10: Please let's stay at the basics. Please describe your counter proposal for a very elementary add Px, Py, Pz operation. There's really no need to procede to Perl6 objects, if we can't even find a common interoperating implementation that is suited for Parrot's target languages. And it does rule out syntax changes and using a different opcode for invoking MMD subroutines than non-MMD subroutines. Yep. - Sam Ruby leo
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote:
Sam Ruby wrote:
First, a direct quote from
http://www.perl.com/pub/a/2004/04/16/a12.html?page=10:
Please let's stay at the basics. Please describe your counter proposal
for a very elementary
add Px, Py, Pz
operation.
There's really no need to procede to Perl6 objects, if we can't even
find a common interoperating implementation that is suited for Parrot's
target languages.
And it does rule out syntax changes and using a different opcode for
invoking MMD subroutines than non-MMD subroutines.
Yep.
First, a few things to note: the semantics of add vary from language
to language. In particular, add is not guaranteed to be commutative in
Python (think string addition).
As my proposal is primarily focused on where the logic is placed in the
system, not how it works, I'll like to use your proposal
http://xrl.us/egvp as a starting point. Just to make sure that I
don't mischaracterize your proposal, can you take a look at the attached
and either agree that it represents a reasonable first approximation of
what you had in mind, or modify it so that it is?
Once that's done, I'll sketch out all of the changes required to enable
Perl and Python to each have their own separate semantics for this
operation, and yet be able to have meaningful interop when it comes to
adding a PerlInt and a PyInt, or vice versa.
- Sam Ruby
Index: math.ops
===
RCS file: /cvs/public/parrot/ops/math.ops,v
retrieving revision 1.32
diff -u -r1.32 math.ops
--- math.ops7 Dec 2004 17:24:53 - 1.32
+++ math.ops22 Dec 2004 16:08:50 -
@@ -171,7 +171,32 @@
}
inline op add (in PMC, in PMC, in PMC) :base_core {
- mmd_dispatch_v_ppp(interpreter, $2, $3, $1, MMD_ADD);
+ if (1) { /* this is here to allow declarations, even in C89 */
+ struct Parrot_Context ctx;
+ struct parrot_regs_t *bp = interpreter-ctx.bp;
+ STRING *__add = const_string(interpreter, __add);
+ INTVAL mmd_flag;
+ PMC *addsub;
+
+ /* we probably don't need to save the full context, just a few regs... */
+ save_context(interpreter, ctx);
+
+ /* let's ignore the complexities of a distance_func for now... */
+ mmd_flag = 0;
+ addsub = VTABLE_find_method(INTERP, $1, __add, 0, mdd_flag);
+ if (!addsub)
+ mmd_flag = 0;
+ addsub = VTABLE_find_method(INTERP, $2, __add, 1, mdd_flag);
+
+ /* assume NCI for now */
+ VTABLE_invoke(interpreter, sub, NULL);
+
+ /* note: this was allocated by __add */
+ $3 = BP_REG_PMC(bp,5);
+
+ /* again, probably overkill */
+ restore_context(interpreter, ctx);
+ }
goto NEXT();
}
Re: MMD and VTABLE_find_method
Sam Ruby wrote:
First, a few things to note: the semantics of add vary from language
to language. In particular, add is not guaranteed to be commutative in
Python (think string addition).
Yes, of course.
As my proposal is primarily focused on where the logic is placed in the
system, not how it works, I'll like to use your proposal
http://xrl.us/egvp as a starting point. Just to make sure that I
don't mischaracterize your proposal, can you take a look at the attached
and either agree that it represents a reasonable first approximation of
what you had in mind, or modify it so that it is?
It's a reasonable respresentation, yes. Finding the right functions is
more complex, though, as described in my proposal.
I'd just outline the functionality of the add opcode like this:
inline op add (out PMC, in PMC, in PMC) :base_core {
PRESERVE_CONTEXT;
add_func = mmd_find(__add...) // via VTABLE_find_method
REG_PMC(5) = $2;
REG_PMC(6) = $3;
VTABLE_invoke(interp, add_func, 0);
res = REG_PMC(5);
RESTORE_CONTEXT;
$1 = res;
}
the basics are:
* the destination PMC $1 is created by the opcode
* no other registers are changed, nor the context
* finding the __add method uses VTABLE_find_method to
find all possible __add methods and a distance
function to get the best match
* the best matching function is invoked
Once that's done, I'll sketch out all of the changes required to enable
Perl and Python to each have their own separate semantics for this
operation, and yet be able to have meaningful interop when it comes to
adding a PerlInt and a PyInt, or vice versa.
Great, thanks.
- Sam Ruby
leo
Re: MMD and VTABLE_find_method
Hi, a lurker here.
Probably you forgot the braces:
+ /* let's ignore the complexities of a distance_func for now... */
+ mmd_flag = 0;
+ addsub = VTABLE_find_method(INTERP, $1, __add, 0, mdd_flag);
+ if (!addsub)
{
+ mmd_flag = 0;
+ addsub = VTABLE_find_method(INTERP, $2, __add, 1, mdd_flag);
}
+
Bye.
Re: MMD and VTABLE_find_method
Sam Ruby wrote: Leopold Toetsch wrote: However, from http://www.perl.com/pub/a/2004/04/16/a12.html?page=10: Whenever you make a call using subroutine call syntax, it's a candidate for multiple dispatch. I read this to mean that the *caller* does nothing to distinguish between calls to single dispatch subroutines from multiple dispatch subroutines. So... how does one determine at compile time which opcode to use? This probably needs some clarification from Perl6 people. Anyway, if Parrot just gets: foo(Px, Py, Pz) there is no information, how many invocants are participating in MMD. So candidates for multiple dispatch must be declared somewhere. $a.foo($b, $c) := foo($a, $b, $c) Given the latter syntax, how does the compiler know when to emit a callmethodcc foo and when to emit a call_MMD foo? The compiler has to know it. E.g. foo($a: $b, $c); # 1 invocant foo($a, $b: $c); # 2 MMD invocants and as Parrot has to find a method depending on n MMD invocants, this information must be present at runtime. This leads to the assumption that we'll need an opcode call_MMD meth, n_invocants and some changes in pdd03 as the current calling scheme doesn't have anything about argument order. I have described that in subject: MMD: more implications The only thing I am attempting to solve is the presumption that MMD calls can be detected at compile time. It's quite clear for infix operations like add. For arbitrary subroutines the compiler has to know it, as outlined above. Unless you can describe a mechanism which enables the callers to detect at compile time whether they are invoking a MMD subroutine or not, this code needs to be either executed as a part of an VTABLE_invoke. See above. Again, I am not suggesting that the algorithm be made any thinner, in fact, I am not suggesting any change to the algorithms that you have described. I am merely suggesting where the logic needs to be placed. This is quite clear, IMHO. As said: Px = Py + Pz is a call to a MMD function, which is located by the described sequence of VTABLE_find_method and called. The dispatch happens at the opcode level. That's really the same as a callmethodcc opcode, which happens to have just one invocant. There is no difference between these to invocations except that add or + is a fancy shortcut for humans reading the source code. Above is exactly the same as: Px = Py.__add(Pz) But as there are two invocants and we know that's and add operation, we have an optimized opcode for this kind of infix MMD operations like: Px = call_MMD_2 __add, Py, Pz where Px is *created* by the opcode. I'm just proposing this equivalence and a scheme to make it running. And despite that it's looking like a fat method call, Parrot executes this sequence, if the __add isn't overloaded: if (cache-type == (Py-vtable-base_type 16|Pz-vtable-base_type) Px = (cache-function)(Py, Pz); which is 30% faster then the current mmd_dispatch based opcode. - Sam Ruby leo
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote: Sam Ruby wrote: Leopold Toetsch wrote: However, from http://www.perl.com/pub/a/2004/04/16/a12.html?page=10: Whenever you make a call using subroutine call syntax, it's a candidate for multiple dispatch. I read this to mean that the *caller* does nothing to distinguish between calls to single dispatch subroutines from multiple dispatch subroutines. So... how does one determine at compile time which opcode to use? This probably needs some clarification from Perl6 people. Anyway, if Parrot just gets: foo(Px, Py, Pz) there is no information, how many invocants are participating in MMD. So candidates for multiple dispatch must be declared somewhere. A few things to note: foo is a PMC. It therefore is an object. It can have state (properties, attributes, etc). It can know how many arguments are involved in multiple dispatch. All calls to foo are likely to have the same number of arguments participating in MMD. This number is known when foo is defined. If that information is captured in the PMC itself, it can be exploited at runtime. $a.foo($b, $c) := foo($a, $b, $c) Given the latter syntax, how does the compiler know when to emit a callmethodcc foo and when to emit a call_MMD foo? The compiler has to know it. E.g. foo($a: $b, $c); # 1 invocant foo($a, $b: $c); # 2 MMD invocants and as Parrot has to find a method depending on n MMD invocants, this information must be present at runtime. This leads to the assumption that we'll need an opcode call_MMD meth, n_invocants Changing the external syntax for subroutine calls in P6 may be an option. Changing the syntax for function calls in Python is not an option. Therefore, if changing the syntax is required, it is likely that Python will not be able to call arbitrary subroutines involving MMD. It would be ideal if callers did not have to know how such subroutines were defined, and could continue to emit invokecc sequences on Sub PMCs, and for this to be handled at runtime. and some changes in pdd03 as the current calling scheme doesn't have anything about argument order. I have described that in subject: MMD: more implications The only thing I am attempting to solve is the presumption that MMD calls can be detected at compile time. It's quite clear for infix operations like add. For arbitrary subroutines the compiler has to know it, as outlined above. When expressed via an infix notation, I agree that it is not a problem. When expressed via the equivalent method call notation, (as Python allows), it becomes one. And despite that it's looking like a fat method call, Parrot executes this sequence, if the __add isn't overloaded: if (cache-type == (Py-vtable-base_type 16|Pz-vtable-base_type) Px = (cache-function)(Py, Pz); which is 30% faster then the current mmd_dispatch based opcode. That code will execute just as fast if placed inside the invoke logic of a MMD PMC. - Sam Ruby
Re: MMD and VTABLE_find_method
Sam Ruby wrote: Leopold Toetsch wrote: A few things to note: foo is a PMC. It therefore is an object. It can have state (properties, attributes, etc). It can know how many arguments are involved in multiple dispatch. The MMD information can't hang off the Sub PMCs. How do you find the correct foo Sub then? ... This leads to the assumption that we'll need an opcode call_MMD meth, n_invocants Changing the external syntax for subroutine calls in P6 may be an option. Changing the syntax for function calls in Python is not an option. Therefore, if changing the syntax is required, it is likely that Python will not be able to call arbitrary subroutines involving MMD. Python doesn't have the concept of MMD. You can't specify the number of invocants in Python source code. So yes, if nothing is known about the subroutine, it's unlikely that it can be called from Python. If the translator is aware of the fact that a Perl6 multi sub is called, the call syntax can be adapted - however it'll look like. It would be ideal if callers did not have to know how such subroutines were defined, and could continue to emit invokecc sequences on Sub PMCs, and for this to be handled at runtime. Well, I don't know how the Perl6 compiler will translate: foo($a, $b, $c) If there is more then one foo Sub PMC around, the call syntax still must have the number of invocants attached to it, so that MMD can happen. It's quite clear for infix operations like add. For arbitrary subroutines the compiler has to know it, as outlined above. When expressed via an infix notation, I agree that it is not a problem. When expressed via the equivalent method call notation, (as Python allows), it becomes one. Please note that the shown method call syntax was an internal representation of the functionality. But WRT Python: i = 1 j = 2 print i.__add__(j) can be translated directly to the method call of Parrot's infix __add method. And despite that it's looking like a fat method call, Parrot executes this sequence, if the __add isn't overloaded: if (cache-type == (Py-vtable-base_type 16|Pz-vtable-base_type) Px = (cache-function)(Py, Pz); which is 30% faster then the current mmd_dispatch based opcode. That code will execute just as fast if placed inside the invoke logic of a MMD PMC. Where does this hypothetical MMD PMC come from? Where is it created? The opcode is just: add Px, Py, Pz Py or Pz can be plain PyInts or Integers. Where does that MMD PMC come from? And no, it wouldn't have the same performance. - Sam Ruby leo
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote:
Sam Ruby wrote:
Leopold Toetsch wrote:
A few things to note: foo is a PMC. It therefore is an object. It
can have state (properties, attributes, etc). It can know how many
arguments are involved in multiple dispatch.
The MMD information can't hang off the Sub PMCs. How do you find the
correct foo Sub then?
[snip]
Well, I don't know how the Perl6 compiler will translate:
foo($a, $b, $c)
If there is more then one foo Sub PMC around, the call syntax still
must have the number of invocants attached to it, so that MMD can happen.
A foo PMC could represent an entire row in a two dimensional MMD, or
an entire plane in a three dimensional MMD, ... etc.
A Perl6 compiler could translate the above to:
87 find_lex P5, a
90 find_lex P6, b
93 find_lex P7, c
96 find_global P0, foo
108 set I0, 1
111 set I1, 0
114 set I2, 0
117 set I3, 3
120 set I4, 0
126 invokecc
The foo PMC could know how many of the arguments are relevant for MMD
dispatch. Should only the first two arguments be relevant, this code
could be as simple as:
void* invoke(void* next) {
...
if (cache-type == (Py-vtable-base_type
16|Pz-vtable-base_type)
return VTABLE_invoke( cache-function );
...
}
[snip]
That code will execute just as fast if placed inside the invoke
logic of a MMD PMC.
Where does this hypothetical MMD PMC come from? Where is it created? The
opcode is just:
add Px, Py, Pz
Py or Pz can be plain PyInts or Integers. Where does that MMD PMC come
from?
Once MMD is solved connecting it up to the PerlScalar PMC (for example)
would be rather straightforward. Syntax like the following would result
in an appropriate entry being added to the MMD dispatch table:
multi sub infix:+ (Us $us, Us $ustoo) {...}
The Parrot_PerlScalar_add function (which would revert back to being a
vanilla vtable) would know about the portion of the MMD dispatch table
that is relevant to Perl scalar add operations, and invoke it.
(Note: one thing that hasn't been discussed to date is how registers
will be handled. The current add opcode doesn't have any side effects)
- Sam Ruby
Re: MMD and VTABLE_find_method
Sam Ruby wrote: Leopold Toetsch wrote: The caller sets: mmd_flag := NULL ... no MMD, plain method lookup mmd_flag := depth ... return the next matching method starting at the given parent search depth In the general case, how does the caller know that MMD is invoked? Perl6 multi subs are denoted with the multi keyword. We need some extensions to pdd03 that pass this information on to Parrot. It basically boils down to a new opcode: call_MMD method, n as described in subjects MMD: more implications and MMD dispatch A cache invalidation function is called from add_method (and remove_method) which resets entries for the passed class. And, in some languages, all calls to set_attr or setprop type methods, where the value invoked may be invokable, or might obscure visibility to one that is. As calls to setting attributes/properties are frequent, my concern is that this may more than wipe out any potential benefit that such a cache may provide. You don't have operator overloading implemented in py*, do you? Anyway the code generator emits: add Px, Py, Pz Now some attribute set operations on the class, metaclass or in the __dict__ can mean an overloading of the __add__ method of CPy. To handle that correctly, you can either not emit an add opcode in the first place, or you have to track the attribute set operations so that you are able to call the user-provided __add__ method. You can of course in the current scheme install an add MMD method that does always a full method lookup, but then you got the performance problem you are worrying about. Also, note that the Perl sub defined above is not a method. Yes. But Perl6 allows multi subs to be called as methods on the first invocant too: $a.foo($b, $c) := foo($a, $b, $c) Comments welcome, Counter-proposal. I see no reason why a full multi-dimensional multi-method dispatch PMC could not commence immediately, complete with a fully-functional polymorphic inline cache. Once it is ready and tested, we can explore setting things up so that the various mmd_dispatch_* functions to exploit this functionality for the existing predefined binary operations. I don't see how this solves anything, except that you seem to be moving the burden of MMD to an additional PMC. What does this proposed MMD PMC do? How does it find the appropriate multi-method? I've described a versatile MMD scheme that is able to do n-dimensional MMD. Counter-proposals are very welcome, but the proposal has to include the mechanism how it works. A MMD PMC that does it is too thin, sorry. - Sam Ruby leo
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote: Sam Ruby wrote: Leopold Toetsch wrote: The caller sets: mmd_flag := NULL ... no MMD, plain method lookup mmd_flag := depth ... return the next matching method starting at the given parent search depth In the general case, how does the caller know that MMD is invoked? Perl6 multi subs are denoted with the multi keyword. We need some extensions to pdd03 that pass this information on to Parrot. It basically boils down to a new opcode: call_MMD method, n as described in subjects MMD: more implications and MMD dispatch My question was: how does the caller make such a determination? Yes, in Perl 6, the multi subs are defined with the multi keyword. However, from http://www.perl.com/pub/a/2004/04/16/a12.html?page=10: Whenever you make a call using subroutine call syntax, it's a candidate for multiple dispatch. I read this to mean that the *caller* does nothing to distinguish between calls to single dispatch subroutines from multiple dispatch subroutines. So... how does one determine at compile time which opcode to use? A cache invalidation function is called from add_method (and remove_method) which resets entries for the passed class. And, in some languages, all calls to set_attr or setprop type methods, where the value invoked may be invokable, or might obscure visibility to one that is. As calls to setting attributes/properties are frequent, my concern is that this may more than wipe out any potential benefit that such a cache may provide. You don't have operator overloading implemented in py*, do you? Anyway the code generator emits: add Px, Py, Pz Now some attribute set operations on the class, metaclass or in the __dict__ can mean an overloading of the __add__ method of CPy. To handle that correctly, you can either not emit an add opcode in the first place, or you have to track the attribute set operations so that you are able to call the user-provided __add__ method. You can of course in the current scheme install an add MMD method that does always a full method lookup, but then you got the performance problem you are worrying about. The overloading functionality has been added for a number of methods, but not yet for __add__. I've been adding methods one at a time based on the existence of test cases. Classes like PyString are primitive, and opcodes like get_iter directly access the vtable. For classes written completely in PIR, the vtable entry for get_iter causes __iter__ methods to be invoked. Note: this decision is made at runtime, not at compile time. Instead of pessimistically assuming that all such invocations will require a method lookup, this decision is deferred to the appropriate implementation of VTABLE_get_iter. Classes written in PIR but inherit from primitive classes employ a proxy, analogous to the delegate class, but in reverse. Note: proxies are only created if there is such a mix of PIR and NCI involved. All of this is taken care of by the Cinvoke methods of PyType and PyProxyType, the compiler is unaware of these details. Also, note that the Perl sub defined above is not a method. Yes. But Perl6 allows multi subs to be called as methods on the first invocant too: $a.foo($b, $c) := foo($a, $b, $c) Given the latter syntax, how does the compiler know when to emit a callmethodcc foo and when to emit a call_MMD foo? Comments welcome, Counter-proposal. I see no reason why a full multi-dimensional multi-method dispatch PMC could not commence immediately, complete with a fully-functional polymorphic inline cache. Once it is ready and tested, we can explore setting things up so that the various mmd_dispatch_* functions to exploit this functionality for the existing predefined binary operations. I don't see how this solves anything, except that you seem to be moving the burden of MMD to an additional PMC. What does this proposed MMD PMC do? How does it find the appropriate multi-method? I've described a versatile MMD scheme that is able to do n-dimensional MMD. Counter-proposals are very welcome, but the proposal has to include the mechanism how it works. A MMD PMC that does it is too thin, sorry. The only thing I am attempting to solve is the presumption that MMD calls can be detected at compile time. Unless you can describe a mechanism which enables the callers to detect at compile time whether they are invoking a MMD subroutine or not, this code needs to be either executed as a part of an VTABLE_invoke. Again, I am not suggesting that the algorithm be made any thinner, in fact, I am not suggesting any change to the algorithms that you have described. I am merely suggesting where the logic needs to be placed. - Sam Ruby
MMD and VTABLE_find_method
The current MMD scheme is strictly 2-dimensional and it is totally
static. It is not suitable for supporting Perl6 in it's current form.
1) summary of current state
MMD (multi method dispatch) is used to find a method for binary
operations like add or cmp depending on the classes (or types) of
the left and right operand. The current implementation utilizes a
quadratic table per function. Entries can be added dynamically with the
mmdvtregister opcode.
For the MMD_ADD function of two Integer PMCs:
add Px, P.Integer, P.Integer
a different slot is used as for adding an Integer and a PerlInt
add Px, P.Integer, P.PerlInt
(the P.type notation indicates the PMC class)
We have already a native Integer PMC and PyInt, PerlInt, and TclInt
variants in the Parrot tree. At least the first three are doing
basically the same. They should just inherit the functionality of
Integer. The same is true for other Parrot core types.
But creating even a static setup of MMD functions for all permutations
of Integer PMCs is almost impossible, the more that another HLL can
easily be added at runtime. Creating MMD slots for this type would need
the knowledge of other existing types including their behavior. And
there are of course more permuations: add P.Float, P.int ...
E.g.
$P0 = new PyInt# or PerlInt, TclInt, Integer, ...
$P1 = new Integer# or PerlInt, TclInt, ...
$P2 = add $P0, $P1
If Parrot should be able to run code originating from different HLLs the
core implementation has to provide a common and reasonable subset of
functionality. [1]
Currently even above mixed types add operation isn't working (The
Integer could be the result of a Parrot library call).
2) n-dimensional MMD
Perl6 supports a more general form of MMD:
multi sub foo(ClassA $a, ClassB $b, ClassC $c : ...) { ... }
which dispatches on the types of three invocants. Extending the static
two-dimensional table to even just one more dimension would already
occupy more memory then most computers have (yes, I know that tables can
be compressed - just add one more dimension ...:-)
3) 1-dimensional method lookup
This is handled by VTABLE_find_method. A new method can easily be
installed by calling VTABLE_add_method. Both are under control of the
class that implements these two VTABLEs.
4) Proposed changes:
a) All method lookup goes through VTABLE_find_method. To achieve MMD
functionality, two arguments are added to the find_method signature:
PMC* find_method(STRING* meth_name, INTVAL mmd_nr, INTVAL* mmd_flag)
mmd_nr is the MMD invocant number:
0 := first (or only invocant)
1 := second invocant (e.g. right argument of 2-dim MMD)
...
mmd_flag is a pointer to an integer, indicating the desired behavior:
The caller sets:
mmd_flag := NULL ... no MMD, plain method lookup
mmd_flag := depth ... return the next matching method starting
at the given parent search depth
depth := 0 this class
:= 1 first parent in search order
:= n n-th pareht ...
The called class returns either NULL (if method wasn't found) or a
pointer to the method function. C *mmd_flag is set to the search
depth of the found method.
Additionally the class can set C *mmd_flag to -1 if no further MMD
lookup should be performed, i.e. the returned function (if any) should
be used.
A 2-dimensional MMD search for a method looks similar to this:
mmd_flag = 0
do
meth = left.find_method(left, name, 0, mmd_flag)
if mmd_flag == -1
return meth
if (meth)
push(found, (meth, mmd_flag, 0))
mmd_flag ++
else
break
mmd_flag = 0
do
meth = right.find_method(right, name, 1, mmd_flag)
if (meth)
push(found, (meth, mmd_flag, 1))
mmd_flag ++
else
break
if ! found.elements
return NULL
sort { distance_func } found
return found[0].meth
b) the Cadd_method vtable is extended with one argument:
void add_method(STRING* meth_name, INTVAL mmd_nr)
The default implementation uses a store_global like the opcode:
store_global class_name_right\0__1, meth_name, func
c) Parrot objects have a dedicated parent_search_array of classes. Plain
PMCs have self_name and their parent names in the Cisa_str. To
simplify and unify both schemes, we move the functionality into the vtable:
vtable-mro ... array of classes for method resolution order
5) Performance considerations
As these scheme obviously needs several lookups to find a matching MMD
function the result should be cached. This caching can be efficiently
done at the opcode level in predereferenced run loops (including JIT)
with a PIC (polymorphic inline cache). [2]
A PIC scheme outperforms the current static MMD table lookup by 30% up
to 70% for overloaded operations.
A cache invalidation function is called from add_method (and
remove_method) which resets entries for the passed class.
Method lookups called from inside Parrot aren't really very
Re: MMD and VTABLE_find_method
Leopold Toetsch wrote:
2) n-dimensional MMD
Perl6 supports a more general form of MMD:
multi sub foo(ClassA $a, ClassB $b, ClassC $c : ...) { ... }
[snip]
4) Proposed changes:
a) All method lookup goes through VTABLE_find_method. To achieve MMD
functionality, two arguments are added to the find_method signature:
PMC* find_method(STRING* meth_name, INTVAL mmd_nr, INTVAL* mmd_flag)
mmd_nr is the MMD invocant number:
0 := first (or only invocant)
1 := second invocant (e.g. right argument of 2-dim MMD)
...
mmd_flag is a pointer to an integer, indicating the desired behavior:
The caller sets:
mmd_flag := NULL ... no MMD, plain method lookup
mmd_flag := depth ... return the next matching method starting
at the given parent search depth
In the general case, how does the caller know that MMD is invoked?
A PIC scheme outperforms the current static MMD table lookup by 30% up
to 70% for overloaded operations.
A cache invalidation function is called from add_method (and
remove_method) which resets entries for the passed class.
And, in some languages, all calls to set_attr or setprop type methods,
where the value invoked may be invokable, or might obscure visibility to
one that is. As calls to setting attributes/properties are frequent, my
concern is that this may more than wipe out any potential benefit that
such a cache may provide.
Also, note that the Perl sub defined above is not a method.
Comments welcome,
Counter-proposal.
With Parrot today, compiler writers need not know the difference between
a closure, a continuation, a coroutine, an nci, or a sub. Or, for that
matter, a PyFunc, a PyGen, or a PyType.
The general case is that the caller has a PMC which does sub. This
may not be a method (the Perl syntax above suggests a simple sub). It
may have been found via find_lex or find_global, been returned by a
previous subroutine call, or have been newly created. Whatever.
At this point, the caller's responsibilities are merely to set up the
registers according to the Parrot Calling Conventions and then execute
the invoke opcode, or equivalent (invokecc, tailcall, ...).
At this point, there are two paths that are possible. Either the
compiler takes full responsibility for emitting code that does the
appropriate second level dispatch. Or there can be code in the Parrot
repository in the form of a new subclass of the existing Sub class which
locates and appropriate destination. (Note: these choices are not
mutually exclusive).
I see no reason why a full multi-dimensional multi-method dispatch PMC
could not commence immediately, complete with a fully-functional
polymorphic inline cache. Once it is ready and tested, we can explore
setting things up so that the various mmd_dispatch_* functions to
exploit this functionality for the existing predefined binary operations.
- Sam Ruby
