Функциональные;

Процедурные;

Объектно-ориентированные;

Декларативные (реляционные).

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

Программа, написанная на процедурном языке , выражает алгоритм решения задачи в терминах действий (процедур), которые необходимо выполнить. Отличие процедуры от функции заключается в том, что процедура может возвращать любое количество значений, в том числе и ни одного. Таким образом, работа программы представляет собой последовательный вызов процедур. К процедурным языкам относятся Pascal, Basic и т.д. Следует отметить, что в любом процедурном языке имеется возможность определения и использования функций, а в функциональном - процедур (функций, невозвращающих значений - обычно определяются с модификатором void).

Программа, написанная на объектно-ориентированном языке , представляет собой набор объектов, взаимодействующих между собой посредством посылки сообщений. Каждый объект характеризуется информационной составляющей (набором атрибутов) и поведенческой (набор событий и методов). Работа программы представляет собой последовательный обмен сообщениями (вызов методов) между объектами. К объектно-ориентированным языкам относятся Object Pascal, Visual Basic, С++, Java и т.д. Следует отметить, что в любом объектно-ориентрованном языке имеется возможность процедурного программирования.

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

Программа, написанная на декларативном языке , представляет собой описание предметной области через набор отношений (англ. relation) между объектами (сущностями) и формулировку цели (задачи), которую требуется решить. В отличие от перечисленных выше языков, в такой программе нет явного описания последовательности действий, необходимых для решения задачи. Как правило, процедура поиска решения выполняется автоматически с использованием соответствующего математического или логического аппарата, лежащего в основе языка и реализованная в его конкретном интерпретаторе 1 (компиляторе 2). К декларативным языкам относятся Prolog, SQL и т.д. Таким образом, несомненным достоинством декларативных языков является концентрация внимания разработчика на том, что надо сделать, а не как.

Другая классификация языков программирования основана на стиле программирования :

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

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

Известна классификация языков программирования по их близости либо к машинному, либо к естественному человеческому языку. Те, что ближе к компьютеру, относят к языкам низкого уровня (Ассемблер), а те, что ближе к человеку, называют языками высокого уровня (Basic, Pascal, Java и т.д.). В этом смысле декларативные языки можно назвать языками сверхвысокого или наивысшего уровня, поскольку они очень близки к человеческому языку и человеческому мышлению.

В 1965 году в работе «A machine oriented logic based on the resolution principle» 3 , опубликованной в 12 номере журнала «Journal of the ACM», Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название «принцип резолюции» . На самом деле, идея данного метода была предложена Эрбраном в 1931 году, когда еще не было компьютеров (Herbrand, «Une methode de demonstration», These, Paris, 1931). Робинсон модифицировал этот метод так, что он стал пригоден для автоматического (компьютерного) использования и разработал эффективный алгоритм унификации, составляющий базис его метода.

Идеи использования логики в качестве языка программирования зародилась в начале 1970-х годов. Первыми исследователями, которые занялись разработкой этой идеи, были Роберт Ковальски (Robert Kowalski) из Эдинбурга (теоретические основы, статьи 1971 и 1974 г.), Маартен ван Эмден (Maarten van Emden) из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ (Alain Colmerauer) из Марселя (реализация, 1973 г.). В 1973 году «группа искусственного интеллекта» во главе с Аленом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (фр. PROgrammation en LOGique) и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алена Колмероэ. Программа была написана на Фортране и работала довольно медленно.

Популяризации Пролога во многом способствовали:

Эффективная реализация (интерпретатор/компилятор) этого языка для ЭВМ DEC-10 Дэвидом Д. Г. Уорреном (David D.H. Warren) из Эдинбурга в 1977 г. Послужила прототипом для многих последующих реализаций Пролога. Что интересно, компилятор был написан на самом Прологе. Эта реализация Пролога, известная как «эдинбургская версия», фактически стала первым и единственным стандартом языка;

Разработка Кларком и Маккейбом (Великобритания) в 1980 году версии для персональных ЭВМ;

Японский проект создания компьютеров V поколения. В конце 1978 г. Министерство внешней торговли и промышленности (МВТП) Японии поручило разработать проект интеллектуальных ЭВМ, специально созданному для этих целей Токийскому институту вычислительной техники (ICOT) 4 . Сердцем этих компьютеров должен был стать не арифметический процессор, а специально оптимизированный для работы с прологоподобными программами.

В 1995 году был опубликован официальный стандарт ISO 5 /IEC 6 языка Пролог (ISO/IEC 13211-1 «Information technology - Programming languages - Prolog - Part 1: General core» - «Информационные технологии. Языки программирования. Пролог. Часть 1. Общее ядро»).

