7 ms·

Interesting points. > Implementing generics in this way breaks parametricity. Simply put, parametricity means being able to reason about functions just from t

by marhee 2y ago

Interesting points. > Implementing generics in this way breaks parametricity. Simply put, parametricity means being able to reason about functions just from their type signature. You can't do this when the function can do arbitrary computation based on the concrete type a generic type is instantiated with. Do you mean reasoning about a function in the sense of just understanding what a functions does (or can do), i.e. in the view of the practical programmer, or reasoning about the function in a typed theoretical system (e.g. typed lambda calculus or maybe even more exotic)? Or maybe a bit of both? There is certainly a concern from the theoretical viewpoint but how important is that for a practical programming language? For example, I believe C++ template programming also breaks "parametricity" by supporting template specialisation. While there are many mundane issues with C++ templates, breaking parametricity is not a very big deal in practice. In contrast, it enables optimisations that are not otherwise possible (for templates). Consider for example std::vector<bool>: implementations can be made that actually store a single bit per vector element (instead of how a bool normally is represented using an int or char). Maybe this is even required by the standard, I don't recall. My point is that in makes sense for C++ to allow this, I think.

SkiFire13 2y ago
> For example, I believe C++ template programming also breaks "parametricity" by supporting template specialisation. C++ breaks parametricity even with normal templates, since you can e.g. call a method that exists/is valid only on some instantiations of the template. The issue is that the compiler can't help you check whether your template type checks or not, you will only figure out when you instantiate it with a concrete type. Things get worse when you call a templated function from within another templated function, since the error can then be arbitrarily levels deep. > My point is that in makes sense for C++ to allow this, I think. Whether it makes sense or not it's a big pain point and some are trying to move away from it (see e.g. Carbon's approach to generics)
- marhee 2y ago
  > C++ breaks parametricity even with normal templates I might be wrong here, but as I understand it "parametricity" means loosely that all instantiations use the same function body. To quote wikipedia: "parametricity is an abstract uniformity property enjoyed by parametrically polymorphic functions, which captures the intuition that all instances of a polymorphic function act the same way" In this view, C++ does not break parametricity with "normal" (i.e. non-specialised) templates. Of course, C++ does not type check a template body against its parameters (unless concepts/trairs are used), leading to the problems you describe, but it's a different thing as far as I understand.
  - jcelerier 2y ago
    Hm, wouldn't any use of if constexpr break that definition? e.g. template<typename T> void f() { if constexpr (is_int<T>) { return 0; } else ...
  - deredede 2y ago
    Parametricity is about behavior, not code. A function parametric in a variable should bevave identically for all values of the variable. If one instance of a C++ template fails to compile and another instance of the same template does compile it is a stretch to say they behave identically, even though they use the same code.
  - lmm 2y ago
    To be parametric it needs to be the same body semantically, not just textually. Particularly in C++ with its heavy operator overloading and limited safety, you can very easily write a template whose body will do the right thing for some types and be undefined behaviour for others (e.g. if your template has comparisons in it and then you instantiate it with a pointer or something).
Quekid5 2y ago
> Consider for example std::vector<bool>: implementations can be made that actually store a single bit per vector element (instead of how a bool normally is represented using an int or char). Your example is considered a misfeature and demonstrates why breaking parametricity is a problem: the specialized vector<bool> is not a standard STL container even though vector<anythingelse> is. That's at best confusing -- and can leads to very confusing problems in generic code. (In this specific case, C++11's "auto" and AAA lessens some of the issues, but even then it can cause hard-to-diagnose performance problems even when the code compiles) See https://stackoverflow.com/a/17797560 https://stackoverflow.com/a/17797560 for more details.
- beached_whale 2y ago
  Vector bool may not have to store a range of space optimized bool values but the interface is still different enough and guarantees different enough that is is largely thought of as a mistake. For one the const reference type is bool and not bool const &. Plus other members like flip… mostly the issue is in generic code expecting a normal vector
