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

Является ли транслятором команда touch ? Входные данные есть (имя файла), выполнение бинарного кода тоже...

при чём тут «команда touch»

Ещё раз, для тех, кто в танке: ты знаешь такую профессию «переводчик»? Ну вот компилятор/интерпретатор и есть «переводчик».

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

Ну а с какого на какой язык — значения не имеет. Вот gcc это вообще «полиглот». Кстати, с ключом -S gcc выплёвывает не бинарник, а текстовый файл.

Вот тебе hello world

	.file	"helloworld.c"
	.section	.rodata
.LC0:
	.string	"hello world"
	.text
	.globl	main
	.type	main, @function
main:
.LFB0:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	andl	$-16, %esp
	subl	$16, %esp
	movl	$.LC0, (%esp)
	call	puts
	movl	$0, %eax
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE0:
	.size	main, .-main
	.ident	"GCC: (GNU) 4.8.2"
	.section	.note.GNU-stack,"",@progbits

это C → IA-32(x86). Только коммпилятор схалявничал, и не доделал до конца. Обычно он этот код в двоичном виде делает:

вот первые байты:

00000000  7f 45 4c 46 01 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 03 00 01 00 00 00  f0 82 04 08 34 00 00 00  |............4...|
00000020  34 0e 00 00 00 00 00 00  34 00 20 00 08 00 28 00  |4.......4. ...(.|
00000030  23 00 20 00 06 00 00 00  34 00 00 00 34 80 04 08  |#. .....4...4...|
00000040  34 80 04 08 00 01 00 00  00 01 00 00 05 00 00 00  |4...............|
00000050  04 00 00 00 03 00 00 00  34 01 00 00 34 81 04 08  |........4...4...|
00000060  34 81 04 08 13 00 00 00  13 00 00 00 04 00 00 00  |4...............|
00000070  01 00 00 00 01 00 00 00  00 00 00 00 00 80 04 08  |................|
00000080  00 80 04 08 08 06 00 00  08 06 00 00 05 00 00 00  |................|
00000090  00 10 00 00 01 00 00 00  08 06 00 00 08 96 04 08  |................|
000000a0  08 96 04 08 00 01 00 00  08 01 00 00 06 00 00 00  |................|
000000b0  00 10 00 00 02 00 00 00  1c 06 00 00 1c 96 04 08  |................|
000000c0  1c 96 04 08 c8 00 00 00  c8 00 00 00 06 00 00 00  |................|
000000d0  04 00 00 00 04 00 00 00  48 01 00 00 48 81 04 08  |........H...H...|
000000e0  48 81 04 08 20 00 00 00  20 00 00 00 04 00 00 00  |H... ... .......|
000000f0  04 00 00 00 50 e5 74 64  2c 05 00 00 2c 85 04 08  |....P.td,...,...|

другие синхронно переводят живую речь (интерпретаторы).

Но sh (а также старый бейсик) никуда входной файл не переводят, а исполняют по мере чтения.

А если мы считаем, что выполнение — подвид «перевода», тогда вопрос про команду touch (а также ftp, mail, cp) остаётся открытым. Входные данные есть, действия есть.

Но sh (а также старый бейсик) никуда входной файл не переводят, а исполняют по мере чтения.

процессор не умеет исполнять бэйсик и sh, потому его надо переводить в ассемблер. А уже потом исполнять.

А если мы считаем, что выполнение — подвид «перевода», тогда вопрос про команду touch (а также ftp, mail, cp) остаётся открытым. Входные данные есть, действия есть.

есть действие. Это выполнение кода из файла /usr/bin/touch.

Оболочка парсит входной текст, видит там непонятное(ей) слово «touch», и потому ищет в путях $PATH такой файл. Если-бы это было «echo», а оболочкой /bin/bash, то она-бы сама «перевела» echo в код.

процессор не умеет исполнять бэйсик и sh, потому его надо переводить в машинный код. А уже потом исполнять.

fixed

я уже писал ниже: ассемблер взаимооднозначен машинному коду.

Ещё раз, для тех, кто в танке: ты знаешь такую профессию «переводчик»? Ну вот компилятор/интерпретатор и есть «переводчик».

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

Так вот транслятор - это переводчик. Компилятор - это транслятор (то есть переводчик). Он переводи текст с ЯП на машкод.

А есть такая профессия - «исполнитель». Это товарищ, который берет текст на некотором языке (на английском) и исполняет этот текст. При этом он его не переводит. Он вообще никаких других языков не знает (кроме английского) и по-этому перевести не может - в принципе. Потому и не переводит. Так вот интерпретатор - это исполнитель. Он не переводчик. И не транслятор, соответственно.

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

Да-да, даже небо, даже аллах - все суть «исполнение».

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

Хаскелл головного мозга? «Мы не изменяем Мир, а транслируем его старое состояние в новое»?

Хаскелл головного мозга? «Мы не изменяем Мир, а транслируем его старое состояние в новое»?

Строго наоборот. Нет никаких состояний, есть только процесс перезаписи. Я бы сказал, абсолютный нондетерменизм. Хаскель, наоборот запарен на глобальном состоянии.

Хаскель, наоборот запарен на глобальном состоянии.

Это где такое? Апологеты на ЛОРе наоборот говорят, что состояний у объектов нет, есть только функции. В качестве примера было «мы не красим холодильник в зелёный цвет, а определяем функцию, которая для холодильника возвращает такой же, но зелёный».

Нет никаких состояний, есть только процесс перезаписи. Я бы сказал, абсолютный нондетерменизм.

То есть процесс перезаписи никак не зависит от состояния на момент начала перезаписи (потому как состояния нет). Сильно!

То есть процесс перезаписи никак не зависит от состояния на момент начала перезаписи

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

есть только функции

В хашкеле ф-ции — это замыкания, они эквивалентны объектам в классовом ООП. Что они там себе мнят — это их проблемы.

В качестве примера было «мы не красим холодильник в зелёный цвет, а определяем функцию, которая для холодильника возвращает такой же, но зелёный».

ИМХО, это эквивалентно присваиванию, при условии, что мы будем обращаться к «зеленому холодильнику» только через эту ф-цию. Семантически эквивалентно, я имею в виду. Это, видимо то, что называется монадами у них?

Хм, но тут вопрос. Ведь перед тем как выполнить программу ее нужно привести к соответствующему машинному представлению. Это разве не трансляция? Где ошибка?

Хм, но тут вопрос. Ведь перед тем как выполнить программу ее нужно привести к соответствующему машинному представлению.

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

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

А именно есть ли такое преобразование, которое переводит систему команд интерпретатора в систему команд CPU?

Вот в чем мой вопрос.

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

ты бредишь: если нет, то как же этот код _исполняется_? Может ты хотел сказать «нельзя сопоставить заранее»? Ну да, такое есть. Ну и что?

PS: вот только что написал калькулятор, прям как в K&R. Там тоже интерпретация выражения вроде 2+2*2=?, выдаёт ессно 6. Да, какой именно код сопоставляется — от выражения зависит, и тем не менее, это всё на C++.

как же этот код _исполняется_?

Исполняется код интерпретатора — он один на все интерпретируемые программы, которым ничего не соответствует кроме такого-то способа их исполнения этим интерпретатором.

Ну и что?

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

только что написал калькулятор

Теперь сделай функцию дампа своего машинного кода который «сопоставляется» в файл для любых выражений. Хотя погоди... тебе же придётся выкинуть свой интерпретатор и написать компилятор :)

