High Order Function with Type Parameter

Agreed. I propose we take a break from this thread. I'll try to compose a summary post or link to a blog of my findings later, which we can then discuss (perhaps a new thread and link from here). But I want to first go do discussion in the other threads, so my understanding is more holistic, not just this one NatPos example.

Yes, that sounds like a good idea :slight_smile:

<rant>I don't like Ceylon's verbose english language combined with Java-esque syntax</rant>

<opinion>I'd prefer Rust hadn't chosen curly brace delimited blocks and semicolons. Python/Haskell indenting is so much clearer/consistent/concise. Code readability is priority #1 in open source.</opinion>

I agree, Ceylon doesn't feel right to me, but I haven't done an objective analysis, just what I have seen of it feels like a step backwards. Rust feels like a step forward from C++, and is less restrictive than Haskell's purity (and more efficient than its lazyness). Personally I would like to see a full effect system, and that's what I am planning for one of my own language projects, but its nice to have a language like Rust already available that is getting close to what I want.

I am here in the Rust forum because it has the most direction towards what I think I want. Also apparently the community is attracting people like you (Haskell experts) and others who I can learn from and test my ideas about programming language design. Much appreciated.

As you know already, I am not yet enamored with the "lifetypes" (lifetimes infecting polymorphic typing) enforced by default. Wish there was some per module or file way to turn that off. Perhaps my opinion will change as we discuss more the need for generalized iterators. I noted your comment in the other thread suggesting perhaps a different way to type the polymorphic lifetimes.

Agreed. I think where we ended up is that the correct module implementation for NatPos required 4 traits and I am claiming that with first-class intersections (which will dictate the need for first-class unions), then the same safety only needs 2 traits, precisely because...

...the trait NatPos : Nat + Pos nominal intersection should no longer be supported in my proposal and thus the only way to call any methods on a Nat /\ Pos is to destructure it with pattern matching (which is not extensible) or to call trait implementations that exist for both Nat and Pos via a dynamic dispatch (which is extensible but ostensibly will require a global hashmap dictionary). I will detail this proposal more later.

I am sure you have some differences in mind, but a non-extensible tagged union is an Enum, and calling trait implementations that exist for both Nat and Pos is what "Nat + Pos" means, and you get dynamic dispatch from trait-objects.

I don't understand Bob's point given a data type can implement both an Ord and an OrdDiv and at least in Rust one can declare the intersection Ord + OrdDiv. Anyone know what he means?

In the second point, I presume he is referring to Haskell's global inference. It seems with module scoping and non-global type inference, that Rust wouldn't have this same issue?

