Prolog

Prolog (от “PROgramming in LOGic”) — декларативный язык программирования общего назначения.

Prolog был создан в 1972 с целью сочетать использование логики с представлением знаний. С тех пор у него появился ряд диалектов, расширяющих основу языка различными возможностями.

Стандарт языка дан в ISO/IEC 13211-1 (1995 год).

Prolog — один из старейших и все еще один из наиболее популярных языков логического программирования, хотя он значительно менее популярен, чем основные императивные языки. Он используется в системах обработки естественных языков, исследованиях искусственного интеллекта, экспертных системах, онтологиях и других предметных областях, для которых естественно использование логической парадигмы.

Prolog был создан под влиянием более раннего языка Planner и позаимствовал из него следующие идеи:

• обратный логический вывод (вызов процедур по шаблону, исходя из целей);
• построение структура управляющей логики в виде вычислений с откатами;
• принцип “отрицание как неудача”;
• использование разных имен для разных сущностей и т.д.

Главной парадигмой, реализованной в языке Prolog, является логическое программирование. Как и для большинства старых языков, более поздние реализации, например, Visual Prolog, добавляют в язык более поздние парадигмы, например, объектно-ориентированное или управляемое событиями программирование, иногда даже с элементами императивного стиля.

Prolog использует один тип данных, терм, который бывает нескольких типов:

• атом — имя без особого смысла, используемое для построения составных термов;
• числа и строки такие же, как и в других языках;
• переменная обозначается именем, начинающимся с прописной буквы, и используется как символ-заполнитель для любого другого терма;
• составной терм состоит из атома-функтора, за которым следует несколько аргументов, каждый из которых в свою очередь является атомом.

Программы, написанные на чистом Prolog, описывают отношения между обрабатываемыми сущностями при помощи клауз Хорна. Клауза — это формула вида Голова :- Тело., которая читается как “чтобы доказать/решить Голову, следует доказать/решить Тело”. Тело клаузы состоит из нескольких предикатов (целей клаузы), скомбинированных с помощью конъюнкции и дизъюнкции. Клаузы с пустым телом называются фактами и эквивалентны клаузам вида Голова :- true. (true — не атом, как в других языках, а встроенный предикат).

Другой важной частью Prolog являются предикаты. Унарные предикаты выражают свойства их аргументов, тогда как предикаты с несколькими аргументами выражают отношения между ними. Ряд встроенных предикатов языка выполняют ту же роль, что и функции в других языках, например, ….

Предикаты с несколькими аргументами могут действовать в нескольких направлениях в зависимости от того, какие из аргументов уже связаны, а какие — нет. Например, ….

Наконец, для того, чтобы быть языком общего назначения, Prolog должен предоставлять ряд сервисных функций, например, процедур ввода/вывода. Они реализованы как предикаты без специального логического смысла, которые всегда оцениваются как истинные и выполняют свои сервисные функции как побочный эффект оценивания.

Целью выполнения программы на Prolog является оценивание одного целевого предиката. Имея этот предикат и набор правил и фактов, заданных в программе, Prolog пытается найти привязки (значения) переменных, при которых целевой предикат принимает значение истинности.

…

Структура программы на Прологе отличается от структуры программы, написанной на процедурном языке. Пролог-программа является собранием правил и фактов. Решение задачи достигается интерпретацией этих правил и фактов. При этом пользователю не требуется обеспечивать детальную последовательность инструкций, чтобы указать, каким образом осуществляется управление ходом вычислений на пути к результату. Вместо этого он только определяет возможные решения задачи и обеспечивает программу фактами и правилами, которые позволяют ей отыскать требуемое решение.

Во всех других отношениях Пролог не отличается от традиционных языков программирования. Как и в случае программы написанной на любом другом языке, Пролог-программа предназначена для решения отдельной задачи.

Пролог (Prolog) — язык логического программирования, основанный на логике дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка. Начало истории языка относится к 70-м годам XX века. Будучи декларативным языком программирования, Пролог воспринимает в качестве программы некоторое описание задачи, и сам производит поиск решения, пользуясь механизмом бэктрекинга и унификацией.

Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Поэтому программа на Прологе не является таковой в традиционном понимании, так как не содержит управляющих конструкций типа if … then, while … do; нет даже оператора присваивания. В Прологе задействованы другие механизмы. Задача описывается в терминах фактов и правил, а поиск решения Пролог берет на себя посредством встроенного механизма логического вывода.