Что тогда представляют из себя команды интерпретатора с точки зрения центрального процессора ПК ?!!

Ничего не представляют.

А именно есть ли такое преобразование, которое переводит систему команд интерпретатора в систему команд CPU?

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

Самый очевидный пример - языки с фекспрами. Они не могут быть компилированы. То есть вообще никак, даже теоретически.

Может ты хотел сказать «нельзя сопоставить заранее»? Ну да, такое есть. Ну и что?

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

если нет, то как же этот код _исполняется_?

Берет и исполняется. Для этого, к счастью, трансляция не требуется.

то есть перевести в какой-то программный код.

машинный код selffix

А именно есть ли такое преобразование, которое переводит систему команд интерпретатора в систему команд CPU?

Интерпретатор принимает выражения своего языка, какой-то внешний вход и производит исполнение с эффектами, возвращает выход. То есть представляет из себя функцию/программу написанную на языке своей реализации — при компиляции она вполне может быть скомпилирована в такой-то код, как и всякая функция. Делать подобное выполнение это всё что он должен — остальное это детали реализации. А если под его системой команд понимаются не они, а выражение его языка, то им не соответствует кода — код один, это код интерпретатора, его входным выражениям соответствуют конкретные пути его исполнения.

Ещё см. Чем отличается компилятор от интерпретатора? (комментарий) — мы можем на любую функцию смотреть как на интерпретатор (то же исполнение). Например, strlen (максимально упрощённый случай) притворяется функцией возвращающей 5 если на вход подаётся строка длинной в пять символов, 7 — семь символов и т.д. Какой код CPU соответствует strlen? Какой код CPU соответствует строке в пять символов?

Исполняется код интерпретатора — он один на все интерпретируемые программы, которым ничего не соответствует кроме такого-то способа их исполнения этим интерпретатором.

да говорю же  — ты бредишь. Выполни $ while true; do true; done. Выполнил? И чем у тебя CPU загружен?

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

дык есть сопоставление. В любом интерпретаторе.

Теперь сделай функцию дампа своего машинного кода который «сопоставляется» в файл для любых выражений. Хотя погоди... тебе же придётся выкинуть свой интерпретатор и написать компилятор :)

чего «годить»? Могу и сопоставить. Каждая строка C++ кода порождает вполне конкретный машинный код. Если его сохранить, получится компилятор. Для каждого выражения получается свой код.

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

в таком случае, выполнить её на IA-32/amd64 тоже невозможно.

Самый очевидный пример - языки с фекспрами. Они не могут быть компилированы. То есть вообще никак, даже теоретически.

да, конечно.

Может ты хотел сказать «нельзя сопоставить заранее»? Ну да, такое есть. Ну и что?

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

с какого перепугу перевод обязан быть однозначным? Ещё раз, для тех кто в танке: обычный цикл выполняется неизвестно сколько раз. Рекурсия выполняется неизвестно сколько раз. Вот у меня например для выражения 1+2+3 две команды add, а для 1+2+3+4 четыре команды add. И что? Код один.

если нет, то как же этот код _исполняется_?

Берет и исполняется

ага. Благодатный огонь снизошёл.

то есть перевести в какой-то программный код.

машинный код selffix

Дзен-программа с фекспрами.

Какой код CPU соответствует strlen

вот такой например:

    movl    %edx, %eax
    .p2align 4,,15
.L3:
    incl    %eax
    cmpb    $0, -1(%eax)
    jne .L3
    subl    %edx, %eax
    ret

Выполнил? И чем у тебя CPU загружен?

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

дык есть сопоставление.

Есть код интерпретатора, один. Интерпретируемые выражения соответствуют путям исполнения этого кода, одного и того же.

А в случае компилятора — свой код для каждой программы.

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

Могу и сопоставить.

Ну выкатывай код.

Каждая строка C++ кода порождает вполне конкретный машинный код.

Так ты калькулятор или интерпретатор C++ написал?

Это код интерпретатора. Теперь показывай код CPU в виде инструкций соответствующий его интерпретируемым программам, то есть строкам — «12345», например (5 при интерпретации).

А конкретный код можно господам в студию ;)

Но конкретно в момент исполнения команд на ЦП эта последовательность задана и однозначна, они же машинные, если программа работает. Иначе такой интерпретатор это сферический конь Бора в вакууме :)

ага. Благодатный огонь снизошёл.

Аналогия близка к действительности. Без пруфов, дальнейшая дискуссия бессмысленна

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

Ну здесь мы все будем единодушны им соответствует их собственный исходный код.

Мне бы такое зрение увидеть никого, да еще на таком расстоянии (с)

Белый Король. Алиса в Зазеркалье

То есть «SELECT foo FROM bar WHERE baz» соответствует не что иное, как «SELECT foo FROM bar WHERE baz»?

Это прямо архи полезно для знания семантики этого языка :)

