Development of the LISP Interpreter

Barabash Konstantin Alekseevich Student, Computer Systems Department, Kazan National Research Technical University named after A.N.Tupolev-KAI 420015, Russia, Republic of Tatarstan, Kazan, Bolshaya Krasnaya str., 55 kostyandriy@mail.ru Other publications by this author     Mangusheva Alina Raisovna PhD in Physics and Mathematics Associate Professor, Department of Intelligent Systems and Information Resource Management, Kazan National Research Technological University 420015, Russia, Republic of Tatarstan, Kazan, Karl Marx str., 68 alinamr@mail.ru Obukhova Margarita Yur'evna Senior Lecturer, Department of Computer Modeling and Technosphere Safety, Kazan Innovative University 420111, Russia, Republic of Tatarstan, Kazan, Moskovskaya str., 42 obuhova@ieml.ru

Grigoryan Karen Al'bertovich PhD in Economics Master's student, Department of Intelligent Systems and Information Resource Management, Kazan National Research Technological University 420015, Russia, Republic of Tatarstan, Kazan, Karl Marx str., 68 karigri@yandex.ru

Interpreter ArchitectureThe developed LISP interpreter has three main routines: read, eval, print.

Read procedure:? Responsible for reading input data and processing them – decomposition into atom names, punctuation marks; introduction of new ordinary atoms into the table of atoms and new numeric atoms into the table of numbers; creation of an S-expression representing input data.

(The term "atom" is historical; this term was used by LISP developer John McCarthy.) ^{[1, 2]}? Returns a typed pointer to the created S-expression.

In this case, if the input S-expression is not an atom, the corresponding list structure will be created in the list area.The typed pointer created as the read output is then passed as input to the eval routine.

The eval procedure implements the EVAL function from LISP. eval interprets the calculation of the S-expression indicated by its input, recursively calling itself to calculate subexpressions.The end result is an S-expression, which is created in the list area if necessary, and a typed pointer to this resulting S-expression is returned as output.

If the input S-expression is invalid, eval outputs an error message and proceeds to the point where read is called to get additional input data.If the original input is evaluable, the output of the typed pointer from eval is sent as input for writing.

The print procedure collects the names and punctuation marks necessary to form a text string representing a given S-expression, and prints this string on the terminal (see Figure 1) ^{[3, 4]}.Figure 1. REPL

Thus, the LISP interpreter has the following form.1. Initialization

2. o = read()

3. r = eval(o)

4. print(r)

5. go to step 2

Description of data typesAll data types are represented by a single l_object structure.

This is done to be able to pass any objects as arguments to functions. The structure of the object looks like this:Listing 1. Object structure

The class field defines the class of the object, the class itself has a class data type, and its name is located in the raw.s field.

The vars field is a symbol table and is used to store the object's own variables. In the case of a custom function, two variables are created inside vars: args of type c_list and body of type c_list. For a built-in function or a special form, only args of type c_list are created in vars, and a reference to the function is specified in raw.fn. The symbol table, in turn, is represented by the following l_var structure, which is an ordinary connected list of objects, additionally containing the name field: Listing 2. l_var structure

InitializationBefore the interpreter starts working, all classes, functions and special forms must be initialized.

Initialization of classes occurs by calling the corresponding init method. While standard functions and special forms should be added to env separately. Listing 3. l_var structure

Creating objectsThe class is created using the new_class function, which returns an object of the class.

The function accepts a class name and a class symbol table. For more convenient operation, additional functions have been created that return the necessary objects: list, raw_fn, fn, raw_spec, spec, object, etc. Listing 4. Structure of the c_int class

If the function is written in C, then you can create such an object using raw_fn. The first argument passes the list of arguments received by the function, the second passes the address to it.Listing 5.

Description of the built-in plus method for the c_int classIf more arguments come to the function than in the argument list, then all the others will be automatically written to a variable named “&rest” that stores a list of the remaining variables.

Reading S-expressions

This procedure scans the input string by reading the next character, and returns:

? NULL if the character is equal to “)”;

