3 ms·

Generic Programming Must Go

15 points by jacques_chirac 11y ago

p0nce 11y ago
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.
eutectic 11y ago
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

p0nce 11y ago

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.

eutectic 11y ago

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