Self-replicating, self-modifiying scripting language

LISP. But the semantics are easily broken by random mutations.

I've personally worked on a mutation-resistant language based on forth to perform simulated annealing, I guess you could adapt code-manipulation primitives to the stack-based skeleton (perhaps using ideas from here).

Check Tierra. http://life.ou.edu/tierra/

Yes, I got started on this idea of the "3D" scripting language from some flowchart I saw LISP used with genetic algorithms, but LISP isn't self-modifiable or self-replicating.... that was the whole point of what I wanted to create.


And yes, I've seen the classic example of Tierra. This is one of the things that got me interested.

And I am not sure about the "mutation-resistant language". What makes it different from LISP?

And code-manipulation primitives are exactly what I'm interested in. But what would these primitives be like? How would they operate on code?

I'm working on a language that's kind of lispy, in that the code can be treated like data and easily modified at runtime. It is called Circa. I'm also planning on exploring different ways that code can be automatically improved at runtime.

One method that I've had some success with, is backpropogation-style training across a dataflow diagram. The short version is this:

1. Construct a dataflow diagram for the code in question. (for me this is easy, that's the base representation I use)
2. Pick some values at the top that you want to get modified. These can be called the "inputs".
3. Pick some results at the bottom that you want to change. For each result, you specify a "desired" value.
4. Since you know exactly how every result was computed, you can then go backwards up the dataflow diagram, and figure out what you need to change to make the whole code spit out your "desired" values.
5. Eventually you will reach the "inputs" at the top, and you can change them to be what you need.

So this method can automatically adjust values, but it doesn't modify structure in any way.

I haven't started experimenting with structure-changing methods, but I don't think they will be too hard. The key is having a code representation which is easy to modify. An assembly-language representation is pretty bad because it's too easy for a small modification to completely change the effect of the code. A lispy representation is better. A dataflow representation is pretty good, I think.

Dataflow representation isn't Turing-complete, but I think for this domain, you are much better off having a restrictive representation which is easier to reason about. Turing-complete representations are pretty hard to reason about (the obvious example being, you can't always know if a piece of code will terminate).

Anyway the Circa project is here if you're interested: http://github.com/andyfischer/circa. It's totally a work in progress, don't expect it to do anything.

Quote:

Original post by polyfrag Yes, I got started on this idea of the "3D" scripting language from some flowchart I saw LISP used with genetic algorithms, but LISP isn't self-modifiable or self-replicating....

LISP is modifiable. Any LISP program is by definition also a LISP value.

Quote:

And I am not sure about the "mutation-resistant language". What makes it different from LISP?

LISP represents source as a tree (of S-expressions). Mutating a tree is hard because crossing-overs can easily change the number of arguments to a function and therefore cause runtime errors. The point of using FORTH-like syntax is that adding, removing or swapping program parts never causes actual semantic issues: every instruction is still able to get the correct elements from the stack.

Quote:

And code-manipulation primitives are exactly what I'm interested in. But what would these primitives be like? How would they operate on code?

LISP code is a tree (lists of lists of lists of lists of etc) and so list-manipulation functions allow you to manipulate LISP programs. Forth code is a sequence of atomic expressions, so sequence manipulation operators (swap, splice, insert, remove) allow you to manipulate Forth code.

But you couldn't use LISP to make a self-replicating script, could you?

[edit] In you LISP you have an instruction that basically copies a whole tree of instructions, right? This is not what I'm interested in. I'm interested in a script that can traverse its entire structure and assemble a replicate of itself 'piece by piece'.

Quote:

Original post by polyfrag But you couldn't use LISP to make a self-replicating script, could you?

Simply write a piece of LISP code that reads itself as input, and generates a new program as output... this is as easy as reading a tree and generating a tree.

But a tree is not able to repeat itself, is it? Unless you have a for/while loop instruction at the very top of the tree.

And how exactly are variables handled in LISP? How could they fit into a tree-hierarchy?


For the scripting language, I was thinking that the tree could 'loop back' at any point in the script, back to any point, creating loops, conditional pathways, etc. And that this looping back could also be self-modified. I.e., the connections could be moved to any nearby connected instruction and connections could also be formed on-the-fly. This would allow the scripts to traverse themselves to replicate, to modify themselves, and to interact with other script/A-life-organisms.

This means that the scripting language would be a giant interconnected mesh without a top-down tree hierarchy. (This is why I wanted to use 3D to represent it, since only that would allow the entire structure and inter-connectivity to be seen.)

[edit]

Quote:

Simply write a piece of LISP code that reads itself as input, and generates a new program as output... this is as easy as reading a tree and generating a tree.

So would it actually read AND parse its own code if it used itself as input? Or does input simply involve the representation of the instructions?

[Edited by - polyfrag on April 1, 2009 2:15:49 AM]

Quote:

Original post by polyfrag But a tree is not able to repeat itself, is it? Unless you have a for/while loop instruction at the very top of the tree.

Any language can be used to construct a program that outputs its own code—it's called a Quine and it's a natural consequence of being Turing-complete.

Now, any dynamic language is able to interpret source code on the fly at runtime, meaning that you can modify your quine to execute the code it outputs (leading to a self-replicating program). You can do this in many languages, such as &#106avascript or PHP.

