1 /** Neuroevolution.
2 
3    See_Also: https://en.wikipedia.org/wiki/Neuroevolution
4 
5    TODO: Profile use of cellops and logops in a specific domain or pattern och
6    and use roulette wheel sampling based on these in future patterns.
7 
8    TODO: reuse bit_traits.packedBitSizeOf
9 
10    TODO: reuse `IndexedBy` `Cells` and `CellIx`
11 */
12 module nxt.nevo;
13 
14 @safe pure:
15 
16 /** Low-Level (Genetic Programming) Operation Network Node Types often implemented
17 	in a modern hardware (CPU/GPU).
18 
19 	See_Also: http://llvm.org/docs/LangRef.html#typesystem
20 	See_Also: http://llvm.org/docs/LangRef.html#instref
21 */
22 enum Lop
23 {
24 	summ,					   /// Sum.
25 	prod,					   /// Product.
26 	emin,					   /// Mininum.
27 	emax						/// Maximum.
28 }
29 
30 /** Obselete.
31 */
32 enum LOPobseleted
33 {
34 	id, /**< Identity. */
35 
36 	/* \name arithmetical: additive */
37 	/* @{ */
38 	add,					  /**< add (mi1o) */
39 	sub,					  /**< subtract (mi1o) */
40 	neg,					  /**< negation (1i1o) */
41 	/* @} */
42 
43 	/* \name arithmetical: multiplicative */
44 	/* @{ */
45 	mul,					  /**< multiply (mimo) */
46 	div,					  /**< divide (mi1o) */
47 	pow,					  /**< power (2i1o) */
48 	inv,					  /**< inverse (1i1o) */
49 	/* @} */
50 
51 	/* \name Harmonic */
52 	/* @{ */
53 	sin,					  /**< sine (1i1o) */
54 	cos,					  /**< cosine (1i1o) */
55 	tan,					  /**< tangens (1i1o) */
56 
57 	/* \name Inverse Harmonic */
58 	csc,					  /**< 1/sin(a) */
59 	cot,					  /**< cotangens (1i1o) */
60 	sec,					  /**< 1/cos(a) */
61 
62 	// Arcus
63 	acos,					 /**< arcus cosine (1i1o) */
64 	asin,					 /**< arcus sine (1i1o) */
65 	atan,					 /**< arcus tanges (1t2i1o) */
66 	acot,					 /**< arcus cotangens (1i1o) */
67 	acsc,					 /**< arcus css (1i1o) */
68 	/* @} */
69 
70 	/* \name hyperbolic */
71 	/* @{ */
72 	cosh, sinh, tanh, coth, csch,
73 	acosh, asinh, atanh, acoth, acsch,
74 	/* @} */
75 
76 	// /* \name imaginary numbers */
77 	// /* @{ */
78 	// real, imag, conj,
79 	// /* @} */
80 
81 	/* \name reorganizer/permutators/permutations */
82 	/* @{ */
83 	identity,				 /**< identity (copy) (1imo) */
84 	interleave,			   /**< interleave (1imo) */
85 	flip,					 /**< flip (1i1o) */
86 	mirror,				   /**< mirror (1i1o) */
87 	shuffle,				  /**< shuffle (1i1o) */
88 	/* @} */
89 
90 	/* \name generators */
91 	/* @{ */
92 	ramp,					 /**< linear ramp (2imo) */
93 	zeros,					/**< zeros (0imo) */
94 	ones,					 /**< ones (0imo) */
95 	rand,					 /**< ranodm (0imo) */
96 	/* @} */
97 
98 	/* \name comparison */
99 	/* @{ */
100 	eq,					   /**< equality (mi1o) */
101 	neq,					  /**< non-equality (mi1o) */
102 	lt,					   /**< less-than (2i1o) */
103 	lte,					  /**< less-than or equal (2i1o) */
104 	gt,					   /**< greater-than (2i1o) */
105 	gte,					  /**< greater-than or equal (2i1o) */
106 	/* @} */
107 
108 	/* \name logical */
109 	/* @{ */
110 	all,					  /**< all (non-zero) (mi1o) */
111 	any,					  /**< any (non-zero) (mi1o) */
112 	none,					 /**< none (zero) (mi1o) */
113 	/* @} */
114 }
115 
116 version (none)
117 {
118 /** Return non-zero if \p lop is an \em Arithmetical \em Additive Operation. */
119 bool isAdd(Lop lop)
120 {
121 	return (lop == Lop.add ||
122 			lop == Lop.sub ||
123 			lop == Lop.neg);
124 }
125 
126 /** Return non-zero if \p lop is an \em Arithmetical \em Additive Operation. */
127 bool isMul(Lop lop)
128 {
129 	return (lop == Lop.mul ||
130 			lop == Lop.div ||
131 			lop == Lop.pow ||
132 			lop == Lop.inv);
133 }
134 
135 bool isArithmetic(Lop lop)
136 {
137 	return isAdd(lop) && isArithmetic(lop);
138 }
139 
140 /** Return non-zero if \p lop is an \em Trigonometric Operation. */
141 bool isTrigonometric(Lop lop)
142 {
143 	return (lop == Lop.cos ||
144 			lop == Lop.sin ||
145 			lop == Lop.tan ||
146 			lop == Lop.cot ||
147 			lop == Lop.csc ||
148 			lop == Lop.acos ||
149 			lop == Lop.asin ||
150 			lop == Lop.atan ||
151 			lop == Lop.acot ||
152 			lop == Lop.acsc
153 		);
154 }
155 
156 /** Return non-zero if \p lop is an \em Hyperbolic Operation. */
157 bool isHyperbolic(Lop lop)
158 {
159 	return (lop == Lop.cosh ||
160 			lop == Lop.sinh ||
161 			lop == Lop.tanh ||
162 			lop == Lop.coth ||
163 			lop == Lop.csch ||
164 			lop == Lop.acosh ||
165 			lop == Lop.asinh ||
166 			lop == Lop.atanh ||
167 			lop == Lop.acoth ||
168 			lop == Lop.acsch);
169 }
170 
171 /** Return non-zero if \p lop is a \em Generator Operation. */
172 bool isGen(Lop lop)
173 {
174 	return (lop == Lop.ramp ||
175 			lop == Lop.zeros ||
176 			lop == Lop.ones ||
177 			lop == Lop.rand);
178 }
179 
180 /** Return non-zero if \p lop is a \em Comparison Operation. */
181 bool isCmp(Lop lop)
182 {
183 	return (lop == Lop.eq ||
184 			lop == Lop.neq ||
185 			lop == Lop.lt ||
186 			lop == Lop.lte ||
187 			lop == Lop.gt ||
188 			lop == Lop.gte);
189 }
190 
191 /** Return non-zero if \p lop is a \em Permutation/Reordering Operation. */
192 bool isPermutation(Lop lop)
193 {
194 	return (lop == Lop.identity ||
195 			lop == Lop.interleave ||
196 			lop == Lop.flip ||
197 			lop == Lop.mirror ||
198 			lop == Lop.shuffle);
199 }
200 }
201 
202 /// Cell Operation.
203 enum CellOp
204 {
205 	seqClone,				   /// sequential clone
206 	parClone,				   /// parallel clone
207 }
208 alias CellOps = Owned!(DynamicArray!CellOp); /+ TODO: bit-pack +/
209 
210 /**m Network (Transformation) Operation Type Code.
211  *
212  * Instructions for a Program that builds \em Computing Networks (for
213  * example Artificial Nerual Networks ANN).
214  *
215  * TODO: What does \em nature cell this information bearer: Closest I
216  * have found is http://en.wikipedia.org/wiki/Allele.
217  */
218 enum Gop
219 {
220 	/* \name Structural: Inter-Node */
221 	/* @{ */
222 	seq,					/**< Sequential Growth. Inherit Initial Value. Set weight to +1. State is \em ON. */
223 	par,					/**< Parallel Growth */
224 
225 	clone,				  /**< Clone. Like \c PAR but  */
226 	/* @} */
227 
228 	/* \name Local: Intra-Node */
229 	/* @{ */
230 	setLOp,				/**< Set Node Logic Operation (see \c Lop). */
231 
232 	setOType, /**< Set Out-Type. Either \c int, \c float or \c double for now. */
233 
234 	incBias,			   /**< Increase Threshold */
235 	decBias,			   /**< Decrease Threshold */
236 
237 	/* There is \em no need for "in-precision", since these are the same
238 	   as in-precision the "previous" nodes in the network. */
239 	incOpRec,			  /**< Increase Out-Precision */
240 	decOpRec,			  /**< Decrease Out-Precision */
241 
242 	incLinkreg,			/**< Increase In-Link-Register */
243 	decLinkreg,			/**< Decrease In-Link-Register */
244 
245 	on,					 /**< \em Activate Current In-Link. */
246 	off,					/**< \em Deactivate Current In-Link. */
247 
248 	/* @} */
249 
250 	wait,				   /**< Wait (Delay) one clock-cycle? */
251 	rec,					/**< \em Recurse up to top (decreasing life with one). */
252 
253 	jmp,					/**< \em Jump to sub-Network/Procedure/Function. */
254 	def,					/**< \em Define sub-Network/Procedure/Function. */
255 
256 	end,					/**< \em Recursion Terminator in serialized code (stream of t's). */
257 	null_,				   /**< \em Network Terminator in serialized code (stream of t's). */
258 }
259 
260 // wchar
261 // wchar_from_LOP(Lop lop)
262 // {
263 //	 wchar_t wc = UNICODE_UNKNOWN;
264 //	 switch (lop) {
265 //	 case Lop.add: wc = UNICODE_CIRCLED_PLUS; break;
266 //	 case Lop.sub: wc = UNICODE_CIRCLED_MINUS; break;
267 //	 case Lop.neg: wc = UNICODE_SQUARED_MINUS; break;
268 //	 case Lop.mul: wc = UNICODE_CIRCLED_TIMES; break;
269 //	 case Lop.div: wc = UNICODE_CIRCLED_DIVISION_SLASH; break;
270 //	 case Lop.pow: wc = UNICODE_UNKNOWN; break;
271 //	 case Lop.inv: wc = UNICODE_CIRCLED_DIVISION_SLASH; break;
272 //	 default: break;
273 //	 }
274 //	 return wc;
275 // }
276 
277 import std.bitmanip : BitArray;
278 import std.random : Random, uniform;
279 
280 import nxt.container.dynamic_array : DynamicArray;
281 import nxt.container.dynamic_array : DynamicArray;
282 
283 import nxt.typecons_ex : IndexedBy;
284 import nxt.owned : Owned;
285 
286 import nxt.variant : FastAlgebraic;
287 
288 alias Data = FastAlgebraic!(long, double);
289 alias Datas = Owned!(DynamicArray!Data);
290 
291 /// Scalar Operation Count.
292 alias OpCount = size_t;
293 
294 /// Relative Cell index.
295 alias CellRIx = ptrdiff_t;
296 
297 /// Relative Cell indexs.
298 alias CellRIxs = Owned!(DynamicArray!CellRIx);
299 
300 /// Calculating Cell.
301 struct Cell
302 {
303 	import std.algorithm.iteration : map, filter, fold;
304 
305 	@safe pure:
306 
307 	this(Lop lop, size_t inputRIxsLength, size_t cellCount)
308 	{
309 	}
310 
311 	/// Randomize a cell.
312 	void randomize(Lop lop, size_t inputRIxsLength, size_t cellCount) @trusted
313 	{
314 		auto gen = Random();
315 		this.lop = lop;
316 
317 		/+ TODO: use std.algorithm to fill in `inputCellRIxs` +/
318 		inputCellRIxs.length = inputRIxsLength;
319 		foreach (ref rix; inputCellRIxs[])
320 		{
321 			rix = uniform(cast(CellRIx)0, cast(CellRIx)cellCount/10, gen);
322 		}
323 	}
324 
325 	nothrow:
326 
327 	OpCount execute(const ref Datas ins, ref Datas outs) const
328 	{
329 		if (ins.empty) { return typeof(return).init; }
330 		final switch (lop)
331 		{
332 		case Lop.summ: return summ(ins, outs);
333 		case Lop.prod: return prod(ins, outs);
334 		case Lop.emin: return emin(ins, outs);
335 		case Lop.emax: return emax(ins, outs);
336 		}
337 	}
338 
339 	/// Sum of `ins`.
340 	OpCount summ(const ref Datas ins, ref Datas outs) const @trusted
341 	{
342 		import std.algorithm.iteration : sum;
343 		outs.length = 1;
344 		outs[0] = ins[].filter!(_ => _.hasValue)
345 					   .map!(_ => _.commonValue)
346 					   .sum();
347 		return ins.length - 1;
348 	}
349 
350 	/// Product of `ins`.
351 	OpCount prod(const ref Datas ins, ref Datas outs) const @trusted
352 	{
353 		outs.length = 1;
354 		outs[0] = ins[].filter!(_ => _.hasValue)
355 					   .map!(_ => _.commonValue)
356 					   .fold!((a, b) => a * b)(cast(Data.CommonType)1.0);
357 		return ins.length - 1;
358 	}
359 
360 	/// Minimum of `ins`.
361 	OpCount emin(const ref Datas ins, ref Datas outs) const @trusted
362 	{
363 		import std.algorithm : minElement;
364 		outs.length = 1;
365 		outs[0] = ins[].filter!(_ => _.hasValue)
366 					   .map!(_ => _.commonValue)
367 					   .minElement(+Data.CommonType.max);
368 		return ins.length - 1;
369 	}
370 
371 	/// Maximum of `ins`.
372 	OpCount emax(const ref Datas ins, ref Datas outs) const @trusted
373 	{
374 		import std.algorithm : maxElement;
375 		outs.length = 1;
376 		outs[0] = ins[].filter!(_ => _.hasValue)
377 					   .map!(_ => _.commonValue)
378 					   .maxElement(-Data.CommonType.max);
379 		return ins.length - 1;
380 	}
381 
382 	Lop lop;				  /// operation
383 	CellRIxs inputCellRIxs;   /// relative indexes to (neighbouring) input cells
384 }
385 alias Cells = IndexedBy!(Owned!(DynamicArray!Cell), `Ix`);
386 
387 /// Network/Graph of `Cells`.
388 struct Network
389 {
390 	@safe pure /*TODO: nothrow @nogc*/:
391 
392 	this(size_t cellCount)
393 	{
394 		auto gen = Random();
395 
396 		cells.reserve(cellCount);
397 		temps.reserve(cellCount);
398 
399 		foreach (immutable i; 0 .. cellCount)
400 		{
401 			cells ~= Cell(gen.uniform!Lop, 10, cellCount);
402 			temps ~= Data(gen.uniform!long);
403 		}
404 	}
405 
406 	/// One step forward.
407 	OpCount step() @trusted
408 	{
409 		typeof(return) opCount = 0;
410 
411 		foreach (immutable i, ref cell; cells)
412 		{
413 			Datas ins;
414 			ins.reserve(cell.inputCellRIxs.length);
415 			foreach (immutable rix; cell.inputCellRIxs)
416 			{
417 				ins ~= temps[(i + rix) % cells.length]; // relative index
418 			}
419 
420 			Datas tempOuts;		 // data to be filled
421 			if (immutable opCount_ = cell.execute(ins, tempOuts))
422 			{
423 				opCount += opCount_;
424 				temps[i] = tempOuts[0];
425 			}
426 		}
427 		return opCount;
428 	}
429 
430 	BitArray pack() nothrow @nogc
431 	{
432 		typeof(return) bits;
433 		return bits;
434 	}
435 
436 	static typeof(this) unpack(in BitArray bits) nothrow @nogc
437 	{
438 		typeof(this) that;
439 		return that;
440 	}
441 
442 	Cells cells;				/// operation/function cells
443 	Datas temps;				/// temporary outputs from cells
444 }
445 
446 /// Generative Code.
447 struct Code
448 {
449 	@safe pure nothrow:
450 
451 	CellOps cellOps; // cell operations, an indirect generative network encoding
452 	alias cellOps this;
453 
454 	Cells.Ix writerIxs;		 /// index to writers
455 
456 	Network generate() const
457 	{
458 		typeof(return) network;
459 		foreach (immutable cellOp; cellOps[])
460 		{
461 		}
462 		return network;
463 	}
464 }
465 
466 unittest {
467 	immutable cellCount = 1_000;
468 	auto task = Network(cellCount);
469 
470 	immutable stepCount = 1_0;
471 	foreach (immutable i; 0 .. stepCount)
472 	{
473 		task.step();
474 	}
475 
476 	// dbg("DONE");
477 }