Как стать автором
Обновить

Комментарии 37

Just another week of Brainfuck! :)
Похоже неделя незаметно перерастает в месяц :)
Потрясающе! Жду ОС на brainfuck
Все чудесатее и чудесатее :)
Но по моему пусть лучше будет больше статей про jit, компиляцию, интепретацию, чем про обзоры телефонов и ненавись к вконтакте.
такими шагами дойдем до того что таки напишут брейнфак на брейнфаке…
В каждом топике про бф это говорят…
Закономерность и постоянность.

А вообще мне даже нравится идея… Может стоит проводить собеседования так? Написать транслятор для брейнфака, сразу видно насколько человек «легкообучаем» и насоклько глубоко он знает технологию + качество кода можно увидеть.
В качестве первой программы в книге по ЯП в самый раз.
Я в одном из топиков уже писал — в трансляторе брейнфака в качестве первой программы смысла намного больше, чем в hello world. И увлекательно, и головой подумать заставляет, и довольно большой набор синтаксических возможностей языка используется — есть пример, на чём разобрать. И даже немного алгоритмики.
Если бы мне первым под нос попался Hello World — ещё вопрос, был бы я сейчас программистом. (а первой была простенькая 3D-игрушка на Dark Basic)
Последнее время, статьи про брейнфак меня уже порядком зафакали.
Но, вот эта статья — это реально круто ;)
Пожалуй, самая интересная статья недели :) Спасибо!
Возможно, я неправ, но это разве JIT? Получился типичный компилятор. Да, результат его работы нельзя запустить напрямую, но это специфика операционки — кроме того, никто не мешает подцепить заголовок, представляющий из себя пролог с кодом, выделяющим память и предоставляющим API.

По идее, JIT нужен в интерпретируемых языках, где статическая компиляция технически невозможна или очень неэффективна (пример: V8 при выполнении следит за тем, к каким полям в JavaScript-объекте идет обращение, и если объект по сути представляет из себя структуру, т.е. фиксированный набор полей, то и генерирует код, который обращается к определенной структуре данных в памяти по жестко вписанным в этот код offset-ам. Сделать такое статически, очевидно, нельзя.)
В топике AOT (Ahead Of Time) компиляция, а не JIT.

И еще, сгенереный код как-нибудь исполняется или просто складывается в файл?
Возможно вы правы, это не JIT в своем классическом понимании. Сгенерированный код конечно выполняется, на него в итоге передается управление, потомм происходит выход из него как из обычной подпрограммы с помощью команды RET. Есть так-же опция (-b), которая позволяет скинуть сгенерированный код в бинарный файл. Его можно посмотреть в HIEW например.
Статья интересная, но оптимизации как таковой нет.
Конечно для маленького кода Brainfuck это не критично (разница не сильно заметна будет), но если уж извращаться, то бОльшую часть кода придётся переписать на асме. У паскаля беда с массивами и операторами присваивания, ресурсы кушает вёдрами при работе в больших циклах.
Вы внимательно статью прочитали? Программа генерирует машинный код а потом его исполняет. При чем тут эффективность работы Паскаля?

Кстати эта ваша «беда» отключается в опциях компилятора паскаля еще начиная с Turbo Pascal. Просто нужно отключить проверку на попадание в границы массива.
При том, что получаемый компилятор не будет оптимизированным. И это не эффективность работы паскаля, а эффективность работы получаемого кода. Я не придираюсь к коду, я придираюсь к слову «оптимизированный». Может мы разные вещи под одним словом понимаем, я лично имею ввиду что этот код может работать раз в 10 быстрее, а следовательно оптимизации в нём как таковой никакой.
Проверка границ массива — самое безобидное из того, что будет в исполняемом файле компилятора. Скачайте Олли и убедитесь.
Если под словом «оптимизированный» Вы имели ввиду отложенное исполнение «брейнфаковских» команд — то это никак не оптимизация.
И да, это не интерпретатор, это — компилятор.
Интерпретатор — Вид транслятора, осуществляющего пооператорную (покомандную) обработку и выполнение исходной программы.
Я не согласен. Никаких таких особенностей работы с массивами или тем более присваиванием никогда в паскале не было, и тем более нет сейчас. Эффективность получаемого кода во много зависит от используемого компилятора (коих для паскаля имеется чуть более чем 9000). Ровно так же, как и получаемого кода, скажем для Си. Вы конечно знаете, что в паскале можно обращаться к массивам не только по индексу, но и по указателю? Ровно так же, как и в Си.
Olly качать не стал, а в Hiew глянул:
      ExBuf[ptr] := 123;

