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

Но конкретно в момент исполнения команд на ЦП эта последовательность задана и однозначна

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

Кстати

constexpr int bottom() { return bottom(); }
template <int n> struct A { enum { value = n }; };
int main() { return A<bottom()>::value; }

хотя типичным лимитом на ресурсы всё становится тут же «разрешимым» :)

Но это уже в сторону мета-программирования и случаев когда интерпретаторы тривиально превращаются в компиляторы, а когда не очень (constant folding и обобщения, разновидности CTFE, макросы и стадии, аbstract interpretation, partial evaluation, Futamura projection).

Посмотрел бегло пдф-ки по тем ссылкам, скажу честно: для моего мировосприятия и мозгов немного мудрённо. Вроде как - ехал Лисп через Лисп верхом на хромом Лиспе.

Потому и написал, что ухватка функциональщика.

Тут уже действительно разница мировосприятия, хотя готов признать, что доля истины в написанном Вами все же есть :)

Потому, хоть в лоб, хоть полбу, если написано x+y, то это надо перевести в add.

А можно и не переводя.

хотя типичным лимитом на ресурсы всё становится тут же «разрешимым» :)

И что же вернет «bottom()» при типичном ограничении на ресурсы? :)

Вот pdf-ки:

http://www.google.com/search?q=dragon book pdf (как бы)

http://www.google.com/search?q=programming language pragmatics pdf

no MIT this time :)

Это обычные книжки по теме, там просто должно быть и Лиспа или функциональщины тоже быть не должно.

clang в segmentation fault упадёт :)

Там -fconstexpr-depth, то есть полнота отсекается глубиной рекурсии (циклов всё равно нет).

Ну то есть и результата не будет. По-этому странно говорить о разрешимости - как же задача решена, если никакого результата нет?:)

Спасибо, гляну.

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

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

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

Но даже если и предположить что мы вот таким вот образом решили неразрешимую задачу, нам доподлинно известно, что сами интерпретаторы так не делают. Они берут и интерпретируют, не отсеивая :)

CTFE

Оно тут не при чем же.

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

То есть CISC инструкции интерпретируются RISC ядром устройства микропрограммного управления, тут победа за Вами.

На этом уровне действительно уже полностью справедливо утверждение, что интерпретация == исполнение.

На более высоком уровне абстрагирования это далеко не так очевидно.

Если ошибся, поправьте.

Вопрос в конкретном определении понятия «сомнительная на завершаемость программа»

Помимо возможности взять интерпретатор рекурсивных функций и вставить туда recursion depth (как в gcc/clang) есть исследования на тему termination checker-ов (типа type только про проблему останова) — есть вполне нетривиальный подкласс RE и разные нетривиальные паттерны рекурсии и циклов для которых завершимость автоматическое свойство и которых хватает для многих случаев когда нужны рекурсия или циклы, а остальное — сомневаемся и отбрасываем или руками разрешаем / доказываем (но это уже делаем работу за компилятор).

Они берут и интерпретируют, не отсеивая

Ну да — полный интерпретатор в трансляторе -> неразрешимость, просто на практике в таких случаях вешают лимит на space/time (если нужна таки трансляция).

Оно тут не при чем же.

Ну что там вместо в C++ — обычные рекурсивные constexpr функции (F) вычисляющиеся (E) во время компиляции (CT).

Хотелось бы примеров, т.к. абстрактное мышление тут уже не справляется.

Откуда берется этот «дефект массы» на входе некоторого исполнителя.

Ну да, если компилятор сделает Lang -> Asm (в CISC, допустим), то на интерпретацию, которая в данном случае есть выполнение на камне, можно смотреть как на Asm -> CPU-machine, то есть на загрузку кода в память — у нас есть состояние CPU-machine, тогда запуск (как Endo(CPU-Machine), например) есть обычная работа CPU (с декодированием в RISC или что там у него) начиная с этого начального состояния.

