[RFC] Traits

[ryzhyk]

No design proposal yet. Just collecting pros and cons of adding support for traits (or some other form of generics) to the language.

Why supporting generics (traits) is a good idea

• Avoid Rust compilation errors. Since we don't have a way to specify trait bounds, extern functions that require such bounds must be declared without trait bounds in DDlog. Calling such a function with an argument that does not satisfy the bounds causes Rust compilation errors.
• Cleaner way to implement string conversions
• Write more logic in DDlog without having to resort to Rust.
• Avoid blanket trait implementations for all types in the program, e.g., applications that do not require serialization can skip implementing serde traits, while those that do can only implement Serialize/Deserialize for a subset of types. Same goes for FromRecord, ToRecord, Mutator.
• Generics increase the expressive power of relation transformers and enable reusable tranformer libraries by allowing transformers to be generic over argument and return types. In the current implementation of transformers in DDlog-1 we achieve this by requiring the caller to provide "accessor" functions with input relations. Traits are a cleaner way to achieve the same.

Why traits are a bad idea

• Design and implementation complexity.
• Not exactly a downside, but something to consider: much of the power of traits in Rust comes from the auto-derive mechanism. Since we are not realistically going to support macros (certainly not procedural macros) any time soon, we will need a way to delegate trait implementation to Rust, e.g., by having a #[derive] attribute that will tell DDlog that the type implements the trait, but will delegate the actual implementation to Rust.
• The previous item will make the interpreter story more complicated, as we will need to expose trait implementations written in Rust to the interpreter.

[Kixiron]

Avoid Rust compilation errors.

Absolutely love this one, the more information we have within ddlog (and by extension, the more information the compiler has access to) the better

Avoid blanket trait implementations for all types in the program, e.g., applications that do not require serialization can skip implementing serde traits, while those that do can only implement Serialize/Deserialize for a subset of types. Same goes for FromRecord, ToRecord, Mutator.

I think it's worth noting that this isn't actually strictly related to traits, we could feasibly detect what plumbing traits are required automatically, this could be a really substantial compile time and binary size gain though, great idea!

The previous item will make the interpreter story more complicated, as we will need to expose trait implementations written in Rust to the interpreter.

I'd imagine this is about the same level of complexity as exposing ddlog functions to dynamic code as well, so it may be a moot point

[ryzhyk]

I think it's worth noting that this isn't actually strictly related to traits, we could feasibly detect what plumbing traits are required automatically, this could be a really substantial compile time and binary size gain though, great idea!

Automatic detection is not always possible, since the code that invokes these traits can be on the client side (e.g., serialization).

I'd imagine this is about the same level of complexity as exposing ddlog functions to dynamic code as well, so it may be a moot point

You're right, and I have to admit I don't know how to do either well :)

[mihaibudiu]

Traits are great, we'd love to have them in P4 too, but if we don't know how to implement them, the question is academic.
I never read a paper on trait type inference. Is it easier than type inference with subtyping?

[ryzhyk]

No idea what the complexity is.

[mihaibudiu]

Then clearly the answer is: "we won't do it in the first version of the new implementation."
We can add it as an issue that we'd like to solve in the future.

[ryzhyk]

I think we should figure out how to do it properly, including inference algorithm.

[ryzhyk]

Added another item in pros:

Generics increase the expressive power of relation transformers and enable reusable tranformer libraries.

[mihaibudiu]

We don't need traits for that. Today our generics are more like c++ templates, checked at use time. They work fine for most uses. You can start with templates and convert them to traits later hopefully.

[ryzhyk]

Let's say you wanted to implement a transformer that generalizes recursive path computation, but would like to make it generic in the Edge type:

Path(x,y) :- Edge(x,y).
Path(x,a) :- Edge(x,y), Path(y, z).

How would you do this without generics?

[mihaibudiu]

I said that you need generics but not yet traits

[ryzhyk]

Fair enough. My thinking is, we should do it properly if we can.

[mihaibudiu]

I am saying that we don't need to do it right away, there is a way to start with templates and convert them to traits when we know how to do it.

[ryzhyk]

I understand, and I don't agree this is a good approach :)

[mihaibudiu]

If you don't know how to do it it may be the only approach.

[ryzhyk]

I mean we could also learn how to do it, but I guess that's crazy talk :)

[mihaibudiu]

You have ~100 things that you need to do, the question is not whether you can do it, but where do you put it in the list and how much it will block the items after it in the list.
The language will have to have some generics even in the first implementation.
I am just trying to be pragmatic.

[ryzhyk]

That is true, we need to evaluate the complexity and decide if it's worth it.

[ryzhyk]

Rust's new trait solver: https://rust-lang.github.io/chalk/book/what_is_chalk.html

[mihaibudiu]

If the API of this solver is general-purpose perhaps it can be just reused. That would be great.

[ryzhyk]

I am staring to read up on it. It apears to be rust-specific. But internals might still be reusable.

[ryzhyk]

I've been reading about chalk and the underlying theory. I believe we should be able to reuse the solver component of chalk by encoding our type system in the IR supported by the solver (the encoding is described in chalk book). Theoretically, the encoding part can be reused as well, but that may pull in too many Rust dependencies.

[ryzhyk]

Minutes of meeting (Sep 23, 2021):

• We don't want to support auto-dereferencing
• We want to support static and non-static members (that take self)
• We want to support mut variables and function arguments