Предлагаю читателям Хабра "эзотерический" язык программирования, обобщающий нормальные алгоритмы Маркова (НАМ) и полусистемы Акселя Туэ (semi-Thue systems). В языке есть возможность интерактивного ввода и вывода, выбора поиска замены подстрок с начала, конца строки или случайным образом, условного рекурсивного вызова одного блока подстановок из другого, а также условного перехода между блоками. Это позволяет совмещать подстановку строк с элементами императивного и даже функционального программирования, а также исследовать недетерминированные алгоритмы.

Интерпретатор написан под Линуксом на языке Common Lisp, который я считаю одним из самых мощных и удобных, в том числе для экспериментальногого программирования. При желании большого труда не составит переписать его на любом популярном языке: например, сделать онлайновую версию в Javascript. Просто для запуска программ Лисп знать практически не нужно: достаточно инсталлировать любую версию Common Lisp и ввести нужный файл парой простых функций. Скачать репозиторий интерпретатора Marthue можно здесь.

Хотелось бы поделиться с читателями Хабра довольно необычной разработкой: настоящим компьютером, сделанном в виде клеточного автомата, действующего по простому правилу Fireworld2 с четырьмя состояниями клеток. Текущая базовая версия компьютера называется "Ижора 1". Еще с 1950-х годов существует такая традиция: давать компьютерам географические названия.

Паттерн, состоящий из более 6 миллионов клеток, содержит 256 килобайт памяти и снабжен монохромным экраном 128x64 пикселей, отражающим состояние экранного раздела ОЗУ, примерно как в ZX Spectrum и других популярных исторических моделях персональных компьютеров. Программы можно писать на ассемблере, компилировать в машинный код, тестировать на эмуляторе и вводить специальной утилитой в сам клеточный автомат. Другая утилита позволяет сохранять текущее состояние компьютера. Для запуска компьютера необходима программа Golly - лучшая на сегодня площадка для подобного рода исследований.

Ассемблер и эмулятор написаны на языке Common Lisp, скрипты для ввода программ в сам клеточный автомат и сохранения его состояния - в Python. Компьютер имеет 32-битную архитектуру и на данный момент в нем все один регистр и одна операция: вычитание с условным переходом в случае отрицательного или нулевого результата (Subleq). Несмотря на примитивность такой модели, давно доказана ее универсальность. Существует даже операционная система Dawn OS, написанная для эмулятора Subleq-процессора.

Итак, суммируем: виртуальный компьютер с экзотической моделью программирования и ресурсами уровня древних ПК 1980-х, исполняющий всего около 10 операций в секунду, требующий современный компьютер с несколькими гигабайтами памяти (рекомендуемый минимум - 8 гигабайт), с эмулятором и ассемблером на Лиспе. Зачем и кому это нужно? Очень краткий ответ: ради хака и ретрокомпьютинга. Ниже - более подробно.