[ANN] SRNC-ST 3.2: Generic Types

The latest version 3.2 of SRNC-ST  (Signature Revealing Naming
Convention - Smalltalk) is available at
http://members.fcc.net/panu/SRNC-ST.htm.

V. 3.2 adds the major new feature of Generic Types to SRNC-ST,  in a
simple way, without having to extend Smalltalk syntax (see below).
Generic Types are a solution to the question: "How do I reuse a
collection interface with different element types?". More generally it
is applicable anywhere where one type serves as a parameter to another.

>From the release notes:

" ...
V. 3.2: Generic Types
To define an interface such as Dictionary, you must define signatures
for methods such as  #at: and #at:put:. In general these methods have
arbitrary Objects as arguments and return values. But what if your
program depends on knowing that more specific types of objects are
stored in a dictionary ? What if you want to constrain the key to be a
String, and the value an Integer for instance ?

In SRNC you can naturally create a subclass of Dictionary specifying
such a narrower interface. But does this mean you have to rewrite all of
the inherited methods that use these types as their interface  ?

No, if you create a 'Generic Type' according to Rule 5 of SRNC-ST.  You
define:

     Dictionary >> at: aKey put: aValue
     ...
     Dictionary class >> Key
     ^anObject
     ...
     Dictionary class >> Value
     ^anObject


For a subclass (sub-interface) of Dictionary called 'StringToIntMap' you
would add the  following overrides:

     StringToIntMap class >> Key
     ^aString

     StringToIntMap class >> Value
     ^anInteger


The method whose return type specifies the meaning of a TSV (Type
Specifying Variable)  is called a 'Type Realizer' (TR). Why are type
realizers *class* methods ? Because if they were on the instance side,
adding a TR would artificially extend the interface of the class using
it. Doing the above example would require that every Dictionary
implements the methods #Key and #Value, even though there is little
value from them at runtime.

By putting the TRs on the class-side we keep them clearly separate from
'real' methods, because they really exist for a different purpose, and
keeping them together makes it easy to understand the generic aspects of
your type specifications.

Rule 5 allows us to specify the properties of a composite type in a
single location, with only few method redefinitions. The information
about the element type is specified "once and only once". Contrast this
to an alternative scheme that somehow defined an explicit syntax for
composite types, like 'aDictionary([String], [Integer])'. If you use
this in 100 places you need to type in 100 x 32 = 3200 characters.   If
instead you define the generic type'StringToIntMap' you need 100 x 14 =
1400 characters, plus the few TR methods needed to define the element
types.

Note also that while it's easy to propose a format like
'aDictionary([String], [Integer])', it is not  easy to define what this
exactly would mean in terms of  individual method signatures.
....
"

Feedbacks welcome.
Thanks
Panu Viljamaa

panu@way.com_nospams (Panu Viljamaa) wrote (abridged):
> V. 3.2 adds the major new feature of Generic Types to SRNC-ST,  in a
> simple way, without having to extend Smalltalk syntax (see below).
> Generic Types are a solution to the question: "How do I reuse a
> collection interface with different element types?". More generally it
> is applicable anywhere where one type serves as a parameter to another.
> [...]
> Feedbacks welcome.

Looks good.

You don't mention related work. Are you aware of "anchored declarations"
in Eiffel? I believe Beta has something called "virtual types" which are
similar. There was a proposal to add them to Java, at:
  http://citeseer.nj.nec.com/thorup97genericity.html

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      [hidden email]      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

Dave Harris wrote:

> You don't mention related work. Are you aware of "anchored
> declarations" in Eiffel? I believe Beta has something called
> "virtualtypes" which are similar. There was a proposal to add them to
> Java, at: http://citeseer.nj.nec.com/thorup97genericity.html

Thanks for  the hint Dave,
I know that "Generic Java (extension)(GJ)  does exist, see:

http://www.cis.unisa.edu.au/~pizza/gj/FAQ/

There is also C++ Templates which are pretty much the same concept.

Generic Java (GJ) looks like this

