3 ms·
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 applie
by 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 agoDo 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 agoThanks! I appreciate that. A few things: - https://scalawithcats.com/ https://scalawithcats.com/ is a book I'm writing. There is an associated newsletter to which I post blog articles and the like. - https://noelwelsh.com/ https://noelwelsh.com/ is my personal site, which hosts my blog.
- paulddraper 2y agoAs a former user of Scala and at times cats, I look forward to your work.
- norir 2y agoFair point about parametricity. A language could in the macro expansion do the equivalent of a scala implicit lookup for a sorting function for the type and return an error at macro expansion time if it can't find one. That avoids the doing the right thing requires discipline problem but I agree it is still less clear from the type signature alone what the type requirements are.
- nimish 2y agoThis is _also_ doable with the ability to constrain generics. sort<A> where A implements Comparable Simpler explanation IMO.
- tines 2y agoNot really an "also", "implements" is just syntax sugar for what the GP is saying.
- nimish 2y agoSure, but it's the same thing in 10x fewer words. Having parametric generic types that accept constraints allows your functions to have the best of all worlds. So a language _with_ that is superior. All zig needs to do is add some way to allow for constraints.
- James_K 2y agoFunctions can crash anyway. I don't see how what you describe is different from a function on integers that errors on inputs that are too big. The programmer has to actively choose to make function break parametricity, and they can equally chose not to do that.
- josephg 2y agoIn an ideal world, a function that only works for small integers would bake that into its type system. Ie, rather than accepting “any integer”, the function would accept a u8, or a value compile-time guaranteed in the range of 0..10 or something. Your point still stands though. Modern programming languages don’t constrain you much at all with their type systems. I spent a little time in Haskell a few years ago and it the kind of reasoning you can do about functions is wild. Eg, if a function has the type signature of A -> A, we know the function has to be the identity function because that’s the only function that matches the type signature. (Well that or the “bottom function”, which loops forever). Lots of functions are like that - where the type definitions alone are enough to reason about a lot of code.
- James_K 2y agoHaskell has quite a few partial functions in the standard library if I recall. Bog standard (!!), head, and tail for lists; fromJust to unwrap Maybes; and even some more interesting examples like "all" which mightn't work on infinite lists. Indeed any Turing-complete language includes partial functions of that final variety.
- _aavaa_ 2y ago> In an ideal world, a function that only works for small integers would bake that into its type system. Ie, rather than accepting “any integer”, the function would accept a u8, or a value compile-time guaranteed in the range of 0..10 or something. Ada takes this approach.