search

chapel-lang / chapel

a Productive Parallel Programming Language
https://chapel-lang.org
Other
1.79k stars 421 forks source link

User-defined Coercion and Cast Syntax #5054

Open mppf opened 7 years ago

mppf commented 7 years ago

Chapel currently supports user-defined casts but not coercions. However, the way to declare a user-defined cast is undocumented and odd. Here is an example:

proc _cast(type toType, src) where isSomeType(toType) {
     ...
}

It would be nice to have a more user-facing feature here.

One proposal for the way to declare a user-defined cast is like this:

proc sourceType.cast(type toType) {
     ...
}

and then the way to indicate automatic coercion was possible between sourceType and toType is like so:

proc sourceType.coercible(type toType) param {
     return true;
}

Some sample use-cases include:

Design questions

updated with conclusions from discussion below:

  1. Should coercions be handled by something indicating if coercion is possible, and then a call to the cast function if so?

TODO based upon discussion below

  1. Should the cast be declared as a method or as a function? Or as a type method?

TODO based upon discussion below

  1. Can user-defined coercions be applied to method receivers?
damianmoz commented 5 years ago

Is this technique ever be likely to enable user to create a bit-wise image of a real(w) into a uint(w), and vica-versa, without any overhead. By this I mean being able to achieve something that the following C does. Otherwise, deep IEEE introspection and manipulation carries a big overhead which would cripple any chance of optimal code.

typedef unsigned long _REAL;
typedef double REAL;
assert(sizeof(REAL) == sizeof(_REAL));
typedef union { REAL rawValue;  _REAL bitImage; } _754;
...
REAL x = ...
...
_754 t = { x };
// at this point t.bitImage will contain the bit-wise image of the floating point number t.rawValue.
mppf commented 5 years ago

@damianmoz - I don't think user-defined coercions or casts would help with that. I think we can make the Chapel compiler support a way to do that, but I wouldn't expect to write it with a cast (since cast from real to uint takes the integral portion as a positive number). Anyway any proposal in that area should go in a separate issue.

damianmoz commented 5 years ago

I can handle a separate issue. I will try and document it. Note that something like

var x = 56.789:real(64)
var encodingAsPerIEEE754 =  x:void(64):uint(64)
...
var xModified = encodingAsPerIEE754:void(64):real(64);

would do the job if the concept of a void or opaque type of a certain number of bytes ever comes into existence. I can do this sort of thing currently with a function call to C but that has totally unacceptable overhead. I will try and put together a design document over the next few weeks.

mppf commented 5 years ago

@damianmoz - I went ahead and created #12053 but I consider it your issue and would be happy to update/replace the issue description. But I wanted to respond to something you said and it doesn't make sense to continue doing that here....

mppf commented 4 years ago

Over in #16576 we are discussing if an init= between types should enable type conversion when passing to in - that is, if such a cross-type init= should enable implicit conversions.

It seems we would still need a separate way of describing a cast. init: is one such proposal but I wonder if we would consider proc : as an alternative

someExpr : someType;

Would end up calling : (someExpr, someType). And so one could write e.g. proc : ( arg: MyRecord, type t:numeric).

Or maybe naming the function : is problematic in some way and it needs to be named cast.

Anyway it seems like if a compatible init= exists, then a cast could/should call that. I'm not really sure whether supporting cast but not implicit conversions should use an initializer (like init:) or a free function (like : or cast).

mppf commented 4 years ago

Regarding this comment

we came up with two pretty good motivating examples that can clarify some of the choices we are facing about whether or not coerce should be able to accept a type argument.

This issue seems similar to what init= faces with the variable type being declared sometimes and not other times. For init=, it is solved by this.type (see the init= technote ). I suspect it could be solved by this.type as well for a proc init:.

... during generic instantiation, we need a way to know which domain type to create based upon the range type. And we can't pass the expected type as an argument to a coerce method because we can't pass a generic type as a type argument in Chapel.

That is no longer true. Generic types can be passed as type arguments. So, we could have a cast/coerce function always accept a type argument if we want to.

vasslitvinov commented 4 years ago

