From: David Simmons Date: 2001-11-26T08:05:26+09:00 Subject: [ruby-talk:26473] Re: Table: Ruby versus Smalltalk, Objective-C, C++, Java; "Pixel" wrote in message news:lybshr6m8r.fsf@leia.mandrakesoft.com... > "David Simmons" writes: > > [...] Hi Pixel, In reading your reply I am frustrated by the sense that you are drilling [as if I did not understand them] into the very issues I was presenting in broad strokes, and which were too lengthy for me to explain [given my time and activities] in the context of a newsgroup post. But, I will try to clarify your items point by point. > > > In dynamic languages which lack multi-methods, we see "double-dispatching" > > (a poor-man's workaround) for receiver+1arg cases where all the types are > > known up front at design time [i.e., no 3rd party development or late > > deployment time integration issues]. > > same in statical typing: http://www.eptacom.net/pubblicazioni/pub_eng/mdisp.html I was not aware that someone was "bothering" to use RTTI (or templates [macros]) to address this issue in C++. Given the importance of C++ I should hardly be surprised. However (in broad terms), this is the problem with implementing genericity in languages which only support static typing [as I alluded to in my previous post regarding the languages Java and C#]. As I said in my previous post, the ideal is a language which has both static and dynamic typing with overloading/multi-methods -- lacking that numerous issues crop up. This is just a "facet" of that generics issue. > > > I am not sure why you mentioned these generally well understood facts [at > > least they are generally well understood within the dynamic language > > implementation community]. > > because your chart has a "yes" for multi-methods in C#/C++ ! You are leaving out key annotation information. The chart says "yes (but restricted facilities)". Now you could readily argue that it should have provided different wording or more explanation [although this is intended to be an informal chart -- not a writeup comparing languages feature by feature]. But it would have been "wrong" to say that it "did not" support "(overloading)" as taken from the row-heading on the chart. > > [...] > > > > cf the Castagna's nice paper > > > http://citeseer.nj.nec.com/castagna95covariance.html > > > > Sorry, I could not access the paper on that site without an ACM online > > library membership. Feel free to send me a PDF if available. > > click on "Cached: PDF" (hail CiteSeer!) Thanks (3 or 4 other people also clued me in on that :), I have the paper now. > > > > > > > > > > > > > If it had such facilities then it could, at runtime, truly dispatch > > > > on one or more parameters to a function (including as a > > > > parameter). > > > > > > Java, C#... are in the same category > > > > I agree, they are broken. But you are preaching to the choir; I am a > > dynamic language advocate, > > but the problem is not being dynamic or not: a statically typed language *can* > have multiple dispatch! > eg: Cecil, MultiJava (http://www.cs.washington.edu/homes/todd/papers/oopsla00.html) > I never debated that; quite the opposite I alluded that some statically typed languages exist with support for type-cases and dynamic typing [and I well aware of Cecil language and Vortex compiler technologies -- Cecil and a number of other languages are mentioned on the web page chart at http://www.smallscript.org/Language%20Comparison%20Chart.asp]. But you've switched the example away from the only-statically-typed languages we had under discussion [Java, C#, C++]. Again, the point is that ideally one wants a language that unified its world-type-object-view with both static and dynamic typing and supports execution-engine/compilation optimization to select/choose (static) overloading/(and dynamic) multi-method invocation mechanics as appropriate, and thereby enables efficient correct genericity. This is one unified idea, that crops up with many variant names [and solution efforts] because so many languages exist with (differing) partial capabilities [thus spawning many unique workarounds with provisos] -- rather than having a generalized object model view [semantics] to address types-in-the-face-of-objects uniformly [which is where my interest has been focused]. > adding multiple dispatch to java: http://citeseer.nj.nec.com/dutchyn01multidispatch.html > > [...] > > > All the "crap" regarding genericity in Java [and C#] would never have been > > an issue if they did away with (or offered alternatives to) the VTable > > dispatch mechanism > > C++ has vtable and genericity (parametric polymorphism, aka templates). > I don't see the limitation that makes Java and C# not having genericity. > (AFAIK Java 1.4 will have generics) > > >-- which is something I appear to be influencing the > > thinking on at Microsoft. It would also be trivial to inherently provide > > proper AOP if true predicate based calltime binding and dispatch was > > performed. NOTE: I am being very careful to stay away from the potentially > > dodgy term "dynamic binding" because, like the broad use [and now relatively > > meaningless] term object-oriented, it has become rather polluted. > > > > Similar issues occur with static language notions of sealed and final as > > well as interfaces. And closely related is the need for selector > > namespaces, which I invented in 1996. Which, to my great satisfaction, are > > now going to be a part of the ECMAScript (JavaScript 2.0) standard. The > > ECMAScript selector namespace design, as far as I known, is unrelated to my > > work -- which is what makes it so satisfying because it means that > > independent parties trying to solve similar problems came to the same > > fundamental conclusions about its importance. > > apropos could you add some "alt=" to http://www.smallscript.net/ (is nicer for > links/lynx users) Good idea; I was lamenting I did not put an explicit link regarding SmallScript into the original post. OTOH QKS Smalltalk [(www.qks.com -- SmalltalkAgents-IDE) which I designed and was the chief architect for] is basically defunct and is no longer downloadable/purchasable. So you can't play with it to see the ideas and concepts in action. SmallScript is my personal evolution in thought within this space and SmallScript is still very much a work in progress. I've been deeply involved in both business issues and design and implementation of virtual-machines, language design, frameworks, and tools which has left me little or no time to focus on publishing papers [let alone writing a book or contributing to the documentation -- until I recently began forcing myself to]. > > it seems like SmallScript description is missing or??? All i can find is ugly > words (pricing, Microsoft, .asp's, Technology Preview...) > > i couldn't find info about this "selector namespace", any link? You won't find a link on the SmallScript site at this time. However, I just made an fairly detailed post on this topic area. The post can be found on comp.lang.ruby as "Selector Namespaces: A Standard Feature For Smalltalk?". > > > > > > > > > http://people.mandrakesoft.com/~prigaux/overloading2.java > > > > Sure, the example is clearly illustrating the problem. Static type binding > > of dynamic type information does not work. I.e., languages which only have > > static binding cannot provide proper semantics for method-implementation > > selection based on argument types. > > hum. C++ and Java do not have "only static binding". I think we both understand the issue. The problem here is that the "semantics" of the term dynamic-binding have been polluted/overloaded. So, as with many topics in comparing languages with regard to "static" and "dynamic" subjects, we quickly get bogged down in terminology as we try to use that terminology to explain/discuss concepts. If all parties don't have a clear concensus on the definitions of the terminology the discussions rapidly digress into areas that are the result of that lack of concensus. So, ignoring the terminology: C++ and Java "typically" (but not always) implement virtual functions using vtables. Where a vtable is an array of function pointers to virtual methods associated with a given type. These languages are not only statically typed, they are based on the concept of static binding of type information as well. In an effort to be "object oriented" [whatever that means] they attempt to provide [OO] polymorphism using vtables which are a weak/limited solution to providing polymorphism over one-type (the message receiver). For static binding based on type information, this means that at compile time the decision is made as to what method to invoke based on the types of the arguments. The partial-polymorphic-solution exception is built by assuming that all types are known at compile time. And that, therefore, tables can be constructed containing common methods for type-trees based on the "type of the receiver ". So one gets a binary-deployment-system that cannot break those compile-time rule of all types known at runtime [it is not dynamic/extensible at runtime and so is brittle], and which also cannot address the problem of polymorphism over the arguments to methods [which leads problems in implementing/supporting genericity, etc because the model is based entirely on static knowledge]. Some languages, like ML, have taken great strides to addressing this problem and ensuring correct behavior but I (currently) think it requires supporting both a static and dynamic type and binding model. So, back to exploring issues in the vtable approach. As mentioned before it is based/built-upon static knowledge of the available set of types. It's indirection mechanism is therefore based on static knowledge, which makes it a static (lookup table) binding mechanism. I.e., the vtable-index [a first-degree binding abstraction approach -- as opposed to a selector-object in dynamic language which is a second-degree binding abstraction] is statically bound into source and thus [among other things] precludes handling dynamic [binding impact] changes to the classes and methods. I.e., vtables are limited in two semantic ways and additionally in one technical way. 1. Semantically it only works for whole-cloth programs where no schema changes [in the binary/compiled-form] will occur to class, namespace, or methods available within the program [that's what makes them static languages]. Why? Because if such changes occur the vtable layouts may need to be changed, the call-sites that use indexed-lookup will have to have the indices changed [not even considering the issues of the methods themselves which have optimized-away/unfolded encapsulation of object structure, etc]. None of which is possible because all the necessary meta-information was thrown away at compile-time [many things are not objects, most things have no self-describing information (i.e., nominal to no reflection facilities) -- RTTI being C++'s only facility]. 2. In a unified OO view, there are no "pure-functions", because classes [or prototypes], namespaces, etc are all objects and functions are just methods on those classes [or prototypes] and namespaces. All operations semantically become about the messages that objects can understand (perform). The concerns about physical-layout/structure of a type vanish leaving us [humans] only concerned [in general] with the message vocabulary [i.e., behavior/interfaces]. The compilers are where the optimization and knowledge about physical representation become paramount for performance and external inter-op [and humans only care when they are meshing with the boundary points -- usually to create optimized small algorithms; an act which requires greater attention and focus than one would normally want to have to put into describing a problem to the computer via a programming language -- generally we want our programming language to be capable of being as transparent as possible so we can focus on the problem domain itself rather than the problem of describing the problem to the computer]. Parameterized types in object definitions are relevant to humans in terms of contractual (behavioral) adherance. To the compiler(s) they allow optimizations to be achieved for better performance and resource utilization [potentially as guided by a human author]. Which gets us back to genericity and best efforts at being informed "statically" about design time behavior-binding (type) errors in our use of contracts as opposed to runtime contractual behavior-binding (type) errors that can always be detected in a well designed language execution architecture. Which leads us into the discussion of genericity in-static-only-binding-type systems [which have the potential to yield optimum performance at a price in terms of correct behavior and/or expressiveness], in-dynamic-only-binding-type systems [which have the potential to yield correct at a price in terms of performance], and in systems that offer both forms of binding [which has the potential to yield both correct behavior and optimum performance]. Proponents of static-typing and correctness argue the virtues of design-time detection. Proponents of dynamic-typing argue the virtues of unit-testing and the dangers of reliance on static-checking of type-bindings as a substitute for verifying interop relations semantics inherent in any system of basic complexity. Both parties have valid and good points and neither are wrong in my view. Both are addressing the same problem space with different techniques; and both have been shown to eliminate the large proportion of defects [albeit leaving different types of defects undetected]. But, in my view, the significance is in the human "level of effort" factor in expressing an original problem, coming later to understand such a design, and later still working with an existing design to maintain or extend it. ** sigh, I seriously digressed [and now I will be in a deep rathole as people beat me up for errors and/or disagreements with my assertions] ** #2 is principally that given that it is desireable to discriminate a function's implementation based on the types of the arguments, vtable as a polymorphic solution offer no mechanism of support for dispatching to a type-specific implementation based on polymorphism amongst the arguments to a function/method. The general approach is to use hand-crafted secondary dispatch [which for arity-1/1-arg methods is called double-dispatch]. 3. The technical issue is that vtables are slower (on current hardware technology) than using adaptive jitting techniques with self-modifying code. Primarily due to the cost of indirectly accessing memory to obtain an address from a vtable which precludes processors from using eager/optimistic prediction; where accessing the memory also results in bouncing from L1-cache to L2-cache to primary memory [and that is increasingly expensive as the timing gap between those forms of memory increases -- similar in nature to the impact on design that one observed in algorithms designed based on the 50's-70's problem of tape, disk, ram gaps]. *. In a just-in-time binding approach pioneered in Smalltalk during the mid 80's, one uses self-modifying code and assumes that most call sites are not polymorphic [which is generally true]. If they are polymorphic, then that breaks down into the case of having a low-degree of polymorphism [say 2-10 types] and the case of having a large degree of polymorphism which literature in this area popularly terms mega-morphism. See OOPSLA papers from the mid-80's to early 90's. This technique was the basis for the design of the self-language, which in turn led to the design of the Animorphic HotSpot VM/Execution-Engine/Runtime technology for Smalltalk; which in turn was acquired by Sun to try and speed Java [JVM] up. What has not, to my knowledge, been applied is a more generalized solution of the same technique multiple-dispatch (overloading/mult-methods). I have done it for both my own general-purpose dynamic-language virtual machine (AOS Platform), and the Microsoft .NET platform (less-optimally through IL). I must presume that someone must have implemented my technique before; almost certainly someone in the lisp family community. However, it is unlikely that it has also been optimized for hi-performance execution with important newer binding predicates including sandboxing and selector namespaces. Providing hi-performance dynamically-dispatched-multi-methods has significant impact on scripting languages and their ability to evolve into full fledged languages that compete in features and performance with mainstream languages today such as C, C++, Java, [C# will soon be in this group if it is not already], Pascal-derivatives, etc. This is especially important because there are, by most accounts, 10-20 times more people and programs using scripting languages and techniques and that number is likely increasing as cost factors and training/experience come into play. > > [...] > > > It is worse than just describing C++ like mechanism as "the vtable-trick". > > VTables are actually (demonstrably) slower than "true" (receiver only) > > dynamic-binding-dispatch mechanisms. This fact is (reasonably well) > > understood today. It is a reality that will increasingly be the case as long > > as the gap between processor core speeds and L2 cache and memory speeds > > continues to widen. > > > > It is fairly easy to illustrate on the Intel processor family. I've posted > > (on comp.lang.smalltalk within the last 12 months) at least two detailed > > explanations showing the machine instructions, cycle-times, and benchmarks. > > The originally published technique was developed by David Ungar and > > published in OOPSLA papers in the mid-80's. It has been a standard part of > > most jit-based Smalltalk implementations for the last ten years or so. > > are you talking about http://www.sun.com/research/self/papers/type-feedback.html ? > > the idea is quite simple: specialize for a given type of object to allow > inlining. In that case, to know which specialization to have, run-time > feedback is used. This applies well to JITs of course. > > I don't see why it prooves that vtable is bad/slower. vtable can also benefit > from specialization. This is also why the default in C++ in no "virtual" > methods, so that performance is the best. > > This is a well known, no? I think, based on your comments, that you are not aware of what I have been doing for the last ten years or so. One of my professional areas of specialty is the design of virtual machines. Your comments sound like the kind of things I would have written as responses to you . As to the bad/slower, in the last 12 months, I wrote two different threads of discussion on this topic [in comp.lang.smalltalk] describing the instructions, cycles, and benchmark information. I also made reference to that fact somewhere in this current thread of discussion. Where I also mentioned that I had not published information on the much more general techniques (which I suspect I have pioneered) for hi-performance dynamic dispatch of common/important predicates with extensibility for general predicate dispatch through Dynamic-AOP/Managed-Object facilities in the object-model of the AOS Platform [the VM architecture I designed and have been evolving for the last ten years] as well as its related peer/work, an enabler for the Microsoft .NET platform. > > In the ML family, the same happens when going from polymorphic functions > (needing boxing) to monomorphic functions (with unboxed data) > see for example: > - the SPECIALIZE pragma in ghc http://www.haskell.org/ghc/docs/4.04/users_guide/users_guide-5.html) > - type-based unboxing (Leroy) http://citeseer.nj.nec.com/88305.html > > > > > However, I intentionally have not published information on techniques I have > > developed (on the AOS Platform VM) for hi-performance predicate based > > (incl - multi-method) dispatching. Especially with regard to implementation > > on the .NET platform, where I am still exploring with Microsoft [who needs > > this technology as much as Sun/Java does]. > > "Where Do You Want To Go Today?" ;p > > Microsoft has a *lot* of people working on languages. Hopefully many are > allowed to publish their work (and even release GPL apps) I know. As a 3rd party, I and others have been been fortunate to have the opportunity to interact [and influence] quite a few of them [it would be nice to be able to observe the same attitude and opportunity to have an influence on Sun folks]. Of course, Microsoft has a clear business objective, and I both hope and greatly fear they will be very successful in achieving based on their approach [the word trepidation has constantly been in my thoughts since I first got involved with Microsoft on the .NET project in 1999]. The real challenge for scripting and dynamic languages lies in the predominance and momentum of ideas and beliefs regarding type-theory and statically-typed languages; and the relative/disproproportionate lack thereof for dynamic languages (especially OO languages like Smalltalk, as opposed to functional dynamic languages like scheme). > > [...] > > > > i don't know what you call "general tail-recursion". Of course the > > > poor C compiler has hard time analysing things to proove the > > > tail-recursion optimisation is safe. > > > > I think we might be speaking about something without our having the same > > definition of terms. Can you cook up a simple example (or some pseudo-code) > > to illustrate what gcc can do? > > once again: > > http://people.mandrakesoft.com/~prigaux/47.c > http://people.mandrakesoft.com/~prigaux/48.c > http://people.mandrakesoft.com/~prigaux/50.c > http://people.mandrakesoft.com/~prigaux/53.c > Ooops, my goof. I (missed) did not notice that reference in my effort to respond to your previous post. [arghh, sorry about that -- I have a nack for writing posts now and again that spur a very large number of conversations and I get sloppy trying to respond to them and keep myself on a time budget]. Now I've seen the gcc example :). It is optimizing calls from within a function to itself [nice syntactic sugar for goto that I was alluding to in my previous post]. By the way, that is a kind of wack example, that assumes knowledge of the stack frame layouts [which are processor dependent -- especially in light of differing register allocations]. Assuming all variables (args and locals) are allocated on the stack. And that they are allocated linearly. And that f() does not use any stack space itself for variables and arranges for the return-address to be "protected" then: n t-> ---- ---- 10 t1[0] 9 ? o "presumably" 8 ? n 7 ? m 6 ? l 5 ? k 4 ? j 3 ? i 2 ? g "presumably if no other stack use in f()" 1 ? f 0 ? e "not touched" However the "reset()" code which is "decrementing" via "t--" seems like very broken (dangerous) way to test the recursion. I.e., it seems more like this example tests assumptions about GCC variable allocation and stack usage than it does anything to do with tail-recursion optimization. In theory, t[2] is either walked over or is actually pointing at the return-address not unless the compiler did some special mangling to move/protect the return address on the stack [like keeping it in a register]. --- Why not a simple recursion test like: int n=0x7FFFFFFF; char *p=0; void recurse() { char c; if (&c != p) { printf("Stack Consumed At : %d [%lx vs %lx]\n",n, &c, &p); p = c; } if (--n > 0) recurse(); // Extra here to prevent compiler optimizing // away before calling recurse()... p = c; } main() { recurse(); } Am I correct in assuming that gcc has no global/module optimizer mechanism for addressing the general tail-recursion case of "a calls b" with "b calls a", etc? -- Dave S. [www.smallscript.com]