Я с радостью признаю, что мои знания Лиспа крайне минимальны. Однако я очень интересуюсь языком и планирую серьезно заняться им в ближайшем будущем. Мое понимание этих вопросов, несомненно, ошибочно, поэтому, если я скажу что-то явно неправильное, пожалуйста, прокомментируйте и исправьте меня, а не голосуйте против.
Истинно гомоиконические и самомодифицируемые языки
Я ищу примеры языков программирования, которые поддерживают как гомоиконность (код имеет то же представление, что и данные), так и неограниченное самомодификация (неограниченное означает, что вы можете изменить каждый аспект своего запущенного кода, а не просто испускать новый код или изменение указателей / делегатов функций.)
Я нашел только три примера, которые соответствуют этим критериям:
- Машинный код. Гомоиконично в том смысле, что все есть числа. Неограниченно модифицируемый, поскольку он включает указатели, которые можно использовать для управления любым адресом памяти, независимо от того, содержит ли этот адрес код или данные.
- Мальболге. Те же рассуждения, что и машинный код. Каждая инструкция модифицируется после выполнения
- ДНК. Не язык программирования, но все же интересно. Он не самомодифицируется в том же смысле, что и машинный код; Где фактические инструкции + данные изменены на месте. Однако он самовоспроизводится и может видоизменяться / развиваться в соответствии со своим предыдущим состоянием (с такими побочными эффектами, как радиация, которые время от времени его портят). В любом случае это всего лишь косвенный способ самомодификации. Короче говоря, ДНК может самомодифицироваться, но это происходит за счет воспроизведения себя во всей своей полноте вместе с соответствующими мутациями. Физическая цепочка ДНК «неизменна».
Почему Lisp нет в этом списке
Лиспа нет в этом списке, потому что мне кажется, что Лисп только почти гомоиконный и поддерживает только ограниченную самомодификацию. Вы можете сделать что-то вроде
(+ 1 2 3)
который будет делать то же самое, что и
(eval '(+ 1 2 3))
В первой версии (+ 1 2 3)
- это необработанный код, а во второй версии - это данные. Допуская истинность этого утверждения, можно утверждать, что Lisp даже не гомиконичен. Код имеет то же представление, что и данные, в том смысле, что они оба являются списками / деревьями / S-выражениями. Но тот факт, что вы должны явно указать, какие из этих списков / деревьев / S-выражений являются кодом, а какие являются данными, мне кажется, говорит о том, что Lisp в конце концов не гомиконичен. Представления очень похожи, но они отличаются крошечными деталями, которые вы должны сказать, имеете ли вы дело с кодом или данными. Это ни в коем случае не плохо (на самом деле все остальное было бы безумием), но подчеркивает разницу между Лиспом и машинным кодом. В машинном коде вам не нужно явно указывать, какие числа являются инструкциями, какие - указателями, а какие - данными. Все является просто числом до тех пор, пока на самом деле не потребуется интерпретация, и тогда это может быть любое из этих значений.
Это еще более веский довод против неограниченной самомодификации. Конечно, вы можете взять список, представляющий некоторый код, и манипулировать им. Например изменение
'(+ 1 2 3)
to
'(+ 1 4 3)
А потом прогоняешь через eval
. Но когда вы это делаете, вы просто компилируете код и запускаете его. Вы не изменяете существующий код, вы просто создаете и запускаете новый код. C # может делать то же самое, используя деревья выражений, даже в менее удобном формате (что возникает из-за того, что код C # имеет другое представление по сравнению с его AST, в отличие от Lisp, который является собственным AST ). Можете ли вы взять весь исходный файл и начать изменять весь исходный файл во время его выполнения, при этом изменения, внесенные в исходный файл, будут влиять на поведение программы в реальном времени?
Если нет способа сделать это, Lisp не является ни гомиконным, ни самомодифицирующимся. (Чтобы отложить спор по поводу определений, Лисп не является гомоиконным или самомодифицирующимся в той же степени, что и машинный код..)
Способы сделать Lisp гомоиконным / неограниченно самомодифицируемым
Я вижу 3 возможных способа сделать Лисп таким же гомоиконным / самомодифицируемым, как машинный код.
- Архитектура, отличная от фон-Неймана. Если бы кто-нибудь мог изобрести какую-нибудь удивительную гипотетическую машину, в которой нижний уровень представления программ - это AST, который может выполняться напрямую (дальнейшая компиляция не требуется). На такой машине AST будет представлять как исполняемые инструкции, так и данные. К сожалению, проблема не будет решена, потому что AST по-прежнему должен быть кодом или данными. Наличие функции eval этого не меняет. В машинном коде вы можете переключаться между кодом и данными сколько угодно. В то время как с eval и Lisp после того, как вы «превратили» некоторый список из данных в код и выполнили его, нет никакого способа вернуть этот список как данные снова. Фактически, этот список исчез навсегда и был заменен его значением. Нам будет не хватать чего-то важного, а именно указателей.
- Ярлыки списков. Если бы требовалось, чтобы у каждого списка была уникальная метка, можно было бы выполнить непрямое самомодификацию, запустив функции для списка с заданной меткой. В сочетании с продолжениями это, наконец, позволило бы реализовать самомодифицирующийся код в том же смысле, в каком он есть в машинном коде. Этикетки эквивалентны адресам памяти машинного кода. В качестве примера рассмотрим программу на Лиспе, в которой верхний узел AST имеет метку «main». Затем внутри main вы можете выполнить функцию, которая принимает метку, целое число, атом и копирует атом в список с меткой, соответствующей метке, предоставленной функции, по индексу, заданному целым числом. Затем просто позвоните с текущим продолжением на main. Итак, самомодифицирующийся код.
- Макросы Лиспа. Я не нашел времени, чтобы понять макросы Лиспа, и на самом деле они могут делать именно то, о чем я думаю.
Пункт 1. в сочетании с 2. приведет к полностью самомодифицирующемуся Лиспу. При условии, что описанная волшебная машина на Лиспе может быть произведена. 2. сам по себе может создать самомодифицирующийся Лисп, однако реализация на архитектуре фон Неймана может быть крайне неэффективной.
Вопросы
- Могут ли какие-либо языки, кроме машинного кода, ДНК и malbolge, выполнять полную само-модификацию, и являются ли они гомоиконными?
- (НЕ утруждайтесь отвечать, если вы сделали tl; dr по приведенному выше тексту). Lisp действительно гомиконный + самомодифицирующийся? Если вы так говорите, можете ли вы процитировать, где именно в моем аргументе я заблудился?
Приложение
Языки с неограниченной самомодификацией, но без гомиконности
- Сборка. В коде используются слова, а не числа, поэтому он теряет гомиконность, но по-прежнему имеет указатели, которые сохраняют полный контроль над памятью и допускают неограниченную самомодификацию.
- Любой язык, использующий необработанные указатели. Например, C / C ++ / Objective C. Тот же аргумент, что и Assembly.
- Языки JIT, которые включают виртуальные указатели. Например, C # /. Net работает в небезопасном контексте. Тот же аргумент, что и Assembly.
Другие концепции и языки, которые могут быть как-то актуальны / интересны: Lisp, Ruby, Snobol, Forth и его метапрограммирование во время компиляции, Smalltalk и его отражение, нетипизированное лямбда-исчисление с его свойством, что все является функцией (что подразумевает, что предполагая, что мы мог бы изобрести машину, которая непосредственно выполняет лямбда-исчисление, лямбда-исчисление будет гомоиконным, а машинный код фон Неймана не будет работать на указанной машине. [И теорема Годельса будет выполнима. Ха-ха, страшная мысль: P])
quote
не имеет большого значения, поскольку ее можно получить с помощью некоторых других и более простых правил оценки, таких как так называемый явный стиль оценки (тот, который лежит в основе упомянутого выше языка ядра), см. [Shu10]. Самомодифицирующееся свойство также не имеет значения, но это простой факт, чтоeval
(как в явном, так и в неявном стилях) не различает идентичность оцениваемого операнда, поэтому не должно быть заметных различий между модификацией на месте и копией + стиранием- by-eval. - person FrankHB   schedule 19.06.2020