Generic ordinary functions, and/or forward references of methods from outside a class

[GoogleCodeExporter]

Currently crack allows forward declarations of classes, but not of the methods 
they contain (from outside the class).

I have a situation where I have two classes, methods for which return instances 
of the other class. One of the classes is generic.

class Class1 {
   Class2 method1();
}

class Class2[T] {
   Class1 method2();
}

Unfortunately this is not possible at present because I can't call the 
constructor for Class2 from method1 as it is a forward reference.

One way around this (in my use case) would be to make method2 an ordinary 
function, rather than a method of Class2. Unfortunately, whilst it seems to be 
possible to create generic methods, it isn't possible to create generic 
ordinary functions.

Class1 method2[T](T b);

On the other hand, I'd really want T to be inferred from the type of b when 
method2 is called.

Original issue reported on code.google.com by goodwill...@googlemail.com on 29 Dec 2014 at 2:55

[GoogleCodeExporter]

I don't quite understand your example, but the work-around for creating generic 
functions is to create a static function in a generic class:

class Wrapper[T] {
    @static Class1 method2(T b) { ... }
}

I concede the desirability of generic functions, though.

Original comment by mind...@gmail.com on 31 Dec 2014 at 2:25

• Changed state: Accepted
• Added labels: Milestone-Post-1.0, Type-Enhancement
• Removed labels: Milestone-0.2, Type-Defect

[GoogleCodeExporter]

Sorry my example was so badly explained. It's hard to write correct code that 
doesn't compile. :-)

Let me try to explain more carefully.

I want to implement a type hierarchy that looks like this:

Integer
Poly[Integer]
Matrix[Integer]

and I want it to be recursive, so that types such as:

Matrix[Poly[Poly[Integer]]] are possible.

Clearly this requires numerous things. I'm not in the business of insisting 
that language implementors go a certain route. I'm happy to wait a year or two, 
see what inventive things crack has done, and try to fit my use case into the 
existing syntax.

That said, let me explain the difficulties I had in implementing this as crack 
currently stands. It's nice for language designers to have specific use cases 
in mind, even if they don't end up explicitly supporting them with the language 
syntax.

Obviously the two things one requires to do the above are:

1) a fully recursive type system
2) generic functions or something similar

Let me first of all comment that I don't understand the need for forward 
references of classes. Until instances of classes are actually created, there 
is surely no need to do anything with the class definitions, except check that 
they parse correctly. This can still be done with a single pass (or perhaps 
crack is too context sensitive for this?).

But, let us accept that crack has decided to require forward references for 
classes to simplify implementation of the language.

Suppose that I want to create a function called parent. It will return an 
object of type Parent, instances of which, for the purposes of this ticket, do 
two things:

1) Contain a String representation of some human readable information.
2) Overloads the call operator for instances of Parent.

class Parent {
   String desc;
}

In fact, the parent function will not just return a plain Parent, but will 
always return an object derived from Parent, depending on the type of the 
object it is passed. For example, if passed an Integer, parent will return an 
instance of the following class derived from Parent:

class IntegerRing : Parent {
   oper init() { desc := "An integer was passed to parent"; }
   oper Integer call(int a) { return Integer(a); }
}

A similar PolyRing and MatrixRing class would also be derived from Parent, 
though in that case they would be parameterised on some type T.

Now we wish to implement the parent function itself. The obvious way is to make 
parent a method of each of the classes we want to support. So in the Integer 
class for example, we'd have:

class Integer {
 #....
 Parent parent() { return IntegerRing(); }
}

All of this mucking around allows us to do:

a := Integer(12);
R := a.parent()
c := R(13);

So what currently goes wrong:

1) Note Integer.parent currently calls the constructor for IntegerRing. The 
call operator of IntegerRing currently calls the constructor for Integer. The 
problem is, crack does not allow forward references to methods, and thus they 
cannot call each other. Thus the type system is effectively not fully recursive.

2) The other option is to make parent a global function. This can be done as 
follows:

Parent parent(Integer b) {
   return IntegerRing();
}

(Aside: I like this a lot, but I suspect if you follow it to its conclusion it 
takes crack way off course, i.e. away from the class based OOP it is based 
around. But let me examine the possibility below to see where it leads.)

(Aside 2: Note it is important that parent return an instance of Parent, rather 
than the Parent class itself, because it may need to contain information that 
is taken from inside b, i.e. it varies not just with the type of b but also 
with the value of b (not relevant for Integer, but certainly for other 
mathematical types).)

Thus we cannot in general have:

Parent parent(Integer b) {
   return IntegerRing;
}

The parent function must instead return an instance of IntegerRing.

The problems begin when we try to do all this for the generic classes Poly[T] 
and Matrix[T]:

class Poly[T] {
  # ...
}

Now I want to be able to do:

a := Poly[Integer]("x^2 + 2x + 1");
R := parent(a);
b := R("x^3 + 1");

[[Even better, I'd like to be able to do:

R, x := PolynomialRing(IntegerRing, "x"); # this returns a tuple consisting of
                                      # x := Poly[Integer]("x"); and
                                      # R := parent(x);
b := x^3 + 1;
c := R(1); # creates a constant polynomial
S, y := PolynomialRing(R, "y");
f := y^2 + x*y + 2*x + 1;
g := S(x + 1); # constant polynomial in y

wherein one can see the utility of all this stuff.
]]

Now the function definition for parent will have to look like this:

PolyRing parent[T](Poly[T] a);

But now I need ordinary generic functions. But I distinguish generic functions 
from template functions. 

A template function would require me to do the following:

R := parent[Integer](a);

where a is of type Poly[Integer]. This is pretty unusable, since it requires 
one to know the parameter of the type of a, which is more or less precisely 
what we are trying to prevent the consumer from having to know.

A proper generic function would allow:

R := parent(b);

The big advantage of this is that precisely the same syntax is required for 
parent if b is an Integer as it is if b is a Poly[Integer].

In other words, crack would infer the type T in a generic function from the 
types of its operands. Of course properly generic functions do come with 
issues, such as resolving ambiguities, allowing specialisations for concrete 
types, type destructuring, triangular dispatch, and they lead to a desire to 
somehow be able to restrict the parameters T to certain classes of types (e.g. 
using interfaces, typeclasses, traits or something similar) and then there are 
issues with inheritance, and so on. Probably it would be a major diversion.

Anyway, I think the paradigm crack really encourages is for parent to be a 
method, not a global function. And I think this is fine.

But as noted, it is only possible to do that if either:

1) forward references are not needed in crack
2) forward references to methods are allowed

Sorry for the very long winded explanation.

Original comment by goodwill...@googlemail.com on 31 Dec 2014 at 5:22

[GoogleCodeExporter]

Thank you for the long-winded explanation :-)

1) Crack requires forward declarations because it is single-pass and (except at 
the expression level) AST-less.  This was a premature optimization.  In 
retrospect it is unlikely to have had any significant impact on performance.  
The next major version of the language will likely depart from the single-pass 
approach and forward declarations will no longer be necessary.
2) I agree that generic functions (as you've described them, using type 
inferencing instead of explicit parameterization) should be added to the 
language.
3) In your case, I think there is an elegant work-around because methods _can_ 
be forward declared in a class context, so you can write this with your Parents 
as nested classes:

class Parent {
    String desc;
    oper init(String desc) : desc = desc {}
}

class Integer {
    # Note that the return type must be the derived parent class, and not parent, for your oper call trick to work.
    # Crack's method dispatch is constrained by the compile-time type of a value.
    class Ring;
    Ring parent();

    oper init() {}

    class Ring : Parent {
        oper init() : Parent('test') {}
        Integer oper call(int a) { return Integer(); }
    }

    Ring parent() {
        return Ring();
    }
}

class Poly[T] {
    class Ring;
    Ring parent();

    oper init() {}

    class Ring : Parent {
        oper init() : Parent('more test') {}
        Poly oper call(String a) { return Poly(); }
    }

    Ring parent() {
        return Ring();
    }
}

i := Integer();
p := i.parent();
i2 := p(100);

poly := Poly[Integer]();
polyp := poly.parent();
poly2 := polyp('x**2 + 1');

The above code compiles and runs (with the addition of Revision ef7b62cf9b53, 
which fixes a bug in forward class declaration that I discovered while coding 
this, thanks!)

Does this work for you?

Original comment by mind...@gmail.com on 1 Jan 2015 at 4:56

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

That's an elegant solution, thanks!

One slight wrinkle I forgot to mention is that b.parent() for b of type integer 
should be "singleton", in the sense that for any integer b you get precisely 
the same instance of IntegerRing.

Basically, one needs ZZ := IntegerRing(); somewhere. Then b.parent() should 
return ZZ regardless of b. This is so that a.parent() == b.parent() for integer 
a and b always returns true.

I forgot about this requirement when I spelled out the issue above.

That can of course be done with some kind of caching. So there's a workaround.

Original comment by goodwill...@googlemail.com on 1 Jan 2015 at 6:07