Subfunctions

[Greven]

What about some kind of jump/goto/gosub-command? I know this will difficult to implement, but we some carefull thoughts, this could be very very powerfull to and making the genome more non-linear!!!??

[Numsgil]

I've been thinking about adding sub functions and functions, and the like, and a major problem I can see is infinite loops.  If a sub calls itself, that is a recursive call, it could freeze the program.  Or if three functions call each other creating a loop.  Once we approach the possibility of loops alot of problems spring up that I don't know how to fix.

[Greven]

I am against caps of any sort in DB, but sometimes it could be nessicary. We could say that a bot only can make x calls in any given cycle or make it cost a lot, so many would kill it? As you said in another thread, only time will let us get the optimal solution. (or something like it)

[Numsgil]

We could prevent bots from calling sub functions from inside sub functions.  That is, limit the nesting capability to one level.

Or two levels, or three levels.  Probably three levels is good enough.  We can set it as a hard limit or chose a different method if we like, but three deep should be the limit.

So instead of X calls per cycle, you can only make X calls without reaching the end of the sub function.  That would work well I think.

Then the problem becomes how to address the new functions without drastic alterations to the DNA.  One solution I can see is 'storing' these functions in memory addresses.

Then if you do *600 you're not putting a memory location onto the stack, but making a call to a sub function.  Kind of like a pointer to a function in C, for people who are familiar with C.  That way mutations can get to existing sub functions easily enough.

You probably won't be able to overwrite sub function memory locations.  Or amybe you can and then you just lose that sub function in the nether regions of the bot's DNA.

On the other hand, it may or may not be biologically realistic.  Definately an interesting idea to explore.

[Numsgil]

On to another topic, I've been looking at the possibility for subprograms.  I think the cost of calling a subprogram should be (Some user defined constant) * sum of (x^n/3^n) for n = 0 to 7 and x = how many calls you've made without returning - 1 (since we start at the 0th n).

So the first call costs 1 nrg.  The next call costs 1.5.  Then: 3, 8.6, 29,93.  The absolute maximum number of calls without returning you can make is 12.  The 13th call costs 47000 nrg, which is strictly impossible.

That ensures that infinite loops are impossible (assuming that the program checks for bot death before it gets to that point).  It also penalizes infinite loops without drastically hurting bots that just want to make a few calls without going deep into the tree.

Like this:

'this would assign a free memory location not taken
'by sysvars as a pointer to the sub function
def sub1 as function

REGULAR PROGRAM CODE
.sub1 call
REGULAR PROGRAM CODE
end

sub1 : 'this tells the program we're defining our sub function now
'Do some math
.sub1 *50 mult call
return '(or maybe end, or stop, or ret, I'm not sure about the syntax yet)
'returns us back to the segment of DNA that called us.

The bot would call sub1 somewhere in its DNA.  sub1 could then execute recursively for up to 12 loops before it would kill the bot.  It would stop if 50 is ever not zero (that would change where the call command is trying to call, and so the call command would fail.

However, if a bot sets 50 to 1 befoe making the calls, the bot could make up to 32000 calls (at 1 nrg each) since the sub function won't be executing other sub functions.

I'm not sure if sub functions should be able to put things on the stack, put things on the condition stack, or write to memory locations (or all of the above).

I could implement "call" as a 'jump to the xth DNA unit and place location in DNA on the calling stack' and "return" as 'jump back to the yth DNA unit where y is on the calling stack'.  Then the DNA is more likely to mutate to use it.

Also means the function pointer can be used as a regular custom variable.

[shvarz]

Uhm, this is way over my head, talk to PY or someone :)

I'm a little concerned that if a program works through some loops and jumps then a lot more mutants will become dead.  Any insertion/deletion would mess up the whole thing.  I think the reason why DBs code is so mutable is because it exists in small chunks that are independent from each other.  Mutate one - others still work fine.  But then again I am not a programmer, so I may well be wrong.

[Greven]

Num I think we need a new thread on the goto/jump/call/etc. issue!

[Greven]

I'm a little concerned that if a program works through some loops and jumps then a lot more mutants will become dead. Any insertion/deletion would mess up the whole thing. I think the reason why DBs code is so mutable is because it exists in small chunks that are independent from each other. Mutate one - others still work fine. But then again I am not a programmer, so I may well be wrong.

I understand you concern shvarz, but I think it should be evolutions job to select against this, but I think we need to discuss this to make the syntax as easy as possible, so it wouldnt be to difficult for evo to evolve this!

[Numsgil]

I'm a little concerned that if a program works through some loops and jumps then a lot more mutants will become dead. Any insertion/deletion would mess up the whole thing. I think the reason why DBs code is so mutable is because it exists in small chunks that are independent from each other. Mutate one - others still work fine. But then again I am not a programmer, so I may well be wrong.

