Чем отличается компилятор от интерпретатора?

ну и покажи мне эту твою лисп-машину.

http://upload.wikimedia.org/wikipedia/commons/1/16/LISP_machine.jpg

откуда у тебя требование эквивалентности?

Из определения трансляции. Если есть программа Х на языке ХХ, то результат трансляции - программа Y на языке YY, котора эквивалентна Х с точки зрения семантики. Иначе это не трансляция, а хуета.

Так как для виснущей программы думаю найдутся уловки доказать, что это вырожденный случай.

Нет, это невырожденный случай, потому как нам известно множество примеров полезных виснущих программ. Эвентлупы, сервера и т.п.. - они работают и никогда не вырубаются (потенциально) и соответствующий им по такой схеме код - бесконечный.

входные данные однозначно заданы.

Конечно неоднозначно. Программы, в которых данные однозначно заданы, никому не нужны. Потому что можно просто вместо этой программы подставить сразу результат ее выполнения.

машинный код тоже может быть актуально бесконечный по числу команд и времени.

Нет, машинный код всегда конечен. Любая программа - это конечная последовательность термов. Машинный код - тоже программа, просто на языке процессора. Трансляция - это функция, которая берет конечный терм на одном языке и возвращает конечный терм на другом языке (который семантически эквивалентен исходному терму).

Достаточно одной команды JMP, которая безусловно переходит сама на себя. Где ты увидел «конец»?

Тут и увидел. В это случае - программа состоит всего из одной единственной команды, собственно, джампа.

а мой калькулятор умеет скобки в которых может быть всё что угодно.

Причем твой калькулятор со скобками?

то, что ты говоришь «команд процессора нет и сделать их невозможно из интерпретируемого кода».

Команды процессора есть. Нету _конечной последовательности команд_, которую можно было бы считать переводом. Потому как бесконечная последовательность команд - текстом не является. И потому переводом быть не может.

Уже вспоминали на первой странице — http://en.wikipedia.org/wiki/Partial_evaluation

При чем тут частичные вычисления? У нас есть программа, ее нельзя оттранслировать, но можно интерпретировать. Все. Ч. Т. Д. Одной такой программы для одного какого-нибудь ЯП (пусть даже выдуманного специально для доказательства нашего тезиса) достаточно, чтобы утверждать, что интерпретатор, в общем случае, не является транслятором.

Опять же тут больше вопрос логики, ибо

бесконечный код != циклический (зацикленный) код

Опять же либо не все столь однозначно. Либо пруфы кода, который есть бесконечный, но не есть цикличный :)

Type 'op' could not be resolved	main.c	/eval_func	line 11	Semantic Error

:D

С какими ключами компилировать?

Опять же либо не все столь однозначно. Либо пруфы кода, который есть бесконечный, но не есть цикличный :)

Не понял. Еще раз - контрол-флоу любой виснущей программы (в частности эвент-лупы, серверы, етц.) бесконечен. При чем тут зацикленность?

Либо пруфы кода, который есть бесконечный, но не есть цикличный :)

for (i = 0; i; i++){
    eval("print(" + intToStr(i) + ");")
}

бесконечный, нецикличный.

нецикличный.

4.2

Но for ведь тоже цикл с параметром ;)

А код без ветвлений, чисто линейный, по здравому размышлению, бесконечным быть не может.

Так что пока не убедили.

Или покажите ошибку в моих суждениях, такая критика всегда интересна :)

что с ним делать?

откуда я знаю? Конечно запостить на ЛОР. Что же ещё?

Или любой реальный интерпретатор или компилятор

facepalm. Давай с твоим выше разберёмся. Или слил?

4.2

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

