Cairo impl design

[spapinistarkware]

Cairo trait and impl system design

Definition of traits in Cairo.

A trait is a "type" for a collection of functions.
In the same way that a function type is a "type" for a single function.
Let's see the analogy.

Trait:

trait Foo {
    fn bar();
}
impl FooImpl of Foo {
    fn bar() {
        // ...
    }
}
fn main<impl Imp: Foo>() {
    Imp::bar()
}

Here, main expected some Imp that has a function bar of a known signature, but the function
itself is not known. It is a generic parameter.

Function:

fn foo() {
}
fn main<f: Fn()>() {
    f()
}

Here, main expects some f that is a function of a known signature, but the function itself is
unknown. It is a generic parameter.

So, a trait in Cairo is equivalent to in a way to a tuple of functions with some signature. A
generalization of a function type.
To those coming from rust or OOP, this may seem a bit weird. But it is actually a very natural.
There is no Self type in Cairo traits.

There are a few main differences from rust:

• Explicit Self.
• Named impls.
• Multiple impls allowed.
• Methods.

Implicit Self generic argument

Rust traits have a hidden generic argument.

pub trait Add<Rhs> {
    // Self is available here.

    type Output;
    fn add(self, rhs: Rhs) -> Self::Output;
}
// i32 is given as Self.
impl Add<u8> for i32 {
    type Output = i32;

    fn add(self, rhs: u8) -> u8 {
        self + (rhs as i32)
    }
}

For those who know rust or come from OOP background, this may seem really natural and obvious.
This begs the question though, why is there an asymmetry between i32 and u8? Between left and right?
If we wanted to be explicit with Self, we could maybe write it like this:

pub trait Add<Self, Rhs> {
    type Output;
    fn add(self: Self, rhs: Rhs) -> Self::Output;
}
impl Add<i32, u8> {
    type Output = i32;

    fn add(self: i32, rhs: u8) -> u8 {
        self + (rhs as i32)
    }
}

This is actually what happens in the background.
The implicit Self property has pros and cons:

• Pro: More ergonomic in a lot of cases
• Pro: Obvious place to declare methods (things that get called by a.foo()).
• Con: Introduces new language quirks and exceptions, less consistent.
• Con: Forces asymmetry between Self and other generic parameters
• Con: Must have at least one generic parameter

This is a tradeoff. In cairo, we chose making Self explicit. We feel this makes the language
simpler and more consistent.

2. Named impls and multiple impls.

In rust, impls are anonymous - they have no name. Also, you can only have one impl per concrete
trait and type.
In cairo, impls behave syntactically and semantically like other items - they are named and you can
define multiple impls (with different names) of the same concrete trait.

The anonymous impl pros and cons:

• Pro: Less verbose on declaration and usage.
• Pro: Impl uniqueness makes it easy to infer impls.
• Con: Introduces new language quirks and exceptions, less consistent.
• Con: Orphan rules. Impls must be defined near the trait or the type.

Impl inference, inconsistent crates and the orphan rules.

Both rust and cairo have impl inference. That means that code can specify a trait, and the compiler
will find the impl to use.

fn main(){
    // The compiler will find the impl for Add and use it.
    Add::add(1, 2);
}

A problem may arise when you have multiple crates that define impls for the same trait and type.
In this case, there is more than one possible impl, and inference will fail.

In rust, there is a unique impl for a trait and type, so you will get a compilation error.
Therefore, it would be impossible to depend on these two crates, which is bad.
Rust introduces the orphan rules to solve this problem.
Impls must be defined near the trait or the type.

In Cairo, there are no orphan rules nor uniqueness demand. To solve this problem when it occurs,
instead, you can always be explicit about which impl you meant. This is why impls are named.

use my_crate::MyAddImpl;
fn main(){
    MyAddImpl::add(1, 2);
}

Inference location.

In rust, because of orphan rules it is enough to check for its definition near the trait or the
type.

In cairo, impls are looked up in the current scope, in the trait scope and in the scope of each
of the generic arguments.

Impl names revisited.