Либо ей соответствует интерпретатор, точнее один из способов его выполнения, http://en.wikipedia.org/wiki/Operational_semantics, со своим смыслом, http://en.wikipedia.org/wiki/Denotational_semantics.

Или другая программа с эквивалентной семантикой, http://homepage.cs.uri.edu/faculty/hamel/courses/2011/fall2011/csc501/lecture..., http://homepage.cs.uiowa.edu/~slonnegr/plf/Book/Chapter7.pdf, и своим смыслом.

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

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

Да и в Вас чувствуется ухватка хаскелиста ;)

Нет подмены понятий, есть понятия языков, грамматик (это к синтаксису), трансляторов, интерпретаторов (это к соответствующим семантикам), это общие понятия. SQL — пример (никаких исчислений кортежей не подразумевалось), Си — пример, как и любые другие языки, будь то DSL или ЯП общего назначения.

И вообще я уже не знаю что мы обсуждаем.

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

Ещё раз ссылки, по мелочи:

http://en.wikipedia.org/wiki/Formal_language

http://en.wikipedia.org/wiki/Formal_grammar

http://en.wikipedia.org/wiki/Interpreter_(computing)

http://en.wikipedia.org/wiki/Translator_(computing) (предложение про интерпретатор проясняется дальше)

http://en.wikipedia.org/wiki/Operational_semantics

http://en.wikipedia.org/wiki/Denotational_semantics

Точнее (загугли pdf-ки):

http://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/032148...

Остальные книжки про компиляторы больше по делу и без общих мест, но в том же духе — интерпретация и трансляция это две разные вещи.

Более новые, там так же, я выше по треду цитировал:

http://www.amazon.com/Concepts-Techniques-Models-Computer-Programming/dp/0262...

http://www.amazon.com/Programming-Language-Pragmatics-Third-Edition/dp/012374... (конкретно тут проясняется про интерпретатор в смысле википедии)

http://www.amazon.com/Design-Concepts-Programming-Languages-Franklyn/dp/02622...

Ещё:

http://homepage.cs.uiowa.edu/~slonnegr/plf/Book/Chapter7.pdf

http://homepage.cs.uri.edu/faculty/hamel/courses/2011/fall2011/csc501/lecture...

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

В чём именно? Я вообще молчу, за меня говорит попса в виде dragon book — никакого отношения ко всяким там... :)

Ещё Харпера можно, но у него там интерпретация и трансляция чисто математические, немного в смысле картинки из http://homepage.cs.uri.edu/faculty/hamel/courses/2011/fall2011/csc501/lecture...

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

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

Есть код интерпретатора, один. Интерпретируемые выражения соответствуют путям исполнения этого кода, одного и того же. А в случае компилятора — свой код для каждой программы.

x+y всегда транслируется компилятором в команду add, и интерпретатором тоже(если без оптимизации конечно). Не вижу разницы в упор.

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

всё там прекрасно вытаскивается.

Ну выкатывай код.

не понимаю, код чего?

Ну возьми gdb и посмотри.

Так ты калькулятор или интерпретатор C++ написал?

калькулятор, который транслирует ЯП арифметических выражений(а это тоже алгоритмический ЯП) в машинный код, и его сразу выполняет. При чём тут C++? Кто вообще сказал, что программа на C++ должна обязательно компилироваться в C++, а уж потом в ассемблер? Мой калькулятор вообще никакого отношения к C++ не имеет, у него на входе арифметическое выражение, а на выходе машинный код, который прямо сразу и выполняется. И сам он на машинном коде, а на C++ только его исходник, который можно на что угодно переписать.

И да, скобки мой калькулятор умеет, а следовательно там есть «мощный eval». Как вы и заказывали.

Это код интерпретатора. Теперь показывай код CPU в виде инструкций соответствующий его интерпретируемым программам, то есть строкам — «12345», например (5 при интерпретации).

это машинный код. Для любых ASCIIZ строк(ну в смысле <2³¹). Для «12345» оно тоже работает(правда там 6 итераций).

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

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

И да, именно взаимно-однозначное существует. Просто людям неудобно им пользоваться. Мне проще писать ⅔x, а компилятор переделывает это в x*0xAAAAAAAA. Также мне нравится использовать все три типа циклов (for, while, do{}while), но компилятор юзает только последний тип. Ну а ещё компилятор через строку пихает goto, и прочую гадость. А мне так читать неудобно.

Теоретически возможно и действительно взаимо-однозначное, вот только _моё_ понятие «удобочитаемости» абсолютно не формализуется. Потому при двойном переводе получается нечитаемый говнокод. За то этот говнокод

1. эквивалентен моему коду

2. взаимо-однозначен

ссылки

ты путаешь подходы и определения. Формально компилятор и интерпретатор ничем не отличается, однако для построения удобного и годного DSL важно учитывать специфику. Т.е. в принципе можно запихать замкнутый eval в C→C, вот только оно нафиг никому не нужно. Сам ЯП заточен не компиляцию в машинный код. Также и введение оптимизируещего компилятора в какой-нить PHP тоже ничего не даст и не нужно. Компилятор всё равно не сможет оптимизировать утиную типизацию, которая определиться только в рантайме. Вот и будет на массив char'ов в 10 штук, хранить и пережёвывать 20 указателей в 8 char'ов каждый. Смысл?

цикл транслируется в команды CPU, которые и выполняются.

Цикл у тебя сразу выполняется в случае pure interpretation. Команды CPU у тебя уже тут, в коде откомпилированного интерпретатора, его бинарника, он берёт твой текст/AST и делает своё дело как любая другая функция — нечего ему транслировать, так как выходного языка не предполагается.

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

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

x+y всегда транслируется компилятором в команду add, и интерпретатором тоже(если без оптимизации конечно).

Да ладно, во что хочет, в то и транслируется, как хочет, так и интерпретирует, то что в C++ _+_ не имеет отношения к тому что в реализуемом языке _+_ (gmp_add или matrix_add, например) — поскипано во имя перегрузки.

Не вижу разницы в упор.

Ты просто привязался к своему «интерпретатор транслирует свои программы в инструкции CPU и выполняет их», хотя привязываться не нужно — нужно коммуницировать :)

