Specializing values in a functional language

Assume a Haskell-like language. Say you have a value of an unknown (abstract) type, but you know it is either an integer, a string, or a tree node.

Are there (/have there been) extensions to Haskell that you can safely inspect and specialize the type of that given value?

A couple of solutions

One standard solution in languages like ML and Haskell is to create your own ADT over the universe of expected types

Here's Haskell

data Univ = UnInt Int | UnString String | UnTree Tree

Then you can write functions over your universe

f :: Univ -> String
f (UnInt n) =  "It's an int " ++ (show n)
f (UnString s) = "It's a string " ++ s
f (UnTree t) = "It's a tree with " ++ (show $ height t) ++ " levels"

The ADT solution guarantees you won't try to use a float on a function that can't handle it.

To call it you have to package up the value, e.g.
f $ UnString "hello".

To make packaging easier, in Haskell you can add a type class

class Univ' a where
  package :: a -> Univ

instance Univ' String where
  package s = UnString s

instance Univ' Int where
  package n = UnInt n

instance Univ' Tree where
  package t = UnTree t

g :: Univ' a => a -> String
g = f . package

So now g does what f does, but you can call it simply with 'g 3' or 'g "hello"'.

If the ADT approach isn't to your liking, then if a language has subtyping (not necessarily subclassing!) and a top type then a universe is built in. Unfortunately, there's no way to be exhaustive over that universe using pattern matching. Here's Scala

f(a:Any) : String = a match {
  case n : Int => "It's an int " + n
  case s : String => "It's a string " + s
  case t : Tree => "It's a tree with " + t.height + " levels"
}

This version of f can take a value of any type, but will throw a match exception for anything but an Int, String, or Tree.

Note that Scala can also do the ADT solution (a bit more verbosely) and implicit conversions can allow you to not explicitly package values up into the Univ type, although the mechanism is a bit different from Haskell's type classes.

By James Iry at Tue, 2008-09-23 15:50 | login or register to post comments

Thanks

I am going for the Scala approach.

[del this remark, different cases: Since I need a case construct anyway to compile pattern matching, I might as well introduce it as a language construct.]

By marco at Tue, 2008-09-23 17:03 | login or register to post comments

Data.Typeable sounds close

Data.Typeable sounds close to what you want. You might also look at the Scrap your boilerplate papers.

By Matt M at Tue, 2008-09-23 16:08 | login or register to post comments

GHC's Specialize Pragma

There is the GHC Pragma {-# SPECIALIZE function :: type #-}

It will ensure that an extra copy of the function, specialized to that type, is created. Specialization might enable more optimizations: notably, GHC can then eliminate the indirect function calls associated with type classes.

By Leon P Smith at Wed, 2008-09-24 03:54 | login or register to post comments

Why is not a primitive of the language?

I wonder. Scala-like specialization (see above post) would be easy enough to implement in Haskell, and from OO programming we now it is just a very nice-to-have feature.

By marco at Wed, 2008-09-24 11:31 | login or register to post comments

Subtyping

Haskell's type system is closely based on Hindly-Milner. HM has the nice property that all programs can be fully inferred - in Haskell most programs can be mostly inferred.

Simon Peyton Jones has commented that as Haskell's type system has expanded it has moved to a knife's edge where just one more tiny feature can turn it around where most programs must mostly be type annotated. Subtyping is not a tiny feature to add to a type system, and indeed Martin Odersky has said that it's a major reason for Scala's limitations in type inference.

Subtyping can also creates a real challenge for type safety. As I alluded above, if a user can add subtypes then pattern matching on subtypes can't be shown exhaustive without whole program analysis. Pattern matches on closed ADTs, on the other hand, are easy to prove exhaustive.

Also, Leon is talking about functions being specialized for polymorpic types which is a different thing altogether. Scala doesn't do that as far as I know.

By James Iry at Wed, 2008-09-24 12:49 | login or register to post comments

Doesn't break subtyping

The Scala manner of specializing doesn't break subtyping or type inference in any way. One just can add a rule that a type-match case construct can take any type (and return the intersection of the rewrite).

The exhaustiveness check is not needed if you just add a default rule (if no types match then do this). (Stated differently: I could accept doing without the exhaustiveness check; I guess this is just a way of thinking which goes against Haskell's "check-as-much-as-you-can" philosophy).

I see the problem with polymorphic types since you would need to pass around RTTI. You are right, guess that is it.

By marco at Wed, 2008-09-24 14:08 | login or register to post comments

Miscommunication

The Scala manner of specializing doesn't break subtyping or type inference in any way

I think we misunderstood each other. I thought you were asking why Haskell doesn't have Scala style matching based on subtyping. In Scala, I can write a function that takes an argument of any specific type and then pattern match on on its subtypes. As such, I was saying that Haskell doesn't do that because it doesn't have subtypes.

If I understand you correctly, you're not proposing full subtyping - you just want one special top type to mean "the unknown type" and some way to dispatch based on a value's known type. In that case, you're right, there is no technical reason why a Haskell like language couldn't have such a thing built-in by doing the equivalent of always deriving Data.Typeable plus generating RTTI for functions.

The exhaustiveness check is not needed if you just add a default rule

Indeed, but the default rule that would most often be used is to throw an error, so requiring it is not terribly useful.

I see the problem with polymorphic types since you would need to pass around RTTI. You are right, guess that is it.

In fact, in Scala that is a problem because type parameters are erased from RTTI. So you can't write

def foo(l : List[_]) : String = l match {
   case _ : List[String] => "strings"
   case _ : List[Int] => "integers"
   case _ : List[Tree] => "trees"
}

By James Iry at Wed, 2008-09-24 16:22 | login or register to post comments

Lambda the Ultimate

User login

Navigation