Eng Cn Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

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

DOI:

10.7256/2454-0714.2022.4.39289

EDN:

ZAAPXY

Received:

30-11-2022


Published:

30-12-2022


Abstract: The article highlights aspects of the development of the LISP interpreter. Despite the fact that LISP is not the most popular language these days (in the TIOBE index for November 2022, this language is in 30th place), the work done by the authors is relevant. Many popular ideas and software technologies today were first developed using LISP machines. The developed interpreter allows the programmer to avoid defining program elements (functions, classes, etc.) unnecessarily. Also, the development result allows you to run any LISP entity that returns a meaningful result. Modern LISP interpreters do not have the ability to overload functions, which is why users have to memorize a huge number of function names whose actions are of the same type. This greatly complicates the learning process, since you have to look for the names of primitive functions in the documentation. Because of this, most of the potential users drop out of training, returning to modern programming languages, without knowing the possibilities of the LISP language. The article reveals the creation of a LISP interpreter capable of competing with modern programming languages in terms of ease of interaction with objects. The article also suggests an approach that provides a garbage collection mechanism by counting references to objects.


Keywords:

common lisp, lateral lisp, lisp programming, programming languages, C language, garbage collector, interpreter development, lisp interpreter, object-oriented programming, functional programming

This article is automatically translated. You can find original text of the article here.

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

ConclusionBased 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].

References
1. T. Ono and H. Yamazaki, "Design and implementation of the distributed Lisp," Proceedings of IEEE Singapore International Conference on Networks and International Conference on Information Engineering '95, 1995, pp. 195-198, doi: 10.1109/SICON.1995.526045.
2. J. M. Farrow and S. Sevinc, "Modelling tools for a common LISP object system environment," [1991] Proceedings. The Second Annual Conference on AI, Simulation and Planning in High Autonomy Systems, 1991, pp. 219-224, doi: 10.1109/AIHAS.1991.138474.
3. M. A. Fukase and T. Nakamura, "Semiparallel execution of compiled Lisp programs," [1991] Proceedings The Fifteenth Annual International Computer Software & Applications Conference, 1991, pp. 719-724, doi: 10.1109/CMPSAC.1991.170266.
4. S. Asadianfam and H. Kolivand, "Verification of Airport Control Using Lisp Functional Language," 2020 13th International Conference on Developments in eSystems Engineering (DeSE), 2020, pp. 245-250, doi: 10.1109/DeSE51703.2020.9450787.
5. M. Kaufmann and J. S. Moore, "An industrial strength theorem prover for a logic based on Common Lisp," in IEEE Transactions on Software Engineering, vol. 23, no. 4, pp. 203-213, April 1997, doi: 10.1109/32.588534.
6. Gibadullin, R.F., Lekomtsev, D.V. & Perukhin, M.Y. Analysis of Industrial Network Parameters Using Neural Network Processing. Sci. Tech. Inf. Proc. 48, 446451 (2021). https://doi.org/10.3103/S0147688221060046.
7. Gibadullin R.F. Flow-safe calls of controls in enriched client applications // Software Systems and Computational Methods. 2022. 4. pp. 1-19. DOI: 10.7256/2454-0714.2022.4.39029 EDN: IAXOMA URL: https://nbpublish.com/library_read_article.php?id=39029.
8. Gibadullin R.F. Organization of secure data transmission in sensor network based on AVR microcontrollers // Cybernetics and Programming. 2018. 6. pp. 80-86. DOI: 10.25136/2306-4196.2018.6.24048 URL: https://nbpublish.com/library_read_article.php?id=24048.
9. Gibadullin R. F. F. Development of Uniform Formalism of Protection of Point, Linear and Area Objects in Cartography // Bulletin of Kazan State Technical University named after A.N. Tupolev. 2010. . 2. pp. 101-105.

Peer Review

Peer reviewers' evaluations remain confidential and are not disclosed to the public. Only external reviews, authorized for publication by the article's author(s), are made public. Typically, these final reviews are conducted after the manuscript's revision. Adhering to our double-blind review policy, the reviewer's identity is kept confidential.
The list of publisher reviewers can be found here.

The subject of the research in the reviewed material is the development of an interpreter in LISP, a family of programming languages for list processing. The research methodology is based on the study of the literature on the research topic, the description of the structure of the developed interpreter, the visual representation of individual procedures and fragments of program code. Unfortunately, the relevance of the work has not been properly substantiated by the author, so it is not clear which scientific problem the research is focused on. The scientific novelty of the reviewed research, according to the reviewer, consists in the development of an interpreter that simplifies writing programs through simpler syntax with the possibility of overloading functions. The following sections are structurally highlighted in the article: Architecture of the interpreter, Description of data types, Initialization, Creation of objects, Reading S-expressions, Execution, Garbage collection, Examples of the work of individual parts of the interpreter, Approbation of the developed interpreter, Conclusion, Bibliography. The author demonstrates the functioning of the developed interpreter using the example of the implementation of the game Life, provides a description of the implementation of additional and auxiliary functions, launch functions, glider, talks about the cyclic change of vertical position to horizontal and vice versa in the described forms of colonies. The bibliographic list includes 9 sources publications of foreign and domestic scientists on the topic of the article, to which there are targeted links in the text confirming the existence of an appeal to opponents. A number of comments should be made on the submitted material. Firstly, there is an abbreviation in a foreign language in the title of the article, which may not be known to all potential readers of the journal. Secondly, the text of the article does not reflect clear formulations of the purpose and objectives of the study, the tasks to be solved, the subject and object of the study, as well as the results obtained, their novelty and practical significance. Thirdly, the article lacks an introduction, without which the reader will not understand the relevance of the research, the degree of elaboration of the problem, the methodological apparatus used by the author in the research process. Without this, the draft publication does not have the outlines inherent in scientific research and cannot be published without appropriate revision. Fourthly, the article makes deviations from the generally accepted rules for the design of illustrations in addition to four figures, 20 fragments of the listing of the program code are given, which in fact are also drawings, but the placement of 24 illustrations in a journal article of generally accepted volume leads to obvious imbalances between the volume of the textual and illustrative parts of the material. Fifth, Figure 4 "Evolution of colony 2" is not displayed in the information system of the journal it is impossible to view and evaluate it. The article corresponds to the direction of the journal "Software Systems and Computational Methods", may arouse the interest of readers after revision in accordance with the comments made, however, the reviewed material, in the opinion of the reviewer, needs proper structuring and refinement.