Change the code of the program during its implementation on the example of Common Lisp

Introduction

In my humble opinion, Lisp — the pearl among the languages of functional programming. Despite the fact that this is one of the first in history (1958) high-level languages, it still never ceases to amaze. I think he was so ahead of his time, his hour is still to come.
/ >
So let's try to write a program, which is difficult to create in other languages. As the name of the article, this program will edit their own code as they run. To create it I use Common Lisp, or rather his interpreter SBCL.


note: if you take SBCL, then it is a property not flashit the stdio stream after each output, I use SBCL via Emacs and Slime, there is no such problem. An adequate solution is not found.

How?

Lisp has remarkable properties, among which worth mentioning a very simple syntax and code uniformity. The great thing is that any code in Lisp is data for the same, and a data may be the code. In particular, it gives the opportunity to write autoaplicada (applicable to themselves) and an (reproducing itself) function. A little bit written about them here; information in turn is taken from the book "the World of Lisp" (E. Guvenen, I. Seppanen) volume 1, page 280. For example, Quinthat is both autosplitting, and an function is written like this:

the

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

In their interpretation, of course, removes himself.
Why not write a function that returns an exact copy of himself, and some new version, which subsequently will be executed again to form an even more mutated version? Will do so.

shell

Pointless to not shake the air and not to produce spherical horses in a vacuum, let's build pseudoprotocol program. The easiest option that comes to mind is the command processor. The user enters, say, a keyboard command, the product of our creativity it takes.

The whole point is that the original (in all senses) the code is very minimalistic. As soon as we feed the interpreter, we will not return to direct work with REPLom. Our program will continuously run and develop (or deteriorate) over time, through our teams.

So, let's start with a function that returns the s-expression that is the definition Lamda-funkciithat represents the initial code. This lambda sensor function takes as a single parameter, the source code and gives as result some code, which in turn is destined to be executed on the next iteration.

the

(defun start-program ()
'(lambda (program) 
(princ "$> ") 
(let ((input (read)))
(when (listp input)
(let ((command (car input)))
(cond
((eq command 'code) ; if command = code,
(setf program ; update the program
(funcall ; the result of being  imposed  polzovatel
(eval (list 'lambda '(program input) (cadr input))) 
program input) 
)
)
(t (format t "Unknown command ~A ~%" command))
)
)
)
program
)
)
)

Our initial code little things. It will prompt you for a user, reads from the keyboard s-vyrajenieif it is a list, the first element is the command name, the rest its arguments. The shell out of the box can only handle one command code. This command takes its first argument and creates from it the lambda sensor function is used to program and input. Why so difficult? Because eval does their dirty work in a null lexical environment, so the local variables of the program and input we are not available, although may be required. Need to find a way to transfer them inside eval; nothing better Landy with parameters I did not occur. Don't rule out that there are more elegant ways. The result of the inner eval is assigned to a variable program. In General it would be possible to simply assign the program to the remainder of the input, but in this case we will not be able to perform additional functions when you use code. About them later.

the

(defun main ()
(let ((program (start-program))) ; set the initial program
; loop until the program is empty, i.e. not nil
(loop while program do 
; a kind of try - catch, increases the stability of the program 
; if the step gives the erroneous code
(handler-case 
; assign a variable program execution result of the function, 
; contained in the variable program parameter program
(setf program (funcall (eval program) program))
; in case of error, please report it
(error (c1) (format t "Error! ~A~%" c1) )
)
)
)
)

So, the cycle goes on, until the program (program variable) is not empty. The program is at the zero iteration is the result of the function start-program and non-zero iteration we assign to it (program variable) the result of executing the functions contained in it (variable program), with the parameter program (again she also). It is not a tautology, and it is important to understand how it works before you move on. Understood? Now run in REPLe main and see the invitation:

the

CL-USER > (main)
$> 

It is possible to create. If you get tired and want back in REPL, it is enough to fulfill our only command code parameter is nil. It will replace the original text to nil and the loop will take it as the termination condition. But we certainly are not going to do this so far. From now on, all commands are entered in our running program. I'll often omit the "$> " for ease of copying.

At this stage, the programming of our shell is difficult and uncomfortable. We need to invoke the command code, and upload the new source code as a whole. But there is no escape. Let's create the command eval, which will begin to solve problems. It will allow us to execute any code, in particular to define a new function.

