1 module erasure; 2 import std.meta; 3 import std.traits; 4 import std.conv : to; 5 6 /++ 7 + Substitute σx into σ, replacing all type variables with name $(B x). 8 + This function is primarily used by Π's specialize function. 9 + Structs and Classes can implement $(B SubstituteImpl(σx, x)) to allow specialization. 10 +/ 11 template Substitute(σx, string x, σ) 12 { 13 static if (staticIndexOf!(σ, Primatives) != -1) 14 { 15 alias Substitute = σ; 16 } 17 else static if (isArray!σ || isAssociativeArray!σ || isFunctionPointer!σ || isDelegate!σ) 18 { 19 alias Substitute = SubstituteNative!(σx, x, σ); 20 } 21 else static if (isPointer!σ) 22 { 23 alias Substitute = Substitute!(σx, x, PointerTarget!σ)*; 24 } 25 else static if (hasMember!(σ, "SubstituteImpl") && !isPointer!σ) 26 { 27 alias Substitute = σ.SubstituteImpl!(σx, x); 28 } 29 else 30 { 31 // assume σ doesn't contain any free variables by default 32 alias Substitute = σ; 33 } 34 } 35 36 /// 37 unittest 38 { 39 static assert(is(Substitute!(Object, "x", α!("x")*) == Object*)); 40 static assert(is(Substitute!(Object, "x", 41 α!("x") function(α!("x"))) == Object function(Object))); 42 } 43 44 private alias Primatives = AliasSeq!(void, bool, byte, ubyte, short, ushort, 45 int, uint, long, ulong, float, double, real, ifloat, idouble, ireal, 46 cfloat, cdouble, creal, char, wchar, dchar); 47 48 private template SubstituteNative(σx, string x, _: 49 τ[], τ) 50 { 51 alias SubstituteNative = Substitute!(σx, x, τ)[]; 52 } 53 54 private template SubstituteNative(σx, string x, _: 55 τ[σ], τ, σ) 56 { 57 alias SubstituteNative = Substitute!(σx, x, τ)[Substitute!(σx, x, σ)]; 58 } 59 60 private template SubstituteNative(σx, string x, _: 61 τ function(σ), τ, σ...) 62 { 63 alias SubstituteNative = Substitute!(σx, x, τ) function( 64 staticMap!(SubstituteCurry!(σx, x), σ)); 65 } 66 67 private template SubstituteNative(σx, string x, _: 68 τ delegate(σ), τ, σ...) 69 { 70 alias SubstituteNative = Substitute!(σx, x, τ) delegate( 71 staticMap!(SubstituteCurry!(σx, x), σ)); 72 } 73 74 private template SubstituteCurry(σx, string x) 75 { 76 alias SubstituteCurry(σ) = Substitute!(σx, x, σ); 77 } 78 79 /++ 80 + A Type Variable is a representation of an unknown type. 81 + The only known property about a type variable is it's size $(B κ). 82 + Two type variables with different names represent two different incompatible types. 83 + Functions that use unbounded type variables should always be private and wrap said function with a forall type. 84 +/ 85 struct α(string x, size_t κ = Object.sizeof) 86 { 87 private void[κ] get; 88 89 template SubstituteImpl(σx, string x2) 90 { 91 static if (x == x2) 92 { 93 static assert(σx.sizeof == κ, 94 "Kind mismatch: size of " ~ σx.stringof ~ " is not " ~ κ.to!string); 95 alias SubstituteImpl = σx; 96 } 97 else 98 { 99 alias SubstituteImpl = typeof(this); 100 } 101 } 102 103 static assert(typeof(this).sizeof == κ); 104 } 105 106 /++ 107 + Forall types (called "∀" is system-f) binds a type variable $(B x) in a type $(B σ). 108 + Forall's purpose is represent a type that can be specialized to something else. 109 --- 110 // this can be read as 111 // forall types "x", x function(x) 112 Π!("x", α!("x") function α!("x")) 113 --- 114 +/ 115 struct Π(string x, σ) 116 { 117 private σ get; 118 119 /++ 120 + A forall type can be specialized into any type that has the same size as the bound type variable $(B x) in $(B σ) including other type variables. 121 +/ 122 Substitute!(σx, x, σ) specialize(σx)() 123 { 124 return *cast(Substitute!(σx, x, σ)*)(&get); 125 } 126 127 template SubstituteImpl(σx, string x2) 128 { 129 static if (x == x2) 130 { 131 alias SubstituteImpl = Π!(x, σ); 132 } 133 else 134 { 135 alias SubstituteImpl = Π!(x, Substitute!(σx, x2, σ)); 136 } 137 } 138 } 139 140 /++ 141 + A type lambda takes a value with a free type variable $(B x) and binds it inside a Forall type. 142 +/ 143 template Λ(string x) 144 { 145 /// 146 Π!(x, σ) Λ(σ)(σ bound) 147 { 148 return Π!(x, σ)(bound); 149 } 150 } 151 152 /// 153 unittest 154 { 155 // this can be read as 156 // forall types "a", such that "a" has the same size of int. x is a value of type a* 157 Π!("a", α!("a", int.sizeof)*) x = Λ!("a")(cast(α!("a", int.sizeof)*) null); 158 assert(x.specialize!(int)() == null); 159 assert(x.specialize!(float)() == null); 160 } 161 162 /++ 163 + N arity type lambda. 164 +/ 165 template Λ(string x, string y, xs...) 166 { 167 auto Λ(σ)(σ bound) 168 { 169 return .Λ!x(.Λ!(y, xs)(bound)); 170 } 171 } 172 173 /++ 174 + Helper mixin template wrapping functions in a foralls. 175 + Given a template $(B symbol), a list a type variables $(B Variables), and a name $(name), this mixin generates two symobls $(B underscore ~ name) and $(B name). 176 + Where $(B underscore ~ name) is a private symbol with free variables and $(B name) is the former wrapped in a forall type. 177 --- 178 // generic identity function in idiomatic D 179 A identityGeneric(A)(A x) 180 { 181 return x; 182 } 183 184 // generate the symbol "_identityPtr" and the "identityPtr" wrapper 185 mixin Erasure!(identityGeneric, "identityPtr", α!("A", (void*).sizeof)); 186 187 // redefine for clearity 188 enum Π!("A", α!("A", (void*).sizeof) function(α!("A", (void*).sizeof))) identity = identityPtr; 189 190 // usage 191 unittest 192 { 193 int* x = new int(1); 194 assert(*identity.specialize!(int*)()(x) == 1); 195 } 196 --- 197 +/ 198 mixin template Erasure(alias symbol, string name, Variables...) 199 { 200 alias impl = symbol!Variables; 201 alias R = ReturnType!impl; 202 alias A = Parameters!impl; 203 204 mixin(q{ private R } ~ "_" ~ name ~ q{(A args){ 205 return impl(args); 206 }}); 207 208 mixin(q{enum } ~ name ~ q{ = Λ!(staticMap!(αName, Variables))(&} ~ "_" ~ name ~ q{);}); 209 } 210 211 version (unittest) 212 { 213 // generic identity function in idiomatic D 214 A identityGeneric(A)(A x) 215 { 216 return x; 217 } 218 219 // generate the symbol "_identityPtr" and the "identityPtr" wrapper 220 mixin Erasure!(identityGeneric, "identityPtr", α!("A", (void*).sizeof)); 221 222 // redefine for clearity 223 enum Π!("A", α!("A", (void*).sizeof) function(α!("A", (void*).sizeof))) identity = identityPtr; 224 225 // usage 226 unittest 227 { 228 int* x = new int(1); 229 assert(*identity.specialize!(int*)()(x) == 1); 230 } 231 232 auto pickLeft(A, B)(A x, B y) 233 { 234 return x; 235 } 236 237 mixin Erasure!(pickLeft, "pickLeftObj", α!("A"), α!("B")); 238 239 unittest 240 { 241 import std.range; 242 import std.algorithm; 243 244 InputRange!int range = pickLeftObj.specialize!(InputRange!int) 245 .specialize!(InputRange!char)()(inputRangeObject(iota(0, 10)), null); 246 assert(equal(range, iota(0, 10))); 247 } 248 } 249 250 private template αName(σ : α!(x, κ), string x, size_t κ) 251 { 252 enum αName = x; 253 }