22 июля 2011 в 17:57

Prolog — удивительный язык программирования

— Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости.

Пролог — уникален. Это единственный язык представляющий парадигму декларативного программирования; это язык, который имеет сотни различных имплементаций, но они все равно называются Prolog, добавляя лишь префиксы и суффиксы к названию; это живой язык в котором не происходит никаких существенных изменений более 20 лет; это, наверное, единственный настолько популярный язык программирования, который не имеет применения в реальном программировании. Почему же Prolog?

Пролог — уникален по своей природе, он появился благодаря счастливому совпадению (таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования — это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.

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


Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+, от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток :)

Как правильно читать программы на прологе


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

Понятия

В языке существует 2 понятия предикаты (условия) и объекты (они же переменные и термы). Предикаты выражают некоторое условие, например объект зеленый или число простое, естественно что условия имеют входные параметры. Например green_object(Object), prime_number(Number) . Сколько в предикате параметров, такова и арность предиката. Объектами — являются термы, константы и переменные. Константы — это числа и строки, переменные — выражают неизвестный объект, возможно искомый, и обозначаются как строчки с большой буквы. Оставим пока термы и рассмотрим простейшую программу.

Программа

Программа — это набор правил, вида Если условие1 и условие2 и… то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).

A :- B_1, B_2. % правило читается как : Если B_1 и B_2, то A
нечетное_простое(Число) :- простое(Число), нечетное(Число).
% Если "Число" - простое и нечетное, то "Число" - нечетное_простое


Как видно имя переменной имеет область видимости — это правило. Математически верно, правило звучит: для любой переменной — «Число», если оно простое и нечетное, то оно простое_нечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетно_простое. Поэтому имя переменной очень важно! Если в левой части (до :- ) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число — простое и нечетное, то Число2 — простое нечетное. Получается все числа простые_нечетные! Это самая распространенная ошибка в Прологе.

A :- B_1, B_2.  % правило читается как : Если B_1 и B_2, то A 
нечетное_простое(Число) :- простое(Число), нечетное(Число).
% Если "Число" - простое и нечетное, то "Число" - нечетное_простое



Пример — совершенные числа

совершенное_число(Ч) :- число(Ч), сумма_делителей_без_числа(Ч, СуммаДелителей), 
            равно(СуммаДелителей, Ч).
совершенное_число(1).

равно(Объект, Объект).
сумма_делителей_без_числа(1, 1).
сумма_делителей_без_числа(Число, Сумма) :- число_предыдущее(Число, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).

сумма_делителей_числа_до_числа(Число, 1, 1).
сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- делится_на(Число, Делитель), 
             число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, СуммаПред, Предыдущее),  сложить(СуммаПред, Делитель, Сумма).
сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- не_делится_на(Число, Делитель), 
            число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).




Для начала формально прочитаем, что означают правила:
  1. Если «Ч» — число и для «Ч» и «СуммаДелителей» выполняется условие сумма_делителей_без_числа, проще говоря СуммаДелителей есть сумма делителей числа «Ч», и «Ч» равно «СуммаДелителей», то «Ч» совершенное число.
  2. 1 — совершенное число. Правила могут не иметь условий, в этом случае они называются фактами.
  3. Всякий объект «О» равен «О». В принципе существует, стандартный предикат "=", но можно вполне заменить на свой.
  4. Факт сумма_делителей_без_числа 1 равна 1.
  5. Если сумма делителей «Число» до предыдущего числа «Число» равна «Сумма», то это и есть сумма_делителей_без_числа. Таким образом выражается, сумма делителей X меньше либо равных Y, так как X делится на X, поэтому берем Y = X — 1.
  6. Далее 3 предиката определяют сумму делителей число меньше либо равных Y (Делитель), 1-й случай Y равное 1, 2-й случай Число делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1) + Y, и 3-й случай Число не делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1).


Программа — как набор определений

Существует второй способ прочтения данных правил, менее математический и более естественный, основанный на «определениях». Можно заметить, что в Прологе все правила слева (в части то) содержат только одно условие, что по сути является «определением» это условия.
Например, 1-ое правило определение совершенных чисел. «Ч» совершенное число, когда «Ч» число и сумма делителей «Ч» равна «Ч». Одинаковые предикаты группируются по имени объединяясь условием «или». То есть к определению можно добавить: «Ч» совершенное число, когда .., или когда «Ч» — это 1.

Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы
проверить истинность некоторого утверждения. Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делится_на».

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

Термы

Термы имеют рекурсивное определение, как именованная совокупность объектов. Терм = 'имя'(объект, объект, ...), пример person('Name', 'Surname'), '+'(1, 2), person(address('Некоторый адрес'), surname('Фамилия'), phone('Телефон')) . Если рассматривать терм, как математическое понятие, то терм является функцией, а точнее функтором, то есть '+'(1, 2) — означает, что существует такой объект, который равен 1+2. Это абсолютно не означает, что 1+2 = 3, в Прологе — это выражение неистинно, точно так же как и в группе остатков по модулю 2, там 3 вообще не существует. Опять же с математической точки зрения Переменные связываются словом Для Всех, а если в утверждении необходимо слово существует то, для этой цели применяется терм (функтор). Для любого числа существует число-факториал :- factorial(X, fact(X)).

С точки зрения программирования терм можно объяснить гораздо проще: терм — это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние — переменная.

