[swift-evolution] [Proposal] Higher Kinded Types (Monads, Functors, etc.)

[Jens Persson]

I've been bumping into (what I've found out to be) the need for HKT a lot
while trying to write highly composable yet optimizable code for
exploratory image (and audio (and video)) processing.

Using Core Image, vImage, vDSP, Metal, etc. directly is not an option here,
since they are much too low level / specialized / non-composable. What I'm
writing is a system that will let me try out new ideas very quickly by
reusing as much code and concepts as possible. Ie I don't want to write
specialized code for every slight variant of a concept. So a separable
convolution should be _one_ generic implementation, and the compiler (not
the programmer) should take care of specializing it for any given value
type and dimensionality, same thing with positions, a position in space is
no different from a position in a color space or a position in space&time,
so they should share a common implementation. I need it to be as
optimizable as possible, because it would be unusable even for just
experimentation otherwise. If something needs to get faster still, we can
then write a Metal version of it.

With the latest improvements in the optimizer (esp. loop unrolling) I have
managed to get the basics of this working, the compiler will generate SIMD
code from my high level code constructs (when possible of course, eg when
doing separable convolution (in any number of dimensions) and the
components are 4 or 4x4 Floats etc).

But I currently have to jump through hoops in order to write simple things
like "static array types" with type-level count and specific memory
footprint. I'm using Peano-esque natural-numbers-as-types for the Count,
and a similar nested-structs-thing to get the proper storage of Count x
Element. But it is impossible to parameterize them for both Count and
Element, so I have to do eg this:

typealias MyFloat4 = StaticArrayOf<Float>.WithCount4

instead of the more straight forward:

typealias MyFloat4 = StaticArray<Float, Count4>

So I wish it was possible to implement it like this:
struct StaticArray<Element, Count> { ... }
where
strideof(StaticArray<Float, Count4>) == 4 * strideof(Float) ==
strideof(float4)

But I've given up and accepted that such parameterization is not possible
without HKT.

Perhaps it would become possible with the proposed generic typealiases, at
least if that implied generic associated types (which I guess would be the
same as HKT?).

Anyway, I'm very impressed by (open source master) Swift's ability to
optimize very high level generic code. I just wish some of my abstractions
could be written in a more straight forward way. I think HKT would make
them simpler. (Sorry for not being more specific).

/Jens



On Thu, Dec 17, 2015 at 6:22 AM, Matthew Johnson via swift-evolution <
swift-evolution at swift.org> wrote:

> > Looking beyond functional programming abstractions, higher-kinded types
> are a fancy way of saying "template template parameters”.
>
> Thanks for bringing that up.  I almost mentioned it.  I didn’t because I
> know the Swift team wants to avoid a lot of what has been done with
> templates and am not sure exactly where you draw the line.  :)
>
> > A textbook motivation for those from C++ land is Andrei Alexandrescu's
> "policy pattern", stuff like this:
> >
> > protocol RefStoragePolicy: <*: class> {
> >  typealias Ref: class
> >  init(ref: Ref)
> >  var ref: Ref
> > }
> >
> > struct Weak<T: class>: RefStoragePolicy { weak var ref: T }
> > struct Unowned<T: class>: RefStoragePolicy { unowned var ref: T }
> > struct Strong<T: class>: RefStoragePolicy { var ref: T }
> >
> > class HeterogeneousRefConsumer<Storage: RefStoragePolicy> {
> >  func consumeRef<T: class>(ref: T) {
> >    let storage = Storage<T>(ref: ref)
> >    doStuffWith(storage)
> >  }
> > }
> >
> > -Joe
> > _______________________________________________
> > swift-evolution mailing list
> > swift-evolution at swift.org
> > https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>



-- 
bitCycle AB | Smedjegatan 12 | 742 32 Östhammar | Sweden
http://www.bitcycle.com/
Phone: +46-73-753 24 62
E-mail: jens at bitcycle.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151217/c5a535e8/attachment.html>