Design patterns for composability with traits (i.e. typeclasses)?

[shelby3]

@keean

Whilst I think your proposal is nice, it is not for me, because performance and monomorphisation are critical things for me. That means the addition of the hash lookup and the lack of monomorphisation, and the requirement for GC, as well as the emphasis on immutability would not work for the kind of progamming language I am interested in.

Afaics, monomorphisation and trait objects could also be supported. I am thinking the polymorphic function (callee) can in some scenarios(1) be declared with trait bounds, but doesn't specify whether it expects a boxed trait object, a reference, a copy type, or a boxed hashtable lookup object. The caller will determine which version of the function is desired. The compiler can create the instance of the (callee) function required by the caller. Rust forces the decision at the function (for non-Copy types) and the data type (for Copy types) declarations, which seems at least in the former case to be premature optimization. I understand that by not declaring these invariants at the function declaration site, the caller is not forced to use a consistent option amongst the aforestated options, but isn't that desired?

Afaics, the immutability only applies when adding a data type to type parameter of a preexisting instance of a data type. All other operations can be mutable.

Afaics, the GC versus other mechanisms for managing the resource lifetimes is an orthogonal issue.

(1) Afaics, the supported scenario is where the callee doesn't apply other functions which make those aforementioned options polymorphic, or at least those functions invoked by the callee are not separately compiled. Note upthread where I employed the term 'module', I meant a separately compiled portion of code.

[shelby3]

@keean

my own work will continue down a slightly different route. I am interested in the expression problem part of this, but having looked around I have translated a solution from Haskell to Rust, and here is the code
...
This doesn't solve all the problems you are trying to solve, and it is not meant to, but it does seem a reasonable solution to the expression problem implementable in Rust as it is, the trick is to treat the collection object as an expression grammar rather than a simple type or enum. To implement a heterogeneous collection we would use the same technique as in the HList paper, and create a 'Cons' datatype, to represent a list constructor, implemented in the same way as 'Add' or 'Mul'.

Thanks for the code example as it aids my understanding of what you prefer or propose as an alternative.