Пример — целочисленная арифметика

  нат(0). 
  нат(число(Число)) :- нат(Число).

  плюс(0, Число, Число).
  плюс(число(Ч1), Ч2, число(Рез)) :- плюс(Ч1, Ч2, Рез).

  умножить(0, Число, 0).
  умножить(число(Ч1), Ч2, Рез2) :- умножить(Ч1, Ч2, Рез), плюс(Рез, Ч2, Рез2).


  1. Определение свойства нат (натуральное число). 0 — натуральное число, если Число натуральное, то существует объект число(Число), которое тоже является натуральным. Математически терм «число» выражает функцию +1, с точки зрения программирования «число» рекурсивная структура данных, вот ее элементы: число(0), число(число(0)), число(число(число(0))).
  2. Отношение плюс — 0 + Число = Число. Если Ч1 + Ч2 = Рез, то (Ч1+1) + Ч2 = (Рез+1).
  3. Отношение умножить — 0 * Число = 0. Если Ч1 * Ч2 = Рез и Рез + Ч2 = Рез2, то (Ч1+1) * Ч2 = Рез2.

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

Как Prolog понимает предикаты и как доказывает утверждения


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

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

Рассмотрим на примере запроса плюс(0, 0, Результат) :
1. Находим совпадение (своеобразный pattern-matching, резолюция) данного запроса с левой частью одно из правил. Для данного запроса плюс(0, Число, Число). Соотнесем поочередно все аргументы запроса с правилом и получим: 0 = 0, 0 = Число, Результат = Число. В этих уравнениях участвуют 2 переменные (Число и Результат), решив их мы получаем, что Число = Результат = 0. Так как у данного правила нет условий, мы получили ответ на заданный вопрос. Ответ: да и Результат = 0.

Запрос нат(Число) :
1. Находим 1-е совпадение с правилом, правило нат(0), решая уравнения по соответствию, проще говоря находя резолюцию, мы получаем Число = 0. Ответ: да и Число = 0.

Запрос плюс(Результат, 0, число(0)):
1. Находим резолюцию с правилом плюс(0, Число, Число): Результат = 0, 0 = Число, число(0) = Число, но (!) Число = 0 = число(0) — не возможно так как 0 совпадает число(0). Следовательно ищем резолюцию со следующим правилом.
2. Находим резолюцию с правилом плюс(число(Ч1), Ч2, число(Рез)), получаем число(Ч1) = Результат, Ч2 = 0, число(Рез) = число(0), отсюда Рез = 0. У этого правила, есть условия которые мы должны проверить, учитывая результаты резолюции (значения переменных), плюс(Ч1, Ч2, Рез) -> плюс(Ч1, 0, 0). Запоминаем значение переменных в стеке и формируем новый запрос плюс(Ч1, 0, 0)
3*. Решая запрос плюс(Ч1, 0, 0) находим резолюцию с плюс(0, Число, Число) и получаем Ч1 = 0 и Число = 0.
4. Возвращаемся по стеку к предыдущим переменным Результат = число(Ч1) = число(0). Ответ найден число(0). Соответственно сейчас пролог машина решила уравнение X + 0 = 1.

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

Пример запроса плюс(Число, Число, Число): ответ да, Число = 0.

Пример запроса плюс(0, 0, 0): ответ нет, при первой же попытке все резолюции не выполняются.

Пример запроса плюс(Число, Число, число(Число)): ответ да, Число = 1. Решение уравнения X + X = X + 1.

Попробуйте провести вывод для умножить(Число, число(0), число(0)), для этого потребуется 2 раза заносить в стек переменные и вычислять новый запрос. Суть Пролог машины такова, что вы можете отказаться от 1-го результата, тогда Пролог вернется к предыдущему состоянию и продолжит вычисление. Например запрос нат(Число), сначала применит 1-е правило и выдаст 0, а затем применит 2-е правило + 1-е правило и выдаст число(0), можно повторить и получить бесконечную последовательность всех натуральных чисел. Другой пример, запрос плюс(Число, число(0), Число2), будет выдавать последовательность всех пар решения уравнения X + 1 = Y.

Заключение


К сожалению, разумный размер топика, не дал мне подобраться к главной теме, а именно к решению сложных логических задач на языке Пролог, не обладая стратегией их решения. Большие куски кода на Прологе могут отпугнуть не только начинающих, но даже опытных программистов. Цель данной статьи показать, что программы на Прологе могут простым образом читаться на естественном языке, а также исполняться простейшим интерпретатором.
Главная особенность Пролога — это не черный ящик и не библиотека, который решает сложные логические задачи, в Mathematica можно ввести алгебраическое уравнение и она выдаст решение, но последовательность выполняемых шагов — неизвестна. Пролог не может решать общие логические задачи (у него отсутствует логическое «или» и «отрицание»), иначе бы его вывод был недетерминированный как линейной резолюции. Пролог — это золотая середина, между простым интерпретатором и машиной для доказательства теорем, сдвиг в любую сторон приводит к потери одного из свойств.

В следующей статье я бы хотел рассказать, как решаются задачи сортировки, о последовательности переливаний, Miss Manners и другие известные логические задачи. Для тех, кто почувствовал себя неудовлеторенным хочу предложить следующую задачу (решившему первым приз):
Написать предикат, который бы генерировал, бесконечную последовательность натуральных чисел, начиная с 3. Это должны быть стандартные числа в Прологе, операции над которыми выполняются при помощи предиката is: X is 3 + 1 => X=4.
+85
33486
120
vics001 44,0

Комментарии (113)