...
 class Channel<A> {
  private Action.Writer<A> writer;
  private Action.Reader<A> reader;
...

final class Sieve {
  public Process counter
    (final Channel<Integer> out, final Channel<String> done)
  {

SRNCs Generic Types /Type Realizers differ from these at least in the
following:

1. TRs introduce no new syntax to the language. Only a new  
interpretation for a naming convention.

2. C++ Templates etc. make the generic parameter an explicit *parameter
of the class*. This means that you need to make the decision to use a
template-type early on in the design cycle. You must also decide the
number of parameters of the class. After this you can't use the type
without supplying a parameter (or is there a default?). So you have
'ordinary types' and 'template types' which are defined and used
differently.

With SRNC all interfaces are in essence generic, because you can
redefine any of the types used as argument- or return types by simply
adding a new Type Realizer method. Thus any type used by an interface
class is essentially a 'parameter with a default value'. The default
value being the similarly named class.

3.  Since SRNC uses class-methods for indicating the type-parameters, it
means the (default) values of those parameters are inherited. So it
becomes easy to define 'by differentiation' new interfaces, overriding
only the type-parameters you wish in your sub-interface.

4. With templates etc. you define the 'actual parameter' of the type
when you use it. As in the above example when you need a Channel, you
write Channel<Integer>  etc.  In SRNC you would first create an explicit
type called IntegerChannel; this amounts to subclasses 'Channel' and
overriding one class method, say #ChannelType for instance. After this
you refer to it by its name, IntegerChannel, which is easier to look at
and shorter to type than      Channel<Integer> .

5. Further, by redefining the type IntegerChannel explicitly, you are
encapsulating the fact that the parameter is 'Integer'. You can later
change the 'implementation of the type' to use a LongInteger instead for
instance. This is the basic principle of data-hiding.



Thanks again
Panu

panu@way.com_nospams (Panu Viljamaa) wrote (abridged):
> I know that "Generic Java (extension)(GJ)  does exist, see:
>
> http://www.cis.unisa.edu.au/~pizza/gj/FAQ/

Err, yes. There are several proposals for adding genericity to Java. GJ
is one. Virtual Types is another. They are rather different. The virtual
types proposal is by Kresten, Krab and Thorup in Denmark. It is less well
known than the GJ one and unlikely to be adopted (I don't know the
current state of play in Java), but still interesting. The paper title is

    Genericity in Java with Virtual Types

and I gave an URL earlier.


> There is also C++ Templates which are pretty much the same concept.

Yep. GJ, C++ templates, and also "generic classes" in Eiffel, are all
roughly the same concept. Virtual types and anchored declarations are
different, and much closer in spirit to SRNC 3.2.

The Virtual Types proposal looks like:

    class Vector {
        typedef ElemType as Object;
        void addElement( ElemType e ) ...
        ElemType elementAt( int index ) ...
    }

The typedef introduces the "virtual type". "Virtual" because it can be
redefined in the subclass:

    class PointVector extends Vector {
        typedef ElemType as Point;
    }

The typedefs play a similar role to your:

    Vector class>>ElemType
        ^anObject

    PointVector class>>ElemType
        ^aPoint

methods. In both cases there is nothing like Vector<Point>. This echoes
your comments about IntegerChannel versus Channel<Integer>.

Do you see how similar "virtual types" are to your "type realisers"? I
gather this is independent invention. You should take it as a sign you
are onto a good thing. I agree this approach may be a better fit with
Smalltalk/SRNC than the GJ/Templates concept.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      [hidden email]      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

Panu Viljamaa wrote:
>

> 4. With templates etc. you define the 'actual parameter' of the type
> when you use it. As in the above example when you need a Channel, you
> write Channel<Integer>  etc.  In SRNC you would first create an explicit
> type called IntegerChannel; this amounts to subclasses 'Channel' and
> overriding one class method, say #ChannelType for instance. After this
> you refer to it by its name, IntegerChannel, which is easier to look at
> and shorter to type than      Channel<Integer> .

Well, the C++ way would be simply
typedef Channel<Integer> IntegerChannel;
which seems pretty easy to me.

--
Steve Toledo-Brown
Speaking for myself only.
Humans please use reply-to address: nomail is a non-read spam hole.

Stephen Toledo-Brown wrote:

>>
> Well, the C++ way would be simply typedef Channel<Integer> IntegerChannel; which seems pretty easy to me.

This is easy indeed, and adds quality to the software. But since it is
not *required* practice, many programmers won't follow it. Therefore you
see the 'ugly'  < Integer >  more often than not in C++ programs. In
SRNC-ST  the *only* way to define composite/generic types is to give
them a name.

As I argued in my  reply to Eric Fruttero, a construct like "Channel
<Integer >" (typically) unnecessarily exposes the internals of the
data-structure to its users, and creates a 'wide' interface which is
harder to reuse.

But in XP terms,  "Channel <Integer>" violates the "Once and only once"
rule, ( if  you use that type more than once). If you But more
importantly you keep the ability to change the properties of that type
in "one and only one" place -  to keep it only as wide as necessary.

I assume you agree, since you advocated the typedef approach above. I'm
just trying to analyze why it is such a good practice.
-Panu

Dave Harris wrote:

Thanks for the comment Dave.  You are right.

As Stephen Toledo-Brown pointed out, typedefs can also be used in
C/C++.  But I assume with VirtualTypes they are more or less 'required',
which is a good thing.

-Panu

Sorry, a sentence somehow got clipped offf:

Panu Viljamaa wrote:

> But in XP terms,  "Channel <Integer>" violates the "Once and only
> once"  rule, ( if  you use that type more than once). If you But more  
> importantly you keep the ability to change the properties of that
> type  in "one and only one" place -  to keep it only as wide as
> necessary.

Should read:
.... "Channel <Integer>" violates the "Once and only once"  rule, ( if  
you use that type more than once). If you type IntegerChannel instead,
you save 2 characters <> every time you use that type. But more
importantly you keep the ability to change the properties of that type  
in "one and only one" place -  to keep it only as wide as necessary.

Thanks & Sorry
-Panu

[hidden email] (Dave Harris) writes:


I can't resist pointing out, because this only recently sunk in: in
this code, PointVector is no longer a subtype of Vector, because you
can only store Point's into it.  Yet, I bet Virtual Types would allow
the following:

        Vector v = new PointVector();
        v.addElement(new Integer(12));  // allowed by Vector,
                                        // but not by PointVector

If it doesn't allow it, then it probably doesn't allow the following,
which is perfectly type safe, since the vector is only read and not
written:

        Object foo(Vector v) {
                return v.elementAt(1); }
        ...
        PointVector pv;
        ...
        foo(pv);



A big problem in OO typing is that, for convenience, classes are
usually allowed as types.  However, full classes make it very hard to
have true subtyping relationships -- there are just too many available
methods in a typical class.  Mentally we tend to thinking about
subsets of the interfaces, but it would seem to be a pain to be
explicit about things like "ReadableVector" versus
"ReadableWritableVector".


-Lex

[hidden email] (Lex Spoon) wrote (abridged):
> I can't resist pointing out, because this only recently sunk in: in
> this code, PointVector is no longer a subtype of Vector, because you
> can only store Point's into it.  Yet, I bet Virtual Types would allow
> the following:
>
>         Vector v = new PointVector();
>         v.addElement(new Integer(12));  // allowed by Vector,
>                                         // but not by PointVector

The proposal makes that a runtime error. This is consistent with Java
arrays, eg:

    Object[] array = new Point[10]
    array[0] = new Integer(12);  // Allowed by int[] but not by Point[].

In other words, Java arrays are covariant. Method arguments which take
virtual types are also covariant. You can use a PointVector as a Vector
provided you don't try to store a non-Point in it.


That is allowed and is statically type safe.


> A big problem in OO typing is that, for convenience, classes are
> usually allowed as types.  However, full classes make it very hard to
> have true subtyping relationships -- there are just too many available
> methods in a typical class.  Mentally we tend to thinking about
> subsets of the interfaces, but it would seem to be a pain to be
> explicit about things like "ReadableVector" versus
> "ReadableWritableVector".

Indeed. The Virtual Types paper I referenced earlier puts it this way:

   The type system of an object-oriented programming language
   will always reflect some tradeoff between the following
   three desirable properties: covariance typing, full
   static typing, and subtype substitutability.

The paper has a critique of Java's type system and a rationale for their
choice of extending it. Although static type checking isn't a focus of
SRNC, I think their choice would fit reasonably well with Smalltalk.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      [hidden email]      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

Lex Spoon wrote:
What an earth is the point of this?  Why not just allow
covariance in method overrides?

Sorry I missed the start of this .. anyone got a reference
to the detailed proposal for virtual types?

Does it sort out the mess when previously separate method
declarations (differing only in arg. type) start to clash
in subclasses due to virtual type redefinitions?

As far as I can see, explicit virtual types offer no
advantage over just allowing covariant method overrides.
Unless of course it supports Eiffel-style type anchoring.
Then, for example, it would be very handy to have

  class Object {
    typedef ThisType as Object
    public ThisType clone() {..}
    public boolean equals( ThisType other ) {..}
    ..
    }

  class BrazilianTreeFrog {
    typedef ThisType as BrazilianTreeFrog;
    }

for now you get proper type checking on your most general
operations without having to downcast all over the place.
Does the proposal allow this?  

--
http://www.mk.dmu.ac.uk/~gperkins/

[hidden email] (Graham Perkins) wrote (abridged):
> What an earth is the point of this?

Well, you notice that the PointVector class does not declare any method
overrides? Yet the (inherited) methods will be retyped correctly. The
virtual types proposal gives a form of covariant typing together with a
single point of update for the type.


> Sorry I missed the start of this .. anyone got a reference
> to the detailed proposal for virtual types?

  http://citeseer.nj.nec.com/thorup97genericity.html

Or search for "Genericity in Java with Virtual Type", Kresten, Krab,
Thorup, ECOOP 1997.

The original discussion was about SRNC-ST 3.2.


> As far as I can see, explicit virtual types offer no
> advantage over just allowing covariant method overrides.
> Unless of course it supports Eiffel-style type anchoring.

Yes, it allows that. Wasn't it obvious? The example you ask for is almost
exactly the same as the example you quoted.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      [hidden email]      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

I came late to this thread, so what I am about to say may have been said
before...

"Graham Perkins" <[hidden email]> wrote in message
news:[hidden email]...
This is exactly how virtual patterns work in a computer language called
BETA.  see www.mjolner.dk for a BETA compiler.  Basically, a pattern is a
construct not unlike a class, and it is used in place of other constructs:
packages, functions(!), classes, inner classes, closures, generic types.  I
found it a difficult language to program in, but completely fascinating.
One of the problems is that the pattern construct is too overloaded!

> > >
> > >     class PointVector extends Vector {
> > >         typedef ElemType as Point;
> > >     }
>
> What an earth is the point of this?  Why not just allow
> covariance in method overrides?

The point is, it allows the internal representation of the base class to be
modified by the subclass.  This can be used to create generic container
classes, a la STL in C++.  Allowing covariance in method overrides doesn't
solve this problem.

Cheers,
Andrew

Could you spell out how your proposal will cause a type error in my
example above?  How does one declare "v" such that adding integers to
it will not be allowed in the specific cases that a PointVector is
used instead of a general Vector?  Keep in mind that v might be a
method parameter, and that the "new PointVector()" might not be
visible at compile-time (eg, it might be in a dynamically loaded
class).




Thanks for pointing out Java arrays as a simpler case of covariance
going wrong.  Here's a full program with a type error that the
compiler misses:


==== example ====
public class Test
{
public static void main(String[] args)
{
    Object x[] = new Integer[100];
    x[3] = new Float(1.1);

    System.out.println(x[3].toString());
}

}
================


(Especially interesting is that there's no type cast!)


-Lex

[hidden email] (Lex Spoon) wrote (abridged):
> > The proposal makes that a runtime error.
>
> Could you spell out how your proposal will cause a type error in my
> example above?

It's not my proposal; the authors are Kresten, Krab and Thorup, and I
gather something similar is implemented in Beta, Ada and Eiffel.

For Java, they propose that the compiler expand the addElement() call to
include a type-test, so it becomes like:

    v.addElement( v.cast$ElemType( new Integer(12) ) );

where the cast$ElemType is a compiler-generated virtual function, like:

    Object cast$ElemType( Object o ) {
        return (Point) o;
    }

It has to be virtual because there may be further subclasses of
PointVector. Of course a smart compiler/linker/loader/VM can optimise in
various ways.


> How does one declare "v" such that adding integers to it will not
> be allowed in the specific cases that a PointVector is used instead
> of a general Vector?  Keep in mind that v might be a method
> parameter, and that the "new PointVector()" might not be visible
> at compile-time (eg, it might be in a dynamically loaded class).

Just declare "v" normally. Eg:

    void add( Vector v, Integer i ) {
        v.addElement( i ); // Runtime error!
    }

It doesn't matter that PointVector is loaded at runtime - the
cast$ElemType() method will be loaded with it. Obviously optimisations
such as inlining of cast$ElemType() methods will have to be backed out of
and reconsidered when a new subclass is loaded. This is standard
operational procedure for HotSpot style JITs.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      [hidden email]      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

[hidden email] (Dave Harris) writes:


Ahhh, I misread "runtime" as "compile time" above.  Well, for what
it's worth, the same effect is generated with a type checker that
allows covariant overrides: you fall back on runtime tests in the
above case.  I'm guess this system is more general, though.



-Lex