Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 27th, 2012  |  syntax: None  |  size: 4.35 KB  |  hits: 8  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. // The execution core needs to be able to store incomplete/partial
  2. // computations and data. When evaluation eventually happens, it
  3. // needs to store the result, so other references don't need to
  4. // recompute. So we need mutable data, that can be referred to.
  5. // The 3 candidates for doing this are:
  6. // - array []        (5.3sec)
  7. // - object {}       (4.4sec)
  8. // - function that operates on a "free variable"/closure.  (18sec)
  9. //
  10. // some simple benchmarks on v8 showed that arrays and objects perform
  11. // likewise (obj slightly faster, but uses more memory). However, for
  12. // storing things like partially applied functions
  13. // (function, arg1, arg2 .. argN), that have many things to store, an
  14. // array is a better fit. objects would have to use an array-field or
  15. // resort to generated field-names {arg1: 2, arg2: 4}.
  16. // functions perform worst. So we focus on arrays for now.
  17.  
  18.  
  19. // Every entity is an array, where its first argument is a number
  20. // indicating its evaluation status and expected outcome.
  21.  
  22. /*
  23.     lambda machine 'thunk' types
  24.  
  25.       # stuff that cannot be evaluated further
  26.     1  = prim     (wrapped javascript primitive)
  27.     2  = cons     ("real" constructor)
  28.     3  = part     (partially applied function)
  29.       # thunks waiting to be evaluated
  30.     10 = collapse (thunk only referring to other thunk)
  31.     11 = thunk    (function, ready to be applied)
  32.     12 = app      (unevaluated part with args -> thunk)
  33.  */
  34.  
  35. // - prim is native javascript value, boxed
  36. // - cons is a normal functional value (constructor + fields)
  37. // - part is a function and its arguments, having too few yet.
  38. // - collapse happens during tail recursion, when all that is left is
  39. //   a new thunk to evaluate. As we cannot tell references to update their
  40. //   pointers, we collapse in place (copy status/value from other thunk)
  41. // - thunk (should probably be renamed) is a function with enough (or
  42. //   even too much) arguments. It can be evaluated, but because of
  43. //   laziness, it hasn't yet.
  44. // - app (should get better name too) is when we have a partially
  45. //   applied function, and some additional arguments.
  46. //   evaluating turns it into 11 or 3.
  47.  
  48. var slice  = Array.prototype.slice,
  49.     splice = Array.prototype.splice;
  50.  
  51. // compiler should inline this
  52. function prim(obj) {                                           // wrap a primitive
  53.   if (typeof obj === 'object' || typeof obj === 'function') {  // array/obj/date/new String
  54.     return [1, obj];
  55.   } else {         // string/number/bool
  56.     return obj;
  57.   }
  58. }
  59.  
  60. // compiler should inline this
  61. function cons(constructorName) { // constructorName, *fields
  62.   var result = slice.call(arguments);
  63.   result.unshift(2);
  64.   return result;
  65. };
  66.  
  67. // compiler should inline this and perform compile-time analysis
  68. function thunk(fn) { // fn, args
  69.   var result = slice.call(arguments);
  70.   switch(typeof fn) {
  71.   case 'function':
  72.     if (fn.length < arguments.length) { // thunk that can be applied
  73.       result.unshift(11);
  74.     } else {
  75.       result.unshift(3);
  76.     }
  77.     break;
  78.   case 'object':
  79.     if (result.length === 1) {
  80.       result.unshift(10);
  81.     } else {
  82.       result.unshift(12);
  83.     }
  84.     break;
  85.   default:
  86.     result.unshift(1);
  87.   }
  88.   return result;
  89. }
  90.  
  91. function leval(expr) {
  92.   if (typeof expr !== 'object') { // runtime primitive
  93.     return expr;
  94.   }
  95.   var first, type, args, result;
  96.   while (true) {
  97.     type = expr[0];
  98.     first = expr[1];
  99.     switch(type) {
  100.     case 1: // runtime primitive
  101.       return first;
  102.     case 2: // whnf
  103.       return expr.slice(1);
  104.     case 3: // partial function application
  105.       return expr.slice(1);
  106.     case 10: // collapse
  107.       if(first[0] >= 10) { leval(first); } // make sure it's evaluated
  108.       result = first;
  109.       break;
  110.     case 11: // thunk
  111.       args = expr.slice(2, 2 + first.length);
  112.       result = thunk.apply(null, [first.apply(null, args)].concat(expr.slice(2 + first.length)));
  113.       break;
  114.     case 12: // app
  115.       if(first[0] >= 10) { leval(first); } // make sure it's evaluated
  116.       if (first[0] !== 3) { throw 'can only apply partial functions'; }
  117.       result = thunk.apply(null, first.slice(1).concat(expr.slice(2)))
  118.       break;
  119.     default:
  120.       throw 'unknown state in lambda machine';
  121.     }
  122.     splice.apply(expr, [0, expr.length].concat(result)); // pop into here
  123.   }
  124. };
  125.  
  126. // basic interface (out -> in)
  127. exports.leval = exports.$ = leval;
  128. exports.thunk = exports.$$ = thunk;
  129.  
  130. // optimized constructors
  131. exports.prim  = prim;
  132. exports.cons  = cons;
create a new version of this paste RAW Paste Data