+36
Barsik107, #
Мне выносили моск этим языком на 4 курсе, но я не поддался.
+6
vics001, #
Как писал Joshua Bloch: на втором курсе у нас отсеивалась большая половина, потому что не понимала как работать с указателями; я бы перефразировал на 4-м курсе можно отсеивать всех, кто не может перевернуть список на Прологе :)
0
Alukardd, #
Да именно переворотом и не только нам имели мозг!!!
0
sylvio, #
Переворот, кстати, можно сделать очень красиво:

reversed([], []).
reversed([Head|Tail1], [Tail2|Head]) :- reversed(Tail1, Tail2).
0
vics001, #
Долго смотрел на ваше решение не мог понять почему работает, запустил и действительно работает странно (лишние списки появляются):

reversed([], []).
reversed([Head|Tail1], Res) :- reversed(Tail1, Tail2), append(Tail2,[Head], Res).

Но так уже менее красиво и не так эффективно :(
0
Kuznetsov, #
А мне на втором)
0
1vanu4, #
Повезло… Нам на первом семестре взрывали мозг ЛИСПом и ПРОЛОГом =(
0
1vanu4, #
*уже взрывали
+5
p_a, #
Неужели lisp так уж взрывает мозг? Мне кажется, напротив, приводит мысли в порядок при правильном подходе.
+2
1vanu4, #
Наверное Вы правы. Но учить одновременно ЛИСП и ПРОЛОГ на первом семестре было немного хардкорно.
0
Danov, #
Пролог тоже мысли в порядок приводит. Любой ИТ девелопер должен знать Пролог, ведь это методологическая основа SQL.
0
sylvio, #
Пожалуйста, обоснуйте.
SQL это такая реляционная алгебра со свистульками и перделками. То, что они оба декларативны не делает их родственниками.
0
Edro, #
аналогично
+1
Finom, #
У нас Пролог был на втором и пятом курсе. На втором я его понимал, мог сам писать программки, а на пятом вообще не мог понять что это за хрень :)
0
xmdy, #
От написанных мной программ у преподавателя случался взрыв мозга и он ставил зачет не вникая в логику, просто проверял результаты работы))
+3
isden, #
> Мне выносили моск этим языком на 4 курсе, но я не поддался.

Имхо зря… Подобные языки дают очень много экспы и нехило прокачивают скиллы.
+8
Brand, #
+14
vics001, #
0
FINTER, #
Вот объясните мне глупому, что сложного в прологе?
Писать на нем не сложнее чем писать регекспы. Просто нужно понять метод резолютивного спуска и основы матлогики. Делов то…
+3
vics001, #
Писать на нем как минимум не обычно. Имхо написание регекспов проще чем написание программ на Прологе.
Можно сравнить регексп — это конечные автоматы и автоматные грамматики, а Пролог — это контекстно независимые языки :)
0
Barsik107, #
Это было бы смешно, если бы не было так грустно.
+1
Barsik107, #
А все, кто со мной не согласны — назовите хоть один ныне существующий проект, который написан на прологе.
+3
vics001, #
Я обязательно расскажу в статье в каких случаях можно использовать Пролог коммерческих, государственных и opensource проектах. Ссылку на один приводил ниже, а кратко используйте для чего он предназначен, для декларативного описания задач.
0
denisig, #
0
Danov, #
Erlang основан на Prolog, отчасти
+1
Airog, #
Помните Буран который сам летал в космос? Так вот программа которая управляла им была написана на языке очень похожим на пролог, т. е. как бы был создан специализированный пролог.
0
karantir, #
И язык этот назывался Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность, для друзей просто ДРАКОН
0
Infthi, #
пролог вроде как используется для верификации байт-кода JVM, см. JSR 202
0
alexeygrigorev, #
Зря вы так, хороший язык. Мыслить заставляет совсем иначе, не так, как императивные языки программирования.
0
Gruxon, #
Я поддался. В день сдачи. Но в этот же день забыл как его понимать.
–2
Artoha, #
Ну молодец автор, что тут. Написал отличную статейку…
НЛО прилетело и опубликовало эту надпись здесь
+3
vics001, #
Назовите еще языки этой парадигмы? Mercury я бы не брал в счет, по сути дела, такой же Пролог, просто с разными фишками из функционального программирования. Возможно Рефал можно назвать другим языком.

Пролог не печален :) Просто порог вхождения крайне высок, я периодически слежу за обновлениями XSB и SWI-Prolog и поверьте они развиваются. Среду разработки можно взять Eclipse с плагином.

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

Хотя могу привести пример: я использую сейчас Пролог для настройки голосовой помощи на разных языках, так как числа читаются абсолютно по-разному в разных языках, то файлы конфигураций в виде правил Пролога идеально подходят :), обычные property файлы просто не дают гибкости. И между прочим много пользователей прекрасно справилось с локализацией своего языка при помощи Пролога.
НЛО прилетело и опубликовало эту надпись здесь
+1
Kyborg2011, #
HTML не совсем язык программирования. Согласно Википедии:
HTML (от англ. HyperText Markup Language — «язык разметки гипертекста») — стандартный язык разметки документов во Всемирной паутине.
+4
GreyCat, #
Технически, есть мнение, что «декларативные» языки — это такой странный термин, который включает в себя сразу всё, что не включается в «императивные» языки — т.е. и логические (Prolog, Mercury), и функциональные (Lisp и все-все-все), и DSL (HTML, XML, CSS, XSLT, Make), и dataflow-ориентированные (Clojure, PD, Simulink, LabView и т.д.)