компилиться в

movzx     eax,w,[000454770]
mov       b,[eax][00040476F],07B

Что есть имхо вполне приемлемо.
Присваивание:
      ptr := 12;

Компилиться в:
mov       w,[000454770],0000C

Ну и что здесь криминального?
Ооо дааа…
Посидите, подумайте почему код получился таким компактным…
Я намекну: константы. А Вы уж поразмышляйте, почему с ними никаких проблем. Правда, посидите, подумайте. И что компилятору приходится проверять при элементарных арифметических операциях, чтобы программа не вывалилась с ошибкой.
И если бы хоть один язык высокого уровня не имел таких грешков — ассемблер давно уже был бы не нужен.

P.S.: Умельцам тыкать в кнопку минус спасибо. На большее-то они не способны, судя по отсутствию комментариев.
Давайте сюда код. Без констант который. Будем обсуждать. Без него — расцениваю просто как тролинг.
Ребят, вам уже нужно организовать НИИ какой-нибудь.
НИИБФ
НИИЕМ
Одна из лучших статей о БФ за последнее время. Хоть и неделя БФ закончилась в воскресенье.
Не видел реализацию на ЛИСПе!

Тут есть такие спецы?
НЛО прилетело и опубликовало эту надпись здесь
по статьям хабра за последние 10 дней можно издать книжку «100 компиляторов брэйнфака»
Может, хватит уже о брейнфаке?
Я просто оставлю это здесь:

yuriy.nasretdinov$ time sh compile-run.sh 
?
real	0m0.922s
user	0m0.853s
sys	0m0.041s


test.bf:
>+>+>+>+>++<[>[<+++>-
 >>>>>
 >+>+>+>+>++<[>[<+++>-
   >>>>>
   >+>+>+>+>++<[>[<+++>-
     >>>>>
     >+>+>+>+>++<[>[<+++>-
       >>>>>
       +++[->+++++<]>[-]<
       <<<<<
     ]<<]>[-]
     <<<<<
   ]<<]>[-]
   <<<<<
 ]<<]>[-]
 <<<<<
]<<]>.


compile-run.sh:
gcc -o bfc bfc.c && ./bfc test.bf test && ./test


bfc.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

int main(int argc, char *argv[])
{
	if(argc == 1)
	{
		printf("Usage: %s input_file [out_file]\n", argv[0]);
		return -1;
	}
	
	char *inp_file = argv[1], *out_file = "a.out.c";
	
	if(argc >= 3)
	{
		out_file = (char*)malloc(strlen(argv[2]) + 3);
		strcpy(out_file, argv[2]);
		strcat(out_file, ".c");
	}
	
	FILE *fp = NULL;
	if(!strcmp(inp_file,"-")) fp = stdin;
	else fp = fopen(inp_file, "rb");
	
	if(!fp)
	{
		perror("Could not open input file");
		return -2;
	}
	
	FILE *out_fp = fopen(out_file, "wb");
	if(!out_fp)
	{
		perror("Could not create/open output file");
		return -3;
	}
	
	const char *write_str = "";
	
	#define HEAD "#include <stdio.h>\n#include <stdlib.h>\nint main(void) { int *p = (int*)malloc(100000*sizeof(int)); "
	#define FOOT "}"
	fwrite(HEAD, sizeof(HEAD)-1, 1, out_fp);
	
	while(!feof(fp))
	{
		switch(fgetc(fp))
		{
			case '>': write_str = "++p;"; break;
			case '<': write_str = "--p;"; break;
			case '+': write_str = "++(*p);"; break;
			case '-': write_str = "--(*p);"; break;
			case '.': write_str = "putchar(*p);"; break;
			case ',': write_str = "*p = getchar();"; break;
			case '[': write_str = "while (*p) {"; break;
			case ']': write_str = "}"; break;
			default:  write_str = ""; break;
		}
		
		fwrite(write_str, strlen(write_str), 1, out_fp);
		fputc('\n', out_fp);
	}
	
	fwrite(FOOT, sizeof(FOOT)-1, 1, out_fp);
	fclose(out_fp);
	
	char *real_out_file = strdup(out_file);
	real_out_file[ strlen(real_out_file) - 2 ] = 0; // cut last .c
	
	char *const cc_argv[] = { "cc", "-O3" ,"-o", real_out_file, out_file, NULL };
	
	int pid = fork();
	
	if(pid == 0)
	{
		execvp("cc", cc_argv);
	}
	
	int status = 0;
	wait(&status);
	
	unlink(out_file);
	
	if(status == 0)
	{
		
	}else
	{
		printf("Compile failed\n");
		return -4;
	}
	
	return 0;
	
}


