Editing Prolog (section)

== Implementation ==
{{Further|Comparison of Prolog implementations}}
[[File:Prolog systems.svg|thumb|upright=2|Prolog Heritage.<br />Systems with a dark gray background are not supported any more. Arrows denote influences and inspiration of systems. Quick legend: JIT = "Just in Time Compiler", JVM = "Java Virtual Machine", TOAM = "Tree-Oriented Abstract Machine"]]
=== ISO Prolog ===
The [[International Organization for Standardization]] (ISO) Prolog [[technical standard]] consists of two parts. ISO/IEC 13211-1,<ref name="ISO 13211">ISO/IEC 13211: Information technology – Programming languages – Prolog. [[International Organization for Standardization]], Geneva.</ref><ref>{{cite book |last1=Ed-Dbali |first1=A. |last2=Deransart |first2=Pierre |last3=Cervoni |first3=L. |year=1996 |title=Prolog: the standard: reference manual |publisher=Springer |location=Berlin |isbn=978-3-540-59304-1}}</ref> published in 1995, aims to standardize the existing practices of the many implementations of the core elements of Prolog. It has clarified aspects of the language that were previously ambiguous and leads to portable programs. There are three corrigenda: Cor.1:2007,<ref name="Cor.1">{{Cite web|url=https://www.iso.org/cms/render/live/en/sites/isoorg/contents/data/standard/05/04/50405.html|title=ISO/IEC 13211-1:1995/Cor 1:2007|website=ISO}}</ref> Cor.2:2012,<ref name="Cor.2">{{Cite web|url=https://www.iso.org/cms/render/live/en/sites/isoorg/contents/data/standard/05/80/58033.html|title=ISO/IEC 13211-1:1995/Cor 2:2012|website=ISO}}</ref> and Cor.3:2017.<ref name="Cor.3">{{Cite web|url=https://www.iso.org/cms/render/live/en/sites/isoorg/contents/data/standard/07/31/73194.html|title=ISO/IEC 13211-1:1995/Cor 3:2017|website=ISO}}</ref> ISO/IEC 13211-2,<ref name="ISO 13211"/> published in 2000, adds support for modules to the standard. The standard is maintained by the [[JTC1|ISO/IEC JTC1]]/[[SC22]]/WG17<ref name="WG17">{{Cite web|url=http://iso.org/jtc1sc22wg17|title=ISO/IEC JTC1 SC22 WG17}}{{Dead link|date=February 2023 |bot=InternetArchiveBot |fix-attempted=yes}}</ref> working group. ANSI X3J17 is the US Technical Advisory Group for the standard.<ref name="X3J17">{{cite web|url=http://www.sju.edu/~jhodgson/x3j17.html|title=X3J17 and the Prolog Standard|access-date=2009-10-02|archive-url=https://web.archive.org/web/20090823160951/http://www.sju.edu/~jhodgson/x3j17.html|archive-date=2009-08-23|url-status=dead}}</ref>

=== Compilation ===
For efficiency, Prolog code is typically compiled to abstract machine code, often influenced by the register-based [[Warren Abstract Machine]] (WAM) instruction set.<ref>David H. D. Warren. [http://www.ai.sri.com/pubs/files/641.pdf "An abstract Prolog instruction set"]. Technical Note 309, [[SRI International]], Menlo Park, CA, October 1983.</ref> Some implementations employ [[abstract interpretation]] to derive type and mode information of predicates at compile time, or compile to real machine code for high performance.<ref>{{Cite journal |doi=10.1109/2.108055 |last1=Van Roy |first1=P. |last2=Despain |first2=A. M. |title=High-performance logic programming with the Aquarius Prolog compiler |journal=Computer |volume=25 |pages=54–68 |year=1992 |s2cid=16447071}}</ref> Devising efficient implementation methods for Prolog code is a field of active research in the logic programming community, and various other execution methods are employed in some implementations. These include [[clause binarization]] and [[stack machines|stack-based virtual machines]].{{Citation needed|date=November 2010}}

=== Tail recursion ===
Prolog systems typically implement a well-known optimization method called [[tail call#Tail call optimization|tail call optimization]] (TCO) for deterministic predicates exhibiting [[tail recursion]] or, more generally, tail calls: A clause's stack frame is discarded before performing a call in a tail position. Therefore, deterministic tail-recursive predicates are executed with constant stack space, like loops in other languages.

=== Term indexing ===
{{Main|Term indexing}}
Finding clauses that are unifiable with a term in a query is linear in the number of clauses. [[Term indexing]] uses a [[data structure]] that enables [[Sublinear time|sub-linear-time]] lookups.<ref>{{Cite book |last1=Graf |first1=Peter |title=Term indexing |year=1995 |publisher=Springer |isbn=978-3-540-61040-3}}</ref> Indexing only affects program performance, it does not affect semantics. Most Prologs only use indexing on the first term, as indexing on all terms is expensive, but techniques based on ''field-encoded words'' or ''[[Superimposed code|superimposed]] codewords'' provide fast indexing across the full query and head.<ref name=WisePowers>{{cite conference |last1=Wise |first1=Michael J. |last2=Powers |first2=David M. W. |title=Indexing Prolog Clauses via Superimposed Code Words and Field Encoded Words |journal=International Symposium on Logic Programming |pages=203–210 |year=1986}}</ref><ref name=Colomb>{{Cite journal |doi=10.1016/0743-1066(91)90004-9 |title=Enhancing unification in PROLOG through clause indexing |journal=The Journal of Logic Programming |volume=10 |pages=23–44 |year=1991 |last1=Colomb |first1=Robert M. |doi-access =}}</ref>

=== Hashing ===
Some Prolog systems, such as [[Logic Programming Associates|WIN-PROLOG]] and SWI-Prolog, now implement hashing to help handle large datasets more efficiently. This tends to yield very large performance gains when working with large corpora such as [[WordNet]].

=== Tabling ===
{{main|Tabled logic programming}}
Some Prolog systems, ([[B-Prolog]], [[XSB]], [[SWI-Prolog]], [[YAP (Prolog)|YAP]], and [[Ciao (programming language)|Ciao]]), implement a [[memoization]] method called ''tabling'', which frees the user from manually storing intermediate results. Tabling is a [[space–time tradeoff]]; execution time can be reduced by using more memory to store intermediate results:<ref>{{Cite journal |last1=Swift |first1=T. |journal=Annals of Mathematics and Artificial Intelligence |volume=25 |issue=3/4 |pages=201–240|title=Tabling for non-monotonic programming |year=1999 |doi=10.1023/A:1018990308362 |s2cid=16695800}}</ref><ref>{{cite journal|last1=Zhou|first1=Neng-Fa|last2=Sato|first2=Taisuke|title=Efficient Fixpoint Computation in Linear Tabling|journal=Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming|date=2003|pages=275–283|url=http://www.sci.brooklyn.cuny.edu/~zhou/papers/ppdp03.pdf}}</ref>
<blockquote>Subgoals encountered in a query evaluation are maintained in a table, along with answers to these subgoals. If a subgoal is re-encountered, the evaluation reuses information from the table rather than re-performing resolution against program clauses.<ref>{{Cite journal |doi=10.1017/S1471068411000500 |title=XSB: Extending Prolog with Tabled Logic Programming |journal=Theory and Practice of Logic Programming |volume=12 |issue=1–2 |pages=157–187 |year=2011 |last1=Swift |first1=T. |last2=Warren |first2=D. S. |arxiv=1012.5123 |s2cid=6153112}}</ref></blockquote>
Tabling can be extended in various directions. It can support recursive predicates through '''SLG resolution''' or linear tabling. In a multi-threaded Prolog system tabling results could be kept private to a thread or shared among all threads. And in incremental tabling, tabling might react to changes.

=== Implementation in hardware ===
During the [[Fifth Generation Computer Systems project]], there were attempts to implement Prolog in hardware with the aim of achieving faster execution with dedicated architectures.<ref>{{Cite book |first5=K. |last5=Kiriyama |page=100 |doi=10.1145/30350.30362 |year=1987 |first4=K. |last4=Kurosawa |last2=Bandoh |first1=S. |first2=T. |title=Proceedings of the 14th annual international symposium on Computer architecture - ISCA '87 |last3=Yamaguchi |first3=S. |last1=Abe |chapter=High performance integrated Prolog processor IPP |isbn=978-0-8186-0776-9 |s2cid=10283148}}</ref><ref>{{cite conference |first=Ian |last=Robinson |isbn=978-3-540-16492-0 |doi=10.1007/3-540-16492-8_73 |title=A Prolog processor based on a pattern matching memory device |conference=Third International Conference on Logic Programming |series=Lecture Notes in Computer Science |publisher=Springer |volume=225|pages=172–179 |year=1986}}</ref><ref>{{Cite journal |journal=ACM SIGPLAN Notices |title=Performance and architectural evaluation of the PSI machine |volume=22 |page=128 |doi=10.1145/36205.36195 |year=1987 |last1=Taki |first4=M. |last2=Nakajima |first1=K. |last4=Ikeda |first2=K. |last3=Nakashima |first3=H. |issue=10 |doi-access=free}}</ref> Furthermore, Prolog has a number of properties that may allow speed-up through parallel execution.<ref>{{Cite journal |last1=Gupta |first1=G. |last2=Pontelli |first2=E. |last3=Ali |first3=K. A. M. |last4=Carlsson |first4=M. |last5=Hermenegildo |first5=M. V. |year=2001 |journal=[[ACM Transactions on Programming Languages and Systems]] |title=Parallel execution of prolog programs: a survey |volume=23 |page=472 |doi=10.1145/504083.504085 |issue=4 |s2cid=2978041 |url=http://oa.upm.es/11160/ |doi-access=free}}</ref> A more recent approach has been to compile restricted Prolog programs to a [[field programmable gate array]].<ref>{{Cite web|url=http://www.cl.cam.ac.uk/~am21/research/sa/byrdbox.ps.gz|title=Statically Allocated Systems}}</ref> However, rapid progress in general-purpose hardware has consistently overtaken more specialised architectures.

In 1982, computers operated at around 10,000 to 100,000 LIPS [logical inferences per second]. The FGCS planned to produce computers operating at 0.1 to 1 GLIPS.<ref>{{Cite book |last1=Bramer |first1=M. A. |url=https://archive.org/details/fifthgenerationa0000bram |title=The fifth generation: an annotated bibliography |last2=Bramer |first2=Dawn |date=1984 |publisher=Addison-Wesley |isbn=978-0-201-14427-7 |location=Wokingham, England ; Reading, Mass |pages=6}}</ref> The Institute for New Generation Computer Technology documents estimated that 1 LIP took about 100 operations on a conventional computer. The plan was to produce at the end of the project (in 1992) a machine with 1000 processors achieving 1 GLIPS, implying at least 1 MLIPS per processor.<ref>{{Cite journal |last1=Feigenbaum |first1=Edward |last2=Shrobe |first2=Howard |date=1993-07-01 |title=The Japanese national Fifth Generation project: Introduction, survey, and evaluation |journal=Future Generation Computer Systems |series=FGCS Conference |volume=9 |issue=2 |pages=105–117 |doi=10.1016/0167-739X(93)90003-8 |issn=0167-739X|doi-access=free }}</ref>

[[Sega]] implemented Prolog for use with the Sega AI Computer, released for the Japanese market in 1986. Prolog was used for reading [[natural language]] inputs, in the [[Japanese language]], via a [[touch pad]].<ref>{{cite magazine |date=March 26, 1987 |title=Software that takes games seriously |magazine=[[New Scientist]] |publisher=[[Reed Business Information]] |via=[[Google Books]] |page=34 |url=https://books.google.com/books?id=RI51dkpbcGoC&pg=PA34 }}{{Dead link|date=November 2023 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>