В этом плане — термин — спорный, и если говорить про логические и constraint-ориентированные языки — то, о чем статья, собственно — то там действительно вариантов кроме Prolog и тучи его диалектов — явно немного. Mercury да Oz, по сути. Ну, Erlang еще — с бооольшой натяжкой.
+5
Calvrack, #
Разве make не декларативный язык?
0
vics001, #
Расскажите подробнее :) Например Ant вообще не полный язык по Тьюринга, когда-то писал на нем рекурсию, так нормально и не написал.
0
jtootf, #
И каким, простите, образом декларативность связана с полнотой по Тьюрингу? SQL, скажем, вполне себе декларативный eDSL запросов к реляционным БД — при этом ни разу не Тьюринг-полный. Agda2 — вполне себе декларативный функциональный язык с зависимыми типами (ну или система автоматического доказательства теорем, кому что ближе) — и тоже отличается прискорбной Тьюринг-худобой.
0
vics001, #
Конечно не связано, но полные по Тьюрингу интересны с другой стороны, тем, что они могут использоваться как язык общего назначения, то есть решать общие задачи.
В конце концов с чистой декларативностью можно прийти к XML и к текстовому описанию задачи.

Хотя прежде всего акцент хотел бы поставить на слове «программирования», так SQL я бы считал языком, но не программирования, а языком написания запросов к базе данных. По сути дела мы пишем запрос, но не можем предсказать как он будет выполняться.
0
jtootf, #
Предсказать, как будет выполняться наш код, мы можем только на языках низкого уровня: уже на уровне C уверенность в конкретном поведении железки будет сомнительной (что уж говорить о языках уровня C# или REBOL).
0
Litiy, #
Пролог единственный который я знаю язык логического программирования, но даааалеко не единственный декларативный. Haskell, Lisp реализуют парадигму декларативного программирования, например.

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

Пролог это язык для реализации алгоритмов с большим неявным перебором вариантов (логический вывод, нахождение зависимостей, перебор ходов в шахматах) и он действительно хорош, но достаточно неповоротлив в плане интеграции (я интегрировал visual prolog с .net).
0
vics001, #
Насчет интеграции не поворотлив, это отговорки ленивых, которые уже забыли как компилировать C код, того же XSB, и подключать нативные библиотеки. И тем более отговорки, потому как есть библиотеки, которые например обычный ассемблерный (конечно не любой), переводят в Java байткод.

Просто Пролог — не мейнстрим. А куда ему развиваться? Вы про какой Пролог? Мне кажется SWI-Prolog и XSB очень даже активно развиваются.

ИМХО, Visual Prolog не долюбливаю (извращенцы, писать UI на Прологе и операции присваивания).
0
jtootf, #
GUI на Prolog'е, к слову, прекрасно пишется с помощью XPCE (для SWI). С некоторыми оговорками по удобству эта библиотека приближается к Tcl/Tk.
0
norguhtar, #
Наш любимый SQL. Prolog язык логической парадигмы, а не декларативной все же.
НЛО прилетело и опубликовало эту надпись здесь
+1
vics001, #
SQL не язык программирования, вот об этом я пытался сказать. То что он интерпретируется некоторой машиной не делает его языком программирования, напишите на SQL вычисление факториала хотя бы :)
+3
vics001, #
Ну так и что декларативного в PL/SQL? Обычные циклы, присваивания — императивный язык, такой же как Basic принципиально. Запросы SQL92 действительно декларативны.
0
alexkolzov, #
Язык программирования не обязательно является полным по Тьюрингу. SQL — язык программирования, поскольку позволяет писать программы
0
jtootf, #
Вы очень легко (и неосторожно) оперируете формальными определениями. Тьюринг-полнота не является обязательным условием для того, чтобы называть некоторый язык языком программирования. Даже ЯП общего назначения не обязан быть Тьюринг-полным (хотя, как правило, это подразумевается) — для доменных языков это в большинстве случаев просто вредно.
0
alexkolzov, #
Декларативные языки программирования включают несколько подклассов, логические только один из них. К декларативным относятся все функциональные языки (чисто функциональные), языки запросов к базам данных и т.д. Вообще язык реализует декларативную парадигму программирования, если с его помощью описывается в большей степени определение задачи, а не конкретный алгоритм ее решения.
Пролог яркий, но не единственный логический язык программирования. Например существует его ровесник Дейталог, тоже логический, хотя основан на другой теории.
+1
akalend, #
в далекие 90-е пытался написать на Прологе экспертную систему по диагностике.
теперь я его уже наверно забыл. Спасибо что Вы вспомнили о нем, было приятно вспомнить.
0
EugeneBond, #
аха… я тоже про курс экспертных систем вспомнил.
правда нас на лабораторном практикуме мучали расчетами прогнозов погоды. у большинства студентов результат был близок к результату главных метереологических служб — нифига не совпадало с реальностью :)
+3
shwars, #
Спасибо за статью в стиле «Пролог за 10 минут». Не согласен с тем, что Пролог — единственный. Есть намного более современные и интересные логические языки — например, Mercury. И с точки зрения выноса мозга студентам он лучше… поэтому я разбавляю им свой курс Логического программирования :)
0
vics001, #
Пролог — может и не современный, зато абсолютно чистый :) И чем больше я пишу на нем, тем меньше я хочу чтобы в нем вообще что-то менялось. Я даже готов убрать все предикаты по чтению файлов, сокетов, все эти императивные штуки, отсечение хочется отрезать, оставив только not — предикат.

