Generic Programming Must Go

My favourite talk from DConf 2015. It is about the tension in the compile-time realm between:

- static interfaces (C++ concepts, Rust traits, Haskell typeclasses... or whatever name they have in a particular language)

- and the more adhoc compile-time duck-typing (eg: D static if, C++ expression SFINAE). Alexandrescu is arguing for the latter being more useful.

I can only agree with him considering the sheer difficulty of making reusable generic code that squarely fits a problem domain.

Programmers interested in meta-programming and reuse would probably enjoy the talk.

All of the examples he shows fall into one of two classes:

-Check whether a type implements a method; if so, do that method.

-Check whether a type implements a method; if so, branch on the success / failure of that method.

Both of these examples can be implemented using interfaces with default implementations, in a way which avoids having to explicitly branch at every call-site. You have to rely on the compiler to do inlining, constant-folding and dead code elimination if you want the same performance as the method in the video, but it gives shorter (and arguably simpler) code and useful type signatures.

To-wit, here's a proof of concept in Haskell:

  import Debug.Trace                                                            
                                                                                
  data VoidPtr = VoidPtr | Null                                                 
                                                                                
  data WithDealloc = WithDealloc                                                
                                                                                
  data NoDealloc = NoDealloc                                                    
                                                                                
  class Allocator a where                                                       
    alloc :: a -> VoidPtr                                                       
    alignment :: a -> Int                                                       
                                                                                
  class Allocator a => Dealloc a where                                          
    dealloc :: a -> VoidPtr -> ()                                               
    dealloc _ _ = trace "dummy dealloc" ()                                      
                                                                                
  instance Allocator WithDealloc where                                          
    alloc _ = VoidPtr                                                           
    alignment _ = 0                                                             
                                                                                
  instance Dealloc WithDealloc where                                            
    dealloc _ _ = trace "specialized dealloc" ()                                
                                                                                
  instance Allocator NoDealloc where                                            
    alloc _ = VoidPtr                                                           
    alignment _ = 0                                                             
                                                                                
  class Allocator a => Owns a where                                             
    owns :: a -> VoidPtr -> Bool                                                
    owns _ _ = False                                                            
                                                                                
  data BackupAllocator a b = BackupAllocator a b                                
                                                                                
  instance (Allocator a, Allocator b) => Allocator (BackupAllocator a b) where  
    alloc (BackupAllocator a b) =                                               
      case x of                                                                 
        VoidPtr -> x                                                            
        Null -> alloc b                                                         
      where x = alloc a                                                         
    alignment (BackupAllocator a b) = min (alignment a) (alignment b)           
                                                                                
  instance (Owns a, Dealloc a, Dealloc b) => Dealloc (BackupAllocator a b) where
    dealloc (BackupAllocator p f) b                                             
      | p `owns` b = dealloc p b                                                
      | otherwise  = dealloc f b                                                
                                                                                
  instance Owns WithDealloc                                                     
  instance Owns NoDealloc                                                       
  instance Dealloc NoDealloc                                                    
                                                                                
  test = (a, b)                                                                 
    where a = dealloc (BackupAllocator WithDealloc NoDealloc) VoidPtr -- Dummy  
          b = dealloc (BackupAllocator NoDealloc WithDealloc) VoidPtr -- Specialized