Are names on items necessary? They have no semantic meaning. They are there to describe the item
for better readability.
For example, a function name indicates what it does. A variable name indicated what it holds.

In a rust world where impls are uniquely defined by trait and type, the names of the trait and the
type hold all the information, so a name on the impl is redundant.

In a cairo world where multiple impls are allowed, however, maybe there is a meaning for the name?

Here are some examples where names have meaning:

impl GovernanceToken of ERC20<ExchangeContract> { .. }
impl CollateralToken of ERC20<ExchangeContract> { .. }
impl ConfigAsJson of Serde<Config> { .. }
impl ModularAddition of Add<u32> { .. }

There are cases, however, where the name is redundant. In this case, it is desired to somehow avoid
this name, while still being able to explicitly refer to the impl in case of inference ambiguity.
There are some ways to solve this, but the best way is still an open question.
Suggestions to this are welcome.

Methods

A method is an ergonomic way to call a function on a value: value.foo().
In rust, you can define a method by adding taking any trait/impl on a certain type, and using the
self keyword:

impl MyImpl for MyStruct {
    fn foo(self) {
        // ...
    }
}
fn bar(a: MyStruct) {
    a.foo();
}

In Cairo, you can define a methods by taking any trait.impl and using the self keyword. Note that
unlike rust, there is no restriction on the type of the trait/impl, since traits and impl have
no Self type.

impl MyImpl of SomeTrait {
    fn foo(self: MyStruct) {
        // ...
    }
}
fn bar(a: MyStruct) {
    a.foo();
}

In rust, conceptually, methods are defined on the "type". Though, they can actually be defined in
unrelated files for unreleated traits. Since traits have a Self type, this is a natural place
to put methods.

In Cairo, there is no such natural place. Conceptually, methods could be defined anywhere, even on
free functions, using the self keyword. Having methods only on impls does not have the benefit
of having the associated Self type.

However, having methods on free functions can lead to name conflicts:

// a.cairo:
fn foo(self: A) {}
// b.cairo:
fn foo(self: B) {}
// main.cairo:
use a::foo;
use b::foo; // Error: Name conflict.
fn main(a: A, b: B) {
    a.foo();
    b.foo();
}

This is why in Cairo, methods still can only be defined on impls.

[iddriss]

Trait:

trait Foo {
    fn bar();
}
impl FooImpl of Foo {
    fn bar() {
        // ...
    }
}
fn main<impl Imp: Foo>() {
    Imp::bar()
}

Coming from a non-rust background, I initially found traits a little confusing; I thought of it as an interface but it didn't really fit into that paradigm. This put things into perspective a little, great read.
In the example above, the implementation of the trait uses foo instead of Foo. Does that mean it's case insensitive and would work regardless?
for example using multiple impls for the Foo trait.

impl FooImpl of Foo {
    fn bar() {
        // ...
    }
}

impl AnotherFooImpl of foo {
     fn bar() {
        // ...
    }
}

Should both work?

[spapinistarkware]

Oops, typo. Fixed above. Thanks!

[wraitii]

Thanks for taking the time to write this out. This makes the intent clearer and clears out some of my points in this post.

I have some further questions / comments / things that make me wonder if the design could be further clarified.

Implementations and modules are kind of the same thing / Suggestion for nameless impl

It seems to me like it would be acceptable to do:

// modularAddition.cairo
use traits::Add;
impl Add<u8, u8> { ... }

// regularAddition.cairo
use traits::Add
impl Add<u8, u8> { some other impl }

// somewhere_else.cairo
use traits::Add;
use modularAddition;
// or 
use regularAddition;

If the name needs to be specified, then perhaps just reusing the module name makes sense? This would reduce ambiguity.

Confusion about methods not entirely cleared up

It seems slightly awkward to define traits in Cairo 1 as 'a type for a collection of functions' that should be symmetrical, and self not really a particularly privileged type, and also use that to define methods on self.

Your example of ModularAddition for example doesn't seem like it should define methods, to an extent, or that it should do so on both arguments in case of a more generic ModularAddition<X, Y>. Those are more of an operator class of traits, and it might be worth to have some different syntax/effects for these. Perhaps this could be specified on the trait itself:

trait Something<T, U> {
    fn DoSomething() method of T, U {
    }
}

Or maybe a nomethod attribute if the generic behaviour should method of first-arg.

self-type and traits.

On the other hand, generic-less traits might be a mistake. There is already a way to group related functions together: a module. Having traits do that by default just seems redundant.

If traits had to have at least one generic type, even an explicit one, it would be somewhat easier to understand their purpose. In practice, literally all the traits in the corelib take an explicit T (or C) type as their first generic parameter, which acts as the self type. In the case of ModularAddition traits, this isn't really a self type, but it still makes sense to take generic types.

It would also prevent the issue of shadowing:

impl Something of MyTrait {
   fn foo(self: A) {}
   fn foo(self: B) {}
}

This is currently possible but broken (and in fact, should probably bug out since you point out that it would bug out with free functions).

[spapinistarkware]

1. Your first suggestion adds a special case to the language. That the module name somehow refers to the impl. I don't see the benefit though.
   Unnamed impls are a possibility, but I'm still not convinced it's necessary or good.

2. Adding a method keyword is something we considered. But why is it better than the self keyword?

3. I don't see why genericless traits are a mistake. Are 0 size types a mistake? Are traits with no functions a mistake?

IMO adding edge cases to the language just because they don't seems to be used often, is a mistake. It makes it harder to understand the language and is an opening to inconsistencies (for example, when using macros to generate code).

A module is not the same as an impl at all! You can't pass it as a generic arg!

Also, genericless impls are useful. From the top of my head:
trait Graph{
fn neighbors(Node)->Array;
}

For am algorithm that is generic in that impl.

In rust you would make a wrapper type. In cairo you don't need.

[wraitii]

1. Your first suggestion adds a special case to the language. That the module name somehow refers to the impl. I don't see the benefit though.
   Unnamed impls are a possibility, but I'm still not convinced it's necessary or good.

Sorry, that's not really what I meant. What I wanted to point out was that how impl are resolved lead to this working nicely. Because you can currently import a specific impl by importing the module containing it (per the rule of impl are resolved in the the current scope, in the trait scope and in the scope of each of the generic arguments. ).
So in essence nameless impl already work fine and have a de-facto name / grouping -> the name of the module. If you wanted to use modularAddition you'd just have a ModularAddition module somewhere containing all those impls, no need to import specifically the impls.
So it would look like

// math.cairo or something
trait Add {}
// ModularAddition.cairo
use math::Add;
impl Add { /* specific code for modular addition */ }

// usercode.cairo, bring the impl in scope via the module being brought in scope.
use corelib::math::ModularAddition;