Для меня будущее Пролога в связке с другими языками
0
shwars, #
Пролог совсем не чистый (pure), если под чистотой понимать соответствие процедурной и декларативной семантики. Вот Mercury — намного чище, и в нем как раз нет отсечения, но есть not (отрицание по неуспеху)и условная конструкция ->.

Насчет связки — на 100% согласен. И ещё — мозги, промытые Прологом, потом лучше думаю даже в императивных категориях.
0
vics001, #
Условная конструкция (; ->) легко выражается и на чистом Прологе с использованием отсечения.

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

Да, под «чистым» Прологом, я понимаю Пролог без отсечения, хотя в реальности чистый Пролог практически не применим, но с него обязательно надо начинать. А потом уже ISO Prolog, Mercury.
+1
Traut, #
можете показать примеры относительно свежего real-life софта, написанного на прологе? веб/не-веб? интересно насколько сложные продукты можно создать сегодня на прологе
0
vics001, #
Я писал выше использовать лучше всего Prolog в связке с другими языками, так я и поступаю. Особенно мне нравится возможность создания в Прологе DomainSpecificLanguage, об этом я обязательно хотел бы рассказать.

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

В написании программ на Прологе сегодня, абсолютно нет необходимости, хотя для многих задач он подходит гораздо лучше.
0
tranquil, #
Интересно как использовать пролог в связке с другими языками и какую реализацию использовать?

Я так и не нашёл ни одной годной реализации, всё очень примитивно.

Выяснил, что SWI-Prolog это самая продвинутая реализация. Так вот это очень недоразвитый проект. Ничего практически полезного с ним сделать нельзя. Документация по интеграции с другими системами ужасная. Очень сложный сишный код, который периодически падает по непонятным причинам.

Например, code.google.com/p/pyswip/ — библиотека работы с swi-prolog из python. Есть аналогичная библиотека для хаскеля hackage.haskell.org/package/hswip. Попробуйте сделать с их помощью многопоточную программу. Чтобы с интерпретатором могли работать сразу несколько потоков. Это невозможно.

Я думаю что у пролога большое будущее. Но писать исполняемый код на нём большое извращение.
Пролог идеален только в качестве языка запроса к дедуктивным базам данных. В конце концов SQL это частный случай пролога. На прологе можно намного проще делать всякие outer join и выполнять рекурсивные запросы без использования хранимых процедур. Реально проще.

Осталось только написать такую дедуктивную СУБД.
0
dgudkov, #
на прологе сегодня можно создавать такие же сложные продукты как и 25 лет назад, когда на нем была написана программа автоматической посадки «Бурана»

www.rsdn.ru/forum/education/4219574.flat.aspx

ЗЫ. Очень мне нравился пролог в институте, жаль не получил он более широкого применения — например в системах бизнес-анализа. Надеюсь что рано или поздно это исправится.
0
Danov, #
После изучения Prolog моей первой мыслью было «Почему на нем не делают бухгалтерскую систему?». И то что в 1С заложен императивный язык — это недоразумение.
0
Dementor, #
Потому что бухгалтерский, а особенно налоговый учет в наших СНГшных краях крайне нестабилен. И для успешных бух. и нал. решений необходима система с возможностями быстрого внесения модификаций.
Вот выпустили налоговики очередное письмо-разъяснение, которое отличается от предыдущих какой-то мелочью — в 1С нужно только формулу подредактировать (иногда даже без перезапуска рабочей базы, если это касается расчета зарплаты), а на языке логического программирования пришлось бы половину программы переписать, что бы подстроится под «прихоти» налоговиков (а через месяц они еще что-то потребуют изменить в расчетах угрожая за невыполнение штрафами).
0
vics001, #
Что вы такое рассказываете :) Как быстро обновить можно базу данных? Представьте все ваши правила по расчету 1С бухгалтерии лежат в таблице базы данных: запустив один SQL Update вы можете за 1 секунду внести изменения, причем не останавливая работу БД.

Пролог по сути дела та же БД только там можно хранить не только факты, но и правила. Существуют такие запросы как assert/retract. На практике вы конечно можете столкнуться со скомпилированными предикатами в некоторых имплементациях, но если иметь эту функциональность в виду, то все будет тип топ.

Еще одно замечание: База Данных, Пролог, возможно 1С скрипт, более понятный инструмент для непрограммистов, чем языки общего назначения — C, Java, Basic.
0
Dementor, #
Не могу с вами спорить, так как пролог изучал только на протяжении одного семестра (и это был Turbo Prolog). Хочу только отметить, что ставки и границы налогов, формулы расчета зарплатных начислений делаются в 1С в пользовательском интерфейсе без необходимости делать запросы на языке SQL к БД.

Править код нужно при более сложных изменениях. Пример из жизни за эту зиму/весну — налоговики хотели сначала что бы рассчитывали ЕСВ, а потом облагали разность с начислением 15% до границы и 17% все что свыше, но по результатам месяца получения взносов они увидели, что денег приходит чуть меньше чем они хотели и они выпустили разъяснение, что нужно сначала обложить начисления 15% и 17% процентами, а из остатка вычитать ранее рассчитанный ЕСВ (таким образом завышена база для 17%). Так вот в письме все очень просто — разъяснение дается с формулами знакомыми всем по школьной алгебре. Такие правки легко и просто вносить «неспециалистам» (достаточно найти только «где»). А вот сможет ли среднестатистический выпускник школы со знаниями алгебры и с пониманием «что от него хотят налоговики» подправить правила Пролога?

