Принципы построения программ на Prolog

      Комментарии к записи Принципы построения программ на Prolog отключены

В этой теме 3 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 10 мес. назад.

  • Автор
    Сообщения
  • #2280

    questioner
    Участник

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

  • #2285

    Все программы выполняются на процессоре, который исполняет инструкции друг за другом. Специальный регистр указывает на номер текущей команды, после ее выполнения счетчик увеличивается. Исключение составляют команды условного или безусловного перехода, с их помощью в реализуется ветвление и все виды циклических конструкций. Таким же поведением обладают программы на ассемблерах, а также всех императивных языках — таких как C++, Java, Pascal.

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

    фрукт(апельсин).
    фрукт(яблоко).
    фрукт(груша).

    В данном случае предикат фрукт состоит из трех частей, соединенных точкой, эквивалентной логическому ИЛИ. Программу на Prolog удобно рассматривать в виде дерева, при этом узлами являются операторы и составные части предиката. Так, пример приведенный выше мог быть изображен следующим образом:
    prolog-predicates
    Части, которые расположены в коде раньше — помещаются в дереве левее. При исполнении программы, интерпретатор обходит дерево слева направо, до тех пор, пока не сможет установить истинность формулы.

    Если мы сделаем запрос фрукт(вишня), то вишня будет сопоставлено последовательно с каждым фруктом, после того, как груша будет обработана интерпретатор установит, что вишня не является фруктом, следовательно предикат завершится неудачей.

    Запрос может содержать оператор NOT, инвертирующий результат, так при запросе NOT(фрукт(вишня)) интерпретатор обработает первую часть предиката, установит что вишня не является апельсином и вернет истину. Такой результат может быть передан в код, инициировавший запрос, если результат по каким-либо причинам не подойдет, то интерпретатор может вернуться назад и попробовать перебрать другие виды фруктов.

  • #2293

    Выражения языка пролог могут соединяться не только оператором ИЛИ, но и другими видами операторов — при этом программа также как в рассмотренном примере может быть представлена в виде дерева. При выполнении программы выполняется обход дерева слева направо. Особым поведением обладает оператор отсечения — он запрещает переходы по следующим дугам во всех операторах ИЛИ, расположенных выше в дереве.

    if_then_else_example(X, Y):-
      X < 10, X > 3, !, Y is 1; Y is 2.

    Семантика Prolog-программ

    Если при обходе дерева управление получит оператор отсечения, то стоящий выше оператор ИЛИ не сможет передать управление операции Y is 2. Такой вид оператора отсекает все альтернативные решения в дереве, стоящие выше. Однако он не распространяет свое действие на нижестоящие операторы ИЛИ, поэтому цель может возвращать несколько решений даже если содержит оператор отсечения.

  • #2295

    В качестве еще одного примера можно рассмотреть функцию поиска максимума из трех чисел:

    max3(A, B, C, Max):-
      A > B, A > C, !, Max = A;
      B > C, !, Max = B.
    max3(_A, _B, C, Max):-
      Max = C.

    Пример дерева программы Prolog

    ЕСЛИ A > B И A > C, ТО Max = A
    ИНАЧЕ (ЕСЛИ A =< B ИЛИ А =< C) ЕСЛИ В > С, ТО Мах = В
    ИНАЧЕ (ЕСЛИ ОБА УСЛОВИЯ ВЫШЕ НЕ ВЫПОЛНИЛИСЬ) Мах = С

    Из примера видно, что отсечение можно понимать как логическое следствие, ограничивающее поиск решений если одно решение уже найдено.

    В данном случае переменные А, В и С должны быть конкретизированы, т.к. иначе возникнет ошибка при выполнении оператора сравнения (нельзя сравнивать неинициализированные переменные).

    Вариант ответа возможен только один, т.к. в каждой ветви алгоритм кроме последней стоят отсечения. Убрать отсечения нельзя, т.к. это приведен к некорректной работе (например, даже если А наибольшее число — будут проверяться B>C и если условие выполнится — то программа вернет в качестве ответа и A, и B {по очереди})

Для ответа в этой теме необходимо авторизоваться.