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

Он не врёт, просто путает /no spoilers ;)

потому, что если bash просмотрит весь файл, и не найдёт done, то он рухнет с ошибкой.

И?

А если не рухнул, значит такой момент существует.

На основании чего сделан такой вывод? Если внутри цикла евал - то в момент просмотра цикла цикл не определен. Но баш прекрансо этот цикл выполняет. Так что практика опровергает твои глупые заявления.

Вообще чего ты уперся в этот done? Если я напишу программу которая проверяет в сфайле наличие вхождения слова «done» то эта программа с какого-то перепугу превратится в транслятор?

только она не бесконечная, увы.

Не бесконечная. Но в циклы не сворачивается.

тогда что? Опять что-то бесконечное придумаешь?

Нет, это графи в котором есть лупы с множественными тчоками входа.

for (...){
...
label 1;
...
if (...) goto 2;
...
}

for (...){
...
label 2;
...
if (...) goto 1;
...
}

вот тут будет irreducible flow graf

Теперь перепиши без гото.

ТСО там нет, но там есть оптимизация хвостовой рекурсии.

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

если у тебя есть eval который eval'ит код, то машинное представление естественно зависит от данных, и в общем случае определено однозначно только лишь после однозначного определения входных данных. Либо тебе придётся тащить в своём коде свой компилятор/интерпретатор.

И что? В базу ЦАБ тоже нельзя сейчас записать дату твоей смерти, т.к. она не определена. Потому базы ЦАБ не существует, и быть не может, да?

Нет. База ЦАБ существует. И мало того, есть два решения этой проблемы:

1. не хранить данные о мёртвых (не юзать такой eval)

2. хранить NULL вместо даты смерти, и ставить её когда ты умрёшь. (делать eval когда нужно).

если у тебя есть eval который eval'ит код, то машинное представление естественно зависит от данных, и в общем случае определено однозначно только лишь после однозначного определения входных данных.

Да определили мы входные данные, все в порядке (да, интерпретатор не является транслятором уже лишь только потому, что без входных данных работать не может, так что ты несешь заведомую чушь, мы просто пошли тебе навстречу и сейчас рассуждаем о сферическом в вакууме «а что если бы»). Машкод теперь как мне получить?

А это и не ТСО. Это замена хвостовой рекурсии циклом.

это как раз TCO. А после неё замена на обычный цикл (когда ret меняется на jmp, этот jmp как раз и образует бесконечный цикл).

это как раз TCO.

Нет, это не ТСО. Есть три разные оптимизации: ТСО, оптимизация хвостовой рекурсии и замена хвостовой рекурсии циклом.

В реализации?

А то речь была про стандарт, если это http://www.scala-lang.org/docu/files/ScalaReference.pdf, то я не вижу.

ты бредишь. В таком случае я «2+2=» не смогу вычислить, ибо «на этой ленте нет места для 4».

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

белены объелся? В моём компьютере память не ограничена?!

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

потому что прошло уже полвека, и за эти полвека придумали много нового. Потому вот и ЛОР работает на java. А если эту жабу писали-бы по книжкам 70х, то он бы годами посты отправлял и требовал эксабайты.

Так после десятого знака будет 11 знак. Потом 12. Потом 13. И так далее.

я всё равно не вижу проблемы. Ну запиши ты своё число в EAX, и будет у тебя работать до 2³²го знака, а дольше ты всё равно не проживёшь. Как и наша планета кстати.

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

белены объелся? В моём компьютере память не ограничена?!

Конечно нет. Всегда можно подрубить еще один винт.

потому что прошло уже полвека, и за эти полвека придумали много нового

Это замечательно. Я готов услышать от тебя описание этих современных методов 21 века, которые позволяют решать алгоритмически неразрешимые задачи. Жду с нетерпением просто.

я всё равно не вижу проблемы. Ну запиши ты своё число в EAX, и будет у тебя работать до 2³²го знака, а дольше ты всё равно не проживёшь.