Вероятно по этой причине императивные языки (такие как 1С, Basic, Pascal, С, Java и прочие) более популярны и понятны для неспециалистов, чем логические и функциональные.
0
vics001, #
Согласен с вами, но вы говорите об инфраструктуре программы 1С, а не языка. Если пользователям дать удобный интерфейс редактировать таблицы в БД и рассказать в какой таблице подредактировать, то он прекрасно будет справляться и даже полюбит эту функциональность, так как никого не надо будет звать.

Вершиной программирования для непрограммистов я все же считаю Excel, потому что людям не надо пользоваться дополнительными программами и не надо искать (!), где редактировать. Все прямо in place (WYSIWIG). К сожалению Excel зародился standalone программой, а если бы он изначально использовался как корпоративная база данных и база функций, то ничего бы другого и не надо было.
0
Dementor, #
Согласен с обоими утверждениями.
0
denisig, #
+1
SFx, #
Спасибо за статью.
6 лет назад я писал курсачи всей группе по нему, одной левой ногой. сейчас же все забыл.
0
alexzzam, #
Про задачу. Если плюс работает и число есть, всё же просто, нет?
good(3).
good(y is x + 1) :- good(x).
0
vics001, #
Нет так не правильно, по крайней мере ISO Prolog — не пропустит :)
good(y is x + 1) :- good (x).

В первую очередь не понятно, x, y — переменные? Тогда должны быть с большой буквы.
Если переписать в безоператорный вид, ваша программы выглядит так:

good(3).
good(is(Y, '+'(X, 1)) :- good(X).

Надеюсь можете представить, что программа будет выводить на запрос :- good(X). ;)
0
alexzzam, #
А!
То есть, второе правило должно быть таким?
good(Y) :- is(Y, '+'(X, 1)), good(X).
0
vics001, #
Вот вы и пришли ко второй ошибке :)
Y is X + 1. Зафейлится на любом Прологе, потому что у оператора is справа не должно быть переменны, а X переменная.
0
vics001, #
Но идея правильная для чистого Пролога.

good(s(s(s(0)))).
0
vics001, #
good(Y) :- Y = s(X), good(X).
0
alexzzam, #
Ну, в условиях-то задачи было, что можно пользоваться плюсом, is и нормальными числами, поэтому я и не возился с этим инкрементом.
К слову, а в чём отличие is от других? Вот я могу написать abc(X, Y), но не могу is(X, Y)?
И если в одной из частей is можно использовать только константные выражения, он кажется довольно бесполезной штукой.
0
vics001, #
Дело в том, что абстрактные математические числа — это вещь в себе. Но как число 4, 5, которое вполне конкретное для процессора, может сложиться с переменной? В общем числа это нечто неродное для Пролога, интересность задачи, что даже с неродным можно работать.
+2
sudoers, #
Сегодня пролог это игрушка, с современными БД он работать не обучен. Это следствие того что язык давно не развивается (или наоборот, потому что нет БД он и не развивался).
–1
dgudkov, #
Современные БД (реляционные) не очень-то и современные — они все построены на принципах заложенных 30 лет назад, в середине 70-х. Просто тогда идея реляционных БД получила больший вес, а декларативные СУБД не получили распространения.
+3
sudoers, #
Я не про БД говорю, а про то что пролог не умеет работать с большим объемом данных, а без этого он для реальных проектов БЕСПОЛЕЗЕН.
0
dgudkov, #
не разглядел фразы про большие объемы данных в вашем комменте
0
vics001, #
Хм, во-первых Пролог сам по себе большая БД, с очень удобным языком запросов!
Во-вторых что вы понимаете под объемами? Да не переживайте в последних Пролог системах, давно уже сняли ограничения на 2 Mb объем памяти :)

Да и есть примочки к базам данным, используя odbc, все таблицы в этом случае представляются как базы фактов и бэктрекинг поддерживается, изнутри SQL.
0
vics001, #
Только не подумайте заменять Oracle на Prolog. Заказчик вас не поймет :)
0
alexkolzov, #
Это неверно. В основе Пролога и реляционных баз данных очень схожая теория. Лет двадцать назад разрабатывались системы связывания пролога и реляционных баз данных (CPR-системы), которые позволяли получать очень хорошие интенсиональные базы данных
+1
denim, #
два зачета, алгоритмика и пролог. препод по первому предмету предложил написать логическую игру, если он проиграет — зачет. по второму надо было написать хоть что то, никто мало кто что в прологе понимал. в итоге родились реверси на прологе — два зачета одним выстрелом ))
0
stoodiakv1, #
подскажите ламеру, в какой среде можно на прологе писать? «а то я что-то не до пёр»
0
Finom, #
Turbo Prolog :)
0
Velitsky, #
Вооружись книгой Братко «Алгоритмы искусственного интеллекта на языке PROLOG» и получай удовольствие. Как ещё один вариант можешь иметь ввиду систему Strawberry Prolog
0
SHVV, #
Спасибо за статью.
Вспомнилось, как в институте писал на Prolog-е крестики-нолики в бесконечном n-мерном пространстве.
Точнее, игра называется «Гомоку Нарабе».
0
susl, #
Я тоже писал это в универе :) Я думаю на каждом курсе кто-то да и напишет реализацию этой игры на Прологе
+2
Velitsky, #
Для начала скажу, что мне тоже кажется неправильным говорить что Пролог единственный декларативный или «логический» язык программирования. В каком-то смысле это даже не совсем язык программирования, ведь все задачи решаются одним и тем же методом — перебора. Но его описательная мощь и простота удивительна!

