References

Developers
1

So I want to explain why references are no good. Correct any mistakes please!
The problem, in summary, is that Chapel lies to the user and uses tricks to maintain the lies which cannot be sustained in the presence of parametric polymorphism.
Consider

   var x : int = 1;
   ref r : int = x;

If I understand correctly, x refers to an object with address I will write &x, with an int stored in the object. We say x has type int. On the other hand, r is also a variable, with address &r, but it actually contains a pointer to an int, a type I will write int*. I will write *p to refer to the value stored at address p. Now lets examine 4 scenarios.

R-context:

  1. An int value is expected, and x is written. Chapel copies x.
  2. An int pointer is expected and x is written. Chapel copies &x.
  3. A int value is expected and r is written. Chapel copies *r.
  4. An int pointer is expected, and r is written. Chapel copies r.

There are two more cases, when instead of x, an expression of type int is used. This may or may not require a temporary if an int is expected, but if an int pointer is expected, if that can happen then store has to be allocated somehow and its address copied. For example

ref rtemp : int = 1 + 2;

if allowed would require that. Before proceeding, there is a related issue: overloading. For some set of functions, with a parameter type int and one of the intents in out inout I assume this means, copy value in the first case and copy pointer in the other two. The problem is, before we can say Chapel is expecting some type, we have to resolve overloads. But I'm going to skip considering that for the moment.

Now there is another scenario where a pointer is always required, and that is assignment. On the LHS of an assignment, a pointer is required.

L-context
5. So if x is written, the pointer is &x
6. but if r is used, the pointer is just r

So we now have six cases where the compiler has to cheat to maintain the lie it made to the user. I want to spell out the fiction:

the user expects x and r to have identical behaviour,

except that the underlying store of a variable declared as a reference may be shared with another variable or reference. The cheats 1 thru 6 maintain that requirement.

parametric polymorphism
Can we sustain this fiction, if instead of int we have some unknown type T? The answer is yes, provided T is restricted to be non-pointer value type. We need to consider classes. A value of class type is actually a pointer. So if c0 is of class type C, then there are two possible semantics (I don't know which Chapel implements):

semantic 1

var c1 = c0; // copies pointer
ref c2 = c0; // copies pointer
ref c3  = c1; // copies pointer
ref c4 = c2; // copies pointer

So now our rules 1-4 above are broken by classes. As assignment to c1 will not change the object c2, c3 and c4 refer to.

We can sustain the rules however. For example

semantic 2

var c1 = c0; // copies pointer
ref c2 = c0; // sets c2 to &c1, double indirection now

so now c2 is a pointer to a pointer underneath, and if we assign a new value to c1, the object referred to by c2 will also change. Since semantic #1 breaks the usual rules, with parametric polymorphism we have to add another caveat: T cannot be a class type either. Semantic #2 is already covered by the first caveat, provided we allow that a class type is a non-pointer type.

The reason for the exclusion is that it is not possible to maintain the cheats unless we can distinguish pointer to T from T. In other words the compiler still has to know a reference variable is a pointer to T, whilst a variable is an actual T. It cannot do this if T = pointer to U for some type U. If semantic #1 is used, then there are two cases for T: either it is a non-class non-pointer or a class type, and we have to know which because the semantics are different.

further problems

So it may seem, we can retain references by the rules above together with constraints on type variables that would hide something the compiler needs to know to maintain the lie. Unfortunately, there are more problems. The key one here is that functions can only have one argument. Multiple arguments are total nonsense. The type of a function is given by D->C, where D is the domain and C is the codomain. If you want multiple arguments there are two ways to get them: pass a tuple typed argument, and, pattern match it inside the function to extract the individual components. The other method is to use higher order functions, which is what users of Haskell and Ocaml often do.

Why can't a function have multiple arguments? Because it is impossible to do even basic algebra. For example, the rule for composition of the functions

f: A -> B
g: C -> D

is that the composite g . f requires B = C, and, the composite then exists and is given by

(g . f) (x:A):D { return g(f(x)); }

if a function has two arguments, composition is impossible. If you want to combine functions you now need a complex set of rules indexed by the numbers of arguments, instead of one single simple rule. In C++, heavy duty template meta-programming is required to obtain some generality (and this wasn't possible until recently).

So you basically have to go with passing a tuple as an argument. But now, tuples are first class types themselves and you can have a variable of tuple type:

var x : int * string = (42, "hello");
... f(42,"hello"); 
... f(x) ...

note I use the correct notation for tuple types. Both the calls to f will work. It's no longer possible to have in out and inout parameters (because, trivially, there is only really one parameter!).

All the components of a tuple value will be non-references or classes, because only a variable can be a reference. If you want the inout and out semantics, it's easy to get by explicitly using read-write and write-only pointers .. but you cannot do this if you only have references. the problem, essentially, is you now have TWO stages of binding: first, constructing the tuple, and then, passing it to the function. So the magic rules that maintain the fiction fall apart because they're only one step rules.

All these complications and issues just evaporate if you put pointer types into the language. It is best not to lie to the user, but you simply cannot lie to the compiler. The point is you already have pointer types in the type system. References can be maintained ONLY by syntactic sugar, since in that case, they might confuse the user .. but never the compiler.

2

So far I have not been able to understand the problem. I understand that references add some complexity to the language and in some ways things would be simpler / more consistent if we have only pointers.

Would it be possible to show a specific example of a Chapel program that doesn't behave as one would expect today in order to discuss this issue in more detail? Or, if that is not possible, and it would require the interface declarations, could you show an example of a Chapel program that uses interfaces that has the problem?

3

No, I expect it all works just fine today, because you don't have polymorphism. The problem only comes when you do have parametric polymorphism. I can't show you interface examples, because i have no idea how they work. The problem interfaces are required to solve are to allow more convenient polymorphism than you get with basic parametric polymorphism. Until Chapel can type check EVERY definition before ANY definitions are used, it hasn't even got to first base. Heck, even ISO C can do that. And then you have to add parametric polymorphism and check all the definitions before instantiation. ONLY THEN is it sane to even talk about type classes/interfaces/concepts.

4

We seem to be having some problems with terminology. According to the description in Parametric polymorphism - Wikipedia (and I tend to view Wikipedia as an acceptable reference for "what do people mean by term XYZ") we would have parametric polymorphism in the form of generic functions. C++ is listed there as supporting parametric polymorphism (presumably with template functions) and Chapel generic functions have a similar level of capability.

So I don't think it's true that Chapel doesn't have parametric polymorphism.

We are looking at adding interfaces in order to have bounded parametric polymorphism (according to the terminology in that Wikipedia page). I suspect that it's your view that the only useful / reasonable parametric polymorphism is bounded parametric polymorphism.

Myself, I would prefer to discuss in terms of example programs, rather than programming languages theory jargon.

I can't show you interface examples, because i have no idea how they work.

You can learn about them in https://github.com/chapel-lang/chapel/blob/main/doc/rst/developer/chips/2.rst and in the section of https://chapel-lang.org/releaseNotes/1.25/01-language.pdf starting on slide 32.

But independent of that - responding to your original post - I still don't see an issue. Here I will go in to slightly more detail on why.

In terms of the potential problem you noted above with classes, what we have is semantic 2, if I understand your example correctly.

Semantic #2 is already covered by the first caveat, provided we allow that a class type is a non-pointer type.

What is the first caveat? Given that the language design is closer to semantic 2, what exactly is the problem with references and classes?

The key one here is that functions can only have one argument. Multiple arguments are total nonsense. ... Why can't a function have multiple arguments? Because it is impossible to do even basic algebra. ... the composite g . f ...

I don't think the Chapel language will ever support g . f like you can have in functional programming languages. Instead, you can create a function that applies a combination of functions using a lambda / first class function (although our first-class function language design needs some work) or just make a regular function declaration to do it. In particular, I wouldn't view giving up on inout / out etc intents as a worthwhile trade to gain support for g . f.

5

Neither C++ nor Chapel has parametric polymorphism because irrespective of the populist crud in Wikipedia, the requirement is that polymorphic function definitions be statically type checked such that, for any call which matches the function interface, the instantiation of the body is guaranteed to be correct and does not require type checking to be assured of correctness. In addition, the semantics of a polymorphic function must be independent of the types it is called with.

Neither C++ nor Chapel is capable of type checking polymorphic functions. Therefore neither has parametric polymorphism.

In addition, to support parametric polymorphism, it is a requirement that the type constructors of the type system themselves be parametric. This means, for any type T, C(T) exists and is a distinct type. You can understand in a populist way as a requirement the constructors be orthogonal. So, the usual function type constructor -> is an example, A -> B takes two arguments of any type and gives a new type. In C, for any data type T, T* is pointer to T. Pointer formation is parametric (but only for data types, and C arrays don't count either). So actually the array case is an example of non-parametricity and you can see this in the language .. when you pass an array you just get a pointer to the first element. Array constructors are not parametric.

In C++, references do not have this property. T& is the same type as T&&. For pointers though T** is not the same as T*. So C++ cannot have parametric polymorphism. The type system is broken.

In the case of C++, I was actually a NB rep on the committee for 10 years and strenuously argued template should disallow instantiation of a type variable with anything other than a value type, that is, int is allowed but const int and int& are not. In C++98, this is the case for type variables deduced for function calls, so such uses of function templates could be parametric if dependent name lookup is disallowed as well. But the committee didn't consist of people that actually understood type systems and bad instantiations are allowed for classes and functions if given explicitly, and of course, C++ also has dependent name lookup, So C++ definitely does not have parametric polymorphism and never will. It will never be possible to type check C++ templates. They are in fact just jumped up macros. Syntax macros, yes, but macros all the same.

Crud like C++ generics are equivalent (one level up) to K&R C or Fortran I, where a function taking a float could be called with an int. It wouldn't work, but that was the programmers fault: the type system had no function prototypes so there was no way the type checker (or what it had that passed as a type checker) could tell.

6

Let me show you the difference between parametric polymorphism and generics. Here is a Felix program:

fun generic(x) => x + x;
println$ generic(1);

//fun polymorphic[T] (x:T) => x + x;

The output is:

~/felix>flx f
2

Now I uncomment the last line of the program:

Flx_lookup:inner_bind_expression: Client Error binding expression (+ (x, x))
Error at:
/Users/skaller/felix/f.flx: line 4, cols 29 to 34
3:
4: fun polymorphic[T] (x:T) => x + x;
                               ******
5:

[Flx_lookup.bind_expression] Inner bind expression failed binding (+ (x, x))
CLIENT ERROR
[flx_bind/flx_lookup.ml:2973: E149] [lookup_name_with_sig] Can't find +[] of BTYP_array(BTYP_type_var(60493:TYPE),2)=
+[] of <T60493>^2
In /Users/skaller/felix/f.flx: line 4, cols 29 to 34
3:
4: fun polymorphic[T] (x:T) => x + x;
                               ******
5:

You see? Notice I didn't even call the function f. You simply cannot add any arbitrary type to itself.

7

BTW I think you can already do, or almost do, higher order functions. You use a Chapel class, with an apply() method an instance is a function closure. The constructor (init method?) accepts a pointer to the context as described below.

The rules are like this:

  1. You cannot store a function closure in a data structure on the heap, this would lead to unresolvable circular references

  2. A function can return a nested function. in particular a curried form of function defined like this:

proc (...) (...)

with two "arguments" is actually a single function with the first parameter, returning a function that accepts the second parameter. The first function class must be stored in the second with owned attribute. When the second function is destroyed the first one will be deleted. This is safe because functional abstraction ensures that the second function is the only one that can see the local variables of the first one (including its parameter).

3, A function can pass a nested function to another function. The class has owned attribute in the calling function but is passed to function with borrowed attribute. This is safe because the borrowed attribute requires the called function to forget the function by the time it returns, so it will remain owned by the function which contains it.

  1. By using shared, rule 1 can be relaxed. In fact reference counted functions will work just fine, even on the heap, provided of course you don't create a cycle. I do not know how to statically ensure this doesn't happen.

In Objective C, originally it has manual reference counting, and Apple tried to fix this with a GC, then gave up, and made LLVM do the reference counting automatically. I think it is still possible in Obj C to make cycle. In Swift, it is more constrained.

However, allowing this can be deferred to when proper machinery is known. The first two cases .. returning a function and passing one to another function .. are the two most common cases and are both easily managed if you have the equivalent of C++ uniq_ptr for the first case (owned) of just use a plain pointer (borrowed) for the second. Note that a borrowed pointer cannot be returned .. it must be forgotten. In Chapel, replace "pointer" with "reference to class".