На сегодня существует довольно много реализаций Пролога. Наиболее известные из них следующие: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic iis Workbench, Strawberry Prolog, SWI-Prolog, Turbo Prolog (PDC Prolog, Visual Prolog), UNSW Prolog и т. д. В нашей стране были разработаны такие версии Пролога как Пролог-Д (С. Григорьев), Акторный Пролог (А. Морозов), а также Флэнг (А. Манцивода, В. Петухин).

5. Дайте определение понятиям: « », « », « ».

9. Что понимается под « » и « » списка?

И рассмотреть решения простейших задач на Прологе.

Прежде, чем начинать, хотелось бы кратко ответить на злободневные вопросы от хабрачитателей:
- Где реально используется Пролог?
- Такие проекты существуют, некоторые приводились в комментариях к 1-й статье. Важно что, большинство программистов пишут на Прологе не от безвыходности, а от того, что им нравится Пролог. В конце концов Пролог не может использоваться для любой задачи, такой создание UI или манипулирование с файлами.

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

Почему нет сообщества Пролога?
- Оно есть. Такова специфика языка, что он очень полюбился в академической среде (большинство Prolog систем пишутся в различных университетах и наоборот практически любой университет пишет свой Пролог), из-за этого можно сказать страдает и применимость языка. Стоит отметить, что сообщество небольшое, но очень лояльное: практически все известные языки нашли свое отражение в современных языках (Lisp, ML -> F#, Scala; Smalltalk -> Java, Scala (агенты), скриптовые -> Ruby), в отличие от Пролог.

Думаю на этом хватит философских рассуждений и можно приступить к реальным примерам:)

В конце как обычно ожидает задача на приз.

Пример №1 - поиск совершенных чисел

Для этого примера нам понадобится предикат is/2. X is 3 + 1 * 2 - вычисляет выражение справа и заносит в переменную слева, это не присваивание (!), а утверждение что X = 7. Проще говоря фраза X = 7, X = 3 - не имеет решения потому как X не может быть одновременно 7 и 3.
Так же нам понадобится решение задачи из предыдущего топика. Задача была написать предикат, который бы генерировал все натуральные числа подряд, вот решение:
ints(0). ints(X) :- ints(Y), X is Y + 1.
На самом деле это декларативная версия стандартного предиката integer/1, который проверяет, что аргумент целое число. Проблема стандартного предиката, что он работает правильно для запроса:- integer(1) и не работает для запроса integer(X).

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

Не пытайтесь описать инструкции поиска решения, предположите, что вы уже нашли решение, а ваша задача только проверить, что решение найдено.

Как ни странно, но это стратегия прекрасно работает.
%% Декларативное определение натуральных чисел ints(0). ints(X) :- ints(Y), X is Y + 1. %% Совершенное число - это 1) натуральное число 2) сумма делителей равна числу perfect_number(X) :- ints(X), Y is X - 1, calculatesum_divisors_till(Sum, X, Y), Sum = X. %% Проверка суммы делителей 1-й аргумент Сумма, 2-й - число для которого ищем делители, %% 3-е - число до которого ищем делители calculatesum_divisors_till(0, _NumberToDivide, 0). calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem = 0, Ts is Till - 1, calculatesum_divisors_till(SumPrev, NumberToDivide, Ts), Sum is SumPrev + Till. calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem > 0, Ts is Till - 1, calculatesum_divisors_till(Sum, NumberToDivide, Ts).

Вставляем исходный текст в файл, запускаем интерпретатор и компилируем его (через запрос:-compile("путь_к_файлу/perfect_numbers.pl"). Пишете запрос :- perfect_number(X). и интерпретатор выдает ответ, при нажатии ";" выдает следующий. Обратите внимание запрос может быть :- perfect_number(X), X > 6 . Тогда все ответы будут больше 6. Конечно программа работает не оптимально, сама проверка может быть упрощена с использованием простых делителей, попробуйте.

Пример №2 - генерация перестановок.

Для постановки и решения этой задачи нам понадобятся понятие списков. Списки не являются базовым понятиям языка, между списками можно провести прямую аналогию со связными списками в C. Вернемся к определению терма как к рекурсивной структуре данных.
%% Определим пустой список как объект nil list(nil). %% Определим список из одного элемента 1 list(t(1, nil)). %% Определим список из элементов 1, 2, 3 list(t(1, t(2, t(3, nil)))). %% Опишем к примеру процедуру поиска в списке %% 1. результат находится в голове списка (1-й элемент) %% _ - означает незначимую для нас переменную member(X, t(Y, _)) :- X = Y. %% 2. результат не первый элемент, но содержится в хвосте списка после первого элемента member(X, t(_, Tail)) :- member(X, Tail).

Как многие бы сказали обычная рекурсия и чтобы списки не выглядели как-то особенно в Прологе существует синтаксический сахар для них: nil можно записать , t(1, nil) - , t(1, t(2, nil)) - , t(1, Sublist) - , t(1, t(2, Sublist)) - . Рекомендуется пользоваться синтаксическим сахаром для списков, потому как внутреннее название термов может отличаться (чаще всего терм называется ".").
%% 1. результат находится в голове списка (1-й элемент) member(X, ). %% 2. результат не первый элемент, но содержится в хвосте списка после первого элемента member(X, [_| Tail]) :- member(X, Tail).
Вернемся к исходной задаче генерации перестановок. Все прекрасно помнят, что количество перестановок n!, но вот дай эту задачу большинству программистов и все начнут судорожно вспоминать и говорить, что писали это в школе и забыли как делается перебор. В среднем алгоритм появляется после стараний и мучений через минут 20. При знании Пролога этот алгоритм пишется за 2 минуты или не пишется вообще:)