Что касается Пролога и курса Логического программирования и Искусственного Интеллекта, то они мне очень понравились — это реально весело. И мне очень нравится что они заставляют программистов думать совершенно по-другому.

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

Пролог действительно очень легко воспринимается теми, кто не сталкивался с программированием (и наверное воспринимается ими легче, чем теми кто программировал, но не сталкивался с Прологом). Отношения между объектами в Прологе описываются очень легко и красиво, почти в категориях естественного языка. Именно поэтому люди его легко понимают.Он изначально создавался для того, чтобы любой человек мог описать задачу…

На Прологе иногда очень легко реализовывать задачи, которые написаны на обычных, императивных, языках программирования, и наоборот. Например задача Эйнштейна решается на Прологе таким же количеством строк кода, сколько предложений уходит на её описание в текстовом виде.
А вот на императивных языках Вам бы ещё долго пришлось бы описывать алгоритмы перебора.
+1
susl, #
> Например задача Эйнштейна решается на Прологе таким же количеством строк кода, сколько предложений уходит на её описание в текстовом виде.
Ну я не могу упустить такой возможности попиариться :) habrahabr.ru/blogs/programming/122142/
0
Hitory, #
«Объектами — являются термы термы» — ошибка или так и должно быть?)
0
vics001, #
ошибка
0
vics001, #
Кто-нибудь решит задачу? Неужели нет на хабре людей знающих Пролог? Приз-то ждет, не отказывайтесь :)
0
susl, #
если я правильно понял что нужно сделать, то:
?- [user].
|: seq(3).
|: seq(N) :- seq(X), N is X + 1.
|: % user://1 compiled 0.00 sec, 524 bytes

Yes
?- seq(X).
X = 3 ;
X = 4 ;
X = 5 ;
X = 6
Yes
0
alexzzam, #
Вот мне тут выше сообщают, что это решение неверное. Но ваше «compiled 0.00 sec» внушает уверенность. 8)
0
susl, #
Ну ваше решение неверное по другим причинам :) Но если б я его заметил, то не постил бы своё, наверно. Каюсь. Вы были в шаге от победы :)
0
alexzzam, #
Объясните разницу, пожалуйста. 8)

Я: good(Y) :- is(Y, '+'(X, 1)), good(X).
vics001: Y is X + 1. Зафейлится на любом Прологе, потому что у оператора is справа не должно быть переменны, а X переменная.
Вы: seq(N) :- seq(X), N is X + 1.
0
susl, #
Ну как правильно написал vics001, в вашем случае и X и Y в is — переменные. Т.е. пролог еще не знает чему они равны, когда видит предикат is.
Он не может вычислить X знаю Y, либо наоборот, поэтому обозлиться на вас.
Для таких вещей нужен SMT-solver, Пролог такое не умеет (кроме некоторых академических диалектов, которые пишутся на раз для того чтоб опубликовать статью).

В моём же случае, сначала находится X из предиката seq/1. Теперь Х имеет какое-то значение, и значение N находится уже зная его, как будто это просто присваивание (хоть это и не совсем так).
0
vics001, #
Правильно!!!
Задача возникла как-то раз для того, чтобы перебирать последовательность чисел и интерес был в том, чтобы перебирать бесконечно. Так как нельзя складывать (в is) переменные то сначала это даже показалось невозможно, но решение есть.

% :- range(X, Y), Генерирует все числа X начиная с Y.
range(X, X).
0
vics001, #
range(X, Y) :- range(Xs, Y), X is Xs + 1.

% range(X, Y, Z), генерирует между Y и Z.
range(X, X, Z) :- X <= Z.
range(X, Y, Z) :- range(Xs, Y, Z), Xs < Z, X is Xs + 1.

Своеобразные циклы for и функциональные range на Прологе :)
0
VovixLDR, #
У нас в свое время (1997) Пролог упоминался в учебнике информатики 10-11 кл. обычной школы и даже приводились примеры.
Интересно, а современную школоту вообще учат хоть одному языку программирования?
0
alexeygrigorev, #
Да, в моей школе все так же учат паскалю начиная с 10 класса.
+1
alexeygrigorev, #
Так?

predicates
	next_natural(integer).
	
clauses
	next_natural(A) :- write(A), nl, A1 = A + 1, next_natural(A1).

GOAL
	next_natural(3).


Это Visual Prolog, там, как я помню, is нет, поэтому использую =.
0
vics001, #
Да это предикат пишет подряд все числ, но имелось в виду, чтобы числа выдавались бектрекингом и предикат мог использоваться для перебора чисел, в принципе правильный ответ уже написали.
0
alexkolzov, #
> алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно)
Это не так. Во-первых метод резолюций, а не алгоритм. Во-вторых, метод резолюций — это доказательство суждения методом утверждения на основе опровержения. То есть доказательство основано на опровержении обратного утверждения. Это не то же самое, что доказать любую теорему, поскольку метод не всегда дает результат
>… но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание
Здесь Вы не правы, основная проблема Пролога, которая в свое время затормозила его развитие — необходимость наличия как раз служебных предикатов, как assert, что делает его не совсем чистым декларативным, а добавляет черты процедурности. Также в спецификации Пролога определен служебный предикат not (как раз логическое отрицание) и некоторые другие, которые делают правила Пролога не хорновскими дизъюнктами
0
vics001, #
Вы правы, метод (!) резолюций, а последовательность в какой проводить резолюции между дизъюнктами, образует алгоритм (например, простейший алгоритм — метод линейной резолюции).

