jdegoes/HigherKindedJava.java

TomasMikula · 2016-07-08T02:54:05Z

@jbgi This version fixes your example:

class Option<A> {
  protected Option() { }
}
interface App<F, A> {
  F proof();
}
class OptionF  {
  private final Option<?> value;

  private OptionF(Option<?> value) {
      this.value = value;
  }

  public static <A> App<OptionF, A> fromOption(Option<A> v) {
    return new App<OptionF, A>() {

      public OptionF proof() {
          return new OptionF(v);
      }

    };
  }

  public static <A> Option<A> toOption(App<OptionF, A> v) {
    return (Option<A>) v.proof().value;
  }
}
interface Function<A, B> {
  B apply(A a);
}
interface Functor<F> {
  <A, B> App<F, B> map(Function<A, B> f, App<F, A> fa);
}

jbgi · 2016-07-08T08:30:38Z

@TomasMikula, indeed! But unfortunately this just move unsafety onto the type parameter:

    public static void main(String[] args) {
        App<OptionF, Integer> intOption = OptionF.fromOption(new Option<Integer>());
        App<OptionF, String> fakeStringOption = new App<OptionF, String>() {
            @Override
            public OptionF proof() {
                return intOption.proof();
            }
        };
        Option<String> notAstringOption = OptionF.toOption(fakeStringOption); // unsafe cast of an Option<Integer> to an Option<String> !!
    }

jdegoes · 2016-07-08T14:42:17Z

@jbgi Ah, you're right! Thanks for being so patient. 🙏

Although, I'd point out the following: this is not accidental type unsafety, but malicious type unsafety, in the sense that, a user would have to intentionally work around the limited options for constructing OptionF.

I have another idea to fix this loophole by moving closer to the paper, representing an existential type via skolemization, and forcing delimited modules on the user... I'll give it a try this weekend and post back.

TomasMikula · 2016-07-08T16:50:35Z

@jbgi Ah yeah. Second attempt:

class Option<A> {
  protected Option() { }
}
interface App<F, A, Self extends App<F, A, Self>> {
  <T> T accept(Function<App<F, A, ? extends F>, T> f);
}
class OptionF  {
  private OptionF() {}

  private static class AppOption<A> extends OptionF implements App<OptionF, A, AppOption<A>> {
    public final Option<A> value;

    AppOption(Option<A> value) {
      this.value = value;
    }

    public <T> T accept(Function<App<OptionF, A, ? extends OptionF>, T> f) {
      return f.apply(this);
    }
  }

  public static <A> App<OptionF, A, ?> fromOption(Option<A> v) {
    return new AppOption<A>(v);
  }

  public static <A> Option<A> toOption(App<OptionF, A, ?> v) {
    return v.accept(app -> (AppOption<A>) app).value;
  }
}
interface Function<A, B> {
  B apply(A a);
}
interface Functor<F> {
  <A, B> App<F, B, ?> map(Function<A, B> f, App<F, A, ?> fa);
}

jbgi · 2016-07-08T19:32:20Z

Well, this one is harder. But once you start using F-bounded polymorphism in conjunction with parametric polymorphism then they are cases where the compiler just accept anything, like this one:

  public static void main(String[] args) {
    App<OptionF, String, ?> fake = fake();
    OptionF.toOption(fake); // ClassCastException
  }

  static <A, F extends OptionF & App<OptionF, A, F>> App<OptionF, A, F> fake() {
    return new App<OptionF, A, F>() {
      @Override public <T> T accept(Function<App<OptionF, A, ? extends OptionF>, T> f) {
        return f.apply(this);
      }
    };
  }

TomasMikula · 2016-07-08T20:07:05Z

Interesting. One more try 😄. The difference here is addition of method

Self self();

to the App interface.

class Option<A> {
  protected Option() { }
}
interface App<F, A, Self extends App<F, A, Self>> {
  <T> T accept(Function<App<F, A, ? extends F>, T> f);
  Self self();
}
class OptionF  {
  private OptionF() {}