Как же решить на Прологе? Воспользуемся правилом не поиска решения, а проверки, что решение найдено. Предикат perm(Source, Permutation) - где Source исходный список, Permutation - перестановка.

%% Если исходный список пустой то существует одна перестановка пустой список perm(, ). %% 1-й элемент перестановки должен содержаться в исходном списке, %% при чем его надо сразу исключить из оригинального списка, %% остальные элементы должны быть перестановкой перестановкой %% оставшегося оригинального списка perm(Source, ) :- member_list_exclude(Element, Source, SourceExcluded), perm(SourceExcluded, Tail). %% Проверка того, что элемент содержится в списке, а 2-й список является списком без элемента %% Название предиката member_list_exclude соответствует порядку аргументов %% 1-й - элемент, 2-й - список, 3-й - список без элементов member_list_exclude(X, , L). member_list_exclude(X, , ) :- member_list_exclude(X, L, Ls).
Запрос :-perm(, X) генерирует все перестановки. Интересно, что запросы симметричны :-perm(X, ) относительно аргументов, правда данный запрос зависает и чтобы он работал необходимо поменять member_list_exclude и perm местами в perm.

Пример №3 - генерация сочетаний.

Генерация сочетаний по простоте реализации похожа на генерацию перестановок. Нам понадобится предикат member/2 - принадлежность элемента списку. Предположим у нас есть 2 списка: 1-й исходный список, 2-й - предполагаемое сочетание, необходимо проверить правильность сочетания. Элементы сочетания располагаются в порядке исходного списка.

Member(X, ). member(X, [_|L]) :- member(X, L). comb(, ). %% Вариант 1: 1-й элемент сочетания содержится в исходном списке comb(, ) :- comb(List, Tail). %% Вариант 2: сочетание является правильным сочетанием хвоста списка, %% то есть 1-й элемент исходного списка не содержится в сочетании comb([_|List], Tail) :- comb(List, Tail).

Пример №4 - сортировка.

Данный пример рассмотрим достаточно подробно и попытаемся провести оптимизацию первичного решения. Процесс написания на Прологе выглядит следующим образом: 1) первичное описание задачи и получение переборного решения 2) логическая оптимизация перестановкой предикатов справа 3) логическая оптимизация введения упрощенных проверок или удаление лишних условий 4) введение эвристик и оптимизация отдельних случаев путем отсечений.

Вариант 1. Сортировка наивная : первый элемент отсортированного массива должен быть минимальным, остальные элементы должны быть отсортированы. Первый массив исходный, второй массив отсортированный исходный.

Sort(, ). sort(List, ) :- min_list_exclude(Min, List, Exclude), sort(Exclude, SortRest). %% Рекурсивно исключаем минимальное число, если в списке одно число исключаем его min_list_exclude(M, [M], ). min_list_exclude(Min, , ExcludeRes) :- min_list_exclude(Ms, L, Exclude), find_result(result(M, L), result(Ms, ), result(Min, ExcludeRes)). %% Дополнительный предикат для определения пары с минимальным ключом find_result(result(M, L), result(Ms, _), result(M, L)):- M < Ms. find_result(result(M, _), result(Ms, Exclude), result(Ms, Exclude)):- Ms =< M.
Можно заметить, что сложность данного алгоритма квадратичная и основная проблема в том, что мы каждый раз ищем минимальный элемент, не сохраняя при этом никакой полезной информации.
Отметим также, что мы пытаемся определить, что такое 1-й элемент отсортированного массива.

Вариант 2. Быстрая сортировка. Посмотрим на проблему со второй стороны и попытаемся определить место 1-го элемента списка в отсортированном массиве (применим рекурсию к исходному массиву).