Прикол в том, что CPU-machine может быть не «выполнением на камне», а чистой интерпретаций в каком-нибудь эмуляторе (или не чистой с JIT).

Ну и абстрактный интерпретатор — Очепятки в книге по функциональному программированию (комментарий), простой арифметики, но он шаблонный, совсем нельзя сказать что он делает в терминах CPU, но при этом понятно что он делает в терминах арифметических операций типа Value (которые играют роль «ассемблера» тут), потому что это абстрактный интерпретатор. И тот факт, что C++ предполагает компиляцию кода этого интерпретатора не играет роли — как бы и так всё понятно.

Интересная концепция.

a program written in a source language S is directly executed by an S-interpreter, which is a program written in an implementation language

это никак не противоречит тому, что S переводится(транслируется) в язык реализации. Мало того, это твоя цитата как раз подтверждает факт трансляции, ибо «directly executed» возможно только на языке реализации.

¹ тебе по большому счёту не нужно, так как у тебя есть S-интерпретатор, который на своём уровне абстракций выполняет свои программы без всяких CPU. Сравни, допустим, с интерфейсом к файловым системам — ты можешь работать с ним как с API не зная ничего про архитектуру, код CPU, драйвера или ОС, тебе это не интересно на этом уровне.

ну мой калькулятор тоже позволяет абстрагироваться от деталей реализации. И что? Всё равно при вычислении 17^17=650 выполняются вполне определённые команды, на вполне конкретном CPU. Мне этот калькулятор как раз для компиляции и нужен, ибо gcc не умеет возводить в 17ю степень над GF(1399). Потому в коде я могу либо 650 записать, либо умножать 17 само на себя 17 раз. Фактически, мой калькулятор я использую именно как компилятор, ибо число 650 я прямо так и пишу в свой код, и в комментарии указываю, что это 17^17.

Ты как-то в сторону и на частности опять. Код не будет нигде находиться — см. A. выше.

будет. См ответ на А выше.

Чистый интерпретатор не делает S-terms -> T-terms, он берёт S, загружает в вычислитель и запускает его — S-terms -> S-machine.

ну вот а S-machine можно сохранить, а можно выполнить. Как хочешь. В первом случае получится компиляттор, во втором интерпретатор.

Попросту говоря, block не будет в другом месте (это же тоже локально), он будет кусками размазан где попало, то есть это не конкретные инструкции, а нетривиальные отношения на них — вытащить их во что-то вменяемое не тривиально

«нетривиально» лишь только потому, что семантика языка S не рассчитана на это вытаскивание. Как и реализация интерпретатора. Можно-ли решетом носить воду? В принципе можно — доработать решето(например смазать маслом), либо наоборот использовать впитывающие свойства решета(в мокром решете немножко воды унести можно). Принципиально решето эквивалентно ведру, вот только много дырок, и они (для воды) слишком крупные. И нет удобной ручки. Но это всё непринципиальные отличия. Из ведра можно сделать хреновое решето, из решета — хреновое ведро.

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

Да никакая «это» не «реальность» :)

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

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

рекурсию ты придумал, у меня её нет. S-int → S-maсhine. Всё. Далее S-machine уходит в файл или в процессор, который и вычисляет результат.

Не так. Принимаешь source программу, то есть строку, во время компиляции вычисляешь её длину n и генерируешь target программу ret n. Это будет правильное продолжение аналогии.

угу. А у меня не так? И ты не путай строку-данные и строку-код. Строка-код принимает на вход строку-константные-данные. Если у тебя интерпретатор, то строка-код переводится в строка-машкод, строка-константные-данные тоже переводится в строка-машкод (например в C/C++ это адрес в памяти обычно), а уж потом это всё исполняется. В случае компилятора это(строка-машкод) записывается в файл. Если данные не константные, а например содержимое файла, то строка-данные-из-файла тоже переводится в код fopen(3)/fread(3)/fclose(3) к примеру.

