[ruby-talk:26473] Re: Table: Ruby versus Smalltalk, Objective-C, C++, Java;

"Pixel" <[e-mail]> wrote in message
news:[e-mail]...
> "David Simmons" <[e-mail]> 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 <this> as a
> > > > parameter).
> > >
> > > Java, C#... are in the same category
> >
> > I agree, they are broken. But <g> 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 <this>".

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 <g>.

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)

<g> 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" <t> 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 <g> 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 <n>: %d [%lx vs %lx]\n",n, &c, &p);
        p = c;
    }
    if (--n > 0) recurse();

    // Extra here to prevent compiler optimizing
    // <c> 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]