Sort_b(, ). sort_b(, List) :- split(T, R, Less, Great), sort_b(Less, LessSort), sort_b(Great, GreatSort), append(LessSort, , List). %% Разделяем массив на 2 массива больше и меньше split(_, ,, ). split(T, ,, Great) :- M < T, split(T,R, Less,Great). split(T, ,Less, ) :- M >= T, split(T,R, Less,Great). %% Склеиваем 2 списка append(, M, M). append(, Right, ) :- append(Left, Right, Res).
Можно заметить, что мы улучшили результаты сортировки, так как быстрая сортировка заведомо быстрее пузырьковой. Для того, чтобы еще улучшить результаты, мы можем вспомнить сортировку слияниями, которая в любом случае дает O(n lg n), но к сожалению данная сортировка применима только к массивам, а не к связным списка, с которыми мы работаем. Единственный вариант использовать дополнительную структуру данных для хранения - дерево.

Вариант 3. Сортировка с использованием бинарного дерева.

Для данного вида сортировки переведем исходный список в бинарное дерево, а затем, воспользовавшись обходом дерева слева, получим отсортированный массив. Дерево будем представлять рекурсивным термом tree(Object, LeftSubTree, RightSubTree) .
sort_tree(, nil). sort_tree(, Tree) :- sort_tree(L, LTree), plus(X, LTree, Tree). %% Добавление в элемента в дерево plus(X, nil, tree(X, nil, nil)). plus(X, tree(O, L, R), tree(O, ResL, R)) :- O >= X, plus(X, L, ResL). plus(X, tree(O, L, R), tree(O, L, ResR)) :- O < X, plus(X, R, ResR). sort_t(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). append_list(, L, L). append_list(, R, ) :- append_list(L, R, T). tree_list(nil, ). tree_list(tree(X, L, R), List) :- tree_list(L, ListL), tree_list(R, ListR), append_list(ListL, , List).

Вариант 4. Сортировка с использованием сбалансированного бинарного дерева.

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

Sort_btree(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). tree_list(nil, ). tree_list(tree(X, L, R, _), List) :- tree_list(L, ListL), tree_list(R, ListR), append(ListL, , List). sort_tree(, nil). sort_tree(, Tree) :- sort_tree(L, LTree), plus_tree(X, LTree, Tree). construct_tree(A, AL, AR, tree(A, AL, AR, ADepth)) :- diff(AL, AR, _, ADepth). diff(AL, AR, ADiff, ADepth) :- depth_tree(ALs, AL), depth_tree(ARs, AR), ADiff is ALs - ARs, max_int(ALs, ARs, AD), ADepth is AD + 1. max_int(A, B, A) :- A > B. max_int(A, B, B) :- A =< B. append(, L, L). append(, R, ) :- append(L, R, T). depth_tree(0, nil). depth_tree(X, tree(_, _, _, X)). plus_tree(X, nil, tree(X, nil, nil, 1)). plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep), balance_tree(tree(O, ResL, R, Dep), Diff, Res). plus_tree(X, tree(O, L, R, _), Res) :- O < X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep), balance_tree(tree(O, L, ResR, Dep), Diff, Res). %% No rotations balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff > -2. %% Small right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff >= 0, construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Result). %% Big right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff < 0, BR = tree(C, CL, CR, _), construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree), construct_tree(C, BSubTree, ASubTree, Result). %% Small left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0, construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result). %% Big left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff > 0, BL = tree(C, CL, CR, _), construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree), construct_tree(C, ASubTree, BSubTree, Result).
Данный пример не является достаточно выразительным для реализации на Прологе, хотя и дает представление о программах среднего объема. Для тренировки можно реализовать пузырьковую сортировку или сортировку вставками, оставим это на усмотрение читателя.

Пример №5 - Задача о переливаниях.

В качестве следующей задачи рассмотрим классическую задачу о состояниях, эта задача гораздо лучше отражает преимущества использования Пролог. Общая постановка задачи: даны некоторые емкости с водой, необходимо путем переливаний получить определенное количество воды в некоторой емкости. Для примера возьмем 3 кувшина емкостью 12 литров, 8 литров, 5 литров, наполним 1-й полностью, то есть 12 литрами и поставим задачу получить 6 литров . Для начала попытайтесь решить эту школьную задачу при помощи ручки и листка бумаги :)

Прежде чем генерировать различные алгоритмы и пытаться их применить к задаче, давайте сначала перепишем условия в терминах Пролога. Опишем емкость как терм sosud(Id, MaximumCapacity, CurrentCapacity) , состояние системы опишем как список емкостей. Пример . Теперь опишем запрос:

%% solve_pr_wo(InitialState, Goal, Steps). :- solve_pr_wo(, sosud(X, _, 6), Steps).

Обратите внимание, что Goal = sosud(_, _, 6), то есть нам не важно какой емкости сосуд главное чтобы в нем было именно 6 литров.

Теперь когда нам все известно опишем способ проверки решения, считая что шаги заданы в переменной Steps.

%% Для получения состояния не требуется ни одного шага, %% значит один из сосудов находится в списке solve_pr_wo(State, Goal, ) :- member(Goal, State). %% Первый шаг это перелить из Sosud в Sosud2 и получить состояние %% первого сосуда ResSosud, а второго ResSosud2. %% Конкретный пример шага: %% mv(sosud(1, 12, 12) -> sosud(2, 8, 0), sosud(1, 12, 4) -> sosud(2, 8, 8)). solve_pr_wo(State, Goal, ) :- %% В первую очередь проверка домена, что сосуды действительно %% содержатся в текущем состоянии и они не равны друг другу member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), %% Осуществление самого переливания, здесь %% участвуют все 4 переменных шага mv(Sosud, Sosud2, ResSosud, ResSosud2), %% Замена состояния сосудов в списке состояний по очереди replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %% Дальнейшие шаги должны выполняться по рекурсии solve_pr_wo(StateX, Goal, Steps). %% На самом деле обычная замена элемента в списке %% replace(ElementToReplace, InList, ElementToReplaceWith, OutList). replace(S, , X, ). replace(S, , X, ) :- replace(S, L, X, Ls). %% Процедура переливания - 2 варианта %% исходный сосуд будет исчерпан или целевой наполнен %% Опустошение первого сосуда во второй mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > < Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.

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

Что же, описание программы написано - можно запустить. Не стоит удивляться программа не заработает, оно попросту зависнет:) Это не так плохо как может показаться, потому что если бы программа не зависла, то она выдала бы правильный ответ. Следует разобраться почему же она зависла и здесь нам на помощь придет понимание как же Пролог разворачивает правила, чтобы найти решение. На самом деле, не надо иметь голову способную запомнить до 10 точек возврата, чтобы понять, что каждый следующий раз когда solve_pr_wo -> вызывает по рекурсии solve_pr_wo, он вызывает 2 предиката member/2, которые всегда выдают одно и то же 1-й и 2-й сосуд (предикат not вызывает backtracking и не позволяет member выбрать 1-й и 1-й сосуд). То есть алгоритм постоянно переливает из 1-го во 2-й и обратно.

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

Полная версия программа с распечаткой состояний и единственным предикатом для вызова solution:

Write_list(). write_list() :- writeln(X), write_list(L). solution:- solve_pr(, sosud(_, _, 6), , Steps), write_list(Steps). replace(S, , X, ). replace(S, , X, ) :- replace(S, L, X, Ls). %% будем считать стратегией переливания не сами шаги, а просто конечные состояния %% зная начальное и конечное состояние, не трудно догадаться, какой шаг был выполнен solve_pr(State, Goal, _, ) :- member(Goal, State). solve_pr(State, Goal, History, ) :- member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), mv(Sosud, Sosud2, ResSosud, ResSosud2), replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %%% та самая проверка конечного состояния not(member(StateX, )), solve_pr(StateX, Goal, , Steps). %% mv(sosud(_Id, Max, Current), sosud(_Id2, Max2, Current2), ...,...). %% Опустошение первого сосуда во второй mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0, Current3 is Current2 + Current, Current3 =< Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.

Все теперь работает! Как упражнение можно модифицировать программу, чтобы она находила переливания за оптимальное число шагов. Можете поэкспериментировать вот на этих задачках .

Замечание : ярые сторонники императивного программирования заметят, что все, что мы сделали это перебор всех состояний с возвратами (проход в глубину), причем без использования эвристик, и будут абсолютно правы. Дело в том, что мыслить в Прологе нужно как раз не перебором, а описанием задачи и описанием проверки решения, а к императивности вычислений всегда нужно возвращаться для оптимизации, если она нужна! Двойственность природы - не минус, а плюс. Стоит также отметить, что крупные Пролог системы, очень хорошо адаптированы для поиска состояний с возвратами.

Заключение

Хотелось бы отметить, что задачи рассмотренные в данной статье являются этюдами для программирования на Прологе. Так как большинство из них занимает около 10-15 строк, то программист на Прологе в состоянии воспроизвести их по памяти при достаточном частом порешевании их. А возвращаться к ним обязательно стоит, так как это напоминает об искусстве программирования (точно так же как быстрая сортировка на C). Более сложные и более прикладные задачи для повседневного использования будут рассмотрены позже.