I understand you concern shvarz, but I think it should be evolutions job to select against this, but I think we need to discuss this to make the syntax as easy as possible, so it wouldnt be to difficult for evo to evolve this!

I agree, if the bot mutates such that it never reachest the end of its DNA, it will die.  But there are lots of mutations that are lethal.  The trick is just to reproduce at low energy amounts, so the vested energy in each kid is low.

Subfunctions could probably take values from the stack, making them a custom command.  Then the other commands, the more complex ones, can be made into subfunctions that themselves are capable of being mutated, and will also cost the bot energy based on complexity.   (A ceil uses much less advanced commands than a pyth, so it would make less nested subfunction calls).  The only problem is in mutating new commands, and representing the new commands somehow.

[Carlo]

I agree with Shvarz. There's no need to add to the language things which you can already obtain with the actual language. A few points to remember you WHY the actual language works the way it works:

1) the activation condition/ body model resembles vaguely that of dna. It is believed that the genome works as a giant network of reciprocally influencing genes; many alife simulations use neural or similar networks as a dna; the DB language is not much different, in that it allows you to design networks of genes activations. The advantage of the DB language over networks is that you can directly program a DNA, and that you can understand (with some effort) how a mutated DNA works.

2) the dna language has been designed to have a syntax reduced to the bone. This is because dnas are going to be randomly mutated, and a random mutation which breaks the code's syntax is just a waste of time. So, the syntax is very very simple, the only requirement is to preserve the cond start stop structure and to put comparison operators and commands in their respective place (that is, in the cond part and in the body part, respectively). There are no other rules.

3) the dna language has been designed to ensure a fair distribution of computational time between robots. The alife simulators allowing a traditional language, Tierra and Avida (I.e., they allow loops and subroutines) solve the problem of the distribution of cpu resources allowing each organism to execute only a precise number of _single instructions_ per cycle. The DB language allows the execution of the entire dna. You can have loops, but you have to split them in different cycles.

4) the resulting language is Turing-complete, in the sense that you can express with it whatever you can express with every other, more complex, language.


So, I perfectly agree with Shvarz. You can already do everything in the current language and whatever you may add to it will make it more difficult to mutate and decrease its evolvability. As for the subroutines (without cycles of any kind): they may be comfortable, but there's nothing you can't do with the actual system. Subroutines would create new problems, because they would break the linearity of the dna execution. They would be substantially macros, separated from the rest of the dna. Why don't you write an external compiler instead? Write a standalone program which receives as input a program in a more "comfortable" version of the DB language and produces a dna as an output. Could be very interesting from the point of view of programming combat bots.

Some other considerations:

I'd agree on making the syntax even looser by allowing to mix cond, start and stop everywhere in the code, as well as allowing the use of comparison operators and instructions everywhere. But this would be, after all, a minor change (and it would make the code much much more difficult to read).

I don't understand why you want so much to have junk dna. JUnk dna is dna which is not used and has no use. Being not used, it will become a total junk and will never by usable again thanks to a mutation. So its size will always increase, never decrease, and will never be useful to evolution. So tell me why you want junk dna so much (leaving apart the fact that there's already junk dna).

[Greven]

I don't understand why you want so much to have junk dna. JUnk dna is dna which is not used and has no use. Being not used, it will become a total junk and will never by usable again thanks to a mutation. So its size will always increase, never decrease, and will never be useful to evolution. So tell me why you want junk dna so much (leaving apart the fact that there's already junk dna).

I must disagree on this one! Yes junk DNA is just non-functional DNA, but can you explain how a simple single celled bacteria became a human, without taking junk DNA into account? No you can not!

DNA didnt shuffled the DNA back and forth to find a mutation that would prove a little benefical, instead entire strings of the junk DNA became functional, often this would lead to dead of the individual, but a few times this would lead to an increase in fitness for the organism.

In the history of evolution, often there were huge jumps in the species, with no direct link between the ancestor and the current specie, how would you explain that? God's work?
 
Funny enough this aspect is supported by many ALife simulations, were there are small changes of the genome over a very long time and suddenly big mutations take place over a very very short time! This must be junk DNA becoming somewhat usefull, read some of the articles of Avida and/or Tierra to get more infomation.

[Greven]

Regarding my own post above!

It is not as simple as I state it, many things needs to considered, but it is one of the few things at play!

[Numsgil]

I agree with all the points you listed, Carlo, but how I interpret them into modding the language is different.

An external compiler would work just fine, and indeed is an option for non-looping subroutines (just simple macros) and other things we want to add to the language.  But I hate the idea of having access to something the bots don't.

I can see this working two ways.  In the first model, DNA is deconstructed into the most basic commands (ie: cond, start, stop, end, add, sub, mult, dec, inc, store, etc.) from higher level commands.  Mutations are much more focused, by simple fact that there are fewer commands possible to mutate.

In the second model, the higher level commands are supported by the language intrinsically, and mutations are allowed to use them.  Mutations tend to be less focused since there are fewer basic commands and more specialized ones.

I would support an in-game toggle between how the program compiles the code of an imported bot and runs mutations.  Bots would run the same in either system (assuming all higher level functions are able to be constructed from lower level ones) so it would only really effect how mutations run.

When the program reads back the DNA, it needs to have something which can clearly identify what is Junk and what is actually being run.  Perhaps some color coding scheme can be implemented.

Why I want junk DNA is the simple fact that real eukaryotic organisms have it.  It may offer increases in fitness, it may not.  No one has really devised a long term experiment to find out, so no one can say one way or another.

I'm trying as hard as I can to make diploid multibots that sexually reproduce and swim around supported by the system.  I don't want to just have a toggle for eukaryote to protist.  I want each part to be independant and functional, and then have bots assemble the individual parts on their own.  That is, I want the bots to spontaneously assemble themselves into multibots and colony organisms.

The jump from eukaryote to protist was rather large and quite sudden.  There were so many changes at once that it's difficult to see what were beneficial, which were consequential, and which were just random.  So I'm just going to allow all of them to be modeled and hope for the best.

[Carlo]

An external compiler would work just fine, and indeed is an option for non-looping subroutines (just simple macros) and other things we want to add to the language.  But I hate the idea of having access to something the bots don't.

Well, you can always create an interface on the compiler so that the bots can swim in it and play with its commands.   :lol:
Anyway, the bots don't need to play with the compiler because there's nothing the compiler can do that they can't. The compiler is just an useful instrument for you to _see_ dnas in a more comfortable way. But evolution don't need to see anything.

Why I want junk DNA is the simple fact that real eukaryotic organisms have it.  It may offer increases in fitness, it may not.  No one has really devised a long term experiment to find out, so no one can say one way or another.

These days seems more and more probable that junk dna has some important regulatory functions inside the genome. Someone has even calculated that the apparent complexity of living organisms is more related to the amount of junk dna in their dna than to the quantity of actual genes.
But this is probably because real junk dna is not so junky, and has some active role in the chemical processes that make the cells work. This means that it does something, while junk dna in DB doesn't do anything. You can add as much junk dna as you please in DB, it won't do anything because it is not even interpreted. There isn't as far as I know any hidden function inside DB that will magically use junk dna to boost evolution.

I'm trying as hard as I can to make diploid multibots that sexually reproduce and swim around supported by the system.

I think that the main problem of sexual reproduction in darwinbots isn't the diploidy (yes, that's one problem, and I clarly feel that's something wrong in the actual sexrepro function; but on the other hand I'd like to know _exactly_ what's wrong with it. Remember that diploidy requires crossing over anyway, this means you have to split the two chromosomes and mix them). Anyway, the main problem of sexual reproduction in DB is the fact that sexual reproduction is a complex thing. Requires a good communication, a good synchronization, time... yes, a comfortable place... How can you find a partner, decide to mate, mate, wait for sons, in an environment in which 10 cycles are an eternity, and you can be hit by anybody and pushed far away? There's something wrong with time in DB. Physics is too fast with respect to internal dna timing.

By the way, this reminds me of the ND debate. You said you were going to add ND routines and a checkbox control to select for ND execution.Can I send you those routines to integrate in the next version?

[shvarz]

I'll start a separate post on junk DNA in "Biology" section so that we can discuss it there.

For now I just want to say that there is two reasons why I want to have junk DNA in DBs (and by junk I mean DNA that is neither in cond or in executable parts of a gene).
1. As far as I can tell, no other AL sim ever tried to simulate effect of junk DNA.  It would be interesting to see the effects.  It is not going to forever increase as Carlo suggested, because deletions will control the size of it  - the more junk DNA you have the more often deletions will happen in that DNA.  So, there is going to be some steady-state level of junk DNA and it might be interesting to see what that level would be and what kind of effects on evolution it may have.
2. It allows an additional kind of mutations: those involving start, stop, cond, else.  Say you have a gene:

cond
start
1
2
3
4
5
6
7
8
stop

Right now there is no way to shorten this gene to the first four steps and still keep the last four somewhere.  With these new mutations it is possible to get mutation like this:

cond
start
1
2
3
4
stop
5
6
7
8
stop

So, the original gene is shortened but all that good code is not lost - it is still there.  It can be moved around and attached to some other gene, or it can become a completely new gene.  With current system it is impossible.


Of course, the problem is that in DBs the mutation rate is fairly high, so any non-epressed DNA will go to crap quickly.  I am aware of this and I think I have a solution, but I don't want to talk about it yet to avoid going away from the original topic.