(let loop ([i 0])
    (eval `(begin (define (yoba) (print ,i))
                  (yoba)))
    (loop (add1 i)))

push 1
call print
push 2
call print
push 3
call print
...

Но for ведь тоже цикл с параметром ;)

Да, но разница в том что если мы залогируем выполняемые команды, то в случае

for (i = 0; i; i++){
    print(i);
}

push i
call print
push i
call print
...

А код без ветвлений, чисто линейный, по здравому размышлению, бесконечным быть не может.

может. На бесконечной ленте машины Тьюринга. На конечной ленте с n битами возможно ровно 2ⁿ состояний, после которых будет повтор прошлой комбинации(или раньше). Уже обсудили.

мы получим последовательность

нет. Мы получим цикл. Только на ассемблере. В ассемблере x86 есть команда jnz, которая переходит если не ноль. Тебе этого мало? Почему ты тело цикла переводишь в код, а сам цикл for(;;) не переводишь, и куда он у тебя исчез? Опять магия?

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

теперь докажи и покажи мне эту свою «портянку» из одних и тех же команд, и покажи, куда делся цикл?

Я тебе не верю, а дебажить твой говнокод на лиспе мне лень.

Я имел ввиду на практике, а не в абстракциях.

Или просветите, как видите, я в этом деле дилетант, но с запалом :)

на практике анонимус принимает желаемое за действительное, и показывает только те команды, которые понимает (почему-то push+printf без pop). С такой ерундой через микросекунду будет переполнение стека и сегфолт.

А в теории это обычное дело для наших борщеедов-скобочников, любящих заниматься теоретическими размышлениями. Лисперы они вообще живут в другой реальности. Как и их гипотетический код. Которого в этой реальности нет.

По поводу jnz весьма верное замечание :)

Тем не менее, дискуссия получилась познавательной.

Лично для меня, мозг тоже иногда тренировать нужно :)

да, у меня где-то валялся интерпретатор/компилятор для brainfuck'а. Это очень простой ЯП, и если ты попробуешь сделать его компилятор/интерпретатор, то ты поймёшь, что тут на самом деле всё просто. Там всего 8 команд: см. http://ru.wikipedia.org/wiki/Brainfuck

Т.ч. компилятор/интерпретатор будет очень простым. Что бы ещё упростить задачу, можно компилировать не в машкод, а в C код, который затем прогонять оптимизирующим компилятором типа gcc.

Данный ЯП обладает Тьюрринг-полнотой, а следовательно на нём можно переписать _любую_ задачу с _любого_ ЯП. Это доказано.

откуда я знаю? Конечно запостить на ЛОР. Что же ещё?

Это интерпретатор типизированного лямбда-исчисления с числами и их арифметикой.

ТЫ рассказываешь как его превратить в компилятор из лямбда-термов в ассемблер x86_64 (если это «формально одно и то же» — этот интерпретатор на x86_64 запускается и работает, я проверил :)).

facepalm.

Ничего не фейсплалм. Бери любой интерпретатор байткода и любой компилятор и смотри какие там техники реализаций ([1], [2], [3], bytecode translation, bytecode execution, virtual machines & runtime, JIT, tracing JIT).

ТЫ объясняешь как они «формально одно и то же».

Давай с твоим выше разберёмся.

Так разобрались же уже — вот тебе и сказать нечего.

Компилятором будет

// gcc format

namespace x86_64 {

    // register allocation :)

    const char r1[] = "%eax";

    // instruction selection

    void gen_label(size_t i) {
        printf(".L%zu:\n", i);
    }

    void gen_ret() {
        printf("\tret\n");
    }

    void gen_pls() {
        printf("\tadd\t$1, %s\n", r1);
    }

    void gen_dbl() {
        printf("\tadd\t%s, %s\n", r1, r1);
    }

    void gen_jmp(size_t i) {
        printf("\tjmp\t.L%zu\n", i);
    }

    // wrapper

    void gen_main() {
        printf("\t.globl main\n");
        printf("main:\n");
        printf("\txor %s,%s\n", r1, r1);
    }

}

void compile(const Op code[], size_t len) {

    for (size_t i = 0; i < len; ++i) {
        x86_64::gen_label(i);
        switch (code[i]) {
        case HLT: x86_64::gen_ret(); break;
        case PLS: x86_64::gen_pls(); break;
        case DBL: x86_64::gen_dbl(); break;
        default : x86_64::gen_jmp(label(code[i])); break;
        }
    }

}

int main() {

    const Op code[] = { PLS, DBL, JMP(5), DBL, HLT, PLS, DBL, JMP(3) };

    x86_64::gen_main();
    compile(code, sizeof(code) / sizeof(Op));

}

compile вместо

Reg run(const Op code[]) {

    for (Reg i = 0, reg = 0;;)
        switch (code[i]) {
        case HLT: return reg;
        case PLS: ++reg; ++i; break;
        case DBL: reg *= 2; ++i; break;
        default : i = label(code[i]); break;
        }

}

Компилятор и интерпретатор тупейшего языка оба AST-driven — ну офигеть «формально одно и то же».

Рассказывай.

g++ / clang++ -std=c++11

У нас есть программа, ее нельзя оттранслировать, но можно интерпретировать

Вот там и превращают I_static * I_dynamic -> O в I_dynamic -> O предвычислением I_static, но это последнее I_dynamic -> O всегда остаётся и не устраняется, это то что ты говоришь — интерпретация всегда возможна, а трансляция только частично — всё равно останется кусок на интерпретацию.

на практике

да, у меня где-то валялся интерпретатор/компилятор для brainfuck'а.

Офигеть ты практик :)

case PLS: ++reg; ++i; break;

тут ты тоже пиши

case PLS: exec_pls_in_c(&reg, &i); break;

…


void exec_pls_in_c(int *arg, int *i)
{
    int *arg;
    int *i;
}

а то ты для «компилятора» почему-то выписываешь функции, а для «интерпретатора» — нет.

Почему?

Офигеть ты практик

за то это _полный_ компилятор/интерпретатор, а не просто составление AST. Потому ты и путаешься в примитивных вещах, т.к. у тебя нет опыта перевода AST на уровень железа. Даже для brainfuck'а.

Почему ты тело цикла переводишь в код, а сам цикл for(;;) не переводишь, и куда он у тебя исчез? Опять магия?

Потому что цикла не получается. Код нециклический. Нельзя эту последовательность свернуть в циклический машкод.

теперь докажи и покажи мне эту свою «портянку» из одних и тех же команд, и покажи, куда делся цикл?

Он никуда не девался, его там не было. На каждой итерации объявляется новая функция, компилируется джит-компилятором и генерируется новый машкод, отличный от машкода других итераций. Потом этот новый машкод выполняется.

Я тебе не верю

Отличный аргумент!

на практике анонимус принимает желаемое за действительное, и показывает только те команды, которые понимает (почему-то push+printf без pop).

Я опустил несущественные команды. pop в самом printf. От того что ты добавишь туда еще каких-то команд код все равно не станет циклическим, он нециклический из-за констант. Пока ты не уберешь константы - он не может быть приведен к циклическому виду.

Как и их гипотетический код. Которого в этой реальности нет

Я тебе привел конкретный код, который есть в реальности, который можно выполнить и который работает вполне конкретным образом. Но ты же в домике.

Тебе разжёвывать нужно?

using Reg = ...; // (1)
using Address = Reg; // (1)

void exec_pls(Reg&); // (1)
void exec_dbl(Reg&); // (1)
void exec_inc(Reg&); // (1) (6)
void exec_jmp(Reg&, Address); // (1)

#define EXEC_HALT(R) return R // (2)

Reg run(const Op code[]) { // (3)
    for (Reg i = 0, r1 = 0;;) { // (4)
        switch (fetch(i, code)) { // (5)
        case HLT: EXEC_HALT(r1); // (2) (6)
        case PLS: exec_pls(r1); exec_inc(i); break; // (6)
        case DBL: exec_dbl(r1); exec_inc(i); break; // (6)
        default : exec_jmp(i, label(fetch(i, code))); break; // (6)
        }
    }
}

using RegName = ...; // (1)
using Label = ...; // (1)

void gen_ret(RegName); // (1) (2)
void gen_pls(RegName); // (1)
void gen_dbl(RegName); // (1)

void gen_label(Label); // (1)
void gen_jmp(Label); // (1)

void compile(const Op code[], size_t len) { // (3)
    RegName r1 = get_reg(); // (1)
    for (Label i = 0; i < len; ++i) { // (4)
        gen_label(i); // (6)
        switch (fetch(i, code)) { // (5)
        case HLT: gen_ret(r1); break; // (2) (6)
        case PLS: gen_pls(r1); break; // (6)
        case DBL: gen_dbl(r1); break; // (6)
        default : gen_jmp(label(fetch(i, code))); break; // (6)
        }
    }
}

Внимательно смотрим на различие в типах, сигнатурах, коде и назначении.

(1) — интерпретатор по мере исполнения своей программы работает с состоянием своей машины (регистры, адреса, эффекты исполнения), транслятор занимается синтаксическим переводом своей программы (имена, метки, генерация инструкций).

(2) — интерпретатору HLT это остановка, транслятору — нет, просто очередной кусок терма для перевода.

(3) — если выполнение интерпретатором закончится, то останется конечное состояние машины, трансляция всегда закончится, результатом будет выхлоп в виде перевода исходной программы.

(4) — обход программы интерпретатором начинается с исходного состояния машины и продолжается сколько угодно долго, это её выполнение, в т.ч. с зависаниями, у транслятора — один проход по программе за конечное время, это перевод, он начинается с одной программы и даёт в итоге другую.

(5) — даром что оба AST-driven, потому что примитивнейшие.

(6) — сами по себе действия разные.

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

И про реальные(tm) интерпретаторы с компиляторами тоже ничего не рассказываешь :(

Неверное. jnz ничем не поможет, т.к. на каждой итерации надо перескакивать на _новый_ кусок машкода. И эти новые куски генерятся до бесконечности. Никакого конечного цикла, если эти куски склеить, не получится. На самом деле, там в коде есть три куска, первый и третий постоянны, а второй - генерится на каждой итерации, замещая предыдущий. То есть:

1. прыгнули на начало цикла, сгенерили машкод

2. прыгнули на сгенеренный машкод, вывели число, прыгнули на конец цикла

3. инкремент i, проверка на выход, прыжок на начало цикла

компилятор/интерпретатор

2 в 1?

Писать «компилятор/интерпретатор» с намёком на то что это одно и то же есть смысл только если ты хочешь чтобы тебя приняли за идиота или человека который не знает значения используемых слов.

Потому ты и путаешься в примитивных вещах, т.к. у тебя нет опыта перевода AST на уровень железа. Даже для brainfuck'а.

Ты путаешься в примитивных вещах, т.к. у тебя нет опыта разработки хоть сколько-нибудь сложного транслятора (brainfuck'и не считаются, а то может ты там напился, вот у тебя «компилятор/интерпретатор» и вышел).

Почему «Ы»?

Почему сгенерили? Или мы уже перешли на рассмотрение JIT-компиляции, вместо классической?!

Почему сгенерили?

Потому что так racket работает.

Или мы уже перешли на рассмотрение JIT-компиляции, вместо классической?!

Можно и без jit. Можно либо не генерить машкод вовсе (и интерпретировать то что внутри евала), либо как будет в cl - генерить машкод ф-и сразу при ее объявлении (а не при вызове). Но один хрен на каждой итерации будет создан новый, отличный от других кусок машкода. И «классическая компиляция» тут просто невозможна. Нету кода, который можно получить до запуска программы. Он генерится во время работы программы (такова семантика программы) и потому бесконечен (т.к. программа его бесконечно генерит и выполняет и генерит...). Это как раз то, что получается, когда мы пытаемся компилировать интерпретируемый по дизайну язык.

Это как раз то, что получается, когда мы пытаемся компилировать интерпретируемый по дизайну язык.

То есть либо мы такое дело интерпретируем (и никакого машкода нету вовсе), либо мы можем компилировать «кусками», но тогда получается бесконечный машкод. Скомпилировать в конечный машкод же мы не в состоянии. По-этому трансляции не происходит. Нету конечного машкода, который был бы семантически эквивалентен исходной программе.

Плюс к тому код ведь может не генерироваться, а вызываться из библиотечной функции.

Или нет?

Плюс к тому код ведь может не генерироваться, а вызываться из библиотечной функции.

Так он бесконечный. Он не влезет ни в какую библиотеку.

(и никакого машкода нету вовсе)

Ну это уже перебор, скажем так статичного машкода. А в противном случае, как бы оно выполнялось на ЦП. Сферический конь?! :D

Ну это уже перебор, скажем так статичного машкода.

Когда мы интерпретируем, то есть машкод интерпретатора, но нету машкода выполняемой программы.

Можно не интерпретировать а компилировать «кусками», тогда получается бесконечный машкод исполняемой программы. А конечного не выходит.

Но действие то, одно и тоже - вывод символа.

Причем здесь бесконечность? Меняется ведь только аргумент функции.

В любом случае, благодарю за интересную беседу. Узнал кое-что концептуально интересное.

Потому что цикла не получается. Код нециклический. Нельзя эту последовательность свернуть в циклический машкод.

но не в машинном ты же свернул? А почему в машинный нельзя без разворачивания?

Причем здесь бесконечность?

При том что бесконенчо генерируется разный код.

Меняется ведь только аргумент функции.

Нет, меняется вся итерация. Без евала просто выводится символ, с евалом - объявляется функция, компилируется в машкод, выполняется этот машкод. На каждой итерации.

Он никуда не девался, его там не было. На каждой итерации объявляется новая функция, компилируется джит-компилятором и генерируется новый машкод, отличный от машкода других итераций. Потом этот новый машкод выполняется.

это называется «неявный цикл». Типа вот этого:

#include <stdio.h>

void f(int counter, int *y)
{
·   if(counter == 0)·   return;
·   *y *= counter;
·   f(counter-1, y);
}

int main(int argc, char *argv[])
{
·   int n = 5;
·   int y = 1;
·   f(n, &y);
·   printf("%d!=%d\n", n, y);
·   return 0;
}

08048450 <f>:
 8048450:	8b 44 24 04          	mov    eax,DWORD PTR [esp+0x4]
 8048454:	8b 4c 24 08          	mov    ecx,DWORD PTR [esp+0x8]
 8048458:	85 c0                	test   eax,eax
 804845a:	74 0c                	je     8048468 <f+0x18>
 804845c:	8b 11                	mov    edx,DWORD PTR [ecx]
 804845e:	66 90                	xchg   ax,ax
 8048460:	0f af d0             	imul   edx,eax
 8048463:	48                   	dec    eax
 8048464:	75 fa                	jne    8048460 <f+0x10>
 8048466:	89 11                	mov    DWORD PTR [ecx],edx
 8048468:	c3                   	ret    

но не в машинном ты же свернул?

Свернул. Он же циклический.

А почему в машинный нельзя без разворачивания?

Без разворачивания нечего сворачивать. Чтобы получить свернутый машинный код, нам надо вообще для начала получить машинный код. А он бесконечный и нециклический. Мы можем сразу преобразовать в машинный код обвязку цикла, но то что внутри евала так и останется нескомпилированным кодом на лиспе до тех пор, пока выполнение туда не дойдет.

это называется «неявный цикл».

Нет, это не «неявный цикл». Тут вообще нету цикла.

как видишь, gcc свернул рекурсию в цикл.

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

Твой хаскель/лисп тоже так делает.

Нет, не делает. Более того - это невозможно сделать. Еще раз - на каждой итерации генерируется новый машинный код и этот новый код исполняется. Потом идет переход к следующей итерации, генерация нового кода, исполнение. И так до бесконечности. Итерации никогда не повторяются (т.к. в машкоде разные константы).

Я опустил несущественные команды. pop в самом printf

нет там pop. Учи матчасть, printf делает «push/pop» только для своих локальных переменных, для внешних локальных «push/pop» делает main.

От того что ты добавишь туда еще каких-то команд код все равно не станет циклическим, он нециклический из-за констант. Пока ты не уберешь константы - он не может быть приведен к циклическому виду.

это тебе так кажется. Ты путаешь «я не знаю как» с «это невозможно».

Я тебе привел конкретный код, который есть в реальности, который можно выполнить и который работает вполне конкретным образом. Но ты же в домике.

ещё раз повторяю: рекурсия всегда сворачивается в цикл. Только каждая итерация этого цикла может выполняться в своём собственном контексте. Т.ч. любой _код_ можно всегда свернуть в цикл, однако для этого может потребоваться неизвестно сколько памяти (точнее столько, сколько будет проходов рекурсии/цикла). Однако код может быть представлен в конечном виде всегда.

А этот твой eval == типичная рекурсия.

Собственно вот:

Добро пожаловать в DrRacket, версия 6.0 [3m].
Язык: racket [выбранный].
> (require disassemble)
> (for ([i 10])
    (eval `(begin (define (x) ,i) (x)))
    (decompile x #:size 26))
00000000  488943F8          mov [rbx-0x8],rax
00000004  4883C3F8          add rbx,byte -0x8
00000008  B801000000        mov eax,0x1
0000000D  4C8B75C8          mov r14,[rbp-0x38]
00000011  4883C428          add rsp,byte +0x28
00000015  5F                pop rdi
00000016  5E                pop rsi
00000017  5B                pop rbx
00000018  5D                pop rbp
00000019  C3                ret

00000000  488943F8          mov [rbx-0x8],rax
00000004  4883C3F8          add rbx,byte -0x8
00000008  B803000000        mov eax,0x3
0000000D  4C8B75C8          mov r14,[rbp-0x38]
00000011  4883C428          add rsp,byte +0x28
00000015  5F                pop rdi
00000016  5E                pop rsi
00000017  5B                pop rbx
00000018  5D                pop rbp
00000019  C3                ret

00000000  488943F8          mov [rbx-0x8],rax
00000004  4883C3F8          add rbx,byte -0x8
00000008  B805000000        mov eax,0x5
0000000D  4C8B75C8          mov r14,[rbp-0x38]
00000011  4883C428          add rsp,byte +0x28
00000015  5F                pop rdi
00000016  5E                pop rsi
00000017  5B                pop rbx
00000018  5D                pop rbp
00000019  C3                ret

00000000  488943F8          mov [rbx-0x8],rax
00000004  4883C3F8          add rbx,byte -0x8
00000008  B807000000        mov eax,0x7
0000000D  4C8B75C8          mov r14,[rbp-0x38]
00000011  4883C428          add rsp,byte +0x28
00000015  5F                pop rdi
00000016  5E                pop rsi
00000017  5B                pop rbx
00000018  5D                pop rbp
00000019  C3                ret

00000000  488943F8          mov [rbx-0x8],rax
00000004  4883C3F8          add rbx,byte -0x8
00000008  B809000000        mov eax,0x9
0000000D  4C8B75C8          mov r14,[rbp-0x38]
00000011  4883C428          add rsp,byte +0x28
00000015  5F                pop rdi
00000016  5E                pop rsi
00000017  5B                pop rbx
00000018  5D                pop rbp
00000019  C3                ret

00000000  488943F8          mov [rbx-0x8],rax
00000004  4883C3F8          add rbx,byte -0x8
00000008  B80B000000        mov eax,0xb
0000000D  4C8B75C8          mov r14,[rbp-0x38]
00000011  4883C428          add rsp,byte +0x28
00000015  5F                pop rdi
00000016  5E                pop rsi
00000017  5B                pop rbx
00000018  5D                pop rbp
00000019  C3                ret

...
> 

нет там pop. Учи матчасть, printf делает «push/pop» только для своих локальных переменных, для внешних локальных «push/pop» делает main.

При чем тут main и printf? При чем тут вообще твоя сишка?

это тебе так кажется. Ты путаешь «я не знаю как» с «это невозможно».

Это невозможно, и это доказано.

Если это возможно - предъяви мне, пожалуйста, алгоритм, который это сделает.

ещё раз повторяю: рекурсия всегда сворачивается в цикл.

Во-первых, нет, не всегда. Во-вторых - нет, там нету рекурсии.

Однако код может быть представлен в конечном виде всегда.

Нет. И, что характерно - интерпретаторы этого не делают.