Befunge (Язык и компилятор)

[frp]

Среди подобных языков может кто знает как программировать на Befunge? А то я прочитал статью в Википедии и не понял.

[RasenHerz]

чего уж, учите сразу Malbolge

[frp]

чего уж, учите сразу Malbolge

Не хочу.
1) Абсолютно нигде не описан
2) Чересчур сложен
А Befunge, Brainfuck, Whitespace интересно.

[NickLion]

Среди подобных языков может кто знает как программировать на Befunge? А то я прочитал статью в Википедии и не понял.

Там все понятно вроде, только есть неуточненные моменты (по работе со стеком). По сути у Вас есть матрица операций, премещение происходит по вертикали/горизонтали. Когда достигается край матрицы, идет зацикливание на противоположную сторону. Также имеется стек. И самые необходимые операции над ним.

PS может и самому придумать язык. Только чтобы матрица была как минимум 4х мерной

PPS такой уже есть: 4DL

PPPS Надо в этот язык еще многопоточность добавить. И квантовые вычисления в основу положить. Кубиты там всякие.

[frp]

PS может и самому придумать язык. Только чтобы матрица была как минимум 4х мерной biggrin.gif

Еще есть трехмерный - Trefunge, но на википедии нет описания, а интересно.
Еще интересно, что такое byter.
Есть прикольный язык Piet. Где найти толковую документацию?
А насчет Befunge понял. Где взять интерпретатор под Linux? Могу сам написать, но очень уж сильно лень - здесь инструкций намнооооооого больше, чем в brainfuck. Кстати это все ложь, что нельзя компилятор написать. Компилятор, который генерирует из befunge-кода нативный бинарный код, написать нельзя, но компилятор, который будет компилировать по принципу старого компилятора BASIC A, можно и я реализую меньше чем за 2 часа (встраивать код программы Befunge в бинарник вместе с некоторым подобием интерпретатора).
А знает кто-нибудь про язык WhiteSpace больше, чем википедия?

[NickLion]

Кстати это все ложь, что нельзя компилятор написать.

Если нет запрета на запись в сегмент кода (например ДОС), то проблем в компиляции вообще нет Но даже с запретом проблем для компиляции нет. В основу положим 2 матрицы - одна - неизменный код, каждая инструкция = call [соответствующая ячейка в матрице адресов], а в матрице адресов храним уже адреса подпрограмм, которые и выполняют нужное действие. Соответственно запись чтение производится над матрицей адресов.

[frp]

Если нет запрета на запись в сегмент кода (например ДОС), то проблем в компиляции вообще нет smile.gif Но даже с запретом проблем для компиляции нет. В основу положим 2 матрицы - одна - неизменный код, каждая инструкция = call [соответствующая ячейка в матрице адресов], а в матрице адресов храним уже адреса подпрограмм, которые и выполняют нужное действие. Соответственно запись чтение производится над матрицей адресов.

Это развитие моей идеи? Я еще предлагаю все эти функции на которые call в отдельный so выделить - программы меньше занимать будут (теоретически размер будет сопоставим с программами на ассемблере). Даже если не выделять, то голый бинарник, думаю, будет меньше, чем 1024 байта. Скиньте ссылки где найти статьи по программированию в nasm (я под Linux на ассемблере не программировал, но под ДОС делал многое). Попробую сие дело реализовать (сделаю две реализации - на MASM под ДОС и на NASM под Linux). Такое компилирование даже проще, чем интерпретирование.
Еще возник вопрос по brainfuck. Я когда только начинаю знакомство с языком то пишу на нем программу, которая считывает с клавиатуры два числа, делает сложение и печатает результат. Решил сделать такую навороченную додавалку на brainfuck. Столкнулся с проблемой - как подвинуть указатель на текущую ячейку на переменное число ячеек?

[NickLion]

Это развитие моей идеи? Я еще предлагаю все эти функции на которые call в отдельный so выделить - программы меньше занимать будут (теоретически размер будет сопоставим с программами на ассемблере). Даже если не выделять, то голый бинарник, думаю, будет меньше, чем 1024 байта. Скиньте ссылки где найти статьи по программированию в nasm (я под Linux на ассемблере не программировал, но под ДОС делал многое). Попробую сие дело реализовать (сделаю две реализации - на MASM под ДОС и на NASM под Linux). Такое компилирование даже проще, чем интерпретирование.
Еще возник вопрос по brainfuck. Я когда только начинаю знакомство с языком то пишу на нем программу, которая считывает с клавиатуры два числа, делает сложение и печатает результат. Решил сделать такую навороченную додавалку на brainfuck. Столкнулся с проблемой - как подвинуть указатель на текущую ячейку на переменное число ячеек?

Ну в каком-то плане и развитие, хотя я эту идею придумал, когда прочитал, что мол трудно написать компилер. Под NASM не кодил, не знаю, но сидел когда-то тут и там есть и компилятор, и статьи по насму. Передвигать можно только на следующую или предыдущую ячейку. Для передвижние на произвольное число ячеек надо исхитряться. Писал когда-то под машину Тьюринга и умножение. В непозиционной системе, в которой в алфавите только 1 и разделитель *, соответственно *1* - 0, *11* - 1, *111* - 2, и т.д. Прикольное занятие для мозгов.

PS кстати, не обязательно эту идею реализовывать на асме, можно строить код на C:

Код: Выделить всё

typedef void ( *cell_func_t ) ();
cell_func_t matrix[ 128 ][ 128 ];
int dir = 0;
int dirs[ 4 ][ 2 ] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int ipx, ipy;
while( 1 ) {
    matrix[ ipy ][ ipx ]();
    ipx += dirs[ dir ][ 0 ];
    ipy += dirs[ dir ][ 1 ];
}