Eval это перевод строка-код → строка-код, в C/C++ не применяется, ибо семантика ЯП для этого очень плохо подходит. (заточена на преобразование в машкод). Ну и из-за необходимости для этого тащить весь gcc в любой хэлловорлд.

с какого перепугу перевод обязан быть однозначным?

При чем тут однозначность? Его просто нет. Мы никак не можем перевести. Ни однозначно, ни многозначно. Вообше никак.

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

Ещё раз, для тех кто в танке: обычный цикл выполняется неизвестно сколько раз. Рекурсия выполняется неизвестно сколько раз.

И что?

то, что необязательно делать свой цикл для каждого числа итераций, как делал интерпретатор в 70х годах прошлого века.

Не существует в общем случае последовательности команд, которую бы интерпретатор сопоставлял интерпретируемому коду.

а что тогда выполняет процессор?

Именно так, их нельзя скомпилировать. Это алгоритмически неразрешимая задача.

а как же полнота ЯП по Тьюрингу?

Любая виснущая программа, например :) Ей никакого машинного кода при интерпретации соответствовать не может (т.к. выполняется по факту бесконечная последовательность команд), но однако она прекрасно интерпретируется :)

4.2

думаешь в машинном коде нельзя сделать бесконечный цикл?

Но конкретно в момент исполнения команд на ЦП эта последовательность задана и однозначна

В том и дело что нет. Во-первых эта последовательность зависит от входных данных

4.2

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

во-вторых эта последовательность может быть актуально бесконечна - то есть перевода нету вовсе.

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

Потому, хоть в лоб, хоть полбу, если написано x+y, то это надо перевести в add.

А можно и не переводя.

сумму в хрустальном шаре смотреть будешь? Или таблицу сложения (2^32)^2 сохранишь?

И что же вернет «bottom()» при типичном ограничении на ресурсы? :)

UB

Ну да — полный интерпретатор в трансляторе -> неразрешимость, просто на практике в таких случаях вешают лимит на space/time (если нужна таки трансляция).

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

Хотелось бы примеров, т.к. абстрактное мышление тут уже не справляется.

Еще раз - любая виснущая программа. Ей соответствует актуально бесконечная последовательность команд - то есть мы не сможем «перевести» таким образом.

это никак не противоречит тому, что S переводится(транслируется) в язык реализации. Мало того, это твоя цитата как раз подтверждает факт трансляции, ибо «directly executed» возможно только на языке реализации.

S-interpreter может быть реализован, например, аппаратно. То есть язык реализации - и есть S-язык. Как, допустим, в лисп-машинах язык реализации - лисп и лисп-машина интерпретировала лисп-программу.

ну вот а S-machine можно сохранить

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

тогда и выполнение машкода невозможно, если этого машкода нет.

Коненчо возможно. Это доказывается хотя бы тем, что интерпретаторы ИРЛ существуют. Если бы это было невозможно - интерпретаторов бы не существовало.

то, что необязательно делать свой цикл для каждого числа итераций, как делал интерпретатор в 70х годах прошлого века.

Если внутри цикла есть eval (или фекспр или еще что подобное) - обязательно. Цикл целиком скомпилировать будет невозможно - только отдельную его итерацию. Которая в свою очередь тоже может содержать отдельный цикл (а может и не содержать). Итерации которого, в свою очередь, могут снова оказаться «плохими».

а что тогда выполняет процессор?

Команды процессора, очевидно. А что?

а как же полнота ЯП по Тьюрингу?

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

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

здесь тоже нельзя сказать:

if(внешние_условие)
    действие;

S-interpreter может быть реализован, например, аппаратно. То есть язык реализации - и есть S-язык. Как, допустим, в лисп-машинах язык реализации - лисп и лисп-машина интерпретировала лисп-программу.

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

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

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

