Generic Programming Must Go(youtube.com)
youtube.com
Generic Programming Must Go
https://www.youtube.com/watch?v=mCrVYYlFTrA
2 comments
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:
-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
- 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.