Ну замечательно, то есть ты согласен с тем, что мы получим бесконечную ациклическую последовательность?

Именно так. Лента конечна в каждый момент времени, но бесконечна потенциально (мы можем подклеивать куски). И в таком предположении некоторые задачи - неразрешимы.

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

А после неё замена на обычный цикл (когда ret меняется на jmp, этот jmp как раз и образует бесконечный цикл).

Не ret, а call. ret как был так и остается. И это (замена call на jmp) как раз и есть TCO.

70х

0x.

наша задача — разрешима. Всегда можно попросить систему выделить немножко байт для контекста. Потому можно преобразовывать любой код на любом ЯП в машинный, причём сам код преобразования будет иметь заранее известную длину.

Замечательно. Раз она разрешима - я готов ознакомиться с алгоритмом. Ведь тебе, как человеку, обладающему знаниями 21 века не составит труда его привести?

Если ты не заметил, то общепринятая терминология

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

Я говорил, что разница между компилятором и интерпретатором не принципиальная

Конечно, принципиальная. Компилятор - транслирует, интерпретатор - не транслирует.

Причём этот поток всегда(может быть) заранее ограничен, на любых данных. А значит, его всегда можно сохранить в файл, и выполнить потом, независимо от данных.

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

Вот у тебя программа, входные данные, интерпретатор и логи его работы. Как по этой информации мне получить итоговый конечный машкод? Описание алгоритма, пожалуйста. Этот алгоритм, естественно, должен работать для любой программы. И при этом он должен быть реализован в каких-то реально существующих интерпретаторах, а не толкьо в твоем воспаленном воображении.

Компиляторы не зацикливаются (если не брать разное суровое метапрограммирование). Интерпретаторы — зацикливаются, вполне.

сами интерпретаторы тоже не зацикливаются. Зацикливается процессор, когда исполняет один и тот же код бесконечно. И не важно, чем этот код порождён, из файла, или из интерпретатора.

Любая VM выполняет свои программы сама, без всяких машкодов. Как она это умудряется делать?

при чём тут VM? Это тоже машина. И код у неё тоже машинный. Как и у процессора. Не вижу разницы.

Мы написали интерпретатор и компилятор языка в котором есть HTL

давай ещё обсудим, почему интерпретатор по другому делит на ноль, нежели компилятор? Ну нету результата у твоей HLT, стало быть и выполнения никакого нет(точнее «выполнение» тут не имеет смысла, как деление на ноль)

интерпретаторы зацикливаются

не. Интерпретатор штатно работает, выдавая одно и тоже.

Как и скомпилированный файл — выдаёт одни и те же байты JMP, которые процессор постоянно читает.

Причём современный интерпретатор в данном случае сначала посчитает байты JMP, а потом будет кормить процессор этими вычисленными байтами до бесконечности.

Ты можешь и компилятор также зациклить.

Интерпретатоыр не зацикливаются. Компиляторы зацикливаются.

ОК, я все понял.

Теперь перепиши без гото.

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

Хотя тут тоже непонятно: а почему твой говнокод нельзя скомпилировать С goto?

давай ещё обсудим, почему интерпретатор по другому делит на ноль, нежели компилятор?

Не по-другому. Также.

ТСО там нет, но там есть оптимизация хвостовой рекурсии.

ка что такое TCO? Я думал это tail call optimization, не? http://en.wikipedia.org/wiki/Tail_call

Хотя тут тоже непонятно: а почему твой говнокод нельзя скомпилировать С goto?

Ты о чем? Речь шла о невозможности привести рекурсию к циклу. С гото, конечно, можно. С циклами (без гото) - нельзя.

ка что такое TCO? Я думал это tail call optimization, не?

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

Конечно нет. Всегда можно подрубить еще один винт.

нельзя. Денег нет. Высылай, тогда утверждение будет доказано. ☺

Ну замечательно, то есть ты согласен с тем, что мы получим бесконечную ациклическую последовательность?

и что? Производящая рекуррентная функция будет конечной и очень простой. Причём её не нужно получать из портянки-кода, т.к. она записана в исходном тексте.