То есть ты говоришь, что

void f(int n) {
    ...
    if (n == 2) {
        ... block ...
    }
}

транслирует (во время выполнения, чо) вход 2 в CPU инструкции block. Они полученные уже, правда, заранее компиляцией этого кода, да и не работает это — сделай block не локальным, но нетривиальным control flow и непонятно где твоё соответствие (в формальном смысле этого слова, то есть отображения из язык в язык, а то может ты «примерно» говоришь).

всё там прекрасно вытаскивается.

Ну возьми gdb и посмотри.

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

При чём тут C++?

Ты говоришь

Каждая строка C++ кода порождает вполне конкретный машинный код.

А тебе надо, чтобы каждое арифметическое выражение транслировалось в машинный код (раз всё вытаскивается). Т.е. я тебе даю, например, (2+3)*5 — твой велосипед мне кидает кусок ассемблера/машинного кода, а если ты интерпретируешь, то нечего рассказывать, ты путаешь код самого интерпретатора с кодом который бы соответствовал (2+3)*5 при компиляции.

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

Да, я уже понял что ты пишешь, «у меня на входе strlen строки, а на выходе машинный код [который ты в виде *.s уже запостил], который прямо сразу и выполняется».

это машинный код. Для любых ASCIIZ строк

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

Но это не относится к нашему спору.

Это относится к тому, что compile/decompile не «взаимно-однозначны» — это сложно и невозможно, если только на классах эквивалентности modulo сохранению семантики — это возможно и легко, но не интересно и есть вопрос о том что есть сохранение семантики.

взаимно-однозначное существует

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

Вот только код после декомпиляции невозможно читать людям

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

Формально компилятор и интерпретатор ничем не отличается

А пруф? А то пишуть альтёрнатив апроач.

Но правда, что и то и другое можно объединить под общим «processing», «обработка».

З.Ы. в математике, тащемто, интерпретация и трансляция (гомоморфизм) это примерно то же, что эти понятия по ссылкам.

Цикл у тебя сразу выполняется в случае pure interpretation. Команды CPU⁽¹ у тебя уже тут, в коде откомпилированного интерпретатора, его бинарника, он берёт твой текст/AST и делает своё дело как любая другая функция — нечего ему транслировать⁽², так как выходного языка не предполагается.

т.е. ты утверждаешь, что (1 берётся из хрустального шара или другой магией(благодатным огнём), да?

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

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

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

x+y всегда транслируется компилятором в команду add, и интерпретатором тоже(если без оптимизации конечно).

Да ладно, во что хочет, в то и транслируется, как хочет, так и интерпретирует, то что в C++ _+_ не имеет отношения к тому что в реализуемом языке _+_

ЯП и его стандарт не имеет. Однако компилятор в IA-32 других вариантов не знает. Как и интерпретатор. И не приплетай сюда перегрузку, она меняет сам смысл operator+(). Речь лишь про встроенный тип int/float. Я уже говорил выше, что если у тебя «утиная» типизация, то что компилятор, что интерпретатор, могут только в рантайме решить, каким кодом складывать числа. Посему тащат за собой всё множество кодов для любых сложений.

Ты просто привязался к своему «интерпретатор транслирует свои программы в инструкции CPU и выполняет их», хотя привязываться не нужно — нужно коммуницировать :)

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

транслирует (во время выполнения, чо) вход 2 в CPU инструкции block. Они полученные уже, правда, заранее компиляцией этого кода, да и не работает это — сделай block не локальным, но нетривиальным control flow и непонятно где твоё соответствие (в формальном смысле этого слова, то есть отображения из язык в язык, а то может ты «примерно» говоришь).

всё работает. Сделай block не локальным, и код будет находится в другом месте. Будет. И с интерпретатором также.

Ну возьми gdb и посмотри.

Это не вытаскивается, это каша

это не доказательство. Выхлоп интерпретатора никто не готовил специально для тебя. Твой CPU эту кашу жрёт, и просит ещё, а что тебе не пошло — твоя проблема. Выхлоп gcc -O2 тоже не слишком просто осилить, если программа нетривиальная.

Т.е. я тебе даю, например, (2+3)*5 — твой велосипед мне кидает кусок ассемблера/машинного кода, а если ты интерпретируешь, то нечего рассказывать, ты путаешь код самого интерпретатора с кодом который бы соответствовал (2+3)*5 при компиляции.

вот «код самого интерпретатора» и есть выход. Этот код может вычислить (2+3)*5, и дать ответ 25. Т.о. данный код является трансляцией любого выражения в машинный код, даже если само выражение заранее неизвестно. Как видишь, условие известности алгоритмов не обязательно. Алгоритм можно задать во время выполнения. Т.е. можно 2+(3*5), а можно (2+3)*5. Тут числа одинаковые, но алгоритм вычисления разный. Ответ тоже разный. Но интерпретатор один единственный, хотя машинный код порождается и выполняется разный.

Да, я уже понял что ты пишешь, «у меня на входе strlen строки, а на выходе машинный код [который ты в виде *.s уже запостил], который прямо сразу и выполняется».

у тебя тоже.

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

почему нет? Ок, напишу:

if(strcpy(input_string, "strlen")==0)
    fwrite(мой_код, размер_кода, 1, выходной_файл);

Ну то есть транслятора из строк в CPU код у тебя нет

зачем тебе такой транслятор? Что тебе мешает хранить строки как наборы байт? Зачем тебе их транслятор?

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

я на C/C++ — нет. Но теоретический такой код возможен и такой компилятор тоже. Просто оно никому не нужно. Если я пишу ⅔, то компилятор это превращает в 0x55555556, откуда ты ⅔ уже не вытащишь однозначно. Если я пишу x*=2, компилятор пишет x<<=1. Это тоже обратно переводится в x<<=1.

Нет, значит не взаимно-однозначное, если тебе не пофиг на читаемость и сохранение абстракций и не нужно только «работает так же»

при чём тут читаемость? Возможность есть. Просто она никому не нужна. Проще исходник приложить. Потому никто и не реализовал.

да и то, не факт, что компиляция с оптимизациями, декомпиляция и повторная компиляция с оптимизациями будет «так же» работать

