Главная arrow книги arrow Копия Глава 9. Логический вывод в логике первого п arrow Эффективная реализация логических программ
Эффективная реализация логических программ

Но даже в самых эффективных интерпретаторах Prolog, в связи с издержками на поиск по индексу, унификацию и формирование стека рекурсивных вызовов, требуется выполнение нескольких тысяч машинных команд в расчете на каждый этап логического вывода. В действительности интерпретатор постоянно ведет себя так, как если бы он никогда до сих пор не видел данную программу; например, ему приходится каждый раз находить выражения, которые согласуются с целью. С другой стороны, откомпилированная программа Prolog представляет собой процедуру логического вывода для конкретного множества выражений, поэтому ей известно, какие выражения согласуются с целью. В процессе компиляции система Prolog по сути формирует миниатюрную программу автоматического доказательства теоремы для каждого отдельного предиката, устраняя тем самым основную часть издержек интерпретации. Эта система позволяет также применять открытый код для процедуры унификации каждого отдельного вызова, что позволяет избежать необходимости проведения явного анализа структуры терма (подробные сведения об унификации с открытым кодом приведены в [1557]).

Наборы команд современных компьютеров плохо согласуются с семантикой Prolog, поэтому большинство компиляторов Prolog компилирует программу в промежуточный язык, а не непосредственно в машинный язык. Наиболее широко применяемым промежуточным языком является язык WAM (Warren Abstract Machine — абстрактная машина Уоррена) получивший название в честь Дэвида Г.Д. Уоррена, одного из создателей первого компилятора Prolog. Язык WAM представляет собой абстрактное множество команд, которое подходит для преобразования в него программ Prolog и может интерпретироваться или транслироваться в машинный язык. Другие компиляторы транслируют программу Prolog в программу на языке высокого уровня, таком как Lisp или С, а затем используют компилятор этого языка для трансляции в машинный язык. Например, определение предиката Append может быть откомпилировано в код, показанный в листинге 9.4. Ниже приведено несколько замечаний, заслуживающих упоминания в этой связи.