В конце аж 2 задачки на приз :

Как известно в функциональном и логическом всячески пытаются избежать программ с side эффектами, оборачивают их в монады, придумывают специальные концепции. Стандартная проблема - это проблема внешнего мира, например, запись данных в файл, невозможно откатить запись в файл или отменить отсылку нескольких байт по сокету, а следовательно бэктрекинг будет работать не совсем корректно. Совет один - не используйте для этих целей Пролог. Но есть такие предикаты, которые очень хороши и специфичны для Пролога, но имеют side effect. Пример assert (asserta, assertz): он добавляет в базу правил (фактов) простое правило (факт). Пример assert(prime(3)) : добавляет факт, что 3 простое число и запрос :-prime(X) , теперь будет выдавать 3, даже при пустой исходной программе.
Задача : написать декларативную версию assert , то есть при возврате программы по бэктрекингу факт не должен оставаться в памяти, а должен работать как логическое предположение.
Пример работы : запрос c(X) должен выдавать одно число 4 для следующей программы!
a(X) :- b(Y), X is Y + 1 . c(X) :- my_assert(b(3)), a(X). c(X) :- b(X).
В классической математической логике 2 теориям уделяется гораздо больше внимание, чем всем остальным - это теория множеств и теория предикатов . Между ними существуют определенная связь, одно выражается через другое и наоборот. Например, предикат - это множество значений на которых он истинен, и наоборот множество - это предикат принадлежности. Традиционная реляционная теория баз данных оперирует множествами, а Пролог оперирует - предикатами. В общем, задача состоит в том, чтобы выразить абсолютно традиционную для теории множеств операцию - операцию взятия множества всех подмножеств .
Задача : дан некоторый одноместный предикат a/1 (в общем случае множество элементов не ограничено, может быть бесконечно), написать предикат subset_a/1, который будет выдавать подмножества, состоящие из элементов множества a.
Пример : запрос subset_a(X) выдает X = , X = , X = , X = (порядок не важен):
a(1). a(2). subset_a(X) :- ....?

Спасибо за внимание.

Теги: Добавить метки

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

В октябре 1981 года Японское министерство международной торговли и промышленности объявило о создании исследовательской организации - Института по разработке методов создания компьютеров нового поколения (Institute for New Generation Computer Technology Research Center ). Целью данного проекта было создание систем обработки информации, базирующихся на знаниях. Предполагалось, что эти системы будут обеспечивать простоту управления за счет возможности общения с пользователями при помощи естественного языка. Эти системы должны были самообучаться, использовать накапливаемые в памяти знания для решения различного рода задач, предоставлять пользователям экспертные консультации, причем от пользователя не требовалось быть специалистом в информатике. Предполагалось, что человек сможет использовать ЭВМ пятого поколения так же легко, как любые бытовые электроприборы типа телевизора, магнитофона и пылесоса. Вскоре вслед за японским стартовали американский и европейский проекты.

Появление таких систем могло бы изменить технологии за счет использования баз знаний и экспертных систем. Основная суть качественного перехода к пятому поколению ЭВМ заключалась в переходе от обработки данных к обработке знаний. Японцы надеялись, что им удастся не подстраивать мышление человека под принципы функционирования компьютеров, а приблизить работу компьютера к тому, как мыслит человек, отойдя при этом от фон неймановской архитектуры компьютеров. В 1991 году предполагалось создать первый прототип компьютеров пятого поколения.

Теперь уже понятно, что поставленные цели в полной мере так и не были достигнуты, однако этот проект послужил импульсом к развитию нового витка исследований в области искусственного интеллекта и вызвал взрыв интереса к логическому программированию. Так как для эффективной реализации традиционная фон неймановская архитектура не подходила, были созданы специализированные компьютеры логического программирования PSI и PIM .

В качестве основной методологии разработки программных средств для проекта ЭВМ пятого поколения было избрано логическое программирование , ярким представителем которого является язык Пролог . Думается, что и в настоящее время Пролог остается наиболее популярным языком искусственного интеллекта в Японии и Европе (в США, традиционно, более распространен другой язык искусственного интеллекта -язык функционального программирования Лисп ).

Название языка "Пролог" происходит от слов ЛОГическое ПРОграммирование (PROgrammation en LOGique во французском варианте и PROgramming in LOGic - в английском).

Пролог основывается на таком разделе математической логики, как исчисление предикатов . Точнее, его базис составляет процедура доказательства теорем методом резолюции для хорновских дизъюнктов . Этой теме будет посвящена следующая лекция.

В истории возникновения и развития языка Пролог можно выделить следующие этапы.