ну дык с оптимизацией оно и так «не так» работает. А быстрее. Т.е. это не баг, а фича. Если я пишу 1+2, компилятору плевать на однозначность, и он пишет 3, откуда естественно не вытащить 1+2. Неужели ты думаешь, что невозможно написать такой компилятор, который будет в рантайме Over9000 раз складывать 1+2? Ради вселенской однозначности...

Формально компилятор и интерпретатор ничем не отличается

А пруф?

пруф — возможность исполнения и того и того в семантике одного и того же CPU. Потому что в CPU нет «двух режимов», а есть только один — исполнение кода. Потому, хоть в лоб, хоть полбу, если написано x+y, то это надо перевести в add.

т.е. ты утверждаешь, что (1 берётся из хрустального шара или другой магией(благодатным огнём), да?

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

A.

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-интерпретатор, который на своём уровне абстракций выполняет свои программы без всяких CPU. Сравни, допустим, с интерфейсом к файловым системам — ты можешь работать с ним как с API не зная ничего про архитектуру, код CPU, драйвера или ОС, тебе это не интересно на этом уровне. Есть представление о семантике implementation language и ладно — дальше нам не нужно.

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

(S-terms -> S-Machine) by S-interpreter

B.

Но если хочешь — пусть S-интерпретатор написан на своём языке Inter и может быть скомпилирован в язык CPU компилятором Inter -> CPU, это будет ⁽², язык CPU может быть выполнен CPU-интерпретатором — вот это уже ⁽¹. Интерпретация это семантическая обработка, с ней связан абстрактный вычислитель, то есть в случае S-интерпретатора совсем абстрактный, в случае CPU — и конкретный тоже.

(S-terms -> S-Machine) by S-interpreter

(Inter-terms -> CPU-terms) by Inter-to-CPU compiler for this particular S-interpreter

(CPU-terms -> CPU-machine) by CPU-interpreter

C.

In the translation approach, an S program is translated to a program in the target language T, which can be executed by a T-interpreter.

Чистый интерпретатор не делает S-terms -> T-terms, он берёт S, загружает в вычислитель и запускает его — S-terms -> S-machine. То есть с одной стороны у нас трансляция — синтаксическая обработка в виде чёрного ящика который работает как функция (http://en.wikipedia.org/wiki/Natural_transformation, http://en.wikipedia.org/wiki/Homomorphism, гомоморфизмы синтаксических структур из синтаксических категорий с естественностью по отношению к модельным функторам в семантические домены, то есть вообще говоря синтаксическая трансляция учитывает сохранение семантики), то есть принимает программы (синтаксис) и возвращает программы (он же), а с другой интерпретация — семантическая в виде ящика который работает как исполнитель/машина которая просто принимает программы и их выполняет (семантика, http://en.wikipedia.org/wiki/Functor, http://en.wikipedia.org/wiki/Interpretation_(logic), модели, семантические домены).

Речь лишь про встроенный тип int/float.

Сделай block не локальным, и код будет находится в другом месте.

Т.е. можно 2+(3*5), а можно (2+3)*5.

Ты как-то в сторону и на частности опять. Код не будет нигде находиться — см. A. выше. Но если берёшь B., то не путай и пойми простую вещь — терму S не соответствует CPU-терм (в ситуации к конкретно написанным (Inter-терм) и скомпилированным в конкретный CPU-терм интерпретатором), ему соответствует конкретный пробег CPU-машины/интерпретатора. Попросту говоря, block не будет в другом месте (это же тоже локально), он будет кусками размазан где попало, то есть это не конкретные инструкции, а нетривиальные отношения на них — вытащить их во что-то вменяемое не тривиально, поэтому компиляция отличается от интерпретации.

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

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

вот «код самого интерпретатора» и есть выход.

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

Ок, напишу

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

зачем тебе такой транслятор?

Это пример.

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

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

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

И что?

дык есть сопоставление. В любом интерпретаторе.

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

в таком случае, выполнить её на IA-32/amd64 тоже невозможно.

Возможно. Выполняют ведь.

да, конечно.

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

да, конечно.

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

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

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

Кстати

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 на пассах).

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

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

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

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? При чем тут вообще твоя сишка?

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

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

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

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

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

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

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

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

Где ты там увидел рекурсию вообще?

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

Вот беда - у нас цикл бесконечный!

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

не принципиально. Когда транслятор зацикливается, то если он компилятор, то он считает данный цикл обработанным, и переходит к следующему. Если это тупой интерпретатор, то он опять обрабатывает этот цикл. Сегодня таких интерпретаторов не бывает. Сейчас интерпретатор как и компилятор обрабатывает _весь_ цикл, а уж потом его исполняет, когда полностью до конца распарсит.

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

Интерпретатор делает также, однако этот код никуда не пишет, а просто выполняет.

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

это особенности реализации. Команда HLT вообще не имеет отношения к алгоритмам.

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

это верно только для тупых интерпретаторов, которые выполняют по одной команде за один свой цикл.

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

это тоже неверно. Например bash откажется выполнять цикл, в котором нет done. Даже не начнёт. Что доказывает тот факт, что bash сначала транслирует цикл, а уже потом его выполняет. Как и компилятор.

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

что, попроще никак не придумать? Думаешь я тебе лютую ☣ написать не смогу, которую тебе будет не распарсить?

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

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

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

зачем, если там тоже самое?

И там не может быть ничего другого, ибо этот кусок == результат трансляции одного и того же.

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

ой, а можно подумать, что push умеет заталкивать в стек только предварительно вычисленные константы! ВНЕЗАПНО: она когда-то вообще константы не умела, а только регистры. А что-бы сделать из регистра с 123 регистр 124 не нужен специальный код. Достаточно одной команды INC на любое число.

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

Нет, это не так для любого языка с евалом. Ладно там всякие лиспы, пехепе с джаваскриптом для тебя тоже не существует?

зачем, если там тоже самое?

Затем, что там НЕ то же самое.

ой, а можно подумать, что push умеет заталкивать в стек только предварительно вычисленные константы! ВНЕЗАПНО: она когда-то вообще константы не умела, а только регистры. А что-бы сделать из регистра с 123 регистр 124 не нужен специальный код. Достаточно одной команды INC на любое число.

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

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

а у тебя _вообще_ нет опыта разработки транслятора с нуля, от и до. Ты умеешь только придумывать AST, и вставлять их в чужую реализацию. Потому ты и не понимаешь, как эти твои AST работают на реальном железе. Т.е. ты как блондинка за рулём: умеешь руль крутить, умеешь педали нажимать, но если хоть одна гайка открутиться, то тебе остаётся только плакать и звонить в СТО. За то ты отлично и лучше меня знаешь, как проехать в фитнес-центр своего Мухосранска. А я — да, ламо. И Мухосранска не знаю.

Но действие то, одно и тоже - вывод символа. Причем здесь бесконечность?

он думает, что рекурсия == бесконечный и не сворачиваемый код.

он думает, что рекурсия

Рекурсия есть только в твоих фантазиях. И, еще раз, не любая рекурсия сворачивается в цикл. С рекурсией можно сделать irreducible флоу-граф. Он не сворачивается в цикл.

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

нет, не надо. Точнее он у нас уже есть. Смотри: у тебя есть функция foo(const char*s), которая умеет обрабатывать твой ЯП (не важно как, исполнять/компилировать). Там нет eval. Дык в чём проблема? Если у тебя в s встретился eval, просто выполни foo(то_что_в_eval). В машинном коде есть такая команда, а именно CALL для x86.

Я так и не увидел проблемы.

нет, не надо. Точнее он у нас уже есть.

Нету. Откуда он возьмется?

Дык в чём проблема? Если у тебя в s встретился eval, просто выполни foo(то_что_в_eval). В машинном коде есть такая команда, а именно CALL для x86.

Ну да, именно так оно и работает. Но это ничего не меняет.

Я так и не увидел проблемы.

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

То есть в твоем коде был цикл. Просто ты его записал в виде рекурсии.

в твоём коде есть eval, а это и есть рекурсия самого компилятора/интерпретатора. Т.е. цикл. Да, что-бы сделать хороший, годный eval, тебе придётся тащить весь компилятор/интерпретатор с собой и со своим кодом. Потому в C/C++ нет такого «хорошего и годного eval».

Итерации никогда не повторяются (т.к. в машкоде разные константы).

кто сказал, что это константы? Это для printf они константы, а для main это одна и та же переменная i, которая постоянно инкрементируется.

как видишь на каждом шаге генерируется свой код.

Язык: racket

и что? Тупой интерпретатор не осилил понять, что это цикл? Ну выкинь его на помойку. Такой код даже первоклассник свернёт в цикл.

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

дык ты начал с push i/printf. Я тебе и объясняю, что раз ты написал push, то будь любезен написать pop. Т.к. printf этого не сделает сама.

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

разворот рекурсии в цикл? Да легко: call на саму себя это и есть аналог jmp на саму себя, если допустить бесконечность стека. И любая рекурсия это тоже цикл, только в собственном локальном контексте.

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

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

контрпример?

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

а что по твоему eval, как не рекурсия?

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

Нет.

контрпример?

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

даже bash делает. Ну а твоя ракета — увы, из 70х годов прошлого века. Выполняет по одной команде, тупо, как QBASIC из Windoows95.

и что? Тупой интерпретатор не осилил понять, что это цикл?

_ни один_ интерпретатор не осилит понять, что это цикл.

Такой код даже первоклассник свернёт в цикл.

Первоклассник - свернет. А вот компилятор/интерпретатор - не свернет, т.к. это алгоритмически неразрешимая задача. Такие дела.

Для того, чтобы было проще, видоизменим несколько задачу. Пусть у нас ест ф-я pi-n, которая принимает i и возвращает i-й знак десятичного представления числа пи. И пусть у нас есть 10 разных ф-й, которые принимают число и возвращают некоторый список, который представляет define-форму. Теперь делаем так:

(for ([i (in-naturals)])
    (eval ((eval (string->symbol (pi-n i))) i))
    (x))

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

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

Вот беда - у нас цикл бесконечный!

если ты Бог, и будешь жить вечно, то разве тебе сложно найти/сделать бесконечную память для бесконечного цикла?

даже bash делает.

Не делает. Знаешь, я могу понять, когда люди прост врут, но какой смысл врать глупо - когда тебя любой сразу уличит во лжи? Перестань так делать.

Т.к. printf этого не сделает сама.

Кто тебе сказал, что не сделает?

разворот рекурсии в цикл? Да легко: call на саму себя это и есть аналог jmp на саму себя, если допустить бесконечность стека. И любая рекурсия это тоже цикл, только в собственном локальном контексте.

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

контрпример?

Любой irreducible граф.

если ты Бог, и будешь жить вечно, то разве тебе сложно найти/сделать бесконечную память для бесконечного цикла?

Извини, но в машине тьюринга нету актуально бесконечной памяти :(

Когда транслятор зацикливается

Трансляторы не зацикливаются. И да, в этих вопросах ты точно теоретик-кун :) Ну то есть ты даже не представляешь как циклы компилируются на уровне манипуляций которые компилятор производит — апостериори только смотришь на вход и выхлоп. Посмотри хотя бы http://llvm.org/docs/tutorial/LangImpl5.html#for-loop-expression.

Сегодня таких интерпретаторов не бывает. Сейчас интерпретатор как и компилятор обрабатывает _весь_ цикл, а уж потом его исполняет, когда полностью до конца распарсит.

Ты путаешь, но подожди — я тебе ниже вопрос задам.

транслятор ... Если это тупой интерпретатор

Книжек не читай @ свои определения придумывай :/

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

Ну, допустим, компилятор переводит — можно и даже нужно результат сохранять, так как это и есть назначение компилятора. Интерпретатор — нет, какое нафиг «код никуда не пишет», если у него нет никакого кода, только выполнение (а это назначение интерпретатора).

это особенности реализации. Команда HLT вообще не имеет отношения к алгоритмам.

ЩИТО? L ::= (PLS | DBL | JMP Number | HLT)* — грамматика языка в вопросе, изволь интерпретировать HLT как следует и компилировать так же.

это верно только для тупых интерпретаторов, которые выполняют по одной команде за один свой цикл.

Это верно всегда.

это тоже неверно. Например bash откажется выполнять цикл, в котором нет done. Даже не начнёт. Что доказывает тот факт, что bash сначала транслирует цикл, а уже потом его выполняет. Как и компилятор.

Это тоже верно, кроме одного слова «один», тут имелся в виду мой конкретный пример (у него один проход, вообще — не обязательно).

И ты опять люто путаешь (про bash), смотри ниже вопрос.

я только про них и говорю, а не про какие-то лютые абстракции, как ты.

Тогда давай вопрос тебе:

У реализаций .NET, JVM и любых современных (продвинутых!) интерпретаторов обычно есть две трансляции и две интерпретации, то есть четыре _разных_ вещи, назови их.

Сегодняшние реальные™ компиляторы сначала транслируют код, а потом его уже исполняют.

Компиляторы типа GCC транслируют код, ничего они потом его не выполняют.

А не «по одной команде», как ты почему-то считаешь

С чего ты взял вообще что я как-то «считаю»? Я привожу простейший пример и про него говорю (потому что ты даже тут не понимаешь). Тут нечего считать. И это

что, попроще никак не придумать?

Чуть посложней пример, но ты не доволен. Что конкретно не понятно? Интерпретатор типизированного лямбда-исчисления с числами и арифметикой написанный на языке в котором есть функции, может даже на C++ можно один в один переписать. И как его расширить до компилятора с аллокацией регистров и оптимизациями выражений?

(видимо древних книжек начитался)

Я дал три ссылки на книги про компиляторы — почему они древние и какие нужно читать вместо, в студию.

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

Нет, это не так для любого языка с евалом. Ладно там всякие лиспы, пехепе с джаваскриптом для тебя тоже не существует?

они тоже сначала транслируют(циклы например), а потом уже исполняют.

они тоже сначала транслируют(циклы например), а потом уже исполняют.

Нет :(

Проверь уже и перестань нести чепуху.

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

в данном случае у тебя в рекурсивном коде меняется только одна, как ты говоришь «константа». Потому приведение тривиально: необходимо и достаточно использовать эту «константу» как аргумент функции. Т.е. код получается:

void foo(int i)
{
    printf("%d\n", i);
    foo(i+1);
}

А после TCO for(;; i++) printf("%d\n", i);

в данном случае у тебя в рекурсивном коде меняется только одна, как ты говоришь «константа». Потому приведение тривиально: необходимо и достаточно использовать эту «константу» как аргумент функции.

Это замечательно но мне более интерсен последний пример - где в ациклическом порядке к i применяются еще не определенные на момент компиляции цикла функции.

а у тебя _вообще_ нет опыта разработки транслятора с нуля, от и до.

У меня-то есть.

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

Ты тоже не умеешь и не знаешь. Почему? А я так решил — ты решил что я знаю, а чего нет :)

А после TCO for(;; i++) printf(«%d\n», i);

TCO не так работает. Ну да не суть, мы не о том.

_ни один_ интерпретатор не осилит понять, что это цикл.

это самое обычное TCO. AFAIK скала его по стандарту обязана понимать. А gcc не обязан по стандарту, но всё равно делает (если оно даёт профиит конечно).

Первоклассник - свернет. А вот компилятор/интерпретатор - не свернет, т.к. это алгоритмически неразрешимая задача. Такие дела.

она «неразрешима» только в МТ на бесконечной ленте. В конечном случае — разрешима всегда.

Для того, чтобы было проще, видоизменим несколько задачу. Пусть у нас ест ф-я pi-n, которая принимает i и возвращает i-й знак десятичного представления числа пи.

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

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

потому что само число π точно не определено. Ни в какой момент. Ты можешь только конечный знак узнать за конечное время.

Не делает. Знаешь, я могу понять, когда люди прост врут, но какой смысл врать глупо - когда тебя любой сразу уличит во лжи? Перестань так делать.

дык возьми и напиши цикл без done, и заставь его выполняться. И сразу увидишь, что это правда, и ни одной итерации выполнено не будет. Bash скажет «нету done, это не цикл, а говно какое-то»

Т.к. printf этого не сделает сама.

Кто тебе сказал, что не сделает?

это стандартные соглашения вызова функций. Делает pop тот, кто сделал push. Мне ещё раз продемонстрировать машинный код?

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

почему именно «портянку», а не исходник, из которого эта портянка получилась?

Любой irreducible граф.

бинарное дерево подойдёт?

Извини, но в машине тьюринга нету актуально бесконечной памяти :(

бесконечная лента уже не актуальна?

это самое обычное TCO.

При чем тут TCO? Тебя видимо, смутило, что там луп вызывается? Ну перепиши без лупа с for, это несущественно.

она «неразрешима» только в МТ на бесконечной ленте. В конечном случае — разрешима всегда.

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

НЕТ такой функции, и быть не может

Конечно, есть. Но, см. выше - даже если мы предположим, что нету, и ты будешь хуячить свой хитрый перебор - то ничего не меняется. Ведь мы точно знаем, что реальные интерпретаторы ТАК НЕ ДЕЛАЮТ.

Ты можешь только конечный знак узнать за конечное время.

А мне ничего другого и не надо. Только узнавать конечный знак за конечное время. На каждой итерации. И никаких проблем.

бесконечная лента уже не актуальна?

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

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

дык возьми и напиши цикл без done, и заставь его выполняться. И сразу увидишь, что это правда, и ни одной итерации выполнено не будет. Bash скажет «нету done, это не цикл, а говно какое-то»

И как это опровергает мои слова? Ну проверяет bash наличие done, и что?

Мне ещё раз продемонстрировать машинный код?

Машинный код чего? Твоих фантазий из сишки? Не надо, они не имеют отношения к разговору. Если мне надо будет для моей вм, чтобы был pop внутри функции - то он будет внутри функции.

почему именно «портянку», а не исходник, из которого эта портянка получилась?

Ну это и есть исходник. Портянка с кучей goto.

бинарное дерево подойдёт?

Нет, это reducible граф.

Трансляторы не зацикливаются. И да, в этих вопросах ты точно теоретик-кун :)

зацикливается. Например bash зацикливается на done, который передаёт управление на заголовок цикла. Если done не будет, то bash ни единой итерации не сделает.

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

Интерпретатор — нет, какое нафиг «код никуда не пишет», если у него нет никакого кода, только выполнение (а это назначение интерпретатора).

«выполнение» это и есть машинный код. Ничего другого выполнять нельзя по определению.

ЩИТО? L ::= (PLS | DBL | JMP Number | HLT)* — грамматика языка в вопросе, изволь интерпретировать HLT как следует и компилировать так же.

HLT не относится к алгоритму, а относится к твоей реализации. Это «конечная точка из которой нет выхода». Дели на ноль сам.

У реализаций .NET, JVM и любых современных (продвинутых!) интерпретаторов обычно есть две трансляции и две интерпретации, то есть четыре _разных_ вещи, назови их.

я на собеседовании? Тогда встречный вопрос к тебе: какого цвета мой холодильник? Не знаешь? Следующий!

Компиляторы типа GCC транслируют код, ничего они потом его не выполняют.

интерпретаторы сами тоже ничего не выполняюют, а делегируют процессору выполнение(или LLVM).

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

Почему «по-этому»? Не существует такого момента, в том и дело.

Проверь уже и перестань нести чепуху.

вчера уже проверял. Мне для маздайщиков скриншот делать?

вчера уже проверял.

Зачем ты снова врешь?

Мне для маздайщиков скриншот делать?

Так ведь не сделаешь.

Это замечательно но мне более интерсен последний пример - где в ациклическом порядке к i применяются еще не определенные на момент компиляции цикла функции.

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

А после TCO for(;; i++) printf(«%d\n», i);

TCO не так работает. Ну да не суть, мы не о том.

вот как раз так оно и работает в итоге в данном конкретном случае. Выше я приводил пруф, с машинным кодом, в котором ты и можешь видеть этот цикл, из факториала. Тебе отмотать?

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

Замечательно. Остается вопрос:

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

Явно же откуда-то возможно, если интерпретатор является транслятор и программу транслирует?

вот как раз так оно и работает в итоге в данном конкретном случае.

Нет, не так.

Выше я приводил пруф, с машинным кодом, в котором ты и можешь видеть этот цикл, из факториала. Тебе отмотать?

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

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

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

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

ну если пользоваться знаниями почерпнутыми из книжек 70х — да.

А мне ничего другого и не надо. Только узнавать конечный знак за конечное время. На каждой итерации. И никаких проблем.

и в чём твоя проблема? 10 знаков, 10 кодов. Запиши свои 10 кодов и получи желаемое.

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

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

ну если пользоваться знаниями почерпнутыми из книжек 70х — да.

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

и в чём твоя проблема? 10 знаков, 10 кодов. Запиши свои 10 кодов и получи желаемое.

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

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

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

плохо у тебя. Если у нас есть лента длинной l, мы для решения задачи можем приклеить к ней конечный кусок n, и решить задачу. Ну и пофиг, что n=2^l. Да хоть l!.

плохо у тебя.

Да нет, все хорошо.

Если у нас есть лента длинной l, мы для решения задачи можем приклеить к ней конечный кусок n, и решить задачу. Ну и пофиг, что n=2^l. Да хоть l!.

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

зацикливается. Например bash

bash целиком не транслятор, а интерпретатор.

Если ты не заметил, то общепринятая терминология это языковой процессор — транслятор ИЛИ интерпретатор, интерпретатор — НЕ транслятор, трансляторы — компиляторы, декомпиляторы, ассемблеры, дисассемблеры и т.д.

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

«выполнение» это и есть машинный код. Ничего другого выполнять нельзя по определению.

У тебя машкод головного мозга, надо как-то лечить :)

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

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