Это тупо транслятор-компилятор BF-C с оптимизацией -O3 (в конце), которую можно убрать, если хотеть полной кроссплатформенности. Ах да, *nix-only из-за вызова компилятора, но это тоже можно обойти, если хочется.
Предлагаю небольшой тест: берите написанный вами интерпретатор, и запускайте вот этот не хитрый код
Для интереса запустил на моём оптимизирующем трансляторе в PHP. 5,5 минут.

Долго, но PHP не слишком скоростной язык :)

Получился вот такой код (простите, что сильно длинный):
$in=array(103, 114, 102, 103, $id = 0);
$d = array_fill(-65535, 65535, $di = 0);
++$di;
$d[$di++]++;
$d[$di++]++;
$d[$di++]++;
$d[$di]++;
$d[$di+1]+=2;
while ($d[$di])
{
    ++$di;
    while ($d[$di])
    {
        $d[$di-1]+=3;
        $d[$di]--;
        $di+=6;
        $d[$di++]++;
        $d[$di++]++;
        $d[$di++]++;
        $d[$di]++;
        $d[$di+1]+=2;
        while ($d[$di])
        {
            ++$di;
            while ($d[$di])
            {
                $d[$di-1]+=3;
                $d[$di]--;
                $di+=6;
                $d[$di++]++;
                $d[$di++]++;
                $d[$di++]++;
                $d[$di]++;
                $d[$di+1]+=2;
                while ($d[$di])
                {
                    ++$di;
                    while ($d[$di])
                    {
                        $d[$di-1]+=3;
                        $d[$di]--;
                        $di+=6;
                        $d[$di++]++;
                        $d[$di++]++;
                        $d[$di++]++;
                        $d[$di]++;
                        $d[$di+1]+=2;
                        while ($d[$di])
                        {
                            ++$di;
                            while ($d[$di])
                            {
                                $d[$di-1]+=3;
                                $d[$di]--;
                                $d[$di+=5]+=3;
                                $d[$di+1]+=$d[$di]*5;
                                $d[$di]=0;
                                $d[++$di]=0;
                                $di-=6;
                            }
                            $di-=2;
                        }
                        $d[++$di]=0;
                        $di-=5;
                    }
                    $di-=2;
                }
                $d[++$di]=0;
                $di-=5;
            }
            $di-=2;
        }
        $d[++$di]=0;
        $di-=5;
    }
    $di-=2;
}
++$di;
flush(print chr($d[$di]));
Оптимизация моего mercury-варианта (случаи [+], [-], +++++, ------) дает почти двухкратное ускорение (4m 40s -> 2m 30s), однако все-равно гораздо медленнее =(

www.progz.ru/t140549/#post1011206214
В моем простом интерпретаторе (без конвертации в машинные коды x86), с вышеописанной оптимизацией ([+], [-], ++++++, — , >>>>>> и тд) выполняется данный код за ~68 секунд. Интерпретатор тот тоже на паскале, если вдруг интересно — можно взглянуть тут: tronix286.pochta.ru/brainfk/index.htm
Но это все я думаю закономерно, так как паскаль — это компилируемый язык, а mercury — я честно так до конца и не понимаю, какой. Вроде как тоже компилируемый. Но для меня он пока очень необычен, не разбирался пока.
Компилируемый тоже ) Ну если углубиться в детали, то он сперва компилируется в си а потом с пом. gcc в исполняемый код.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.