то, что необязательно делать свой цикл для каждого числа итераций, как делал интерпретатор в 70х годах прошлого века.

Если внутри цикла есть eval (или фекспр или еще что подобное) - обязательно. Цикл целиком скомпилировать будет невозможно

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

а что тогда выполняет процессор?

Команды процессора, очевидно. А что?

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

S переводится(транслируется) в язык реализации. Мало того, это твоя цитата как раз подтверждает факт трансляции, ибо «directly executed» возможно только на языке реализации.

Ты продолжаешь

void wut(int);

«wut принимает числа и переводит(транслирует) их в свой собственный же код на языке своей реализации. Бо «wut takes an int and directly executes its code on it» возможно только на языке реализации».

Я не знаю что тут сказать.

мой калькулятор я использую именно как компилятор

Да, я выше писал — простой чистый интерпретатор в виде алгоритма f : Input -> Value тривиально превращается в компиляцию тривиальных программ как ret_instruction_is_target(f(compile_time_input_as_source)).

Но не f : Input -> Effects.

ну вот а S-machine можно сохранить, а можно выполнить

S-machine это множество состояний машины, для данного терма S это будет конкретное состояние в котором всё что ты найдёшь это представление терма S (в этом разница между состояниями) и «код интерпретатора» (он один и тот же), там нет кода соответствующего трансляционно терму S, так что нет трансляции S.

«нетривиально» лишь только потому, что семантика языка S не рассчитана на это вытаскивание.

Слово «семантика» решил вставить?)

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

Можно-ли решетом носить воду?

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

тыц

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

Также нет и «чистого интерпретатора», они все немножко(или не немножко) компиляторы. «Чистотой» могут похвастаться лишь самые примитивные поделия из древности.

Угу, в википедии написано про пре-трансляцию, байткод и т.д. и т.п., я знаю. А кусок который конечный интерпретатор — интерпретатор, а не транслятор.

S-int → S-maсhine

Я про терм S спрашиваю, а не про S-int. И про хоть какой-то T термов в результате (машина — не язык).

Далее S-machine уходит в файл или в процессор, который и вычисляет результат.

Ещё раз — S-machine это модель машины.

А у меня не так?

Нет, ты не понял пример с strlen (у тебя в [inline] size_t не фигурирует, ну и ты опять написал нечто в духе того что выше про wut).

На самом деле, все границы условны. В мире нет идеально чёрного и идеально белого. Есть только светло-серый, и тёмно-серый.

А если под вещества, так вообще! Наверное :)

Это единственный возможный пример? Хотеть видеть/знать больше примеров!

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

Хотя пример взят правильный это да - в случае с зависшей программой.

Но, так как я в данном случае выступаю в роли Фомы Неверующего, то хочется как минимум еще одного доказательства не из области крайних случаев состояния исполнителя :)

Хороший ответ!

Уже вспоминали на первой странице — http://en.wikipedia.org/wiki/Partial_evaluation, в конечном итоге всё равно останется код который всё ещё надо выполнить такой-то машиной.

А ты какой ответ спрашиваешь?

Даже не знаю, например:

#include <cstddef>

enum op { halt = 0, pls, dbl };

size_t ev(size_t in, op code[]) {

    for (size_t reg = in;; ++code)
        switch (*code) {
        case pls:
            ++reg;
            break;
        case dbl:
            reg *= 2;
            break;
        case halt:
            return reg;
        }

}

int main() {

    op code[] = { pls, dbl, pls, pls, dbl, dbl, halt };

    return ev(1, code);

}

теперь вопрос — как нам получить ассемблер соответствующий ev? Ну -S. Ассемблер для { pls, dbl, pls, pls, dbl, dbl, halt } — любо петросянство про то что ev для любого аргумента возвращает свой собственный машинный код (какого звучит, а :)), либо нам надо пройтись руками по цепочке, делать switch и собрать нужный код руками. Ну то есть выбросить интерпретатор и написать компилятор (не путаем с превращением ev в транслятор из (size_t, op[]) в size_t — речь про (size_t, op[]) -> asm).