и что?

У нас есть бесконечная ациклическая последовательность десятичных цифр. Теперь мы делаем 10 функций, каждая из которых принимает число и возвращает строку, которая потом пойдет на евал. Евал сгенерирует некоторый машкод и отдаст поток управления этому машкода. Т.к. последовательность применяемых ф-й ациклична - у тебя нету никакого способа «вынести» переменную i как ты сделал это с предыдущим примером. У тебя получится бесконечный ациклический машкод. Который никак не сделать конечным, не свернуть в цикл и т.п.

Не ret, а call. ret как был так и остается. И это (замена call на jmp) как раз и есть TCO.

в данном случае ret тоже убирается. Т.к. он недостижим и вообще лишний.

Вот у тебя программа, входные данные, интерпретатор и логи его работы.

ты забыл исходный код самого интерпретатора. Именно его и нужно доделывать.

в данном случае ret тоже убирается.

 8048468:	c3                   	ret  

не убирается

TCO (а так же оптимизация хвостовой рекурсии и сворачивание в цикл) вообще с ret никак не связаны. Такие дела.

Хорошо, и код интерпретатора.

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

Ты о чем? Речь шла о невозможности привести рекурсию к циклу. С гото, конечно, можно. С циклами (без гото) - нельзя.

ну извини. Я не пользуюсь такими говноциклами, и не понимаю, на кой ляд они вообще нужны. ИМХО любой компилятор/интерпретатор имеет право отказаться жрать такое говно.

В качестве примера программы рассмотрим мой пример с евалом

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

Способ?

Я требую продолжения балета!

Ну ладно, JVM, .NET и реализации современных «интерпретируемых» языков.

Первая стадия трансляции — компиляция основного языка в байткод VM (сборка jar, например).

Это при сборке, AOT. Всё остальное — времени выполнения.

Первая стадия интерпретации — выполнение VM-ой этого байткода, VM написана на C или C++, скомпилирована и выполняется прямо на CPU, таким образом, «нативна», она использует функции рантайма, которые тоже нативны (аллокаторы, GC, операции примитивных типов и т.п.).

Вторая стадия трансляции — JIT, байткод, то есть IR VM, кроме непосредственно кода имеет связанную метаинформацию сохраняющую сведения о высоко-уровневых конструкциях, это позволяет VM при выполнении байткода детектировать впервые вызванные или просто горячие методы (типичный JIT) или горячие циклы (traced JIT), в этом случае нативный компилятор (который тоже часть рантайма) из IR в машинный код архитектуры на которой работает программа транслирует горячий байткод в машинный (со всякими оптимизациями опирающимися на информацию о текущем выполнении, которая есть у таких систем, в отличии от схемы AOT-сразу-в-машкод).

Вторая стадия интерпретации — нативное выполнение машкода от JIT, то есть VM/CPU в mixed-mode execution байткод/машкод.

А вот типичные компилируемые языки (C, C++) — только первая стадия сразу в машкод, и последняя на CPU. И LLVM тоже не VM (должно быть понятно).

А bash просто имеет перед своей стадией интерпретации стадию проверки (компиляции в IR?), если это понимать/различать, то в разговоре про непосредственно интерпретацию не должно быть спрыгиваний на проверки/пре-трансляцию (тут вторая цитата это же поясняет).

ну извини. Я не пользуюсь такими говноциклами, и не понимаю, на кой ляд они вообще нужны.

Да ради бога. Напоминаю - речь шла о приведении рекурсии к циклу. Ты сказал, что он всегда приводится. Я тебя поправил - нет, не всегда. На этом можно окончить разговор о рекурсии, циклах и гото.

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

ок.

Но это не меняет тот факт, что любую рекурсию можно свернуть в цикл, только потребуется хранить n контекстов в памяти. Но это не важно, т.к. при рекурсии эти n контекстов тоже хранятся в стеке.

Этот ваш eval тоже можно свернуть, если он определён с точностью до кода (т.е. если там меняются только переменные).

