Generalize ?. and []. operators / generic map operation.
Gavin King
and T[] respectively. Now, really, these are just special cases of an
operation that makes sense for any type with the metatype Functor. We
could instead have just one symbol to represent this, say, *. or ^.
Then xs*.y would be defined as
F.map(X.y)(xs)
Where xs is an instance of F<X> for some type constructor F with the
metatype Functor. So this has got me paying proper attention to the
problem of how to represent Functors in Ceylon, i.e. and how to define
a polymorphic map() function that works for optional types, sequences,
collections, trees, etc. (The purpose of this would be to be able to
abstract over all type constructors which can be map()ed.)
There are a couple of issues with trying to do this generalization in
the current language:
0) We don't have metatypes yet.
1) We can't define metatypes for a union type, so the type
constructors ? and [] can't be functors.
2) Without type constructor parametrization, I don't think it's
possible to represent Functor as a metatype.
Actually, if I'm understanding my Haskell correctly - and I might not
be - a Functor is represented in Haskell as a type class that applies
to a higher kind. (i.e. in our terminology, a metatype of a type
constructor.)
Now, I believe I can encode the notion of a functor into our type
system like this:
Functor<F<T>X> {
F<Y> map<Y>(Y f(X x))(F<X> x);
}
(Assuming support for type constructor parametrization.)
Then a List type would be a functor as follows:
interface List<X> is Functor<List,X> ....
The difference between this and the Haskell definition is that in
Haskell the type parameter X would be a parameter of map(), not of
Functor. (I haven't yet thought this through far enough to decide how
serious a limitation of our type system this is.)
So the point of all this is that without the introduction of type
constructor parametrization and a metatype system somewhat more
flexible than what I have written down today, we would not be able to
define the *. operator without resort to overloading, nor would we be
able to define a single polymorphic map() operation, and therefore we
would not be able to abstract over types that can be map()ed. The FP
folks won't love that.
--
Gavin King
gavin...@gmail.com
http://in.relation.to/Bloggers/Gavin
http://hibernate.org
http://seamframework.org
Gavin King
for optional and sequence types:
//a higher-kinded interface defining the metatype
interface Functor<F<T>,X> {
shared F<Y> map<Y>(Y f(X x))(F<X> fx);
}
//a type alias for T?
shared type Optional<T> = Nothing|T; //i.e. T?
//an interface that introduces a metatype
//to Type<T?>
shared interface OptionalFunctor<T>
adapts Type<Optional<T>>
satisfies Functor<Optional,T> {
shared actual Y? map(Y f(X x))(X? x) {
if (exists x) {
return f(x);
}
else {
return null;
}
}
}
//a type alias for T[]
shared type Seq<T> = Empty|Sequence<T>; //i.e. T[]
//an interface that introduces a metatype
//to Type<T[]>
shared interface SeqFunctor<T>
adapts Type<Seq<T>>
satisfies Functor<Seq,T> {
shared actual Y[] map(Y f(X x))(X[] xs) {
variable Y[] result := {};
for (x in xs) {
result = result.append(f(x));
}
return result;
}
}
So the "total" list of languages features that I need is:
1) type constructor parametrization
2) type aliases for union types
3) the ability to (like in a generalized algebraic type) parametrize
such a type by a parameter that does not appear in all cases of the
union
4) metatypes for these union types aliases
5) the ability to introduce a metatype
That's a reasonable slab of functionality, but notice that it's all
pretty consistent with stuff we've already speculated that we might
need.
Stephane Epardaud
1/ I don't get the feeling that "map" should work on optional types, I
understand it's similar in concept to a sequence of 0 or 1 size, but
"map" is about taking lists and returning lists. I'm not sure other FP
languages will have "map" be defined as returning something else than
a sequence (not in Scheme in any case).
2/ If we can have "Nothing|Empty|Sequence<X> foo;" then (whether now
with ?. and *. or with your proposal) how do we "map" over it?
"foo?*.x" ?
3/ Enabling overriding of those operators means that we'll lose the
ability to optimise them properly in the compiler because they are
defined on types that can be subclassed (Object? or Sequence)
4/ Do we really want to allow overriding of those operators?
5/ "?." is a pretty common operator nowadays, "*." less so I think and
starts looking a bit complex (and reeks of multiplication). "[]." was
a bit more intuirive (if more verbose) in my opinion.
6/ A Real Man's "map" is defined as such
(http://www.cs.bham.ac.uk/research/projects/poplog/paradigms_lectures/lecture5.html#map):
(map f e1 ... en)
where:
- f is a function of n arguments,
- ei to en are lists of the same length,
- the result is a list each of whose members is obtained by applying f
successively to the members of the lists ei to en.
So for example:
(map + (list 1 2 3) (list 4 5 6)) == (list (+ 1 4) (+ 2 5) (+ 3 6)) ==
(list 5 7 9)
So FP guys will mock us anyways because this can't be mapped easily to
a Sequence type ;)
7/ The compiler can implement the current version of "?." and "[]." as
it is defined right now, for M1, without all this.
Gavin King
<stephane...@gmail.com> wrote:
> 1/ I don't get the feeling that "map" should work on optional types, I
> understand it's similar in concept to a sequence of 0 or 1 size, but
> "map" is about taking lists and returning lists. I'm not sure other FP
> languages will have "map" be defined as returning something else than
> a sequence (not in Scheme in any case).
In Haskell, Maybe is not only a Functor but even a Monad. You can fmap() it.
> 2/ If we can have "Nothing|Empty|Sequence<X> foo;" then (whether now
> with ?. and *. or with your proposal) how do we "map" over it?
> "foo?*.x" ?
Good question.
> 3/ Enabling overriding of those operators means that we'll lose the
> ability to optimise them properly in the compiler because they are
> defined on types that can be subclassed (Object? or Sequence)
Does it? I don't think so.
> 4/ Do we really want to allow overriding of those operators?
That's an interesting question, but even if we don't, we still might
want to be able to abstract over map().
> 5/ "?." is a pretty common operator nowadays, "*." less so I think and
> starts looking a bit complex (and reeks of multiplication). "[]." was
> a bit more intuirive (if more verbose) in my opinion.
Agreed.
> 7/ The compiler can implement the current version of "?." and "[]." as
> it is defined right now, for M1, without all this.
Sure, but the question isn't really about M1, it's about what is the
future direction.
Gavin King
> I am trying to decide whether to invest my effort in Ceylon or Scala.
> Scala has higher kinds but not first intersection and union types.
> Ceylon vice versa.
>
> I want to impress upon the Ceylon developers how important higher
> kinds are.
>
> Also I want to ask how serious is Ceylon about implementing higher
> kinds and in what calendar year is implementation currently projected?
Hi Shelby,
Unfortunately, I'm going to have to give the same kinda unhelpful
answer I've been giving:
I personally like the idea of being able to parameterize an operation
(or even a type) by a type constructor. Clearly there's some things
that simply can't be expressed without type constructor
parameterization. However:
1. Right now we're killing ourselves trying to get a 1.0 release ready
for later this year, and we still have a lot of work to go on that,
especially since we have barely started work on the SDK. We simply
don't have the bandwidth to work on this right now.
2. While a simple thing to understand conceptually, support for kinds
seems to me to be something that would dramatically complexify the
specification and typechecker. All of a sudden we will have things
floating around which are neither values nor types. And we have not
even started to ask ourselves about the decidability issues connected
with this feature.
So, while I think it's quite likely that Ceylon will someday support
this feature, and that it will indeed fit quite naturally into the
language, both syntactically and philosophically, it won't be a
feature of Ceylon 1.0.
http://ceylon-lang.org
http://hibernate.org
http://seamframework.org
Shelby
Scala has higher kinds but not first intersection and union types.
Ceylon vice versa.
I want to impress upon the Ceylon developers how important higher
kinds are.
Also I want to ask how serious is Ceylon about implementing higher
kinds and in what calendar year is implementation currently projected?
> nor would we be
> able to define a single polymorphic map() operation, and therefore we
> would not be able to abstract over types that can be map()ed.
generality of higher-order abstractions is extensive and very
powerful. And because this is backed up by sound category theory,
there are not unforeseen corner cases lurking (as is the case with
other standard library designs such as Scala's).
Functor enables reuse of any arity 1 function on parametrized types
(collections, etc):
// Functional programming (FP) paradigms are fundamentally about not
repeating oneself.
//
// Functor enables the reuse of all functions of type, T -> A,
// i.e. functions which input a type T and return a type A,
// without requiring specialized versions of functions of type, Sub<T>
-> Sub<A>.
//
// For example, if List<T> is a functor, then a function of type, Int -
> String,
// can convert a List<Int> into a List<String>.
// There is no need to create a specialized morphism function of type,
List<Int> -> List<String>.
Applicative enables reuse any function of any arity on parametrized
types (collections, etc):
// Unlike Functor.map, Applicative.<- inputs the function lifted to an
Applicative,
// e.g. Sub<T -> B -> C>, instead of an unlifted function, e.g. T -> B
-> C,
// so that any number of multiple Applicative.<- can be chained,
// so functions with N number of input parameters can be lifted
// to a function that inputs N number of Applicative.
//
// For example, applying Sub<T>.<-( Sub<T -> B -> C> ) outputs Sub<B -
> C>,
// then applying Sub<B>.<-( Sub<B -> C> ) outputs Sub<C>.
//
// DETAILS:
//
// Without the such a model, the equivalent code is excessively
verbose
// and must be specialized for each subtype, as shown in examples
below, and also at this link:
// http://en.wikibooks.org/wiki/Haskell/Applicative_Functors#Using_Applicative_Functors
//
// For example, given a morphism function of type, Int -> Int -> Int -
> Int:
// f( Int a, Int b, Int c ) = a + (b * c)
// Apply this function to 3 lists, List( 1, 2, 3 ), List( 10 ),
List( 6, 7 ), as follows:
// List( 1, 2, 3 ).<-( List( 10 ).<-( List( 6, 7 ).<-
( List( f ) )))
// The Applicative.-> operator is left-associative and is called on
its right operand,
// so that the arguments of 'f' are placed in left-to-right order,
// as they would be in a normal function call of 'f':
// List( f ) <- List( 6, 7 ) <- List( 10 ) <- List( 1, 2, 3 )
// Or more efficiently, employing Functor.<-- (operator for
Function.map) as follows:
// List( 1, 2, 3 ).<-( List( 10 ).<-( List( 6, 7 ).<--(f) ))
// f <-- List( 6, 7 ) <- List( 10 ) <- List( 1, 2, 3 )
// The result is List( 16, 26, 36, 17, 27, 37 ).
//
// Each applicaion of Applicative.<- curries the function, f, with the
elements of the list:
// List.lift( f ) == List( f )
// List( 6, 7 ).<-( List( f ) ) == List( f(6), f(7) )
// List( 10 ).<-( List( f(6), f(7) ) ) == List( f(6)(10), f(7)
(10) )
// List( 1, 2, 3 ).<-( List( f(6)(10), f(7)(10) ) ) == List( f(6)
(10)(1), f(6)(10)(2), f(6)(10)(3), f(7)(10)(1), f(7)(10)(2), f(7)(10)
(3) )
// List( f(6)(10)(1), f(6)(10)(2), f(6)(10)(3), f(7)(10)(1), f(7)
(10)(2), f(7)(10)(3) ) == List( 16, 26, 36, 17, 27, 37 )
//
// f is a function of type Int -> Int -> Int -> Int
List( f ) is type List<Int -> Int -> Int ->
Int>
// f(6) is a curried function of type Int -> Int -> Int
List( f(6), f(7) ) is type List<Int -> Int -> Int>
// f(6)(10) or f(6,10) is a curried function of type Int -> Int
List( f(6)(10), f(7)(10) ) is type List<Int -> Int>
// f(6)(10)(1) or f(6,10,1) returns an Int with value 16
List( 16, 26, 36, 17, 27, 37 ) is type List<Int>
//
// The equivalent code without an Applicative model is:
// a = List( 6, 7 )
// b = List( 10 )
// c = List( 1, 2, 3 )
// result = List(
// f( a.head, b.head, c.head),
// f( a.head, b.head, c.tail.head),
// f( a.head, b.head, c.tail.tail.head)
// f( a.tail.head, b.head, c.head),
// f( a.tail.head, b.head, c.tail.head),
// f( a.tail.head, b.head, c.tail.tail.head) )
//
// The applicative model expresses the semantics more clearly:
// result = List( f ) <- List( 6, 7 ) <- List( 10 ) <- List( 1, 2,
3 )
// Or more efficiently:
// result = f <-- List( 6, 7 ) <- List( 10 ) <- List( 1, 2, 3 )
Monad enables composition of functions that return parametrized types
with those that don't:
http://blog.sigfpe.com/2006/06/monads-kleisli-arrows-comonads-and.html
// Monad.bind lifts morphism functions which input the unlifted and
return the lifted subtype, T -> Sub<A>,
// to Monad (subtype) morphisms, Sub<T> -> Sub<A>.
//
// This enables the composition of functions which return the Monad
subtype, see Monad.compose.
//
// RATIONALE:
//
// Functor.compose enables the composition of a function which returns
the Functor subtype, T -> Sub<A>,
// with a function that inputs and outputs unlifted types, A -> B.
//
// But Functor provides no means to compose two functions which both
return the Functor subtype,
// so we need Monad.compose to accomplish such composition without
boilerplate specific to each lifted subtype.
Traversable combines a Functor.map and Foldable.fold in a single pass
of the iteration, i.e. single walk of the contained T instances:
// If the called function, T -> Maybe<F<A>>, returns None, the
iteration terminates.
//
// Traversable.traverse can map and fold to any Applicative in a
single pass of the iteration.
//
// RATIONALE:
//
// The conceptual efficiency of combining two orthogonal operations in
a single pass of the iteration,
// can also be described as computing the Applicative<Traversable>,
instead of Traversable<Applicative>
// as Functor.map can do with the function, T -> F<A>, where F is an
Applicative
// and assuming the subtype, Sub<T>, of the Functor is also a
Traversable.
State monad threads the state, S, through the composition of functions
which do and do not operate on the encapsulated state.
// RATIONAL:
//
// Thus generally any kinds of orthogonal state can composed with any
functions that that don't operate on the encapsulated state,
// without case-specific boilerplate.
> The FP
> folks won't love that.
Ross Tate
Shelby Moore
understand that Haskell (type classes) can't do virtual inheritance of
implementation nor diamond multiple instance of interfaces:
http://copute.com/dev/docs/Copute/ref/Complete%20solutions%20to%20the%20%93Expression%20Problem.htm#8409828
This forces the duplicate implementation of many similar methods in the
Prelude (explosion of boilerplate).
Apparently the main benefit of this tradeoff is it enables global type
inherencing to be decidable, although this fails with some popular GHC
extensions (probably GADTs?):
http://stackoverflow.com/questions/7234095/why-is-scalas-type-inference-not-as-powerful-as-haskells/7234238#7234238
Scala and Ceylon don't support global type inferencing.
Do you mean decidability of the type inferencer? Or does the decidability
issue occur with type parameterization even if all the other concrete
types have been explicitly listed?
I was looking at some research today, which generalizes the decidability
of type systems.
Essense of Principle Typing:
http://lambda-the-ultimate.org/node/529
I am (still) trying to grasp that research paper, and for me the
introduction section of the following paper helped advance my
understanding.
Rank 2 Intersection Types for Modules:
http://www.di.unito.it/~damiani/papers/ppdp03.pdf
I can't probably more readily grasp code examples, than representations in
some abstract calculus.
Shelby
> implementation nor diamond multiple instance of interfaces:
> I can't probably more readily grasp code examples
Incidentally the creator of Scala was recently explained the
complexity and fragility of the implementation of higher-kinds:
http://groups.google.com/group/scala-language/msg/ff2536f0f0296ec8
"One particularly amusing twist is that this could in one fell sweep
eliminate what I consider the worst part of the Scala compiler. It
turns out that the internal representation of higher-kinded types in
the Scala compiler is the same as the internal representation of raw
types in Java (there are good reasons for both representation
choices). But raw types should map to existentials, not to
higher-kinded types. We therefore need to map Java raw types to Scala
existential types. The code that does this is probably the most
fragile and intricate part of the Scala compiler. There's basically
no
good way to do it without either forgetting some transformations or
accidentally tripping off cyclic reference errors."
The Scala standard library did not leverage higher-kinds (instead
favoring a builder approach which is starting to demonstrate corner
cases):
http://stackoverflow.com/questions/1722726/is-the-scala-2-8-collections-library-a-case-of-the-longest-suicide-note-in-hist/7397388#7397388
I am guessing that Martin was thus thinking higher-kinds are less
valuable, but it was pointed out to him that there is no currently
known way to abstract Functors without them:
http://groups.google.com/group/scala-language/msg/610bfa1772a2565a
The point I am making is that when you get into designing your
standard library, you may realize you need higher-kinds. Note, I do
not claim be an expert on this issue.
I will wax philosophical. It seems every 10 years or so, a new
mainstream language is born due to some fundamental need. For Java
around 2000, that was GC and the elimination of pointers (and all the
complexity and lack of safety). In the 1960s, we programmed in
numbers, 1970s assemblers added symbolics, 1980s C added functions,
static typing, implicit stack, etc, 1990s C++ added OOP, and 2010s the
maturing of dynamically typed multi-paradigm. Now we are headed to
statically typed multi-paradigm.
So the question is what is the major win feature of statically typed
multi-paradigm? I am thinking it is the higher-order abstractions from
category theory, and any other concept that has a generalized impact
on reuse and extensibility.