木目擇司
출전; http://www.his.atr.co.jp/ecm/tierra-doc/japanese/tierra.html
티에라 사용 설명서 http://www.isd.atr.co.jp/~ray/pubs/doc/
톰 레이의 홈페이지 http://www.his.atr.co.jp/~ray/
1990년 1월, 델라웨어 대학의 진화 생물학자인 톰·레이는 컴퓨터 내부 세계에서 진화하는 시스템을 실현했다.
다윈이 주창한 진화론은 지금까지 화석 등의 진화의 산물을 관찰하는 것으로, 그 이론 의 검증과 새로운 이론의 전개가 이루어져 왔다. 톰·레이는 1970년대말 이래 매년 중미의 코스타리카의 열대 우림에서, 진화의 형적을 계속 관찰해 오고 있었다. 하지만, 그는 점차 불만을 느끼기 시작하고 있었다. 분명히 열대 우림 안에서는 동식물의 복잡한 상호 관계나 형태 변화를 볼 수 있고 그것이 진화의 결과라는 것을 알 수 있었다. 그러나, 진화의 프로세스 그 자체의 진행을 조사하기 위해서는 관찰자인 인간의 수명은 거기에 비교해 너무나도 너무 짧다.
1987년, 톰·레이는 도시바의 랩탑(lap-top) PC를 샀다. 그는 그것을 사용해, 하버드 대학의 대학원생이었던 무렵에 생각난 자기 복제하는 프로그램을 만들어 보려고 생각했다. 이윽고 그는 「인공생명」이라고 하는 책을 통해서 랭톤을 알게되고, 제1회 인공생명 국제회의를 조직한 크리스·랭턴을 만난다. 약 1년에 걸쳐 톰·레이와 랭턴은 메일로 의견 교환을 계속했다. 레이의 제안은 돌연변이와 유전 코드의 재조합에 의해, 자기 복제하는 프로그램을 만든다는 것이었다. 랭턴은 이 제안에 대해서 톰·레이가 하려고 하는 일은 컴퓨터 바이러스와 같은 위험성이 있다는 것을 지적했다.
1989년 톰·레이는 제1회 인공생명 국제회의가 개최된 뉴멕시코주 로스알라모스를 방문했다. 거기에는 복잡계나 인공생명의 제일선의 연구자가 모여 있었지만, 레이의 견해에 대해 랭턴과 같이 회의적인 의견이 많았다.
가장 많이 지적된 문젯점은 자기 복제 프로그램이, 컴퓨터 밖으로 누출될 위험성이었다. 그럴 경우 컴퓨터 바이러스나 웜 처럼 컴퓨터에 손상을 입힐지 모른다.
또 다른 문제는 기존의 컴퓨터 언어의 경우 코드의 일부를 변경키면 본래의 기능이 손상을 입게된다. 그런데 티에라는 진화를 통해 코드를 변경시키면서 그 프로그램을 작동시키려고 한다. 과연 그것이 가능할까 하는 것이었다.
첫째 문제에 대해서, 랭톤은 가상 컴퓨터 상에서 자기 복제 프로그램을 실행하자는 제안을 했다. 보통 컴퓨터에서는 하드웨어 위에 오페레이팅(operating) 시스템이 있어, 각종의 프로그램을 실행한다. 랭톤의 제안은, 오퍼레이팅 시스템 위에 가상 컴퓨터를 만들어 이 프로그램을 실행함으로 자기 복제 프로그램이 가상 컴퓨터의 밖으로 누출되지 못하도록 한다는 것이었다.
두 번째의 문제에 대해서는, 원래 컴퓨터 기술자는 아니었던 레이로서는 문제라고 생각하지 않았다. 실제 자연계에서는 유전자의 변이를 통해 진화가 일어나고 있다 . 유전자가 정보를 전하는 코드에 지나지 않는다고 볼 때, 컴퓨터 프로그램도 진화하지지 않을 리가 없다고 그는 생각했다.
델라웨어 대학으로 돌아간 레이는 그의 아이디어의 실현에 착수했다.
기존의 컴퓨터 언어에서는, 그 코드를 일부를 랜덤하게 바꾸면, 온전히 기능하지 않게 된다. 그러나 유전 코드는 로부스트(robust) 하다. 이 차이는 무엇 때문인가. 레이는 2개의 아이디어를 실행했다.
첫째는 "명령 세트의 수"이다. 유전 코드는 4 종류의 핵산을 알파벳으로 나타내 표현한다. 이러한 핵산 3개를 하나의 그룹으로 하여 하나의 아미노산에 번역된다. 3개의 핵산을 묶는 방법은 64가지가 있으므로, 각각의 편성 "코돈"는 20 종류의 아미노산의 어떤 것인가에 대응한다. 이것은 유전 코드에는 리던던시(redundancy)가 있어, 몇개의 코돈이 같은 아미노산으로 번역된다는 것을 의미한다.
여기서 중요한 것은, 돌연변이는 핵산의 치환, 삽입, 삭제를 일으켜, 그것에 의해 64종의 코돈의 치환이 일어나, 또 아미노산과 그리고 만들어지는 단백질의 치환을 일으킨다는 것이다. 즉 유전 코드는 64개의 코돈 또는 20 종류의 아미노산의 치환을 일으킨다.
같은 방식으로 컴퓨터의 기계어를 해석해 보면, 그 돌연변이는 매우 광범위의 대상에대해 일어날 수 있다는 것을 알 수 있다. 예를 들어, 컴퓨터에서 각각의 명령어은 32 비트로 구성되는데, 이것은 2의 32승(40억 이상)의 명령어의 치환이 있을 수 있다 것을 의미한다. 40억개의 명령 세트 중에서와 20개의 명령 세트 중으로 부터와는, 유용한 명령 세트를 찾아낼 수 있는 가능성은 아주 다르다.
거기서 레이는 명령어의 사이즈를 5 비트로 축소했다. 그러면 명령어의 종류는 2의 5승 즉 32개가 된다. 이런 적은 수의 명령어에서는 컴퓨터는 동작하지 않을 것이라고 생각될지도 모르지만 그렇지 않다. 실제의 컴퓨터의 기계어에서는 , 겨우 100 종류의 명령어 밖에 사용하지 않는다. 32 비트의 명령어 공간의 대부분은 수나 그 명령이 작용되는 오퍼랜드를 지정하는데 사용된다.
레이는 기계어로부터 오퍼랜드를 없앴다. 그가 생각해 낸 기계어에서는 모든 수는 CPU의 레지스터안에 격납되는 레지스터에서 그 값에 해당하는 주소가 지정된다.
이 변경은 다른 문제를 일으켰다. 그러나 또 동시에 새로운 발명을 가져왔다. 컴퓨터는 메모리 공간에 명령을 차례로 실행하지만, 가끔 분기나 루프 명령이 있다. 즉 명령어의 순서가 메모리가 있는 위치로부터 다른 위치로 점프 한다.
코드의 일부분이 다른 주소에 있는 일부분과 상호작용을 일으킨다. 레이는 이러한 일이 생물학과 어떻게 유비될 수 있을까 생각했다. 생물의 세계에서는 구체적 x, y, z의 좌표 공간을 계산하고 단백질 분자가 상호작용 하는 것은 아니다. 그 대신, 단백질 분자는 분자의 표면 형상이 열쇠와 열쇠구멍의 관계에 있어 맞으면 결합하고 맞지 않으면 떨어지는 방식으로 상호작용이 행해지고 있다. 표면의 상보적인 형상에 의해 분자끼리가 결부된다. 레이는 이 생각을 그의 기계어에 받아 들였다. 이것이 2번째의 아이디어이다. 정확한 주소를 지정하는 대신에 코드의 특정 부분에 패턴을 마련해 그 패턴과 가장 가까이 있는 상보적 패턴을 찾아, 거기로 점프 하는 것이다.
이렇게 해, 이 2개의 아이디어(소수의 명령 세트와 상보적인 패턴에 의한 애드레싱)를 포함시킨 가상 컴퓨터 "Tierra"(스페인어로 지구를 의미한다)가 탄생했다. 그리고 레이는 벌써 "진짜" 컴퓨터의 기계어 용으로 작성한 자기 복제 프로그램을 Tierra용으로 번역했다.
레이는 처음에 이 가상 컴퓨터 Tierra와 자기 복제 프로그램이, 자기 복제 이외에는 그 무엇을 특별히 의중에 두고 설계하지 않았다. 그는 그 무렵, 고도의 자기 복제 능력을 가진 가상 컴퓨터를 만들려면 몇 년이나 걸릴 것이라고 생각하고 있었다. 하지만, 1990년 1월 3일의 밤, 처음 가상 컴퓨터 위에 자기 복제 프로그램의 실행에 성공했을 때 그 계획은 근본적으로 변경되었다. 레이는 그날 밤 시스템의 설계자로부터 다시 관찰자가 되었다. 다만 이번은 자연계의 열대 우림의 관찰자가 아니고,"디지털 정글"의 관찰자였다.
이 디지털 정글 안의 생물들에서도 부근의 생물들을 공격하거나 혹은 그 공격을 방어하는 방법의 탐색등이 끝 없이 반복되어지고 있었다. 진화는 기본적으로는 이기적인 프로세스이다. 그 성공도는 유전자를 장래의 세대에 얼마나 많이 남기는가에 의해 평가된다. 그 목적을 달성하는데 진화는 매우 독창적이다.
일단 환경이 생물(레이가 스스로 코딩 한 종으로 조상종이라고 부른다)로 채워지면, 이러한 생물들이 환경 중에서 가장 중요한 것이 된다. 그의 가상 컴퓨터가 최초로 실행된 밤, 생물들은 그들의 환경에는 많은 정보가 있다는 사실일을 알아냈다. 그다지 영리하지 않은 생물들은 그것들이 필요로 하고 있는 모든 정보를 단순히 복사하고 있었다. 그러나 보다 진화한 종이 이웃의 정보를 사용해 자기 복제하는 방법을 짜냈다. 그리고 그것들은 곧바로 디지털 정글의 환경을 채웠다. 이것들을 조상종의 코드를 이용해 자기 복제를 실시하는 것으로부터 기생종이라고 부른다.
하지만 이 기생종들의 번영은 길게 계속되지 않았다. 최초 기생종은 필요로 하는 정보를 간단하게 찾아낼 수가 있었다. 그러나 그것들이 증가해 환경 전체를 채워, 숙주(조상종)의 수가 줄어들면서, 그 정보를 찾아내는 일이 곤란하게 된다. 이 종은 급속히 수를 줄어들게 된다.
기생종이 줄어들면 숙주는 다시 그 수를 회복시킨다. 그러면 또 기생종의 수가 그 뒤를 쫓아 자신을 회복한다. 이와 같이 기생종과 숙주에 의한 "Lotka-Volterra"사이클로 불리는 포식자와 사냥감 의 개체수의 주기 변동을 일으키는 현상이 관찰되었다.
하지만 이만큼은 아니었다. 숙주는 이윽고 기생종에 대해서 "면역"적인 기능을 하는 메카니즘을 발달시켰다. 우선 숙주는 한 번은 기생 종의 복제를 허락한다. 그리고 기생종을 속이는 정보를 준비한다. 이 정보는 기생종이 2번째의 복제 과정에서 그것들이 기생하고 있는 숙주의 복제를 실시하게 하게 되어 있다. 숙주 자신은 자기 복제할 때 이 기생종은 없어도 상관없기 때문에, 이윽고 이 기생종은 멸종한다. 이 종을 레이는 기생종이 가지고 있는 에너지(CPU 시간)를 빼앗아 버리는 종이라고 하는 의미로 하이퍼 기생종이라고 부르고 있다.
기생종이 멸종한 후, 하이퍼 기생종은 한층 더 진화해 사회적 하이퍼 기생종이 되었다. 이미 기생종은 존재하지 않기 때문에, 그것들은 서로 이웃에 위치해 서로끼리의 증식을 서로 돕는다. 하지만 곧바로, 사회적 하이퍼 기생종끼리의 신뢰 관계 는 레이가 "Cheater"(사기꾼)라고 부르는 종에 의해 부수어진다. Cheater는 하이퍼 기생종이 사용한 것과 같은 방법으로, 동료의 에너지를 빼앗아 버린다.
그 후, 새로운 실험으로 Tierra의 가상 생물에서 sex마저 발견되었다. 디지털 생물끼리 그리고 유전자를 혼합해, 새로운 유전 코드를 가진 자손을 낳았다.
레이는 Tierra는 「생명이 어떠한 형태를 취할 수 있는 것일까?」, 그리고, 「어째서 종은 각각 달라, 종과 종의 중간의 형태를 가진 생물이 없는 것은 왜인가?」라는 의문에 답할 수 있는 강력한 도구가 될 것이라고 한다.
그리고 레이의 최대의 꿈은 디지털 컴퓨터 안에서 "캄브리아 폭발"을 일으키는 것이다. 6억 년전에 일어난 캄브리아 폭발은 생명의 탄생 이상으로 특필해야 할 사건 이다. 이 때 갑자기 온갖 다세포 생물이 출현했다. 그리고 생각보다는 짧은 기간내 그리고 생물의 다양한 형태가 시험 받아 그갓으로 부터 오늘까지 남아 있는 주요한 생물의 형태가 결정되었다. Tierra에 만약 캄브리아 폭발과 같은 현상을 일으킬 수가 있으면, 그것은 모든 종류의 다양성이나 복잡함을 가진 정보처리 시스템을 가진 디지털 생물이 창조되었다는 것을 의미할 것이다.
우리는 생명이라는 것에 대해 하나의 형태 밖에 모른다. 지구라고 하는 하나의 생태계 밖에 우리는 모르기 때문이다. 여기에 또 하나 생태계를 도입하자. 이 생태계는 컴퓨터 속에 만들어지고 있다. 유기 화합물로 완성된 생명과는 완전히 다른, 디지털 정보로 완성된 생태계 Tierra이다.
기본 개념
유기 생물(식물)은 태양 에너지를 이용해 이것을 화학에너지로 변환해, 영양물을 자신의 몸을 구성하기 위한 물질로 바꾼다. 초식동물은 물론, 육식동물이 먹이를 통해서 얻는 에너지도 거슬러 올라가면 식물이 얻은 태양 에너지에 귀착한다. 지구상의 생태계를 극히 단순화해서 말하면, 모든 생물은 한정된 양의 에너지(태양 에너지)와 양분으로서의 물질을 획득하기 위해서, 그것들이 차지하는 공간을 서로 탈취하려고 하는 것이라고 볼 수 있다.
Tierra는 지구 생태계의 이 기본적인 구조를 흉내내고 있다. 컴퓨터 안의 자원으로서 가장 중요한 것이 2개 있다.
하나는 CPU(중앙연산 처리장치)의 스피드로, 빠르면 빠를수록 짧은 시간에 많은 정보처리를 할 수 있다. 이것은 에너지를 많이 얻을 수 있으면 얻을 수 있는 만큼 많은 화학반응을 일으켜, 자신의 몸을 만들거나 자손을 남기기는 등 많은 생명 활동을 할 수 있다는 것에 대응한다.
다른 하나는 메모리 공간(RAM)에서 컴퓨터로 실행되는 프로그램이나 그것을 위한 데이터는 RAM상에 놓여진다. 크고 복잡한 프로그램일수록 그만큼 큰 메모리 공간을 필요로 한다. 이것은 몸이 크면 그만큼 넓은 공간과 그 몸을 구성하는 물질을 필요로 하는 것과 같다.
Tierra의 세계에서는 생물(디지털 생물로 불린다)들은 각각, 독립한 프로그램으로 생각하면 된다. 그러한 프로그램(디지털 생물)들은 기본적인 기능으로서 자기 복제 능력이 필수적이다. 그들의 목적은 보다 많이 자신과 같은 프로그램을 메모리 공간상에 계속 늘려 가는 것이다. 디지털 생물들은 동시에 여럿이 존재하지만, 일반의 컴퓨터 시스템에서는 CPU는 1개 밖에 없는 것이 보통이다. Tierra 시스템은 차례로 각각의 생물에게 CPU의 이용 시간을 할당한다. 보다 많이 CPU 시간을 얻은 생물은 생존 경쟁에서 그 만큼 우위에 선다.
Tierra의 세계의 생물은 프로그램이라고 말했지만, 그것들은 전용의 기계어로 기술된다. 기계어는 컴퓨터를 직접 조작할 수 있는 언어이다. 톰·레이에 의하면 기계어는 비트 , 바이트, CPU 레지스터나 명령 pointer를 직접 조작할 수 있으므로, 핵산은 아니고 화학적으로 활성적인 아미노산과 같은 것이라고 한다. Tierra에서는 생물은 RNA 세계 의 생물들의 유추로 설명할 수 있다. RNA 세계의 생물들은 유전 정보를 운반하고, 대사 활동을 실시하기 때문이다.
RAM 메모리 안에서 디지털 생물들이 서식하는 부분을 Tierra에서는 스프(soup)라고 부른다. 디지털 생물들의 게놈은 일련의 기계어로 구성된다. 그것들은 자기 복제하기 위한 코드를 포함한다. 톰·레이는 최초의 생물로서 80개의 기계어로 구성된 선조종(先祖種)의 코드를 작성했다.
가상 컴퓨터
Tierra는 가상 컴퓨터이다. 진짜의 컴퓨터로부터 보면 그것은, 오퍼레이팅(operating) 시스템 위에서 실행되는 하나의 프로그램에 지나지 않는다. 그러나 Tierra 프로그램 자신은 하나의 완전한 컴퓨터 시스템으로서의 기능을 가진다. 그리고 디지털 생물들의 각각의 프로세스는 이 가상 컴퓨터상의 가상 프로세스로서 실현되고 있다. Tierra를 가상 컴퓨터로서 실현하는 것은 아래와 같은 몇 가지 이점이 있다.
1. 만약 디지털 생물이 진짜의 기계어로 기술되어 그것이 진짜의 컴퓨터 상에서 직접 실행되면, 그것은 컴퓨터 바이러스나 웜과 같이, 컴퓨터 시스템에 대해서 나쁜 영향을 줄 우려가 있다. 그러나 디지털 생물이 가상 컴퓨터용의 기계어로 기술되고 있다면, 그것은 진짜의 컴퓨터에 있어 워드프로세서 소프트웨어의 문서 파일과 같은 단순한 데이터에 지나지 않는다.
2. 기계어는 각각의 하드웨어 고유의 명령 세트에 의해 구성되어 있다. 디지털 생물을, 어느 진짜의 기계어로 기술해 버리면 그 하드웨어가 기술의 진보에 의해 구닥다리가 되었을 경우, 다시 새로운 하드웨어용의 기계어로 고쳐 쓰지 않으면 안 되게 될 것이다. Tierra는 가상 컴퓨터이기 때문에, Tierra 자체를 이식할 수 있고 따라서 디지털 생물의 기계어(Tierra 언어)를 수정할 필요는 없다. Tierra 자체는 C언어로 기술되고 있으므로, 대부분의 컴퓨터 시스템에 이식 가능하다.
3. 기존이 많은 기계어는, 그래서 기술된 코드가 진화할 수 있도록 설계되어 있지 않다. 폰·노이만형 컴퓨터의 기계어는, 그 일부에서 랜덤한 변경이 발생하면 프로그램으로서 기능할 수 없게 된다. 따라서, 코드에 돌연변이 등의 처리를 가하는 일은 거의 불가능하다. 가상 컴퓨터로 사용되는 기계어에서는 이러한 ”취약성"을 제거하기 위한 노력이 집중되고 있다.
Tierra는 MIMD형(multiple instruction, multiple data. 동시에 복수의 명령을 다른 복수의 데이터에 대해서 실시하는 병렬 컴퓨터의 타입)의 병렬 컴퓨터 시스템을 의식해서 만들어졌다. 각각의 디지털 생물이 하나의 CPU를 가지도록 설계되고 있지만, 이것은 실제는 CPU 시간을 작은 타임 슬라이스에 분할하는 것으로써, 병렬형 컴퓨터를 흉내내고 있을 뿐이다.
이 가상 컴퓨터에서는 각 CPU는 2개의 주소용 레지스터, 2개의 수치용 레지스터, error flag용 레지스터, 스택 포인터, 10개 단어 분의 스택, 그리고 명령 pointer를 갖추고 있다. 이 가상 CPU는 이하와 같은 C언어의 구조체 데이터로서 만들어져 있다.
(현재 구조체 cpu는 Cpu로 이름이 변경되었다. 또 보다 많은 레지스터를 정의할 수 있도록 레지스터용 배열이 정의되고 있다. )
struct cpu { /* structure for registers of virtual cpu */
int ax; /* address register */
int bx; /* address register */
int cx; /* numerical register */
int dx; /* numerical register */
char fl; /* flag */
char sp; /* stack pointer */
int st[10]; /* stack */
int ip; /* instruction pointer */
} ;
Tierra의 CPU로 실행되는 계산은 지극히 낮은 확률에서는 무효가 되는 것이 있다. (돌연변이의 항 참조. )
명령 세트는 CPU내의 레지스터를 사용해 단순한 수치 연산이나 비트 오퍼레이션을 실시하도록 설계되었다. 어떤 종류의 명령은 레지스터내의 데이터를 다른 레지스터에 이동시키거나 RAM 메모리와 레지스터간 데이터의 이동을 실시한다. 그밖에 「명령 pointer(IP)」의 위치를 제어하는 명령도 구비되어 있다. IP는 디지털 생물이 가고 있는 코드의 메모리상의 주소의 위치를 특정하는 것이다.
CPU는 차례 차례로, 명령의 read-복호-실행-IP의 인크리먼트(increment)라고 하는 일련의 사이클을 반복한다. IP에 의해 지시되어지고 있는 기계어 명령이 CPU에 읽혀 그 비트·패턴을 해독해 그것에 대응하는 명령을 특정해, 그 명령을 실행한다. 그리고 IP는 1개소의 명령의 주소값에 인크리먼트(increment)된다. 다음의 사이클로 그 명령이 CPU에 읽혀 복호, 실행을 한다. 그러나 예를 들면 JMP, CALL, RET와 같은 분기 명령에서는 IP는 떨어진 위치에 있는 명령으로 이동한다. 초기의 Tierra에서 이 CPU 사이클은 아래에 나타내는 타임·슬라이스·루틴에 의해 실장되고 있었다.
(현재 이 부분의 코드는 상당한 부분 고쳐 쓸 수 있지만 기본 구조는 변함이 없다. 루틴명은 TimeSlice()라고 변경되었다.)
void time_slice(int ci)
{ Pcells ce; /* pointer to the array of cell structures */
char i; /* instruction from soup */
int di; /* decoded instruction */
int j, size_slice;
ce = cells + ci;
for(j = 0; j < size_slice; j++)
{ i = fetch(ce->c.ip); /* fetch instruction from soup, at address ip */
di = decode(i); /* decode the fetched instruction */
execute(di, ci); /* execute the decoded instruction */
increment_ip(di, ce); /* move instruction pointer to next instruction */
system_work(); /* opportunity to extract information */
}
}
Tierra 언어
진화 가능한 가상 기계 언어(Tierra 언어)는, 생물의 DNA, RNA와 단백질을 참고로 한 2개의 특징을 갖고 있다.
하나는 명령 세트의 수를 생물의 유전 코드와 같은 정도의 사이즈가 되도록 한 일 이다. 실제의 생물에서는 64개의 코돈을 이용해 DNA에 코드 되고 있어 그것들의 코돈은 20 종류의 아미노산으로 번역된다. Tierra 언어에서는 5 비트의 2 진수로 표현되는 32개의 명령으로 구성되어 있다.
또 명령 세트의 수를 진짜 줄였기 때문에 Tierra 언어에는 수치 오퍼랜드가 존재하지 않는다. Tierra 언어에서는 레지스터와 스택만을 이용해 수치 연산을 실시한다. 어떠한 이유로써 정수를 명령 코드의 일부로서 사용하고 싶을 때는, 수치를 레지스터에 놓는 것으로 한다. 그리고 그 수치의 수식(修飾)에는 최하위 비트로의 반전과 왼쪽 쉬프트를 이용해 실시한다. 이 일에 의해 프로그램의 사이즈는 증가하지만, 수치 오퍼랜드의 필요는 없어진다.
제2의 특징은, 「템플릿에 의한 주소 방식」이다. 대부분의 기계어에서는 데이터의 참조나 점프 명령에는 주소 번호를 이용한다. 한편 생물의 경우, 예를 들면 세포질안에서 단백질 분자 A가 다른 단백질 분자 B와 상호작용 하려고 할 때 분자 B의 정확 좌표 위치를 필요로 하는 것은 아니다. 분자 A는 자신의 표면에 분자 B의 표면과 상보적인 형상의 템플릿을 준비한다. 그리고 확산에 의해 2개의 분자가 가까워졌을 때 2개의 템플릿이 상보적이면 그것들은 서로 겹쳐 상호작용을 일으킨다.
Tierra 언어의 템플릿에 의한 주소 방식의 예를 JMP(jump) 명령으로 보여준다. 각 JMP 명령의 뒤에는 몇개의 NOP(no-operation) 명령이 계속된다. NOP 명령에는 NOP_0, NOP_1의 2 종류가 있다. 예를 들면 5개의 명령으로부터 되는 코드열,
JMP, NOP_0, NOP_0, NOP_0, NOP_1
을 생각해 보자. 이 때 시스템은 이 코드열의 전후에 있는 가장 가까운 위치에 있다 상보적인 패턴
NOP_1, NOP_1, NOP_1, NOP_0
을 찾는다. 만약 패턴이 발견되면 IP는 곧 다음에 있는 명령을 가리켜 실행을 시작한다. 만약 패턴이 발견되지 않을 때는, 에러·플래그를 세트하고 JMP 명령은 무시된다. 실제로는 Tierra 실행 개시시에 탐색 범위를 지정해 둔다.
이상과 같이 Tierra 언어는 2개의 독특한 특징을 가지고 있다. 1개는 수치 오퍼랜드 를 가지지 않는, 매우 소수의 명령 세트이며, 다른 하나는 템플릿에 의한 주소 방식이다. 그 외의 점에서는, 대부분의 전형적인 기계어와 같이 되어 있다. 즉, MOV, CALL, RET, POP, PUSH 등 보통 기계어가 준비되어 있다. 아래에 초기의 Tierra에서 사용된 명령 세트를 보여주고 있다. (이 명령 세트도 초기의 것으로, 현재의 버전에서는 대폭 추가, 변경, 삭제하고 있다. )
void execute(int di, int ci)
{ switch(di)
{ case 0x00: nop_0(ci); break; /* no operation */
case 0x01: nop_1(ci); break; /* no operation */
case 0x02: or1(ci); break; /* flip low order bit of cx, cx ^= 1 */
case 0x03: shl(ci); break; /* shift left cx register, cx <<= 1 */
case 0x04: zero(ci); break; /* set cx register to zero, cx = 0 */
case 0x05: if_cz(ci); break; /* if cx==0 execute next instruction */
case 0x06: sub_ab(ci); break; /* subtract bx from ax, cx = ax - bx */
case 0x07: sub_ac(ci); break; /* subtract cx from ax, ax = ax - cx */
case 0x08: inc_a(ci); break; /* increment ax, ax = ax + 1 */
case 0x09: inc_b(ci); break; /* increment bx, bx = bx + 1 */
case 0x0a: dec_c(ci); break; /* decrement cx, cx = cx - 1 */
case 0x0b: inc_c(ci); break; /* increment cx, cx = cx + 1 */
case 0x0c: push_ax(ci); break; /* push ax on stack */
case 0x0d: push_bx(ci); break; /* push bx on stack */
case 0x0e: push_cx(ci); break; /* push cx on stack */
case 0x0f: push_dx(ci); break; /* push dx on stack */
case 0x10: pop_ax(ci); break; /* pop top of stack into ax */
case 0x11: pop_bx(ci); break; /* pop top of stack into bx */
case 0x12: pop_cx(ci); break; /* pop top of stack into cx */
case 0x13: pop_dx(ci); break; /* pop top of stack into dx */
case 0x14: jmp(ci); break; /* move ip to template */
case 0x15: jmpb(ci); break; /* move ip backward to template */
case 0x16: call(ci); break; /* call a procedure */
case 0x17: ret(ci); break; /* return from a procedure */
case 0x18: mov_cd(ci); break; /* move cx to dx, dx = cx */
case 0x19: mov_ab(ci); break; /* move ax to bx, bx = ax */
case 0x1a: mov_iab(ci); break; /* move instruction at address in bx
to address in ax */
case 0x1b: adr(ci); break; /* address of nearest template to ax */
case 0x1c: adrb(ci); break; /* search backward for template */
case 0x1d: adrf(ci); break; /* search forward for template */
case 0x1e: mal(ci); break; /* allocate memory for daughter cell */
case 0x1f: divide(ci); break; /* cell division */
}
inst_exec_c++;
}
Tierra operating system
Tierra의 가상 operating system는 디지털 생물의 서식을 위해서, 프로세스간 통신(여기에서는 아마 디지털 생물끼리의 통신의 의미) , (디지털 생물에게) 메모리와 CPU 타임의 할당 등을 실시한다.
메모리의 할당 ― 세포성
Tierra는 그 실행 개시 직후, 진짜 컴퓨터 시스템의 메모리 가운데, 그 일부를 디지털 생물이 생식하기 위한 「스프」용 메모리로서 확보한다. 보통 그 크기는 60000바이트이다(파라미터 설정 파일에 의해 변경 가능하다). 이것은 그 스프 안에 60000개 분의 기계어 명령이 놓여지는 용량이 있는 일을 의미한다. (Tierra 언어에서는 각 명령어는 1바이트인 8 비트중 5 비트 밖에 사용하지 않지만, 프로그램상 1 명령을 1바이트에 할당하고 있다. )
Tierra에서는 디지털 생물의 기본 단위를 「세포(셀)」라고 하고 있다. 각 셀은 1개의 CPU를 가지고 있고(현재의 버젼에서는 복수의 CPU를 가지는 것으로 다세포성을 실현시키는 일도 할 수 있다), 또 스프내의 어떤 블록을 확보하고 있어, 거기에 각 셀의 게놈(Tierra 언어의 순서)이 보존되고 있다. 이 블록에는 그것을 소유하고 있는 셀은 기입할 수 있고(쓸 수 있고) 읽어들여 동작을 실시할 수가 있다. 그러나 그 블록의 소유자가 아닌 셀은 read밖에 실시할 수가 없다. 이것은 각 셀이 「반투막」성의 세포막으로 보호되고 있다는 것을 의미한다.
셀은 자기 복제시에는 자신의 게놈이 기술되고 있는 블록 외에, 복제처의 셀(딸 셀)용의 블록을 확보한다. 이것은 기계어 명령 "mal"에 의해 행해진다. 그리고 그 블록에 자신(어머니 셀)의 게놈을 카피한다. 그리고 기계어 명령 "divide"에 의해 딸 셀은 독립(자기 자신 의 명령 pointer를 획득) 해, 그 시점에서 어머니 셀은 그 딸 셀의 블록에 기입할 권리를 잃는다. 그 후, 딸 셀도 새로운 어머니 셀이 되어 자기 복제 프로세스를 개시한다.
에너지(CPU 시간)의 배분
현실의 세계와 같이 개개의 생물들이 동시에 활동하기 위해서는, Tierra operating system는 멀티·태스크(또는 패러렐)가 아니면 안 된다. Tierra에서는 이 일을 달성하기 위해서, CPU 시간을 분할(슬라이스·사이즈)해 차례로 디지털 생물들에 배분하는 일로 이 구조를 제공하고 있다. 시스템은 「슬라이서·큐」로 불리는 대행렬(待行列)을 관리하고 있다. 새로운 생물(셀)이 태어나면, 가상 CPU가 만들어져 어머니 셀의 바로 앞의 슬라이서·큐에 넣어진다. 슬라이스·사이즈가 셀의 복제에 필요로 하는 시간보다 충분히 짧으면, 근사적으로 병렬성이 실현되고 있다고 생각해도 좋을 것이다.
슬라이스·사이즈의 결정 방법이지만, 그것은 각 셀의 게놈 크기의 멱승에 비례하게 되어 있다. 만약 멱을 1보다 크게 하면, 게놈이 큰 생물은 작은 생물보다 1 명령어 정도 보다 많은 CPU 시간이 할당되어지게 된다. 만약 멱을 1보다 작게 설정해 두면, 반대로 게놈이 작은 생물은 그 만큼 보다 많은 CPU 시간이 배분된다. 멱이 1이라면 게놈의 사이즈에는 관계없이 모든 명령어에 동일한 CPU 시간이 배분된다. 이와 같이 멱의 설정의 방법을 통해 큰 생물을 좋아하는 환경으로 할까 작은 생물을 좋아하는 환경으로 할까를 선택할 수가 있다. 일정한 시간 폭으로 시분할 하면, 큰 생물은 그만큼 각 명령어에 배분되는 CPU 시간이 적어짐으로, 작은 생물에게 유리한 환경이 될 것이다.
죽음과 도태
자기 복제하는 생물들은 또 쉽게 집에 스프를 가득채워 버린다. 만약 이 생물들이 불로 불사라면, 생물들은 새로운 복제를 실시할 수가 없게 되어, Tierra 시스템내의 프로세스는 끝나버릴 것이다.
Tierra operating system는 "리퍼(죽음의 신)"라고 하는 시스템을 준비하고 있다. 이것은 스프가 어느 정도 가득하게 되면(예를 들면,80%이상으로 설정한다. ), 생물들은 죽도록 설정되어 있다.
디지털 생물(셀)은 각각 직선 모양의 대행렬(리퍼·큐)로 늘어놓을 수 있어 있다. 새로운 디지털 생물이 태어나면, 그것은 리퍼·큐의 최 후미에 놓여진다. 리퍼가 발동하면, 그것은 리퍼·큐의 맨 앞의 디지털 생물로부터 죽여 간다. 그렇지만 각 생물은, 그것들이 실행하는 명령어가 실패하는가 성공하느냐에 따라, 리퍼·큐 속을 오르내린다. 성공하면 큐안의 위치를 뒤로 돌릴 수 있어, 죽음의 신의 마의 손을 피할 수 있다. 실패하면 앞으로 놓여져 죽음의 신의 먹이가 될 때가 가까워진다.
리퍼의 도입에 의해, 뛰어난 알고리즘을 가진 디지털 생물은 보다 오래 살고 , 뒤떨어진 디지털 생물의 수명은 짧아진다.
돌연변이
진화는 그 생물의 유전 코드(게놈)가 변화하는 일로 해서 발생한다. 이 변화(돌연변이) 는 아마, 개개의 생물이 살아 있는 동안 혹은 차세대에게 게놈을 주고 받는 도중의 양쪽 모두에 일어날 수 있다. Tierra operating system에서는, 스프에 놓여진 명령어에 랜덤한 비트의 반전을 일으키거나 Tierra 언어를 불완전한 형태로 실행시키는 경우에 돌연변이가 일어난다.
돌연변이의 방법에는 2개의 종류가 있다. 하나의 방법은, 어느 백그라운드·레이트로 스프 전체(예를 들면 60000 명령 즉, 300000 비트)중에서 랜덤하게 어느 비트를 선택하고, 그 비트를 반전(0을 1에, 1을 0에)시킨다. 이것은 우주선에 의해 지구상의 생물의 유전자가 손상되는 방법을 흉내내고 있다. 이것으로 해서 어떠한 디지털 생물도 영구히 각 명령이 정상적으로 실행된다고 하는 보증은 없어져, 그 생물은 불로 불사에서는 있을 수 없게 된다. 이 백그라운드·레이트는 10000 명령당 1 비트로 설정되어 있다(파라미터 설정 파일에 의해 변경 가능하다).
또 다른 돌연변이의 방법은, 디지털 생물이 자기 복제하는 중간에 일어난다. 복제할 때, 어떤 확률로 랜덤하게 복제되는 명령 세트의 비트를 반전시킨다. 이것에 의해, 복제 에러가 일어난다. 그 확률은 1000내지 2500 명령 마다 1 비트로 설정되어 있다. 어느 쪽의 경우도, 돌연변이가 일어나는 간격은 주기적인 현상이 일어나는 것을 단절시키기 때문에 랜덤하게 변화한다.
이러한 돌연변이에 가세해, Tierra 언어의 명령이 일정한 낮은 확률로 부정확한 동작을 하는 것으로 해서 변이가 일어난다. 대부분의 명령 세트에 대해, 명령의 실행 결과에 낮은 확률로 1을 더하거나 줄이는조작을 행한다. 예를 들면, 가산 명령은 레지스터의 값에 1을 더하지만, 가끔 0또는 2를 더하는 일이 있도록 해 둔다. 비트 반전 명령은 보통, 최하위 비트를 반전시키지만, 가끔 최하위 비트의 다음에 큰 비트를 반전시키거나 혹은 반전을 하지 않는 것이 있도록 해 둔다. 또, 레프트 쉬프트 명령은 보통 모든 비트를 1 비트 만큼 좌로 쉬프트 시키지만, 가끔, 2 비트 쉬프트 시키거나 혹은 전혀 쉬프트 조작을 실시하지 않는 것이 있도록 해 둔다. 이와 같이 Tierra 언어 의 명령 세트의 동작은 결정적인 것이 아니고 확률적인 것이다.
돌연변이의 결과, 새로운 유전자형을 가진 디지털 생물이 탄생하지만, 그것들은 "유전자 뱅크"매니저라고 하는 시스템에 자동적으로 등록된다. 유전자 뱅크는 새로운 유전자형을 가진 셀 가운데, 2회의 자기 복제에 성공한 셀에 이름을 붙여 등록한다.
(이것은 아마, 1회째의 자기 복제 프로세스와 2번째 이후의 자기 복제 프로세스에서는, 명령 실행 회수가 다르기 때문일 것이다. 톰·레이가 설계한 선조종의 생물에서는 자기의 사이즈를 측정하기 위한 코드가 포함되어 있다. 1회째의 복제시에는 스프에 복제를 위한 영역을 확보하기 위해서, 자기의 사이즈를 측정해야 한다. 그 생물이 2번째의 자기 복제를 실시할 때는 사이즈의 측정은 필요없기 때문에, 1회째와 2번째의 명령 실행 회수가 다르다. )
각각의 유전자형은 숫자와 3자리수의 알파벳의 조합으로 명명된다. 예를 들면 80개의 명령어로 완성된 최초의 디지털 생물은 80 aaa라는 이름을 붙여진다. 최초의 숫자가 명령어의 수를 나타내, 다음의 3자리수의 알파벳에 의해 그 사이즈의 생물로 최초로 나타난 순서대로 aaa, aab와 같이 분류한다. 최초로 출현한 사이즈 45의 생물은 45 aaa이며, 다음에 같은 사이즈 45이지만 유전자형이 다른 생물이 출현하면 거기에는 45 aab라는 이름이 붙여진다.
이와 같이 각각의 생물에게 이름을 붙여 동시에 그 생물의 어머니 생물의 이름을 관련지어 두는 것에 의해, 진화 계통수를 작성하는 일도 가능하다. 유전자 뱅크는 명명과 동시에 그 생물이 태어난 일시, 그리고”대사"데이터, 즉, 1회째와 2번째의 딸 셀을 자기 복제하는데 필요로 한 명령 실행 회수와 에러 회수, 그리고 몇개의 환경 변수(주소·템플릿의 탐색 한계 파라미터 및 타임·슬라이스의 멱승 파라미터. 이것들은 그 환경에 적응하는 생물의 사이즈에 영향을 준다.)도 기록한다.
최초의 디지털 생물 선조종
여기서 톰·레이가 설계한 최초의 생물(선조종)의 코드를 조사해 보자. 톰·레이는 이 선조종을 설계할 때, 자기 복제를 위한 코딩만을 생각하고 의도적으로 진화를 일으키게 하는 것 같은 장치는 넣지 않다고 말하고 있다.
선조종의 코드는 대략적으로 나누면 3개로 나누어 고찰해볼 수 있다,
1. 자기 검사
선조종은 우선, 스프내에서 자신의 코드가 개시되는 위치(코드 개시 주소)와 종료하는 위치(코드 종료 주소)를 계측 한다. 코드 개시 주소는 4개의 no-opration 명령에 의한 템플릿(nop1, nop1, nop1, nop1)으로 표시되고 있다. 마찬가지로 코드 종료 위치는 템플릿(nop0, nop0, nop0, nop1)으로 표시되고 있다.
선조종은 5개의 명령 adrb, nop_0, nop_0, nop_0, nop_0에 의해 코드 개시 위치를 특정한다. adrb 명령은 4개의 nop_0 명령과 상보적인 템플릿을 후방(스프 주소가 감소하는 방향)으로 향해 탐색한다.
마찬가지로 adrf, nop_0, nop_0, nop_0, nop_1에 의해, 코드 종료 위치를 특정한다. 코드 개시 위치와 종료 위치는 각각 bx레지스터와 ax레지스터에 격납(格納)되어 ax레지스터의 값으로부터 bx레지스터의 값을 깎는 방식으로 자신의 코드 사이즈(명령어의 수)를 계산해, cx레지스터에 격납한다.
2. 자기 복제 루프
사이즈 계측이 끝나면, 자기 복제 루프에 들어간다. 우선, 딸 셀에 코드를 복제하기 위해서 스프 내에 어머니 셀의 코드 사이즈 분의 영역을 확보한다(MAL 명령). 이 때 확보한 영역의 선두 주소를 AX 레지스터에 격납한다. 그리고 카피 프로세스를 호출한다. 카피 프로세스를 호출하려면 5개의 명령어 call, nop_0, nop_0, nop_1, nop_1 에 의해, 템플릿(nop0, nop0, nop1, nop1)과 상보적인 템플릿을 탐색한다. 이것에 의해, 카피 프로세스의 코드에 IP가 이동해 그 처리를 행한다.
3. 카피 프로세스
mov_iab 명령에 의해 bx레지스터의 주소(카피 원본)에 있는 명령어를 ax레지스터의 주소에 카피한다. 이 조작을 어머니 셀의 코드 사이즈(cx) 만큼 반복한다.
모든 명령어의 카피를 완료했으면 다시 자기 복제 루프 내로 돌아와, divide 명령을 실시한다. 이 명령에 의해 어머니 셀은 딸 셀의 메모리에의 기입권을 잃는다. 그리고 딸 셀은 명령 pointer가 주어진다. 그리고 슬라이서·큐와 리퍼·큐에 엔트리된다.
최초의 복제가 끝나면, 어머니 셀은 2번째에는 자기 검사 코드를 실행하지 않는다. jmp 명령에 의해 자기 복제 루프의 처음으로 돌아가, 다시 복제를 실시한다. 이 루프는 무한 루프이다.
이 80 명령의 코드중 48 명령은 no-operation 명령이다. 4개의 no-operation 명령을 조합해 12개의 템플릿을 만들어, 코드의 개시, 종료 주소, 카피 프로세스나 무한 루프, 점프 명령의 마킹에 사용하고 있다.
선조종의 코드는 어셈블러 코드로 가리키면, 이하의 표와 같은 80개의 Tierra 언어로 구성되어 있다. 또한 여기에서는 예로서 코드의 개시 주소가 스프의 30000번지 째에 놓여져 있도록 한다. 또 참고로서 표의 오른쪽란에 AX, BX, CX, DX의 각 레지스터에 어떻게 값이 격납되는지를 나타냈다. (아래표 보는 방법; 첫행을 예로 들면 주소는 "30000", 명령어는 "nop_1", 설명은 "어머니 셀 코드 개시 주소 템플릿", AX BX CX DX 모두 "-"이다. 차례로 읽어나가면 된다.)
주소 명령어 설명 AX BX CX DX
자기 검사 코드 블록
30000 nop_1 어머니 셀 코드 개시 주소 템플릿 - - - -
30001 nop_1 어머니 셀 코드 개시 주소 템플릿 - - - -
30002 nop_1 어머니 셀 코드 개시 주소 템플릿 - - - -
30003 nop_1 어머니 셀 코드 개시 주소 템플릿 - - - -
30004 zero CX레지스터에 값 0을 격납. - - 0 -
30005 or1 CX레지스터의 제1 비트에 1을 세트 - - 1 -
30006 shl CX레지스터의 값을 1 비트 왼쪽 쉬프트 - - 2 -
30007 shl CX레지스터의 값을 하나 더 1 비트왼쪽 쉬프트. CX레지스터에는 템플릿 사이즈가 격납된다. - - 4 -
30008 mov_cd DX=CX, DX에 템플릿 사이즈가 격납된다. - - 4 4
30009 adrb 후속의 일련의 nop 명령에 의한 템플릿과 상보적인 템플릿의 주소(상보적인 템플릿의 마지막 nop 명령의 다음의 주소)를 전방(주소치가 줄어들 방향으로) 탐색한다. 이것에 의해 어머니 셀의 코드 개시 주소 템플릿 의 주소가 요구되어 그 값은 AX레지스터에 격납된다. 30004 - 4 4
30010 nop_0 코드 개시 주소 템플릿과 상보적인 템플릿 30004 - 4 4
30011 nop_0 코드 개시 주소 템플릿과 상보적인 템플릿 30004 - 4 4
30012 nop_0 코드 개시 주소 템플릿과 상보적인 템플릿 30004 - 4 4
30013 nop_0 코드 개시 주소 템플릿과 상보적인 템플릿 30004 - 4 4
30014 sub_ac AX = AX - CX를 계산. 이것에 의해 어머니 셀의 코드 개시 주소 템플릿의 최초의 주소, 즉 어머니 셀의 개시 어드레스가 구해진다. 그 값은 AX레지스터에 격납된다. 30000 - 4 4
30015 mov_ab BX = AX를 실시한다.
즉 어머니 셀의 코드 개시 주소의 값을 BX 레지스터에 카피한다. 30000 30000 4 4
30016 adrf 후속의 일련의 nop 명령에 의한 템플릿과 상보적인 템플릿의 주소를 후방 (주소치가 증가하는 방향)에 탐색한다. 그것에 의해, 코드 종료 아드레스 템플릿의 주소가 요구된다. 그 값은 AX 레지스타에 격납된다. 30079 30000 4 4
30017 nop_0 코드 종료 주소 템플릿과 상보적인 템플릿 30079 30000 4 4
30018 nop_0 코드 종료 주소 템플릿과 상보적인 템플릿 30079 30000 4 4
30019 nop_0 코드 종료 주소 템플릿과 상보적인 템플릿 30079 30000 4 4
30020 nop_1 코드 종료 주소 템플릿과 상보적인 템플릿 30079 30000 4 4
30021 inc_a AX = AX + 1을 계산.
이 게놈 코드에는 코드 종료 주소 템플릿의 다음에 근처의 게놈과의 단락을 위한 더미명령이 1 단어가 포함되어 있다(30079번지). 또, 이 더미 명령의 주소가 어머니 셀의 코드 종료 아 드레스이지만, 다음에 코드의 사이즈를 올바르게 계산하기 위해서 AX레지스터의 값에 1을 더해 둔다. 30080 30000 4 4
30022 sub_ab CX = AX - BX를 계산.
어머니 셀의 코드 사이즈를 계산해, CX레지스터에 격납한다. 30080 30000 80 4
자기 복제 루프의 코드 블록
30023 nop_1 자기 복제 루프의 주소 템플릿 30080 30000 80 4
30024 nop_1 자기 복제 루프의 주소 템플릿 30080 30000 80 4
30025 nop_0 자기 복제 루프의 주소 템플릿 30080 30000 80 4
30026 nop_1 자기 복제 루프의 주소 템플릿 30080 30000 80 4
30027 mal 딸 셀의 영역, 이 경우 연속한 80 명령분의 영역을 스프중에 확보해, 그 선두 주소를 AX레지스터에 격납한다. 예로서 31000으로 한다. 31000 30000 80 4
30028 call 후속 하는 일련의 nop 명령에 의한 템플릿과 상보적인 템플릿을 탐색해, 그 템플릿의 주소에 있는 명령의 실행을 실시한다. 여기에서는 카피 프로세스를 호출하고 있다. 31000 30000 80 4
30029 nop_0 카피 프로세스의 개시 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30030 nop_0 카피 프로세스의 개시 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30031 nop_1 카피 프로세스의 개시 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30032 nop_1 카피 프로세스의 개시 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30033 divide 딸 셀을 독립시킨다. 어머니 셀은 딸 셀의 영역에의 명령어를 기입할 수 없게 된다. 딸 셀에는 명령 pointer가 주어져 슬라이스·큐와 리퍼·큐에 들어간다. 31000 30000 80 4
30034 jmp 후속 하는 일련의 nop 명령에 의한 템플릿과 상보적인 템플릿의 다음의 명령(30027 mal)에 점프한다. 이것에 의해 새로운 딸 셀의 복제를 시작한다. 31000 30000 80 4
30035 nop_0 자기 복제 루프의 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30036 nop_0 자기 복제 루프의 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30037 nop_1 자기 복제 루프의 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30038 nop_0 자기 복제 루프의 주소 템플릿과 상보적인 템플릿 31000 30000 80 4
30039 if_cz 카피 프로세스의 템플릿과 단락짓기 위한 더미 명령. 31000 30000 80 4
카피 프로세스 코드 블록
30040 nop_1 카피 프로세스의 템플릿 31000 30000 80 4
30041 nop_1 카피 프로세스의 템플릿 31000 30000 80 4
30042 nop_0 카피 프로세스의 템플릿 31000 30000 80 4
30043 nop_0 카피 프로세스의 템플릿 31000 30000 80 4
30044 push_ax AX레지스터의 값을 스택에 격납. 딸 셀의 코드 개시 주소를 스택에 퇴피(退避)해 둔다. 31000 30000 80 4
30045 push_bx BX레지스터의 값을 스택에 격납. 어머니 셀의 코드 개시 주소를 스택에 퇴피해 둔다. 31000 30000 80 4
30046 push_cx CX레지스터의 값을 스택에 격납. 어머니 셀의 코드 사이즈를 스택에 퇴피해 둔다. 31000 30000 80 4
30047 nop_1 카피 루프 개시 주소 템플릿 31000 30000 80 4
30048 nop_0 카피 루프 개시 주소 템플릿 31000 30000 80 4
30049 nop_1 카피 루프 개시 주소 템플릿 31000 30000 80 4
30050 nop_0 카피 루프 개시 주소 템플릿 31000 30000 80 4
30051 mov_iab BX레지스터에 격납되어 있는 주소의 명령어를, AX레지스터에 격납되어 있는 주소에 카피한다. 예를 들면, 어머니 셀의 코드 개시 주소 30000에 있는 명령어 nop_1을 딸 셀의 코드 개시 주소 31000에 카피한다. 31000 30000 80 4
30052 dec_c CX레지스터의 값을 1줄인다. 예를 들어 80이 79가 된다. 31000 30000 79 4
30053 if_cz 만약 CX레지스터의 값이 0, 즉 어머니 셀의 모든 명령어를 딸 셀에 카피 해 두려면 다음의 명령(30053 jmp)을 실행한다. 그렇지 않으면, 그것을 스킵 해 그 다음의 명령(30055 nop_0)를 실행한다. 즉, CX레지스터의 값 만큼 카피 루프가 실행된다. 31000 30000 79 4
30054 jmp 후속 하는 일련의 nop 명령에 의한 템플릿과 상보적인 템플릿의 다음 명령(30071 pop_cx)에 점프한다. 31000 30000 79 4
30055 nop_0 카피 프로세스 종료 주소 템플릿과 상보적인 템플릿 31000 30000 79 4
30056 nop_1 카피 프로세스 종료 주소 템플릿과 상보적인 템플릿 31000 30000 79 4
30057 nop_0 카피 프로세스 종료 주소 템플릿과 상보적인 템플릿 31000 30000 79 4
30058 nop_0 카피 프로세스 종료 주소 템플릿과 상보적인 템플릿 31000 30000 79 4
30059 inc_a AX레지스터의 값을 1 증가한다. 어머니 셀의 다음의 명령어를 가리킨다. 31001 30000 79 4
30060 inc_b BX레지스터의 값을 1 증가한다. 딸 셀의 다음의 주소치가 된다. 31001 30001 79 4
30061 jmp 후속 하는 일련의 nop 명령에 의한 템플릿과 상보적인 템플릿의 다음의 주소에 있는 명령(30051 mov_iab)으로 점프한다. 다음의 명령어의 카피를 실시한다. 31001 30001 79 4
30062 nop_0 카피 루프 개시 주소 템플릿과 상보적인 템플릿 31001 30001 79 4
30063 nop_1 카피 루프 개시 주소 템플릿과 상보적인 템플릿 31001 30001 79 4
30064 nop_0 카피 루프 개시 주소 템플릿과 상보적인 템플릿 31001 30001 79 4
30065 nop_1 카피 루프 개시 주소 템플릿과 상보적인 템플릿 31001 30001 79 4
30066 if_cz 템플릿과 템플릿을 단락짓기 위한 더미 명령. 31001 30001 79 4
30067 nop_1 카피 프로세스 종료 주소 템플릿 31001 30001 79 4
30068 nop_0 카피 프로세스 종료 주소 템플릿 31001 30001 79 4
30069 nop_1 카피 프로세스 종료 주소 템플릿 31001 30001 79 4
30070 nop_1 카피 프로세스 종료 주소 템플릿 31001 30001 79 4
30071 pop_cx 스택으로부터 CX레지스터에 값(어머니 셀의 코드 사이즈)을 복귀시킨다. 31001 30001 80 4
30072 pop_bx 스택으로부터 BX레지스터에 값(어머니 셀의 코드 개시 주소)을 복귀시킨다. 31001 30000 80 4
30073 pop_ax 스택으로부터 AX레지스터에 값(딸 셀의 코드 개시 주소)을 복귀시킨다. 31000 30000 80 4
30074 ret 카피 프로세스를 종료해, 이 루틴을 call 한 명령어의 다음 명령어를 실행한다. 31000 30000 80 4
코드 종료 블록
30075 nop_1 코드 종료 주소 템플릿 - - - -
30076 nop_1 코드 종료 주소 템플릿- - - -
30077 nop_1 코드 종료 주소 템플릿- - - -
30078 nop_0 코드 종료 주소 템플릿- - - -
30079 if_cz 다른 셀과의 단락을 위한 더미 명령 - - - -
여기서 Tierra에서 일어난 진화의 예를 몇 개 소개하겠다. 여기서 설명하는 진화의 예는, 사이즈 60000(Tierra 언어 명령 60000개 분 )의 스프 메모리에, 앞장에서 설명한 80 명령으로 구성된 선조종(80aaa)을 배양시킨 결과이다. Tierra에 대해 시간은 Tierra 언어 명령의 전실행 회수로 카운트 된다. 선조종은 839 명령에서 최초의 자기 복제를 실시해, 2번째 이후는 813 명령으로 딸 셀을 복제한다. 리퍼는 스프 메모리의80%가 명령어로 가득 찬 후에 기동된다. 일단 리퍼가 기동되면 그 후 스프 메모리의 점유율은 대략 80%로 유지된다.
비트 반전에 의한 진화
비트 반전에 의한 돌연변이의 영향에 대해 고찰해 보자. 비트 반전에 의한 돌연변이에서는 게놈의 사이즈는 변하지 않는다. 그러나 비트 반전에 의해 어떤 명령어가 다른 명령어로 되면, 자기 복제 프로세스에 영향을 준다.
예를 들면, no-operation 명령(nop_0, nop_1)에 비트 반전이 일어나면, 이하와 같이 일어날 수 있는 5개의 변이 가운데 1개는 다른 no-operation 명령으로, 나머지 4개는 다른 종류의 명령으로 바뀐다.
명령어(16진, 2진표시)
nop_0 (0x00, 00000) --> nop_1 (0x01, 00001)
--> or1 (0x02, 00010)
--> zero (0x04, 00100)
--> inc_a (0x08, 01000)
--> call (0x16, 10000)
nop_1 (0x01, 00001) --> nop_0 (0x00, 00000)
--> shl (0x03, 00011)
--> if_cx (0x05, 00101)
--> inc_b (0x09, 01001)
--> ret (0x17, 10001)
즉, no-operation 명령으로 비트 반전이 일어나면 80%의 확률로 템플릿의 사이즈를 바꾸어 버리든지, 또는 20%의 확률로 템플릿의 패턴을 바꾸어 버린다. 템플릿의 패턴의 변화는 사이즈 계측의 잘못해, 복제 루틴의 호출이나 루프 , 점프 명령 시에 잘못된 명령 pointer를 지시하는 등의 현상을 일으킨다.
전형적인 진화의 프로세스를 Artificial Life Monitor (ALmond) 프로그램 (by Marc Cygnus mcygnus@mcs.com)에 의해 볼 수가 있다. 이하의 그림은 Tierra Photo Essay 로부터 전재했다.
이러한 그림은 선조종이 스프메모리를 채운 후, 파라사이트(기생종)가 출현해, 그 파라사이트에 대해서 면역 기능을 가진 종이 후속해서 나타나는 모습을 보여주고 있다.
적색선으로 나타나는 숙주(선조종 사이즈 80)가 스프 메모리의 대부분을 차지하고 있다. 황색선으로 표시된 파라사이트(사이즈 45)는 아직 적다.
파라사이트가 증식 해 호스트의 수가 급감했다. 면역종(청색선, 사이즈 79)이 나타나기 시작했다.
면역종이 증식하기 시작한다
스프메모리의 대부분이 면역종으로 채워진다. 이 후 파라사이트는 멸종한다.
선조종 80 aaa의 43번째의 명령어 nop_0에 비트 반전이 일어나, 템플릿의 패턴이 바뀌면, 흥미로운 새로운 종이 탄생했다. 43번째의 명령어는 다른 3개의 no-operation 명령 과 함께 카피 프로세스의 시작을 나타내는 템플릿을 구성하고 있다. 이 템플릿 (nop1, nop1, nop0, nop0)이 (nop1, nop1, nop1, nop0)으로 변이해 버렸다. 선조종에서는 템플릿(nop1, nop1, nop1, nop0)은 게놈의 종료 위치를 나타내는 템플릿이다. 따라서 변이종은 43번째의 명령어가 포함되는 템플릿을 게놈의 종료 위치로 착각해 버려, 45번째의 명령어까지 밖에 복제하지 않는다. 이렇게 해 사이즈 45의 신종 45 aaa가 태어난다.
이 신종 45 aaa는 카피 프로세스를 가지지 않는다. 따라서 단독으로는 자기 복제를 실시할 수 없다. 그러나 Tierra의 생물들은 스프메모리의 반투막적인 성질에 의해, 다른 생물의 스프메모리 영역에 있는 명령어를 "읽는" 일은 할 수 있다. 만약, 0045 aaa의 근처에 선조종 80 aaa가 존재하고 있어, 템플릿의 탐색 범위 내(보통은 200에서 400 명령어 분만큼 세트 해 둔다)에 카피 프로세스가 있으면, 45 aaa는 그것을 이용해 자기 복제를 실행할 수가 있다. 이와 같이 45 aaa는 선조종 80 aaa의 근처에 있어, 그 코드의 일부를 이용하는 일로부터, 톰·레이는 이 종을 파라사이트(기생종)라고 이름 붙였다.
파라사이트 0045 aaa의 코드를 나타낸다.
nop1 ; 01 0
nop1 ; 01 1
nop1 ; 01 2
nop1 ; 01 3
zero ; 04 4
not0 ; 02 5
shl ; 03 6
shl ; 03 7
movDC ; 18 8
adrb ; 1c 9
nop0 ; 00 10
nop0 ; 00 11
nop0 ; 00 12
nop0 ; 00 13
subAAC ; 07 14
movBA ; 19 15
adrf ; 1d 16
nop0 ; 00 17
nop0 ; 00 18
nop0 ; 00 19
nop1 ; 01 20
incA ; 08 21
subCAB ; 06 22
nop1 ; 01 23
nop1 ; 01 24
nop0 ; 00 25
nop1 ; 01 26
mal ; 1e 27
call ; 16 28
nop0 ; 00 29
nop0 ; 00 30
nop1 ; 01 31
nop1 ; 01 32
divide ; 1f 33
jmpo ; 14 34
nop0 ; 00 35
nop0 ; 00 36
nop1 ; 01 37
nop0 ; 00 38
ifz ; 05 39
nop1 ; 01 40
nop1 ; 01 41
nop1 ; 01 42
nop0 ; 00 43
pushA ; 0c 44
톰 레이(Ray, T. S. 1992. Evolution, ecology and optimization of digital organisms. Santa Fe Institute working paper 92-08-042.)에 의하면, 사이즈79인 종은, 파라사이트에 대한 면역 기능을 획득했다. 0079 aab라고 하는 게놈 타잎을 가진 종의 양 옆에 파라사이트 0045 aaa를 두어 각각을 번식시키면, 0045 aaa는 최초 가운데는 복제를 실시할 수 있지만, 그 후 스프 메모리로부터 배제되어 버리고 만다.
0079 aaa가 스프 메모리를 지배한 후, 0051 aao라고 하는 새로운 기생종이 출현했다. 이 종은 어떠한 방법으로 0079 aab의 면역 기능을 회피하고 있다고 생각된다.
톰·레이에 의하면, 이 0079 aab와 0051 aao 라는 게놈 타잎은 그의 유전자 은행으로부터는 소실되어 버렸고, 유전자 코드는 입수할 수 없었다. 다만, Tierra에 있어 기생종에 대한 방어는 생각보다는 용이하게 실현될 수 있다. 예를 들어, 기생종은 숙주의 카피 루틴을 call 명령에 의해 호출하는 것이기 때문에, 숙주의 카피 루틴 템플릿이, 기생종의 가지고 있지 않은 템플릿으로 옮겨지면, 이미 기생종은 숙주의 카피 루틴을 호출하는 일은 할 수 없게 된다.
레이에 의하면, 0080 gai라고 하는 종은 파라사이트의 공격을 반대로 이용해 배제해 버리기 때문에 하이퍼·파라사이트로 불린다. 0080 gai는 카피 루틴이 끝나도 ret 명령이 없기 때문에, 호출하고 원래로 리턴 하지 않는다. 그 대신 jmpb 명령으로 카피 프로세스의 적절한 장소로 돌아가 버린다. 이와 같이 해, 이 종은 파라사이트의 IP(명령 pointer)를 빼앗아 버린다. 게다가 자기 복제 처리가 끝날 때마다, 자기 사이즈 계측 코드로 돌아와 원본카피의 주소를 격납하고 있는 bx레지스터와 카피 사이즈를 격납하고 있는 cx레지스터의 값을 리셋트 해버린다. 이와 같이 해 파라사이트의 CPU에는 하이퍼·파라사이트의 코드를 카피 하기 위한 주소값과 사이즈가 격납되어버려 파라사이트는 하이퍼·파라사이트의 코드를 카피하지 않으면 안되게 되어 버린다.
여기서 설명한 0080 gai의 코드도 잃어버린 것 같다. 그림에 있는 것과 같은 기능을 가진 게놈 코드를 메뉴얼로 고쳐 쓰는 일도 가능하겠지만, 여기에서는 추가해서 다른 하이퍼·파라사이트 0078 aaa의 코드를 보여주고 있다. 파라사이트가 0078 aaa의 카피 루틴을 사용해 1회째의 전체 게놈의 카피를 실시한 후, 45행째의 jmp 명령으로 22행째의 divide 명령이 실행되어 1회째의 자기 복제에는 성공한다. 그러나 23행째의 jmpb 명령에 의해 , IP가 3행째의 adrb에 세트 되어 버린다. 따라서 2번째로부터는, 파라사이트 는 이 하이퍼·파라사이트의 복제를 실시하는 일이 되어 버린다.
그런데 이 게놈에는 하나 더 주목해야 할 특징이 있다. 그것은 자기 검사의 코드이다. 선조종에서는 템플릿 사이즈를 쉬프트 명령 등에 의해 계산하고 있었지만, 이 게놈은 adrb 명령을 사용해 그 수고를 생략하고 있다.
코드를 보면 알 수 있듯이 처음은 adrb, nop0, nop0, nop1에 의해 개시 주소의 템플릿 을 요구하고 있다. 이것에 의해, ax레지스터의 값은 개시 주소+템플릿 사이즈가 된다. 이 때 adrb 명령은 동시에 템플릿 사이즈를 cx레지스터에 격납 한다. 다음에 sub_ac명령에 의해, ax = ax - cx를 계산해 개시 주소가 계산된다. 다음에 movab 명령에 의해 bx레지스터에도 개시 주소를 카피한다. 그리고 adrf, nop0, nop0, nop0 명령에 의해 코드 종료 주소를 요구해 결과를 ax레지스터에 격납한다. 다음의 jmb 명령은 무시되어 zero 명령으로 cx레지스터를 0으로 해, sub_ab명령으로 cx = ax - bx에 의해 사이즈를 계산해 결과를 cx레지스터에 격납한다.
nop1 ; 01 0
nop1 ; 01 1
nop0 ; 00 2
adrb ; 1c 3
nop0 ; 00 4
nop0 ; 00 5
nop1 ; 01 6
sub_ac ; 07 7
movab ; 19 8
adrf ; 1d 9
nop0 ; 00 10
nop0 ; 00 11
nop0 ; 00 12
jmpb ; 15 13
zero ; 04 14
sub_ab ; 06 15
mal ; 1e 16
call ; 16 17
nop0 ; 00 18
nop0 ; 00 19
nop1 ; 01 20
nop1 ; 01 21
divide ; 1f 22
jmpb ; 15 23
nop0 ; 00 24
nop0 ; 00 25
nop1 ; 01 26
jmp ; 14 27
nop1 ; 01 28
nop0 ; 00 29
ifz ; 05 30
nop1 ; 01 31
nop1 ; 01 32
nop0 ; 00 33
nop0 ; 00 34
pushax ; 0c 35
pushbx ; 0d 36
pushcx ; 0e 37
nop1 ; 01 38
nop0 ; 00 39
nop1 ; 01 40
nop0 ; 00 41
movii ; 1a 42
dec_c ; 0a 43
ifz ; 05 44
jmp ; 14 45
nop1 ; 01 46
nop1 ; 01 47
nop0 ; 00 48
nop0 ; 00 49
inc_a ; 08 50
inc_b ; 09 51
jmpb ; 15 52
nop0 ; 00 53
nop1 ; 01 54
nop0 ; 00 55
nop1 ; 01 56
jmpb ; 15 57
nop1 ; 01 58
nop0 ; 00 59
popbx ; 11 60
nop1 ; 01 61
popcx ; 12 62
popbx ; 11 63
popbx ; 11 64
ret ; 17 65
ifz ; 05 44
ifz ; 05 44
ifz ; 05 44
ifz ; 05 44
ifz ; 05 44
ifz ; 05 44
ifz ; 05 44
ifz ; 05 44
nop0 ; 00 66
nop1 ; 01 67
nop1 ; 01 68
nop1 ; 01 69
사회적 하이퍼·파라사이트 0061 acg는 집단이 되어, 서로 서로 도우면서 복제를 실시한다. 하이퍼·파라사이트는 자기 복제가 끝나면 jmpb0000 명령 에 의해 자신의 자기 사이즈 계측 코드에 점프 하지만, 이 게놈의 경우는 jmpb010에 의해 자신의 선두 코드 를 넘어, 자기의 앞에 존재하는 0061 acg의 후미에 있는 jmpb 0101의 템플릿을 표적으로 해 점프 한다. Tierra에서는 010의 상보적 템플릿으로서 0101도 패턴 매칭(최초의 0을 무시 해 101으로 인식) 하고 있다. 이렇게 해, 이 하이퍼·파라사이트는 재차, 자기 사이즈 계측 코드를 실행할 수 있다. 이 게놈이 몇 개가 죽 줄지어 있으면, 이 순서가 차례차례로 반복되어지므로 순조로운 자기 복제가 가능하게 된다. 만약, 이 게놈의 앞에 다른 코드를 가진 종이 있는 경우는 그 수순은 올바르게 행해지지 않는다.
보통 하이퍼·파라사이트에 대해서 이런 종류의 유리한 점은 게놈·코드가 짧아지는 일 이다. 특히 대부분의 템플릿의 길이를 선조 종의 4에 대해서 3으로 줄어들도록 진화 하고 있다.
사회적 하이퍼·파라사이트 0061 aaa의 코드를 나타낸다.
nop1 ; 01 0
nop1 ; 01 1
nop0 ; 00 2
adrb ; 1c 3
nop0 ; 00 4
nop0 ; 00 5
nop1 ; 01 6
sub_ac ; 07 7
movab ; 19 8
adrf ; 1d 9
nop0 ; 00 10
nop0 ; 00 11
nop0 ; 00 12
zero ; 04 13
zero ; 04 14
sub_ab ; 06 15
mal ; 1e 16
call ; 16 17
nop0 ; 00 18
nop0 ; 00 19
nop1 ; 01 20
inc_b ; 09 21
divide ; 1f 22
jmpb ; 15 23
nop0 ; 00 24
nop1 ; 01 25
nop0 ; 00 26
call ; 16 27
movab ; 19 28
pushcx ; 0e 29
ifz ; 05 30
nop1 ; 01 31
nop1 ; 01 32
nop0 ; 00 33
nop0 ; 00 34
pushax ; 0c 35
pushcx ; 0e 36
pushcx ; 0e 37
nop1 ; 01 38
nop0 ; 00 39
nop1 ; 01 40
nop0 ; 00 41
movii ; 1a 42
dec_c ; 0a 43
ifz ; 05 44
jmpb ; 15 45
nop1 ; 01 46
nop1 ; 01 47
nop0 ; 00 48
inc_a ; 08 49
inc_b ; 09 50
jmpb ; 15 51
nop0 ; 00 52
nop1 ; 01 53
nop0 ; 00 54
nop1 ; 01 55
pushdx ; 0f 56
popbx ; 11 57
nop1 ; 01 58
nop1 ; 01 59
nop1 ; 01 60
게놈 0027 aab는 사기꾼(cheater)로 불리는 것으로 사회적 하이퍼 파라사이트의 사이에 끼어들어, IP(인스트럭션instruction 포인터)를 강탈해 자기 복제를 실시한다. 카피 루틴도 사회적 하이퍼 파라사이트의 물건을 사용한다.
사기꾼 0027 aab의 코드는 아래와 같다.
nop1 ; 01 0
nop1 ; 01 1
nop0 ; 00 2
adrb ; 1c 3
nop0 ; 00 4
nop0 ; 00 5
nop1 ; 01 6
sub_ac ; 07 7
movab ; 19 8
adrf ; 1d 9
nop0 ; 00 10
nop0 ; 00 11
nop0 ; 00 12
zero ; 04 13
sub_ab ; 06 14
sub_ab ; 06 15
mal ; 1e 16
call ; 16 17
nop0 ; 00 18
nop0 ; 00 19
nop1 ; 01 20
nop1 ; 01 21
divide ; 1f 22
jmp ; 14 23
nop1 ; 01 24
nop1 ; 01 25
nop1 ; 01 26
지금까지 말해 온 디지털 생물들의 진화는 대략 10억 명령쯤의 기간에 발생한 사건이다 . 여기에서는 150억 명령 후에 스프메모리를 조사해 발견된, 고도로 발달 한 디지털 생물의 게놈에 대해 기술하고자 한다.
이 게놈(0072etq)은 2개의 특징을 가지고 있다.
1. 새로운 자기 계측 방법
지금까지 말해 온 디지털 생물은 자기 계측 때, 코드의 시작과 끝을 나타내는 템플릿 의 주소를 요구해 그 차이로부터 사이즈를 계산하고 있었다. 이 디지털 생물은 전반의 36 명령의 코드밖에 작동하지 않는다. 그리고 코드 종료 템플릿을 사용하지 않고, adrf, nop 명령(6,7행째)에 의해, 코드의 중간 정도(34행째nop)의 템플릿을 두어 그 주소를 요구해 sub_ab 명령(10행째)으로 cx레지스터에 코드의 사이즈의 반(36)을 세트해, 더욱 더 shl 명령(12행째)으로 2배로 정확한 사이즈를 계산하고 있다.
2. 루프의 전개에 의한 카피 프로세스의 효율화
선조종의 카피 루프는 이하와 같은 순서에 의해 행해지고 있었다.
(1) 명령어를 어머니 셀로부터 딸 셀에 카피한다.
(2) cx레지스터의 값(어머니 셀의 사이즈)을 1만큼 줄인다.
(3) cx레지스터의 값이 0이 되면 카피 루프를 나간다.
0이 아니면 루프내의 다음의 처리를 실시한다.
(4) ax레지스터의 값(딸 셀의 명령어의 카피처 주소)을 1 증가한다.
(5) bx레지스터의 값(어머니 셀의 명령어의 카피원주소)을 1 증가한다.
(6) 카피 루프의 처음으로 돌아간다.
이것에 대해서 72 etq는 다음의 순서를 사용한다.
(1) 명령어를 어머니 셀로부터 딸 셀에 카피한다. (15행째)
(2) cx레지스터의 값을 3줄인다. (16-19행째)
(3) ax레지스터의 값을 1 증가한다. (20행째)
(4) bx레지스터의 값을 1 증가한다. (21행째)
(5) 명령어를 어머니 셀로부터 딸 셀에 카피한다. (22행째)
(6) cx레지스터의 값을 1줄인다. (23행째)
(7) ax레지스터의 값을 1 증가한다. (24행째)
(8) bx레지스터의 값을 1 증가한다. (25행째)
(9) 명령어를 어머니 셀로부터 딸 셀에 카피한다. (26행째)
(10) cx레지스터의 값을 1줄인다. (27행째)
(11) cx레지스터의 최하위 비트를 반전한다. (28행째) 루프의 최초의 cx레지스터의 값이 짝수라면, 이 코드의 실행시에는 cx레지스터의 최하위 비트는 반드시 1이 되어 있다. 따라서, 이 명령은 cx레지스터의 값을 1 더 줄이는 것과 같은 효과를 가져온다.
(12) cx레지스터의 값이 0이 되면 카피 루프를 나간다. (29행째) 0이 아니면 루프내의 다음의 처리를 실시한다.
(13) ax레지스터의 값을 1 증가한다. (31행째)
(14) bx레지스터의 값을 1 증가한다. (32행째)
(15) 카피 루프의 처음으로 돌아간다. (33행째)
1회의 루프로 3개의 명령어를 카피한다. 이것에 의해, (12)의 비교나 (15)의 카피 루프의 처음으로 돌아가는 처리가, 카피마다 체크하는데 비교해, 1/3로 끝낼 수 있다. 그리고 이 3개의 명령어의 카피에 필요로 하는 명령 실행 회수는, 세어 보면 18이며, 이것은 1 명령어의 카피에 6 명령으로 끝낸다는 것을 의미한다. 선조종의 경우도 이와 같이 세어 보면, 1 명령어의 카피에 10 명령을 필요로 하고 있으므로 40%도 효율이 향상된 것이다.
또, cx레지스터의 값은 shl 명령(12행째)으로 최초 72에 세트되어 있는 것으로, 이 루프는 12회 주위 전반의 36 코드만이 복제된다. 딸 셀의 나머지의 36 명령 분의 스페이스는 졍크 코드가 된다. 이와 같이 필요한 스페이스의 2배의 스페이스를 취하는 일에 의해, 보다 많은 CPU 시간을 얻을 수 있다. 이러한 현상은 슬라이스 타임과 게놈의 사이즈가 동일해지도록 환경 설정을 실시했을 때에 나타난다.
nop1 ; 01 0
adrb ; 1c 1
nop0 ; 00 2
divide ; 1f 3
sub_ac ; 07 4
movab ; 19 5
adrf ; 1d 6
nop0 ; 00 7
inc_a ; 08 8
call ; 16 9
sub_ab ; 06 10
pushbx ; 0d 11
shl ; 03 12
mal ; 1e 13
nop0 ; 00 14
movii ; 1a 15
dec_c ; 0a 16
dec_c ; 0a 17
jmpb ; 15 18
dec_c ; 0a 19
inc_a ; 08 20
inc_b ; 09 21
movii ; 1a 22
dec_c ; 0a 23
inc_a ; 08 24
inc_b ; 09 25
movii ; 1a 26
dec_c ; 0a 27
not0 ; 02 28
ifz ; 05 29
ret ; 17 30
inc_a ; 08 31
inc_b ; 09 32
jmpb ; 15 33
nop1 ; 01 34
ifz ; 05 35
nop1 ; 01 36
adrb ; 1c 37
nop0 ; 00 38
divide ; 1f 39
sub_ac ; 07 40
movab ; 19 41
adrf ; 1d 42
nop0 ; 00 43
inc_a ; 08 44
call ; 16 45
sub_ab ; 06 46
pushbx ; 0d 47
shl ; 03 48
mal ; 1e 49
nop0 ; 00 50
movii ; 1a 51
dec_c ; 0a 52
dec_c ; 0a 53
jmpb ; 15 54
dec_c ; 0a 55
inc_a ; 08 56
inc_b ; 09 57
movii ; 1a 58
dec_c ; 0a 59
inc_a ; 08 60
inc_b ; 09 61
movii ; 1a 62
dec_c ; 0a 63
not0 ; 02 64
ifz ; 05 65
ret ; 17 66
inc_a ; 08 67
inc_b ; 09 68
jmpb ; 15 69
nop1 ; 01 70
ifz ; 05 71
Tierra의 가상 기계어(Tierra language)는 모두 C언어로 쓰여져 있으므로, 명령 세트를 자유롭게 다시 만들 수가 있다. 여기에서는 1992년까지 만들어진 4개(살)의 명령 세트를 소개한다. 이러한 명령 세트는 그 해에 Santa Fe연구소에서 행해진 명령 세트의 개선에 관한 회의에서 서로 논의한 아이디어를 Tom Ray 가 프로그래밍 한 것이다.
이 회의에는 Steen Rassmussen(Santa Fe연구소), Walter Tackett(Hughes Aircraft), Chris Stephenson(IBM), Kurt Thearling (Thinking Machines), Dan Pirone (Santa Fe 연구소)와 Tom Ray가 참가했다.
4개의 명령 세트의 1번째는 Tierra 개발 초기의 것으로 다른 3개의 명령 세트와의 정합성을 취하기 위해서 다시 조금 고친 것이다. 2번째의 명령 세트는 Kurt Thearling가, 3번째의 명령 세트는 Tom Ray 자신이, 4번째는 Walter Tackett가 제안했다.
명령 세트 1
Tierra 개발 당초에 Tom Ray 자신이 설계한 명령 세트이다. 이 명령 세트는 사이즈 80의 "선조종"을 실행시키기 위해서 고안되었다. 따라서, 몇 가지 부족한 기능이 있다.
우선, CPU 레지스터와 메모리 스프의 사이에 정보를 교환하는 일을 할 수 없다. I/O명령이 없다. 2개의 레지스터의 사이에서만, 정보의 이동이 가능하다. 다만 이 부족한 기능은 스택을 사용하는 것으로 대체할 수 있다. 딸 셀의 메모리 확보의 방법으로 "first fit"로 불리는 방법 이외에 선택할 수 없다. "다세포"성을 실현하는 기능이 없다. 등이다.
No Operations: 2
nop0 템플릿용 명령
nop1 템플릿용 명령
Memory Movement: 11
pushax push AX onto stack
pushbx push BX onto stack
pushcx push CX onto stack
pushdx push DX onto stack
popax pop from stack into AX
popbx pop from stack into BX
popcx pop from stack into CX
popdx pop from stack into DX
movcd DX = CX
movab BX = AX
movii move from ram [BX] to ram [AX]
Calculation: 9
sub_ab CX = AX - BX
sub_ac AX = AX - CX
inc_a increment AX
inc_b increment BX
inc_c increment CX
dec_c decrement CX
zero zero CX
not0 flip low order bit of CX
shl shift left all bits of CX
Instruction Pointer Manipulation: 5
ifz if CX == 0 execute next instruction, otherwise, skip it
jmp jump to template
jmpb (jump backwards to template
call push IP onto the stack, jump to template
ret pop the stack into the IP
Biological and Sensory: 5
adr search outward for template, put address in AX, template size in CX
adrb search backward for template, put address in AX, template size in CX
adrf search forward for template, put address in AX, template size in CX
mal allocate amount of space specified in CX
divide cell division
Total: 32
----------------------------------------------------------
Tierra 최초의 선조종 0080 aaa의 코드를 나타낸다.
format: 3 bits: 2156009669 EXsh TCsh TPs MFs MTd MBh
genotype: 0080aaa parent genotype: 0666god
1st_daughter: flags: 0 inst: 827 mov_daught: 80 breed_true: 1
2nd_daughter: flags: 0 inst: 809 mov_daught: 80 breed_true: 1
Origin: InstExe: 0,0 clock: 0 Thu Jan 01 -5:00:00 1970
MaxPropPop: 0.8306 MaxPropInst: 0.4239 mpp_time: 0,0
ploidy: 1 track: 0
comments: the ancestor, written by a human, mother of all other creatures.
track 0: prot
xwr
nop1 ; 010 110 01 0 beginning marker
nop1 ; 010 110 01 1 beginning marker
nop1 ; 010 110 01 2 beginning marker
nop1 ; 010 110 01 3 beginning marker
zero ; 010 110 04 4 put zero in cx
not0 ; 010 110 02 5 put 1 in first bit of cx
shl ; 010 110 03 6 shift left cx (cx = 2)
shl ; 010 110 03 7 shift left cx (cx = 4)
movcd ; 010 110 18 8 move cx to dx (dx = 4)
adrb ; 010 110 1c 9 get (backward) address of beginning marker --> ax
nop0 ; 010 100 00 10 complement to beginning marker
nop0 ; 010 100 00 11 complement to beginning marker
nop0 ; 010 100 00 12 complement to beginning marker
nop0 ; 010 100 00 13 complement to beginning marker
sub_ac ; 010 110 07 14 subtract cx from ax, result in ax
movab ; 010 110 19 15 move ax to bx, bx now contains start address of mother
adrf ; 010 110 1d 16 get (forward) address of end marker --> ax
nop0 ; 010 100 00 17 complement to end marker
nop0 ; 010 100 00 18 complement to end marker
nop0 ; 010 100 00 19 complement to end marker
nop1 ; 010 100 01 20 complement to end marker
inc_a ; 010 110 08 21 increment ax, to include dummy instruction at end
sub_ab ; 010 110 06 22 subtract bx from ax to get size, result in cx
nop1 ; 010 110 01 23 reproduction loop marker
nop1 ; 010 110 01 24 reproduction loop marker
nop0 ; 010 110 00 25 reproduction loop marker
nop1 ; 010 110 01 26 reproduction loop marker
mal ; 010 110 1e 27 allocate space (cx) for daughter, address to ax
call ; 010 110 16 28 call template below (copy procedure)
nop0 ; 010 100 00 29 copy procedure complement
nop0 ; 010 100 00 30 copy procedure complement
nop1 ; 010 100 01 31 copy procedure complement
nop1 ; 010 100 01 32 copy procedure complement
divide ; 010 110 1f 33 create independent daughter cell
jmp ; 010 110 14 34 jump to template below (reproduction loop)
nop0 ; 010 100 00 35 reproduction loop complement
nop0 ; 010 100 00 36 reproduction loop complement
nop1 ; 010 100 01 37 reproduction loop complement
nop0 ; 010 100 00 38 reproduction loop complement
ifz ; 010 000 05 39 dummy instruction to separate templates
nop1 ; 010 110 01 40 copy procedure template
nop1 ; 010 110 01 41 copy procedure template
nop0 ; 010 110 00 42 copy procedure template
nop0 ; 010 110 00 43 copy procedure template
pushax ; 010 110 0c 44 push ax onto stack
pushbx ; 010 110 0d 45 push bx onto stack
pushcx ; 010 110 0e 46 push cx onto stack
nop1 ; 010 110 01 47 copy loop template
nop0 ; 010 110 00 48 copy loop template
nop1 ; 010 110 01 49 copy loop template
nop0 ; 010 110 00 50 copy loop template
movii ; 010 110 1a 51 move contents of [bx] to [ax] (copy one instruction)
dec_c ; 010 110 0a 52 decrement cx (size)
ifz ; 010 110 05 53 if cx == 0 perform next instruction, otherwise skip it
jmp ; 010 110 14 54 jump to template below (copy procedure exit)
nop0 ; 010 110 00 55 copy procedure exit complement
nop1 ; 010 110 01 56 copy procedure exit complement
nop0 ; 010 110 00 57 copy procedure exit complement
nop0 ; 010 110 00 58 copy procedure exit complement
inc_a ; 010 110 08 59 increment ax (address in daughter to copy to)
inc_b ; 010 110 09 60 increment bx (address in mother to copy from)
jmp ; 010 110 14 61 bidirectional jump to template below (copy loop)
nop0 ; 010 100 00 62 copy loop complement
nop1 ; 010 100 01 63 copy loop complement
nop0 ; 010 100 00 64 copy loop complement
nop1 ; 010 100 01 65 copy loop complement
ifz ; 010 000 05 66 this is a dummy instruction to separate templates
nop1 ; 010 110 01 67 copy procedure exit template
nop0 ; 010 110 00 68 copy procedure exit template
nop1 ; 010 110 01 69 copy procedure exit template
nop1 ; 010 110 01 70 copy procedure exit template
popcx ; 010 110 12 71 pop cx off stack (size)
popbx ; 010 110 11 72 pop bx off stack (start address of mother)
popax ; 010 110 10 73 pop ax off stack (start address of daughter)
ret ; 010 110 17 74 return from copy procedure
nop1 ; 010 100 01 75 end template
nop1 ; 010 100 01 76 end template
nop1 ; 010 100 01 77 end template
nop0 ; 010 100 00 78 end template
ifz ; 010 000 05 79 dummy instruction to separate creature
명령 세트 2
당시 Thinking Machines사에 근무하고 있던 Kurt Thearling의 제안을 바탕으로 해 설계 되었다. 이 명령 세트의 특징은 4개의 새로운 명령 ax, bx, cx, dx에 의해 각 레지스터의 상대 위치를 늘어놓고 돌아갈 수가 있는 것이다. 그렇다면, 2개의 레지스터의 조를 만들어, 최초의 조에는 명령 세트가 작용하는 값을 넣어 두어, 나머지의 조에는 최초의 조의 어느 레지스터를 사용하는지를 지정할 수 있도록 할 수 있다.
값을 넣어 두는 레지스터의 조를 AX, BX, CX, DX로 해, 그러한 레지스터를 가리키는 레지스터를 R0, R1, R2, R3로 한다. 초기 상태에서는 R0는 AX를 R1는 BX를 R2는 CX를 R3는 DX를 가리키고 있다. 명령 add는 R2 = R1 + R0 를 실행하는 것으로써, CX = BX + AX 를 계산한다.
그러나 dx라고 하는 명령을 실행하면, R0는 DX를 가리켜, R1는 AX를 R2는 BX를 R3는 CX를 가리킨다. 그리고 여기서 add 명령을 실행하면, BX = AX + DX를 계산한다. 만약, 다시 dx명령을 실행하면, R0는 DX를 R1도 DX를 R2는 AX를 R3는 BX를 가리킨다. 따라서 add 명령은 AX = DX + DX를 계산한다. 나아가 명령 cx, bx, ax를 차례로 실시하고 레지스터의 차례는 원래대로 돌아간다.
No Operations: 2
nop0 템플릿용 명령
nop1 템플릿용 명령
Memory Movement: 12
ax make AX R0, R1 = R0, R2 = R1, R3 = R2, R3 is lost
bx make BX R0, R1 = R0, R2 = R1, R3 = R2, R3 is lost
cx make CX R0, R1 = R0, R2 = R1, R3 = R2, R3 is lost
dx make DX R0, R1 = R0, R2 = R1, R3 = R2, R3 is lost
movdd move R1 to R0
movdi move from R1 to ram [R0]
movid move from ram [R1] to R0
movii move from ram [R1] to ram [R0]
push push R0 onto stack
pop pop from stack into R0
put write R0 to output buffer, three modes: #ifndef ICC: write R0 to own output buffer #ifdef ICC: write R0 to input buffer of cell at address R1, or, if template, write R0 to input buffers of all creatures within PutLimit who have the complementary get template
get read R0 from input port
Calculation: 8
inc increment R0
dec decrement R0
add R2 = R1 + R0
sub R2 = R1 - R0
zero zero R0
not0 flip low order bit of R0
shl shift left all bits of R0
not flip all bits of R0
Instruction Pointer Manipulation: 5
ifz if R1 == 0 execute next instruction, otherwise, skip it
iffl if flag == 1 execute next instruction, otherwise, skip it
jmp jump to template, or if no template jump to address in R0
jmpb jump back to template, or if no template jump back to address in R0
call push IP + 1 onto the stack; if template, jump to complementary templ
Biological and Sensory: 5
adr search outward for template, put address in R0, template size in R1, and offset in R2, start search at offset +- R0
adrb search backward for template, put address in R0, template size in R1, and offset in R2, start search at offset - R0
adrf search forward for template, put address in R0, template size in R1, and offset in R2, start search at offset + R0
mal allocate amount of space specified in R0, prefer address at R1, if R1 < 0 use best fit, place address of allocated block in R0
divide cell division, the IP is offset by R0 into the daughter cell, the values in the four CPU registers are transferred from mother to daughter, but not the stack. If ! R1, eject genome from soup
Total: 32
-----------------------------------------------------------
이 명령 세트를 이용해 프로그램 된 선조종 0095 aaa의 코드를 나타낸다.
format: 3 bits: 3
genotype: 0095aaa parent genotype: 0666god
comments: the ancestor for instruction set 2.
track 0: prot
xwr
nop1 ; 010 000 01 0 beginning marker
nop1 ; 010 000 01 1 beginning marker
nop1 ; 010 000 01 2 beginning marker
nop1 ; 010 000 01 3 beginning marker
zero ; 010 000 12 4 zero out ax so that adrb offset is zero
adrb ; 010 000 1c 5 find start, ax = start+4, bx = templ size, cx = offset
nop0 ; 010 000 00 6 complement to beginning marker
nop0 ; 010 000 00 7 complement to beginning marker
nop0 ; 010 000 00 8 complement to beginning marker
nop0 ; 010 000 00 9 complement to beginning marker
bx ; 010 000 03 10 abcd -> babc
sub ; 010 000 11 11 bx = ax - bx, bx = start, ax = start+4, cx = offset
ax ; 010 000 02 12 abab
cx ; 010 000 04 13 caba
dx ; 010 000 05 14 dcab
zero ; 010 000 12 15 zero out dx so that adrf offset is zero
adrf ; 010 000 1d 16 find end, dx=end, cx=templ size, ax=offset, bx=start
nop0 ; 010 000 00 17 complement to end marker
nop0 ; 010 000 00 18 complement to end marker
nop0 ; 010 000 00 19 complement to end marker
nop1 ; 010 000 01 20 complement to end marker
inc ; 010 000 11 22 increment to include dummy instruction at end
bx ; 010 000 03 21 bdca
sub ; 010 000 11 22 cx = dx - bx, bx=mom, dx=end, cx=size, ax=offset
nop1 ; 010 000 01 23 reproduction loop marker
nop1 ; 010 000 01 24 reproduction loop marker
nop0 ; 010 000 00 25 reproduction loop marker
nop1 ; 010 000 01 26 reproduction loop marker
cx ; 010 000 04 27 cbdc, cx=size, bx=mom, dx=end
push ; 010 000 1a 39 save size on stack
mal ; 010 000 1e 34 allocate daughter, cx=daughter, bx=mom, dx=end, ax=off
ax ; 010 000 04 27 acbd
pop ; 010 000 04 27 ax=size, cx=daughter, bx=mom, dx=end of mom
call ; 010 000 1a 39
nop0 ; 010 000 00 40 copy procedure complement
nop0 ; 010 000 00 41 copy procedure complement
nop1 ; 010 000 01 42 copy procedure complement
nop1 ; 010 000 01 43 copy procedure complement dx=ret adr, cx=size, bx=mom
zero ; 010 000 12 44 zero out dx so that IP offset is zero
divide ; 010 000 1f 45 create independent daughter cell
bx ; 010 000 04 27 bdcb, bx=mom, dx=ret adr, cx=size
jmpb ; 010 000 19 50
nop0 ; 010 000 00 51 reproduction loop complement
nop0 ; 010 000 00 52 reproduction loop complement
nop1 ; 010 000 01 53 reproduction loop complement
nop0 ; 010 000 00 54 reproduction loop complement
ifz ; 010 000 16 55
nop1 ; 010 000 01 56 copy procedure template
nop1 ; 010 000 01 57 copy procedure template
nop0 ; 010 000 00 58 copy procedure template
nop0 ; 010 000 00 59 copy procedure template
push ; 010 000 0a 63 save (ax) length on stack
bx ; 010 000 03 60 bacd, bx=mom, ax=length, cx=daughter, dx=end of mom
push ; 010 000 0a 61 save (bx) start of mom on stack
cx ; 010 000 02 69 cbac, cx=daughter, bx=mom, ax=length, dx=end of mom
nop1 ; 010 000 01 64 copy loop template
nop0 ; 010 000 00 65 copy loop template
nop1 ; 010 000 01 66 copy loop template
nop0 ; 010 000 00 67 copy loop template
movii ; 010 000 09 70 move contents of [bx] to [cx] (copy one instruction)
ax ; 010 000 04 71 acba, ax=length, cx=daughter, bx=mom, dx=end of mom
dec ; 010 000 0f 72 decrement ax (size)
ifz ; 010 000 16 78 if ax == 0 perform next instruction, otherwise skip it
jmp ; 010 000 18 79 jump to template below (copy procedure exit)
nop0 ; 010 000 00 80 copy procedure exit complement
nop1 ; 010 000 01 81 copy procedure exit complement
nop0 ; 010 000 00 82 copy procedure exit complement
nop0 ; 010 000 00 83 copy procedure exit complement
bx ; 010 000 02 84 bacb, bx=mom, ax=length, cx=daughter, dx=end of mom
inc ; 010 000 0e 85 inc addr of mother cell
cx ; 010 000 03 86 cbac, cx=daughter, bx=mom, ax=length, dx=end of mom
inc ; 010 000 0e 87 inc addr of daughter
jmpb ; 010 000 19 92 jump back to top of copy loop
nop0 ; 010 000 00 93 copy loop complement
nop1 ; 010 000 01 94 copy loop complement
nop0 ; 010 000 00 95 copy loop complement
nop1 ; 010 000 01 96 copy loop complement
ifz ; 010 000 16 97 dummy instruction to separate templates
nop1 ; 010 000 01 98 copy procedure exit template
nop0 ; 010 000 00 99 copy procedure exit template
nop1 ; 010 000 01 100 copy procedure exit template
nop1 ; 010 000 01 101 copy procedure exit template
bx ; 010 000 03 104 bcba
pop ; 010 000 0b 105 pop bx (start of mom) off the stack
cx ; 010 000 04 102 cbcb
pop ; 010 000 0b 103 pop cx (size) off the stack
dx ; 010 000 05 106 dcbc
pop ; 010 000 0b 107 pop dx (IP) off the stack
jmp ; 010 000 18 108 return, dx=ret adr, cx=size, bx=mom
ifz ; 010 000 16 109 dummy to separate jmp from template
nop1 ; 010 000 01 110 end template
nop1 ; 010 000 01 111 end template
nop1 ; 010 000 01 112 end template
nop0 ; 010 000 00 113 end template
ifz ; 010 000 16 114 dummy to separate creatures
명령 세트 3
Tom Ray 자신이 RPN Hewlett-Packard 계산기의 특징에서 착상을 얻어 설계했다고 한다.
No Operations: 2
nop0 템플릿용 명령
nop1 템플릿용 명령
Memory Movement: 11
rollu roll registers up: AX = DX, BX = AX, CX = BX, DX = CX
rolld roll registers down: AX = BX, BX = CX, CX = DX, DX = AX
enter AX = AX, BX = AX, CX = BX, DX = CX, DX is lost
exch AX = BX, BX = AX
movdi move from BX to ram [AX]
movid move from ram [BX] to AX
movii move from ram [BX] to ram [AX]
push push AX onto stack
pop pop from stack into AX
put write AX to output buffer, three modes: #ifndef ICC: write AX to own output buffer #ifdef ICC: write AX to input buffer of cell at address BX, or, if template, write AX to input buffers of all creatures within PutLimit who have the complementary get template
get read AX from input buffer
Calculation: 9
inc increment AX
dec decrement AX
add AX = BX + AX, BX = CX, CX = DX
sub AX = BX - AX, BX = CX, CX = DX
zero zero AX
not0 flip low order bit of AX
not flip all bits of AX
shl shift left all bits of AX
rand place random number in AX
Instruction Pointer Manipulation: 5
ifz if AX == 0 execute next instruction, otherwise, skip it
iffl if flag == 1 execute next instruction, otherwise, skip it
jmp jump to template, or if no template jump to address in AX
jmpb jump back to template, or if no template jump back to address in AX
call push IP + 1 onto the stack; if template, jump to complementary templ
Biological and Sensory: 5
adr search outward for template, put address in AX, template size in BX, and offset in CX, start search at offset +- BX
adrb search backward for template, put address in AX, template size in BX, and offset in CX, start search at offset - BX
adrf search forward for template, put address in AX, template size in BX, and offset in CX, start search at offset + BX
mal allocate amount of space specified in BX, prefer address at AX, if AX < 0 use best fit, place address of allocated block in AX
divide cell division, the IP is offset by AX into the daughter cell, the values in the four CPU registers are transferred from mother to daughter, but not the stack. If ! CX genome will be ejected from the simulator
Total: 32
-----------------------------------------------------------
이 명령 세트를 이용해 프로그램 된 선조종 0093 aaa의 코드를 나타낸다.
format: 3 bits: 3
genotype: 0093aaa parent genotype: 0666god
track 0: prot
xwr
nop1 ; 010 000 00 0 beginning marker
nop1 ; 010 000 00 0 beginning marker
nop1 ; 010 000 00 0 beginning marker
nop1 ; 010 000 00 0 beginning marker
zero ; 010 000 00 0 to clear bx
enter ; 010 000 00 0 to clear bx
adrb ; 010 000 00 0 find start
nop0 ; 010 000 00 0 complement to beginning marker
nop0 ; 010 000 00 0 complement to beginning marker
nop0 ; 010 000 00 0 complement to beginning marker
nop0 ; 010 000 00 0 complement to beginning marker
exch ; 010 000 00 0 ax = templ size, bx = start addr after templ
sub ; 010 000 00 0 ax = start addr
zero ; 010 000 00 0 to clear bx
exch ; 010 000 00 0 to clear bx, ax = start, bx = 0
adrf ; 010 000 00 0 find end
nop0 ; 010 000 00 0 complement to end marker
nop0 ; 010 000 00 0 complement to end marker
nop0 ; 010 000 00 0 complement to end marker
nop1 ; 010 000 00 0 complement to end marker
inc ; 010 000 00 0 increment ax, to include dummy instruction at end
rollu ; 010 000 00 0 ax = start, bx = end
push ; 010 000 00 0 save start addr on stack
sub ; 010 000 00 0 ax = bx - ax, ax = size
pop ; 010 000 00 0 pop start addr from stack: ax = start, bx = size
nop1 ; 010 000 00 0 reproduction loop marker
nop1 ; 010 000 00 0 reproduction loop marker
nop0 ; 010 000 00 0 reproduction loop marker
nop1 ; 010 000 00 0 reproduction loop marker
mal ; 010 000 00 0 allocate daughter, ax = daughter, bx = mom, cx = size
call ; 010 000 00 0 call template below (copy procedure)
nop0 ; 010 000 00 0 copy procedure complement
nop0 ; 010 000 00 0 copy procedure complement
nop1 ; 010 000 00 0 copy procedure complement
nop1 ; 010 000 00 0 copy procedure complement, ax = mom, bx = size
rolld ; 010 000 00 0 put ax = mom, bx = size
zero ; 010 000 00 0 set offset of IP into daughter at 0
divide ; 010 000 00 0 create independent daughter cell
rolld ; 010 000 00 0 put ax = mom, bx = size
jmpb ; 010 000 00 0 jump back to template below (reproduction loop)
nop0 ; 010 000 00 0 reproduction loop complement
nop0 ; 010 000 00 0 reproduction loop complement
nop1 ; 010 000 00 0 reproduction loop complement
nop0 ; 010 000 00 0 reproduction loop complement
ifz ; 010 000 00 0 dummy instruction to separate templates
nop1 ; 010 000 00 0 copy procedure template
nop1 ; 010 000 00 0 copy procedure template
nop0 ; 010 000 00 0 copy procedure template
nop0 ; 010 000 00 0 copy procedure template
rolld ; 010 000 00 0 roll mom's start address to ax
push ; 010 000 00 0 push mom's start address on stack
rolld ; 010 000 00 0 roll mom's size to ax
push ; 010 000 00 0 push mom's size on stack
rollu ; 010 000 00 0 roll stack back up
rollu ; 010 000 00 0 roll stack back up
nop1 ; 010 000 00 0 copy loop template
nop0 ; 010 000 00 0 copy loop template
nop1 ; 010 000 00 0 copy loop template
nop0 ; 010 000 00 0 copy loop template
movii ; 010 000 00 0 move instruction from mother [bx] to daughter [ax]
rolld ; 010 000 00 0 roll size down to ax
rolld ; 010 000 00 0 roll size down to ax
dec ; 010 000 00 0 decrement size
ifz ; 010 000 00 0 test for end of loop (size = 0)
jmp ; 010 000 00 0 jump out of loop
nop0 ; 010 000 00 0 copy procedure exit complement
nop1 ; 010 000 00 0 copy procedure exit complement
nop0 ; 010 000 00 0 copy procedure exit complement
nop0 ; 010 000 00 0 copy procedure exit complement
rollu ; 010 000 00 0 roll mother's address into ax
inc ; 010 000 00 0 increment mother's address
rollu ; 010 000 00 0 roll daughter's address into ax
inc ; 010 000 00 0 increment daughter's address
jmpb ; 010 000 00 0 jump to top of copy loop
nop0 ; 010 000 00 0 copy loop complement
nop1 ; 010 000 00 0 copy loop complement
nop0 ; 010 000 00 0 copy loop complement
nop1 ; 010 000 00 0 copy loop complement
ifz ; 010 000 00 0 dummy instruction to separate templates
nop1 ; 010 000 00 0 copy procedure exit template
nop0 ; 010 000 00 0 copy procedure exit template
nop1 ; 010 000 00 0 copy procedure exit template
nop1 ; 010 000 00 0 copy procedure exit template
pop ; 010 000 00 0 pop size from stack into ax
pop ; 010 000 00 0 pop mom's address from stack into ax
pop ; 010 000 00 0 pop call's address from stack into ax
jmp ; 010 000 00 0 jump to instruction after call (return)
ifz ; 010 000 00 0 dummy instruction to separate templates
nop1 ; 010 000 00 0 end marker
nop1 ; 010 000 00 0 end marker
nop1 ; 010 000 00 0 end marker
nop0 ; 010 000 00 0 end marker
ifz ; 010 000 00 0 end marker
여기에서는 Kurt Thearling(당시 Thinking Machines사)와 Tom Ray가 행한, Tierra에 다세포 생물의 특징을 갖게 해 병렬 프로그래밍을 사용한 디지털 생물의 진화에 대한 연구에 대해 소개한다.
초기의 Tierra의 가상 생물들은 단세포 생물적인 특징 밖에 없었지만, 새롭게 다세포적인 성질을 덧붙이는 일로, "캄브리아 폭발"과 같은 진화의 다양성을 실현하려고 했다.
이 연구에서는, 다세포성은 이하와 같이 기능한다고 생각한다.
1) 생물은 단세포로부터 시작해, 세포 분열에 의해 다세포 생물이 된다.
2) 다세포 생물의 각각의 세포는 같은 게놈을 가진다.
3) 다세포 생물의 각각의 세포의 기능의 차이는, 각각의 세포가 같은 게놈의 다른 부분의 명령을 병렬로실행하는 일에 의해 실현된다.
실제의 유기 생명체에서는 세포 각각이 게놈을 갖고 있지만, Tierra에서는 메모리와 카피 프로세스에 필요로 하는 시간을 절약하기 위해서, 세포는 1개의 게놈을 공유하는 일로 했다. 즉 Tierra의 다세포 생물은 하나의 게놈과 그것을 공유하는 복수의 가상 CPU로부터 구성되어 있고 그것들에 CPU가 병렬로 명령을 실행한다.
다세포성 실현을 위해서 몇개의 새로운 명령 세트가 고안 되었다.
split 명령과 join 명령
split 명령이 실행되면, 그것을 실행한 생물에 대해서 하나 더의 새로운 가상 CPU가 준비된다. 레지스터, 스택, IP의 값은 원래의 CPU로부터 새로운 레지스터에 카피된다. 다만 DX레지스터의 값은 다르다. split 명령의 나머지 양쪽 모두의 CPU의 DX레지스터의 값은 1 비트 왼쪽으로 쉬프트 해, 새로운 쪽의 CPU에는 1이 더해진다. DX레지스터는 CPU를 구별하는 값(CPU 자기 주소)의 설정에 이용된다. 예로서 이하의 코드에 대해 설명한다.
split ; create 2 CPUs
split ; now split both CPU again, creating 4 CPUs
처음의 DX레지스터의 값이 0000이라고 하면, 최초의 split 명령에 의해 본래의 CPU의 DX레지스터의 값은 0000인 그대로이고, 새로 만들어진 DX레지스터의 값은 0001이 된다. 각각의 CPU가 2번째의 split 명령을 실행하면, 오리지날의 DX레지스터의 값은 0000인 그대로이고, 오리지날의 CPU로부터 2번째의 split 명령으로 만들어진 CPU의 DX는 0001, 1회째의 split 명령으로 만들어진 CPU의 DX는 1 비트 왼쪽으로 쉬프트 해 0010, 그 CPU가 행한 다음의 split 명령으로 만들어진 CPU의 DX는 0011이 되어, 모든 CPU에서 DX레지스터는 유니크한 값을 가진다.
join 명령은 이것을 실행한 CPU가 다른 CPU도 이 명령에 도착할 때까지, 아무것도 하지 말고 기다리라는 명령이다. 이 명령이 실행된 뒤, 오리지날의 CPU 이외는 모두 죽음으로 끝난다. 이것은 divide 명령을 정상적으로 실시하기 위해서 설치되었다. 복수의 CPU가 각각 게놈의 어떤 부분의 카피를 담당한다고 했을 때, 모든 게놈의 복제가 끝나고 나서 divide 명령을 실시하게 하기 위해서 사용한다.
zeroD 명령, shr 명령, offAACD 명령과 offBBCD 명령
split 명령은 DX레지스터를 빈번하게 사용한다. 그러나, 기존의 명령 세트에는 DX레지스터를 직접 조작할 수 있는 명령이 없었다. 그 때문에 새로이 zeroD 명령을 추가했다. zeroD 명령은 DX레지스터에 값 0을 세트한다. split 명령의 직전에 이 명령을 두는 것으로 DX레지스터의 값을 초기화할 수가 있다.
또 하나 shr 명령을 추가했다. 이 명령은 CX레지스터의 값을 1 비트 오른쪽으로 쉬프트 한다. CX레지스터에는 평상시 게놈의 사이즈가 들어간다. 이 명령을 실행하면, 사이즈의 2분의 1의 값을 얻을 수 있다. 이 값은 split 명령에 의해 2배가 된 CPU가 카피 루프를 실행할 때 반복 회수로서 이용할 수 있다.
각 CPU가 병렬적으로 각각 게놈의 카피처 주소를 효율적으로 계산할 수 있도록, "offset"용의 명령이 추가되었다. offAACD 명령은 CX레지스터의 값(카피해야 할 게놈 사이즈)에 DX레지스터의 값(CPU 자기 주소)을 실어 그것을 AX레지스터 (딸 셀의 처음 주소가 격납되고 있다)에 가세해, 카피처의 주소를 계산하는데 사용할 수 있다. offBBCD 명령은 같은 조작을 BX레지스터에 실시하는 일에 의해 카피원의 주소를 계산한다.
선조종
Kurt가 생각한 선조종 0082 aaa의 코드를 제시한다. 알고리즘은 명령 세트 1의 선조종과 거의 같다. 25행째의 split 명령전에 zeroD 명령이 2개 들어가 있지만, 이 중의 하나는 이 코드의 사이즈가 2의 배수가 되기 위한 더미이다. 2의 배수로 하는 일로 2개의 CPU가 꼭 반씩 코드를 카피할 수 있도록 했다.
0 nop1 ; beginning marker
1 nop1 ; beginning marker
2 nop1 ; beginning marker
3 nop1 ; beginning marker
4 adrb ; get (backward) address of beginning marker --> ax
5 nop0 ; complement to beginning marker
6 nop0 ; complement to beginning marker
7 nop0 ; complement to beginning marker
8 nop0 ; complement to beginning marker
9 subAAC ; subtract cx from ax, result in ax
10 movBA ; move ax to bx, bx now contains start address of mother
11 adrf ; get (forward) address of end marker --> ax
12 nop0 ; complement to end marker
13 nop0 ; complement to end marker
14 nop0 ; complement to end marker
15 nop1 ; complement to end marker
16 incA ; increment ax, to include dummy instruction at end
17 subCAB ; subtract bx from ax to get size, result in cx
18 nop1 ; reproduction loop marker
19 nop1 ; reproduction loop marker
20 nop0 ; reproduction loop marker
21 nop1 ; reproduction loop marker
22 mal ; allocate space (cx) for daughter, address to ax
23 zeroD ;
24 zeroD ;
25 split ;
26 call ; call template below (copy procedure)
27 nop0 ; copy procedure complement
28 nop0 ; copy procedure complement
29 nop1 ; copy procedure complement
30 nop1 ; copy procedure complement
31 join ;
32 divide ; create independent daughter cell
33 jmpo ; jump to template below (reproduction loop)
34 nop0 ; reproduction loop complement
35 nop0 ; reproduction loop complement
36 nop1 ; reproduction loop complement
37 nop0 ; reproduction loop complement
38 ifz ; dummy instruction to separate templates
39 nop1 ; copy procedure template
40 nop1 ; copy procedure template
41 nop0 ; copy procedure template
42 nop0 ; copy procedure template
43 pushA ; push ax onto stack
44 pushB ; push bx onto stack
45 pushC ; push cx onto stack
46 shr ;
47 offAACD ;
48 offBBCD ;
49 nop1 ; copy loop template
50 nop0 ; copy loop template
51 nop1 ; copy loop template
52 nop0 ; copy loop template
53 movii ; move contents of [bx] to [ax] (copy one instruction)
54 decC ; decrement cx (size)
55 ifz ; if cx == 0 perform next instruction, otherwise skip it
56 jmpo ; jump to template below (copy procedure exit)
57 nop0 ; copy procedure exit complement
58 nop1 ; copy procedure exit complement
59 nop0 ; copy procedure exit complement
60 nop0 ; copy procedure exit complement
61 incA ; increment ax (address in daughter to copy to)
62 incB ; increment bx (address in mother to copy from)
63 jmpb ; jump to template below (copy loop)
64 nop0 ; copy loop complement
65 nop1 ; copy loop complement
66 nop0 ; copy loop complement
67 nop1 ; copy loop complement
68 ifz ; this is a dummy instruction to separate templates
69 nop1 ; copy procedure exit template
70 nop0 ; copy procedure exit template
71 nop1 ; copy procedure exit template
72 nop1 ; copy procedure exit template
73 popC ; pop cx off stack (size)
74 popB ; pop bx off stack (start address of mother)
75 popA ; pop ax off stack (start address of daughter)
76 ret ; return from copy procedure
77 nop1 ; end template
78 nop1 ; end template
79 nop1 ; end template
80 nop0 ; end template
81 ifz ; line 81 - dummy instruction to separate creature
진화
이 병렬 CPU판의 Tierra를 실행하면 잠시 후에, 싱글 CPU판의 Tierra와 비슷하게 파라사이트가 출현하거나 템플릿 사이즈가 감소해 코드가 짧게 되어 가는 최적화등의 현상이 일어난다.
그런데 , 1개의 딸 셀을 복제하는데 필요로 하는 실행 회수를 종마다 달리 플롯 했다 그래프를 보면, 일정 명령 실행 회수(215밀리언 명령) 무렵에 급격한 효율의 상승이 보여졌다. 이것은 주된 생물이 split 명령의 실행을 늘려 단시간에 자기 복제를 할 수 있도록 진화한 일을 이야기하고 있다. 실제로 코드를 조사해 보면, 지금까지 스프를 지배하고 있던 종의 사이즈가 44였는데 대해, 새롭게 지배적이 된 종의 사이즈는 52로 증가하고 있었다. 그럼에도 불구하고, 복제 효율은 올라가 있었다. 이것은 증가한 코드 가운데 11 개의 코드가 의미의 없는 코드(인트론) 이고, split 명령을 하나 늘렸을 때 코드 사이즈가 4의 배수가 되도록 일부러 넣은 것이다. 그 후, 인트론은 조금씩 감소해, Tierra 실행 개시부터 1억 명령 후에는 사이즈는 40이 되었다. 이 게놈(0040aba)은 아래와 같다.
0 nop0 ; begining template
1 adrb ; find beginning + template size
2 nop1 ;
3 subAC ; subtract template size from beginning
4 movAV ; put begining in BX
5 adrf ; find end
6 nop0 ;
7 nop0 ;
8 subCAB ; calculate size
9 mal ; allocate space for daughter
10 incC ; intron (since CX no longer used)
11 split ; 2 CPUs
12 ifz ; intron (since CX [size + 1] couldn't be zero)
13 movCD ; intron (since previous ifz could never be true)
14 shr ; size = size / 2
15 offAACD; partition genome into two halves and adjust
16 offBBCD; AX and BX accordingly
17 zeroD ; zero out DX before second split
18 pushB ; save beginning on stack
19 shr ; size = size / 2
20 split ; 4 CPU
21 offAACD; re-partition genome into four quarters and
22 offBBCD; adjust AX and BX
23 nop1 ;
24 nop0 ;
25 movii ; copy instruction from mother to daughter
26 decC ; decrement number of instrucitons left to copy
27 ifz ; if number of instructions left to copy == 0
28 jmp ; jump forward to just before the join
29 nop0 ;
30 incA ; increment source address
31 incB ; increment destination address
32 jmpb ; jump back to beginning of copy loop
33 nop0 ;
34 nop1 ;
35 join ; join up multiple CPUs
36 divide ; divide the daughter
37 ret ; return back to beginning of creature and start over
38 nop1 ; ending template
39 nop1 ; ending template
이 코드를 보면 알수 있는 것은, 아직 인트론이 3개 남아 있다는 것이다. 이것들을 없애는 일은 할 수 없다. 왜냐하면 4 CPU의 코드는 4의 배수가 아니면 정확하게 딸 셀의 복제를 할 수 없기 때문이다.
여기서 설명한 다세포판 Tierra는 어느 정도의 성공은 하고 있다. 그러나 Tom Ray가 목표로 하고 있는 캄브리아 폭발이라고 하는 현상까지는 일어나지 않았다. Tom Ray는 디지털 생물의 다양성을 더하기 위해서는, 디지털 환경 그것을 복잡하게 해 주는 것이 필요하다고 생각하고 있다. 그리고 현재, Tierra를 인터넷에 접속해, 복잡한 토폴러지를 가진 네트워크 환경 하에서, 디지털 생명 의 진화를 일으키려 하고 있다.