Fatal choice
In my previous article ( en ), I talked about the history of the fifth-generation Japanese computer system project, launched under the ringing of fanfare in 1982 and deceased in 1992, taking logical programming with me. In this article, I will talk about how Prolog was chosen as the language for systems of the fifth generation, instead of the more obvious Lisp. I am interested in the phenomenon of people capable of forming adherents of a language. I hope in this article I can explain it.
About terminology. Logical programming is a method that uses logical sentences in the representation of procedures and data, and performs calculations based on the statements obtained. Prologue is a programming language based on these two ideas. Both language and method played a major role in the systems of the fifth generation.
At the conference, which opened the project, in 1981 Fuchi called logic programming its main programming methodology. On the final in 1992, Furukawa recalled that the team of the Electrotechnical Laboratory (ETL) from Tokyo (which later started the fifth generation systems project) in 1976 had a lot of experience in Lisp, and Prologue was completely unfamiliar with it. In 1976, this was the case with everyone: outside of Marseille, only a couple of institutions knew about Prolog.
Fuchi became interested in logic programming [1] after reading Kawasaki's article [7] in 1974. This probably forced Furukawa to search for the Prologue during his visit to the Standford Research Institute in 1976. He did indeed find the source code on Fortran of the first version of the Prolog interpreter distributed for outside of marseille. In 1974, David H. D. Warren took a copy to Edinburgh. And in 1976, Harry Barrow brought a copy from Edinburgh to the Stanford Research Institute. Warren [1] said: "Harry could not start the system by himself and gave it a copy of Furukawa." In 1976, in Tokyo ETL, Furukawa and several other researchers began experimenting with Prolog. The United States acted as a carrier of the Prolog virus, having themselves avoided infection.
')
As a result of his work at ETL, Furukawa demonstrated several database indexing programs on the prologue. Apparently, the positive results allowed ETL to obtain the prologue implementation for DEC-10 from David H. D. Warren. Furukawa wrote [2] :
For information on the history of the prologue, I turned to the book “The Birth of Prologue” by Alan Kolmeoera and Philip Rossell [3] . The first steps were taken in 1971 by a group led by Colmerour at Aix-Marcel University. After creating several preliminary versions that serve exclusively for processing natural languages, a “final version” was created in 1973. Under the influence of Kawasaki, the logic of sentences became a language, and a certain form of statements served as a procedure call mechanism. This version was the first, called the “Prologue” and used for tasks other than the processing of natural languages. In early 1974, after Warren’s visit to Marseille, a copy of the Prologue came to Edinburgh; and from Edinburgh quickly spread to several European institutions (Budapest, Leuven, Lisbon) and Canada.
From 1974 to 1977 a lot of fascinating experiments were carried out, which continued in Marseilles. Helder Coelho from Lisbon began to assemble programs for the book How to do it on the Prologue. In 1975, Warren began writing the Prolog compiler on the DEC-10 Prolog. When it was completed in 1977, it turned out that a major improvement had been made to the 1973 Marseille interpreter. Warren and his colleagues dared to compare it with the Lisp compiler, which was perfect as a work of art, and got interesting results. Lists were reversed 30-50% faster than Lisp. The result was amazing, because lists are translated into logical terms and are processed in a uniform way, like any other term. Symbolic differentiation (depending on data) was performed from 1.1 to 2.6 times faster than on Lisp. In 1977 Lisp was 18 years old, and Prologue was 6, and only a handful of people worked on its development from 1971 to 1977.
The following examples are, by and large, useless. They are chosen to demonstrate the attractive nature of the Prologue.
Suppose a program for the predicate “move” meaning when writing move (X1, Y1, X2, Y2) that the knight can move from the cage (X1, Y1) to the cage (X2, Y2).
Having the appropriate program, you can ask
which would mean “can a horse go to one of the cells diagonally in one move” and get the answer “No”.
When asked
meaning “can a knight go to the cell diagonally in two moves” we get the answer “Yes”, with all the moves if necessary. The program will be next
Another example. Suppose we have a set of twenty-seven figures contained in the following lists.
with the condition that each of the digits d = 1, .., 9 there are three occurrences of d, where d are separated from each other by d positions. To solve, we need a rather complicated query.
but the program itself is very small and contains only general purpose predicates:
The early history of the prologue seems to me very interesting: only a few people in six years from scratch have developed it into an elegant, powerful and effective language that is included in the Big Four so far. The early history of Lisp is no less entertaining. In the 1950s, McCarthy chose the language for his “ Advisor ” project. Candidates were IPL-V Newela and Simon and the Fortran compiler, developed by the Backus team at IBM. The IPL had the advantage of flexible data structures represented by lists. On the other hand, McCarthy liked Fortran because of its iteration mechanism. Therefore, he began an experiment in creating FLPL (Fortran List Processing Language), a version of the Fortran compiler with support for working with lists. I recall that at that time support for user-defined functions in Fortran was an undocumented property with a long-term implementation, and the function body was limited to one line. Not surprisingly, McCarthy began work on his own list processing language. In November 1958, the interpreter was already working at MIT. Soon it evolved into a language known to us now as Lisp, which was a side effect of working on a project description.
One of the features of the language was its universality: is it possible to calculate everything that is calculated in principle? As a demonstration, the program used the universal Turing machine. Many people like the fact that McCarthy preferred the universal function from the theory of recursive functions. Until that time, this theory was used only within the set of natural numbers. McCarthy noted that the naturalness of a set is not a limitation, and that it will work with any enumerated set. All this led to a universal function for functions on symbolic expressions (S-expressions).
The universal function took as an argument the description of any function and the description of its arguments. As a result, it produced the result of executing the function on the arguments. To write such a function, it was necessary to change the syntax of the function definition. It was necessary to describe it using data, and here it is - S-expression.
In his article, McCarthy described a small set of operations on S-expressions: ATOM, EQ, CONS, CAR, CDR. To them, he added QUOTE and COND as logical functions. The status of LABEL and LAMBDA is rather intriguing: EVAL rewrites lists so that they appear as atoms in them, so LABEL and LAMBDA are used in the process.
We can consider the universal McCarthy function as an elegant axiomatization of the approach to calculations [8] . But what was a theoretical investigation became Lisp. The universal function changed the language so that not only the data, but also the functions became lists. Thanks to Roussel's inspiration and his abilities as a programmer, the universal function became an interpreter.
To answer the question of why people fall in love with the Prologue, I did not invent anything better than to cite a few examples. For Lisp, there is an even better way: check out the universal function of EVAL and its inseparable APPLY. They are found at the very beginning of the description of Lisp. Here is the pons asinorum [9] : it seems to me that those who have abandoned the study abandoned him in this very place. After crossing the bridge, the newcomer continues the journey to the end and becomes an adherent of Lisp.
The similarities of the Lisp and the Prologue are, and have always been, the subject of endless debate. We ignore the creations of people writing FORTRAN Lisp programs and people using the prologue like Pascal with pattern support. In short, everything that McCarthy called “pornographic programming” [4] should be ignored. In this debate, only code written with knowledge of “Zen language” should be considered. Description of Zen Prologue leave on another time. For Lisp, it will be as follows.
From a modern point of view, the main thing that McCarthy did was the definition of a virtual machine. In general, he identified it during a mental experiment exclusively for descriptive purposes. Therefore, he could afford to make it as simple as possible from a logical point of view: out of seven primitives working with lists (ignoring the differences between lists and S-expressions) consisting only of the head and tail. It is surprising that all this developed into a language that could be implemented at that time. And even more intriguing is that an extremely simple virtual machine has survived over the decades of growing memory and processor speeds. Based on this virtual machine, all the EVAL / APPLY interpreters are built, which can be found in any Lisp introductory course.
As soon as a novice comprehends Zen Lisp, it becomes natural for him to write any program, as an extension of the limited capabilities of the basic interpreter. And these seven primitives are not buried and are not removed from sight, as soon as the interpreter is finished. On the contrary, they are very often found in user code. Gilbert told the opponents of the theory of sets: “No one will force us to leave the paradise created for us by Cantor”. The same is experienced by lispery in relation to the paradise created by McCarthy.
The fifth generation project was launched by people who know Lisp and perceive Prologue as an intriguing novelty. The vision (or mirage) of the new generation of computers was based on logical calculations and parallelism, which shifted the balance of opinions in favor of Prolog. Had it happened otherwise, the fate of fifth-generation systems would have no effect on Lisp: it was already widely distributed. But historically it happened that fragile and early hopes for Prologue collapsed along with the collapse of fifth-generation systems that did not achieve their goals.
About terminology. Logical programming is a method that uses logical sentences in the representation of procedures and data, and performs calculations based on the statements obtained. Prologue is a programming language based on these two ideas. Both language and method played a major role in the systems of the fifth generation.
At the conference, which opened the project, in 1981 Fuchi called logic programming its main programming methodology. On the final in 1992, Furukawa recalled that the team of the Electrotechnical Laboratory (ETL) from Tokyo (which later started the fifth generation systems project) in 1976 had a lot of experience in Lisp, and Prologue was completely unfamiliar with it. In 1976, this was the case with everyone: outside of Marseille, only a couple of institutions knew about Prolog.
Fuchi became interested in logic programming [1] after reading Kawasaki's article [7] in 1974. This probably forced Furukawa to search for the Prologue during his visit to the Standford Research Institute in 1976. He did indeed find the source code on Fortran of the first version of the Prolog interpreter distributed for outside of marseille. In 1974, David H. D. Warren took a copy to Edinburgh. And in 1976, Harry Barrow brought a copy from Edinburgh to the Stanford Research Institute. Warren [1] said: "Harry could not start the system by himself and gave it a copy of Furukawa." In 1976, in Tokyo ETL, Furukawa and several other researchers began experimenting with Prolog. The United States acted as a carrier of the Prolog virus, having themselves avoided infection.
')
As a result of his work at ETL, Furukawa demonstrated several database indexing programs on the prologue. Apparently, the positive results allowed ETL to obtain the prologue implementation for DEC-10 from David H. D. Warren. Furukawa wrote [2] :
I wrote a program to build a Rubik's cube on the Prologue DEC-10. It was effective and solved the problem in a relatively short time (about 20 seconds). In this type of expert systems, the decision-making mechanism is effectively implemented using tail recursion on the Prolog. After this experiment, I became convinced that the prologue is a language for processing knowledge.
For information on the history of the prologue, I turned to the book “The Birth of Prologue” by Alan Kolmeoera and Philip Rossell [3] . The first steps were taken in 1971 by a group led by Colmerour at Aix-Marcel University. After creating several preliminary versions that serve exclusively for processing natural languages, a “final version” was created in 1973. Under the influence of Kawasaki, the logic of sentences became a language, and a certain form of statements served as a procedure call mechanism. This version was the first, called the “Prologue” and used for tasks other than the processing of natural languages. In early 1974, after Warren’s visit to Marseille, a copy of the Prologue came to Edinburgh; and from Edinburgh quickly spread to several European institutions (Budapest, Leuven, Lisbon) and Canada.
From 1974 to 1977 a lot of fascinating experiments were carried out, which continued in Marseilles. Helder Coelho from Lisbon began to assemble programs for the book How to do it on the Prologue. In 1975, Warren began writing the Prolog compiler on the DEC-10 Prolog. When it was completed in 1977, it turned out that a major improvement had been made to the 1973 Marseille interpreter. Warren and his colleagues dared to compare it with the Lisp compiler, which was perfect as a work of art, and got interesting results. Lists were reversed 30-50% faster than Lisp. The result was amazing, because lists are translated into logical terms and are processed in a uniform way, like any other term. Symbolic differentiation (depending on data) was performed from 1.1 to 2.6 times faster than on Lisp. In 1977 Lisp was 18 years old, and Prologue was 6, and only a handful of people worked on its development from 1971 to 1977.
The following examples are, by and large, useless. They are chosen to demonstrate the attractive nature of the Prologue.
Suppose a program for the predicate “move” meaning when writing move (X1, Y1, X2, Y2) that the knight can move from the cage (X1, Y1) to the cage (X2, Y2).
Having the appropriate program, you can ask
?- move (U,U,V,V).
which would mean “can a horse go to one of the cells diagonally in one move” and get the answer “No”.
When asked
?- move(U,U,X,Y),move(X,Y,V,V).
meaning “can a knight go to the cell diagonally in two moves” we get the answer “Yes”, with all the moves if necessary. The program will be next
move(X1,Y1,X2,Y2) :- diff1(X1,X2),diff2(Y1,Y2).
move(X1,Y1,X2,Y2) :- diff2(X1,X2),diff1(Y1,Y2).
% diff1(X,Y): X Y 1.
diff1(X,Y) :- succ(X,Y).
diff1(X,Y) :- succ(Y,X).
% diff2(X,Z): X Z 2.
diff2(X,Z) :- succ(X,Y),succ(Y,Z).
diff2(X,Z) :- succ(Z,Y),succ(Y,X).
% succ(X,Y): Y X.
succ(1,2). succ(2,3). succ(3,4). succ(4,5). succ(5,6). succ(6,7). succ(7,8).
Another example. Suppose we have a set of twenty-seven figures contained in the following lists.
[1,9,1,6,1,8,2,5,7,2,6,9,2,5,8,4,7,6,3,5,4,9,3,8,7,4,3]
[1,9,1,2,1,8,2,4,6,2,7,9,4,5,8,6,3,4,7,5,3,9,6,8,3,5,7]
[1,8,1,9,1,5,2,6,7,2,8,5,2,9,6,4,7,5,3,8,4,6,3,9,7,4,3]
[3,4,7,9,3,6,4,8,3,5,7,4,6,9,2,5,8,2,7,6,2,5,1,9,1,8,1]
[7,5,3,8,6,9,3,5,7,4,3,6,8,5,4,9,7,2,6,4,2,8,1,2,1,9,1]
[3,4,7,8,3,9,4,5,3,6,7,4,8,5,2,9,6,2,7,5,2,8,1,6,1,9,1]
with the condition that each of the digits d = 1, .., 9 there are three occurrences of d, where d are separated from each other by d positions. To solve, we need a rather complicated query.
?-equals(List,
[_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_]),
sublist([9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9],List),
sublist([8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8],List),
sublist([7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7],List),
sublist([6,_,_,_,_,_,_,6,_,_,_,_,_,_,6],List),
sublist([5,_,_,_,_,_,5,_,_,_,_,_,5],List),
sublist([4,_,_,_,_,4,_,_,_,_,4],List),
sublist([3,_,_,_,3,_,_,_,3],List),
sublist([2,_,_,2,_,_,2],List),
sublist([1,_,1,_,1],List).
but the program itself is very small and contains only general purpose predicates:
% sublist(X,Y) X Y
sublist([],List).
sublist([X|Xs],[X|Ys]) :- append(Xs,_,Ys).
sublist(List,[Y|Ys]) :- sublist(List,Ys).
append([],Y,Y).
append([U|X],Y,[U|Z]) :- append(X,Y,Z).
equals(X,X).
The early history of the prologue seems to me very interesting: only a few people in six years from scratch have developed it into an elegant, powerful and effective language that is included in the Big Four so far. The early history of Lisp is no less entertaining. In the 1950s, McCarthy chose the language for his “ Advisor ” project. Candidates were IPL-V Newela and Simon and the Fortran compiler, developed by the Backus team at IBM. The IPL had the advantage of flexible data structures represented by lists. On the other hand, McCarthy liked Fortran because of its iteration mechanism. Therefore, he began an experiment in creating FLPL (Fortran List Processing Language), a version of the Fortran compiler with support for working with lists. I recall that at that time support for user-defined functions in Fortran was an undocumented property with a long-term implementation, and the function body was limited to one line. Not surprisingly, McCarthy began work on his own list processing language. In November 1958, the interpreter was already working at MIT. Soon it evolved into a language known to us now as Lisp, which was a side effect of working on a project description.
One of the features of the language was its universality: is it possible to calculate everything that is calculated in principle? As a demonstration, the program used the universal Turing machine. Many people like the fact that McCarthy preferred the universal function from the theory of recursive functions. Until that time, this theory was used only within the set of natural numbers. McCarthy noted that the naturalness of a set is not a limitation, and that it will work with any enumerated set. All this led to a universal function for functions on symbolic expressions (S-expressions).
The universal function took as an argument the description of any function and the description of its arguments. As a result, it produced the result of executing the function on the arguments. To write such a function, it was necessary to change the syntax of the function definition. It was necessary to describe it using data, and here it is - S-expression.
... After describing EVAL and publishing about it, Steve Russell asked why I would not program EVAL and do the interpreter; I answered, well, well, do not confuse theory with practice, EVAL is for reading, not for calculations. But he continued and made an interpreter. He compiled EVAL from my article in 704 lines of machine code, corrected the bugs and told everyone about the Lisp interpreter, which it actually was; in general, from the moment Lisp acquired the form in which we know it today, the form of S-expressions (highlighted by Stoyan [5] in the transcript of The History of Lisp, a conversation with McCarthy in 1974)
In his article, McCarthy described a small set of operations on S-expressions: ATOM, EQ, CONS, CAR, CDR. To them, he added QUOTE and COND as logical functions. The status of LABEL and LAMBDA is rather intriguing: EVAL rewrites lists so that they appear as atoms in them, so LABEL and LAMBDA are used in the process.
We can consider the universal McCarthy function as an elegant axiomatization of the approach to calculations [8] . But what was a theoretical investigation became Lisp. The universal function changed the language so that not only the data, but also the functions became lists. Thanks to Roussel's inspiration and his abilities as a programmer, the universal function became an interpreter.
To answer the question of why people fall in love with the Prologue, I did not invent anything better than to cite a few examples. For Lisp, there is an even better way: check out the universal function of EVAL and its inseparable APPLY. They are found at the very beginning of the description of Lisp. Here is the pons asinorum [9] : it seems to me that those who have abandoned the study abandoned him in this very place. After crossing the bridge, the newcomer continues the journey to the end and becomes an adherent of Lisp.
The similarities of the Lisp and the Prologue are, and have always been, the subject of endless debate. We ignore the creations of people writing FORTRAN Lisp programs and people using the prologue like Pascal with pattern support. In short, everything that McCarthy called “pornographic programming” [4] should be ignored. In this debate, only code written with knowledge of “Zen language” should be considered. Description of Zen Prologue leave on another time. For Lisp, it will be as follows.
From a modern point of view, the main thing that McCarthy did was the definition of a virtual machine. In general, he identified it during a mental experiment exclusively for descriptive purposes. Therefore, he could afford to make it as simple as possible from a logical point of view: out of seven primitives working with lists (ignoring the differences between lists and S-expressions) consisting only of the head and tail. It is surprising that all this developed into a language that could be implemented at that time. And even more intriguing is that an extremely simple virtual machine has survived over the decades of growing memory and processor speeds. Based on this virtual machine, all the EVAL / APPLY interpreters are built, which can be found in any Lisp introductory course.
As soon as a novice comprehends Zen Lisp, it becomes natural for him to write any program, as an extension of the limited capabilities of the basic interpreter. And these seven primitives are not buried and are not removed from sight, as soon as the interpreter is finished. On the contrary, they are very often found in user code. Gilbert told the opponents of the theory of sets: “No one will force us to leave the paradise created for us by Cantor”. The same is experienced by lispery in relation to the paradise created by McCarthy.
The fifth generation project was launched by people who know Lisp and perceive Prologue as an intriguing novelty. The vision (or mirage) of the new generation of computers was based on logical calculations and parallelism, which shifted the balance of opinions in favor of Prolog. Had it happened otherwise, the fate of fifth-generation systems would have no effect on Lisp: it was already widely distributed. But historically it happened that fragile and early hopes for Prologue collapsed along with the collapse of fifth-generation systems that did not achieve their goals.
Source: https://habr.com/ru/post/107165/
All Articles