Index: doc/working/resolver_design.md =================================================================== --- doc/working/resolver_design.md (revision e229c2272ab72542375efbd4ac6ca3037f4360ce) +++ doc/working/resolver_design.md (revision dd5190664a69fab66e1b83a45dbd80f155c0ce79) @@ -87,34 +87,241 @@ element-wise; summation starts at `(0, 0, 0, 0)`. -**TODO** Costs of T, T*, lvalue T, rvalue T conversions (if applicable) - -### Lvalue Conversions ### -**TODO** Finish me - -#### NOTES -* C standard 6.3.2.1 -* pointer_like_generators.md - -### Qualifier Conversions ### -**TODO** Finish me - -#### NOTES -C standard 6.3.2.3.2: We can add any qualifier to the pointed-to-type of a -pointer. -* Glen thinks this means that we should make the default assignment operator - `?=?(T volatile restrict *this, T that)`, but I'm not sure I like the - implications for the actual implementation of forcing `this` to be - volatile -* I want to consider whether this property should generalize to other - parameterized types (e.g. `lvalue T`, `box(T)`) - -C standard 6.3.2.1.1: "modifiable lvalues" recursively exclude structs with -const-qualified fields - -C standard 6.3.2.1.2: Using lvalues as rvalues implicitly strips qualifiers - -C standard 6.2.4.26: - -C standard 6.7.3: **TODO** +### Lvalue and Qualifier Conversions ### +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 `ref T`. +Syntax bikeshedding can be done later (there are some examples at the bottom +of this section), but `ref T` is sufficiently distinct from both the existing +`lvalue T` (which it subsumes) and the closely related C++ `T&` to allow +independent discussion of its semantics. + +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; + ref 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` (`const ref T`) 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; + ref 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 ); + +The other syntactic option for reference re-bind would be to overload +assignment and use type inference on the left and right-hand sides to +determine whether the referred-to variable on the left should be reassigned to +the value on the right, or if the reference on the left should be aliased to +the reference on the right. +This could be disambiguated with casts, as in the following code example: + + int i + int j; + ref int r = i; // (0a) + ref int s = i; // (0b) + + i = j; // (1) + i = (int)s; // (2) + i = s; // (3) + // --------------------- + r = s; // (4) + r = (ref int)j; // (5) + // --------------------- + r = j; // (6) + r = (int)s; // (7) + +By the expected aliasing syntax, (0a) and (0b) are initializing `r` and `s` as +aliases for `i`. +For C compatibility, (1) has to be assignment; in general, any assignment to a +non-reference type should be assignment, so (2) and (3) are as well. +By types, (4) and (5) should have the same semantics, and the semantics of (6) +and (7) should match as well. +This suggests that (4) and (5) are reference re-bind, and (6) and (7) are an +assignment to the referred variable; this makes the syntax to explicitly alias +a local variable rather ugly (and inconsistent with the initialization +syntax), as well as making it rather awkward to copy the value stored in one +reference-type variable into another reference type variable (which is likely +more painful in functions with by-reference parameters than with local +variables of reference type). + +Because of the aforementioned issues with overloading assignment as reference +rebind, in addition to the fact that reference rebind should not be a +user-overloadable operator (unlike assignment), I propose refererence rebind +should have its own dedicated operator. + +The semantics and restrictions of `ref T` are effectively the semantics of an +lvalue of type `T`, and by this analogy there should be a safe, qualifier +dropping conversion from `ref const volatile restrict T` (and every other +qualifier combination on the `T` in `ref T`) to `T`. +With this conversion, the resolver may type most expressions that C would +call "lvalue of type `T`" as `ref 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 `ref int`, lvalue `const char` to +`ref const char`). +By similar arguments to pointer types, qualifiers should be addable to the +referred-to type of a reference (e.g. `ref int` to `ref const int`). +As a note, since pointer arithmetic is explictly not defined on `ref T`, +`restrict ref 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(ref 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 `ref` conversions; +`answer` has the type `ref const int`, which can be converted to `int` by the +lvalue-to-rvalue conversion (which drops the qualifiers), then up to `ref 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 `ref 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. + +**TODO** Consider arguments for move semantics and see if there is a +compelling case for rvalue references. ### Conversion Operator Costs ### @@ -624,4 +831,24 @@ 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 `_unit_t` allows for more concise and consistent specification of the increment and decrement operators, @@ -714,5 +941,9 @@ then take the non-deleted alternative, and of two equivalent-cost deleted interpretations with the same return type pick one arbitrarily rather than -producing an ambiguous resolution. +producing an ambiguous resolution. This would also be useful for forbidding +pointer-to-floating-point explicit conversions (C11, 6.5.4.4). +**TODO** Cover default parameters, maybe named parameters (see "named +arguments" thread of 11 March 2016) + ### Sizeof, Alignof & Offsetof Expressions ### @@ -732,4 +963,19 @@ for each interpretation `J` of `y` with the same type as `J` costing the sum of the costs of `I` and `J`. + +### Index Expressions ### +**TODO** Consider adding polymorphic function in prelude for this, as per +6.5.2.1.2 in the C standard: + + forall(otype T, otype I, otype R, otype E | { R ?+?(T, I); lvalue E *?(R); }) + lvalue E ?[?](T a, I i) { return *(a + i); } + +I think this isn't actually a good idea, because the cases for it are niche, +mostly odd tricks like `0[p]` as an alternate syntax for dereferencing a +pointer `p`, and adding it to the prelude would slow down resolution of +every index expression just a bit. Our existing prelude includes an indexing +operator `forall(otype T) lvalue T ?[?](ptrdiff_t, T*)`, plus qualified +variants, which should satisfy C source-compatibility without propegating this +silly desugaring further. #### Compatible Functions ####