the

(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))) ; NEW
(t (format t "Unknown command ~A ~%" command))
)
)
)
program
)
)
)

Perhaps it will give a STYLE-WARNING, it's not scary. Check out:

the

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

5 $>

Voila, it works!
Tampered with the system using three functions (rsubs, rrem, rins). rsubs (Recursive substitution) recursively replaces the old form (the first parameter old) to the new (second new parameter) in the form (the third parameter form). rrem (Recursive remove) remove the form (the first parameter what) from the shape (second parameter of form) is also recursively. Finally, rins (Recursive insert) inserts the next in a form (where the first parameter) in the form (second parameter what) in the form (the third parameter form), and if the key :before t, then the insert is executed before the form where, otherwise — after. We need to perform three commands.

See three teams

(eval 
(defun rsubs (new old form)
(cond
((atom form) (if (equal old form) new form))
((equal old form) new)
(t (loop for el in form collect (rsubs new old 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 is 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 (what list el) (list el what))
(if (listp el) 
(list (rins where what el :before before))
(list el)
)
)
))
)
)
)

It is already possible to add new commands to our processor more beautiful way, just because code is not just replaces the code in its argument and executes it beforehand. Add the view command, which will print out the contents of the variable program. A very useful command for tracking code changes. As you can see, here is the code after insertion of a new atom cond.

the

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

Test, you should get something like this:

Example output (view)

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

(EVAL (LIST 'LAMBDA '(PROGRAM INPUT) (CADR INPUT)))
PROGRAM INPUT)))
((EQ COMMAND 'EVAL) (EVAL (CADR INPUT)))
(T (FORMAT T "Unknown command ~A ~%" COMMAND)))))
PROGRAM)) 
$> 

Great! Now we easily add teams to add teams. Well, how else to call it? The command syntax would be: (add-name cmd-new-command-that-she-is-doing). But here we will have interesting situation. The last time we inserted the code of the new team after the atom cond, because it was the easiest. The name is common, and if the text will appear in another reference, the insert will fail and there that would disrupt the operation of those parts that we were not going to touch. To solve this problem by many ways, for example, enter a unique token and insert new commands after it. The token would represent an impossible condition, which we will add after cond:

the

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

Ready. Now we will transfer the rins to the location of the inserts with the marker. The bulkiness of the marker means nothing, because we will create a team that will know him, and we will no longer need to remember it. By the way, it is impossible to command code add-cmd used the definition of the marker, otherwise rins will find and will break it. You can try to cheat rins, twisting the marker, but it is much easier just to make a separate external function (rins them not looking). The add-command-to-program takes the first argument the program program, and returns its updated, adding a new command that performs an action is:

the

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

Actually create a add-cmd.

the

(code 
(rins '((eq t nil) 'secret-marker) ; marker inserted after the following
`((eq command 'add-cmd) ; the name of the new add command-cmd
(setf program (add-command-to-program program (cadr input) (caddr input)))
) 
program
)
) 

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

the

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

More useful would be the ability to save to the program file and then downloading it from a file. Determine the appropriate commands save and load:

the

(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 results to any text file and load them from there. But we should remember that we save and upload only the contents of the program; all functions, we defined a command eval + defun, these files are not stored, they are stored in the memory of the interpreter. To correct this unfortunate misunderstanding is possible, but we will not get into it.

the

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

Customisation

For a change do some customization of our dialogue. For example, add fun greetings function:

the

(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 you will use them in a command shell:

the

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

We will get something like:

the

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

Finally, I propose to get rid of unnecessary parentheses, replacing (read) for something a little more complicated: we will read a line and independently frame by its brackets.

the

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

The result:

the

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

Finally, let's take another look at the code:

Final result

Thy bidding, master? view

(LAMBDA (PROGRAM)
(PRINC (GREETING))
(LET ((INPUT
(READ-FROM-STRING (CONCATENATE 'STRING "(" (READ-LINE) ")"))))
(WHEN (LISTP INPUT)
(LET ((COMMAND (CAR INPUT)))
(COND ((EQ NIL T) 'SECRET-MARKER)
((EQ COMMAND 'LOAD)
(SETF PROGRAM
(WITH-OPEN-FILE (STREAM (CADR INPUT))
(READ STREAM))))
((EQ COMMAND 'ADD)
(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. 

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

Article based on information from habrahabr.ru