- HelloNurse 2y ago
  The C++ vector<bool> specialization is bad because breaking many important implicit contracts about taking the address of vector<> elements makes it practically unusable if a normal vector<> is expected, but it isn't specialized incorrectly in a formally meaningful sense: all errors are outside the class (unsatisfied expectations from client code) and implicit (particularly for C++ as it was at the time).
  - Quekid5 2y ago
    You're not wrong, but is at the very least weird that a specialization doesn't conform to the concept that the general template does. Something which proper parametricity would have avoided -- if it were available. (The Hysterical Raisins are understandable, esp. given that it wasn't even possible to specify Concepts in C++ until 2020...)
    - 2y ago
nialv7 2y ago
one thing you can reason about a function is: does it exist at all? if you don't have parametricity, you can't even be sure about that. in Rust, as long as your type satisfies a generic function's bounds, you can be sure instantiating that function with this type will compile; in C++ you don't have that luxury.
noelwelsh 2y ago
In terms of implementation, you can view parametricity as meaning that within the body of a function with a generic type, the only operations that can be applied to values of that type are also arguments to that function. This means you cannot write fn sort<A>(elts: Vec<A>): Vec<A> because you cannot compare values of type A within the implementation of sort with this definition. You can write fn sort<A>(elts: Vec<A>, lessThan: (A, A) -> Bool): Vec<A> because a comparison function is now a parameter to sort. This helps both the programmer and the compiler. The practical upshot is that functions are modular: they specify everything they require. It follows from this that if you can compile a call to a function there is a subset of errors that cannot occur. In a language without parametricity, functions can work with only a subset of possible calls. If we take the first definition of sort, it means a call to sort could fail at compile-time, or worse, at run-time, because the body of the function doesn't have a case that knows how to compare elements of that particular type. This leads to a language that is full of special cases and arbitrary decisions. Javascript / Typescript is an example of a language without parametricity. sort in Javascript has what are, to me, insane semantics: converting values to strings and comparing them lexicographically. (See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...) This in turn can lead to amazing bugs, which are only prevented by the programmer remembering to do the right thing. Remembering to do the right thing is fine in the small but it doesn't scale. Breaking parametricity definitely has uses. The question becomes one about the tradeoffs one makes. That's why I'd rather have a discussion about those tradeoffs than just "constime good" or "parametricity good". Better yet are neat ideas that capture the good parts of both. (E.g. type classes / implicit parameters reduce the notational overhead of calling functions with constrained generic types, but this bring their own tradeoffs around modularity and coherence.)
- dmvdoug 2y ago
  Do you have a blog or other site where you post your writing? Your explanations are quite good and easy to follow for someone like me, an interested/curious onlooker.
  - noelwelsh 2y ago

by marhee 2y ago

SkiFire13 2y ago

> For example, I believe C++ template programming also breaks "parametricity" by supporting template specialisation. C++ breaks parametricity even with normal templates, since you can e.g. call a method that exists/is valid only on some instantiations of the template. The issue is that the compiler can't help you check whether your template type checks or not, you will only figure out when you instantiate it with a concrete type. Things get worse when you call a templated function from within another templated function, since the error can then be arbitrarily levels deep. > My point is that in makes sense for C++ to allow this, I think. Whether it makes sense or not it's a big pain point and some are trying to move away from it (see e.g. Carbon's approach to generics)

marhee 2y ago
> C++ breaks parametricity even with normal templates I might be wrong here, but as I understand it "parametricity" means loosely that all instantiations use the same function body. To quote wikipedia: "parametricity is an abstract uniformity property enjoyed by parametrically polymorphic functions, which captures the intuition that all instances of a polymorphic function act the same way" In this view, C++ does not break parametricity with "normal" (i.e. non-specialised) templates. Of course, C++ does not type check a template body against its parameters (unless concepts/trairs are used), leading to the problems you describe, but it's a different thing as far as I understand.
- jcelerier 2y ago
  Hm, wouldn't any use of if constexpr break that definition? e.g. template<typename T> void f() { if constexpr (is_int<T>) { return 0; } else ...
- deredede 2y ago
  Parametricity is about behavior, not code. A function parametric in a variable should bevave identically for all values of the variable. If one instance of a C++ template fails to compile and another instance of the same template does compile it is a stretch to say they behave identically, even though they use the same code.
- lmm 2y ago
  To be parametric it needs to be the same body semantically, not just textually. Particularly in C++ with its heavy operator overloading and limited safety, you can very easily write a template whose body will do the right thing for some types and be undefined behaviour for others (e.g. if your template has comparisons in it and then you instantiate it with a pointer or something).

Quekid5 2y ago

> Consider for example std::vector<bool>: implementations can be made that actually store a single bit per vector element (instead of how a bool normally is represented using an int or char). Your example is considered a misfeature and demonstrates why breaking parametricity is a problem: the specialized vector<bool> is not a standard STL container even though vector<anythingelse> is. That's at best confusing -- and can leads to very confusing problems in generic code. (In this specific case, C++11's "auto" and AAA lessens some of the issues, but even then it can cause hard-to-diagnose performance problems even when the code compiles) See https://stackoverflow.com/a/17797560 https://stackoverflow.com/a/17797560 for more details.

beached_whale 2y ago
Vector bool may not have to store a range of space optimized bool values but the interface is still different enough and guarantees different enough that is is largely thought of as a mistake. For one the const reference type is bool and not bool const &. Plus other members like flip… mostly the issue is in generic code expecting a normal vector
HelloNurse 2y ago
The C++ vector<bool> specialization is bad because breaking many important implicit contracts about taking the address of vector<> elements makes it practically unusable if a normal vector<> is expected, but it isn't specialized incorrectly in a formally meaningful sense: all errors are outside the class (unsatisfied expectations from client code) and implicit (particularly for C++ as it was at the time).
- Quekid5 2y ago
  You're not wrong, but is at the very least weird that a specialization doesn't conform to the concept that the general template does. Something which proper parametricity would have avoided -- if it were available. (The Hysterical Raisins are understandable, esp. given that it wasn't even possible to specify Concepts in C++ until 2020...)
  - 2y ago

nialv7 2y ago

one thing you can reason about a function is: does it exist at all? if you don't have parametricity, you can't even be sure about that. in Rust, as long as your type satisfies a generic function's bounds, you can be sure instantiating that function with this type will compile; in C++ you don't have that luxury.

noelwelsh 2y ago

In terms of implementation, you can view parametricity as meaning that within the body of a function with a generic type, the only operations that can be applied to values of that type are also arguments to that function. This means you cannot write fn sort<A>(elts: Vec<A>): Vec<A> because you cannot compare values of type A within the implementation of sort with this definition. You can write fn sort<A>(elts: Vec<A>, lessThan: (A, A) -> Bool): Vec<A> because a comparison function is now a parameter to sort. This helps both the programmer and the compiler. The practical upshot is that functions are modular: they specify everything they require. It follows from this that if you can compile a call to a function there is a subset of errors that cannot occur. In a language without parametricity, functions can work with only a subset of possible calls. If we take the first definition of sort, it means a call to sort could fail at compile-time, or worse, at run-time, because the body of the function doesn't have a case that knows how to compare elements of that particular type. This leads to a language that is full of special cases and arbitrary decisions. Javascript / Typescript is an example of a language without parametricity. sort in Javascript has what are, to me, insane semantics: converting values to strings and comparing them lexicographically. (See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...) This in turn can lead to amazing bugs, which are only prevented by the programmer remembering to do the right thing. Remembering to do the right thing is fine in the small but it doesn't scale. Breaking parametricity definitely has uses. The question becomes one about the tradeoffs one makes. That's why I'd rather have a discussion about those tradeoffs than just "constime good" or "parametricity good". Better yet are neat ideas that capture the good parts of both. (E.g. type classes / implicit parameters reduce the notational overhead of calling functions with constrained generic types, but this bring their own tradeoffs around modularity and coherence.)

dmvdoug 2y ago
Do you have a blog or other site where you post your writing? Your explanations are quite good and easy to follow for someone like me, an interested/curious onlooker.
- noelwelsh 2y ago