  private static class AppOption<A> extends OptionF implements App<OptionF, A, AppOption<A>> {
    public final Option<A> value;

    AppOption(Option<A> value) {
      this.value = value;
    }

    public <T> T accept(Function<App<OptionF, A, ? extends OptionF>, T> f) {
      return f.apply(this);
    }

    public AppOption<A> self() {
      return this;
    }
  }

  public static <A> App<OptionF, A, ?> fromOption(Option<A> v) {
    return new AppOption<A>(v);
  }

  public static <A> Option<A> toOption(App<OptionF, A, ?> v) {
    return v.self().accept(app -> (AppOption<A>) app).value;
  }
}
interface Function<A, B> {
  B apply(A a);
}
interface Functor<F> {
  <A, B> App<F, B, ?> map(Function<A, B> f, App<F, A, ?> fa);
}

jbgi · 2016-07-09T09:17:46Z

@TomasMikula: It looks like a good solution... but only for data types with 1 type parameters. A major problem with encoding of hkt that make use F-Bounded polymorphism is that it does not scale well to multiple type parameters: you would have to create a new, independent interfaces AppX for each data types of X type parameters, because App2 cannot extends App (due to the F-Bounded constraint). Eg.

interface App2<F, A, B, Self extends App2<F, A, B, Self>> {
  <T> T accept2(Function<App2<F, A, B, ? extends F>, T> f);
  Self self2();
}

Then how to retrieve an App from an App2 (eg. to make use for Functor) without giving up information on type parameters ?? I tried something like:

interface App2<F, F2, A, B, Self extends App2<F, F2, A, B, Self>> {
  <T> T accept(Function<App2<F, F2, A, B, ? extends F2>, T> f);
  Self self();
  App<F, B, ?> toApp();
}

class EitherF<A> {
  private EitherF() {}
  private static class AppEither<A, B> extends EitherF<A> implements App<EitherF<A>, B, EitherF.AppEither<A, B>> {
    public final Either<A, B> value;
    AppEither(Either<A, B> value) {
      this.value = value;
    }
    @Override public <T> T accept(Function<App<EitherF<A>, B, ? extends EitherF<A>>, T> f) {
      return f.apply(this);
    }
    @Override public AppEither<A, B> self() {
      return this;
    }
  }

  static class EitherF2 {
    private EitherF2() { }
    private static class App2Either<A, B> extends EitherF2 implements App2<EitherF<A>, EitherF2, A, B, EitherF2.App2Either<A, B>> {
      public final Either<A, B> value;
      App2Either(Either<A, B> value) {
        this.value = value;
      }
      @Override public <T> T accept(Function<App2<EitherF<A>, EitherF2, A, B, ? extends EitherF2>, T> f) {
        return f.apply(this);
      }
      @Override public EitherF2.App2Either<A, B> self() {
        return this;
      }
      @Override public App<EitherF<A>, B, ?> toApp() {
        return new EitherF.AppEither<>(value);
      }
    }
  }
  public static <A, B> App2<EitherF<A>, EitherF2, A, B, ?> fromEither(Either<A, B> v) {
    return new EitherF2.App2Either<A, B>(v);
  }
  public static <A, B> Either<A, B> toEither(App2<?, EitherF2, A, B, ?>  v) {
    return v.self().accept(app -> (EitherF2.App2Either<A, B>) app).value;
  }
  public static <A, B> Either<A, B> toEither(App<EitherF<A>, B, ?>  v) {
    return v.self().accept(app -> (EitherF.AppEither<A, B>) app).value;
  }
}

While it appears to works (very verbosely) until then, it stops to works as soon as you try to use something like a BiFunctor on an App2: then you lost information on the first type parameter of App2, and with it, the ability to retrieve a useful App from the App2.