Неплохо. Надо будет что погонять под отладчиком от нефиг делать.

Что же, спасибо, занимательно.

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

ну термы входного языка вполне однозначно переводятся в термы машинного. С этим ты согласен? Что мешает тогда сохранять машинные термы?

либо нам надо пройтись руками по цепочке, делать switch и собрать нужный код руками

this. Вот только «делать switch» не нужно, ты его и так делаешь. Просто сохраняй в файл команды.

Ну то есть выбросить интерпретатор и написать компилятор

то, что у тебя написано, уже и есть компилятор. Не хватает только записи в файл одной команды в каждом case'е. Причём места они не займут лишнего, ибо их можно поставить _вместо_ выполнения.

Добавим безусловных циклов, чтоб пример anonymous-а с зависанием был

#include <cstddef>
#include <cassert>

using Reg = size_t;

enum Op : Reg {
    HLT = 0,
    PLS = 1,
    DBL = 2
};

Op JMP(Reg label) {
    return Op(label + 3);
}

Reg label(Op op) {
    assert(op >= 3);
    return op - 3;
}

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: // JMP
            i = label(code[i]);
            break;
        }

}

int main() {

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

    return run(code);

}

Теперь трейсинг control flow с накоплением инструкций не прокатит, так как control flow может продолжаться сколько угодно долго.

Просто сохраняй в файл команды.

Nice try ;)

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

у тебя хреновая реализация jamp, она прыкает по входному коду, а должна прыгать по выходному коду. Т.е. тебе нужно:

1. добавить lable, такой NOP, который ничего не делает, а только сохраняет в памяти транслятора текущий адрес _выходного_ потока

2. добавить jmp lable, но вместо lable вставить адрес из п1.

Да, для переходов вперёд потребуется два прохода. Но ты не расстраивайся, тот же bash всё равно делает как минимум 2 прохода по файлу, пруф я уже здесь приводил.

пишем интерпретатор — нет

почему «нет»? Между твоей командой PLS и командой INC из x86 существует взаимно-однозначное соответствие. Не вижу проблемы.

Мне не нужно.

Оно не работает из коробки — нужно переписывать, в этом поинт. При том, что это максимально простой пример с четырьмя тупыми инструкциями, для «компиляции» вообще pretty printer-a хватит, AST-driven в обоих случаях, но разный код, разные типы аргументов и результатов, сигнатуры то есть, разное назначение.

Ещё можно взять такой же игрушечный

L : Set → Class
c : ℕ → L ℕ
v : ∀ {a} → a → L a
_·_ : ∀ {a b} → L (a → b) → L a → L b
_+_ : L ℕ → L ℕ → L ℕ
_*_ : L ℕ → L ℕ → L ℕ
ƛ : ∀ {a b} → (a → L b) → L (a → b)

run : ∀ {a} → L a → a
run (c n) = n
run (v v) = v
run (e₁ · e₂) = run e₁ (run e₂)
run (e₁ + e₂) = run e₁ + run e₂
run (e₁ * e₂) = run e₁ * run e₂
run (ƛ e) = run · e

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

Или любой реальный интерпретатор или компилятор — насколько это разные задачи (написать VM для эффективного прогона байткода, или заниматься многочисленными source-to-source/graph-to-graph на пассах).

здесь тоже нельзя сказать:

Ты не понял. В случае фекспров мы не знаем не только будут ли выполнены сайд-эффекты исполнения, но и будут ли выполнены сайд-эффекты «компиляции». Так что твой пример не подходит - мы можем заранее скомпилировать «действие;» и все будет ок. А в фекспрах - не можем, потому что не знаем надо ли будет это делать, а будет оно сделано или нет - может повлиять на контрол-флоу рантайма. В результате мы должны раскрывать макросы в рантайме.