(and to clarify in this example, the only difference from working Cairo1 code is that you'd need to write Impl _ of Add right now).

2. Adding a method keyword is something we considered. But why is it better than the self keyword?

Is the self keyword actually a keyword here or does it just take the type of the first variable ?
The reason is just the logical continuation of your reasoning I think:

This begs the question though, why is there an asymmetry between i32 and u8? Between left and right?

I agree that there's no real reason for this asymmetry in self-less traits, so why not make the method thing explicit. It would only be a keyword on the trait level which is perhaps not a ton of syntactic noise, and could enable nice use-cases such as commutative operators (as described for Add of two different types maybe).
It would also make explicit something that is currently implicit (defining a method), and that particular thing Cairo 1 is a bit 'weird' on, so maybe the added explicitness would be a good thing for e.g. new devs.

I get that in most cases you'll be defining methods on the first argument though, the self type, so this might be seen as a little redundant, but then you could just make the self a property of the trait in the first place and then have it be implicit.

Anyways, this isn't really a good or bad thing necessarily, just an interesting direction that this 'full symmetry' / self-less trait direction can be taken on.

A module is not the same as an impl at all! You can't pass it as a generic arg!

Sorry, my point was that a generic-less trait ends up being the same sort of 'thing' as a module, not that a module is the same thing as a trait in general.

3. I don't see why genericless traits are a mistake. Are 0 size types a mistake? Are traits with no functions a mistake?

Well, generic-less traits are kinda weird. They don't necessarily feel like a logical extension of 1-generic or n-generic traits, because they still define methods.
What I would expect from higher-generic-traits is that no-generic traits are just a bundle of functions, not a way to specify methods on some specific types. If you don't have a self type and no generic type argument, what are you defining methods on ? But in practice, 0-generic traits seem to correspond to struct implementations in rust, which use a slightly simpler syntax, and aren't a trait at all.
So that's kind of unexpected and IMO a little weird, which is why I think they could be removed.
Though in that case, with respect to this:

Also, genericless impls are useful. From the top of my head: trait Graph{ fn neighbors(Node)->Array; }

Isn't that just a struct implementation, which takes an impl in rust? Intuitively, I would side with rust that their behaviour makes more sense.

Consider rust:

struct Node {}
impl Node { fn neighbors(Node) -> Array; }

v Cairo

struct Node {}
trait Node { fn neighbors(Node) -> Array; }
impl NodeTrait for Node { fn neighbors(Node) -> Array { ... } }

But maybe I'm misunderstanding you or missing something, because I don't understand this comment:

For am algorithm that is generic in that impl.
In rust you would make a wrapper type. In cairo you don't need.

You mean an algorithm that would take an arbitrary 'Graph'-compatible type ? But Cairo 1 doesn't really allow that since the Graph trait is defined only for the Node struct?

[wraitii]

After a talk with @spapinistarkware, here are the answers to the above:

1. Regarding naive nameless impl, this could lead to ambiguity that cannot be resolved. E.G. this is possible:

// moduleA.cairo
impl TryInto<felt252,u256> { ... }
impl Into<u256, felt252> { ... }

// moduleB.cairo
impl TryInto<felt252,u256> { ... }
impl Into<u256, felt252> { ... }

// Now you cannot import one from A and one from B, so in some cases this could get you stuck.

2. Is the self keyword actually a keyword here or does it just take the type of the first variable ?

It is indeed actually a keyword, so the rest of the comment doesn't really apply. Ergo, traits don't always define methods, and so things make more sense overall.

3. Part of the comment is invalidated by self being special. Shahar also said that a more rust-like syntax to declare methods on struct was possibly wanted, so that part of the comment may also be invalidated in the future.

With regards to the usefulness of generic-less traits, they can be seen as 'groups of functions' for generic programming.
E.G. you can have this:

trait MathOp {
   fn Add(...);
   fn Sub(...);
   fn Mul(...);
}
// I believe this isn't cairo 1 syntax for this but you get the idea.
// This function is only defined for these specific operations.
fn ProcessOp<op: MathOp>(a, b) {}

Instead of having to do something more like this:

struct MathOp;
trait MathOp {
   fn Add(...);
   fn Sub(...);
   fn Mul(...);
}
impl MathOp for Mathop {...}
fn ProcessOp<op: MathOp>(a, b) {}

[wraitii]

Regarding nameless impl

I think it should be possible to just give impl a default name for importing.
To reuse my example from above, the problem is the following:

// moduleA.cairo
impl TryInto<a,b> {...}
impl TryInto<c,b> {...}
impl Into<a,b> {...}

// moduleB.cairo
impl TryInto<a,b> {...}
impl Into<a,b> {...}

Let's say I want TryInto from A and Into from B, I should be able to write

use moduleA::TryInto<a,b>;
use moduleB::Into<a,b>;

The names are unambiguous, there cannot be collisions since you can't define the same implementation for the same types in the same module several times.
If having <> in use is problematic, it could perhaps be parsed as:

use moduleA::TyInto_a_b;

in the case where there is ambiguity that needs to be resolved.

[lambda-0x]

impl Add<u8> for i32 {
    type Output = i32;

    fn add(self, rhs: u8) -> u8 {
        self + (rhs as i32)
    }
}

I think this should be:

 impl Add<u8> for i32 {
     type Output = i32;
 
     fn add(self, rhs: u8) -> Self::Output /* or i32 */ {
         self + (rhs as i32)
     }
 }

same for other example