The Early Days of Prolog in Hungary - a personal
account
Peter Szeredi
Budapest University of Technology and Economics
http://www.cs.bme.hu/~szeredi/english
Editor: Enrico Pontelli
Below is a somewhat lengthy letter written around 1992 to Peter Van
Roy, when he asked me for material for his JLP paper on Prolog
implementations [PVR1994].
Background
In early seventies there was no specialised computer science education
at the Hungarian universities. The demand for computer specialists was
mostly covered by employing people who graduated in mathematics or
engineering.
I graduated in 1972 as a mathematician, my thesis was in mathematical
logic. I had also been programming computers for six years by
that time.
My first encounter with computers and programming was in 1966 when I
was 17. I was quite lucky to find a place, the Computer Center of the
Ministry of Heavy Industries (NIM IGÜSZI), where I got a friendly
reception and given access to computers. I worked there part-time
during my studies and had done quite a bit of hacking in systems
programming. I also was active in the Algol 68 group: we first
translated the Algol 68 report to Hungarian and then started to work on
an Algol 68 implementation (which has never been finished). [A
sidetrack: during implementation I managed to discover an inconsistency
in the type (mode) system of Algol 68 which was later named "incestuous
unions".]
I joined (full time) the software department at NIM IGÜSZI in
1972. I worked in a group producing various system programs for a new
Hungarian computer. For our development work we used a relatively
unknown language CDL (Compiler Definition Language) designed by C. H.
A. Koster of Nijmegen University. We got acquainted with Koster
through our work on Algol 68 as he was one of the authors of the Algol
68 report. Koster invented a variant of van Wijngaarden's two level
grammars called affix grammars, and designed a language based on this
type of grammar, which was CDL.
Here is a piece of code in CDL:
factorial+n+f-n1:
equal+n+1, make+f+1;
subtr+n+1+n1, factorial+n1+f, times+f+n+f.
If you replace the affixes (+id) with parenthesised arguments, delete
the local variable declaration (-n1) and replace the ':' with ':-' you
get exactly Edinburgh Prolog notation (all this in 1970/71, some two
years before Prolog and six years before the Edinburgh notation was
invented). Of course, CDL is an imperative language, with destructive
assignment, and also there is no backtracking, but otherwise the
notation and the control is surprisingly similar to that of Prolog.
CDL is actually an open ended language, i.e. it lacks any primitive
operations. These (such as the equal, make, subtr, ... operations
above) have to be supplied in the target language (most of the time the
assembly language of the target computer, or sometimes a higher level
language, such as C). CDL is thus more like a recursive macro language.
In early seventies computerisation was one of the buzzwords in Hungary,
and there was quite a bit of government money for R&D work in
computer software. From this money another group at NIM
IGÜSZI (the "Logic in Computer Science" group), led by
István Németi, got a grant for developing an interactive,
semi-automatic verification system for a simple algorithmic language.
The verification system contained a structure sharing Boyer-Moore type
theorem prover. We managed to convince Németi's group to use CDL
as the implementation language. Because of this, and also because of my
earlier interest in logic I myself got interested in this work. I
remember looking at the theorem prover working on small theorems in
algebra, and realising that it wasn't able to go much beyond toy
problems.
Besides program verification, Németi's group was interested in
all kinds of interactions between logic and computer science. A
particular goal of theirs was to study and develop logic based
declarative programming languages such as Prolog. They had seminars on
declarative programming languages (e.g. on logic programming) during
1973 and they corresponded with the department of Computational Logic
in Edinburgh which led to Németi's visiting Edinburgh in 1974.
The first Hungarian Prolog
Németi had research contacts in Edinburgh and visited Scotland
several times. From there he brought the news and some papers
about a theorem prover (?) called Prolog. I was quite taken aback by
the fact that there was a theorem prover that could do something
useful: calculate the factorial of a number! Németi
brought the Marseille interpreter as a deck of cards from Edinburgh
together with a brief description of built-ins (on a line printer
listing) entitled Epilog[400,400] and copies of slides of David
Warren's talk entitled "What is Prolog?".
Porting of the Marseille Fortran interpreter to the ICL 1903A computer
of NIM IGÜSZI was included into our research contract for 1975. A
member of Németi's group, Péter Tóth, who was
given this task, encountered unexpected problems due to the different
word and character size (ICL 1900 had 24 bit words and 6 bit
characters). While he was struggling with the porting, I decided to try
to write my own Prolog interpreter in CDL. I actually had never had a
look at the Marseille Prolog itself, I based the implementation on the
last three slides of David Warren's above mentioned talk, entitled
'Example to illustrate how Prolog is implemented'. This showed three
snapshots in the execution of the (naive) rev(a.b.X, a.b.X) goal. The
structure of the (single) stack was quite apparent from these slides,
and this, together with my earlier encounter with a structure sharing
unification algorithm was enough to get me started. CDL proved to be a
very convenient implementation tool, especially suited for parsing, so
the tokeniser and parser were written in CDL, rather than in Prolog (as
was the case for the Marseille interpreter).
I succeeded in producing a working Prolog interpreter in a few weeks,
just in time for the usual yearly out of town gathering of NIM
IGÜSZI software developers where Prolog was the main topic that
year. The availability of a working interpreter gave a big boost to
that meeting. Several people got rather excited about Prolog, including
Ferenc Darvas who worked on projects for drug-industry, Iván
Futó, who worked in simulation, Zsuzsa Márkusz, an
architect, Miklós Szõts, a civil engineer turned computer
scientist. (Both Zsuzsa Márkusz and Miklós
Szõts were students of Németi.) In a few weeks after the
meeting Miklós Szõts produced the very first application
of the Hungarian Prolog: a program for planning of a one level workshop
building using prefabricated panels. Ferenc Darvas also came back with
a number of application proposals, where he believed Prolog to be of
good use, such as predicting drug interactions and various other
programs in drug design.
Very active months and years followed, with various applications
projects going on, which demanded various language extensions, ports to
other computers, debugging facilities, etc. Through this fruitful
interaction between implementors and application developers the Prolog
interpreter grew from a toy to a usable system.
This system (which is often confused with MProlog, the second Hungarian
Prolog, see later) had no name in itself. It used the Marseille syntax,
but the built-ins had English names (although some, which could pass as
English, at least for me, remained the same as in the Marseille Prolog,
e.g. univ, egalf, etc.). Here is an example:
+FACT(0,1).
+FACT(*N,*F)
-LESS(0,*N) -MINUS(*N,1,*N1) -FACT(*N1,*F1) -TIMES(*F1,*N,*F).
It was a batch-oriented system, as most of the computers in Hungary at
that time were mainframes without interactive access. It provided a
selective exhaustive trace and backtrace services. It had a number of
new built-ins over the Marseille functionality, such as undoable input
and undoable database predicates.
Undoable input was implemented using a a circular buffer in the
tokeniser to store the tokens read in. Token and term input predicates
trailed the value of the current token pointer of this circular input
buffer before the actual input was made. If such an input predicate was
backtracked over, its side effect was undone by moving the current
token pointer back to its original position (of course, this
backtracking capability was limited by the size of the buffer).
Subsequent input predicates read the tokens from the buffer, and
switched back to ``real'' input only when the sequence of unread tokens
was exhausted.
The second half of seventies there was thus a boom for Prolog in
Hungary. Several pilot application projects were started, mostly with
the help of government grants, though. The Prolog was ported to the
Siemens BS2000 computer, the first widely used interactive
implementation.
[You asked for anecdotes, so here is one. One of the first, very
popular, interactive demo programs (written by my younger brother
János) was a Hungarian natural language question-answer system,
which could parse and remember simple facts and rules about people and
itself (the program) and answer questions about these. It rejected
statements from which one could deduce some negative fact about the
program itself. E.g. after the rule 'If one is nice, he is
stupid' had been entered, it refused to accept the statement 'You are
nice', and actually gave an explanation why. One night a big shout was
heard at the terminal room, where two students were playing with this
program: I managed to tell the computer that he is stupid - shouted one
of them - simply by spelling it stoopid (it is even easier to misspell
the Hungarian equivalent of stupid).]
The Hungarian Prolog arouse the interest of LP researchers fairly soon.
I've dug up a letter from David Warren dated February 1976, and from
Bob Kowalski dated July 1976 in which they inquire about our Prolog.
Bob Kowalski actually visited us for a few days on his way back from
vacation in Poland in the summer of 1976. David Warren came in June
1977 for a two-week visit. [It turned out at that time that David
was influenced in his design of the Edinburgh syntax by his earlier
work in Algol 68, thus explaining similarities with CDL.] In 1978
there was symposium on Logic in Programming in
Salgótarján, with several logic programmers present. In
1980 the Logic Programming Workshop was held in Debrecen.
Unfortunately by the end of seventies the steam started to run out for
Prolog applications in Hungary. The biggest problem was the price of
computer time. To run Prolog one needed to purchase computer time
on one of the big western made mainframes, and this was much more
expensive than employing people to do the same task by hand (the labour
price being much more cheap than in the West). Thus in Hungary, in late
seventies, natural intelligence proved to be much cheaper than the
artificial one.
MProlog - the second Hungarian Prolog
Catching the last wave of big government grants for software, the
development of a new Prolog implementation was started in 1978. This
implementation, later called MProlog, was based on the three stack
Warren model of 1977. It was written in CDL2, a successor to CDL.
The MProlog system offered two paths for program execution. During
development, the Program Development SubSystem (PDSS) provided an
interactive environment for writing and testing programs. For
application delivery the Production System was offered, which used the
traditional translate-link-execute model.
PDSS was a comprehensive environment for the development of MProlog
programs providing support for program entry, editing, execution,
tracing, saving, etc. PDSS was implemented in MProlog itself. For
the programs entered, the system retained the source (without layout),
including variable names. PDSS stored the program as a
syntax-tree, which was always presented to the user in a standard,
pretty-printed format.
In the Production System MProlog source modules were first converted
into a compact internal format using the pretranslator. The translation
process included syntactic and semantic analysis (such as variable
classification), and produced a binary module containing Prolog code in
a format suitable for interpretation or further compilation.
Pretranslated modules could be linked---in MProlog terminology,
consolidated---into an executable program by the consolidator
program. The Consolidator also had the capability of
consolidating several binary modules into a single new binary module.
MProlog also has a native code compiler for certain architectures (IBM
370, M68000, VAX, Intel 386), as well as a byte-code compiler. The
compiler transformed a pretranslated module to a compiled module, with
the resulting module also amenable to consolidation. The compiler
encompassed a number of important improvements over the original
structure sharing compiler model, including techniques similar to those
used in the WAM.
The binary program resulting from consolidation was executed by the
interpreter. Unlike some other Prolog implementations, in MProlog the
interpreter was the core of the system. It was written in CDL2 and in
addition to interpretation proper, it served as the run-time system
(i.e. memory management, etc.) for the compiled code.
MProlog extended the usual Edinburgh Prolog language in a number of
respects. It had a (name based) module concept, user-controlled
multi-level indexing, exception handling, a rich set of built-ins,
including the undoable ones inherited from the first Hungarian Prolog.
For more details on MProlog, see [Far1994].
Although the development of MProlog was started at NIM IGÜSZI,
most of the people involved gradually moved to SZKI, a big computer
company set up a
few years before. I myself moved to the Theoretical Laboratory, the
department responsible for advanced research within SZKI in 1979. This
Lab was led by Bálint Dömölki, who helped a lot in
keeping the logic programming R&D alive. In SZKI I met Péter
Köves and Zsuzsa Farkas, who, in the following years were leading
the development of various sub-projects for MProlog. All in all, SZKI
provided an environment much more appreciative than NIM IGÜSZI for
the results achieved.
MProlog was being developed on the Siemens machine of SZKI. It was
demonstrated at the Debrecen workshop in June 1980, using a terminal
connected to the mainframe in Budapest. The Hungarian-made terminal was
very awkward to handle, one had to enter each message off-line,
surroundedwith special control characters showing which part of the
screen to transmit, and then press a special 'send' button to do the
actual transmission. As I recall, only Lew Baxter from Canada was brave
enough to tackle this terminal, successfully running his version of the
who-owns-the-zebra (five houses) puzzle. Strangely enough, four
years later he was recruited as the main Prolog expert for Logicware,
the company set up in Toronto to market MProlog in North America.
The announcement of the Japanese Fifth Generation Project gave a big
boost to the MProlog work. It was decided that MProlog will be made
into a product marketed in the West. A user documentation was produced
in English. One of the problems characteristic of the contemporary
Hungarian environment was that it was very difficult to find a way of
printing it out on a printer capable of producing lower case letters.
MProlog was ported to IBM CMS in 1981 and to VAX VMS in 1982. A problem
with the latter port was that officially there were no VAXes in Hungary
due to COCOM restrictions. In reality there were a few ones smuggled
in, but they were very difficult to access. The initial, partly
successful port to VAX was done at Nijmegen. Later we managed to get
some limited access to a VAX in Hungary. Epsilon GmbH in West Berlin,
formed from the developers of CDL2 also helped a lot by porting MProlog
to computers not available in Hungary.
The first sale of MProlog was in September 1982, in France. In the
subsequent years a number of European sales followed, in part through
Epsilon. In 1983 a Japanese distributor was appointed and, after a
version supporting Japanese characters was developed, several copies of
the system were sold.
In early 1984 a Hungarian born Canadian entrepreneur established a
company named Logicware to market MProlog in North America. The main
goal of Logicware was to enter Prolog into the data processing
departments of big companies. MProlog had the advantage of being
available on mainframes as well as minicomputers, workstations and PCs.
Logicware management decided that the biggest obstacle in widespread
acceptance of (M)Prolog was the inappropriateness of the terminology
and notation, as well as the lack of educational tools. Therefore
big efforts went into redesigning the terminology and the language. For
example the term 'clause' was replaced by the term 'statement',
'predicate' by 'definition', 'term' by 'expression', the new terms
being thought to be more acceptable for data processing people. The
built-in predicates were re-structured, and the names changed according
to the new terminology. E.g. the predicate 'clause' became
'matching_statement' where the word 'matching' indicated that the
built-in enumerated its multiple solutions on backtracking.
A group previously working on CDL2 itself, led by Tamás Langer
joined SZKI late 1983. In its height there were about 15 people working
full time on MProlog.
We switched from using the CDL2 compiler to the CDL2 Lab, a
sophisticated program development environment. The Lab, with its
powerful inter-module code-generation scheme, helped a lot in efficient
porting of MProlog to a wide range of architectures.
A new version of the compiler was designed and implemented. The first
version of the compiler, which was a fairly straightforward adaptation
of the Warren 1977 compiler was not really successful, as the code was
only 5-7 times faster than the (fast) interpreted one (and speedups
were even worse if lots of built-ins were invoked). The new compiler
had various features taken over from the WAM as well as further
extensions, some of which are described in a paper in the proceedings
of the workshop on Implementations of Logic Programming Systems of
ICLP93.
A special 16-bit version of MProlog was designed and implemented on IBM
PCs. With the appearance of 386 processors a 32-bit version was also
ported to the PC. Further ports included workstations (e.g. SUN),
Macintosh, IBM MVS, etc.
Significant effort was spent on tuning MProlog. The most often used
code in the interpreter was rewritten to assembly language of the
target computer, resulting in a fairly fast interpreter. In mid 1980-s
even a special piece of hardware was designed and prototyped, to
support efficient execution of MProlog (but this experiment did not go
any further than the prototype).
The PDSS went through several stages of development gradually achieving
the functionality outlined above. Various extensions, user interface
tools were also developed.
A tutorial supported by an appropriate educational software tool was
also produced.
In addition to MProlog development work, efforts were made to produce
libraries, tools, and concrete applications of MProlog.
Unfortunately the business plans of Logicware didn't materialise, and
the company gradually went out of business. SZKI continued the
maintenance and support of MProlog with the help of European
distributors in Germany and Italy.
In 1990 a new company, named IQSOFT, has been formed from the
Theoretical Lab of SZKI. IQSOFT maintained and used MProlog in early
1990-s, but mostly for internal purposes.
Other Hungarian Prolog implementations
Iván Futó and his group developed an extension of the
first Hungarian Prolog, called T-Prolog, for discrete simulation
purposes. One of the interesting features of T-Prolog was its
coroutining control, which was initially implemented using (double)
interpretation. In MProlog special built-ins for handling continuations
were included, and a T-Prolog implementation avoiding double
interpretation was constructed. In mid-eighties an independent Prolog
implementation, called CS-Prolog, was developed by Futó's group.
The line of T-Prolog, CS-Prolog etc. languages is described in
detail in Futó's invited talk at ICLP93 [Fut1993].
References
[Far1994] Zs. Farkas., P. Köves, P. Szeredi:
MProlog: an Implementation Overview. In Evan Tick and Giancarlo Succi
(editors): Implementations of Logic Programming Systems. Kluwer
Academic Publishers, 1994, 103-117
[Fut1993] I. Futó: Prolog with
Communicating Processes: From T-Prolog to CSR-Prolog (Invited paper),
In: D. S. Warren (Ed.): Logic Programming, Proceedings of the Tenth
International Conference on Logic Programming, MIT Press, 3-17.
[PVR1994] P. Van Roy: 1983-1993: The Wonder Years
of Sequential Prolog Implementation. Journal of Logic Programming
19/20: 385-441 (1994)