From: Eivind Eklund Date: 2005-10-04T23:48:48+09:00 Subject: Re: Type inference On 10/4/05, Eric Mahurin wrote: > --- Eivind Eklund wrote: > > > On 10/3/05, Eric Mahurin wrote: > > > Maybe I misunderstood what Eivind was asking for. From the > > > last message it sounded like he was asking for the > > > interpreter/comilier/VM to try to infer what the class was > > for > > > the object of some variable. > > > > Not class. What is possible is to infer the binding of > > certain > > messages (method calls). The "Class" concept in Ruby sort of > > isn't > > classes, more a way to launch an object with a predefined set > > of > > method bindings. > > "class" is still closer to what you are talking about than the > ruby definition of "type" I've seen running around. The one > I've seen is basically analogous to interfaces in Java, but > includes all methods. For example IO and StringIO could be > considered the same "type". I don't think that kind of "type" > inference does any good for improving performance (the methods > for IO and StringIO are completely independent). That's what's usually called an abstract type. What we are (or at least I am) discussing is inferring what's usually called concrete types. > For ruby, I'd still say class is close enough. And if an > object changes it's meta class (initially the normal class), > that meta/singleton class should be treated as it's class for > "class" inference purposes. I still think we should call it (concrete) type inference, because everybody else does, and having two subtly different definitions for "class" seems likely to trip up communication. And this area is hard enough as it is. > > > The reason for doing this would be to transform something > > dynamically typed (all ruby > > > variables) to something statically typed. I think this is > > the > > > critical thing needed in dynamically typed languages to > > give > > > performance that approaches statically typed languages. > > > > Not really. It's possible to do this at run-time, and that's > > easier > > than doing it at "compile time". The combination result in > > the > > fastest code, of course. > > I didn't say it needed to be done at compile-time. This > transformation can be done at compile-time or run-time. There's somewhat more that can be done at run time than at compile time. The run time techniques are usually considered as outside the scope of type inference, though they're also relevant for a general discussion of optimization techniques. I would prefer to stick with discussing type inference techniques first, as they can be used for more than pure optimization. > I think that having to allow for methods of objects to change > (either by changing class methods or meta class methods) after > this transformation is done becomes problematic. This problem has already been handled by the Self implementation, unless I've significantly misunderstood. > This chapter has benchmarks: > > http://research.sun.com/self/papers/chambers-thesis/t14.ps.Z > > Performance ranges from 22% to 65% of optimized C. Compare > that to ruby - from about 0.25% to 10% of C (language > shootout). Seems like somebody should try implementing ruby in > the self virtual machine. I read somewhere that smalltalk was > implemented on this VM, so why not ruby? ruby got many of its > features from smalltalk, right? Yes. I think pure Ruby should be possible to translate to the Self interpreter in a fairly direct fashion, more or less with just a parser throwing things to the backend. The challenge is that the Ruby standard library is written in C, and we do not have a complete implementation in Ruby available (or didn't the last time I checked, anyway.) There's metaruby, which has some of it, and RIR (Ruby-in-Ruby), that may have some other parts. I don't think there's anything complete? > > > It sounds like you are talking about type checking not > > class > > > inference. > > > > These are (or can be, at least) aspects of the same thing. > > Inference > > of the binding for messages (methods) let us do static > > inference of > > the real types (not classes) involved, and can give early > > warnings, > > like "That method call is going to result in an uncaught > > NoMethodError" or "That code branch will never ever be > > called". > > Again it depends on what your definition of "type" is. By "real type" I mean "concrete type" which again means "what exact code will be run by method calls and what memory layout the type has". I think this is fairly universally accepted terminology among those doing research on types (though maybe I've just picked up terminology used by a subcommunity - I've restricted myself to reading research that seemed interesting.) > If your > method checks to make sure that an argument responds to all > that is needed (psuedo checking the "duck-type"), I don't think > that helps the type (exact method bindings) inference problem. It might actually help somewhat, as the call flow gets more limited. When we do that check, it is no longer possible for an error to happen further down in the call graph and create an exception. This may also avoid some cases of half-executed code, which again maybe could simplify the rest of the analysis (because half-changed objects don't happen.) > If it [your method -EE] checks for a specific class, that would trivialize this > inference. If it check for a specific concrete type, that trivialize the inference. However, classes in Ruby are *not* concrete types, and that's very important to remember. That's why I want to have other terminology. I'm not sure if you mean concrete type (and if so, how are we going to specify concrete types?) or Ruby classes above. The latter help little (as it is trivial to override kind_of? and instance_of?). > > You cannot completely describe the duck-type of an argument > > in the general case. > > I could see that since it is so recursive. But, you may if you > limit the depth. That's the way I think it's been done in the Self environment. The inference engine finds the types to a certain depth, add some assertions that check that those parts are true, and runs the code under those assumptions. If the assertions fail, the relevant part is recompiled or interpreteted. This is done partially at compile time (in the form of extraction of the relevant part of the environment to create a single "application binary" to ship to users), and partially through "type feedback" at runtime, which notice that something always is the same concrete types, and JIT-compiles code based on that. Eivind.