fork(2) download
copy 
  1. function Thunk (value) {
  2.   this.value = value;
  3. }
  4.  
  5. function Lambda (fn) {
  6.   this.fn = fn;
  7. }
  8.  
  9. function App (fn, arg) {
  10.   this.fn = fn;
  11.   this.arg = arg;
  12. }
  13.  
  14. function Evaluate (val) {
  15.   while (val instanceof Thunk) {
  16.     var v = val;
  17.     if (v.evaluated) {
  18.       val = val.value;
  19.     } else {
  20.       val = val.value();
  21.     }
  22.     if (val instanceof App) {
  23.       val = (PeelLambda(Evaluate(val.fn)))(val.arg);
  24.     }
  25.     v.evaluated = true;
  26.     v.value = val;
  27.   }
  28.   return val;
  29. }
  30.  
  31. function PeelLambda (lam) {
  32.   if (!(lam instanceof Lambda)) {
  33.     throw "type error: apply a non-lambda to a value"
  34.   }
  35.   return lam.fn;
  36. }
  37.  
  38. function Apply (fn) {
  39.   return function (arg) {
  40.     return new Thunk(function () {
  41.       return new App(fn, arg);
  42.     });
  43.   };
  44. }
  45.  
  46. // add = (+)
  47. var add = new Lambda(function (x) {
  48.   return new Lambda(function (y) {
  49.     return new Thunk(function () {
  50.       return Evaluate(x) + Evaluate(y);
  51.     });
  52.   });
  53. });
  54.  
  55. // sub = (-)
  56. var sub = new Lambda(function (x) {
  57.   return new Lambda(function (y) {
  58.     return new Thunk(function () {
  59.       return Evaluate(x) - Evaluate(y);
  60.     });
  61.   });
  62. });
  63.  
  64. function Cons (car, cdr) {
  65.   this.car = car;
  66.   this.cdr = cdr;
  67. }
  68.  
  69. function Nil () {
  70. }
  71.  
  72. // []
  73. var nil = new Thunk(function () {
  74.   return new Nil();
  75. });
  76.  
  77. // (:)
  78. var cons = new Lambda(function (x) {
  79.   return new Lambda(function (xs) {
  80.     return new Thunk(function () {
  81.       return new Cons(x, xs);
  82.     });
  83.   });
  84. });
  85.  
  86. // head [] = error "head: empty list"
  87. // head (x:_) = x
  88. var head = new Lambda(function (list) {
  89.   return new Thunk(function () {
  90.     var xxs = Evaluate(list);
  91.     if (xxs instanceof Cons) {
  92.       return xxs.car;
  93.     } else {
  94.       throw "head: empty list";
  95.     }
  96.   });
  97. });
  98.  
  99. // tail [] = error "tail: empty list"
  100. // tail (_:xs) = xs
  101. var tail = new Lambda(function (list) {
  102.   return new Thunk(function () {
  103.     var xxs = Evaluate(list);
  104.     if (xxs instanceof Cons) {
  105.       return xxs.cdr;
  106.     } else {
  107.       throw "tail: empty list";
  108.     }
  109.   });
  110. });
  111.  
  112. // map _ [] = []
  113. // map f (x:xs) = f x : map f xs
  114. var map = new Lambda(function (f) {
  115.   return new Lambda(function (list) {
  116.     return new Thunk(function () {
  117.       var xxs = Evaluate(list);
  118.       if (xxs instanceof Cons) {
  119.         var x = xxs.car;
  120.         var xs = xxs.cdr;
  121.         return Apply(Apply(cons)(Apply(f)(x)))
  122.                                 (Apply(Apply(map)(f))(xs));
  123.       } else {
  124.         return nil;
  125.       }
  126.     });
  127.   });
  128. });
  129.  
  130. // take _ [] = []
  131. // take n _ | n <= 0 = []
  132. // take n (x:xs) = x : take (n - 1) xs
  133. var take = new Lambda(function (n) {
  134.   return new Lambda(function (list) {
  135.     return new Thunk(function () {
  136.       var xxs = Evaluate(list);
  137.       if (xxs instanceof Cons) {
  138.         var nval = Evaluate(n);
  139.         if (nval <= 0) {
  140.           return nil;
  141.         } else {
  142.           var x = xxs.car;
  143.           var xs = xxs.cdr;
  144.           return Apply(Apply(cons)(x))
  145.                                   (Apply(Apply(take)(Apply(Apply(sub)(n))(one)))(xs));
  146.         }
  147.       } else {
  148.         return nil;
  149.       }
  150.     });
  151.   });
  152. });
  153.  
  154. function Unit () {
  155. }
  156.  
  157. // unit = ()
  158. var unit = new Thunk(function () {
  159.   return new Unit();
  160. });
  161.  
  162. // print = \x -> log x; return ()
  163. //   (not so monadic...)
  164. var print = new Lambda(function (x) {
  165.   return new Thunk(function () {
  166.     console.log(Evaluate(x));
  167.     return Apply(return_)(unit);
  168.   });
  169. });
  170.  
  171. // return
  172. var return_ = new Lambda(function (x) {
  173.   return new Thunk(function () {
  174.     return x;
  175.   });
  176. });
  177.  
  178. // (>>)
  179. var then = new Lambda(function (fn1) {
  180.   return new Lambda(function (fn2) {
  181.     return new Thunk(function () {
  182.       Evaluate(fn1);
  183.       Evaluate(fn2);
  184.     });
  185.   });
  186. });
  187.  
  188. // mapM_ _ [] = return ()
  189. // mapM_ f (x:xs) = f x >> mapM_ f xs
  190. var mapM_ = new Lambda(function (f) {
  191.   return new Lambda(function (list) {
  192.     return new Thunk(function () {
  193.       var xxs = Evaluate(list);
  194.       if (xxs instanceof Cons) {
  195.         var x = xxs.car;
  196.         var xs = xxs.cdr;
  197.         return Apply(Apply(then)(Apply(f)(x)))
  198.                                 (Apply(Apply(mapM_)(f))(xs));
  199.       } else {
  200.         return Apply(return_)(unit);
  201.       }
  202.     });
  203.   });
  204. });
  205.  
  206. // zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
  207. // zipWith _ _ _ = []
  208. var zipWith = new Lambda(function (f) {
  209.   return new Lambda(function (listx) {
  210.     return new Lambda(function (listy) {
  211.       return new Thunk(function () {
  212.         var xxs = Evaluate(listx);
  213.         if (xxs instanceof Cons) {
  214.           var yys = Evaluate(listy);
  215.           if (yys instanceof Cons) {
  216.             return Apply(Apply(cons)(Apply(Apply(f)(xxs.car))(yys.car)))
  217.                                     (Apply(Apply(Apply(zipWith)(f))(xxs.cdr))(yys.cdr));
  218.           }
  219.         } else {
  220.           return nil;
  221.         }
  222.       });
  223.     });
  224.   });
  225. });
  226.  
  227. var zero = new Thunk(function () {
  228.   return 0;
  229. });
  230.  
  231. var one = new Thunk(function () {
  232.   return 1;
  233. });
  234.  
  235. var twenty = new Thunk(function () {
  236.   return 20;
  237. });
  238.  
  239. var hundred = new Thunk(function () {
  240.   return 100;
  241. });
  242.  
  243. // inf = 0 : map (+1) inf
  244. var inf = new Thunk(function () {
  245.   return Apply(Apply(cons)(zero))
  246.                           (Apply(Apply(map)(Apply(add)(one)))(inf));
  247. });
  248.  
  249. // fib = 0 : 1 : zipWith (+) fib (tail fib)
  250. var fib = new Thunk(function () {
  251.   return Apply(Apply(cons)(zero))
  252.                           (Apply(Apply(cons)(one))
  253.                                             (Apply(Apply(Apply(zipWith)(add))(fib))(Apply(tail)(fib))));
  254. });
  255.  
  256. // main = mapM_ print (take 100 fib)
  257. var main = new Thunk(function () { 
  258.   return Apply(Apply(mapM_)(print))(Apply(Apply(take)(hundred))(fib)); 
  259. });
  260.  
  261. Evaluate(main);
  262.  
Success #stdin #stdout 0.07s 10928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676220
23416728348467684
37889062373143900
61305790721611580
99194853094755490
160500643816367070
259695496911122560
420196140727489660
679891637638612200
1100087778366101900
1779979416004714000
2880067194370816000
4660046610375530000
7540113804746346000
12200160415121877000
19740274219868226000
31940434634990100000
51680708854858330000
83621143489848430000
135301852344706760000
218922995834555200000
https://ideone.com/5FmJha
language:
Node.js (node 11.12.0)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!