1 /** 2 Lightweight Modular Staging library for D langauge. 3 4 Popularization of dependency injection framework somehow shaded 5 the bigger and more general technique - staging and staged computation. 6 7 This library ractifies that omission for the D language. 8 9 10 Built with love based on the ideas in the paper: 11 12 Lightweight Modular Staging: A Pragmatic Approach to 13 Runtime Code Generation and Compiled DSLs 14 by Tiark Rompf and Martin Odersky. 15 16 The above paper and many other good ones by Scala team at EPFL 17 are here http://infoscience.epfl.ch/record/150347/files/gpce63-rompf.pdf. 18 19 20 Synopsis 21 22 --- 23 auto stage = new BasicStage(); 24 int[] trace; // our primitive trace buffer 25 auto v1 = stage.slot!double("var1").map(delegate double(double x) { 26 trace ~= 1; 27 return x; 28 }); 29 auto v2 = stage.slot!double("var2").map(delegate double(double x) { 30 trace ~= 2; 31 return x; 32 }); 33 stage["var1"] = lift(1.5); 34 auto part = (v1 + v2).partial(stage); 35 stage["var2"] = lift(-0.5); 36 // first pass - both map functions called once 37 assert(part.eval(stage) == 1.0); 38 assert(trace == [1, 2]); 39 40 // second pass - only v2 is evaluated 41 assert(part.eval(stage) == 1.0); 42 assert(trace == [1, 2, 2]); 43 --- 44 45 */ 46 47 module lms; 48 49 class Box { 50 // replace value of this box with another, may throw if cannot do that 51 void replace(Box another) { 52 throw new LmsException("Internal error - cannot replace contents of this lifted value"); 53 } 54 } 55 56 /// Lift a simple constant 57 Lift!T lift(T)(T value) 58 if (!is(T : Lift!U, U)){ 59 return new Constant!T(value); 60 } 61 62 /// ditto 63 Lift!T lift(T)(Lift!T lifted) { 64 return lifted; 65 } 66 67 /** 68 Stage is equivalent to DI container (or rather DI is simple late-binding + basic form of staging) 69 but the composition and execution of them is independent 70 and encapsulated by Lift!T interface 71 72 A user is expected to sub-class and define custom stages as needed. See also `BasicStage`. 73 */ 74 interface Stage { 75 /// Lift a placeholder - slot for concrete value to be filled in at a later stage 76 Slot!T slot(T)(string name) { 77 auto lifted = new Slot!T(name); 78 register(name, lifted); 79 return lifted; 80 } 81 82 /// Register existing slot at this _stage_ with name `name` 83 Slot!T slot(T)(string name, Slot!T value) { 84 register(name, value); 85 value.reset(); 86 return value; 87 } 88 89 /// Register existing slot at this _stage_ with original name 90 Slot!T slot(T)(Slot!T value) { 91 register(value.name, value); 92 value.reset(); 93 return value; 94 } 95 96 /// Try to evaluate (lower) lifted value using this stage 97 auto eval(T)(Lift!T value) { 98 return value.eval(this); 99 } 100 101 /// Do partial evaluation for lifted value, this folds all known-constant sub-tries and optimizes expressions 102 auto partial(U)(U value) 103 if (!is(U : Slot!T, T)) { 104 return value.partial(this); 105 } 106 107 ///ditto 108 auto partial(U)(U value) 109 if (is(U : Slot!T, T)) { 110 return cast(Lift!T)this[value]; 111 } 112 113 void register(T)(Slot!T slot) { 114 register(slot.name, typeid(T)); 115 } 116 117 /// This is an implementation hook - register must save name,typeinfo pair to check type matching later 118 void register(string name, Box box); 119 120 /// This is an implementation hook - bind must check that typeinfo matches and bind value to the lifted slot 121 Box opIndexAssign(Box value, string name); 122 123 /// Third implementation hook - lookup bound value for a given name 124 Box opIndex(string name); 125 } 126 127 /** 128 Simple stage that keeps slots as key-value pairs in built-in AA. 129 130 Could be used as is or as an example to build your own stage(s). 131 */ 132 class BasicStage : Stage { 133 override void register(string name, Box box) { 134 if (name in slots) throw new LmsNameConflict("This stage already has slot for '"~name~"' variable"); 135 slots[name] = box; 136 } 137 138 override Box opIndexAssign(Box lifted, string name) { 139 auto p = name in slots; 140 if (!p) throw new LmsNameResolution("This stage doesn't have '"~name~"' variable"); 141 slots[name].replace(lifted); 142 return lifted; 143 } 144 145 override Box opIndex(string name) { 146 auto p = name in slots; 147 if (!p) throw new LmsNameResolution("This stage doesn't have '"~name~"' variable"); 148 return slots[name]; 149 } 150 151 private Box[string] slots; 152 } 153 154 // Lifted value of type T 155 abstract class Lift(T) : Box { 156 // full evaluation, may fail if some variables are not defined at this stage 157 abstract T eval(Stage stage); 158 // partial evaluation given all of variables we know at this stage 159 abstract Lift!T partial(Stage stage); 160 // 161 final Lift!U map(U)(U delegate(T) mapFunc) { 162 return new Mapped!(T, U)(this, mapFunc); 163 } 164 // 165 final Lift!U flatMap(U)(Lift!U delegate(T) mapFunc) { 166 return new FlatMapped!(T, U)(this, mapFunc); 167 } 168 169 /// 170 auto opBinary(string op, U)(U rhsV) 171 if (!is(U : Lift!V, V)) { 172 return map((lhsV){ 173 return mixin("lhsV "~op~" rhsV"); 174 }); 175 } 176 177 /// 178 auto opBinary(string op, U)(U rhs) 179 if (is(U : Lift!V, V)) { 180 return flatMap((lhsV) { 181 return rhs.map((rhsV) { 182 return mixin("lhsV "~op~" rhsV"); 183 }); 184 }); 185 } 186 } 187 188 /// Simpliest of all - just a constant, stays the same, regardless of _stage_ 189 class Constant(T) : Lift!T { 190 this(T value) { 191 this.value = value; 192 } 193 194 override T eval(Stage stage) { 195 return value; 196 } 197 198 override Lift!T partial(Stage stage) { 199 return this; 200 } 201 202 private T value; 203 } 204 205 /// Slot - a placeholder for value, that will be provided at a later _stage_ 206 class Slot(T) : Lift!T { 207 this(string name) { 208 _name = name; 209 reset(); 210 } 211 212 override void replace(Box another) { 213 expr = cast(Lift!T)another; 214 } 215 216 void reset() { 217 expr = lift(T.init).map(delegate T (T x){ 218 throw new LmsEvaluationFailed("slot "~_name~" has no bound value at this stage"); 219 }); 220 } 221 222 override T eval(Stage stage) { 223 return expr.eval(stage); 224 } 225 226 override Lift!T partial(Stage stage) { 227 return expr; 228 } 229 230 string name() { return _name; } 231 232 private string _name; 233 private Lift!T expr; 234 } 235 236 // Lifted map function call 237 private class Mapped(T, U) : Lift!U { 238 this(Lift!T arg, U delegate(T) func) { 239 this.liftedArg = arg; 240 this.func = func; 241 } 242 243 override U eval(Stage stage) { 244 return func(liftedArg.eval(stage)); 245 } 246 247 override Lift!U partial(Stage stage) { 248 import std.stdio : writeln; 249 auto v = liftedArg.partial(stage); 250 auto c = cast(Constant!T)v; 251 if (c) return lift(func(c.eval(stage))); 252 return v.map(func); 253 } 254 255 private Lift!T liftedArg; 256 private U delegate(T) func; 257 } 258 259 private class FlatMapped(T, U) : Lift!U { 260 this(Lift!T arg, Lift!U delegate(T) func) { 261 this.liftedArg = arg; 262 this.func = func; 263 } 264 265 override U eval(Stage stage) { 266 return func(liftedArg.eval(stage)).eval(stage); 267 } 268 269 override Lift!U partial(Stage stage) { 270 return liftedArg.partial(stage).flatMap((arg){ 271 return func(arg); 272 }); 273 } 274 275 private Lift!T liftedArg; 276 private Lift!U delegate(T) func; 277 } 278 279 class LmsException : Exception { 280 this(string message) { 281 super(message); 282 } 283 } 284 285 class LmsNameResolution : LmsException { 286 this(string message) { 287 super(message); 288 } 289 } 290 291 class LmsNameConflict : LmsNameResolution { 292 this(string message){ 293 super(message); 294 } 295 } 296 297 class LmsEvaluationFailed : LmsException { 298 this(string message){ 299 super(message); 300 } 301 } 302 303 version(unittest) { 304 void assertThrows(T)(lazy T expr) { 305 try { 306 expr; 307 } 308 catch(LmsException e) { 309 return; 310 } 311 assert(0, expr.stringof ~ " should throw but didn't!"); 312 } 313 } 314 315 /// 316 @("basics") 317 unittest { 318 auto stage = new BasicStage(); 319 auto value = lift(40) + 2; 320 assert(stage.eval(value) == 42); 321 } 322 323 /// 324 @("slots") 325 unittest { 326 auto stage = new BasicStage(); 327 auto slot = stage.slot!string("some.slot"); 328 assert(slot.name == "some.slot"); 329 auto expr = slot ~ ", world!"; 330 assertThrows(stage.eval(expr)); 331 332 stage["some.slot"] = lift("Hello"); 333 assert(stage.eval(expr) == "Hello, world!"); 334 335 auto laterStage = new BasicStage(); 336 laterStage.slot(slot); 337 assertThrows(laterStage.eval(slot)); 338 339 laterStage["some.slot"] = lift("Bye"); 340 341 assert(stage.eval(expr) == "Bye, world!"); 342 } 343 344 345 /// 346 @("partial evaluation") 347 unittest { 348 auto stage = new BasicStage(); 349 int[] trace; // our primitive trace buffer 350 auto v1 = stage.slot!double("var1").map(delegate double(double x) { 351 trace ~= 1; 352 return x; 353 }); 354 auto v2 = stage.slot!double("var2").map(delegate double(double x) { 355 trace ~= 2; 356 return x; 357 }); 358 stage["var1"] = lift(1.5); 359 auto part = (v1 + v2).partial(stage); 360 stage["var2"] = lift(-0.5); 361 // first pass - both map functions called once 362 assert(part.eval(stage) == 1.0); 363 assert(trace == [1, 2]); 364 365 // second pass - only v2 is evaluated 366 assert(part.eval(stage) == 1.0); 367 assert(trace == [1, 2, 2]); 368 } 369 370 /// 371 @("CTFE") 372 unittest { 373 enum result = () { 374 auto stage = new BasicStage(); 375 auto s = stage.slot!int("int"); 376 stage["int"] = lift(123); 377 auto s2 = lift(2); 378 //auto s3 = s + s2; // somehow fails.. to be fixed soon 379 return stage.eval(s); 380 }(); 381 static assert(result == 123); 382 }