Перечень возможных синтаксических конструкций Пролога невелик, и в этом смысле язык прост для изучения. С другой стороны, декларативный стиль программирования оказывается столь непривычным и новым для опытных программистов, что вызывает шок и в ряде случаев оказывается тормозом.

Пролог реализован практически для всех известных операционных систем и платформ. В число операционных систем входят OS для мэйнфреймов, всё семейство Unix, Windows, OS для мобильных платформ.

Многие современные реализации языка имеют внутреннее расширение за счет ООП-архитектуры. Кроме проприетарных решений, существуют свободные реализации Пролог.

Пролог критикуется в первую очередь за свою недостаточную гибкость, отчего решения на обычных языках программирования (типа C++, Java) в сочетании с базами данных оказываются более технологичными, чем аналогичные решения на Прологе. Негибкость заключается в трудности изучения языка, более высоких требованиях к квалификации программиста на Прологе, трудности отладки программы, неразвитости технологии программирования, плохой контролируемости промежуточных результатов.

Основные вехи развития языка Prolog

Prolog стал воплощением идеи использования логики в качестве языка программирования, которая зародилась в начале 1970-х годов, и само его название является сокращением от слов “programming in logic” (программирование в терминах логики). Первыми исследователями, которые занялись разработкой этой идеи, были Роберт Ковальски (Robert Kowalski) из Эдинбурга (теоретические основы), Маартен ван Эмден (Maarten van Emden) из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ (Alain Colmerauer) из Марселя (реализация). Популяризации языка Prolog во многом способствовала эффективная реализация этого языка в середине 1970-х годов Дэвидом Д. Г. Уорреном (David D.H. Warren) из Эдинбурга. К числу новейших достижений в этой области относятся средства программирования на основе логики ограничений (Constraint Logic Programming — CLP), которые обычно реализуются в составе системы Prolog. Средства CLP показали себя на практике как исключительно гибкий инструмент для решения задач составления расписаний и планирования материально-технического снабжения. А в 1996 году был опубликован официальный стандарт ISO языка Prolog.

Наиболее заметные тенденции в истории развития языка Prolog

В развитии языка Prolog наблюдаются очень интересные тенденции. Этот язык быстро приобрел популярность в Европе как инструмент практического программирования. В Японии вокруг языка Prolog были сосредоточены все разработки компьютеров пятого поколения. С другой стороны, в США этот язык в целом был принят с небольшим опозданием в связи с некоторыми историческими причинами. Одна из них состояла в том, что Соединенные Штаты вначале познакомились с языком Microplanner, который также был близок к идее логического программирования, но неэффективно реализован. Определенная доля низкой популярности Prolog в этой стране объясняется также реакцией на существовавшую вначале “ортодоксальную школу” логического программирования, представители которой настаивали на использовании чистой логики и требовали, чтобы логический подход не был “запятнан” практическими средствами, не относящимися к логике. В прошлом это привело к широкому распространению неверных взглядов на язык Prolog. Например, некоторые считали, что на этом языке можно программировать только рассуждения с выводом от целей к фактам. Но истина заключается в том, что Prolog — универсальный язык программирования и на нем может быть реализован любой алгоритм. Далекая от реальности позиция “ортодоксальной школы” была преодолена практиками языка Prolog, которые приняли более прагматический подход, воспользовавшись плодотворным объединением нового, декларативного подхода с традиционным, процедурным.

Элементы синтаксиса:

Ссылки:

• Статья в Wikipedia (англ.)
• Статья в Wikipedia (рус.)

Примеры:

Hello, World!:

Visual Prolog создает проекты автоматически. Для запуска примера следует создать новый проект, выбрав “Console” в качестве UI Strategy, перейти к редактированию файла main.pro и заменить его содержимое приведенным кодом.

implement main
    open core

constants
    className = "main".
    classVersion = "".

clauses
    classInfo(className, classVersion).

clauses
    run():-
        console::init(),
        stdio::write("Hello, World!"),
        programControl::sleep(1000),
        succeed().
end implement main

goal
    mainExe::run(main::run).

Факториал:

Для запуска создайте новый проект с UI Strategy “Console” и замените содержимое файлов main.cl и main.pro приведенным кодом.

