Си компилятор для машины Тьюринга

[vak]

Собираем компилятор:

git checkout https://github.com/retrage/elvm.git
cd elvm
make tm

При сборке будет прогнана куча тестов, так что понадобятся три гигабайта места на диске. Результат окажется в каталоге out:

$ size out/8cc out/elc out/tm
   text	   data	    bss	    dec	    hex	filename
 150381	   3136	   5184	 158701	  26bed	out/8cc
 329064	  83328	  30696	 443088	  6c2d0	out/elc
   6687	    737	     56	   7480	   1d38	out/tm

Здесь 8сс преобразует исходник Си во внутреннее представление (ассемблер виртуальной машины). Затем elc генерит код для целевой архитектуры, в нашем случае для машины Тьюринга. Третий компонент tm это симулятор машины Тьюринга, он выполняет полученный код.

Компилируем и выполняем стандартный тест Hello World:

$ cat test/hello.c
#include <stdio.h>

int main() {
  const char* p = "Hello, world!\n";
  for (; *p; p++)
    putchar(*p);
  return 0;
}
$ out/8cc -S -Ilibc test/hello.c
$ out/elc -tm hello.s > hello.tm
$ out/tm -b -n -v hello.tm
running: steps=10000000 cells=34251
running: steps=20000000 cells=34251
...
running: steps=480000000 cells=34491
halt: accept=1 steps=482391152 cells=34491
Hello, world!

Программа выполняется за 482 миллиона шагов и занимает 34 тысячи ячеек ленты.

Формат кода машины Тьюринга описан в комментариях к симулятору: tm.c

Comments

[dijifi]

Хреново оптимизирует.

Или может это стандартная библиотека подвела?

Программа: 13 шагов
Crt0: 482391139 шагов

[vak]

Машина Тьюринга вообще не самая удачная архитектура с точки зрения производительности. Память без адресации, с последовательным доступом.

[spamsink]

Зато по размеру отлично оптимизирует. Я вижу

% gcc -o hello -O3 hello.c
% wc -c hello
8272 hello

Всего в 4 раза лучше, чем машина Тьюринга (и это не считая кода для stdio, которое в линуксе в динамической библиотеке).

[sab123]

Создается ощущение, что они выбрали какой-то ограниченный алфавит для машины Тьюринга вместо произвольного, подогнанного под программу.

[vak]

У машины Тьюринга размер "бинарника" 170 мегабайт.

$ wc -c hello.tm 
 170335212 hello.tm

[spamsink]

Ой. Ну по крайней мере "сегмент данных" не на столько же порядков больше. :)