Существуют ли программы, которые итеративно пишут новые программы?

Question

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

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

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

Я, вероятно, напишу это в Ruby из-за его простого синтаксиса и динамической компиляции, а затем представлю визуализацию при обработке с использованием ruby-processing.

Я хотел бы знать следующее:

• Есть ли название для этого типа программирования?
• Что в данный момент существует в этом поле?
• Кто является основным донором?
• БОНУС! - Каким образом я могу процедурно присваивать значение выходным программам после компиляции (да / нет)?
  Я, возможно, захочу расширить функциональность этой программы, чтобы генерировать программу на основе параметров, но я хочу, чтобы программа определяла эти параметры посредством запуска программ, которые компилируют и присваивают значение выводу программ. Этот вопрос, вероятно, более сложный, чем разумный для бонуса, но если вы можете придумать простой способ сделать что-то подобное менее чем за 23 строки или одну гиперссылку, пожалуйста, добавьте его в свой ответ.

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

Answer 1

Посмотрите "генетическое программирование".

Редактируйте, чтобы отвечать на комментарии:

@ chris, @Kasturi: true.То, что было описано в OP, - это система вывода грамматики путем попыток грубой силы компилировать какой-то конкретный синтаксис, а затем генерировать новый конкретный синтаксис из грамматики.Если вам обязательно нужно что-то очень близкое к этому описанию ... лучший совет, который я имею, это изучить построение скрытой модели Маркова из конкретного синтаксиса в каком-то языке с очень минимальным синтаксисом.Я бы подумал об использовании минимальной комбинаторной логики (что-то похожее по духу на язык Unlambda).

С другой стороны, генетическое программирование - это техника с некоторой развитой практикой и литературой, и она не является «детерминированной», носкорее случайный процесс.Это также довольно широкий термин - возможно, система ОП представляет собой предельный случай ГП с кроссовером 0% и мутацией 100%.

Answer 2

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

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

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

Классические генетические алгоритмы устанавливают критерии искусственного размножения - программа, которая делает лучшую работу, искусственно выбрана для воспроизведения.

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

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

К сожалению, ваша описанная система все еще имеет несколько искусственных критериев воспроизведения: способность компилировать.

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

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

Совсем нет; это будет считаться «пригодным» для воспроизведения как программа print('k')

Я предлагаю, возможно, использовать каркас из случайно работающих строк программ, имеющих доступ к API, которые могут:

• Чтение / запись на жесткий диск, и вдруг у вас есть программы, которые могут сами записывать случайные строки как программы.
• Удалить / изменить другие файлы на жестком диске; это позволяет программам конкурировать друг с другом. Ваш API может быть спроектирован так, чтобы файл мог быть удален только в том случае, если «сила» (произвольное значение ... возможно, длина символа) программы сильнее, чем у файла.
• Запускать другие сценарии на жестком диске ... возможно, даже те, которые они пишут сами
• Доступ к интернету; на веб-сервер? Возможность писать / прикреплять / отправлять / читать электронные письма?

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

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

Answer 3

Ищите Грамматическое развитие .

Answer 4

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

Например, с учетом реализации

def add(a,b)
  a
end

Вы можете добавить тест

assert_equal 3, Foo.new.add(1,2)

и попросите вашу программу попробовать любую комбинацию методов на a в пределах add (например, a.-(b), a.to_s, a.+(b)), пока один из мутантов не пройдет этот тест и существующие тесты.

Возможно, вы захотите посмотреть на heckle (или Zentest?), Чтобы найти примеры изменения тестируемого кода.

Answer 5

Ранними, но очень интересными работами в этом направлении были «АМ» Дуга Лената (математик) и Эвриско (обобщение АМ).

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

Answer 6

Что было бы оптимальным, это программа что постоянно переписывает и улучшает сам, поэтому мне не нужно

Выполните следующие действия:

1. Написать генератор псевдослучайных чисел в сборке. (реальный режим)
2. Изменить программу так, чтобы она записывала (например) 64 КБ случайных чисел и выполняла FAR JMP для первого байта.
3. (необязательно) Создание драйвера для таймера сторожевого устройства для предотвращения бесконечных циклов
4. Загрузка в загрузочный сектор какого-либо устройства.
5. Получить несколько компьютеров. Настройте так, чтобы в случае тройной ошибки они перезагрузились и загрузились с загрузочного сектора вашего устройства
6. Загрузите компьютеры и подождите несколько десятилетий (или столетий), чтобы они принесли что-то полезное
7. Прибыль!