Если ты используешь суперкомпиляцию в eval, то придётся тащить за собой твой суперкомпилятор, да.

Но это не меняет тот факт, что любую рекурсию можно свернуть в цикл

Нет, нельзя если граф irreducible

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

И я все еще жду от тебя способ получения машкода.

У нас есть бесконечная ациклическая последовательность десятичных цифр. Теперь мы делаем 10 функций, каждая из которых принимает число и возвращает строку, которая потом пойдет на евал. Евал сгенерирует некоторый машкод и отдаст поток управления этому машкода. Т.к. последовательность применяемых ф-й ациклична - у тебя нету никакого способа «вынести» переменную i как ты сделал это с предыдущим примером. У тебя получится бесконечный ациклический машкод.

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

Это между прочим вполне рабочий код, именно так выполняются виртуальные функции в C++. Т.е. каждый объект класса хранит указатель на таблицу, а в таблице хранятся указатели на функции. В итоге, прямо в рантайме для каждого объекта подставляется своя виртуальная функция.

И ВНЕЗАПНО: процессоры IA-32/amd64 отлично с этим работают. Там и команды для этого есть специальные, для дважды косвенного перехода.

не убирается

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

сами интерпретаторы тоже не зацикливаются

Ну CPU-то (интерпретатор же) зацикливается?

И не важно, чем этот код порождён, из файла, или из интерпретатора.

Мысленный эксперимент — бубунта без gcc и бинарным пакетом с каким-нибудь интерпретатором. Машинный код последнего есть. Машинного кода программ которые он интерпретирует нет (и не может быть, компилятора-то нет), если только ты не считаешь, что постоянный код самого интерпретатора это он и есть (но это не дело).

при чём тут VM? Это тоже машина. И код у неё тоже машинный. Как и у процессора. Не вижу разницы.

С любым интерпретатором связана VM. Её код это интерпретируемые программы. Машинный код он у скомпилированной реализации для запуска.

Ну нету результата у твоей HLT, стало быть и выполнения никакого нет

А у компилятора есть. В смысле, он на HLT смотрит совсем иначе.

Ты можешь и компилятор также зациклить.

gcc можешь? Иди на багтрекер тогда.

что ты этим доказал?

Да ради бога. Напоминаю - речь шла о приведении рекурсии к циклу. Ты сказал, что он всегда приводится. Я тебя поправил - нет, не всегда.

причём показал почему-то цикл, а не рекурсию. Ты ничего не перепутал?

Ты же говоришь о том, что можно любую рекурсию привести к хвостовому виду

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

Плюс ещё одну функцию, которая просматривает цифры в аргументе, и выполняет нужные функции в зависимости от цифр.

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

Я такого не говорил.

Врешь:

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

А у компилятора есть. В смысле, он на HLT смотрит совсем иначе.

ну сделай в компиляторе HLT, что-бы смотрел также. Можешь там матерное слово по-русски написать прямо в коде. Чем тебе не HLT в компиляторе?

Ты можешь и компилятор также зациклить.

gcc можешь?

код чуток подправить, что-бы как в компиляторах, не останавливался, а дальше компиллил.

бесконечное количество яблок вполне соответствует.

такого количества не бывает.

бывает. man трансфинитные числа , кардинальные, порядковые

вот Алеф 0, например — количество всёх порядковых чисел.

Я такого не говорил.

Конечно не говорил, ты просто перепутал приведение рекурсии к хвостовому виду (которое возможно выталкиванием фреймов со стека на хип) и приведением рекурсии к циклу (которое невозможно).

Врешь:

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

это ты врёшь, когда приписываешь мне слова «не выделять стекфреймы вообще». И слова «к хвостовому виду (CPO transformation)». Это ты их придумал. Я говорил «в цикл», но про CPO — твоя фантазия.

бесконечное количество яблок вполне соответствует.

такого количества не бывает.

бывает. man трансфинитные числа , кардинальные, порядковые

придурок, где ты видел такие ЯБЛОКИ?