HLT не относится к алгоритму, а относится к твоей реализации. Это «конечная точка из которой нет выхода». Дели на ноль сам.

Мы написали интерпретатор и компилятор языка в котором есть HTL, вместо с DBL, PLS и JMP — четыре инструкции. Конечно, они имеют отношение самое прямое.

Но можно обобщить тезис — интерпретаторы зацикливаются (как в том — JMP зацикливает, HLT прерывает), трансляторы — нет (в компиляторе того примера JMP ничего не зацикливает, HLT ничего не прерывает).

я на собеседовании? Тогда встречный вопрос к тебе: какого цвета мой холодильник? Не знаешь? Следующий!

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

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

Вот опять. Ответь на вопрос про четыре вещи.

И ты сказал, что компиляторы что-то там выполняют, то есть ты имел в виду, что МЫ выполняем их выхлоп на CPU? Это ок. Но сами они ничего не выполняют.

(или LLVM).

Зачем LLVM? Причём тут LLVM вообще?

Доку по ссылке про циклы-то прочитал?

Ну проверяет bash наличие done, и что?

а то, что когда bash увидит done, цикл будет полностью определён, а значит будет возможность его компиляции. Сделать «бесконечную портянку» у тебя не получится, т.к. цикл конечен и определён однозначно. Только на твоей ракете такое говно получается.

Не имеет отношения — VM работает на любой архитектуре, железной реализации, ты можешь хоть на бумажке её выполнять, никаких интелов.

Я уже говорил ему про выполнение на бумажке. Ответ был ожидаем - «ололо борщевики, посчитай мне факториал гугола набумажке!».

Ну это и есть исходник. Портянка с кучей goto.

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

бинарное дерево подойдёт?

Нет, это reducible граф.

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

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

Почему «по-этому»? Не существует такого момента, в том и дело.

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

AFAIK скала его по стандарту обязана понимать

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

а то, что когда bash увидит done, цикл будет полностью определён, а значит будет возможность его компиляции.

С чего ты взял? Из того, что баш проверяет наличие done совершенно никак возможность трансляции не следует. Racket, например, проверяет связанность переменных внутри модуля, и что?

Сделать «бесконечную портянку» у тебя не получится, т.к. цикл конечен и определён однозначно.

Конечно, получится, евал же в баше есть. Можно сделать такой же пример, как в Racket, и будет то же самое.

Он не врёт, просто путает /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?

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