In addition to what stvn said, I'd just like to add that the design of the type system and particular the signature system depends on certain guiding principles. One of these
stvn alluded to, which is that it doesn't cost much to wedge in extra options at a point where you're already obligated to make an n-way choice, such as at the dispatcher selection boundary, or at the wrapper/wrappee boundary in &foo.
One principle he kinda glosses over is that we tend to build features into the signature/type system when it replaces code you'd have to write yourself, and probably do a poorer job at. Signature types are not there primarily so that your routine can wring its hands over the shoddy data it is receiving. You can use them for that, of course, but the signature types are there mostly so that the MMD dispatcher can decide whether to call your routine in the first place. That's just an extension of the idea that you shouldn't generally check the type of your invocant because the dispatcher wouldn't call you in the first place unless the type were consistent. By putting the type declaratively into the signature, we can give the information to the MMD dispatcher without committing to a type check where the computer can figure out that it would be redundant.
And the whole MMD dispatch system is there to replace the nested switch statements or cascaded dispatches you'd have to do to solve the problem if you rolled your own solution.
And then it would still be subtly wrong in those cases where you're tricked into imposing a hierarchy on invocants that should be treated equally. The whole Perl 5 overloading scheme is a case study in that sort of error...
Likewise the rest of the signature binding power is provided to
declaratively replace all the boilerplate procedural code that people have to write in Perl 5 to unpack @_.
Even if the declarations just generate the same boilerplate
code and we get no performance boost, we've at least saved the user from having to watch the faulty rivets pop out of their boilerplate.
Not to mention having to stare at all that boilerplate in the first place...
Anyway, those are some of the principles that have guided us. We may have certainly screwed them up in spots, and doubtless we'll find some bottlenecks in the design that we didn't anticipate because we're just too stupid. But as you may have noticed, we're trying really hard to design a language where we can compensate for our own stupidities as we figure them out over the long term. If there's anything that can't be fixed in the design, that's probably it. | [reply] |
In compiled languages, where most of the groundwork for Traits and the others is being done, the complexities of method resolution and search order are compile time only costs. By runtime, the method call has been resolved either to a vtable entry, or to the actual entrypoint address.
You are mistaken here on two points actually. First, Most of the work on traits is being done using Smalltalk, which is in fact a compiled language, but it is also a very dynamic language. IIRC it does not use any type of vtable or compile time method resolution, but treats all object message sends as dynamic operations. Second, all compiled OO languages do not perform method resolution at compile time, that is a (C++/Java)ism really, and does not apply universally.
I also want to point out that Class::Trait does all of it's work at compile time. This means that there is no penalty for method lookup by using traits. In fact since the alternative to traits is usually some kind of MI, traits are actually faster since the methods of a trait are aliased in the symbol table of the consuming class and so no method lookup (past local symbol table lookup) needs to be performed.
... snipping a bunch of stuff about Parrot and method performance ...
It would also make Traits (and similar solutions) a practical solution to that MI complexity--but only if the method resolution can be fully resolved at compile-time
Well, again, Traits (the core concept, not just Class::Trait) do not have any method lookup penalty really. The whole idea is that you don't have another level of inheritance, so you don't have all the pain and suffering which goes along with it. I suggest you might read the other papers on traits, not just the canonical one Ovid linked too, they provide a much more detailed explaination of the topic.
The fear I have is that Perl 6, and other dynamic languages that are trying to adopt trait-like behaviours, are also adding
- Pre & post method entrypoints.
- Dynamic inheritance resolution.
- Dynamic vtables at the class (and maybe instance) level.
- Full introspection.
- Runtime macro capabilities.
Each of these things adds runtime cost to the process of invoking a method.
What you have just described is essentially CLOS (Common LISP Object System), which is not slow at all. In fact, in some cases CLOS is comparable to C++ in speed, and I would not doubt that in many cases it is faster than Java (and lets not even talk about programmer productivity or compare LOC cause CLOS will win hands down). Java/C++ both suck rocks at this kind of stuff for one reason, and one reason alone. They were not designed to with this way. If you want these types of features in your Object system, you need to plan for them from the very start, otherwise you end up with..... well Java.
It is also important to note that a dyanamic languages can be compiled, and that the concepts are not mutally exclusive. LISP has been proving this fact for over 40 years now.
The code reads:
$obj->method();
The interpreter has to do
- Is method a macro? If so, expland it.
- What is the class of $obj?
That's at least a two levels of indirection. One to look up the class name. One to look up the hash storing the method names associated with that classname.
To start with, macros are expanded at compile time, in pretty much all languages I know of. Sure it might be the second phase of a compile, but it is still before runtime.
Next, an $obj should hold it's class information directly in it's instance. In Perl 5 it is attached to the reference with bless, other languages do it their own way, but in general, an "instance type" will have a direct relation to the class from whence it came. So my point is that while it might be a level of indirection, it is very slight, and certainly should not involve any serious amount of "lookup" to find it.
As for the method name lookup, you are correct, but some kind of lookup like this happens for just about every sub call too (unless of course you inline all your subroutines, which would just plain silly). We suffer a namespace lookup penalty because it allows us to use namespaces which are essential to well structured programming and have been for about 20+ years now. Basically what I am getting at is, you should not add this to your list of "why OO is slow" since it is not really OO that brings this to the table, it is namespaces as a whole.
Can classX do method?
If not, then look up the list of classes/traits/roles that it might inherit this method from.
Whoops,.. you are assuming traits/roles are inherited again. They are not, they are flattened, they have no method lookup penalty.
Also look up classX' search pattern (depth/breadth/etc.).
Ouch! This is a bad bad bad idea, it would surely mean the end of all life as we know it ;)
But seriously, take a look at C3, it (IMO) aleviates the need for this type of "feature".
For each superthing, lookup the address of it's vtable and check if it can do the method.
There you go with those vtable things again, thats just plain yucky talk. Seriously, method dispatching can be as simple as this:
sub dispatch {
my ($obj, $method_name, @args) = @_;
my $class = $obj->class;
foreach my $canidate ($class->get_MRO()) {
return $canidate->get_method($method_name)->($obj, @args)
if $canidate->has_method($method_name);
}
die "Could not find '$method_name' for $obj";
}
Even with Traits/Roles, it really can be that simple (remember, they flatten, not inherit). Sure, you can add more "stuff" onto your object model which complicates the dispatching, but still the core of it doesn't need to be much more than what you see above.
... snip a bunch of other stuff ...
What happens if you find two (or more) superthingies that could provide that method? Now you have to go through a conflict arbitration process.
This is a non-issue, let me explain why. To start with, in Pure OO (no traits/roles), there is no conflict arbitration, if you find it in the current class, that is it, done, end of story. If you add traits/roles it actually doesn't change anything since they are "flattened". By the time the dispatcher gets to them, they are just like any other methods in the class, so normal OO dispatch applies.
Assuming that after all that, we isolated a resolution for the method, we now have to go through lookups for PRE() & POST() methods, and about half a dozen other SPECIAL subs that can be associated with a method or the class it is a part of.
A good implementation of this would have combined the PRE, POST and SPECIAL subs together with the method already (probably at compile time) I know this is how CLOS works. The cost you speak of is really an implementation detail, and (if properly implemented) is directly proportional to the gain you get by using this feature. Always remember that nothing is free, but some things are well worth their price.
And that lot, even with the inherent loops I've tried to indicate, is far from a complete picture of the processes involved if all the features muted for P6 come to fruition. All of that was just to find the method to invoke.
Now you have to sort out all the actual-to-formal parameter mappings, with all the
slurpy/non-slurp.
named/un-named.
required/optional.
read-only/read-write
by-reference/by value.
defaulted/no-default.
type constrained.
range constrained.
does constrained.
is constrained.
will constrained.
possibilities and combinations thereof.
And many of those will themselves require class hierarchy and method resolutions.
A good number of these can and will be resolved at compile time by the type inferencer (remember, Perl 6 will be a compiled dynamic language, just as Perl 5 is today). And of course a properly written implementation means that you will only pay for the features you actually use, so things like type contstraints (subtyping) will not affect you unless you actually use it (and again will likely be something done at compile time anyway).
Keep in mind that many of the features you descibe here, which you insist will slow things down, are features found in a number of functional languages, many of which are really not that slow (and compare to C speed in some cases). Compiler technology and Type checkcing has come a long way since the days of Turbo Pascal, and it is now possible to compile very high-level and dynamic code in say Standard ML or Haskell to very very tight native code. My point, it is not just hardware technology which is advancing.
Yes, I agree that there is a complexity problem with MI that must be addressed, but I also see huge performance problems arising out of the solutions be proposed, which when combined with all the other performance sapping, runtime costs being added through the desire for even greater introspection and dynamism.
Well, I think you are mistaken about these "performance problems" in many cases, but even so, if Traits makes for a cleaner, more maintanable class hierarchy, that is a "performance problem" I can live with. Remember, for many programs, your greatest bottleneck will be I/O (database, file, network, whatever). IMO, only if you are writing performance critical things like Video Games or Nuclear Missle Guidance systems do you really need to care about these "performance problems", and if that is what you are writing, then why the f*** are you writing it in Perl ;)
Combined, these mean that the single biggest issue I have with the current crop of dynamic language implemetations, performance--which Perl is currently the best of the bunch--is going to get worse in the next generation, not better.
To start with Perl is not the fastest, nor is it the most dynamic. If you want dynamic, lets talk LISP, which not only has what Perl has, but it has much of what Perl 6 will have and then some (it certainly has all the features you have descibed above). LISP is not slow, in fact it is very fast. Why? Well, because it is compiled correctly. If we continue to use old, and outdated compiler theory/technology, then all the cool new whiz-bang stuff we want to add onto our language will just slow it down. On the other hand, if we bring our compiler theory/technology up to date with out language design/theory, then it is likely we won't suffer those penalties.
Remember, just because Java/C++/C#/etc. can't do it right, doesn't mean it can't be done.
| [reply]
[d/l]
[select] |
Wouldn't it be nice if you could generate your charts or summarise your data, or search your in-memory DB quickly enough that you didn't need to keep the user appraised of the delay?
I note that you qualified that with "in-memory", so that's a way out, but I just want to point out that Perl is fast enough and computers are fast enough that whenever I have to let my user know of a delay it's almost always due to a complicated database query, heavy disk IO or some request to an external resource. These three things, if slow, will be slow regardless of the language. Yes, Perl is slower than most commonly used languages but much of that can be alleviated with profiling and proper algorithm design.
And I am unsure yet whether Traits are either the best semantically, or the least likely to degrade performance, of the possible solutions to the problem they address.
From my personal experience with MI, mixins (I faked 'em via Exporting), Java interfaces and traits, I'm fairly convinced that traits are the best semantically and the lest likely to degrade performance (there's a tiny compilation hit with traits, but it's neglible. 300 tests in my lastest version run in about 4 wallclock seconds). Of course, while my original suspision of the superiority of traits came from my reading about them, my current opinion stems from my having experience with traits. I keep hearing in this thread comments which sound dangerously close to "I won't use traits because I haven't used traits" or "I won't use traits because other's don't". I find the first argument to be stupid. We never learn anything that way. The second argument might have a bit of merit ... being afraid to lead the way is often a survival traits ... but that doesn't mean people can't try them on non-critical systems so they can find out for themselves whether or not they're worthwhile. Folks railing against a technology they've never used just strikes me as a bit odd.
The major questions I wonder about are whether or not the implementation I am maintaining has any bugs and what features need to be added/tweaked. However, I'm also not saying Class::Trait is the best choice, either. There are several competitors out there which offer different interfaces and capabilities. Just because Class::Trait is the most feature-complete doesn't make it the best. Still, I'd hare for folks to let fear of the unknown keep them from tying out these technologies. They really have made my life simpler at work (and I fully realize that my knowledge of real-world use of traits is relatively new. It's better than most have, though :)
| [reply] |
BrowserUK
Wow,.. nice post :)
I think that we have an impedance match on our interpretation of the phrase "dynamic language".
Yes, I agree, although not really that different. My criteria for a "dynamic" language, is more the ability to write agile code which can cope with dynamic requirements. This could include eval-ing code at runtime, but it also includes other language features such as polymorphism. For instance, I am currently reading about the Standard ML module system. SML is very often a rigorously staticically compiled language, but it's module system is built in such a way that it almost feels like a more dynamic language. This is because of Functors, which (if I understand them correctly) are essentially parametric modules whose parameters are specificed as module "signatures". When you call a functor, you then pass a "structure" that conforms to that "signature" and the functor then creates a new "structure" based on that (it is not all that different from C++ STL stuff actually). If you then combine the module system with ML's polymorphism, you can get a very high degree of dynamic behavior, while still being statically compiled.
My point, static code analysis does not have to limit the dynamism in a language.
I also want to quickly say that runtime introspection (read only, or read-write) is not (IMO) a criteria for dynamic languages. In fact in some languages, like SML, I think runtime introspection is just not needed. However, that said, I personally like runtime introspection in my OO :)
If LISP is so dynamic, and yet also so fast, I would like to understand how it achieves that.
I won't claim to be an expert on LISP compilation, because I truely have no idea about this. I do know that the only language still in use today as old as LISP is FORTRAN. Both of these langauge have blazingly fast compilers available probably for the simple reason that 40+ years of improvement has gone into them.
As for how LISP is so dynamic, I think LISP macros have a lot to do with that. LISP has virtually no syntax (aside from all the parens), so whan you write LISP code, you are essentially writing an AST (abstract syntax tree). LISP macros are basically functions, executed at compile time, which take a partial AST as a parameter, and return another AST as a result. This goes far beyond the power of text substituion based macros. And of course, once all these macros are expanded in compile time, there are no runtime penalties.
To be totally honest, I have written very little LISP/Scheme in my life. Most of my knowledge comes from "reading" it, rather than "writing" it. But with languages like LISP, I think more of the (real-world applicable) value actually comes from the "groking" of the language, and not the "using" of it. In other words, it is much easier to find work writing Perl than it is writing LISP, but knowing LISP can make me a better Perl programmer.
With respect to my use of the term 'vtable'.
<snip a buch of things related to static method lookup vs. dynamic method lookup>
Much of what you say is true, but I think it has more to do with the design and implementation of the languages, and less to do with the underlying concepts.
I beleive that static analysis can go a long way, and caching and memoization can take it even further, and whatevers left is probably so minimal I don't need to worry about it. The best results can be acheived by combining all the best practices into one.
Will this work? I have no idea, but it's fun to try :)
re: program efficiency vs. programmer efficiency
I work for a consultancy which writes intranet applications for other businesses (we are basically sub-contractors). While performance is important (we usually have guidelines we must fall within, and we load test to make sure), these applications are long living (between 2-7 years). It is critical to the success of our business, and in turn to the success of our client's business that these applications are maintainable and extendable. Our end-users may not be anything more than periferally aware of this, and therefore seem not to care about it. However, those same end-users like hearing "yes" to their enhancement requests too. So while those end-users may not associate this with my use of OO, or trade-offs I made for readability, or time I spent writing up unit tests, they certainly would "feel" it if I didn't do that.
My point is that, for some applications, and for some businesses, application performance is much lower on the list than things like correctness, flexibility and extendability.
Search patterns, breadth first/ depth first etc.
Yeah, I read that part in A12 as well, I think it is flat out insanity myself :) Nuff said.
I vaguely remember trying to look up some term that came up within these discussion--something like the "New York Method" or "City Block Method"?--and failing to find an explanation.
The name you are looking for is "Manhattan Distance". I am not that familiar with the algorithm myself, however, I surely (unknowingly) employed it many a times since I lived in NYC for a while :) Google can surely provide a better explaintation.
And I am unsure yet whether Traits are either the best semantically, or the least likely to degrade performance, of the possible solutions to the problem they address.
I am not 100% sure of this either, I like the sound of Traits/Roles, but you never know when something better might come along.
| [reply] |