В main.cl добавлена одна строка factorial : (integer N, integer F) procedure (i,o)., которая определяет бинарный предикат factorial с известным первым и неизвестным вторым аргументами. Ключевое слово procedure описывает поведение предиката, указывая, что его вычисление всегда будет успешным и будет найдено ровно одно решение, так что откаты не понадобятся.

В main.pro находится собственно определение нового предиката. Для каждого его вызова есть два возможных соответствия — с нулевым или произвольным первым аргументом. Visual Prolog перебирает формулы в порядке их появления в коде, так что если первый аргумент равен нулю, проверка начинается с первой формулы factorial(0,F). Первое правило формулы — !, так называемое отсечение, использование которого предотвращает откат ко второй формуле и таким образом обеспечивает наличие ровно одного решения предиката. После этого переменная F, содержащая решение предиката, устанавливается в 1 и выводится на печать. Вторая формула factorial(N,F) рекурсивно вычисляет F1 как факториал N-1, устанавливает решение предиката равным N*F1 и выводит его на печать. Наконец, stdio::nl печатает новую строку.

При выполнении основной программы предикат factorial выполняется ровно один раз, для N=12. С каждым вызовом рекурсии N уменьшается на единицу, пока не становится равным нулю. После этого значения факториалов возвращаются и выводятся на печать в порядке возрастания. Программа обрабатывает только факториалы до 12!, т.к. попытка вычисления 13! вызывает ошибку переполнения целочисленного типа.

% main.cl
class main
    open core

predicates
    classInfo : core::classInfo.
    factorial : (integer N, integer F) procedure (i,o).
predicates
    run : core::runnable.

end class main

% main.pro
implement main
    open core

constants
    className = "main".
    classVersion = "".

clauses
    classInfo(className, classVersion).
    factorial(0,F) :- 
        !,
        F = 1, 
        stdio::write("0! = 1"),
        stdio::nl.
    factorial(N,F) :-
        factorial(N-1,F1),
        F = N*F1,
        stdio::write(N, "! = ", F),
        stdio::nl.
        
clauses
    run():-
        console::init(),
        factorial(12,F),
        programControl::sleep(1000),
        succeed().
end implement main

goal
    mainExe::run(main::run).

Числа Фибоначчи:

В этом примере определяются два новых предиката — бинарный fibonacci(N,F) для вычисления N-ого числа Фибоначчи и loop(N) для его вывода на печать. Единожды вычисленные числа не сохраняются для позднейшего использования, поэтому эта реализация неэффективна.

Следует отметить отличие реализаций предикатов от примера для факториала: формулы, описывающие начальные условия, задаются для произвольного значения переменной, но вычисляются до конца только в том случае, если первое правило (N<3 или N=1, соответственно) оценивается как истинное. Кроме того, каждый предикат записан как одна формула, использующая конъюнкцию и дизъюнкцию, а не как набор отдельных формул, использующих только конъюнкцию.

% main.cl
class main
    open core

predicates
    classInfo : core::classInfo.
    fibonacci : (integer N, integer F) procedure (i,o).
    loop : (integer N) procedure (i).
predicates
    run : core::runnable.

end class main

% main.pro
implement main
    open core

constants
    className = "main".
    classVersion = "".

clauses
    classInfo(className, classVersion).
    fibonacci(N,F) :- 
        N < 3, !, F = 1;
        fibonacci(N-1,F1), fibonacci(N-2,F2), F = F1 + F2.
    loop(N) :-
        ( N = 1, !, fibonacci(1,F);
          loop(N-1), fibonacci(N,F) ),
        stdio::write(F, ", ").        
clauses
    run():-
        console::init(),
        loop(16),
        stdio::write("..."),
        programControl::sleep(1000),
        succeed().
end implement main

goal
    mainExe::run(main::run).

Hello, World!:

Этот пример не требует загрузки фактов или правил. Запрос выполняется в интерактивном режиме, и его результат выглядит следующим образом:

Hello, World!
yes

Первая строка является собственно выводом предиката write, вторая — результат оценивания запроса.

write('Hello, World!'), nl.

Числа Фибоначчи:

Простая рекурсивная реализация слишком неэффективна с точки зрения памяти, чтобы успешно выполняться в Poplog, поэтому этот пример демонстрирует более сложную технику — рекурсию с запоминанием. Дополнительный предикат memo(Goal) определяется так, что в первый раз, когда оценивается Goal, результат оценки добавляется в базу фактов, и при следующем запросе не переоценивается, а используется как известный факт.

