Last Steps Towards an Ultimate PROLOG

ABSTRACT

A portable version of Prolog, an Artificial Intelligence language, is presented. A complete system has been implemented on a micro-computer using a floppy-disk virtual memory. The general methodology of the implementation is discussed in terms of an abstract machine (Micromegasl suppor­ ting a language (Candide) in which the Prolog sys­ tem is written.

I INTRODUCTION

Prolog has been developed in our research laboratory in 1973 by A. Colmerauer and P. Roussel [1,2,10], mainly for natural language processing systems. Since then, it has been applied to vari­ ous A.I. fields. Several Prolog interpreters have been written, and even a compiler by 0. Warren for a DEC 10 computer. Practice and theory of Prolog have been also studied and extensively des­ cribed (see [3,5,6,8]). Amazingly, the influence of Prolog has been until now restricted to Europe, where the language has been largely di s tributed and used. However, some recent papers in the lit­ terature show a growing interest from the U.S. community [9,11].

II MOTIVATIONS

During the past years, Prolog users clamored for more facilities to write very large programs. For these reasons, we decided to start a new ge­ neral version required to be usable on large com­ puters as well as on micro-computers . Our first try in that direction was the design of a Prolog system on an Exorciser M6800 micro -computer. This work is reported in [4,7] and gave encouraging results, specially in the use of floppy disks for virtual memory management.

The Prolog system reported here i s intended to be the "ultimate" one in the sense tha t it is specially designed to fullfil the requirements of

1. Easy transportability.
2. Running large applications thanks to a large memory space dynamically organized as a tree structured hierarchy of sub-worlds to achieve soft­ ware protection and management of memory space.

LAST STEPS TOWARDS AN ULTIMATE PROLOG

1. Colmerauer, H. Kanoui. M. Van Caneghem

Groupe d'Intelligence Artificielle Faculte des Sciences de Luminy Universite d'Aix-Marseille II 13288 Marseille Cedex 9,France

1. Versatility by a practical tool to add user-oriented evaluable predicates.
2. Powerful new built-in features such as coroutines, infinite-trees processing [5] , error recovering and user controlled execution thanks to the concept of "block".
3. Interactivity by including clause editing capabilities.

III REALIZATION

We exhibit a complete, self-contained systern which includes :

1. A high level programming language, Candide, designed to provide the software tools needed to write the interpreter.
2. A candide compiler whi ch emits code for an abstract machine, Micromegas, featuring the hardware viewpoint of the system.
3. A Micromegas emulator which interprets the Micromegas code at run-time. This is the only part which depends on the host machine on which the Prolog system is implemented.
4. The Prolog interpreter itself, which is the heart of the system, and consists of 50 pages of Candide code.

A complete. fully documented version of this system is operational on Appl e II. The implemen­ tation on a Solar 16-65 (french minicomputer equivalent to POP 11-65) is on pro~rP.ss and will be done by September 81.

The abs1ract machine Micromegas is embedded into the operating system of the host computer, leaving free access to the built-in resources (e.g. in the Apple II implementation, the U.C.S.O. Pascal system procedures and functions can be reached from the Micromegas level) .

The abstract machine uses cells and words : a cell is the smallest part of memory addressable both by the host computer and by the Micromegas machine . A word is a sequence of contiguous cells containing a large address : in the Apple II im­ plementation, we have 8-bit cells and 24-bit word s .

This rrovides an addressing space of 2 megabytes, simulated by a virtual memory management system implemented by software on a floppy disk. The Mi­ cromeRHD machine has also 256 general purpose re ­ i~i~·t.nr~· r-Jnd r1 rJ!"H?r mHmory which r.ontains the pro ­ !';ram ,1J1J i:l local variable slack .

Tho Micromegas instructions perform arithme­ tic, transfers, comparisons. The operands are cells or word s from the virtual memory. the registers and the stack . Other instructions perform condi­ tion<~l, unconditional or computed goto's, proce­ dure invocation and return, extcrn,ll procedure activation, and so on.

IV PROLOG ON APPLE II

This implementation needs :

1. An Apple II with 48 K bytes of memory.
2. 2 . Two 143 K bytes floppy disks.
3. ]. Tho language card.

The Micromegas emulator is embedded into the Apple Pnscal system and consists in 10 pages of Pasca l code (Initialisation, I/0, and virtual me ­ mory management) plus 15 pages of 6502 assembler code (performing the 16 instructions of the Micro­ megas machine). The Micromegas code for the Prolog interpreter needs 12 K bytes. The virtual memory system in implemented on the two floppies and the main memory paging area occupies 40 256-byte pages. Such n configuration allows up to 50-pages Prolog pro1~rams .

V CONCLUSION

Tim performance of a micro-computer imple­ munl.<lU.on is slnw compi'lred with a large computer 11111!. Nuvurtheless, tile system remains usable thanks !.11 t.li" lm·gu virtual memory. fl micro-computer im­ pli!numt..ll inn ciln be used by A. I. students, or uv"n lly roseilr·chors for testinr; and debugginr; pro­ grams, thus performing (at home) on a personnal computer the more tedious and time consuming part of programming work. Naturally, the definitive app lication will be run on a bigger computer.

Is it really the ultimate Prolog ? Certainly yes for us !

In fact, we have deliberately spent three years to design the system and build the adequate tools to perform our research. This r;oal is now achieved and we have definitely moved back to the Prolog users family.

ACKNOWLEO�~MENTS

fill~; Wlll'k ht1:. IHH!tl :.ipon:;rJrt?LI lly t.hu Contrn N.d.l"n"l d" !.1 l~ncllnn:ilu :;cttulllfiquf! (l_qulpe dl! """'""'"'"' Fl!>!ill!:inu :HI:I).