The encoding in https://github.com/derive4j/hkt/blob/master/src/main/java/org/derive4j/hkt/__2.java does not have this problem: App2 simply extends App.
And since the annotation processor is packaged with the library providing the AppX interfaces (named __X), type-safety will be ensured as long as the user does not explicitly deactivate annotation processing (which I would qualified as malicious/intentional in the same sense as my specially crafted counter-examples).

jdegoes · 2016-07-09T16:22:01Z

OK, I'm not going to claim it's pretty... 😆

public class Test {
  public static void main(String[] args) {
    String result = OptionModule.inject(new OptionConsumer<String>() {
      public <OptionF> String consume(OptionModule<OptionF> provider) {
        Option<Integer> answer = Option.some(42);

        App<OptionF, Integer> answerF = provider.fromOption(answer);

        App<OptionF, String> answer2 = provider.functor().map(new Function<Integer, String>() { public String apply(Integer i) { return i.toString(); } }, answerF);

        return provider.toOption(answer2).getOrElse("");
      }
    });

    System.out.println(result);
  }
}

interface Function<A, B> {
  B apply(A a);
}

abstract class Option<A> {
  private Option() { }

  public A getOrElse(A def) {
    return fold(def, new Function<A, A>() { public A apply(A a) { return a; } });
  }

  public static <A> Option<A> none() { 
    return new Option<A>() {
      public <Z> Z fold(Z none, Function<A, Z> some) {
        return none;
      }
    };
  }

  public static <A> Option<A> some(A a) { 
    return new Option<A>() {
      public <Z> Z fold(Z none, Function<A, Z> some) {
        return some.apply(a);
      }
    };
  }

  public abstract <Z> Z fold(Z none, Function<A, Z> some);
}

interface App<F, A> { }

interface Functor<F> {
  <A, B> App<F, B> map(Function<A, B> f, App<F, A> fa);
}

interface OptionConsumer<Z> {
  <OptionF> Z consume(OptionModule<OptionF> provider);
}

class OptionModule<OptionF> {
  private OptionModule() { }

  public <A> App<OptionF, A> fromOption(Option<A> v) {
    return new AppOption<A>(v);
  }

  public <A> Option<A> toOption(App<OptionF, A> v) {
    return (((AppOption<A>)v).value);
  }

  public Functor<OptionF> functor() {
    return new Functor<OptionF>() {
      public <A, B> App<OptionF, B> map(Function<A, B> f, App<OptionF, A> fa) {
        Option<A> o1 = toOption(fa);
        return fromOption(o1.fold(Option.none(), new Function<A, Option<B>>() { public Option<B> apply(A a) { return Option.some(f.apply(a)); } }));
      }
    };
  }

  public static <Z> Z inject(OptionConsumer<Z> consumer) {
    return consumer.consume(new OptionModule<OptionFTag>());
  }

  private class AppOption<A> implements App<OptionF, A> {
    public final Option<A> value;

    AppOption(Option<A> value) {
      this.value = value;
    }
  }

  private static class OptionFTag { private OptionFTag() { } }
}

TomasMikula · 2016-07-09T18:19:18Z

@jbgi I never meant to suggest anyone should use that, it is really obscure. I was just trying if I could make it safe. I find @jdegoes's solution much cleaner (no F-bounds), although all the client code has to be written as a consumer of OptionModule.

jbgi · 2016-07-09T19:15:32Z

@jdegoes, this one was easy 😄

  public static void main(String[] args) {
    OptionModule.inject(new OptionConsumer<String>() {
      public <OptionF> String consume(OptionModule<OptionF> provider) {
        provider.toOption(new App<OptionF, String>() {}); // ClassCastException
        return "";
      }
    });
  }

jbgi · 2016-07-09T19:17:38Z

@TomasMikula even if it is obscure, if that does not impact client code and code can be generated it could have been a good solution.

jdegoes · 2016-07-09T20:24:19Z