Код написан здесь, поэтому может что-то упустил.

PPS только дошло, что матрица инструкций ведь не нужна. понял после того как код написал. надо выспаться %)

[frp]

Да, вы правильно написали. Теперь доделаю до толкового уровня. А вообще надо это выложить где нибудь кроме форума.

[frp]

Возникли неоднозначности:
1) Какого размера ячейки стека?
2) Могут ли числа в ячейках стека получать отрицательные значения?
3) В каком порядке в стеке находятся операнды для p(PUT) и g(GET)?

[NickLion]

Возникли неоднозначности:
1) Какого размера ячейки стека?
2) Могут ли числа в ячейках стека получать отрицательные значения?
3) В каком порядке в стеке находятся операнды для p(PUT) и g(GET)?

Неоднозначности еще будут. Относительно стека в вики вообще мало комментарией, так что надо искать официальное описание. Относительно ячеек и значений в них - думаю можно взять знаковые целые, 32 или 64 бита. Для начал хватит. В приницпе можно применить длинную арифметику, тогда - вообще любое значение. Лишь бы памяти хватило.

PS я в том коде забыл про зацикливание, не забудьте этот момент

PPS а вот и официальная спецификация

[frp]

Нашел:
1) Знаковый 32-бит (это в C int)
2) Да
3) Для get сначала pop y, потом pop x, для put - pop y, pop x, pop i (где i - инструкция).
Еще некоторые неясные моменты выяснил.
Компилятор получится jit (некоторые моменты как ни крути придется компилировать во время выполнения. Уже написал 119 строк кода и почти доделал.

[frp]

Я создал первую бета-версию компилятора Befunge . Он состоит из двух фалов: befunge_comp.cpp и befunge_jit.cpp.
Сам компилятор в файле befunge_comp.cpp. Он превращает программу на Befunge в двумерный массив, который содержит ASCII-коды символов и пишет результат в файл befunge_code.h.
Потом он компилирует файл befunge_jit.cpp. В результате получается бинарник программы.
Файл befunge_jit.cpp уже во время выполнения заменяет в таблице Befunge - код на адреса соответствующих функций и выполняет код.
Багрепорты писать сюда.
Пока возникла одна проблема - в функции befunge_rnd() в файле befunge_jit.cpp функция random() генерирует числа всегда одинаковые. Как это исправить?

[NickLion]

1. Может тогда уже вынести в отдельную тему в проектах форума?
2. Замечания по коду:
1)

Код: Выделить всё

cell_func_t matrix[ 128 ][ 128 ];

здесь лучше сделать

Код: Выделить всё

cell_func_t matrix[ MATRIX_HEIGHT ][ MATRIX_WIDTH ];

а константы определять в befunge_code.h
2) соответственно эти константы перенести в befunge_comp/jit.cpp вместо 128
3)

Код: Выделить всё

cell_func_t compile(int d)
{
    unsigned char c=d;
    switch(c)
    {
        case '>':return befunge_r;break;
.....................
        case '?':return befunge_rnd;break;
    }
    if((c>='0')&&(c<='9'))return befunge_postnum;
    return befunge_nop;
}

для ускорения работы этой функции (выполняется ведь не один раз) можно завести массивчик, в котором индекс - это символ, а значение - функция, тогда сама ф-ция превратится в:

Код: Выделить всё

cell_func_t compile(int d)
{
    unsigned char c=d;
    if( c > 127 ) return befunge_nop;
    return char2func[ c ];
}

4)

Код: Выделить всё

        ipx += dirs[ dir ][ 0 ];
        ipy += dirs[ dir ][ 1 ];

заменить на

Код: Выделить всё

        ipx += dirs[ dir ][ 0 ] % MATRIX_WIDTH;
        ipy += dirs[ dir ][ 1 ] % MATRIX_HEIGHT;

5) <iostream> работает медленнее, чем <stdio.h>, может стоит все же использовать эти функции? Да и привязка к C++ тут ни к чему.
6) Может стоит проконтролировать обвал стека?
Вроде все, что на первій взгляд.

[frp]

Спасибо. От C++ вряд ли стоит отказаться - в С очень неудобно ошибки обрабатывать.
А от использования iostream - не проблема.
Еще возникло одно неудобство с константами MATRIX_HEIGHT и MATRIX_WIDTH.
Программа ведь может использовать ячейки, которых в файле-исходнике просто нет. Где тогда брать значения констант? Или сделать параметры в командной строке?
Модератор, перенесите часть темы, которая касается компилятора Befunge, в проекты форума.

[frp]

Сделал перечисленные вами оптимизации. Также обнаружил и исправил целую кучу ошибок. От C++ в файле befunge_jit.c отказался полностью.

[frp]

Возникла проблема. random() генерирует числа всегда в одной и той же последовательности. Из-за этого выполнение программы с инструкцией ? не является непредсказуемым. Как исправить?
В borland c++ для этого была функция randomize(). В gсс такой функции нет.
Насколько правильно будет читать /dev/urandom?
Модератор, перенесите все посты о компиляторе Befunge в отдельную тему.

[NickLion]

Чтобы rand() выдавала разные значения при каждом запуске надо вызвать:

Код: Выделить всё

#include <stdlib.h>
#include <time.h>
time_t t;
srand( time( &t ) );

[frp]

Исправил. Также нашел одну серьёзную ошибку в befunge_jit.c, из-за которой программа могла не компилироваться. Исправил, теперь все работает.
Формат вызова компилятора теперь немного другой:

Код: Выделить всё

befunge_comp <исходник> <бинарник> <ширина_матрицы> <высота_матрицы>