Алгоритм действительно доказывает любую теорему, если доказательство существует. Технически берется утверждение, которое необходимо доказать и его отрицание добавляется в теорию (к начальным аксиомам). Если теория оказывается противоречивой, значит, противоречие будет найдено (это гарантирует метод резолюций) и значит теорема верна. Формально если проследить все резолюции дизъюнктов приведшие к противоречию, это и будет доказательство «от противного». Если утверждение не является теоремой, то вывод достаточно печален, доказать это может и не получится.

Определение предиката not через отсечение:
not(A) :- A, !, fail.
not(_).

Если бы отрицание было действительно логическим то в Прологе бы допускалась запись вида:
A;B;C :- D, E, F.
В принципе появление логического отрицания равносильно появлению логического Или.
0
alexkolzov, #
Если бы резолюция доказывала любую теорему, математика бы вымерла. Повторюсь, опровержение противоположного утверждения не всегда возможно, метод резолюции не всегда дает ответ об истинности исходного утверждения. Вообще, метод резолюции по определению позволяет доказать невыполнимость множества дизъюнктов, а применительно к доказательству теорем его возможности весьма ограничены.
> простейший алгоритм — метод линейной резолюции
алгоритм и метод — не одно и то же. Хотя это вопрос терминологии.
Отсечение само по себе есть элемент процедурности. Проблема с отрицанием заключается именно в потери дизъюнктом вида хорновского, что приводит к теоретическим ограничениям. В Дейталоге, например, отсечения и отрицания нет, поэтому он является более чистым, чем Пролог.
> A;B;C :- D, E, F.
Пролог по определению имеет дело с хорновскими дизъюнктами. Представленная запись — не он
0
vics001, #
Вторую часть я прокомментировать не могу, так как потерял суть обсуждения.
А вот первую вполне, так как хотел бы сделать это абсолютно понятным для всех даже далеких от математики.

Метод резолюций докажет любую верную теорему, если она представляется логикой первого порядка. Возможно на это потребуется 100 лет современного компьютера, но это теоретически не важно. Истинность исходного утверждения равносильна противоречивости теории, состоящей из аксиом и отрицания исходного утверждения.

Для использования для доказательства реальных утверждений в математике встречаются вполне конкретные сложности:
1. Обычно в математике встречаются теории с равенством, то есть используется отношение равенства
2. Даже в простейшая арифметика является теорией второго порядка (позволяет использовать кванторы для предикатов, для любого предиката и т.п.), потому что содержит математическую индукцию.
3. Формализация современной математики, то есть приведение все к букве закона математической логики, встречает сопротивление других математиков, которые считают, что излишняя формализация затрудняет понимание и останавливает прогресс математики. Ведь еще Гедель доказал, что любая теория должна постоянна пополняться аксиомами, наиболее правдивыми в реальности. В общем, для того, чтобы сформулировать теорему Мат Анализа, потребуется много работы и я еще не видел ни одного автоматического доказательства теоремы из Мат. Анализа.

Вот эта книга в принципе все рассказывает в подробностях:
Чень Ч., Ли Р. // Математическая логика и автоматическое доказательство теорем

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

0
alexkolzov, #
Книгу читал, спасибо. Ваше объяснение корректно, собственно, я и хотел, чтобы в статье было уточнение «любая теорема, представимая в виде множества дизъюнктов логики первого порядка». Но никак не «любая теорема, это неверно. Гедель не доказал, а выдвинул предположение. А для метода резолюции характерной чертой является комбинаторный взрыв количества опорных утверждений (исходных дизъюнктов и их резольвент). Так что Ваше утверждение ну уж очень громкое.
Насчет второй части я поясню. Пролог имеет дело с хорновскими дизъюнктами, поскольку для них метод резолюции имеет самую простую форму. В хорновских дизъюнктах допустимо только одно утверждение с отрицанием, посему выражение вида
pred(X, Y) :- not(X), pred1(X, Y). (выражение утрированное)
не является хорновским дизъюнктом, что приводит к определенным проблемам (каким — разговор отдельный). И относительно оператора отсечения и служебных предикатов. Из-за них Пролог не является чистым декларативным языком, поскольку для него характерно:
1. Чувствительность к порядку
2. Оператор отсечения и предикаты типа assert явно задают порядок вычислений, т.е. приводят к потере декларативной природы
0
jtootf, #
Алгоритм унификации Prolog'а настолько тривиален, что откровенно непонятно, зачем в современном мире привязываться к его (откровенно устаревшим) реализациям. Вот, скажем, Prolog реализованный в Haskell в 200 строчек:

http://propella.blogspot.com/2009/04/prolog-in-haskell.html

А вот — более идиоматичный вариант реализации той же идеи:

http://hackage.haskell.org/packages/archive/logict/0.2.3/doc/html/Control-Monad-Logic.html

DCG, несомненно, хороши — но у них есть ряд недостатков, успешно решённых в eDSL-парсерах того же Haskell (с тем же успехом способных разбирать контекстно-зависимые грамматики, причём заметно эффективней).

Нужно ли учить Prolog? Несомненно — настолько же, насколько нужно учить механизм работы тайпчекера Хиндли-Милнера. Стоит ли использовать в работе именно Prolog, а не какую-нибудь из современных реализаций его идей? Вряд ли.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.