The Minkowski's challenge

As a note, you may be able to use some of us who are savvy enough to get your code running on our machines to help with replication of the process. I for one volunteer as I find all of this very facinating. I took a healthy interest in architecture and designed a theoretical architecture similar to the ARM during the last semester of my undergrad work.In addition, if you have enough time to make us familiar with your implementation we may be able to contribute improvements.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

Percy may also have some coding work what needs greater expertise and time than some of us peonies can manage. Do I hear a volunteer?

---

Aslan is not a Tame Lion

I don't see why not. I have thought about it before but it was during the time that my wife was pregnant. Now that my son is 8 months old I am starting to get back some semblance of free time.It wouldn't hurt to mention it to Percy to see if he could use my services. At the very least I could take a look at the TODO list and see if I have any relevant expertise such that I even COULD contribute in a meaningful way. A lot of what I do is more inline with what Barbarian is working on than the Web 2.0 sort of skills necessary to run a message board.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

Right now he is trying to get his new pc to see a second sata drive, but he said he will pick on you as soon as that is solved.

---

Aslan is not a Tame Lion

Thanks for volunteering, folks.Thinking about the best cutting point in the project, I think it will come when the framework is complete and experimentation with selector/fitness rater sequences can begin; we can then try parallel experiments, everyone with his/her preferred selectors. I am so close to completion that I don't think I can efficiently involve anyone instead of just sitting down and finishing it (this is a long weekend, Monday is a national holiday here and bad weather was promised).Selectors will have to be hard-coded and the whole framework recompiled for them to work, so whoever volunteers to find proper evolutionary pathways will either have to write OCaml code or give me the specification of the preferred selector and compile the code I provide in return. As a preparatory measure, I think you could try to download and install the OCaml distribution. Those on Linux or other Posixoid systems with a C compiler and a basic 'make' will have it easy, but those on Windows will need Cygwin+GCC+GNU Make for running real experiments. One can play with the full functionality of the framework on Windows even in the absence of Cygwin GCC; it's just the optimizing compiler, needed for the millions-of-instructions-per-second class of performance, that won't work without it. OCaml provides another optimizing compiler relying upon the Microsoft compiler suite, but I am not well-versed enough in the use of its 'make' functionality to support it.I plan to simply release the source code into public domain, and I welcome any ideas about how to physically do this, given that I do not have a website on which to post it. Right now the code contains no comments whatsoever, but adding them should be easy and fast, and of course I plan to do it before publishing.

Taking a quick peek it doesn't look too bad. It has been awhile but I am familiar with LISP/Scheme and ML. I may be a little rusty in a functional language but it would be fun to dive in. My Gentoo machine just lost its motherboard (I think) but I would be suprised if OCaml was not in the portage tree. If I don't get that machine working by this weekend I'll try to install it in cygwin on my gaming rig. Lets ask Percy if he would be so kind as to host it here. If not I volunteer to host it. I need to check but I may even be able to set you up with a shell account via my hosting service.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

Ah comments, they can be good.* You are not expected to understand this.

---

Aslan is not a Tame Lion

I can host, but the next couple weeks aren't good for me time-wise.--Percy

Thanks in advance for the offered help wrt hosting; some delay is even welcome, since I just realized I need to reimplement population management over a new data structure to speed it up, as it turns out to be the slowest part of the framework. I thought I could implement populations using the Map and Set structures from the OCaml library, but what is needed here is a somewhat modified variant of binomial (min)heaps (which essentially reflects the fact that the populations are actually priority queues with programs queueing up in them waiting for extinction, reverse prioritized by their fitness values - I find this funny but also very helpful, as it just feels to be the proper paradigm). Otherwise only the read-eval cycle and save/restore functionalities are to be implemented, and we are set to go.

Short update on the project.I am at the final step of connecting up the main command reader-interpreter-result printer loop with the already coded procedures. IOW I can already compile a complete framework, only that some commands do nothing except telling me they aren't yet executed. The code they will execute is there already, only they are not linked up. Should be ready by the end of the week, and then serious testing can begin - probably another week or so.The framework has a command prompt interface only, with very rudimentary control over the amount of information dumped at request, e.g. there's no paging of any kind; to help this situation, I use it from within an Emacs shell. I might later create a dedicated Emacs mode for it based on comint, mostly because assembler error messages are of the "something is wrong somewhere in the code" variety, and proper syntax highlighting would help a lot in spotting syntax errors.I have said before that saving and loading of workspaces would be the biggest challenge I see ahead of me. Well, it is done now, but I had to implement my own stream tokenizer for it, in order to allow me to distribute the load and save functionalities between modules. The main issue to be solved was that the workspace is pretty redundant while residing in memory (speedup tricks et al). Now this redundancy does not hurt me because I took care to share structures whenever possible, but such sharing is destroyed both by the standard - binary - dump/reload mechanism (Marshal) in the OCaml library and by the straightforward visit-all-nodes type saving. This would bloat the saved state file and would result in hitting an out-of-memory condition when loading a saved state on the same machine it was saved. So I had to implement an explicit management of structure sharing. There are libraries out there which do this, but I want to keep everything workable with just the basic distribution of OCaml, so I could not use them. The saved state is a pure text document, just for the paranoid who would want to check what kind of files are written by the framework. I certainly would want to do so.I was trying to find a good data structure for populations, and was toying with binomial heaps for about a week, in what turned out to be a severe bout of overengineering. Careful analysis showed that the best amortized complexity is given by simple sorted lists, assuming that sorting is strategically delayed. Experiments supported this idea, so now I have the most primitive collection type - linked lists - holding the populations.I claimed before that for a finite upper bound of representable values the language does not look like being Turing-complete. That turned out to be false: I have found a way to implement any Turing machine in the language, capitalizing on unboundedness of segment count alone. So, the language is Turing-complete as it stands.Writing new selectors should be easy. You have to specify the name (an unique identifier), the description and the fitness rater function. The fitness rater receives a program and returns an integer - there are utilities to decide if the program can write an exact copy of itself and to assemble a histogram of SPECINSTR calls made during a run. The framework needs to be recompiled for a new selector to start working; earlier saved states can be reloaded into the framework after such a recompilation, unless some already used selector was changed - then the results are unpredictable. I will provide a template for doing all this in a clean way.The toy world consists of a chain of populations, each population with its own dedicated selector. The first population can only grow by procreation of members and admission of programs from external files; all subsequent populations can only grow by procreation of members and admission of newly admitted members of the previous population. Populations can be added to the end of this sequence at any time, immediately loaded with the members of the previous population. Any number of populations can be cut from the beginning of the chain, such that some population from the middle becomes the first one. After any such cut, it is no longer possible to admit programs from external files into the first population.Populations hold different genotypes, and are thus limited in diversity, not in count of individuals. Every genotype is present only once, but gets a number of chances to procreate - with a mandatory mutation - equal to its fitness value. In addition, the unchanged parent is also admitted into the next generation. If a population grows beyond its size limit - which is independently settable for every population - then it is cut back to size by removing individuals with the lowest fitness values. One can run the framework with a number of desired generations (full updates along the population chain) or until a certain threshold of fitness value is reached within a certain population. The program can be interrupted from the keyboard, stopping in the latest consistent state.

Why is this? Is is just that previously conserved elements will no longer be conserved or is there some mechanical reason things will become unpredictable? One of the things that may be necessary to get the desired result it to change a selector. Is that possible or are you concieving that a change in a selection behavior can always be achieved by the creation of a new selector.

---

Of course, biblical creationists are committed to belief in God's written Word, the Bible, which forbids bearing false witness; --AIG (lest they forget)

quote:

---

Why is this? Is is just that previously conserved elements will no longer be conserved or is there some mechanical reason things will become unpredictable? One of the things that may be necessary to get the desired result it to change a selector. Is that possible or are you concieving that a change in a selection behavior can always be achieved by the creation of a new selector.

---

I have to start from afar to explain this. I could not make up my mind about the proper use of multiple selectors: should they be applied to a single population one after the other, allowing a fair bit of evolution to happen under each one (geological age approach) or should they coexist as a chain, each accepting migration from the previous one (migration between ecosystems approach)? So I chose a generalization of both (described in my previous post). In this approach, if you alter a selector, you are supposed to scrap the associated population and all populations coming after it, because you want to be able to repeat the whole evolutionary exercise multiple times, and you either cannot do that because the scrapped version of the selector is necessary for some phase, or you can do that but then you better make sure you can indeed, by repeating the evolution of subsequent populations. This being the case, I decided not to try to deal with validation issues and simply assume that the selector behind a certain identifier is invariant. Right now changing the selector would not technically break stuff (although the evolutionary pathway could be rendered un-repeatable - the old selector could be required for a certain phase), but as the application keeps being changed, and I will not care about validation, there's no telling what could happen - this is why I said that the results will be unpredictable.The way I expect the framework to be used is this: figure out an evolutionary pathway, described by a sequence of selectors. Implement all selectors. Create a world with a single population under the control of the first selector. Start evolution. If the required results are showing, add a second population after the first, controlled by the second selector. Continue evolution, ... and so on. As soon as practical, cut off populations from the beginning to save evaluation time. If at some phase you realize that a selector is buggy or just apt to drive evolution towards the wrong goal - this will most likely happen in the last population - then you fix the selector and scrap the population obtained with the wrong selector variant (either implicitly, by reloading the state saved just before the population with the faulty selector was added, or explicitly, if I add a DropLastPopulation command).There are exceptions. If the saved state does not contain populations referring to the selector, then the selector can be freely changed. (Indeed, this is the way I expected it to happen: you change the selector and continue with an early save of the state.) The implementation of a selector can of course be changed at any time if the changes preserve its functionaility (i.e. for the same program it will return the same rating).

Like the title says. I have committed the first full version back into the version control system. (12 source files, 3082 total lines, 81537 total characters.) testing + code sanitizing + adding comments should not take more than the next two weeks; after that the code will be ready to share and experiment with - make it evolve encryption, that sort of thing.

I am not doing well.I have an evasive bug, which takes ages to manifest itself even in the native code executable, and is therefore likely to need weeks of continuous running in the interpreted version (which is a problem because the debugger only understands the latter). Obviously, I have to revert to other means to find it, and this will take some more time.Overall performance is good but not as good as I expected it to be. Profiling shows that the largest chunk of time (about 15%) is spent in runtime system functions managing memory allocation and deallocation; no function of mine uses more than 1% of total time, so on one hand this means I am good at before-the-fact optimization, on the other hand I have no handle on further speed improvements.Apart from that, the stuff works pretty well. According to ancient custom, I have tried to evolve the shortest self-replicating program and got it quite quickly:

prog
     *
     specinstr 0
     specinstr 1
   end

It really sounds like the shortest possible variant.

If you're spending a lot of time constantly allocating/deallocating same-sized blocks, create your own free-list of these blocks. Still, you say that's only 15% of the total, which means it's a meager performance opportunity.What are the other major performance consumers?For no local function to take more than 1% sounds extremely unusual. Especially in so repetitive an application you would expect a fairly expensive core. Are you sure of your profiling results?--Percy