Perhaps the easiest approach is to start out with 2 minimal traits Read<T> and Write<T> (In this analysis an immutable object is an object that doesn't implement Read). Once you have defined these minimal traits then you can group then in super traits. (As an example the set of circles is a subset of the set of ellipses.). Heres is an initial idea

  • SuperSet<T> provides Read<T>
  • SubSet<T> provides Write<T>
  • InterSection<T,U> provides SubSet<T> and SubSet<U>

The above list of rules is far from complete. As and example I didn't add transitive rules for subset relations. Furthermore any implementation of SubSet could cause an automatic implementation of SuperSet. But my point is that you probably have to write these rules by hand before you try to implement them in any language. If you are lucky then you can use the following implementation syntax in Rust (Otherwise you may need macros)

impl <T> Read<T> for U where U: SuperSet<T>

Also have a look at rusts conversion traits to see how rust deals the pointers and copying. Note how From provides Into and note how Option is used for conversions that may fail.

I am not fully convinced that all these intersection traits are useful for a lot of real life applications, but I guess that is another discussion. Traits are fun..

Robert means that if you define sort to use Ord, then there can only be one implementation of Ord for any given type. As you can see in my sort definition I pass a Relation function, which is one solution to this problem. I would guess from Robert's comments that he is a fan of ML style modules where Ord could be a module and you could pass the module as a parameter to another module (or function). This allows different modules to be passed to get different orderings. To understand this look at comparisons between ML modules and Haskell type-classes. If you want to see a safe imperative language (quite like Rust) that uses modules instead if type classes look at Ada.

Personally I find modules result in a lot of parameter clutter, and I find they have a problem of allowing more incorrect options. For example I can call sort on a collection of Fish and pass the ordering module for Trees. Obviously the compiler will catch this, but why give yourself more ways to be wrong? Modules also add more boilerplate than type-classes.

I don't really get his second point either, I would assume like you do that he is referring to the inference of type-classes in Haskell, which Rust doesn't do.

There's some good videos of Robert's lecture courses out there like this one on HoTT

The way you described the difference between the module parameterization versus dependency injection methodologies immediately leads me intuitively in the abstract as to why module parametrization is possibly an anti-pattern. Thanks. Specifically it abstractly appears to be yet another error of premature specialization, because it apparently requires the module developer to decide the range of parameterization. Whereas, with dependency injection the organizational strategy is open to extension and is as granular as the caller wants. Afaics, the only purpose of modules should be encapsulation and scoping.

In short, the (new?) golden rule is that bottom-up dependency injection and inversion-of-control trumps top-down controlled parameterization and loss of encapsulation (in the case of Rust's low-level resource lifetime typing).

Note Rust does support dynamic dispatch via trait objects, so an alternative solution is (which does compile):

use std::io::Read;
use std::fs::File;
use std::io:: Cursor;

fn f<G: Fn(Box<Read>) -> ()>(g: G, pred: bool) {
  if pred {
    g(Box::new(File::open("foo").unwrap()));
  } else {
    g(Box::new(Cursor::new(b"foo")));
  }
}

fn main() {}

Rewriting that example in Rust:

fn apply<A,B>(f: A -> List<A>, b: B, s: String) -> (List<B>, List<String>) {
  (f(b), f(s));
}

It’s a type error because, B and String are not A. That is, the type A is fixed on the right of the quantifier <A,B>. We really want the polymorphism of the argument to be maintained so we can apply it polymorphically in the body of our function.

Thus the reason we'd need higher-ranked types (HRT) in this example translated from Scala to Rust, is because we desire for the type of A to be inferred by the compiler. Instead if Rust had first-class unions, we could annotate the type bounds of A so no higher-ranked inference would be required:

fn apply<A: B \/ String,B>(f: A -> List<A>, b: B, s: String) -> (List<B>, List<String>) {
  (f(b), f(s));
}

You've restricted (changed) the intended semantics. The programmer intended that the input function would only need Read semantics (which is yet another example of how universal inference could be dangerous, see below).

If we want the input function to not use dynamic dispatch (i.e. not use trait objects), then must input a function whose polymorphism is not resolved at the scope of the signature of fn f, e.g. by employing the trait Foo as shown in the solution upthread.

With first-class unions, one could imagine perhaps we could eliminate the boilerplate (and lack of degrees-of-freedom) imposed by the trait Foo, by writing or the compiler inferring HRT:

fn f<A: (File \/ Cursor) /\ Read, G: Fn(A) -> ()>(g: G, pred: bool) {

Which could mean to resolve (caller provide) g with two non-dispatched variants of Read, one for File and the other for Cursor.

@keean and I have been discussing this, and I have pointed out (after @keean showed an example type derivation of divergence) that implicit inference of intersections can combine two different things in ways that the programmer never intended. Imagine a function which calls the add and convolve methods on a generic parameter A. With inferred intersections, the compiler could infer any combination of trait bounds for A which satisfy those two methods, giving weird semantics that were not intended (and also making the inferred types potentially gargantuan). This an example of why universal inference is dangerous.

Also, I have pointed out to @keean that (as explained by the Lambda Cube) function application is a higher-order function operator. First-class intersections (and unions) are higher-order type (construction) operators. When higher-order abstractions are allowed to interact, then the universal inference (i.e. principle typings) of type system diverges to infinite recursion (i.e. is undecidable), analogous to two mirrors facing each other. A concise example of this recursion divergence can be seen by the interaction between Scala's type (construction) operators and first-class subtyping where subtyping is a higher-order subsumption operator. Afaics Scala's problem in that linked example is not confined to universal inference, but to resolving the annotated type, thus illustrating the danger of making the type system unsound when higher-order abstractions are allowed to interact.

Thus I am arguing to @keean that if a language has both higher-order first-class abstractions:

  1. Function application operators
  2. Intersection type construction operators

Then only one of them should interact with the other so as to remove one of the analogous mirrors and prevent unsound divergence into infinite recursion. Thus I argue that intersections can contain higher-order functions, but function application should be illegal for intersections (of functions).

As for @keean's point about fn f(g : Fn(File \/ Cursor) -> Fn(File \/ Cursor)), I wrote to him:

This does not occur very often because it means you can give it an A or a B and you get back an A or a B, but with no relation to the type you gave it.
...
Basically (A \/ B) -> (A \/ B) throws away too much type information.

Well the type signature doesn't necessarily mean that it throws away information. The type signature does not say that if you give it an A, that has any impact on whether you might get an A or a B. The runtime computation is elided from our typing consideration. There could be valid computation with that type which has nothing to do with throwing away information.

That was all clear to me before you wrote it. I was not arguing that function is common. Rather I am stating that the following is not a function in a language without some form of I presume dependent typing:

(A -> A) /\ (B -> B)

Because the call-site will be selecting a result type based on the input type at compile-time.

Which lead to follow on discussion:

Yes, thats what static typing usually does, and this is what we usually want. Consider the identity function:
fn id<A>(x : A) -> A {

Afaics, you are conflating nominal types and anonymous types.

When we call id, we pass any input type and get back that type for one function id.

When we call (A -> A) /\ (B -> B), we are calling potentially two separate functions anonymously. There is no nominal contract (constraint) which says they have to have the same semantics. Semantics are controlled through naming scope.

Thus that is not a function type. It can only be verified to be correct in some dependent typing.

Whereas the union case at least guarantees us we get a subsumption to one function.

Ditto we should not infer intersections of types, for the same reason. The programmer must write the trait bounds when there is an intersection otherwise we can get unintended semantic combinations.

To which @keean replied:

(A -> A) /\ (B -> B)

You need to not get confused between what the type means and how we might implement it.

The intersection of two functions is still a function. It must be. Think of it like this:

The type A -> A is the set of all functions that take a single argument of type A and return a value of the same type. The functions are the values that inhabit the type.

The type B -> B is the set of all functions that take a single argument of type B and return a value of the same type.

So (A -> A) /\ (B -> B) is the set of all objects that are in BOTH the sets A -> A and B -> B, so the object is a function and can be applied.

And so we continue to discuss this in private.

For completeness, I would like to provide the solution to the Scala function in Rust using the technique mentioned above:

use std::collections::LinkedList;
trait MakeSingleton {
    fn new<A>(&self, x : A) -> LinkedList<A>;
}

fn apply<A, F>(f: F, b: A, s: String) -> (LinkedList<A>, LinkedList<String>)
where F : MakeSingleton {
    (f.new(b), f.new(s))
}

fn main() {
    struct MyMakeSingleton;
    impl MakeSingleton for MyMakeSingleton {
        fn new<A>(&self, x : A) -> LinkedList<A> {
            let mut list = LinkedList::new();
            list.push_back(x);
            list
        }
    }
    println!("{:?}", apply(MyMakeSingleton, 1i32, "ABC".to_string()));
}

It's not really that much boilerplate, the trait definition of 'MakeSingleton' is really just giving a name to the type of 'f' which used to be in the signature of 'apply', and giving it a name may make the signature of 'apply' more readable. In 'main' the definition of the function to pass to 'apply' is a few lines longer as we have to declare the function in a trait implementation. That's it, and it is quite easy to do when you get used to it, and it has the advantage of preserving the monomorphisation properties of Rust (which higher-rank-types would not).

Disagree. For comparison:

fn apply<A: B \/ String,B>(f: A -> LinkedList<A>, b: B, s: String) -> (LinkedList<B>, LinkedList<String>) {
  (f(b), f(s));
}

I prefer a programming language that isn't noisy and let's me write the code in the most straightforward and clear manner. Boilerplate makes code more unreadable, consuming more man-hours for every person who reads that open source code. With open source taking over the world of programming, conciseness/precision of expression has become a paramount priority.

I feel strongly that I am correct about this.

You cannot be correct about an opinion :slight_smile: You might prefer to have higher ranked types, but you would lose monomorphisation, and you would lose the ability as a programmer to see this, as with HRT the compiler may or may not be able to optimise it statically (but probably not). I prefer to keep the performance and the monomorphisation. I don't think programming languages should ever be optimised for 'keystrokes'. The correct question is does the extra 'boilerplate' obscure what is going on or make it clearer (after all type signatures are boilerplate and they make programs easier to read most of the time).

I don't see any HRT nor loss of monomorphism in my concise alternative.

Well I was responding to the quoted paragraph:

If you want union types they would not be trait bounds (note: in Rust the things to the right of a ':' in the type parameter list '<' ... '>' are traits), and you would want the intersection of the funciton types, I don't think the union version would work because the output types would be an input to the funciton:

fn apply<B>(f: B -> LinkedList<B> /\ String -> LinkedList<String> , b: B, s: String) -> (LinkedList<B>, LinkedList<String>) {
  (f(b), f(s));
}

The reason the union typed version would not work is we would end up with a function like this:

(B \/ String) -> LinkedList<B \/ String>

How would you actually write this function? Both the arguments and return types are 'inputs' to the function, IE it allows the call site to chose B -> LinkedList<String> for example, or String -> LinkedList<B> as valid uses.

Another obstacle is that Rust does not actually have a function type, you have to use traits, because each closure has a unique type.

Perhaps you skimmed it and missed the bolded portion.

This forum software has so many bugs!

The type parameter A is not an input argument type thus is not a trait bound, rather it is only constraining the type of the function f.

Correct, I wrote the result type incorrectly. Instead it would be:

fn apply<A: B \/ String,B>(f: A -> LinkedList<A>, b: B, s: String) -> (LinkedList<A>, LinkedList<A>) {
  (f(b), f(s));
}

If you want the other way, do this:

fn apply<B>(f: B -> LinkedList<B>, g: String -> LinkedList<String>, b: B, s: String) -> (LinkedList<B>, LinkedList<String>) {
  (f(b), g(s));
}

HRT seems to be all about inference of the function signature. Perhaps there are cases of polymorphism where we can't annotate and must have inference? In that case, we will be forced to use your singleton concept if we want monomorphism instead of HRT.

Type constraints are called traits. A constraint is not a type, and 'A' would still be restricted to a single type with that kind of setup. Where you have a single type variable like 'A' it can only stand for a single type. It could stand for a union type if they were supported, but it could probably not be inferred.

I don't know what you are referring to. The type parameter A is merely a shorthand for writing:

fn apply<B>(f: B \/ String -> LinkedList<B \/ String>, b: B, s: String) -> (LinkedList<B \/ String>, LinkedList<B \/ String>) {
  (f(b), f(s));
}

I am writing pseudo-code. Rust doesn't have first-class unions.

I suppose we miscommunicated.