Изменение кода программы во время ее выполнения на примере Common Lisp

Введение

По моему скромному мнению, Lisp ^[1] — жемчужина среди языков функционального программирования. Несмотря на то, что это один из первых в истории (1958 год) высокоуровневых языков, он по сей день не перестает удивлять. Мне кажется, он настолько обогнал свое время, что его час еще только готовится прийти.

Так давайте попытаемся написать программу, которую проблематично будет создать на других языках. Как следует из названия статьи, эта программа будет редактировать собственный код по мере своего выполнения. Для ее создания я использую Common Lisp ^[2], а точнее его интерпретатор SBCL ^[3].

Примечание: если вы возьмете чистый Emacs ^[4] и Slime ^[5], там этой проблемы нет. Адекватного решения пока не нашел.

Каким образом?

Lisp обладает замечательными свойствами, среди которых хочется отметить очень простой синтаксис и однородность кода. Самое классное то, что любой код на Lisp является данными для него же, и многие данные могут являться кодом. В частности, это дает возможность писать автоаппликативные (применимые сами к себе) и авторепликативные (воспроизводящие себя) функции. Чуть-чуть о них написано здесь ^[6]; информация в свою очередь взята из книги «Мир Лиспа» (Э. Хювёнен, И. Сеппянен) том 1, страница 280. Например, квайн ^[7], который является одновременно и автоаппликативной, и авторепликативной функцией, записывается так:

((lambda (x) (list x (list 'quote x))) 
	'(lambda (x) (list x (list 'quote x))))

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

Командный процессор

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

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

Итак, начнем с функции, возвращающей лямда-функцию ^[8], которая представляет собой начальный код. Эта лямда-функция принимает, как единственный параметр, свой же исходный код и отдает в качестве результата также какой-то код, которому в свою очередь предначертано быть исполненным на следующей итерации.

(defun start-program ()
	'(lambda (program) 
		(princ "$> ") 
		(let ((input (read)))
			(when (listp input)
				(let ((command (car input)))
					(cond
						((eq command 'code)  ; если команда = code,
							(setf program 	 ; то обновим программу
								(funcall     ; результатом того, что ввел пользовтаель
									(eval (list 'lambda '(program input) (cadr input))) 
								program input) 
							)
						)
						(t (format t "Unknown command ~A ~%" command))
					)
				)
			)
			program
		)
	)
)

Наш начальный код мало чего умеет. Он выводит приглашение для пользователя, считывает с клавиатуры s-выражение ^[9], если оно список, то первый элемент — имя команды, остальные — ее аргументы. Командный процессор «из коробки» умеет обрабатывать только одну единственную команду «code». Эта команда берет свой первый аргумент и создает из него лямда-функцию, применяемую к program и input. Зачем так сложно? Потому что eval делает свои грязные делишки в нулевом лексическом окружении, а значит локальные переменные program и input нам не доступны, хотя могут потребоваться. Нужно найти способ их передать внутрь eval; ничего лучше лямды с параметрами мне в голову не пришло. Не исключаю, что есть и более изящные способы. Результат внутреннего eval присваивается переменной program. Вообще можно было б просто присвоить program остаток от input, но в этом случае мы не сможем исполнять дополнительные функции при использовании команды code. О них чуть позже.
Следующая функция main организует цикл работы программы. Вся магия таится именно в ней.

(defun main ()
	(let ((program (start-program))) ; задаем начальную программу
		; цикл, пока программа не пустая, т.е. не nil
		(loop while program do 
			; своеобразный try - catch, увеличивает стабильность программы, 
			; если итерация дает ошибочный код
			(handler-case 
				; присвоим переменной program результат выполнения фукции, 
			        ; содержащейся в переменной program с параметром program
				(setf program (funcall (eval program) program))
				; в случае ошибки, сообщим о ней
				(error (c1) (format t "Error! ~A~%" c1) )
			)
		)
	)
)

Итак, цикл идет, пока программа (переменная program) не пуста. Программа же на нулевой итерации — результат функции start-program, а на ненулевой итерации мы присваиваем ей (переменной program) результат выполнения функции, содержащейся в ней (переменная program), с параметром program (опять она же). Это не тавтология, и важно понять как оно работает, прежде чем двигаться дальше. Разобрались? Теперь запускаем в REPL-е main и видим приглашение:

CL-USER> (main)
$> 

Можно творить. Если надоест и захочется назад в REPL, достаточно выполнить нашу единственную пока команду code в параметром nil. Она заменит исходный текст на nil, и цикл воспримет это как условие завершения. Но мы, конечно, не будем пока этого делать. Отныне все команды вводятся уже в нашу работающую программу. Я буду часто опускать "$> " для удобства копирования.

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

