Home

Generic Programming, Now!

Ralf Hinze and Andres Löh. Generic Programming, Now!. In Roland Backhouse, Jeremy Gibbons, Ralf Hinze and Johan Jeuring, editors, Spring School on Generic Programming, Lecture Notes in Computer Science. Springer-Verlag, 2006.

Tired of writing boilerplate code? Tired of repeating essentially the same function definition for lots of different data types? Datatype-generic programming promises to end these coding nightmares. In these lecture notes, we present the key abstractions of datatype-generic programming, give several applications, and provide an elegant embedding of generic programming into Haskell. The embedding builds on recent advances in type theory: generalised algebraic data types and open data types. We hope to convince you that generic programming is useful and that you can use generic programming techniques today!

Yes, more functional generic programming...

Open data types and open functions are discussed here, but I think this paper wasn't featured on the homepage before.

By Ehud Lamm at 2007-02-01 18:35 | Functional | other blogs | 7083 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

How about making typing completely implicit?

I wonder if it would be possible to make typing completely implicit, i.e. the programmer would not have to write down type declarations or data constructors, just functions. The compiler's job would be to infer if a particular function can be called with a particular value. Compile-time polymorphism would work by a best-fit approach.

For example, let's say we have a type Vector2 with (x, y) members and a type Vector3 with (x, y, z) members. For both types, a function length is defined that computes the length of the hypotenuse:

let Vector2 xval yval = [
    let x = xval
    let y = yval
]

let length v = sqrt v.x*v.x + v.y*v.y

let Vector3 xval yval zval = [
    let x = xval
    let y = yval
    let z = zval
]

let length v = sqrt v.x*v.x + v.y*v.y + v.z*v.z

If we had the following program:

let v1 = Vector2 20 10
let v2 = Vector3 20 10 5
let l1 = length v1
let l2 = length v2

Then perhaps a compiler could choose the appropriate function to call based on how much of a function's requirements is covered. In the above example, since 'v2' is of the form '(x, y, z)', the compiler would have to choose the 2nd version of 'length'.

By Achilleas Margaritis at Fri, 2007-02-02 10:58 | login or register to post comments

Haskell

data Vector2 = Vector2 Double Double

class Vector a where
    len :: a -> Double 
     
instance Vector Vector2 where
    len (Vector2 x y) = sqrt (x*x + y*y)

data Vector3 = Vector3 Double Double Double 

instance Vector Vector3 where
    len (Vector3 x y z) = sqrt (x*x + y*y + z*z)
        
main = do 
    let v1 = Vector2 20 10
    let v2 = Vector3 20 10 5
    let l1 = len v1
    let l2 = len v2
    print (l1,l2)

By Greg Buchholz at Fri, 2007-02-02 15:26 | login or register to post comments

Not exactly the same.

Not exactly the same...In Haskell, the programmer has to know about 'data', 'class' and 'instance'.

By Achilleas Margaritis at Fri, 2007-02-02 16:22 | login or register to post comments

Closer?

import Prelude hiding ((.),length)
(.) = flip ($)
x = (!! 0) 
y = (!! 1)
z = (!! 2)

vector2 xval yval = [
    let x = xval in x,
    let y = yval in y ]

vector3 xval yval zval = [
    let x = xval in x,
    let y = yval in y,
    let z = zval in z ]

length v@[_,_] = sqrt (v.x*v.x + v.y*v.y)

length v@[_,_,_] = sqrt (v.x*v.x + v.y*v.y + v.z*v.z)

main = do
    let v1 = vector2 20 10 
    let v2 = vector3 20 10 5 
    let l1 = length v1
    let l2 = length v2
    print (l1,l2)

By Greg Buchholz at Fri, 2007-02-02 17:26 | login or register to post comments

What language are you using for the code?

Can't quite put my finger on which language you are using, so I'll cheat and give an answer in Standard ML that bypasses the whole question of types and solves the immediate problem:

fun vector2 (x, y) = [x, y]
fun vector3 (x, y, z) = [x, y, z]

fun square x:real = x * x

fun vectorLength v = Math.sqrt(foldr op+ 0.0 (map square v))

val v1 = vector2(20.0, 10.0)
val v2 = vector3(20.0, 10.0, 5.0)
val l1 = vectorLength v1
val l2 = vectorLength v2

Or if you want to declare a type for vectors, we could have:

datatype Vector = Vector2 of real * real
                | Vector3 of real * real * real

fun vectorLength (Vector2(x, y))    = Math.sqrt(x*x + y*y)
  | vectorLength (Vector3(x, y, z)) = Math.sqrt(x*x + y*y + z*z)

val v1 = Vector2(20.0, 10.0)
val v2 = Vector3(20.0, 10.0, 5.0)
val l1 = vectorLength v1
val l2 = vectorLength v2

By Chris Rathman at Fri, 2007-02-02 16:24 | login or register to post comments

On further reflection...

...I think that the question of dispatch based on function overloading points to ad hoc polymorphism. Instead of figuring out how two distinct length functions might be appropriately called, the idea in Generic Programming is that there should be one length function that can handle the different types of vectors you throw at it. So although type classes can be used to get the effect as Greg has shown above, the question comes back of why we need two different length functions in the first place?

By Chris Rathman at Fri, 2007-02-02 23:34 | login or register to post comments