[AI][Lisp]Самомодификация

Пример программы нужен или что?

Если техника реализации - по разному, например как в Си с подгрузкой динамических библиотек.

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

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

Все-таки лучше почитать литературу какую-нибудь.

если пример программы, то собственно toplevel REPL, например

А причем тут тег AI? Что-то мне подсказывает, что ты хочешь поизвращаться, но не знаешь как.

Например, так (то же самое можно и через eval с предварительной генерацией текста функции):

* (defun define-test1 () (defun test (x) x))

DEFINE-TEST1
* (defun define-test2 () (defun test (x) (+ x 2)))

DEFINE-TEST2
* (fboundp 'test)

NIL
* (define-test1)

TEST
* (test 1)

1
* (define-test2)
STYLE-WARNING: redefining TEST in DEFUN

TEST
* (test 1)
3

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

* (setq *funtable* (list (cons 'a (eval (lambda (x y) (+ x y))))))

((A . #<FUNCTION # {A99012D}>))
* (funcall (cdr (assoc 'a *funtable*)) 1 2)

3

Можно в программе любые лямбды генерировать, отправлять сгенерированное в eval и присоединять к нужному имени либо в alist, либо в hash, например. Генерировать текст нужной функции — это уж сам. А можно сделать просто функцию, откуда дергать все время меняющуюся лямбду, чтобы по сто раз STYLE-WARNING не выдавалось. то есть это будет переопределение внутренности функции, а не самой функции.

>А если по теме, то дело возможно в функциях eval и apply

Ну да. И apply тоже.

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

Студент. Но не к лабам готовлюсь, а дипломный проект делаю. А вопрос простой потому, что я в Лиспе пока не очень силён.

Всё просто

Object subclass: Example [
    | class code sample |

    class:  aString [ class  := aString ]
    code:   aString [ code   := aString ]
    sample: aString [ sample := aString ]

    createSample [
        self class compile: (
            'runSample: aStage [ Transcript << $[ << aStage << $]; cr. %1 ]'
                % {sample}) ]

    createModifier [
        self class compile: (
            'modifyClass [ %1 compile: code ]' % {class}) ]

    run [
        self
            createSample;
            createModifier;
            runSample: 'before';
            modifyClass;
            runSample: 'after' ]]

Eval [
    Example new
        class:  (Smalltalk getArgv: 1);
        code:   (Smalltalk getArgv: 2);
        sample: (Smalltalk getArgv: 3);
        run ]

$ gst -f mutable.st Integer "squared [^self factorial]" "Transcript << 3 squared; cr"
[before]
9
[after]
6
$

А блин. Тред-то про Lisp =)

Ага, не заметил типо.

А есть ещё примеры успешных программ, в которых используется самомодификация? к примеру прикладные программы

А есть ещё примеры успешных программ, в которых используется самомодификация? к примеру прикладные программы

This is the way how most of lisps cook executables: they modify they own memory image with given sources and save this image plus some stub to disk.

Ну, довольно трудно на CL написать программу, которая бы не самодифицировалась так или иначе во время работы :)

Например, cl-closure-template - CL реализация Closures Template (недавно была о них новость), во время исполения парсит шаблоны, транслирует их в лисп функции и компилирует, при необходимости создаёт необходимые пакеты. Это самомодификация?

This is the way how most of lisps cook executables: they modify they own memory image with given sources and save this image plus some stub to disk.

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

Ну, довольно трудно на CL написать программу, которая бы не самодифицировалась так или иначе во время работы :)

я не знаю, плакать или смеяться, но у меня получается)

парсит шаблоны, транслирует их в лисп функции и компилирует, при необходимости создаёт необходимые пакеты. Это самомодификация?

а что в данном случае понимается под шаблонами?

> а что в данном случае понимается под шаблонами?

Ну как что, веб-шаблоны, шаблоны веб-страниц

>Это самомодификация?

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

пнтн, да, интересно

Она модифицирует себя во время исполнения, и, при желании, не один раз. Полученные функции становятся немедленно доступными для исполнения, это обычные полноценные функции.

>Она модифицирует себя во время исполнения

Тогда вопросов нет :)

Полученные функции становятся немедленно доступными для исполнения

Нет, это другое. Так в [почти] любом языке можно :) Это не самомодификация.

Нет, это другое. Так в [почти] любом языке можно :)

Это не самомодификация.

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

Собственно, так бы работала любая IDE или RAD, написанная на Lisp. Загружаешь ядро с этой IDE, что-то там ваяешь (например, кнопки таскаешь), а потом же это все генерирует код и засовывает его в это же самое ядро. Изначально кода нет, а потом он появляется. Что-то поменял, и происходит модификация сгенерированных функций. Да тот же swank так работает. Только он не сам для себя генерирует функции, а принимает их извне. Вот если взять для примера связку climacs+swank, то примерно так и происходит.

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

>Если создание пакетов и функций во время исполнение (и их переопределение) не являются самомодификацией

Это обычное расширение кода в рантайме.

то что же тогда самомодификация?

Когда программа правит свой исходник. Правда, в совсем чистом виде это только в случае чистых интерпретаторов работает. Я такое практиковал только на qbasic (пару раз) и на Форте Forthius (там это было нормой - Форт-система себя конфигурировала в процессе работы)

> Когда программа правит свой исходник.

Стёб?

> Когда программа правит свой исходник.

Исходника может не быть.

Когда программа правит свой исходник.

Ну так и тут практически то же самое. Исходный код функции на Lisp — синтаксически это дерево. Именно дерево программа на Lisp генерит. То есть новый исходный код. Показываю.

Вот есть, предположим, функция, которая в зависимости от какого-то параметра, который этой же программой где-то вычисляется генерирует новый код. Назовем ее gen-function. Предположим даже, что и само значение параметра может быть участником новой функции:

(defun gen-function (parameter)
  (case parameter
    (1 `(lambda (x y) 
	  (let (z)
	    (setq z (/ ,parameter (+ x y)))
	    (1+ z))))
    (2 `(lambda (x y)
	  (- x y ,parameter)))
    (3 `(lambda (x y z)
	  (+ (* x y) z)))))

Понятно, что я могу произвольный код на Lisp генерировать. Пробуем. Обрати внимание, что код даже параметризовался parameter (чисто для иллюстрации). Можно любые брать параметры.

CL-USER> (gen-function 1)
(LAMBDA (X Y) (LET (Z) (SETQ Z (/ 1 (+ X Y))) (1+ Z)))
CL-USER> (gen-function 2)
(LAMBDA (X Y) (- X Y 2))
CL-USER> (gen-function 3)
(LAMBDA (X Y Z) (+ (* X Y) Z))
CL-USER> 

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

(defun unknown-function (parameter &rest args)
  (apply (eval (gen-function parameter)) args))

CL-USER> (unknown-function 1 2 2)
5/4
CL-USER> (unknown-function 2 2 2)
-2
CL-USER> (unknown-function 3 1 2 2)
4

Третья функция имеет три аргумента, в отличие от первых двух. Первый аргумент — это параметр.

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

>Когда программа правит свой исходник. Правда, в совсем чистом виде это только в случае чистых интерпретаторов работает. Я такое практиковал только на qbasic (пару раз) и на Форте Forthius (там это было нормой - Форт-система себя конфигурировала в процессе работы)

А как реализовать самомодификацию на Форте? Форт я знаю.

>А как реализовать самомодификацию на Форте? Форт я знаю.

Самомодификацию практически можно реализовать на любой системе, где есть что-то типа eval. eval может быть интерпретацией текста, выполнением байт-кода, компиляцией в native. Это от системы зависит и не играет принципиальной роли здесь. Если найдешь такую реализацию Форт, программы на которой в runtime смогут выполнить динамически сгенерированный текст на Форте, то и реализуешь.

>Исходника может не быть.

Да. Одна из причин, по которым самомодифицирующиеся программы не на всех языках реализуемы :)

>А как реализовать самомодификацию на Форте?

Ну, вот, из практики. На Forthius, например, была классическая блочная система ввода/вывода. Так вот, параметры конфигурации там прописывались в конкретных блоках на конкретных строках. И при изменении настроек параметры менялись в исходнике. При следующем старте Форт-система грузилась с последними изменёнными параметрами.

может лучше brainfuck для этих целей использовать или lua какой?

Просто определи эту функцию заново, с другим телом. С этого момента функция изменена. Если она уже на стеке, то на стеке остаётся старое тело. Новые вызовы будут обращаться к новому тело. Это так, если функция не inline.

http://www.complang.tuwien.ac.at/anton/euroforth/ef99/gassanenko99b.pdf

Двухфазовое порождение кода: пример применения самомодифицирующегося кода М.Л.Гасаненко

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

Данная статья была опубликована на английском языке в трудах конференции euroFORTH'93. Сейчас, в 2000 году, эта статья публикуется в Интернете как пример (1) применения динамических кодов и (2) разбиения процесса на две фазы.

[Gas93] Gassanenko, M.L. Multi-CFA DOES> : Implementation via Self-Modifying Code. Proc. of the euroFORTH'93 conference, 15-18 October 1993, Marianske Lazne (Marienbad), Czech Republic, 9 p. (http://www.forth.org.ru/~mlg/ef93/Self-Modifying-1993-ru.html)

http://www.forth.org.ru/~mlg/

--

Document: Дипломная работа Гасаненко М.Л. (ф-т ПМ-ПУ СПбГУ, 1992)
Document History:
??.06.1990 - работа сдана в печать, опубликована в 1993 г. как: Гасаненко М.Л. Новые синтаксические конструкции и бэктрекинг для языка Форт.//Проблемы технологии программирования - СПб: СПИИРАН, 1992, с.148-162. (Выпуск сборника планировался в 1991 г., осуществлен в 1993 г.; в рецензиях статей в самом этом сборнике указаны данные Л.:ЛИИАН, 1991.)
??.05.1992 - защищена дипломная работа
02.06.1999 - преобразование в HTML с сохранением особенностей оригинального текста.

(http://www.forth.org.ru/~mlg/BacFORTH-88/BF-diplom.html)

--

Расширение возможностей перебора с откатом (бэктрекинга)
М.Л.Гасаненко mlg@forth.org
Опубликовано как: Гасаненко М.Л. Расширение возможностей перебора с откатом (бэктрекинга) // Информационные технологии и интеллектуальные методы. Выпуск №2. СПб.: СПИИРАН, 1997. С.23-35.

(http://www.forth.org.ru/~mlg/BacFORTH-90/pgasmil1-96.html)

--

P.S. Короче, не совсем «стёб», но и не то, о чём которой писал Крон ))) К тому же, никто не запрещает векторные реализации или MARK-FORGET с догрузкой.

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

Эка невидаль... В лиспе это - совершенно стандартный приём. Так работает, например, cl-ppcre. Пользователь в консоли вводит регексп, создаётся парсер этого регекспа, компилируется в нативный код и исполняется. В некоторых реализациях CLOS в момент переопределения метода родовой функции просматривается всё дерево методов, как оно есть на текущий момент, и пересобирается новое общее тело родовой функции.

векторные реализации

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

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

Не, разные реализации могут заинлайнить код при компиляции. Это право у них никто не отбирает. Но ведь есть (declare/declaim (notinline ...)), которую компилятор по стандарту *не вправе* игнорировать.

notinline specifies that it is undesirable to compile the functions named by function-names in-line. A compiler is not free to ignore this declaration; calls to the specified functions must be implemented as out-of-line subroutine calls.

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