1: // Search and Optimisation Streams
2:
3: // Search is the problem of finding a value which
4: // fits some criterion. Given a set of possible
5: // solutions and a test function, search returns
6: // solutions for which the test returns true.
7: // Optimisation generalises search. Instead of a
8: // test function, we have a fitness function which
9: // returns numbers. Optimisation tries to return
10: // the solution with the highest fitness.
11: // A stream is any function which takes no arguments
12: // and returns a result. This simple interface
13: // represents a computation that hasn't been run yet
14: // (also known as a "thunk"). Streams nicely capture
15: // the problems of search and optimisation , since:
16: // 1) Search/optimisation algorithms never halt,
17: // they can always give another value (even if
18: // it stabilises to the same one), so we need to
19: // represent these computations without actually
20: // performing them (which would take forever).
21: // Streams are effectively lazy lists (or
22: // generators, if you prefer) of the results.
23: // 2) Different search algorithms rely on different
24: // numbers of parameters, and use variables at
25: // multiple scope levels. A thunk interface
26: // encapsulates all of this at the point of
27: // definition, so that the resulting streams are
28: // indistinguishable and can be composed
29: // interchangably. We can still use parameters
30: // and state, but they must be curried into the
31: // stream functions. This minimises shared state
32: // and other such nastiness.
33: //
34: // As a consequence of this currying, we generally
35: // don't ending up define streams directly, but
36: // rather curryable functions (combinators, or
37: // 'stream factories', if you prefer) which take
38: // any required parameters as arguments, set up any
39: // required state and return a stream with these
40: // built-in.
41:
42: ///////////////////////
43: // Utility functions //
44: ///////////////////////
45:
46: var c = curry = function(f) {
47: var add_args = function(old_args) {
48: if (old_args.length >= f.length) return apply(f, old_args);
49: return function() {
50: var new_args = [];
51: for (var i = 0; i < arguments.length; i++) new_args.push(arguments[i]);
52: return add_args(old_args.concat(new_args));
53: };
54: };
55: return add_args([]);
56: };
57:
58: var apply = function(f, args) {
59: // Returns f(args[0], args[1], ...)
60: return f.apply(null, args);
61: };
62:
63: var plus = c(function(a, b) {
64: // Reifies + ("add" may get confused with
65: // array.push)
66: return a+b;
67: });
68:
69: var negate = function(a) {
70: // Reifies unary -
71: return -1 * a;
72: };
73:
74: var multiply = c(function(a, b) {
75: // Likewise for * ("times" may get confused
76: // with iterate(f) or range(n))
77: return a*b;
78: });
79:
80: var divide = c(function(a, b) {
81: // Reifies /
82: return a / b;
83: });
84:
85: var modulus = c(function(a, b) {
86: // Reifies %
87: return a % b;
88: });
89:
90: var subscript = c(function(a, b) {
91: // Reifies []
92: return a[b];
93: });
94:
95: var catenate = c(function(head, tail) {
96: // Reifies catenation (joining arrays)
97: return head.concat(tail);
98: });
99:
100: var cons = c(function(head, tail) {
101: // Reifies pairing
102: return [head, tail];
103: });
104:
105: var choose_direction = function(a) {
106: // Turns 0/1 into -1/1
107: return 2*a - 1;
108: };
109:
110: var rebase = c(function(n, b) {
111: // Returns the first number in the base of the
112: // second number. For example, rebase(12, 2)
113: // gives [1, 1, 0, 0], which is 12 in base 2.
114: // We use numbers 0 to b-1 as symbols.
115: var result = [];
116: var val;
117: do {
118: val = (b === 1)? Math.min(1, n) : n % b;
119: result.unshift(val);
120: n = (n - val) / b;
121: } while (n);
122: return result;
123: });
124:
125: var tagged_pruner = c(function(pop, n) {
126: // Simple function to keep the top n members of
127: // the given population (which are prefixed with
128: // their fitnesses)
129: if (pop.length <= n) return pop;
130: pop.sort(function(a, b) {
131: if (a[0] > b[0]) return 1;
132: if (a[0] < b[0]) return -1;
133: return 0;
134: });
135: return pop.slice(pop.length - n);
136: });
137:
138: var take = c(function(n, stream) {
139: // Returns an array of n values taken
140: // from the given stream.
141: var result = [];
142: for (var i = 0; i < n; i++) result.push(stream());
143: return result;
144: });
145:
146: var cartesian_from_polar = function(angles) {
147: // Takes N-1 angles, which are interpreted as
148: // polar coordinates in N-dimensional space (with unit radius).
149: // The final element of the angle array will be taken mod 360,
150: // the rest will be taken mod 180.
151: // Returns the equivalent N components of this vector in
152: // cartesian space.
153: var normalised_angles = (function(these_angles) {
154: if (these_angles.length == 0) return [1];
155: var result = [];
156: for (var i = 1; i < these_angles.length + 1; i++) {
157: result[i] = Math.cos(these_angles[i]);
158: for (var j = 0; j < i; j++) {
159: result[i] *= Math.sin(these_angles[j]);
160: }
161: }
162: return result;
163: })(angles);
164: return these_angles.map(function(v, k) {
165: var result;
166: if (k == these_angles.length - 1) {
167: result = v % 360;
168: if (result < 0) result = 360 + result;
169: }
170: else {
171: result = v % 180;
172: if (result < 0) result = 180 + result;
173: }
174: return result;
175: });
176: };
177:
178: var times = c(function(n, val) {
179: var result = [];
180: while (n--) result.push(val);
181: return result;
182: });
183:
184: var array_compare = c(function(a, b) {
185: // Compare 1D arrays a and b for equality.
186: // Uses ===, so won't work with nested arrays.
187: if (Array.isArray(a) !== Array.isArray(b)) return false;
188: if (!Array.isArray(a)) return a === b;
189: if (a.length !== b.length) return false;
190: for (var i = 0; i < a.length; i++) {
191: if (!array_compare(a[i], b[i])) return false;
192: }
193: return true;
194: });
195:
196: var identity = function(x) { return x; };
197:
198: var n_point_crossover = c(function(points, first, second) {
199: // Takes two array-like solutions (first and
200: // second) and swaps their elements at n points,
201: // chosen by rand.
202: var new_first = first.slice(0);
203: var new_second = second.slice(0);
204: points.forEach(function(n) {
205: var chunk1 = new_first.splice(n * new_first.length);
206: var chunk2 = new_second.splice(n * new_second.length);
207: new_first = new_first.concat(chunk1);
208: new_second = new_second.concat(chunk2);
209: });
210: return [new_first, new_second];
211: });
212:
213: var flip_bit = c(function(rand, string) {
214: // Takes an array of booleans and a random number
215: // between 0 and 1. Indexes the array using the
216: // random number and flips the bit.
217: if (string.length === 0) return string;
218: var index = Math.floor(rand * string.length - 1);
219: var copy = string.slice(0, index);
220: copy.push(!string[index]);
221: return copy.concat(string.slice(index));
222: });
223:
224: /////////////////////////////
225: // Streams and combinators //
226: /////////////////////////////
227:
228: var constant = function(val) {
229: // A constant stream always gives the same
230: // value. This combinator makes constant
231: // streams.
232: return function() {
233: return val;
234: };
235: };
236:
237: var zeros = function() {
238: // A stream of 0s
239: return constant(0);
240: };
241:
242: var ones = function() {
243: // A stream of 1s
244: return constant(1);
245: };
246:
247: var reduce = c(function(init, f, stream) {
248: // Reduce combines the results of a
249: // stream using a reduction function.
250: // For function f, initial value init
251: // and stream values a, b, c, ...
252: // reduce returns:
253: // f(init, a)
254: // f(f(init, a), b)
255: // f(f(f(init, a), b), c)
256: // ...
257: var comb = function() {
258: comb = function() {
259: init = f(init, stream());
260: return init;
261: };
262: return init;
263: };
264: return function() {
265: return comb();
266: };
267: });
268:
269: var counter = function() {
270: // A useful example of a reduction.
271: // Produces a stream of the Naturals
272: return reduce(0, plus, ones());
273: };
274:
275: var hoard = function(comb) {
276: // A reducer which appends all results to an
277: // array
278: return reduce([], catenate, comb);
279: };
280:
281: var delayer = c(function(vals, stream) {
282: // Returns each element of the given
283: // array, then becomes the given stream
284: var index = 0;
285: return function() {
286: if (index < vals.length) return vals[index++];
287: else return stream();
288: };
289: });
290:
291: var delay = c(function(val, stream) {
292: // Returns the given value, then becomes
293: // the given stream
294: return delayer([val], stream);
295: });
296:
297: var map = c(function(f, comb) {
298: // Maps the given function over the given
299: // stream.
300: return function() {
301: return f(comb());
302: };
303: });
304:
305: var iterate = c(function(f, val) {
306: // Takes a function f and a value x, returns
307: // the stream f(x), f(f(x)), f(f(f(x))), ...
308: var result = val;
309: return function() {
310: result = f(result);
311: return result;
312: };
313: });
314:
315: var simple = function() {
316: // SIMPLE, as defined by Jurgen Schmidhuber.
317: // Returns every binary sequence in ascending
318: // order.
319: return enumerate([0, 1]);
320: };
321:
322: var bbj = c(function(i, o, inc, input, n) {
323: // A simple, potentially Turing Complete language,
324: // BitBitJump. We have an unbounded memory full of
325: // zeros, the start of which is initialised to the
326: // binary form of n.
327: // We have a program counter (initially 0), an
328: // address length (initially 2) and a single
329: // instruction which runs over and over:
330: // Read 2 addresses x and y, starting at the
331: // program counter; copy the bit at x to the bit
332: // at y; read a third address from after the
333: // program counter, and use this as the new
334: // program counter.
335: // This implementation uses a bignum (arbitrary
336: // size integer) library to store the memory and
337: // addresses, but the algorithm just uses +, -, *,
338: // /, % and power-of.
339: // We parameterise this implementation with input,
340: // output and address-size-increment. i is a pair
341: // [magic address, destination]; writing 1 to the
342: // magic address will read a value from the input
343: // stream and write it to the destination address.
344: // Similarly o is [magic address, source]; writing
345: // a 1 to the magic address will append whatever is
346: // at the source address to the output we return.
347: // inc is a magic address; writing a 1 to it will
348: // increment the address size, which makes us
349: // Turing Complete. Note that you can disable any
350: // of these by using negative numbers as the magic
351: // addresses (hence "potentially Turing Complete",
352: // since we're not if inc is inaccessible address)
353: load('biginteger.js');
354: var one = BigInteger(1);
355: var two = BigInteger(2);
356: i[0] = BigInteger(i[0]);
357: i[1] = BigInteger(i[1]);
358: o[0] = BigInteger(o[0]);
359: o[1] = BigInteger(o[1]);
360: inc = BigInteger(inc);
361: var pc = BigInteger(0);
362: var mem;
363: var w = BigInteger(2);
364: if (Array.isArray(n)) mem = BigInteger.parse(n.join(''), 2);
365: else mem = BigInteger(n);
366: var output = [];
367: return function() {
368: // Read a word from the program counter
369: var x = mem.remainder(
370: two.pow(
371: pc.add(w)
372: )
373: ).subtract(
374: mem.remainder(
375: two.pow(pc)
376: )
377: ).quotient(
378: two.pow(pc)
379: );
380:
381: // Read the next word
382: var y = mem.remainder(
383: two.pow(
384: pc.add(w).add(w)
385: )
386: ).subtract(
387: mem.remainder(
388: two.pow(
389: pc.add(w)
390: )
391: )
392: ).quotient(
393: two.pow(
394: pc.add(w)
395: )
396: );
397:
398: // Split the memory into above and below the bit to set
399: var higher = mem.subtract(
400: mem.remainder(
401: two.pow(
402: y.add(one)
403: )
404: )
405: );
406: var lower;
407: if (y.compare(BigInteger(0))) lower = mem.remainder(
408: two.pow(
409: y.subtract(one)
410: )
411: );
412: else lower = 0;
413:
414: // Read the bit we're copying
415: var val = mem.remainder(
416: two.pow(
417: x.add(one)
418: )
419: ).subtract(
420: mem.remainder(
421: two.pow(x)
422: )
423: ).quotient(
424: two.pow(x)
425: ).valueOf();
426:
427: // Update the memory (or invoke magic)
428: if (val && y.compare(i[0]) === 0) {
429: val = input();
430: y = i[1];
431: }
432: else if (val && y.compare(o[0]) === 0) {
433: output.push(
434: mem.remainder(
435: two.pow(
436: o[1].add(one)
437: )
438: ).subtract(
439: mem.remainder(
440: two.pow(o[1])
441: )
442: ).quotient(
443: two.pow(o[1])
444: ).valueOf()
445: );
446: val = mem.remainder(
447: two.pow(
448: y.add(one)
449: )
450: ).subtract(
451: mem.remainder(
452: two.pow(y)
453: )
454: ).quotient(
455: two.pow(y)
456: ).valueOf();
457: }
458: else if (val && y === inc) {
459: w = w.add(one);
460: val = mem.remainder(
461: two.pow(
462: y.add(one)
463: )
464: ).subtract(
465: mem.remainder(
466: two.pow(y)
467: )
468: ).divide(
469: two.pow(y)
470: ).valueOf();
471: }
472: mem = higher.add(
473: two.pow(y).multiply(
474: BigInteger(val)
475: )
476: ).add(lower);
477:
478: // Read the next word and jump where it says
479: pc = mem.remainder(
480: two.pow(
481: pc.add(
482: w.multiply(BigInteger(3))
483: )
484: ).subtract(
485: mem.remainder(
486: two.pow(
487: pc.add(w).add(w)
488: )
489: )
490: )
491: ).quotient(
492: two.pow(
493: pc.add(w).add(w)
494: )
495: );
496: return output;
497: };
498: });
499:
500: var bbj_pure = bbj([-1, -1], [-1, -1], -1, function(){});
501:
502: var bbj_io = bbj([0,1], [2,3], 4);
503:
504: var bbj_outputter = bbj([-1, -2], [0, 1], 2, function(){});
505:
506: var bbj_lazy = function(){ };
507:
508: /////////////////////////////
509: // Streams and combinators //
510: /////////////////////////////
511:
512: var constant = function(val) {
513: // A constant stream always gives the same
514: // value. This combinator makes constant
515: // streams.
516: return function() {
517: return val;
518: };
519: };
520:
521: var zeros = function() {
522: // A stream of 0s
523: return constant(0);
524: };
525:
526: var ones = function() {
527: // A stream of 1s
528: return constant(1);
529: };
530:
531: var reduce = c(function(init, f, stream) {
532: // Reduce combines the results of a
533: // stream using a reduction function.
534: // For function f, initial value init
535: // and stream values a, b, c, ...
536: // reduce returns:
537: // f(init, a)
538: // f(f(init, a), b)
539: // f(f(f(init, a), b), c)
540: // ...
541: var comb = function() {
542: comb = function() {
543: init = f(init, stream());
544: return init;
545: };
546: return init;
547: };
548: return function() {
549: return comb();
550: };
551: });
552:
553: var counter = function() {
554: // A useful example of a reduction.
555: // Produces a stream of the Naturals
556: return reduce(0, plus, ones());
557: };
558:
559: var hoard = function(comb) {
560: // A reducer which appends all results to an
561: // array
562: return reduce([], catenate, comb);
563: };
564:
565: var delayer = c(function(vals, stream) {
566: // Returns each element of the given
567: // array, then becomes the given stream
568: var index = 0;
569: return function() {
570: if (index < vals.length) return vals[index++];
571: else return stream();
572: };
573: });
574:
575: var delay = c(function(val, stream) {
576: // Returns the given value, then becomes
577: // the given stream
578: return delayer([val], stream);
579: });
580:
581: var map = c(function(f, comb) {
582: // Maps the given function over the given
583: // stream.
584: return function() {
585: return f(comb());
586: };
587: });
588:
589: var iterate = c(function(f, val) {
590: // Takes a function f and a value x, returns
591: // the stream f(x), f(f(x)), f(f(f(x))), ...
592: var result = val;
593: return function() {
594: result = f(result);
595: return result;
596: };
597: });
598:
599: var simple = function() {
600: // SIMPLE, as defined by Jurgen Schmidhuber.
601: // Returns every binary sequence in ascending
602: // order.
603: return carrying_counter(2);
604: };
605:
606: var fast = c(function(symbols, run) {
607: // FAST, as defined by Jurgen Schmidhuber.
608: // Runs every program using the given
609: // symbols for an ever-increasing number
610: // of steps. Each result is the output of
611: // the next program.
612: // The step function should return a pair
613: // [p, output] where p can be anything, as
614: // long as it can be passed as step's
615: // input. step should also accept an array
616: // of symbols instead, as this is how it's
617: // initialised. If no output is generated
618: // in a step, then make the output []
619: var phase = 1;
620: return map (
621: function(a) {
622: var r = run(a);
623: skipper(
624: constant(Math.pow(symbols.length, phase - a.length)),
625: r
626: )();
627: return r();
628: },
629: phases(
630: function() {
631: return enumerate(symbols);
632: },
633: function () { return phase++; }
634: )
635: );
636: });
637:
638: var fast_bbj_out = function() { return fast([0,1], bbj_outputter); };
639:
640: var fast_bbj_in = function(input) { return fast([0,1], bbj_io(input)); };
641:
642: var uniform_randoms = function() {
643: // Generates random x where 0 <= x < 1
644: return Math.random;
645: };
646:
647: var scaled_randoms = function(ns) {
648: // Generates random floats x where
649: // 0 <= x < n
650: return map(
651: function(a) {
652: return ns()*a;
653: },
654: uniform_randoms()
655: );
656: };
657:
658: var random_ints = function(ns) {
659: // Generates random integers x where 0 <= x < n
660: return map(
661: Math.floor,
662: scaled_randoms(ns)
663: );
664: };
665:
666: var random_bits = function() {
667: // Generates random bits
668: return random_ints(constant(2));
669: };
670:
671: var random_steps = function() {
672: // Chooses randomly between 1 and -1
673: return map(
674: plus(-1),
675: map(
676: multiply(2),
677: random_bits()
678: )
679: );
680: };
681:
682: var random_walker = function(steps) {
683: // Unbiased 1D random walk generator, using a stream
684: // of step sizes.
685: return reduce(
686: 0,
687: plus,
688: product(
689: multiply,
690: random_steps(),
691: steps
692: )
693: );
694: };
695:
696: var random_walk = function() {
697: // Standard 1D random walk
698: return random_walker(ones());
699: };
700:
701: var product = c(function(f, as, bs) {
702: // Combines two streams using a function
703: return function() {
704: return f(as(), bs());
705: };
706: });
707:
708: var make_pareto = function(scale) {
709: // Returns samples from a Pareto distribution,
710: // an inverse power law.
711: // This implements Math.pow(Math.random(), -1 / scale)
712: return map(
713: function(r) {
714: return Math.pow(1.0 - r, -1 /scale());
715: },
716: uniform_randoms()
717: );
718: };
719:
720: var pareto = function() {
721: // Standard Pareto distribution
722: make_pareto(ones());
723: };
724:
725: var levy_flight = function() {
726: // 1D Levy Flight; a random walk with random step
727: // sizes, chosen with a heavy-tailed probability
728: // density (in this case a Pareto distribution)
729: return random_walker(pareto());
730: };
731:
732: var make_exponential = function(base) {
733: // Gives random (natural) numbers from an
734: // exponentially decaying probability distribution.
735: return function() {
736: var sample = 1 - Math.random();
737: var result = 0;
738: while (1.0 / Math.pow(base, result+1) < sample) {
739: sample -= 1.0 / Math.pow(base, result+1);
740: result++;
741: }
742: return result;
743: };
744: };
745:
746: var binary_exponential = function() { return make_exponential(2); };
747:
748: var zip_with = c(function(f, comb1, comb2) {
749: // Combines two streams using the given function
750: return function() {
751: return f(comb1(), comb2());
752: };
753: });
754:
755: var guess = c(function(step, symbols, symbol_choice, phase_choice) {
756: // GUESS, as defined by Jurgen Schmidhuber.
757: // Creates random programs and runs them
758: // for a random number of steps. Returns
759: // the output generated by the program.
760: // [] means no output for a given step.
761:
762: // t controls each run to force halting
763: var t;
764: // A stream of input symbols.
765: // We decrease t as input is read, so
766: // that longer programs are given less
767: // time.
768: var input = finite_chooser(
769: symbols,
770: filter(
771: function(x) {
772: t /= symbols.length;
773: return true;
774: },
775: symbol_choice
776: )
777: );
778: return function() {
779: t = phase_choice();
780: var steps_taken = 0;
781: var max_cell = 0;
782: var mem = function(index) {
783: while (index > max_cell) {
784: mem[max_cell++] = input();
785: }
786: return mem[index];
787: };
788:
789: var output = [];
790: var instance = step(mem);
791: var result;
792: while (steps_taken <= t) {
793: result = instance();
794: if (result !== []) output.push(result);
795: };
796: return output;
797: };
798: });
799:
800: var guess_bbj_out = function() { return guess(bbj_lazy, [0, 1], random_bits(), binary_exponential()); };
801:
802: var make_scattered = c(function(ns, nil, comb, choice) {
803: // Creates arrays a with lengths taken from ns.
804: // Element a[choice()] = comb(), everything else
805: // is nil().
806: return function() {
807: var index = choice();
808: var result = [];
809: var length = ns();
810: for (var i=0; i < length; i++) {
811: if (i == index) result.push(comb());
812: else result.push(nil());
813: }
814: return result;
815: };
816: });
817:
818: var make_manhattan_steps = c(function(n, directions, steps) {
819: // Generalises a 1D stream of steps to N
820: // dimensions. The steps are 0 in every direction
821: // except for those chosen by a stream of integers
822: // between 0 and N-1 inclusive.
823: return make_scattered(
824: constant(n),
825: constant(0),
826: steps,
827: directions
828: );
829: });
830:
831: var finite_chooser = c(function(array, choices) {
832: // Chooses values from the given array, according
833: // to the indices given by choices
834: return function() {
835: return array[choices()];
836: };
837: });
838:
839: var chooser = c(function(streams, choices) {
840: // Interleaves N streams according to a stream of
841: // integer choices from 0 to N-1
842: return function() {
843: return (streams[choices()])();
844: };
845: });
846:
847: var interleave = function(streams) {
848: // Turns an array of streams into a stream of their
849: // results, cycling through the array.
850: var choice = 0;
851: return chooser(
852: streams,
853: function() { return choice = ++choice % streams.length; }
854: );
855: };
856:
857: var vectors = function(streams) {
858: // Makes an N-dimensional vector from N scalars,
859: // using one stream for each dimension.
860: return function() {
861: var result = [];
862: var n = streams.length;
863: for (var i=0; i < n; i++) {
864: result.push((streams[i])());
865: }
866: return result;
867: };
868: };
869:
870: var parallel_map = c(function(fs, stream) {
871: // Takes a stream of arrays and an array of functions, returning
872: // arrays where element i is functions[i](input[i])
873: return map(
874: function(arr) {
875: return arr.map(function(v, k) { return fs[k](v); });
876: },
877: stream
878: );
879: });
880:
881: var nested_map = c(function(f, stream) {
882: // Takes a stream of arrays and maps the given function over
883: // all of the members.
884: return map(
885: function(arr) { return arr.map(f); },
886: stream
887: );
888: });
889:
890: var tag = c(function(f, comb) {
891: // Returns pairs of [f(x), x] where x is drawn from the given
892: // stream.
893: return function() {
894: var val = comb();
895: return [f(val), val];
896: };
897: });
898:
899: var carrying_counter = function(n) {
900: // A stream of all sequences of numbers which
901: // are less than the given integer. For
902: // example, given 3 we would get the stream:
903: // [0], [1], [2], [0, 0], [0, 1], [0, 2],
904: // [1. 0], [1, 1], etc.
905: var result = [-1];
906: var index = 0;
907: return function() {
908: result[index] = result[index] + 1;
909: while (result[index] >= n) {
910: result[index] = 0;
911: index--;
912: if (index < 0) {
913: result.push(0);
914: index = result.length - 1;
915: }
916: else result[index] = result[index] + 1;
917: }
918: index = result.length - 1;
919: return result;
920: };
921: };
922:
923: var enumerate = function(alphabet) {
924: // Returns all strings of the given alphabet, in
925: // size-increasing lexicographic order. The
926: // alphabet is an array of arbitrary symbols.
927: var counter = carrying_counter(alphabet.length);
928: return function() {
929: return counter().map(function(v) {
930: return alphabet[v];
931: });
932: };
933: };
934:
935: var phases = c(function(stream_builder, ns) {
936: // Takes a stream-of-streams-of-arrays. Also
937: // takes a stream of numbers.
938: // We take a number, and a stream of arrays,
939: // and keep returning the arrays until one's
940: // length is more than our number. We then
941: // take the next number and stream, etc.
942: var n = ns();
943: var stream = stream_builder();
944: return function() {
945: var result = stream();
946: while (result.length > n) {
947: n = ns();
948: stream = stream_builder();
949: result = stream();
950: }
951: return result;
952: };
953: });
954:
955: var filter = c(function(f, comb) {
956: // Only returns those values from the given
957: // combinator for which f(value) == true.
958: // WARNING: This will only terminate once it
959: // finds a value which passes the test! Only
960: // use it when you know this will take a
961: // finite number of attempts (or else make sure
962: // to have another process ready to kill this
963: // one!)
964: return function() {
965: var val = comb();
966: while (!f(val)) {
967: val = comb();
968: }
969: return val;
970: };
971: });
972:
973: var skipper = c(function(ns, comb) {
974: // Discards n values from the given combinator,
975: // then returns the next one. The number to
976: // discard is taken from a combinator too.
977: return function() {
978: var n = ns();
979: while (n--) {
980: comb();
981: }
982: return comb();
983: };
984: });
985:
986: var chunk = c(function(ns, comb) {
987: // Reads numbers from ns and returns arrays of
988: // that many values from comb.
989: return function() {
990: return take(ns(), comb);
991: };
992: });
993:
994: var make_population = c(function(ns, source, kill) {
995: // Maintains a population with sizes taken from ns.
996: // The source combinator is used when new values are
997: // needed, and the kill function is used to prune a
998: // population, via kill(pop, n).
999: var pop = [];
1000: return function() {
1001: var size = ns();
1002: while (pop.length < size) {
1003: pop.push(source());
1004: }
1005: while (pop.length > size) {
1006: pop = kill(pop, size);
1007: }
1008: return pop;
1009: };
1010: });
1011:
1012: var survivors = c(function(ns, comb, fitness) {
1013: // Makes a population where each has a fitness, and
1014: // keeps the fittest when pruning.
1015: return make_population(
1016: ns,
1017: tag(fitness, comb),
1018: tagged_pruner
1019: );
1020: });
1021:
1022: var make_breeders = c(function(ns, f, kill) {
1023: // Makes a population where the new members are a
1024: // function of the existing members. The population
1025: // size is set by ns, the function to make new
1026: // members is f and the pruning function is kill.
1027: var pop = [];
1028: var comb = make_population(
1029: ns,
1030: function() {
1031: return f(pop);
1032: },
1033: kill
1034: );
1035: return function() {
1036: pop = comb();
1037: return pop;
1038: };
1039: });
1040:
1041: var make_survival_breeders = c(function(ns, f, fitness) {
1042: // Makes a population where the new members are a
1043: // function of the existing members. Each is given a
1044: // fitness, and the fittest are kept during pruning.
1045: return make_breeders(
1046: ns,
1047: function(pop) {
1048: var val = f(pop);
1049: return [fitness(val), val];
1050: },
1051: tagged_pruner
1052: );
1053: });
1054:
1055: var make_fittest = function(comb) {
1056: // Returns the fittest individual from a population
1057: // of fitness-tagged values (ie. [f(x),x] )
1058: return function() {
1059: var pop = comb();
1060: var fittest = 0;
1061: var fitness = pop[0][0];
1062: for (var i=0; i < pop.length; i++) {
1063: if (pop[i][0] > fitness) {
1064: fittest = i;
1065: fitness = pop[i][0];
1066: }
1067: }
1068: return pop[fittest][1];
1069: };
1070: };
1071:
1072: var mutate = c(function(choices, step) {
1073: return map(function(a) {
1074: if (choices()) {
1075: return step(a);
1076: }
1077: return a;
1078: });
1079: });
1080:
1081: var extremal_optimiser = c(function(source, fitness, size) {
1082: // Performs extremal optimisation. This is similar
1083: // to a genetic algorithm but rather than finding
1084: // fit solutions and breeding them, we find weak
1085: // solutions and replace them. This results in a
1086: // hill climbing behaviour with occasional jumps
1087: // between hills.
1088:
1089: // We maintain a population of solutions drawn
1090: // from source, where the weakest are pruned
1091: // if the population size decreases. When called,
1092: // we set the population to size-1 (pruning the
1093: // weakest solution) then set it back to size and
1094: // return the result.
1095: return skipper(ones(),
1096: survivors(
1097: interleave(constant(size-1), constant(size)),
1098: source,
1099: fitness
1100: )
1101: );
1102: });
1103:
1104: var informed_chooser = function(next) {
1105: // Returns arrays with elements taken from
1106: // the given function. Each time, we call
1107: // it with the partial array we've built
1108: // so far. It should return pairs [a, b]
1109: // where a is a boolean for whether to
1110: // stop and b is the value to push on the
1111: // array.
1112: return function() {
1113: var result = [];
1114: filter(
1115: function(a) {
1116: if (!a[0]) result.push(a[1]);
1117: return a[0];
1118: },
1119: function() { return next(result); }
1120: )();
1121: return result;
1122: };
1123: };
1124:
1125: var levin_builder = function(matrix) {
1126: // Returns arrays of numbers based on their
1127: // probability, where the given matrix tells
1128: // us the probability of each symbol
1129: // based on the program so far. The
1130: // probability of ending the array is 1 -
1131: // the sum of the symbol probabilities.
1132: return informed_chooser(
1133: function(so_far) {
1134: var probs = matrix['['+so_far.join(',')+']'];
1135: var sample = Math.random();
1136: for (var i = 0; i < probs.length; i++) {
1137: if (sample <= probs[i]) return [false, i];
1138: sample -= probs[i];
1139: }
1140: return [true, probs.length];
1141: }
1142: );
1143: };
1144:
1145: var levin_search = c(function(matrices, step) {
1146: // How do we get the number of steps to take?
1147: return levin_builder(matrices());
1148: });
1149:
1150: var oops = c(function(symbols, step, test) {
1151: // Schmidhuber's "Optimal Ordered Problem
1152: // Solver". Similar to FAST, but remembers the
1153: // last successful program. When given a new
1154: // problem, it interleaves new programs with
1155: // continuations of the old program, to
1156: // potentially speed up the search.
1157: var solution_stream = fast(symbols, step);
1158: return filter(
1159: function(a) {
1160: if (test(a)) {
1161: solution_stream = interleave(
1162: map(
1163: concat(a),
1164: phases(
1165: function() {
1166: return enumerate(symbols);
1167: },
1168: counter()
1169: )
1170: ),
1171: fast(symbols, step)
1172: );
1173: return true;
1174: }
1175: return false;
1176: },
1177: function() {
1178: return solution_stream();
1179: }
1180: );
1181: });
1182:
1183: var adaptive_levin = function() {
1184: // Runs a Levin Search, but our probability
1185: // matrix is updated whenever we find an
1186: // acceptable solution.
1187: };
1188:
1189: var ratchet = function(stream) {
1190: // Always returns the best solution found so far
1191: var best;
1192: var fittest = -Infinity;
1193: return map(
1194: function(a) {
1195: if (a[0] > fittest) {
1196: fittest = a[0];
1197: best = a[1];
1198: }
1199: return best;
1200: },
1201: stream
1202: );
1203: };
1204:
1205: var exhaustive = c(function(stream, symbols) {
1206: // Makes the given search stream exhaustive by
1207: // taking every other result from a brute-force
1208: // enumeration of the given symbols
1209: return interleave([stream, enumerate(symbols)]);
1210: });
1211:
1212: var tabu = c(function(ns, stream) {
1213: // Remembers up to n previous results,
1214: // and only gives out a value if it's
1215: // not in it's remembered list. n is
1216: // drawn from ns on each call.
1217: var mem = [];
1218: return function() {
1219: var n = ns();
1220: while (mem.length > n) mem.shift();
1221: var val;
1222: do {
1223: val = stream();
1224: } while (mem.map(array_compare(val)).some(identity));
1225: mem.push(val);
1226: if (mem.length > n) mem.shift();
1227: return val;
1228: };
1229: });
1230:
1231: var innovator = function(stream) {
1232: // Remembers all previous values,
1233: // only gives out values it's not
1234: // seen before.
1235: // NOTE: Don't ask for more values
1236: // than there are in your domain.
1237: // For example, asking for 3 bits
1238: // will hang!
1239: return tabu(map(plus(1), counter()), stream);
1240: };
1241:
1242: var aixi = function(predictor, experimentor, inputs, rewards) {
1243: // AIXI, as defined by Marcus Hutter.
1244: // AIXI tries to give output which
1245: // maximises the rewards, using
1246: // information from the input stream.
1247: // First we try to build a model of
1248: // the input an reward streams, which
1249: // predictor is used for.
1250: // Once we have a good model, we find
1251: // a good output for the model using
1252: // experimentor.
1253: }
Generated by git2html.