If we express a user-defined cast as init:, then it will probably have to produce a value of the cast-to type. This may be too restricting or, conversely, be a desirable property. Cf. a standalone function could potentially return anything.

mppf commented 4 years ago

For something like Matrix wrapping an array, I am thinking about how extending forwarding might be better than any path involving things like init=.

Here is a sketch of the direction:

One interesting implication is that because forwarding is sortof "last resort" a natural extension would have the behavior that the implicit conversions enabled by ref fowarding would only be used if there is no other candidate available (anywhere).

Additionally we have been considering whether or not init= could serve as the way to enable implicit conversions - so that MyType.init=(arg: OtherType) means that OtherType can be implicitly converted to MyType. At the same time, several discussions of implicit conversions have requested not allowing cycles in implicit conversions.

I'm thinking that the init= approach is not really tenable if we don't allow cycles.

Consider a Matrix record containing an array. It would make sense for this Matrix type to allow assignment from arrays of compatible shape. Additionally, it would make sense to allow assignment to arrays with compatible shape from the matrix type:

  var m: MyMatrix = ...;
  var a:[m.domain] real = ...;

  m = a; // sure, this makes sense, it's just setting the matrix elements
  a = m; // sure, this also makes sense, it's just setting the array elements

Now since we have split-init, it's easy to create cases similar to the above that will convert default-init and assignment to a call to init=.

  var m: MyMatrix;
  m = someArray; // split-init -- converts to MyMatrix.init=(someArray)

  var a:[D] real;
  a = m; // split-init -- converts (notionally) to array.init=(m)

As a result, the natural pattern of legal = for the Matrix type would imply that we need init= in both directions, which would lead to a cycle in implicit conversions if init= implies implicit conversions.

So, instead, I think we need to have a separate way to opt in to implicit conversions.

For the Matrix type in particular, we might imagine having a sort of implicit conversion from a Matrix to its array - such as the ref forwarding idea above. We could also/alternatively imagine having an implicit conversion from a compatible 2D array to a Matrix. It seems to me that we have to choose only one of these two if we want to avoid cycles.

I think an interesting next step is to think about what is the problem with cycles and see if we can find any published/online resources about problems people might have run into with the C++ system.

mppf commented 4 years ago

I think an interesting next step is to think about what is the problem with cycles and see if we can find any published/online resources about problems people might have run into with the C++ system.

There is the Google C++ style guide which indicates that implicit conversions should generally not be defined but that they can sometimes be necessary and appropriate for types that are designed to be interchangeable. The Pros and Cons listed there are interesting and worth considering further. Can we come up with a design that avoids most of the Cons? I think these are the relevant Cons:

This is a similar sentiment to Scott Meyer's More Effective C++:

Chapel's current init= story is already relatively similar to the Rust into trait. See e.g. https://doc.rust-lang.org/rust-by-example/conversion/from_into.html#into . The conversion is allowed when the type being converted to is obvious enough. The difference between Rust and Chapel here is that the source of the conversion is decorated with .into() in Rust (but not in Chapel). (And Rust allows the .into() conversion to handle a call argument while Chapel does not currently allow that with init=).

For example, here is a Rust program where the use of .into() converts at a call site to a type that is not known until the call is resolved. There is a type Number that can be created from i32 . An argument of type Number can be passed the result of an my_i32.into().

``` rust use std::convert::From; #[derive(Debug)] struct Number { value: i32, } impl From for Number { fn from(item: i32) -> Self { Number { value: item } } } fn accept_number(num: Number) { println!("My number is {:?}", num); } fn main() { let int = 5; accept_number(int.into()); // separately, initialization works as long as there is a type declaration //let num: Number = int.into(); //println!("My number is {:?}", num); } ```
mppf commented 4 years ago

this issue is related in some ways to Implementing type inference in module code #14213 because the compiler currently allows implicit conversions from a type to what its copy-init produces. So having a way to indicate that its copy-init should produce a different type is relevant.

mppf commented 3 years ago

Here is a table of some of the use cases of implicit conversions that I have been thinking about.

Use Case What is the Explicit Alternative? is ref access important? are the conversions only within the type? is the conversion out of the new type? is the conversion into the new type? is the conversion the same as type inference for var x = ... ?
range(int(8)) -> range(int) myRange : range(int) x
unit library conversions lenInFeet : length(meters) x
range -> domain {myRange} x
int -> bigint new bigint(i) x
CharProxy -> char myCharProxy.char maybe x x
RefType -> Value myRefType.val maybe x x
SumExprType -> Value myExpr.eval() x x
Array View -> Array var arr = myView x x
sync t -> t mySync.readFE() x x
managed ptr -> borrow ptr.borrow() x
version -> tuple ver.version x

Is ref access important? For something like RefType or CharProxy, we could simply expect that = be available to set it, and then maybe it is not such a big deal if you cannot get the reference to the element directly. In fact, some proxy objects might solve a race condition by preventing such access.

What about for the Matrix type? Well, the Matrix type itself isn't particularly useful on its own, beyond just using a 2D array (with the possible exception of allowing * to do matrix-matrix multiplication, but the alternative strategy of adding another operator for that is a reasonable alternative (see issue #16721) ). What would be really useful in linear algebra is to have different sorts of Matrix types that contain properties. For example, a type for a triangular matrix and a type for a diagonal matrix. These types represent a 2D array along with a special property it has. Does it make sense to have user-defined coercions for DiagonalMatrix or TriangularMatrix types? I don't think it does

mppf commented 3 years ago

Following on to https://github.com/chapel-lang/chapel/issues/5054#issuecomment-726873643 here is a list of Pros and Cons of user-defined implicit conversions in any form

Pros:

Cons:

(See PR #13442 for details about overload set checking)

bradcray commented 3 years ago

Some random notes on the last few posts:

if we want to avoid cycles.

I've said this out loud and elsewhere, but I'm not convinced that cycles are inherently problematic, particularly if we don't permit multi-hop coercions. So I agree with this:

I think an interesting next step is to think about what is the problem with cycles

As a simple but arguably easy-to-dismiss example of cycles being handy (or at least "not obiously bad"), we support coercions from bool(8) to bool(64) and from bool(64) to bool(8) without apparent problems. And both directions arguably make sense since there's no information loss. But this is also not a particularly interesting example because it's just a single bit of information in different memory representations.

I've said this to Michael but when I think about initializations of arrays from other types, I think of this less as a coercion or special assignment specific to that type, and more about the notion of assigning from one iterable object of compatible shape/size to another. That is, I think of My1DArr = someExpr as less being about a special = or init= overload for the type of someExpr and more as a legal zippering between it and My1DArr.

range -> domain

I don't think of this as a coercion or assignment we support so much as some special-casing we've done in certain scenarios. For example, by supporting var A: [1..n] ... I think of us as having special-cased array creation to support lists of ranges as a convenience to avoid writing var A: [{1..n}]... rather than interpreting it as a coercion from range to domain. Put another way, it would worry me if we supported my1DDomain = 1..3; [Checking, I see that we do]. I'm not sure we should continue to do so. It seems more like a way to get confused than to support important patterns.

Here is a table of some of the use cases of implicit conversions that I have been thinking about.

I think t -> sync t is another important / key case to think about.

Can lead to call site ambiguities

I don't know that I think of this as a con in the sense that if it could convert to multiple types, you'd want to know that it's an ambiguity rather than having it just pick one. I suppose the real con is that perhaps you wrote the code when only one function existed and then another is introduced, causing a new ambiguity and "breaking" your existing code (but still, you'd rather have it do that then silently call the other function). I find myself wondering whether some sort of --prevent-coercions flag could be supported to help users who feel defensive about such possibilities avoid unwittingly relying on coercions in their code.

mppf commented 3 years ago

I think t -> sync t is another important / key case to think about.

Thanks, I've added that. I also added SumExprType (for e.g. something lazily evaluating addition of GMP numbers as the C++ support does). I also updated the Con you elaborated on.

if we want to avoid cycles.

particularly if we don't permit multi-hop coercions

C++ has the limitation of not permitting multi-hop user-defined coercions (although you can have a built-in numeric conversion on either end). One effect of this is that it becomes more observable when a proxy type is being used. For example, if I have a SumExprType type representing a lazily evaluated sum of two GMP integers, but GMP integers can implicitly convert into to GMP rational numbers, then I wouldn't be able to pass a SumExprType into a function expecting a GMP rational number (when maybe I would expect that I could).

For this reason I have been leaning towards a restriction of no cycles instead of a restriction of no multi-hop conversions (although we could certainly have both restrictions).

(Separately, I found this discussion of why C++ only allows one user-defined conversion - https://stackoverflow.com/questions/21337198/why-user-defined-conversions-are-limited - to summarize if you have types that can convert to any type and types that convert from any other type; all types would be convertible to each other. But I'm not sure this combination has practical value).

If we had neither rule, the compiler would need to look for intermediate types. Say we have an A and want to call a function accepting a D. Do we have to check for a conversion from A -> B -> C ? How is the compiler doing this check? One might imagine it could end up being "guess and check". I.e. "We have a conversion from A to B - suppose we use that. Can we then convert from B to C?". However I'm not convinced it has to be implemented that way.

I'm not even sure if the "don't permit multi-hop coercions" rule would apply to the design in #16729. If we have proc R.canImplicitlyConvertTo(type t) param, then the author of this function decides whether or not to handle nested conversions. Let's take the SumExprType -> bigint -> bigrational example from above. What would somebody write in proc R.canImplicitlyConvertTo(type t) param if they wanted to support that?

proc BigintSumExprType.canImplicitlyConvertTo(type t) param {
  if t == bigint {
    return true; // OK, evaluating the expr results in a bigint
  } else if t == bigrational {
    return true; // OK, evaluate to bigint and convert to bigrational
  }
  return false;
}

That's fine, but what if the author of BigintSumExprType wanted to support this pattern but didn't want to name bigrational (maybe it's not developed yet or maybe they don't want it to be a dependency). The might write:

proc BigintSumExprType.canImplicitlyConvertTo(type t) param {
  if t == bigint {
    return true; // OK, evaluating the expr results in a bigint
  } else {
    // Well, we can convert to bigint, so try that
    return canCoerce(bigint, t);
  }
}

This is effectively creating that "guess and check" algorithm I was describing. I think that there is a reasonable concern that this "guess and check" algorithm will not terminate in some cases involving cycles.

Suppose we have these implicit conversions

A -> B
B -> A

and then we want to check if A can implicitly convert to C. With the "guess and check" algorithm, A says it can convert to B, so we consider B. B says it can convert to A, so we consider A. And then it repeats forever.

Of course we could engineer the compiler to avoid this situation (after all, it can compute some sort of transitive closure on a convertibility graph and do so without being tripped up by cycles). However that might lead to other sorts of limitations.

mppf commented 3 years ago

(Separately, I found this discussion of why C++ only allows one user-defined conversion - https://stackoverflow.com/questions/21337198/why-user-defined-conversions-are-limited - to summarize if you have types that can convert to any type and types that convert from any other type; all types would be convertible to each other. But I'm not sure this combination has practical value).

Just to add a bit to this - a generic record wrapping an arbitrary type (like some kind of Box or sync t kind of thing) could run into this. There, you might want to be able to create the wrapper from an arbitrary type. But, I don't see a use case for converting from a (possibly generic) record to an arbitrary other type.

bradcray commented 3 years ago

For example, if I have a SumExprType type representing a lazily evaluated sum of two GMP integers, but GMP integers can implicitly convert into to GMP rational numbers, then I wouldn't be able to pass a SumExprType into a function expecting a GMP rational number (when maybe I would expect that I could).

Couldn't the type author enable this, though, by providing a SumExprType->GMP rational number conversion?

To me, while it seems plausible to come up with cases where multi-hope conversions might be attractive, in the general case, it seems to dangerous to me, and like a place where casts at the callsite or type-provided short-circuiting conversions (as proposed in the previous paragraph for that case) should be provided. Early in Chapel's development, I recall we had something similar to multi-hop conversions (though I don't think it was exactly that... will have to think what it was), and I remember getting bitten by it a lot before disabling (which I've never regretted).

mppf commented 3 years ago

Couldn't the type author enable this, though, by providing a SumExprType->GMP rational number conversion?

Not if the SumExprType author is not aware of the GMP rational number.

That's what I meant by

That's fine, but what if the author of BigintSumExprType wanted to support this pattern but didn't want to name bigrational (maybe it's not developed yet or maybe they don't want it to be a dependency). The might write:

To me, while it seems plausible to come up with cases where multi-hope conversions might be attractive, in the general case, it seems to dangerous to me

Yeah, I'm not totally convinced we need them either - but "no cycles" still seems like a more appealing restriction to me. That said I could get behind having both restrictions.

bradcray commented 3 years ago

Not if the SumExprType author is not aware of the GMP rational number.

It seems to me that it'd be reasonable to say either (a) the type author should be involved in defining coercions and that casts have to be used otherwise or (b) the GMP rational number author (or a third party) can add a tertiary coercion from SumExprType.

Yeah, I'm not totally convinced we need them either - but "no cycles" still seems like a more appealing restriction to me.

Is there some escape clause that would permit bool(x) <-> bool(y) coercions to continue be supported for x != y? (other than "it's a built-in type"). That's a case that makes cycles seem useful if they're not inherently problematic to me (where it seems as though they haven't been for bools). It seems plausible that a user may want to create a similar family of types that were lossless in terms of value but distinct for some other reason. (e.g., it's equally valid for my "length in feet" to automatically convert to "length in meters" as it is for your "length in meters" to convert to "length in feet").

I think a good argument for no multi-hop coercions is that since bools coerce to ints and ints to reals, and reals to complexes, it would permit a bool to be passed to a routine expecting a real or complex, which seems like something that shouldn't happen without intentional user involvement to me.

I looked through the project history and reminded myself that the early problem I was thinking of was that we used to support coercions to strings, and this caused lots of surprises when there wasn't a better match for a function. I haven't been able to connect it directly to multi-hop coercions, but it seems thematically similar to me for some reason...

mppf commented 3 years ago

Is there some escape clause that would permit bool(x) <-> bool(y) coercions to continue be supported for x != y? (other than "it's a built-in type"). That's a case that makes cycles seem useful if they're not inherently problematic to me (where it seems as though they haven't been for bools).

Sure, we could say that a generic record is allowed to have any conversions among its instantiations (including circular ones).

I think a good argument for no multi-hop coercions is that since bools coerce to ints and ints to reals, and reals to complexes, it would permit a bool to be passed to a routine expecting a real or complex, which seems like something that shouldn't happen without intentional user involvement to me.

I think I was remembering some piece of compiler code that misled me here. I verified that it works as you say - that we can't pass true to an in arg: complex argument; but we can pass 1 and we can convert true into 1 in other situations. I was thinking that the built-in types already supported multi-hop implicit conversions but that does not seem to be the case. I am more inclined to make user-defined conversions also 1-hop as a result.

I looked through the project history and reminded myself that the early problem I was thinking of was that we used to support coercions to strings, and this caused lots of surprises when there wasn't a better match for a function. I haven't been able to connect it directly to multi-hop coercions, but it seems thematically similar to me for some reason...

I'd put this in the "implicit conversions can be surprising" category rather than connecting it to 1-hop.

bradcray commented 3 years ago

Sure, we could say that a generic record is allowed to have any conversions among its instantiations (including circular ones).

That would preclude me from defining different-width bools as distinct types (bool8 or bool16) or to be able to convert both ways between a type added later (e.g., I add a bool1 and want it to inter-convert with the built-in bool(); or want to set up inter-conversions between your generic "length in feet/meters" type and a "length in miles" type that I introduce later as a distinct type).

I continue to prefer permitting circular conversions between arbitrary types until/unless we come up with a compelling reason not to.

I'd put this in the "implicit conversions can be surprising" category rather than connecting it to 1-hop.

That may be right, but I feel like there is still some other factor that I'm not remembering that made it particularly confusing, like an interplay with promoted function calls / operators. I'm pretty sure it's not related to multi-hop conversions (because I'm increasingly confident we've outlawed them from the start), but it still has a similar flavor in my mind for some reason. Anyway I mentioned them in my last response less because I think it's deeply important, more to close out the previous mention I'd made when I was still trying to remember the change.