(code
	'(lambda (program)
		(princ "$> ") 
		(let ((input (read)))
			(when (listp input)
				(let ((command (car input)))
					(cond
						((eq command 'code) 
						    (setf program 
						        (funcall 
						            (eval (list 'lambda '(program input) (cadr input))) 
						         program input)))
						((eq command 'eval) (eval (cadr input))) ; НОВОЕ
						(t (format t "Unknown command ~A ~%" command))
					)
				)
			)
			program
		)
	)
)

Возможно, оно выдаст STYLE-WARNING, это не страшно. Проверим:

$> (eval (print (+ 3 2)))

5 $>

Вуаля, работает!
Приправим систему с помощью трех функций (rsubs, rrem, rins). rsubs (Recursive substitution) заменяет рекурсивно старую форму (первый параметр old) на новую (второй параметр new) в форме (третий параметр form). rrem (Recursive remove) удаляет форму (первый параметр what) из формы (второй параметр form) тоже рекурсивно. Наконец, rins (Recursive insert) вставляет рядом в формой (первый параметр where) форму (второй параметр what) в форме (третий параметр form), причем если указан ключ :before t, то вставка выполняется перед формой where, иначе — после нее. Придется выполнить три команды.

(eval 
	(defun rsubs (old new form)
		(cond
			((atom form) (if (equal form old) new form))
			((equal form old) new)
			(t (loop for el in form collect (rsubs old new el)))
		)
	)
)

(eval 
	(defun rrem (what form)
		(cond
			((atom form) (if (equal what form) nil form))
			(t (loop for el in form 
				if (not (equal what el))
				collect (if (listp el) (rrem what el) el)
			))
		)
	)
)

(eval
	(defun rins (where what form &key before)
		(cond 
			((atom form) form)
			(t (loop for el in form append 
				(if (equal el where) 
					(if before (list what el) (list el what))
					(if (listp el) 
						(list (rins where what el :before before))
						(list el)
					)
				)
			))
		)
	)
)

Уже можно добавлять новые команды в наш процессор более красивым способом, как раз благодаря тому, что code не просто замещает код на свой аргумент, а предварительно исполняет его. Добавим команду view, которая выведет нам содержание переменной program. Весьма полезная команда для отслеживания изменений кода. Как видно, здесь происходит вставка нового кода после атома cond.

(code (rins 'cond '((eq command 'view) (progn (format t "---code---") (print program) (terpri))) program))

Тестируем, должно получиться что-то вроде этого:

$> (view)
---code---
(LAMBDA (PROGRAM)
  (PRINC "$> ")
  (LET ((INPUT (READ)))
    (WHEN (LISTP INPUT)
      (LET ((COMMAND (CAR INPUT)))
        (COND
         ((EQ COMMAND 'VIEW)
          (PROGN (FORMAT T "---code---") (PRINT PROGRAM) (TERPRI)))
         ((EQ COMMAND 'CODE)
          (SETF PROGRAM
                  (FUNCALL
                   (EVAL (LIST 'LAMBDA '(PROGRAM INPUT) (CADR INPUT)))
                   PROGRAM INPUT)))
         ((EQ COMMAND 'EVAL) (EVAL (CADR INPUT)))
         (T (FORMAT T "Unknown command ~A ~%" COMMAND)))))
    PROGRAM)) 
$> 

Отлично! Теперь нам несложно добавить команду, которая будет добавлять команды. Ну, как иначе это назвать? Синтаксис команды будет таков: (add-cmd имя-новой-команды что-она-будет-делать). Но тут нас ожидает пикантная ситуация. В предыдущий раз мы вставляли код новой команды после атома cond, потому что это было проще всего. Имя это распространенное, и если в тексте появится еще одно его упоминание, то вставка будет выполнена и там, что нарушит работу тех частей, которые мы не собирались трогать. Решить эту проблему можно многими способами, например, ввести уникальный маркер и вставлять новые команды после него. Маркер будет представлять собой невыполнимое условие, которое мы добавим после cond:

(code (rins 'cond '((eq t nil) 'secret-marker) program))

Готово. Теперь будем передавать в rins местоположение вставки с помощью данного маркера. Громоздкость маркера ничего не значит, ведь мы создадим команду, которая будет его знать, и нам будет уже необязательно его помнить. Кстати, нельзя, чтобы код команды add-cmd использовал определение маркера, иначе rins найдет и поломает его. Можно попытаться обмануть rins, исказив маркер, но гораздо проще просто вынести в отдельную внешнюю функцию (rins по ним не ищет). Функция add-command-to-program принимает первым параметром программу program и возвращает ее обновленной, дополнив ее новой командой command, выполняющей действие action:

(eval
	(defun add-command-to-program (program command action)
		(rins '((eq t nil) 'secret-marker) ; после маркера   
			`((eq command ',command) ,action) ; применим квазицитирование
			program
		)
	)
)

Собственно создаем команду add-cmd.

(code 
	(rins '((eq t nil) 'secret-marker) 		; вставляем после маркера следующее
		`((eq command 'add-cmd)     	; имя новой команды add-cmd
			(setf program (add-command-to-program program (cadr input) (caddr input)))
		 ) 
		program
	)
) 

Замечательно! Теперь нет ничего проще, чем добавить новые команды (две последние из них лучше пока не запускать):

(add-cmd hi (princ "Hi, "))
(add-cmd quit (setf program nil))
(add-cmd reset (setf program (start-program)))

Более полезными окажутся возможности по сохранению в файл программы и последующей загрузки ее из файла. Определим соответствующие команды save и load:

(add-cmd save (with-open-file (stream (cadr input) :direction :output :if-exists :overwrite :if-does-not-exist :create) (print program stream)))
(add-cmd load (setf program (with-open-file (stream (cadr input)) (read stream))))

Теперь мы можем сохранять наши наработки в любой текстовый файл и загружать их оттуда. Но следует помнить, что мы сохраняем и загружаем только содержимое program; все функции, определенные нами командой eval + defun, в этих файлах не сохраняются, они хранятся в памяти интерпретатора. Исправить это досадное недоразумение можно, но мы не будем сейчас этого касаться.

$> (save "1.txt")
$> (load "1.txt")

Кастомизация

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

(eval
	(defun greeting ()
		(let 
			((sentences (vector
				"My life for Ner'zhul. "
				"I wish only to serve. "
				"Thy bidding, master? "
				"Where shall my blood be spilled? "
				"I bow to your will. "
			)))
			(elt sentences (random (length sentences)))
		)
	)
)

Теперь применим их в командном процессоре:

(code (rsubs '"$> " '(greeting) program))

Получится нечто вроде:

I bow to your will. (hi)
Hi, I wish only to serve. 

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

(code (rsubs '(read) '(read-from-string (concatenate 'string "(" (read-line) ")")) program))

Результат:

Thy bidding, master? hi
Hi, Where shall my blood be spilled?

Давайте напоследок еще раз взглянем на код:

Thy bidding, master? view
---code---
(LAMBDA (PROGRAM)
  (PRINC (GREETING))
  (LET ((INPUT
         (READ-FROM-STRING (CONCATENATE 'STRING "(" (READ-LINE) ")"))))
    (WHEN (LISTP INPUT)
      (LET ((COMMAND (CAR INPUT)))
        (COND ((EQ T NIL) 'SECRET-MARKER)
              ((EQ COMMAND 'LOAD)
               (SETF PROGRAM
                       (WITH-OPEN-FILE (STREAM (CADR INPUT))
                         (READ STREAM))))
              ((EQ COMMAND 'SAVE)
               (WITH-OPEN-FILE
                   (STREAM (CADR INPUT) :DIRECTION :OUTPUT :IF-EXISTS
                    :OVERWRITE :IF-DOES-NOT-EXIST :CREATE)
                 (PRINT PROGRAM STREAM)))
              ((EQ COMMAND 'RESET) (SETF PROGRAM (START-PROGRAM)))
              ((EQ COMMAND 'QUIT) (SETF PROGRAM NIL))
              ((EQ COMMAND 'HI) (PRINC "Hi, "))
              ((EQ COMMAND 'ADD-CMD)
               (SETF PROGRAM
                       (ADD-COMMAND-TO-PROGRAM PROGRAM (CADR INPUT)
                                               (CADDR INPUT))))
              ((EQ COMMAND 'VIEW)
               (PROGN (FORMAT T "---code---") (PRINT PROGRAM) (TERPRI)))
              ((EQ COMMAND 'CODE)
               (SETF PROGRAM
                       (FUNCALL
                        (EVAL
                         (LIST 'LAMBDA '(PROGRAM INPUT) (CADR INPUT)))
                        PROGRAM INPUT)))
              ((EQ COMMAND 'EVAL) (EVAL (CADR INPUT)))
              (T (FORMAT T "Unknown command ~A ~%" COMMAND)))))
    PROGRAM)) 
My life for Ner'zhul. 

С этой штукой можно развлекаться сколько угодно! Но на сегодня хватит.

Автор: tirinox

Источник ^[10]