Changing the program code during its execution on the example of Common Lisp

Introduction

In my humble opinion, Lisp is a gem among functional programming languages. Despite the fact that this is one of the first high-level languages ​​in history (1958), it still does not cease to amaze. It seems to me that he is so ahead of his time that his hour is just getting ready to come.

So let's try to write a program that will be problematic to create in other languages. As the name of the article suggests, this program will edit its own code as it is executed. To create it, I use Common Lisp , or rather its SBCL interpreter.


Note: if you take a clean SBCL , then it has the property not to flush the stdio stream after each output, I myself use SBCL via Emacs and Slime , there is no such problem there. I have not found an adequate solution yet.
')

How?

Lisp has remarkable properties, among which I would like to mention a very simple syntax and uniformity of code. The cool thing is that any Lisp code is data for it, and many data can be code. In particular, it makes it possible to write auto-applicative (self-applicable) and auto-replicative (self-replicating) functions. A little bit about them is written here ; the information in turn is taken from the book “The World of Lisp” (E. Hyuvenen, I. Seppänen) Volume 1, page 280. For example, a quine , which is both an auto-applicative and auto-replicative function, is written like this:

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

When interpreting, of course, it deduces itself.
Why not write a function that returns not an exact copy of itself, but some new version, which will later be executed again to make an even more mutated version? So do.

Command processor

To make senseless not to shake the air and not to produce spherical horses in a vacuum, let's build a pseudo-practical program. The easiest option that comes to mind is a command processor. The user enters, say, from the keyboard a command, the product of our creativity executes it.

The whole point will be that the source (in all senses) code will be very minimalist. As soon as we feed him to the interpreter, we will no longer return to the immediate work with the REPL . Our program will be continuously implemented and developed (or degraded) over time thanks to our teams.

So, let's start with a function that returns an s-expression, which is the definition of a lambda function , which is the starting code. This lambda function takes, as the only parameter, its source code and gives as a result also some code, which in turn is destined to be executed at the next iteration.

 (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 ) ) ) 

Our initial code does little. He prompts the user, reads an s-expression from the keyboard, if it is a list, then the first element is the name of the command, the rest are its arguments. The out-of-box command processor can handle only one single “code” command. This command takes its first argument and creates a lambda function from it that is applied to program and input. Why so hard? Because eval does its dirty work in a zero lexical environment, which means that the program and input local variables are not available to us, although they may be required. We need to find a way to pass them inside eval; nothing better than lamda with the parameters did not occur to me. I do not exclude that there are more elegant ways. The result of the internal eval is assigned to the variable program. In general, it would be possible to simply assign program the remainder of input, but in this case we will not be able to perform additional functions using the code command. About them later.
The following main function organizes the program operation cycle. All the magic is hidden in it.

 (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) ) ) ) ) ) 

So, the cycle goes until the program (program variable) is not empty. The program on the zero iteration is the result of the start-program function, and on a non-zero iteration we assign to it (the program variable) the result of the function contained in it (the program variable) with the program parameter (again it is the same). This is not a tautology, and it is important to understand how it works before moving on. Understood? Now run in the REPL main and see the prompt:

 CL-USER> (main) $> 

You can create. If you get tired and want to go back to the REPL , all you have to do is execute our only code command in the nil parameter. It will replace the source text with nil, and the cycle will take it as a condition of completion. But we, of course, will not do it yet. From now on, all commands are entered into our running program. I will often omit the "$>" for easy copying.

At the current stage, programming our command processor is difficult and inconvenient. We need to call the code command and pass the whole new source code to it. But there is no way out. Let's create an eval team that will start solving problems. It will allow us to execute any code, in particular, to set new functions.

 (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 ) ) ) 

Perhaps it will issue STYLE-WARNING, it's not scary. Check:

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

Voila, it works!
Spice up the system with three functions (rsubs, rrem, rins). rsubs (Recursive substitution) replaces the recursive old form (the first parameter old) with a new one (the second parameter new) in the form (the third parameter form). rrem (Recursive remove) removes the form (first parameter what) from the form (second parameter form) also recursively. Finally, rins (Recursive insert) inserts next to the form (the first parameter where) the form (second parameter what) in the form (third parameter form), and if the key is given: before t, then the insertion is performed before the form where, otherwise - after it. You have to execute three commands.


You can already add new commands to our processor in a more beautiful way, precisely because code does not simply replace the code with its argument, but executes it beforehand. Add a view command that displays the contents of the program variable. A very useful command for tracking code changes. As you can see, here is the insertion of a new code after the atom cond.

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

We are testing, we should have something like this:


Fine! Now it’s easy for us to add a command that will add commands. Well, how else to call it? The command syntax will be as follows: (add-cmd name-new-command-what-she-will-do) . But here we are in for a spicy situation. The previous time we inserted the code of the new command after the atom cond, because it was the easiest thing. This name is common, and if one more mention of it appears in the text, the insertion will be performed there, which will break the work of those parts that we were not going to touch. You can solve this problem in many ways, for example, enter a unique marker and insert new commands after it. The marker will be an impracticable condition that we add after cond:

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

Is done. Now we will transfer to rins the location of the insert using this marker. Bulkness of the marker does not mean anything, because we will create a team that will know him, and we will no longer need to remember him. By the way, it is impossible for the add-cmd command code to use the definition of a marker, otherwise rins will find and break it. You can try to deceive rins by distorting the marker, but it is much easier to simply put it into a separate external function (rins is not looking for them). The add-command-to-program function takes the program parameter as the first parameter and returns it updated by adding a new command to the command that executes the action action:

 (eval (defun add-command-to-program (program command action) (rins '((eq t nil) 'secret-marker) ;   `((eq command ',command) ,action) ;   program ) ) ) 

We actually create the add-cmd command.

 (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 ) ) 

Wonderful! Now there is nothing easier than adding new commands (the last two of them are better not to run yet):

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

More useful will be the ability to save to a program file and then download it from a file. Define the appropriate save and load commands:

 (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)))) 

Now we can save our work in any text file and download them from there. But it should be remembered that we save and load only the contents of the program; All the functions defined by us with the eval + defun command are not saved in these files, they are stored in the interpreter's memory. It is possible to correct this annoying misunderstanding, but we will not touch it now.

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

Customization

For a change, let's customize our dialogue. For example, add a funny greeting function:

 (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))) ) ) ) 

Now apply them to the shell:

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

It will turn out something like:

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

Finally, I propose to get rid of unnecessary brackets by replacing (read) with something more complicated: we will read the string and frame it with brackets ourselves.

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

Result:

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

Let's take another look at the code again:


With this thing you can have fun as you like! But enough for today.