Totally unrelated to the topic but for my fellow Portuguese geeks, `Damas` is the same Damas that wrote the famous (or infamous) Portuguese C book.
Blew my mind when I found out.
Row polymorphism is excellent. I was intro'd to it in Purescript, but I would like to say that Typescript gives you some things that rhyme with it through its combinations of records at the type level.
Highly recommend people mess around with Purescript, you can feel how much pressure is relieved thanks to the row polymorphism tooling almost instantly. Truly, all we wanted as an industry is an easy way to bundle together various tags into our types, and row polymorphism gets you there.
I think row polymorphism is a fairly straightforward thing compared to dependent types in general, but can let you crush a whole class of errors and pay almost nothing in terms of expression costs.
> Highly recommend people mess around with Purescript, you can feel how much pressure is relieved thanks to the row polymorphism tooling almost instantly.
> I think row polymorphism is a fairly straightforward thing compared to dependent types in general, but can let you crush a whole class of errors [...]
Would you care to provide a few examples? I don't have experience with row polymorphism so I'm genuinely curious.
greet :: forall r. { name :: String | r } -> String
greet person = "Hello, " <> person.name <> "!"
greetWithAge :: forall r. { name :: String, age :: Int | r } -> String
greetWithAge person =
"Hello, " <> person.name <> "! You are " <> show person.age <> " years old."
main :: Effect Unit
main = do
let person = { name: "Alice", age: 30, occupation: "Engineer" }
-- greet can accept the person record even though it has more fields
log (greet person) -- Output: "Hello, Alice!"
-- greetWithAge can also accept the person record
log (greetWithAge person)
Structural typing relies on interface compatibility. Row polymorphism is a type-level feature in PureScript where record types are constructed with an explicit "row" of fields.
In Practice, row polymorphism is more granular, allowing you to explicitly allow certain fields while tracking all other fields via a ("rest") type variable.
Example: PureScript allows you to remove specific fields from a record type. This feature, is called record subtraction, and it allows more flexibility when transforming or narrowing down records.
You can also apply exact field constraints; meaning, you can constrain records to have exactly the fields you specify.
Lastly, PureScript allows you to abstract over rows using higher-kinded types. You can create polymorphic functions that accept any record with a flexible set of fields and can transform or manipulate those fields in various ways. This level of abstraction is not possible in TypeScript.
These are just a few examples. In the most general sense, you can think of row polymorphism as a really robust tool that gives you a ton of flexibility regarding strictness and validation.
Somtime ago, there was a debate on the ability of a static type system to model an 'open-world situation' where fields are added to records as model changes. (based on a post[1] which responded to a Rich Hickey talk).
The crucial point was that structural typing on which row-polymorphism is based can model such open-world situations.
Also, having such a system can free you from having overly nested types.
It would be great if Purescript or row-polymorphism became more popular.
This is also why I like interfaces in Golang (as a Haskell developer). You simply define a slice of the world you want to see and anything that fits the box can be passed.
It's just unfortunate golang interfaces dont support fields. Only methods.
Typescript fares better with its interface type
> It's just unfortunate golang interfaces dont support fields. Only methods.
Why is that unfortunate? Usually when defining interfaces you care about the API surface without wanting to care about the internals of what will eventually implement that API. If you suddenly also spec fields with the interface, wouldn't be too easy to couple the internals to the API?
I can't say I've programmed in Go too much, so maybe I'm missing something very obvious.
PureScript is such a cool language. I wish it would get more traction, but it feels like it's competing in the same space as TypeScript, and TypeScript seems to solve the category of problems it addresses well enough for most people.
"A record is an unordered collection of name to value mappings"
If there is one thing that is for sure, it is that we have too many names for "collection of name to value mappings".
In my book the term record is not what first comes to mind when thinking of unordered mappings. All of the usages of the word I can think of imply the possibility of access by name while retaining order. Sometimes this allows easy indexed access (database rows used to be called records) sometimes it doesn't (C structs which also used to be called record types).
C structs are record types, but, while the standard does guarantees an in-memory ordering, in the general case you can't really iterate through members and always have to access by tag, so it might as well be unordered.
Also in C++:
struct A { int x; int y; } a;
struct B { int y; int x; } b;
template<class C> concept has_x_y = requires(C c) {
{ c.x } -> std::convertible_to<int>;
{ c.y } -> std::convertible_to<int>;
};
int sum(has_x_y auto z) { return z.x + z.y; }
...
sum(a);
sum(b);
Yes, it is a very unusual definition of a record. As you rightfully noted, typically, a record is defined as a composite data structure mixing data types (indeed something more or less equivalent to a C struct basically).
Access by name is not even truly necessary and the difference between tuples and records is minimal (you could build something looking exactly like field access on top of tuples with functions and would get as a result something indistinguishable from an actual record).
The existence or not of an order is then totally accessory and it's generally straightforward to build an order on both provided the data types they contain is orderable by ordering the field and then using a lexicographic order.
I tend to agree with you. “Unordered” is very strange when clearly it is consistently “ordered” by some function(name, insertion_id) to facilitate low latency lookup.
The iteration order seems arbitrary to a human, but that is exclusively because function(name, insertion_id) is not optimized for a human. It seems strange to call the collection “unordered” because of how it appears to a human.
I wonder if there's a way to efficiently implement it without resorting to monomorphization?
A function that's polymorphic can be transformed into a more primitive (say C or assembly) function that gets extra arguments that carry the "shape" of the type variable (think of sizes, pointers vs. values, etc.). Is there a similar strategy for these polymorphic records?
I see two issues:
1. The offset of any particular field in the record is unknown at compile time
2. The size of the record itself is unknown at compile time (but this should be trivial as an extra argument.)
Swift solves this by using witness tables. Witness table is a skeleton of the desired record shape. It records offsets of desired fields as found in the actual supplied record. Each function call the actual record is not passed, but its corresponding witness table instead.
For instance, if the "prototype" of the argument is {int foo, float bar}, and I supply {int foo, int baz, float bar}, the table will be {foo: base+0 bytes, bar: base+8 bytes}.
Why doesn't it limit what it pushes on the stack to (foo,bar) instead of pushing (foo,baz,bar) along with an offset table? If the offset table is possible to construct at the callsite, compiling it into the call is also possible.
Because the polymorphic function called may also need to pass the whole record it was given to some other polymorphic function a la "void storeInGlobalStorage(key: string, value: T)".
What pistoleer said basically. Lets say a function expects a 2D point and you want to pass in a rectangle struct (which has x and y plus more info). You'd do something like:
Totally unrelated to the topic but for my fellow Portuguese geeks, `Damas` is the same Damas that wrote the famous (or infamous) Portuguese C book. Blew my mind when I found out.
https://www.wook.pt/livro/linguagem-c-luis-damas/99231
Row polymorphism is excellent. I was intro'd to it in Purescript, but I would like to say that Typescript gives you some things that rhyme with it through its combinations of records at the type level.
Highly recommend people mess around with Purescript, you can feel how much pressure is relieved thanks to the row polymorphism tooling almost instantly. Truly, all we wanted as an industry is an easy way to bundle together various tags into our types, and row polymorphism gets you there.
I think row polymorphism is a fairly straightforward thing compared to dependent types in general, but can let you crush a whole class of errors and pay almost nothing in terms of expression costs.
> Highly recommend people mess around with Purescript, you can feel how much pressure is relieved thanks to the row polymorphism tooling almost instantly.
> I think row polymorphism is a fairly straightforward thing compared to dependent types in general, but can let you crush a whole class of errors [...]
Would you care to provide a few examples? I don't have experience with row polymorphism so I'm genuinely curious.
How does it differ from structural typing in TypeScript though?
Structural typing relies on interface compatibility. Row polymorphism is a type-level feature in PureScript where record types are constructed with an explicit "row" of fields.
In Practice, row polymorphism is more granular, allowing you to explicitly allow certain fields while tracking all other fields via a ("rest") type variable.
Example: PureScript allows you to remove specific fields from a record type. This feature, is called record subtraction, and it allows more flexibility when transforming or narrowing down records.
You can also apply exact field constraints; meaning, you can constrain records to have exactly the fields you specify.
Lastly, PureScript allows you to abstract over rows using higher-kinded types. You can create polymorphic functions that accept any record with a flexible set of fields and can transform or manipulate those fields in various ways. This level of abstraction is not possible in TypeScript.
These are just a few examples. In the most general sense, you can think of row polymorphism as a really robust tool that gives you a ton of flexibility regarding strictness and validation.
Somtime ago, there was a debate on the ability of a static type system to model an 'open-world situation' where fields are added to records as model changes. (based on a post[1] which responded to a Rich Hickey talk).
The crucial point was that structural typing on which row-polymorphism is based can model such open-world situations.
Also, having such a system can free you from having overly nested types.
It would be great if Purescript or row-polymorphism became more popular.
[1] https://news.ycombinator.com/item?id=22090700
This is also why I like interfaces in Golang (as a Haskell developer). You simply define a slice of the world you want to see and anything that fits the box can be passed.
It's just unfortunate golang interfaces dont support fields. Only methods. Typescript fares better with its interface type
> It's just unfortunate golang interfaces dont support fields. Only methods.
Why is that unfortunate? Usually when defining interfaces you care about the API surface without wanting to care about the internals of what will eventually implement that API. If you suddenly also spec fields with the interface, wouldn't be too easy to couple the internals to the API?
I can't say I've programmed in Go too much, so maybe I'm missing something very obvious.
The API surface of some struct is determined by visibility, not by whether a member of the struct is a method or a field.
I can't remember the specifics for why fields cannot be used within a Go interface but I do remember missing it a few times while writing Go code.
PureScript is such a cool language. I wish it would get more traction, but it feels like it's competing in the same space as TypeScript, and TypeScript seems to solve the category of problems it addresses well enough for most people.
"A record is an unordered collection of name to value mappings"
If there is one thing that is for sure, it is that we have too many names for "collection of name to value mappings".
In my book the term record is not what first comes to mind when thinking of unordered mappings. All of the usages of the word I can think of imply the possibility of access by name while retaining order. Sometimes this allows easy indexed access (database rows used to be called records) sometimes it doesn't (C structs which also used to be called record types).
C structs are record types, but, while the standard does guarantees an in-memory ordering, in the general case you can't really iterate through members and always have to access by tag, so it might as well be unordered.
Also in C++:
Yes, it is a very unusual definition of a record. As you rightfully noted, typically, a record is defined as a composite data structure mixing data types (indeed something more or less equivalent to a C struct basically).
Access by name is not even truly necessary and the difference between tuples and records is minimal (you could build something looking exactly like field access on top of tuples with functions and would get as a result something indistinguishable from an actual record).
The existence or not of an order is then totally accessory and it's generally straightforward to build an order on both provided the data types they contain is orderable by ordering the field and then using a lexicographic order.
Yes in Haskell the names are just sugar for index numbers in a tuple (effectively)
I tend to agree with you. “Unordered” is very strange when clearly it is consistently “ordered” by some function(name, insertion_id) to facilitate low latency lookup.
The iteration order seems arbitrary to a human, but that is exclusively because function(name, insertion_id) is not optimized for a human. It seems strange to call the collection “unordered” because of how it appears to a human.
Unordered simply means the order isn’t exposed, not that the bits have somehow literally fallen out of the computer and are scattered on the floor.
But for an open world model we need the unordered definition.
As two structs that have same names at different places in the struct still need to conform to the generic record type
Well written!
I wonder if there's a way to efficiently implement it without resorting to monomorphization?
A function that's polymorphic can be transformed into a more primitive (say C or assembly) function that gets extra arguments that carry the "shape" of the type variable (think of sizes, pointers vs. values, etc.). Is there a similar strategy for these polymorphic records?
I see two issues:
1. The offset of any particular field in the record is unknown at compile time
2. The size of the record itself is unknown at compile time (but this should be trivial as an extra argument.)
For another approach without monomorphization see also my comment at [0] although it's only really meant for the immutable records.
[0] https://osa1.net/posts/2023-01-23-fast-polymorphic-record-ac...
Swift solves this by using witness tables. Witness table is a skeleton of the desired record shape. It records offsets of desired fields as found in the actual supplied record. Each function call the actual record is not passed, but its corresponding witness table instead.
For instance, if the "prototype" of the argument is {int foo, float bar}, and I supply {int foo, int baz, float bar}, the table will be {foo: base+0 bytes, bar: base+8 bytes}.
Why doesn't it limit what it pushes on the stack to (foo,bar) instead of pushing (foo,baz,bar) along with an offset table? If the offset table is possible to construct at the callsite, compiling it into the call is also possible.
Because the polymorphic function called may also need to pass the whole record it was given to some other polymorphic function a la "void storeInGlobalStorage(key: string, value: T)".
What pistoleer said basically. Lets say a function expects a 2D point and you want to pass in a rectangle struct (which has x and y plus more info). You'd do something like:
void f({float x, float y} p);
Becomes
void f(void* p, size_t offsets[2]);
I do not think using theoretical concept would make the convoept easier to understand.