После этого предикат fib(N,F) определяется рекурсивно, но каждый вызов fib “обернут” в предикат memo, поэтому для каждого значения N fib(N,F) оценивается только один раз. При таком подходе печать вычисленных чисел может производиться сразу после их вычисления, без дополнительного цикла.

% fibonacci.pl
:- dynamic(stored/1).

memo(Goal) :-
    stored(Goal) -> true;
    Goal, assertz(stored(Goal)).

fib(1,1) :- !, write('1, ').
fib(2,1) :- !, write('1, ').
fib(N,F) :-
    N1 is N-1, memo(fib(N1,F1)), 
    N2 is N-2, memo(fib(N2,F2)), 
    F is F1 + F2,
    write(F), write(', ').

% interactive
[-fibonacci].
fib(16,X), write('...'), nl.

Факториал:

Этот пример состоит из двух частей — первую часть кода следует сохранить в файле fact.pl, расположенном в рабочем каталоге Poplog, а вторую — ввести вручную в интерактивном режиме.

[-fact]. загружает базу фактов и правил из этого файла в текущую сессию Poplog (и выводит сообщение fact reconsulted, чтобы обозначить успешность загрузки). Запрос fact(16,X). пытается найти значение X, при котором этот предикат будет оценен как истинный. Вывод, требующийся в примере, будет побочным эффектом оценивания запроса, а основным результатом будет X = 20922789888000 ?. Это означает, что если вы недовольны такой привязкой переменных, вы можете отказаться от нее (введя ; ), и будет продолжен поиск лучшей привязки.

% fact.pl
fact(X, F) :- 
    ( X=0, F=1; 
      Y is X-1, fact(Y, Z), F is X*Z), 
    write(X), write('! = '), write(F), nl.

% interactive
[-fact].
fact(16,X).

Квадратное уравнение:

Для запуска создайте новый проект с UI Strategy “Console” и замените содержимое файлов main.cl и main.pro приведенным кодом.

В main.cl добавлена одна строка q : () procedure().. Ключевое слово procedure описывает поведение предиката, указывая, что его вычисление всегда будет успешным и будет найдено ровно одно решение, так что откаты не понадобятся.

В main.pro находится собственно определение нового предиката. Предикат q не принимает аргументов, поскольку читает необходимые данные из stdio. Условное оценивание (конструкцияif-then-else) работает точно так же, как в других языках. Единственным отличием является знак отсечения ! перед then. Это означает, что как только условие if выполняется, откат уже не потребуется.

Хитрость этого примера в том, что невозможно сразу вычислить дискриминант, как в других языках. Тип данных по умолчанию для переменной D в присвоении D = B*B-4*A*C -uReal, который может хранить только неотрицательные числа.

% main.cl
class main
    open core

predicates
    classInfo : core::classInfo.
    q : () procedure().
predicates
    run : core::runnable.

end class main

% main.pro
implement main
    open core

constants
    className = "main".
    classVersion = "".

clauses
    classInfo(className, classVersion).
    q() :-
        stdio::write("A = "), 
        A = stdio::read(),
        if (A = 0), ! then
            stdio::write("Not a quadratic equation."), stdio::nl
        else
            stdio::write("B = "), 
            B = stdio::read(),
            stdio::write("C = "), 
            C = stdio::read(),
            if (B*B = 4*A*C), ! then
                stdio::writef("x = %f", -B/2.0/A)
            elseif (B*B > 4*A*C), ! then
                D = B*B-4*A*C,
                stdio::writef("x1 = %f\n", (-B+math::sqrt(D))/2.0/A),
                stdio::writef("x2 = %f", (-B-math::sqrt(D))/2.0/A)
            else
                D = -B*B+4*A*C,
                stdio::writef("x1 = (%f, %f)\n", -B/2.0/A, math::sqrt(D)/2.0/A),
                stdio::writef("x2 = (%f, %f)", -B/2.0/A, -math::sqrt(D)/2.0/A)
            end if
        end if.
        
clauses
    run():-
        console::init(),
        q(),
        succeed().
end implement main

goal
    mainExe::run(main::run).

Комментарии

blog comments powered by Disqus