The first point that jumps out at me is that a Cons (for constructing a List) is inherently an immutable data structure w.r.t. to extension of the element data type. In other words, a preexisting reference to a Cons (i.e. List) instance will not access the new elements added to the List by a subsequent Cons instance which refers to the preexisting one in the tail reference (e.g. struct Cons(head, tail). Thus you've only gained the solution to the Expression Problem by employing the same requirement on immutability that my proposal requires, yet afaics yours forsakes some of the major composability benefits of my proposal while also introducing boilerplate (and complexity making it more difficult to read and learn) to for example in the use-case of a heterogeneous collection needing to box the union as an Either. The positive attribute of your design pattern is it can be coded now in Rust and Haskell and doesn't require changes to the language or a new language.

[keean]

Based on my experience, if you want something soon, do not write your own language, or at least stick to something close to already implemented, so you have a simple implementation plan. Even my Prolog variant has taken me years but then negation is a big issue.

Have you looked at Go? It's garbage collected, has efficient parallelism due to go routines being stackless, has interfaces. Down sides are more like Java OO than functional generics. You can have a polymorphic collection by casting to the equivalent of Object which is interface{} and you can get the original type back using reflection and TypeOf. All methods are implemented as interfaces, so no inheritance.

[keean]

@shelby3

Thanks for the code example as it aids my understanding of what you prefer or propose as an alternative.

Unfortunately it does not support runtime polymorphism, but it can support mutability, a value in a Cons can be mutable, but it cannot be a different type without rebuilding.

[keean]

Some other thoughts, apologies if I am getting anything wrong: If the callee lists it's method requirements, then the reason we need to know all the traits for the Box is because we need to know the offset for each trait to separately compile the code, but that assumes the trait encoding is an array of structs type encoding. What if trait encoding is a struct of arrays? Now we can pass the trait offsets as parameters, meaning the callee could just specify the traits it needs, and the caller would have to validate those traits exist in the boxed collection. This would mean we could infer from all calls the intersection of these traits.

What this loses is the ability to locally define a new trait (which would require knowing the union of all possible types in the box). What it gains is a simple implementation, and the ability to do runtime polymorphism (so it cannot know what types are in the box).

It seems that with the normal boxed type-classes the receiver determines the list of traits the sender must implement, and with the 'union of types' approach the sender determines the list of type the receiver must implement its traits for. The former clearly fits better with an 'object' model where you view the data transmitted as the data and the methods you can use on them (even if the actual functions are not sent).

I think that something like the latter case can be achieved with enums and some macros. I might have a go and see if I can come up with something.

[shelby3]

@shelby3

Einstein also wanted his theories to be elegant, which is one reason he resisted quantum theory (and I think he will be proven correct)

I found the another clarifying post I had made on that topic.

Note also I had to justify my blog post about the Essence of Genius by making that point that a region is not the same as an area.

[keean]

Here's a quick attempt, at doing what you want in Rust. I have used something like the HList idea to define a type-list with append and fold, see: Rust Playground

This is the module defining the mechanism

mod hlist {
    pub struct Nil;
    pub struct Cons<H, T> {head : H, tail : T}

    pub trait TypeList {type Head;}
    impl TypeList for Nil {type Head = Nil;}
    impl<H, T> TypeList for Cons<H, T> where T : TypeList {type Head = H;}

    pub trait Append<A> : TypeList {
        type Output;
        fn append(self, x : A) -> Self::Output;
    }
    impl<A, T> Append<A> for T where T : TypeList {
        type Output = Cons<A, Self>;
        fn append(self, x : A) -> Self::Output {
            Cons {head : x, tail : self}
        }
    }

    pub trait With<T, A> {
        fn with(&self, x : &T, y : A) -> A;
    }

    pub trait Fold<F, A> : TypeList {
        fn fold(&self, f : &F, a : A) -> A;
    }
    impl<F, A> Fold<F, A> for Nil {
        fn fold(&self, _ : &F, a : A) -> A {
            a
        }
    }
    impl<H, T, F, A> Fold<F, A> for Cons<H, T> where T : Fold<F, A>, F : With<H, A> {
        fn fold(&self, f : &F, a : A) -> A {
            f.with(&self.head, self.tail.fold(f, a))
        }
    }
}

After that this is all we need to define a collection and process it:

fn main() {
    use hlist::{Nil, With, Append, Fold};
    
    let collection = Nil.append("a").append(23i32);
    
    struct Print;
    impl<T> With<T, ()> for Print where for<'a> &'a T : std::fmt::Debug {
        fn with(&self, x : &T, _ : ()) {
            println!("{:?}", x);
        }
    }
 
    collection.fold(&Print, ());
}

You can put any type in the collection, no bounds, and when you fold over the collection Debug (or whatever other trait requirements must be defined on all elements in the collection).

[shelby3]

@keean

but it can support mutability, a value in a Cons can be mutable

I already implied that mutability of the values is allowed in both your HList-like design pattern and in my proposal:

@shelby3

The first point that jumps out at me is that a Cons (for constructing a List) is inherently an immutable data structure w.r.t. to extension of the element data type.

@shelby3

Afaics, the immutability only applies when adding a data type to type parameter of a preexisting instance of a data type. All other operations can be mutable.

[shelby3]

@keean

Here's a quick attempt, at doing what you want in Rust. I have used something like the HList idea to define a type-list with append and fold, see: Rust Playground
...
You can put any type in the collection, no bounds, and when you fold over the collection Debug (or whatever other trait requirements must be defined on all elements in the collection).

Afaics, this code example is very useful for clarifying what your design pattern can't do, which my proposal can. Line 34 in your example is the late binding which enables solving the Expression Problem in both dimensions because it instructs the compiler to recursively walk the nested Cons type of the collection to type check that each H (Head type) satisfies the T : std::fmt::Debug trait bound in line 45:

f.with(&self.head, self.tail.fold(f, a))

But afaics, this conflates the fold algorithm with the choice of data structure. In other words, the data structure for the collection must be built with a recursive Cons-like structure so that fold can recursively destructure it for the compiler's type checker. Thus afaics, your design pattern would not work where the order of the enumeration of the elements is not consistent with order of the recursion of appended element types.

Thanks. Now I understand that HList can't do, which my proposal can.

[keean]

@shelby3

Thanks. Now I understand that HList can't do, which my proposal can.

Well this is just the simple TypeList style solution, we can do variants with an inject and project too, if I can get it to work in Rust, but as I said, the above is my first attempt

[shelby3]

@keean

Some other thoughts, apologies if I am getting anything wrong: If the callee lists it's method requirements, then the reason we need to know all the traits for the Box is because we need to know the offset for each trait to separately compile the code, but that assumes the trait encoding is an array of structs type encoding. What if trait encoding is a struct of arrays? Now we can pass the trait offsets as parameters, meaning the callee could just specify the traits it needs, and the caller would have to validate those traits exist in the boxed collection. This would mean we could infer from all calls the intersection of these traits.

Afaics, that will work and be faster than the hashtable I proposed, but it will require storing many variants of dictionaries in the executable.

Upthread I explained that my proposal does not put the dictionaries in trait objects. Instead each data type could have a cryptographic hash (or index to one) and the trait dictionaries can be looked at runtime by cryptographic hash pair in a hash table. Whereas, hardcoding the dictionary variants as you have explained is another option, which afaics trades space (executable download and memory space) for increased performance.

[shelby3]

@keean

Well this is just the simple TypeList style solution, we can do variants with an inject and project too, if I can get it to work in Rust, but as I said, the above is my first attempt

Perhaps so. But it will be adding a lot of complex boilerplate that wouldn't be necessary with my proposal in order to unconflate the type checking from dependence on the order of adding being consistent with the order of enumeration.

It seems it will make the code very difficult to understand.

It seems my proposal removes that for a K.I.S.S. result. But we'll have to study code examples of both design patterns to make sure.

And I do intuitively believe that the degrees-of-freedom of composability will suffer in your design patterns, because it is always working against itself to unconflate typing from data structure. Afaics, it will require lifting to higher abstractions for each new degree-of-freedom desired, adding more complex boilerplate but never being entirely unconflated for all degrees-of-freedom

[keean]

@shelby3

It seems it will make the code very difficult to understand.

The implementation is probably quite hard to understand, but it is easier to use than it is to write. It has the added advantage that you can use it today in Rust. We may be able to make further ease of use improvements using macros.

[shelby3]

@keean

The implementation is probably quite hard to understand, but it is easier to use than it is to write.

Error messages when only using could become more difficult to understand, such as the error message when a required trait isn't implemented by one of the data types in the collection.

@keean

It has the added advantage that you can use it today in Rust.

I had stated that also:

@shelby3

The positive attribute of your design pattern is it can be coded now in Rust and Haskell and doesn't require changes to the language or a new language.