В 1965 году в работе "A machine oriented logic based on the resolution principle", опубликованной в 12 номере журнала " Journal of the ACM ", Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название " принцип резолюции ". Эту работу можно прочитать в переводе: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции // Кибернетический сборник. - Вып. 7 (1970). На самом деле, идея данного метода была предложена Эрбраном в 1931 году, когда еще не было компьютеров (Herbrand, "Une methode de demonstration ", These, Paris, 1931). Робинсон модифицировал этот метод так, что он стал пригоден для автоматического, компьютерного использования, и, кроме того, разработал эффективный алгоритм унификации, составляющий базис его метода.

В 1973 году " группа искусственного интеллекта" во главе с Аланом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (от Programmation en Logique). Она и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алана Колмероэ. Программа была написана на Фортране и работала довольно медленно.

Большое значение для развития логического программирования имела работа Роберта Ковальского " Логика предикатов как язык программирования " (Kowalski R. Predicate Logic as Programming Language . IFIP Congress, 1974), в которой он показал, что для того чтобы добиться эффективности, нужно ограничиться использованием множества хорновских дизъюнктов . Кстати, известно, что Ковальский и Колмероэ работали вместе в течение одного лета.

В 1976 г. Ковальский вместе с его коллегой Маартеном ван Эмденом предложил два подхода к прочтению текстов логических программ: процедурный и декларативный. Об этих подходах речь пойдет в третьей лекции.

В 1977 году в Эдинбурге Уоррен и Перейра создали очень эффективный компилятор языка Пролог для ЭВМ DEC–10, который послужил прототипом для многих последующих реализаций Пролога. Что интересно,

Лекция посвящена решению задач при помощи графа пространства состояний. Пространство состояний описывается в виде множества состояний – вершин графа, множества переходов от состояния к состоянию – дуг графа, множества начальных состояний и множества конечных состояний. Решение задачи представляется в виде пути на графе пространства состояний, соединяющего начальное состояние с конечным. Если пространство состояний задачи невелико, то будут находиться все оптимальные решения с помощью поиска в глубину. В задачах с большим пространством состояний будет вычисляться только одно оптимальное решение посредством поиска в ширину. К задачам применяются универсальные решатели. Состояния в разных задачах могут принадлежать различным доменам. Для запоминания наилучших среди найденных решений используется "изменяемая переменная" varM. Компилятор сам находит нужные типы. Версия Visual Prolog 7.5, еще не опубликована. Ее публикация планируется в 2014 году, но точная дата пока не известна. Сейчас всем доступна версия Visual Prolog 7.4.

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

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

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

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

Таблица 1. Синтаксис логики предикатов

2. Факты

На Прологе описываются объекты (objects ) и отношения (relations ), а затем описывает правила (rules ), при которых эти отношения являются истинными. Например, предложение

Билл любит собак. (Billlikesdogs.)

устанавливает отношение между объектами Bill и dogs (Билл и собаки); этим отношением является likes (любит). Ниже представлено правило, определяющее, когда предложение "Билл любит собак" является истинным:

Билл любит собак, если собаки хорошие. (Bill likes dogs if the dogs are nice.)

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

Ниже представлено несколько предложений на естественном языке с отношением "любит" (likes):

Билл любит Синди. (Bill likes Cindy)

Синди любит Билла. (Cindy likes Bill)

Билл любит собак. (Bill likes dogs)

А теперь перепишем эти же факты, используя синтаксис Пролога:

likes(bill, cindy).

likes(cindy, bill).

likes (bill, dogs).

Факты, помимо отношений, могут выражать и свойства. Так, например, предложения естественного языка "Kermitisgreen" (Кермит зеленый) и "Caitlinisgirl" (Кейтлин - девочка) на Прологе, выражая те же свойства, выглядят следующим образом:

3. Предикаты

Отношение в Прологе называется предикатом. Аргументы - это объекты, которые связываются этим отношением; в факте

likes (bill, cindy).

отношение likes - это предикат, а объекты bill и cindy - аргументы.

Примеры предикатов с различным числом аргументов:

pred(integer, symbol)

person (last, first, gender)

birthday(firstName, lastName, date)

В примере показано, что предикаты могут вовсе не иметь аргументов.

4. Правила

Правила позволяют вам вывести один факт из других фактов. Другими словами, можно сказать, что правило - это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными. Ниже представлены правила, соответствующие связи "любить" (likes):

Синди любит все, что любит Билл. (Cindy likes everything that Bill likes)

Кейтлин любит все зеленое. (Caitlin likes everything that is green)

Используя эти правила, вы можете из предыдущих фактов найти некоторые вещи, которые любят Синди и Кейтлин:

Синди любит Синди. (Cindy likes Cindy)

Кейтлин любит Кермит. (Caitlin likes Kermit)

Чтобы перевести эти правила на Пролог, вам нужно немного изменить синтаксис:

likes(cindy, Something):- likes (bill, Something). ilikes(caitlin, Something):- green (Something) .

Символ:- имеет смысл "если", и служит для разделения двух частей правила: заголовка и тела. Можно рассматривать правило и как процедуру. Другими словами, правила

likes(cindy, Something):- likes (bill, Something).

likes(caitlin, Something):- green (Something).

означают: "Чтобы доказать, что Синди любит что-то, докажите, что Билл любит это " и "Чтобы доказать, что Кейтлин любит что-то, докажите, что это что-то зеленое" . С такой "процедурной" точки зрения правила могут "попросить" Пролог выполнить другие действия, отличные от доказательств фактов, например, напечатать что-нибудь.

5. Запросы (Цели)

Описав в Прологе несколько фактов, можно задавать вопросы, касающиеся отношений между ними. Это называется запросом (query) системы языка Пролог. Можно задавать Прологу такие же вопросы, которые мы могли бы задать вам об этих отношениях. Основываясь на известных, заданных ранее фактах и правилах, вы можете ответить на вопросы об этих отношениях, в точности так же это может сделать Пролог. На естественном языке мы спрашиваем: Does Bill like Cindy ? (Билл любит Синди?) По правилам Пролога мы спрашиваем:

likes(bill, cindy).

Получив такой запрос, Пролог ответит:

потому что Пролог имеет факт, подтверждающий, что это так. Немного усложнив вопрос, можно спросить на естественном языке: What does Bill like ? (Что любит Билл?) По правилам Пролога мы спрашиваем:

likes(bill, What).

Необходимо отметить, что второй объект - What -начинается с большой буквы, тогда как первый объект - bill - нет. Это происходит потому, что bill - фиксированный, постоянный объект - известная величина, aWhat - переменная.

Переменные всегда начинаются с заглавной буквы или символа подчеркивания!

Пролог всегда ищет ответ на запрос, начиная с первого факта, и перебирает все факты, пока они не закончатся . Получив запрос о том, что Билл любит, Пролог ответит:

Так, как ему известно, что

likes(bill, cindy).

likes(bill, dogs) .

Если бы мы спросили:

What does Cindy like? (Что любит Синди?)

likes(cindy, What).

то Пролог ответил бы:

поскольку Пролог знает, что Синди любит Билла, и что Синди любит то же, что и Билл, и что Билл любит Синди и собак.

Мы могли бы задать Прологу и другие вопросы, которые можно задать человеку. Но вопросы типа "Какую девушку любит Билл?" не получат решения, т. к. Прологу в данном случае не известны факты о девушке, а он не может вывести заключение, основанное на неизвестных данных: в этом примере мы не дали Прологу какого-нибудь отношения или свойства, чтобы определить, являются ли какие-либо объекты девушками.

6. Размещение фактов, правил и запросов

Предположим, есть следующие факты и правила:

Быстрая машина - приятная. (Afastcarisfun).

Большая машина - красивая. (A big car is nice).

Маленькая машина - практичная. (A little car is practical).

Биллу нравится машина, если она приятная. (Bill likes a car if the car is fun).

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

Вот пример, демонстрирующий, как Пролог использует правила для ответа на запросы. Посмотрите на факты и правила в этой части программы ch02e01.pro:

likes(ellen, tennis).

likes (John, football).

likes (torn, baseball).

likes (eric, swimming).

likes (mark, tennis).

likes (bill, Activity):- likes (torn, Activity).

Последняя строка в программе является правилом. Это правило соответствует предложению естественного языка:

Биллу нравится занятие, если Тому нравится это занятие. (Bill likes an activity if Tom likes that activity)

В данном правиле заголовок - это likes (bill, Activity), а тело - likes (torn, Activity). Заметим, что в этом примере нет фактов о том, что Билл любит бейсбол. Чтобы выяснить, любит ли Билл бейсбол, можно дать Прологу такой запрос:

likes (bill, baseball).

Пытаясь отыскать решение по этому запросу, Пролог будет использовать правило:

Загрузите программу ch02e01.pro в среду визуальной разработки VisualProlog и запустите ее утилитой TestGoal.

likes(symbol,symbol)

likes(ellen,tennis).

likes(John,football).

likes(torn,baseball).

likes(eric,swimming).

likes(mark,tennis).

likes(bill,Activity):-likes(torn, Activity).

likes(bill, baseball).

Утилита TestGoal ответит в окне приложения: