Index: doc/proposals/NOTE.txt =================================================================== --- doc/proposals/NOTE.txt (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) +++ doc/proposals/NOTE.txt (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) @@ -0,0 +1,1 @@ +PDFs created using www.markdowntopdf.com Index: doc/proposals/references.md =================================================================== --- doc/proposals/references.md (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) +++ doc/proposals/references.md (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) @@ -0,0 +1,208 @@ +## Lvalues and References ## +C defines the notion of a _lvalue_, essentially an addressable object, as well +as a number of type _qualifiers_, `const`, `volatile`, and `restrict`. +As these type qualifiers are generally only meaningful to the type system as +applied to lvalues, the two concepts are closely related. +A const lvalue cannot be modified, the compiler cannot assume that a volatile +lvalue will not be concurrently modified by some other part of the system, and +a restrict lvalue must have pointer type, and the compiler may assume that no +other pointer in scope aliases that pointer (this is solely a performance +optimization, and may be ignored by implementers). +_Lvalue-to-rvalue conversion_, which takes an lvalue of type `T` and converts +it to an expression result of type `T` (commonly called an _rvalue_ of type +`T`) also strips all the qualifiers from the lvalue, as an expression result +is a value, not an addressable object that can have properties like +immutability. +Though lvalue-to-rvalue conversion strips the qualifiers from lvalues, +derived rvalue types such as pointer types may include qualifiers; +`const int *` is a distinct type from `int *`, though the latter is safely +convertable to the former. +In general, any number of qualifiers can be safely added to the +pointed-to-type of a pointer type, e.g. `int *` converts safely to +`const int *` and `volatile int *`, both of which convert safely to +`const volatile int *`. + +Since lvalues are precicely "addressable objects", in C, only lvalues can be +used as the operand of the `&` address-of operator. +Similarly, only modifiable lvalues may be used as the assigned-to +operand of the mutating operators: assignment, compound assignment +(e.g. `+=`), and increment and decrement; roughly speaking, lvalues without +the `const` qualifier are modifiable, but lvalues of incomplete types, array +types, and struct or union types with const members are also not modifiable. +Lvalues are produced by the following expressions: object identifiers +(function identifiers are not considered to be lvalues), the result of the `*` +dereference operator applied to an object pointer, the result of a member +expression `s.f` if the left argument `s` is an lvalue (note that the +preceding two rules imply that the result of indirect member expressions +`s->f` are always lvalues, by desugaring to `(*s).f`), and the result of the +indexing operator `a[i]` (similarly by its desugaring to `*((a)+(i))`). +Somewhat less obviously, parenthesized lvalue expressions, string literals, +and compound literals (e.g. `(struct foo){ 'x', 3.14, 42 }`) are also lvalues. + +All of the conversions described above are defined in standard C, but Cforall +requires further features from its type system. +In particular, to allow overloading of the `*?` and `?[?]` dereferencing and +indexing operators, Cforall requires a way to declare that the functions +defining these operators return lvalues, and since C functions never return +lvalues and for syntactic reasons we wish to distinguish functions which +return lvalues from functions which return pointers, this is of necessity an +extension to standard C. +In the current design, an `lvalue` qualifier can be added to function return +types (and only to function return types), the effect of which is to return a +pointer which is implicitly dereferenced by the caller. +C++ includes the more general concept of _references_, which are typically +implemented as implicitly dereferenced pointers as well. +Another use case which C++ references support is providing a way to pass +function parameters by reference (rather than by value) with a natural +syntax; Cforall in its current state has no such mechanism. +As an example, consider the following (currently typical) copy-constructor +signature and call: + + void ?{}(T *lhs, T rhs); + + T x; + T y = { x }; + +Note that the right-hand argument is passed by value, and would in fact be +copied twice in the course of the constructor call `T y = { x };` (once into +the parameter by C's standard `memcpy` semantics, once again in the body of +the copy constructor, though it is possible that return value optimization +will elide the `memcpy`-style copy). +However, to pass by reference using the existing pointer syntax, the example +above would look like this: + + void ?{}(T *lhs, const T *rhs); + + T x; + T y = { &x }; + +This example is not even as bad as it could be; assuming pass-by-reference is +the desired semantics for the `?+?` operator, that implies the following +design today: + + T ?+?(const T *lhs, const T *rhs); + + T a, b; + T c = &a + &b, + +In addition to `&a + &b` being unsightly and confusing syntax to add `a` and +`b`, it also introduces a possible ambiguity with pointer arithmetic on `T*` +which can only be resolved by return-type inference. + +Pass-by-reference and marking functions as returning lvalues instead of the +usual rvalues are actually closely related concepts, as obtaining a reference +to pass depends on the referenced object being addressable, i.e. an lvalue, +and lvalue return types are effectively return-by-reference. +Cforall should also unify the concepts, with a parameterized type for +"reference to `T`", which I will write `T&`. + +Firstly, assignment to a function parameter as part of a function call and +local variable initialization have almost identical semantics, so should be +treated similarly for the reference type too; this implies we should be able +to declare local variables of reference type, as in the following: + + int x = 42; + int& r = x; // r is now an alias for x + +Unlike in C++, we would like to have the capability to re-bind references +after initialization, as this allows the attractive syntax of references to +support some further useful code patterns, such as first initializing a +reference after its declaration. +Constant references to `T` (`T& const`) should not be re-bindable. + +One option for re-binding references is to use a dedicated operator, as in the +code example below: + + int i = 42, j = 7; + int& r = i; // bind r to i + r = j; // set i (== r) to 7 + r := j; // rebind r to j using the new := rebind operator + i = 42; // reset i (!= r) to 42 + assert( r == 7 ); + +Another option for reference rebind is to modify the semantics of the `&` +address-of operator. +In standard C, the address-of operator never returns an lvalue, but for an +object of type `T`, returns a `T*`. +If the address-of operator returned an lvalue for references, this would +allow reference rebinding using the usual pointer assignment syntax; +that is, if address-of a `T&` returned a `T*&` then the following works: + + int i = 42; j = 7; + int& r = i; // bind r to i + r = j; // set i (== r) to 7 + &r = &j; // rebind r to j using the newly mutable "address-of reference" + i = 42; // reset i (!= r) to 42 + assert( r == 7 ); + +This change (making addresses of references mutable) allows use of existing +operators defined over pointers, as well as elegant handling of nested +references-to-references. + +The semantics and restrictions of `T&` are effectively the semantics of an +lvalue of type `T`, and by this analogy there should be a safe, qualifier +dropping conversion from `const volatile restrict T&` (and every other +qualifier combination on the `T` in `T&`) to `T`. +With this conversion, the resolver may type most expressions that C would +call "lvalue of type `T`" as `T&`. +There's also an obvious argument that lvalues of a (possibly-qualified) type +`T` should be convertable to references of type `T`, where `T` is also +so-qualified (e.g. lvalue `int` to `int&`, lvalue `const char` to +`const char&`). +By similar arguments to pointer types, qualifiers should be addable to the +referred-to type of a reference (e.g. `int&` to `const int&`). +As a note, since pointer arithmetic is explictly not defined on `T&`, +`restrict T&` should be allowable and would have alias-analysis rules that +are actually comprehensible to mere mortals. + +Using pass-by-reference semantics for function calls should not put syntactic +constraints on how the function is called; particularly, temporary values +should be able to be passed by reference. +The mechanism for this pass-by-reference would be to store the value of the +temporary expression into a new unnamed temporary, and pass the reference of +that temporary to the function. +As an example, the following code should all compile and run: + + void f(int& x) { printf("%d\n", x++); } + + int i = 7, j = 11; + const int answer = 42; + + f(i); // (1) + f(42); // (2) + f(i + j); // (3) + f(answer); // (4) + +The semantics of (1) are just like C++'s, "7" is printed, and `i` has the +value 8 afterward. +For (2), "42" is printed, and the increment of the unnamed temporary to 43 is +not visible to the caller; (3) behaves similarly, printing "19", but not +changing `i` or `j`. +(4) is a bit of an interesting case; we want to be able to support named +constants like `answer` that can be used anywhere the constant expression +they're replacing (like `42`) could go; in this sense, (4) and (2) should have +the same semantics. +However, we don't want the mutation to the `x` parameter to be visible in +`answer` afterward, because `answer` is a constant, and thus shouldn't change. +The solution to this is to allow chaining of the two lvalue conversions; +`answer` has the type `const int&`, which can be converted to `int` by the +lvalue-to-rvalue conversion (which drops the qualifiers), then up to `int&` +by the temporary-producing rvalue-to-lvalue conversion. +Thus, an unnamed temporary is inserted, initialized to `answer` (i.e. 42), +mutated by `f`, then discarded; "42" is printed, just as in case (2), and +`answer` still equals 42 after the call, because it was the temporary that was +mutated, not `answer`. +It may be somewhat surprising to C++ programmers that `f(i)` mutates `i` while +`f(answer)` does not mutate `answer` (though `f(answer)` would be illegal in +C++, leading to the dreaded "const hell"), but the behaviour of this rule can +be determined by examining local scope with the simple rule "non-`const` +references to `const` variables produce temporaries", which aligns with +programmer intuition that `const` variables cannot be mutated. + +To bikeshed syntax for `T&`, there are three basic options: language +keywords (`lvalue T` is already in Cforall), compiler-supported "special" +generic types (e.g. `ref(T)`), or sigils (`T&` is familiar to C++ +programmers). +Keyword or generic based approaches run the risk of name conflicts with +existing code, while any sigil used would have to be carefully chosen to not +create parsing conflicts. Index: doc/proposals/void_ptr.md =================================================================== --- doc/proposals/void_ptr.md (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) +++ doc/proposals/void_ptr.md (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) @@ -0,0 +1,44 @@ +## Options for safer void* handling # +C allows implicit conversions between `void*` and other pointer types, as per +section 6.3.2.3.1 of the standard. +Making these implicit conversions explicit in Cforall would provide +significant type-safety benefits, and is precedented in C++. +A weaker version of this proposal would be to allow implicit conversions to +`void*` (as a sort of "top type" for all pointer types), but to make the +unsafe conversion from `void*` back to a concrete pointer type an explicit +conversion. +However, `int *p = malloc( sizeof(int) );` and friends are hugely common +in C code, and rely on the unsafe implicit conversion from the `void*` return +type of `malloc` to the `int*` type of the variable - obviously it would be +too much of a source-compatibility break to disallow this for C code. +We do already need to wrap C code in an `extern "C"` block, though, so it is +technically feasible to make the `void*` conversions implicit in C but +explicit in Cforall. + +As a possible mitigation for calling C code with `void*`-based APIs, pointers-to-dtype are +calling-convention compatible with `void*`; we could read `void*` in function +signatures as essentially a fresh dtype type variable, e.g: + + void* malloc( size_t ) + => forall(dtype T0) T0* malloc( size_t ) + void qsort( void*, size_t, size_t, int (*)( const void*, const void* ) ) + => forall(dtype T0, dtype T1, dtype T2) + void qsort( T0*, size_t, size_t, int (*)( const T1*, const T2* ) ) + +In this case, there would be no conversion needed to call `malloc`, just the +polymorphic type binding. +This should handle many of the uses of `void*` in C. + +This feature would even allow us to leverage some of Cforall's type safety to write +better declarations for legacy C API functions, like the following wrapper for +`qsort`: + + extern "C" { // turns off name-mangling so that this calls the C library + // call-compatible type-safe qsort signature + forall(dtype T) + void qsort( T*, size_t, size_t, int (*)( const T*, const T* ) ); + + // forbid type-unsafe C signature from resolving + void qsort( void*, size_t, size_t, int (*)( const void*, const void* ) ) + = delete; + } Index: doc/proposals/zero_one.md =================================================================== --- doc/proposals/zero_one.md (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) +++ doc/proposals/zero_one.md (revision bd669678a7e0e870823d1c2922b0a424622e5cf3) @@ -0,0 +1,182 @@ +## Types for 0 and 1 literals ## +The literals `0` and `1` are treated specially by Cforall, due to their +potential uses in operator overloading. +Earlier versions of Cforall allowed `0` and `1` to be variable names, allowing +multiple interpretations of them according to the existing variable +overloading rules, with the following declarations in the prelude: + + const int 0, 1; + forall ( dtype DT ) const DT * const 0; + forall ( ftype FT ) FT * const 0; + +This did, however, create some backward-compatibility problems and potential +performance issues, and works poorly for generic types. To start with, this +(entirely legal C) code snippet doesn't compile in Cforall: + + if ( 0 ) {} + +It desugars to `if ( (int)(0 != 0) ) {}`, and since both `int` and +`forall(dtype DT) DT*` have a != operator which returns `int` the resolver can +not choose which `0` variable to take, because they're both exact matches. + +The general `!=` computation may also be less efficient than a check for a zero +value; take the following example of a rational type: + + struct rational { int32_t num, int32_t den }; + rational 0 = { 0, 1 }; + + int ?!=? (rational a, rational b) { + return ((int64_t)a.num)*b.den != ((int64_t)b.num)*a.den; + } + + int not_zero (rational a) { return a.num != 0; } + +To check if two rationals are equal we need to do a pair of multiplications to +normalize them (the casts in the example are to prevent overflow), but to +check if a rational is non-zero we just need to check its numerator, a more +efficient operation. + +Finally, though polymorphic null-pointer variables can be meaningfully +defined, most other polymorphic variables cannot be, which makes it difficult +to make generic types "truthy" using the existing system: + + forall(otype T) struct pair { T x; T y; }; + forall(otype T | { T 0; }) pair(T) 0 = { 0, 0 }; + +Now, it seems natural enough to want to define the zero for this pair type as +a pair of the zero values of its element type (if they're defined). +The declaration of `pair(T) 0` above is actually illegal though, as there is +no way to represent the zero values of an infinite number of types in the +single memory location available for this polymorphic variable - the +polymorphic null-pointer variables defined in the prelude are legal, but that +is only because all pointers are the same size and the single zero value is a +legal value of all pointer types simultaneously; null pointer is, however, +somewhat unique in this respect. + +The technical explanation for the problems with polymorphic zero is that `0` +is really a rvalue, not a lvalue - an expression, not an object. +Drawing from this, the solution we propose is to give `0` a new built-in type, +`zero_t`, and similarly give `1` the new built-in type `one_t`. +If the prelude defines `!=` over `zero_t` this solves the `if ( 0 )` problem, +because now the unambiguous best interpretation of `0 != 0` is to read them +both as `zero_t` (and say that this expression is false). +Backwards compatibility with C can be served by defining conversions in the +prelude from `zero_t` and `one_t` to `int` and the appropriate pointer +types, as below: + + // int 0; + forall(otype T | { void ?{safe}(T*, int); }) void ?{safe} (T*, zero_t); + forall(otype T | { void ?{unsafe}(T*, int); }) void ?{unsafe} (T*, zero_t); + + // int 1; + forall(otype T | { void ?{safe}(T*, int); }) void ?{safe} (T*, one_t); + forall(otype T | { void ?{unsafe}(T*, int); }) void ?{unsafe} (T*, one_t); + + // forall(dtype DT) const DT* 0; + forall(dtype DT) void ?{safe}(const DT**, zero_t); + // forall(ftype FT) FT* 0; + forall(ftype FT) void ?{safe}(FT**, zero_t); + +Further, with this change, instead of making `0` and `1` overloadable +variables, we can instead allow user-defined constructors (or, more flexibly, +safe conversions) from `zero_t`, as below: + + // rational 0 = { 0, 1 }; + void ?{safe} (rational *this, zero_t) { this->num = 0; this->den = 1; } + +Note that we don't need to name the `zero_t` parameter to this constructor, +because its only possible value is a literal zero. +This one line allows `0` to be used anywhere a `rational` is required, as well +as enabling the same use of rationals in boolean contexts as above (by +interpreting the `0` in the desguraring to be a rational by this conversion). +Furthermore, while defining a conversion function from literal zero to +`rational` makes rational a "truthy" type able to be used in a boolean +context, we can optionally further optimize the truth decision on rationals as +follows: + + int ?!=? (rational a, zero_t) { return a.num != 0; } + +This comparison function will be chosen in preference to the more general +rational comparison function for comparisons against literal zero (like in +boolean contexts) because it doesn't require a conversion on the `0` argument. +Functions of the form `int ?!=? (T, zero_t)` can acutally be used in general +to make a type `T` truthy without making `0` a value which can convert to that +type, a capability not available in the current design. + +This design also solves the problem of polymorphic zero for generic types, as +in the following example: + + // ERROR: forall(otype T | { T 0; }) pair(T) 0 = { 0, 0 }; + forall(otype T | { T 0; }) void ?{safe} (pair(T) *this, zero_t) { + this->x = 0; this->y = 0; + } + +The polymorphic variable declaration didn't work, but this constructor is +perfectly legal and has the desired semantics. + +We can assert that `T` can be used in a boolean context as follows: + + `forall(otype T | { int ?!=?(T, zero_t); })` + +Since the C standard (6.5.16.1.1) specifically states that pointers can be +assigned into `_Bool` variables (and implies that other artithmetic types can +be assigned into `_Bool` variables), it seems natural to say that assignment +into a `_Bool` variable effectively constitutes a boolean context. +To allow this interpretation, I propose including the following function (or +its effective equivalent) in the prelude: + + forall(otype T | { int ?!=?(T, zero_t); }) + void ?{safe}( _Bool *this, T that ) { *this = that != 0; } + +Note that this conversion is not transitive; that is, for `t` a variable of +some "truthy" type `T`, `(_Bool)t;` would use this conversion (in the absence +of a lower-cost one), `(int)t;` would not use this conversion (and in fact +would not be legal in the absence of another valid way to convert a `T` to an +`int`), but `(int)(_Bool)t;` could legally use this conversion. + +Similarly giving literal `1` the special type `one_t` allows for more +concise and consistent specification of the increment and decrement operators, +using the following de-sugaring: + + ++i => i += 1 + i++ => (tmp = i, i += 1, tmp) + --i => i -= 1 + i-- => (tmp = i, i -= 1, tmp) + +In the examples above, `tmp` is a fresh temporary with its type inferred from +the return type of `i += 1`. +Under this proposal, defining a conversion from `one_t` to `T` and a +`lvalue T ?+=? (T*, T)` provides both the pre- and post-increment operators +for free in a consistent fashion (similarly for -= and the decrement +operators). +If a meaningful `1` cannot be defined for a type, both increment operators can +still be defined with the signature `lvalue T ?+=? (T*, one_t)`. +Similarly, if scalar addition can be performed on a type more efficiently than +by repeated increment, `lvalue T ?+=? (T*, int)` will not only define the +addition operator, it will simultaneously define consistent implementations of +both increment operators (this can also be accomplished by defining a +conversion from `int` to `T` and an addition operator `lvalue T ?+=?(T*, T)`). + +To allow functions of the form `lvalue T ?+=? (T*, int)` to satisfy "has an +increment operator" assertions of the form `lvalue T ?+=? (T*, one_t)`, +we also define a non-transitive unsafe conversion from `_Bool` (allowable +values `0` and `1`) to `one_t` (and `zero_t`) as follows: + + void ?{unsafe} (one_t*, _Bool) {} + +As a note, the desugaring of post-increment above is possibly even more +efficient than that of C++ - in C++, the copy to the temporary may be hidden +in a separately-compiled module where it can't be elided in cases where it is +not used, whereas this approach for Cforall always gives the compiler the +opportunity to optimize out the temporary when it is not needed. +Furthermore, one could imagine a post-increment operator that returned some +type `T2` that was implicitly convertable to `T` but less work than a full +copy of `T` to create (this seems like an absurdly niche case) - since the +type of `tmp` is inferred from the return type of `i += 1`, you could set up +functions with the following signatures to enable an equivalent pattern in +Cforall: + + lvalue T2 ?+=? (T*, one_t); // increment operator returns T2 + void ?{} (T2*, T); // initialize T2 from T for use in `tmp = i` + void ?{safe} (T*, T2); // allow T2 to be used as a T when needed to + // preserve expected semantics of T x = y++;