The problem is that you cannot easily change the output code in these languages: there's a strict syntax you need to respect or you'll end up with syntax errors. The difference with LISP is that LISP is able to manipulate a LISP program as a tree, whereas languages like &#106avascript or PHP can &#111;nly manipulate their own code as a string (or in some rare cases through clunky reflection mechanisms). <br><br><!--QUOTE--><BLOCKQUOTE><span class="smallfont">Quote:</span><table border=0 cellpadding=4 cellspacing=0 width="95%"><tr><td class=quote><!--/QUOTE--><!--STARTQUOTE-->And how exactly are variables handled in LISP? How could they fit into a tree-hierarchy?<!--QUOTE--></td></tr></table></BLOCKQUOTE><!--/QUOTE--><!--ENDQUOTE-->With the exception of Forth (and possibly Prolog, depending &#111;n your religious philosophy), every programming language in the world includes variables in a tree: expressions are trees which have variables and literals as their leaves, and statement blocks are trees which have expressions and declarations as their leaves. <br><br>However, I strongly advise you to stay away from variables. The existence of variables is yet another constraint your modification algorithms will have to take into account. If anything, use De Bruijn indices, they have a natural self-verification structure. <br><br><!--QUOTE--><BLOCKQUOTE><span class="smallfont">Quote:</span><table border=0 cellpadding=4 cellspacing=0 width="95%"><tr><td class=quote><!--/QUOTE--><!--STARTQUOTE-->For the scripting language, I was thinking that the tree could 'loop back' at any point in the script, back to any point, creating loops, conditional pathways, etc. And that this looping back could also be self-modified. I.e., the connections could be moved to any nearby connected instruction and connections could also be formed &#111;n-the-fly. This would allow the scripts to traverse themselves to replicate, to modify themselves, and to interact with other script/A-life-organisms.<!--QUOTE--></td></tr></table></BLOCKQUOTE><!--/QUOTE--><!--ENDQUOTE-->Sure. But would that be <i>easy</i>? If self-replicating behavior is part of the organisms, you probably don't want to have a thousand-page program that does nothing but replicate. <br><br><!--QUOTE--><BLOCKQUOTE><span class="smallfont">Quote:</span><table border=0 cellpadding=4 cellspacing=0 width="95%"><tr><td class=quote><!--/QUOTE--><!--STARTQUOTE-->So would it actually read AND parse its own code if it used itself as input? Or does input simply involve the representation of the instructions?<!--QUOTE--></td></tr></table></BLOCKQUOTE><!--/QUOTE--><!--ENDQUOTE-->In LISP, both of these mean the same thing (but to be a little bit more helpful, you would probably write a bootstrap program that constructs the initial program from a clean tree representation, because you probably don't want to write quines by hand)

I wonder.. do you really need the code to be *self* modifying?

I mean, in terms of solving the problem of automatic code improvement, there are two directions you can go.

1, Have some 'candidate' code, which is the code you want to modify and improve, and then have some 'supervisor' code which manages the candidates. The 'supervisor' code is in charge of actually performing the modifications. In the example of a genetic algorithm, the 'supervisor' code is what stores a bunch of candidates and their fitness values, and then performs mutations and crossovers and stuff. The 'supervisor' code doesn't modify itself.

2, Have the code itself initiate the code modification operation, on itself.

Both approaches solve the same problem. It sounds like you really want to implement #2. But #1 is far easier and more effective to implement.

#2 is actually very limiting. Like you pointed out, it's very hard to write a piece of code that can safely iterate over itself. You end up in a weird holistic world, where you can't change one line of code because it mysteriously breaks a piece of code 10 lines above it. So there are certain operations you just won't try to implement.

Whereas with the #1 approach, the sky is the limit on which code modification operations you want to use.

I think a good analogy is brain surgery. Is it more effective for someone to perform brain surgery on themselves, or for someone else to perform it?

One thing to point out.. you can certainly write the system so that the code itself can *influence* how the modification takes place. One example, I experimented with using the ? mark as an operator in Circa. You could put it after a value or function, and that would be a signal to the modification code that it should favor making changes to that thing instead of other things.

Quote:

Sure. But would that be easy? If self-replicating behavior is part of the organisms, you probably don't want to have a thousand-page program that does nothing but replicate.

But I don't want to have a quine. A quine is only able to replicate its own exact structure. If you change a quine slightly, it no longer works. It couldn't for example have a robust self-replicating system that accomodates parts that might be changing.

A quine is like a crystal that repeats its own structure. The self-replicating scripts I wanted to make would be more than that.

Also, a quine can't have any other functionality besides outputting its own code. The scripts I wanted to make would be able to have any functionality besides replication (this is what those 'accomodated parts that might be changing' would be).

And a thousand-page program is very big, but several pages would be good to give the organisms some complexity and create some interesting things (in terms of variety, processes, evolution).

Quote:

I wonder.. do you really need the code to be *self* modifying?

The self-replicating scripts would also have to be self-modifiable.

If the scripts can traverse their own structures and assemble the same structures based on this, where there is no built-in difference between 'this' script and 'that' script (like in CoreWars/Tierra), then there's no reason why the scripts can't self-modify too.

I think they might evolve to take advantage of the ability to self-modify. It might allow for them to have a smaller self-replicating size that uses self-modification 'shortcuts' during the self-replication process. But I have no idea how it could do this, so that's just daydreaming about what it might be like.

And maybe there could be 'parasitic' scripts that parasitize another script's replicating machinery (like in Tierra).

And the self-modification isn't for just self-improvement (or evolution, as mutation would not be done by the organisms on themselves). But I don't know the ways that the scripts might evolve to use self-modification. I would have to have written the self-replicating script to know this.


[edit]

Quote:

Sure. But would that be easy? If self-replicating behavior is part of the organisms, you probably don't want to have a thousand-page program that does nothing but replicate.

And no this wouldn't be easy to have this non-directional jumble of inter-connected instructions, but it is necessary for the interesting results I want to create.

I am basically taking CoreWars/Tierra and making it so that the self-modification/code-manipulation-within-the-program does not depend on the expression of the code but that it is able to functionally change it, and has high level functions and variables unlike in CoreWars/Tierra.

[Edited by - polyfrag on April 1, 2009 10:35:14 PM]