A simple modification renders the original "safe up to null", again:

class Option<A> {
  protected Option() { }
}
abstract class App<F, A> {
  protected F proof();
}
class OptionF  {
  private OptionF() {}

  private static class AppOption<A> extends App<OptionF, A> {
    public final Option<A> value;

    AppOption(Option<A> value) {
      this.value = value;
    }

    protected OptionF proof() {
      return new OptionF();
    }
  }

  public static <A> App<OptionF, A> fromOption(Option<A> v) {
    return new AppOption(v);
  }

  public static <A> Option<A> toOption(App<OptionF, A> v) {
    return (((AppOption<A>)v).value);
  }
}
interface Function<A, B> {
  B apply(A a);
}
interface Functor<F> {
  <A, B> App<F, B> map(Function<A, B> f, App<F, A> fa);
}

jbgi · 2016-07-09T20:33:54Z

@jdegoes, I don't think so. My original counter-example still produce a ClassCastException:
https://gist.github.com/jdegoes/6842d471e7b8849f90d5bb5644ecb3b2#gistcomment-1818237

jdegoes · 2016-07-09T21:31:47Z

Damn access methods. If only Java had protected[this]! Or an abstract private method that could be implemented and seen only by subclasses...

jdegoes/HigherKindedJava.java

TomasMikula commented Jul 8, 2016

Uh oh!

jbgi commented Jul 8, 2016

Uh oh!

jdegoes commented Jul 8, 2016

Uh oh!

TomasMikula commented Jul 8, 2016

Uh oh!

jbgi commented Jul 8, 2016

Uh oh!

TomasMikula commented Jul 8, 2016

Uh oh!

jbgi commented Jul 9, 2016 •

edited

Loading

Uh oh!

jdegoes commented Jul 9, 2016

Uh oh!

TomasMikula commented Jul 9, 2016

Uh oh!

jbgi commented Jul 9, 2016

Uh oh!

jbgi commented Jul 9, 2016

Uh oh!

jdegoes commented Jul 9, 2016

Uh oh!

jbgi commented Jul 9, 2016

Uh oh!

jdegoes commented Jul 9, 2016

Uh oh!

	class Option<A> {
	protected Option() { }
	}
	interface App<F, A> {
	F proof();
	}
	class OptionF {
	private OptionF() {}

	private static class AppOption<A> implements App<OptionF, A> {
	public final Option<A> value;

	AppOption(Option<A> value) {
	this.value = value;
	}

	public OptionF proof() {
	return new OptionF();
	}
	}

	public static <A> App<OptionF, A> fromOption(Option<A> v) {
	return new AppOption(v);
	}

	public static <A> Option<A> toOption(App<OptionF, A> v) {
	return (((AppOption<A>)v).value);
	}
	}
	interface Function<A, B> {
	B apply(A a);
	}
	interface Functor<F> {
	<A, B> App<F, B> map(Function<A, B> f, App<F, A> fa);
	}

jdegoes/HigherKindedJava.java

TomasMikula commented Jul 8, 2016

Uh oh!

jbgi commented Jul 8, 2016

Uh oh!

jdegoes commented Jul 8, 2016

Uh oh!

TomasMikula commented Jul 8, 2016

Uh oh!

jbgi commented Jul 8, 2016

Uh oh!

TomasMikula commented Jul 8, 2016

Uh oh!

jbgi commented Jul 9, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jdegoes commented Jul 9, 2016

Uh oh!

TomasMikula commented Jul 9, 2016

Uh oh!

jbgi commented Jul 9, 2016

Uh oh!

jbgi commented Jul 9, 2016

Uh oh!

jdegoes commented Jul 9, 2016

Uh oh!

jbgi commented Jul 9, 2016

Uh oh!

jdegoes commented Jul 9, 2016

Uh oh!

jbgi commented Jul 9, 2016 •

edited

Loading