Josh Stern (jstern / foshay.citilink.com) wrote:
> Reimer Behrends <behrends / cse.msu.edu> wrote:
> >Josh Stern (jstern / foshay.citilink.com) wrote:
> >> There is a real, non-trivial, example of template
> >> genericity being used to express mathematical ideas
> >> in the CGAL library:
> >> 
> >> http://www.cgal.org/Manual/doc_html/frameset/fsKernel.html
> >> http://www.cgal.org/Manual/doc_html/frameset/fsBasic.html
> >> 
> >> How to do such things in Ruby in full generality (efficiency
> >> aside)?  
> 
> Reimer, you misunderstood the pragmatics of my post.

Umm, no. But I was simply using it as a jumping-off point to discuss
matters that had been raised througout the thread. If you felt
"targeted", my apologies. I was simply using this as an opportunity to
go into lecture mode. :)

> It had previously  been asserted in the discussion that
> Ruby would have trouble with full blown generic programming
> because of the lack of overloading and and automatic instantiation
> of overloaded functions for the generic parameters.

Yes. This, of course, is wrong. Which is why I was giving a more
complete picture as to how genericity can be viewed as an example of
inheritance, for instance. I would again advise that people familiarize
themselves with, say, Beta's virtual patterns. It should be obvious that
classes in Ruby can do pretty much all that patterns can do. Example:

class Polynomial < Ring
  
  def type
    nil # Formal type, undefined
  end

  # add the usual operations on polynomials here, dependent
  # on the result of 'type'.

end

class ComplexPolynomial < Polynomial

  def type
    Complex
  end

end

Now, you may want to modify this to avoid speed problems (e.g.,
computing the function only once and sticking it in a variable,
or using eval/class_eval/etc. to generate an optimized class on
the fly), but the general idea is that in Ruby you can redefine
any aspect of a class, including types, exceptions that are
caught, and whatnot. Put a number of such functions in there,
perhaps encapsulating them in a mixin, and you essentially
have the functionality that are covered by traits.

[...]
> >To begin with, for the most basic use of generic types, no additional
> >effort is necessary--Array and Hash are obvious examples. 

This was simple just noting something important--a large majority
of generic types simply require that the objects they manipulate
simply respond to certain messages--no additional measures are
needed. Just because C++ or Eiffel as statically typed languages
need the types as parameters doesn't mean the same for Ruby or
Smalltalk.

> A main idea of the traits technique is that one may bundle
> all of the generic inteface in a kind of proxy class.

A main idea of the traits technique is that in a compiled language you
somehow have to juggle things around so that the compiler won't
complain. In dynamically typed languages, factory objects will usually
provide the same information that you have elsewhere nicely. If it's
needed at all.

The big problem in C++ is that you have to determine _at compile time_ a
number of things. In Ruby, first of all, many of these don't need to be
determined. Secondly, there's no real difference between compile time
and runtime in Ruby. So, while C++ template mechanism essentially
provides yet another Turing-complete engine (with the concomitant cost
increase for developing correct compilers and other language tools),
dynamically typed languages can just ignore this.

What I'm saying here is that most of the tools for generic programming
in C++ are artifacts of the language, not a prerequisite for using the
techniques.

[...]
> >For more
> >advanced schemes, it may be best to avoid the elaborate and
> >unnecessarily complicated maze of C++ templates and return to simpler
> >approaches. 
> 
> C++ templates aren't actually complicated, but anyway, that's
> off the point anyway.

I'm not sure if you've ever thought about the inherent complexity
of implementing the C++ type mechanism completely and correctly in a
compiler? I played around with trying to do a formal specification
in Z a while ago, which was bad enough. In other words, I'm not
saying that a user can't understand it, but that it adds unnecessary
complexity to the language specification and implementation.

> For instance, the instantion of a parametric type A[X] as
> >A[T], where X is a formal parameter and T a concrete type, can be seen
> >as specialization inheritance from A[X] with X = T. What we need for
> >this to work is to be able to work with types as first class
> >objects--something that C++ can't do, 
> 
> a) that's not necessary

True, Eiffel 2 did it without having types as first class objects, but I
was simplifying here (expressing a sufficient, not a necessary
condition). What I basically mean is that having classes as first class
objects (or an equivalent mechanism) eliminates most of the problems.
C++ "solves" the problem by making the template mechanism a small
programming language of its own, where classes _are_ first class
objects--an exercise that would be absolutely pointless in Ruby.

> b) the traits technique approximates the same thing anyway.

See above.

> >but Ruby can. Instantiating formal
> >parameters of generic types is basically constraining a family of
> >objects along one more dimensions. While I believe that somebody
> >mentioned earlier that genericity and inheritance are orthogonal
> >concepts, the opposite is true: generics introduce a classical is-a
> >relation, generally with full substitutivity (modulo the usual
> >covariance issues).
> 
> I don't understand which is-a relationship you are talking about here.
> Could you give an example?

Simple. Let Polynomial[X] be the generic type of polynomials over a
ring. Then we have

	Complex < Field < Ring,

and thus

	Polynomial[Complex] < Polynomial[X],

where the relation < expresses a subtyping relationship (modulo
covariance issues, which we tend to naturally ignore in Ruby anyway,
since only type theorists tend to get worked up over them).

> >Instantiating the formal paramaters would then be the
> >equivalent to performining currying on 'initialize'. 
> 
> Have to ask you again for an example.  I know currying
> and initialize, but I'm not sure what your vision is
> here.

Class Polynomial < Ring

  def initialize(type, data)
    @type = type
    ... do something with 'data', based on @type ...
  end

  # Add usual operations on polynomial here, depending
  # on @type.

end

Class ComplexPolynomial < Polynomial

  def initialize(data)
    super Complex, data
  end

end

> It should also
> >be noted that just because something is part of C++ it should not
> >necessarily be added to another language; in fact, the converse is
> >generally true.
> 
> I wasn't advocating that.

Sorry. I wasn't trying to claim you did. I was just noting in general
that I usually question the wisdom of importing most of the hacks that
are native to C++ into another unsuspecting language. They generally
come with a ridiculous cost in terms of specifying them properly and
implementing them. For instance, while the fact that the grammar of
C++ isn't LR(k) for any k has certainly served to advance the field
of parsing technology (ANTLR, BTYacc), it hasn't made the language
proper commensurately more expressive.

> Though I have suggested in other posts
> that overloading would be useful in Ruby, but for somewhat different
> reasons.

Overloading doesn't make sense in the context of Ruby, since it requires
static type declarations as a prerequisite. You are probably referring
to multiple dispatch, which is a feature of a number of other languages
(such as Dylan), but not C++.

				Reimer Behrends