? the result of parse_list execution if the character is equal to “(”;

? the result of parse_quote execution if the character is equal to “””;

? the result of parse_string execution if the character is equal to “‘“;? the result of executing the parse_token function.

In any other cases, read creates an S-expression ^[5] corresponding to the input string and returns a pointer to it as a result.

Listing 6. S-expression reading function

ExecutionFor execution, the object received after the reading stage is passed to the eval function.

Listing 7. Eval function

Listing 8. Exec functionThe eval function works as follows:

? If eval receives a list, then, according to the rules, eval is called first for the first element of the list.

? If the result is a special form, then eval is not called for the remaining elements, and all subsequent values of the sheet are passed to the form.

? If eval receives a symbol, then an object is searched in the environment by name and returned.

If the object is not found, then a variable is created with the name of the symbol and with an object of type “c_undefined".In all other cases, the object itself is returned.

Garbage collection

Since S-expressions are sent to the LISP interpreter for evaluation, various structures in the list area are created either based on input or based on evaluation.

Most of these list structures are used once. Such structures are called garbage objects. And in the case of nodes in the list area, the garbage nodes are those that are unavailable.We need to find such useless list nodes and put them in the list of free space of the list area so that they can be reused; otherwise we will run out of memory of the list area.

Every time we get zero when recalculating the number of references to an object, this object is deleted from memory.Listing 9. new_object function

The reference counting method is used for garbage collection. It consists in the fact that each object counts the number of pointers to it. When there is a pointer to itself, the counter value increases by 1; when the pointer to itself is removed, the counter value decreases by 1, if the counter value decreases to 0, indicating that there is no pointer to the object, then it can be safely destroyed. This can be represented in the form of the following figure:Figure 2. Illustration of the garbage collector counter operation

The advantage of the link counting algorithm is that the overhead of memory management is distributed over the entire period of the application. Also, the advantage is connected with the fact that when the value of the object's reference counter becomes 0, the system does not need to access blocks located on other pages in the heap.Examples of the work of individual parts of the interpreter

To demonstrate the work of the interpreter, here are some examples.

The listings will indicate the results of the function through comments of the form “;; =>”, after which the return value will be indicated.Here is an example of a factorial function:

Listing 10. Factorial calculation function

An example demonstrating the work in the style of object-oriented programming (OOP). Let's describe the class “Man". The “man” has a method of growing up, which adds 1 to his years, also has a method of changing the level of happiness: Listing 11.

OOP example

Compared to Common lisp, this implementation of the language has a more intuitive syntax. In listing 11, LISP code is contrasted with Common lisp code (listing 12). As you can see, a new user will not have to remember a large number of functions that perform similar actions, which together with dynamic typing adds flexibility. Listing 12.

Comparison. Code on this LISP implementation

Listing 13. Comparison. Common lisp code

You can also redefine functions for use with your own class, for example for mixing colors (listing 14). This will make LISP more user-friendly for the end user. If this LISP implementation did not allow redefining functions, then this would be a problem, because there is no standard in the names and they may differ from library to library. For example, the color addition function could be called by the following names: mixcolor, add-color, color-add, color+, etc. Listing 14. Color class

The following example demonstrates how LISP macros work. Here (listing 15) there is a macro n+, it takes one argument n and declares a global function that takes one argument x and adds n to it. Listing 15.

Macro n+

Approbation of the developed interpreterAs a demonstration of the interpreter's work, we will present the implementation of the game “Life”.

Let's describe the essence of this game.The place of action is a plane marked up into cells, which can be closed, limited or infinite.

Each cell has eight neighbors surrounding it, and it can be in two states: the cell is either “alive” or "dead". The live cells that stand at the beginning of the game are called the first generation. Each subsequent generation is built on the basis of the previous one according to the rules:? for a “dead” cell: if there are at least three living neighbors, then the cell becomes “alive”;

? for a “living” cell: if there are two or three living neighbors, then the cell continues to live, and in other cases dies.

The game stops when there is not a single living cell left on the field.

Despite the simplicity of the rules, a huge variety of forms can arise in the game. Let's define auxiliary functions that implement some existing LISP functions.

The map function calls the function passed to it for all the elements of the sheet. Nth returns the nth element from the beginning of the sheet, while nth-tail returns the nth element from the end. Listing 16.

Implementation of additional functions

The following describes the functions for working with the field. Get returns the symbol located at the x and y coordinates on the field. Alive returns the Boolean value of the cell state. Print prints the field. Count returns the number of living cells around a given cell. Next, depending on the current state of the field, returns the value of the cell for the next move. Listing 17.

Auxiliary functions

The trigger function is a cyclic search through all the cells and revealing their state for the next move. Listing 18. Launch function

Let's define the starting field in the form of a colony (listing 19). This design is called a glider, as it is able to move infinitely far. In this case, since the boundaries of the world are limited, the glider will stop in a corner, where it will acquire a stable shape in the form of a square. Listing 19. Colony 1

Figure 3. Evolution of colony 1

There are forms of colonies that can change endlessly. The simplest example of such a shape is a straight line consisting of three elements in a row. Listing 20. Colony 2

The result of the life of such a colony is a cyclic change of vertical position to horizontal and vice versa.Figure 4. Evolution of colony 2

Conclusion Based on the results of the work done, an interpreter of the LISP language in C was created, simplifying the writing of programs through a simpler syntax with the possibility of overloading functions.

Using the example of the implemented game application “Life”, the language of the developed interpreter demonstrated a more simplified style of writing the program. The paper also gives a message for the development of the LISP language by including language constructs that provide object-oriented programming approaches. 

Thus, the team of authors has created the foundation for the further development of the LISP language and considers the subject of further work on the use and modernization of the interpreter in order to create software in such subject areas as neural networks in the industrial industry ^[6], parallel programming ^[7], information protection ^{[8, 9]}.