@N_Ikhsanov read-only
Пользователь
6 января в 14:58

Разработка → PROLOG для программистов tutorial

Язык логического программирования PROLOG (далее – ПРОЛОГ) большинству программистов представляется чем-то запутанным и малопригодным для практического применения. В то же время, Интернет основан на символьной информации, поэтому практически все современные программисты сталкиваются с необходимостью обрабатывать символьные структуры данных, а ведь для этого и предназначен язык логического программирования ПРОЛОГ. Этот язык – идеальный для работы с символьными структурами, текстовыми файлами и для построения интеллектуальных программ.
После многолетней работы с ПРОЛОГом, столкнулся с новомодным Haskell, о котором все авторы гордо говорят – «высокий порог вхождения». По-моему, «высота» этого порога образовалась в результате запутанного синтаксиса и нагромождения встроенных процедур. Еще один источник этой «высоты» — высокомерие авторов многочисленных руководств, которые написаны так, будто читатель никогда программ не писал.
Сразу захотелось назад, к «родному» ПРОЛОГу – простому и понятному. Думаю, если объяснить без нагромождений, типа декларативной семантики, время вхождения в логическое программирование для «обычного» программиста не превысит 30 минут.
Попробую описать его с точки зрения процедурного программирования.
ПРОЛОГ имеет два основных отличия от процедурных языков — способ организации вычислений и способ представления данных. Оба этих аспекта языка коренным образом отличаются от традиционных языков программирования. Но не будем забывать, что логическое программирование реализуется на тех же машинах с фон — Неймановской архитектурой.
Представим себе язык программирования, в котором все операции сводятся к вызову процедур. При этом каждая процедура существует в нескольких вариантах и программа сама выбирает себе правильный, точнее говоря, пригодный для каждого конкретного варианта исходных данных вариант реализации (тело) процедуры. Как определяется пригодность – каждый вызов процедуры, во время исполнения программы, по результатам исполнения процедуры, получает логическое значение – TRUE или FALSE. Совокупность процедур с одинаковым именем и арностью называется предикатом.
Каждый предикат в языке ПРОЛОГ идентифицируется двумя параметрами –именем и арностью – количеством параметров. Например, предикат инвертирования списков идентифицируется, как nrev/2, а предикат соединения списков как append/3. Никакого объявления параметров или переменных не требуется, но можно ограничить параметры паттерном в заголовке процедуры. Например, в одном варианте предиката первый параметр может быть указан как [] – пустой список, в другом – как [A,B,C] – список из трех элементов, а в третьем как [H|T] – произвольный непустой список.
Если какое-то условие в теле процедуры не выполняется, выполнение прекращается и вызов процедуры, точнее говоря, выполнение очередного варианта тела процедуры, прекращается и получает значение FALSE. В этом случае, интерпретатор языка запускает следующий по порядку вариант тела этой процедуры. Если же все варианты оказались непригодными, происходит возврат к предыдущей процедуре и для нее также происходит перебор вариантов, таким образом, вычисление в ПРОЛОГе сводится к обходу дерева вложенности процедур.
Возврат к предыдущему вызову называется бэктрекингом (backtracking). По существу это откат, поскольку все значения, полученные переменными в отмененной процедуре, отменяются. Бэктрекинг – уникальное средство данного языка, не имеющее аналогов ни в одном из других массовых языков программирования. Бэктрекинг обеспечивает полный обход дерева логического вывода, что обеспечивает основу для решения интеллектуальных задач.

Алгоритм интерпретации программы (выполнения цели) в системе ПРОЛОГ.

Вход: цель p(A1,A2,…,An)

1. Найти в памяти процедуру по имени p с арностью n.
2. Унифицировать входные параметры цели с заголовком найденной процедуры.
3. Если унификация параметров прошла, выполнить первую цель из тела найденной процедуры.
4. Если унификация не прошла, найти следующий вариант процедуры P/n.
5. Если следующий вариант процедуры P/n не найден, закончить работу с результатом FAIL.
6. Если первая цель выполнилась, перейти к выполнению следующей цели.
7. Если следующая цель не выполнилась, вернуться к предыдущей цели и выполнить следующий вариант ее реализации.
8. Если текущий вариант реализации процедуры P/n не выполнился, перейти к следующему варианту.
9. Если все цели из тела процедуры выполнены, закончить работу с результатом TRUE.

В связи с такой структурой вычислений каждый вызов процедуры называется целью, которая может быть достигнута или нет. Всякое вычисление в ПРОЛОГе имеет логическое значение. Вычисление еще называют поиском вывода (доказательства), а язык ПРОЛОГ – языком логического программирования.
Наверное, синтаксически ПРОЛОГ – самый простой среди языков программирования. Основной синтаксической процедурой является предикат – выражение, аналогичное вызову процедуры — имя и список аргументов –
P(x1, …xn). Имена пишем с малой буквы, а переменные – с большой.
Если опустить детали, синтаксис ПРОЛОГа можно описать следующим образом:

<ПРОЛОГ-предложение> ::= <правило> | <факт> | <запрос>
<правило> ::= <заголовок> ‘:-’<тело>
<факт> ::= <заголовок> ‘.’
<запрос> ::= <тело>‘.’
<тело> ::= <цель> /’,’<цель>/’.’
<заголовок>::= <предикат>
<цель>::= <предикат> |<выражение>
<предикат>::= <имя>/ ‘(‘<терм> /’,’<терм>/ ‘)’/
<терм>::= <атом> |<предикат>|<список>
<атом>::= <переменная> |<число> |<строка>|<имя>
<список>::= <список с заголовком>| <простой список>
<список с заголовком >::= ‘[‘ <терм >/’,’<терм>/’|’ < терм>’]’
< простой список>::= ‘[‘ <терм >/’,’<терм>/’]’|‘['’]’
<выражение>::= <терм> /<оператор><терм>/
<оператор>::= ‘is’ | '=' | ‘==' | ’\=' | ’>=' | ’=<’ | ‘=\=' |

Как видно из синтаксиса, в ПРОЛОГе нет зарезервированных имен за исключением предиката “is”, хотя и применяются различные встроенные предикаты для удобства и связи с внешней средой.

Пример – семейные отношения.
Определим правила для отношений – супруг, ребенок, мать, дочь, брат, потомок. Семейные отношения задаются бинарными и унарными предикатами – правилами (предикаты с переменными) и фактами (предикаты с константами). Правила легко понять, поскольку семейные отношения всем понятны. Например, первое правило гласит: X является матерью Y, если Y есть ребенок X и X женского пола.

mother(X,Y):-child(X,Y),female(X).
daughter(X,Y):-child(Y,X),female(X).
grandchild(X,Y):-child(X,Z),child(Z,Y).
descendant(X,Y):-child(X,Y).
descendant(X,Y):-grandchild(X,Z).

Факты описывают родственников конкретной семьи.

marrow(john, meri). female(meri).
child(john, jack). child(meri, jack). child(john, kate).
marrow(jack,joan). marrow(kate, dick).
child(jack,henry). child(kat,josh).
male(john). female(mery).
male(henry). female(joan).
male(josh). male(dick).

Один набор правил (программа) может применяться к различным наборам фактов (данные).
Набор возможных запросов определяется существующим набором правил. Заголовок каждого правила является основой построения запросов.
Запросы могут быть двух видов – проверочный и поисковый.
Примеры поисковых запросов:
Чья дочь Kat? – daughter(X,kat).
Чей внук Henry? — grandchild(X,henry)
Примеры проверочных запросов:
Dick – ребенок Meri? – child(mery,dick).

Главные понятия ПРОЛОГа: списки, рекурсия, унификация, бэктрекинг. Списки – основная структура данных, применяемая в этом языке. Списки являются основой для организации всех сложных вычислений. Одно из основных свойств списка – отсутствие ограничений на элементы и размер списка. Вложенность списков также ничем не ограничивается. Список в языке трактуется как структура из двух элементов – «головы» и «хвоста». Это разделение является основой вычислений над списками, поэтому наиболее часто применяемый паттерн списка имеет вид [H|T].
Первый элемент списка может иметь любую структуру, а второй – также является списком. Пустой список не содержит элементов и обозначается как [ ].
Вторая базовая структурная единица языка – предикат имеет вид — p(A1,A2,..). Предикаты удобны для группирования данных в одну смысловую единицу. В отличие от списка, количество аргументов предиката фиксировано. Имя предиката пишется с малой буквы, как и все константы в языке.
Переменные всегда начинаются с заглавной буквы. На основе переменных можно строить паттерны для списков.

Примеры списковых паттернов:
[H|T] – не пустой список;
[ ] – пустой список;
[A1,A2,A3] – список из трех произвольных элементов;
[A,A,A|T] – список, в котором первые три элемента совпадают;
[x,10|T] – список, в котором на первом месте стоит символьная константа “x”, а на втором – числовая константа 10.
Рекурсивность структуры списка является важным элементом организации рекурсивных вычислений. Рекурсивные предикаты имеют не менее двух процедур – одна для общего случая, другая – для завершения.
Рекурсивность списков обеспечивает возможность простой формулировки алгоритма операций над списками.
Пример: Вычисление длины списка.

length([H|T],N):-length(T,N1), N is N1+1.
length([],0).

Пример: Инвертирование списка.

nrev([H|T],L) :- nrev(T,L1), append(L1,[H],L).
nrev([],[]).

В ПРОЛОГе нет функций, поэтому нельзя вставить, например, длину списка length(L) в качестве аргумента, как это делается во всех процедурных языках.
В то же время, ПРОЛОГ можно рассматривать как вполне императивный язык, в котором все операции, за исключением бэтрекинга, прописываются явно.
Унификация с первого взгляда вносит некую загадочность и непонятность в язык, но она имеет вполне процедурное объяснение.
Унификация – это подстановка параметров в паттерн и применяется не только для селекции входных параметров, но и для автоматического выделения нужных элементов списка и манипулирования ими – добавления и удаления головного элемента списка.
Пример: соединение списков.

append([H|T], L, [H|L2]):-append(T, L, L2).
append([], L, L).

Правильнее было бы записать второй аргумент в виде [H1|T1], поскольку второй аргумент должен быть списком, но это усложнит предикат, поскольку второй аргумент может быть и пустым списком.
Переменные в ПРОЛОГе – логические, т.е. повторная унификация внутри одной процедуры невозможна. Нельзя написать L = [a,b,c], а потом — L=[12]. Логичность переменных приводит к усложнению унификации, поскольку все унификации в теле одной процедуры не могут быть пересмотрены в процессе вычисления, а значит, они не могут противоречить друг другу.
Унификация логических переменных приводит к неожиданным эффектам, которые имеют вполне императивное объяснение.
Пример: варианты использования предиката соединения списков.
Соединение:

append([a,b,c],[d,e,f],L).
L = [a,b,c,d,e,f] =>
yes.

Проверка связи списков:

append([a,b,c],[1,2,3],[a,b,c,1,2,3]).
yes.

Разложение списка:

append(L1,L2,[a,b,c]).

L1=[a,b,c]
L2=[] ->;

L1=[a,b]
L2=[c] ->;

L1=[a]
L2=[b,c] ->;

L1=[]
L2=[a,b,c] ->;
no.

Здесь символ “;” означает запрос другого варианта решения путем запуска бэктрекинга.

Вычитание списков:

append([a,b], L, [a,b,c,d]).
L=[c,d].

В ПРОЛОГе принято различать вычисления с бэктрекингом (недетерминированные) и без него (детерминированные).
Пример недетерминированного предиката: Решение числовой головоломки.

/*
D O N A L D
+
G E R A L D
— R O B E R T */

sum(L1,L2,L3):-
sum1(L1,L2,L3,L1,L2,L3,0,[0,1,2,3,4,5,6,7,8,9]).

sum1(L1,L2,L3,L11,L12,L13,Ii,Lv):-
dl(L11,L111,E1),
dl(L12,L121,E2),
dl(L13,L131,E3),
val(E1,Lv,Lv1),val(E2,Lv1,Lv2),val(E3,Lv2,Lv3),
sd(E1,E2,E3,Ii,Io),
sum1(L1,L2,L3,L111,L121,L131,Io,Lv3).

sum1(L1,L2,L3,[],_,_,0,_):-!..

dl([H|T],[H|T1],E):- dl(T,T1,E).
dl([H],[],H).

val(E,L,L):-nonvar(E).
val(E,L1,L2):-del(E,L1,L2).

sd(A,B,C,Ii,Io):-
C1 is A+B+Ii,
C is C1 mod 10,
Io is C1 // 10.

del(E,[E|T],T).
del(E,[H|T],[H|T1]):-del(E,T,T1).

s:-
A1=[D, O, N, A, L, D],
A2=[G, E, R, A, L, D],
A3=[R, O, B, E, R, T],
sum(A1,A2,A3),
write(A1),nl,
write(A2),nl,
write(A3),nl.

Предикат sum/3 выполняет основную операцию подбора значений цифр для заданной буквенной формулы. Вычисление проводится для формулы сложения двух чисел любой длины. При наличии известных цифр можно их вставлять вместо переменных. Если длина слагаемых различна, можно вставить нули в начале соответствующего списка.
Предикат sum1/8 использует первые три аргумента для записи результата, аргументы под номером 4,5,6 – в качестве рабочих переменных, седьмой аргумент – начальное значение разряда переноса, восьмой аргумент – список допустимых значений цифр.
Предикат dl/3 выполняет выбор и удаление последнего элемента из списка переменных.
Предикат val/3 выбирает допустимое значение из списка оставшихся вариантов, при этом выбранный вариант цифры, удаляется из списка допустимых вариантов.
Если вариант значения для очередной буквы устанавливался ранее, то он остается без изменений.
Предикат sd/5 проверяет вариант заданной тройки цифр одного столбца:

A+B+Ii = C+Io*10

Если sd/5 не выполняется, возникает бэктрекинг — последний из вызовов предиката val/3 присваивает новое значение переменной E3. Если ни одно из значений E3 не подошло, бэктрекинг продолжается на шаг назад — для E2 выбирается новое значение, затем – если не подойдет ни один вариант E3 E2, для E1.
Предикат sum1/8 выполняется рекурсивно до исчерпания входного списка переменных.
Предикат s/0 – пример вызова предиката sum/3 для решения одного варианта головоломки.
Как видно из примера, программа на ПРОЛОГе может быть очень компактной, при этом алгоритм прост и прозрачен, поскольку никакие неявные вызовы функций не используются.

Можно развивать программу решения таких головоломок, например, сделать ее универсальной – для всех типов числовых ребусов, улучшить ввод исходных данных.
Для этого надо делать такие операции как лексический и синтаксический анализ. Эти операции рассмотрим во второй части.
@N_Ikhsanov
карма
6,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

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

  • –1
    Вся несостоятельность и нежизнеспособность PROLOG была доказана еще 40 лет назад проектом так называемых «Компьютеров пятого поколения»

    Да и Гедель со своей теоремой о неполноте логических систем так и маячит.
    • +4
      Насчет Геделя особенно круто. Сказал так сказал.
      Про пятое поколение тоже сказано сто раз.
      Хотелось бы по существу текста что-нибудь услышать.
      • +3
        Пролог крут как инструмент для исследований. Когда неизвестно, есть ли решение у задачи, когда зависание или исчерпание ресурсов программист поймёт и простит, остановив вычисление и добавив в программу новые отсечения.

        Когда задача уже решена, и нужно только получать частные решения для разных значений параметров, заново запускать полноценный поиск решения — пустая трата ресурсов. Возможно, было бы полезно сделать такой инструмент, который находит цепочку доказательства для данной задачи и пишет императивный код, например на Си, который для данных параметров решает задачу оптимально.
        • 0
          Есть такое мнение, что Пролог хорош для прототипирования и не годится для коммерческих разработок. Не могу с этим согласиться.
          Пролог просто еще один из языков для работы с символьной информацией и здесь он круче всех.
          Пролог в чистом виде не решает всех проблем с интеллектуальными задачами, но он дает основу для их решения. И эта основа прочнее и надежнее, чем у других языков искусственного интеллекта.
          Моя цель — показать, что в ПРОЛОГе нет ничего сложного и любой программист может его освоить и эффективно применять в работе.
          • +2
            Ничего не имею против Prolog или вашей статьи (спасибо, кстати, она прояснила некоторые вещи), но вот это:

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


            всё-таки ваше мнение.Задачи искуственного интеллекта — это очень размытое понятие, но в последние годы оно в основном упоминается в контексте:

            1. Машинного обучения
            2. Интеллектуальных агентов (по сути то же машинное обучение, но с ответной реакцией)

            И вот здесь язык, который даёт самую надёжную основу для решения таких задач, — это математика. В основном, линейная алгебра, статистика и немного мат. анализ. А от языка программирования требуется удобная передача математических методов на вычислительную машину. И вот здесь, насколько мне известно, Prolog-у нечего предложить, по крайней мере не на том уровне, на котором предлагают Python, Matlab, Julia или даже Scala.
            • 0
              это очень размытое понятие, но в последние годы оно в основном упоминается в контексте:
              1. Машинного обучения
              2. Интеллектуальных агентов (по сути то же машинное обучение, но с ответной реакцией)
              Это исключительно ваше видение. Если же разбираться подробно, то интеллектуальных задач достаточно много. Исторически к интеллектуальным относили символьные задачи. А у вас предложены лишь вычислительные. И дальнейший спор предлагаю не развивать, т.к. он упрется в определение термина «интеллектуальный».

              PS: Нынче в Deep Learning нейросетях используют символьную математику для снижения вычислительной сложности расчета производной при обучении.
              • +1
                Давайте начнём с того, что нынче в тренде как раз упомянутые вами сети глубокого обучения, которые и относятся к вычислительным, а никак не к символьным. То, что в некоторых из них для решения частной задачи используетя символьное дифференциирование, никак не переносит эти сети в класс символьных методов, и на Prolog их никто не переписывает.

                В остальном вы сказали всё то же, что и я: да, понятия интеллекта и интеллектуальной задачи довольно размыты, и да, таких задач много, языков для их решения тоже много, и ни один из них не даёт "основу прочнее, чем у других языков" для решения всех этих задач.
        • 0
          Когда задача уже решена, и нужно только получать частные решения для разных значений параметров, заново запускать полноценный поиск решения — пустая трата ресурсов

          Чисто навскидку: можно модифицировать саму программу, можно модифицировать ее автоматически, сохраняя таким образом промежуточные точки.
    • +1
      Вся несостоятельность и нежизнеспособность PROLOG была доказана еще 40 лет назад проектом так называемых «Компьютеров пятого поколения»

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

      Теорема Гёделя в данном случае означает, что не существует универсального алгоритма решения произвольных логических задач. То есть, программа на прологе может не завершается, но изменить алгоритм можно переформулировав задачу, модифицировав программу.

      Уверен, логическое программирование ещё себя покажет, например в Coq успешно применяется автоматический вывод.
      • +1
        Теорема Гёделя в данном случае означает, что не существует универсального алгоритма решения произвольных логических задач. То есть, программа на прологе может не завершается, но изменить алгоритм можно переформулировав задачу, модифицировав программу.


        Фактически, из этого следует, что вместе с программой должна поставляться кнопка «Вызов разработчика». Для того чтобы данный разработчик немедленно приступил к коррекции программы, чтобы она начала «понимать» поставленную задачу. Что и говорит о несамостоятельности таких систем.
        • +2
          Несамостоятельность — это не «несостоятельность и нежизнеспособность».
          • +1
            Отсюда и вывод: пролог — инструмент исследователя.
            Программы на прологе — не для пользователя.
        • +1
          … вместе с программой должна поставляться кнопка «Вызов разработчика»
          1С вам в подарок на рождество )
          Для любой развивающейся информационной системы нужна кнопка «Вызов разработчика»
          • 0
            Есть мнение, что на то и создается ИИ, чтобы разработчика не звать. Вот вы же не зовете разработчика, чтобы научиться суп варить, или там, с девушками знакомиться? То-то же.
            • –1
              ИИ создается для решения задач, которые человек решить не может в силу огромного объема вычислений. А мечта заменить разработчика — так и останется мечтой манагеров.

              Процесс формализации существенно неформален, а потому в общем случае неформализуем.
              Разработчикам платят за формализацию фантазий манагеров.
              • +1
                Обычно разработчиков зовут, чтобы баг пофиксить или сделать новую фичу.
                А для задач, куда подходит Пролог (там, где вычисление гарантированно завершается, Пролог не нужен — алгоритм известен, его можно просто императивно записать), придётся вызывать разработчика в штатных случаях, а не только в экстренных.
            • 0
              Вот вы же не зовете разработчика, чтобы научиться суп варить, или там, с девушками знакомиться?
              Вообще-то зову. Разработчик сидит в устройстве, называемое «поваренная книга».
              • +1
                Там сидит разработчик супа, а не ваших мозгов. Ваши мозги умеют сами себя настроить на варку супа. Ну, некоторым правда надо испортить пару килограмм продуктов и кастрюльку пожечь, но это уж как пойдет.
                • 0
                  Я хотел показать другую мысль. Человек, с рождения живущий как маугли, не способен самостоятельно научиться варить суп. Так уж вышло, что общество — своего рода разработчик для каждого его члена. Можно возразить, что общество не создает мозг, а только учит существующий — но вы и сами не с нуля компьютер собираете, на котором будет выполняться ваш алгоритм.
                  • +1
                    Вы все ту же мысль штампуете. Отличие разума от чистой формально-логической системы с правилами вывода и предикатами состоит в том, что разум способен обучаться и воспитываться, без обращения к Создателю разума, который в нем что-то подвинтит. А средство воспитания — поваренная книга, или девушка, которая вам пишет «Не пиши мне больше, ублюдок!» и забанивает в социальной сети на веки вечные — не важно.

                    Так вот, тот самый Гедель и показал, что сколько правил и предикатов не засовывай, всегда возможна cитуация, когда вся логика встанет колом, встретив неведанное — например, если вы выловите эту забанившию девушку на улице и она вам скажет «О, милый рыцарь, ты таки добился меня!». (Ну просто создатель логической системы забыл заложить правило, что женское НЕТ, это иногда и ДА).
                    • +2
                      Перечитал ветку с самого начала и понял, что вы говорите именно о прологе, а не о «любой развивающейся информационной системы». Разумеется, в этом контексте я с вами спорить не буду, вы правы.
  • +1
    Текст не читай @ комментарий пиши.

    Хоть кто-нибудь использует пролог где угодно, кроме как для решения ru.wikipedia.org/wiki/Загадка_Эйнштейна? Можно мне примеров систем, которые написаны на прологе и вот прям сейчас работают?
    • 0
      Prolog has been used in Watson… Prolog is used for pattern matching over natural language parse trees. Wiki

      Вообще Пролог это всяческие экспертные системы. Типа вводишь набор симптомов, получаешь диагноз.
    • 0
      Относительно недавно видел пролог в проекте Crisp в качестве DSL для описания правил. Похоже, правда, что проект больше не развивается.
    • 0
      На прологе раньше писали медицинские системы, по идее следователи должны пользоватся Прологом.
      • 0
        Вот это упрощенное понимание языка PROLOG, как готового средства для экспертной системы. Для ЭС нужен естественно-языковый интерфейс и другие средства, которые и надо делать на языке PROLOG.
    • 0
      К примеру, правила верификации java class-файлов описаны в стандарте именно в виде предикатов пролога: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1.
      Это, конечно, не «система, написанная на прологе», но вполне себе его использование.
      • –2
        Посмотрел этот текст — там сплошной ПРОЛОГ. Написано так, будто читатель должен владеть этим языком.
        Очевидно, что автор этим языком владеет хорошо.
        «The type checker enforces type rules that are specified by means of Prolog clauses. English language text is used to describe the type rules in an informal way, while the Prolog clauses provide a formal specification. „
  • 0
    Prolog — элитный язык, культивируется в основном в крупных организациях, связанных с наукой — IBM, NASA, Ericsson,…

    Вот некоторые ссылки:
    1) Clarissa, a fully voice-operated procedure browser has been developed by the NASA Intelligent Systems Division.
    ti.arc.nasa.gov/tech/cas/user-centered-technologies/clarissa

    2) Ericsson Network Resource Manager — www.ericsson.com

    3)Axon Idea Processor axon-research.com
    Our company (www.intologic.com) mostly uses Prolog.

    4)LPA Applications
    Environmental Modelling — www.lpa.co.uk/apl_001.htm
    Payrolls — www.lpa.co.uk/apl_003htm
    Sales Modelling — www.lpa.co.uk/apl_004tm
    Management Consultancy — www.lpa.co.uk/apl_006m
    Other applications — www.lpa.co.uk/use_app.htm

    5)IBM Watson (partially) — en.wikipedia.org/wiki/Watson_%28computer%29

    Примеры нетривиальных процедур на PROLOG:
    colin.barker.pagesperso-orange.fr/lpa/lpa.htm
  • 0
    Основная причина недостаточного распространения PROLOG — это язык LISP — поскольку он появился на 20 лет раньше, все основные американские институты и фирмы, где программируют ИИ, используют LISP.
    Надо сказать, что в последних версиях наиболее мощной версии LISP Allegro CL (FRANZ inc.) содержится PROLOG как подмножество языка.
    franz.com/support/documentation/8.2/doc/prolog.html
  • +6
    Вот так бы я решил числовую головоломку на «новомодном» Haskell c «высоким порогом».
    module Main where
    
    import Control.Monad (guard)
    import Data.List (nub)
    import Text.Printf (printf)
    
    {-
      D O N A L D
    + G E R A L D
      -----------
      R O B E R T
    -}
    
    solutions :: [(Int, Int, Int)]
    solutions = do
      d <- [1..9]
      o <- [0..9]
      n <- [0..9]
      a <- [0..9]
      l <- [0..9]
      g <- [1..9]
    
      let (t:r:e:_) = revDigits (2 * unDigits [a, l, d])
    
          donald = unDigits [d, o, n, a, l, d]
          gerald = unDigits [g, e, r, a, l, d]
    
          (_:_:_:b:_) = revDigits (donald + gerald)
          robert = unDigits [r, o, b, e, r, t]
    
      guard (donald + gerald == robert)
      guard (different [d, o, n, a, l, g, e, r, b, t])
    
      return (donald, gerald, robert)
        where unDigits = foldl (\ a b -> a * 10 + b) 0
              different xs = length (nub xs) == length xs
              revDigits x = let (q, r) = quotRem x 10 in r:(revDigits q)
    
    main = do
      let (a, b, c):_ = solutions
      printf "  %d\n+ %d\n  ------\n  %d\n" a b c
    


    На моём компьютере ответ считается чуть более полусекунды:
    $ time ./Main
      526485
    + 197485
      ------
      723970
    
    real	0m0.592s
    user	0m0.587s
    sys	0m0.004s
    
    • 0
      По моему, если сравнивать:
      — программа на ПРОЛОГе в 10 раз понятнее, поскольку все использованные идентификаторы (процедуры) описаны в тексте программы;
      — Ваша программа не универсальна, поскольку содержит исходные данные в тексте;
      — скорость решения на моем простейшем компьютере — меньше одной сотой секунды.

      Наверное, у HASKELL, есть свои преимущества, это вопрос личных предпочтений.
      • +5
        программа на ПРОЛОГе в 10 раз понятнее, поскольку все использованные идентификаторы (процедуры) описаны в тексте программы

        Ну, это очень спорное утверждение. Использование готовых, уже известных другим программистам функций и абстракций обычно всё же облегчает понимание программы.

        Вот версия, которая перебирает чуть меньше вариантов и ощутимо короче:
        module Main where
        
        import Data.List (permutations)
        import Text.Printf (printf)
        
        {-
          D O N A L D
        + G E R A L D
          -----------
          R O B E R T
        -}
        
        solutions :: [(Int, Int, Int)]
        solutions = filter good $ map assign (permutations [0 .. 9])
          where assign [d, o, n, a, l, g, e, r, b, t] = ( unDigits [d, o, n, a, l, d]
                                                        , unDigits [g, e, r, a, l, d]
                                                        , unDigits [r, o, b, e, r, t]
                                                        )
                unDigits = foldl (\ a b -> a * 10 + b) 0
                good (donald, gerald, robert) = donald + gerald == robert
        
        main = do
          let (a, b, c):_ = solutions
          printf "  %d\n+ %d\n  ------\n  %d\n" a b c
        
  • 0
    Поправьте меня если я ошибаюсь: мне кажется что для современных языков (java, python, etc) не так сложно реализовать DSL с тем-же функционалом, или я что-то упускаю?
    • 0
      Хороших реализаций языка ПРОЛОГ очень мало, хотя много любительских.
      Java, Python вынуждены встраивать операции со списками как дополнение, а в ПРОЛОГе они в ядре системы.
      • +2
        Фишка в том что Java и Python популярные языки общего назначения. Так не лучше ли написать хорошую библиотеку реализующую функционал пролога чем интегрировать еще один язык?
        • +2
          Написать можно, равно как интегрировать готовое.
          Вопрос, что делать дальше, на чём писать бизнес-логику. Заставлять программеров ломать мозги в сторону пролога, оставив их без привычного пошагового дебагера с показом watches и прочего.

          Брр… Как представлю, будет написан мегабайт пролог-кода, где какое-утверждение 5000 строками ниже может существенно повлиять на ход доказательства. А писавший это уволится. И разгребай как хочешь.
          • 0
            Я сейчас работаю с чем-то похожим. Система декларативного описания бизнес-правил. Отладка тоже весьма и весьма… Хотя ПРОЛОГ конечно сложнее будет.
            • 0
              Это интересно, можем обсудить. Если хотите, напишите мне на почту.
          • 0
            В ПРОЛОГе тоже есть debugger с пошаговой трассировкой. Хотя правильнее будет обходиться без него.
            А что касается, больших программ на ПРОЛОГе, поиск ошибок должен быть даже проще, поскольку язык требует строго иерархической структуры программ.
        • 0
          Если я не ошибаюсь, на этих языках есть реализации ПРОЛОГа, сделанные специально для интеграции с ними.
          По-моему, лучше делать на ПРОЛОГе отдельные библиотеки и DLL, не смешивая два языка с разной парадигмой.
    • +1
      Есть Yield Prolog. Он достаточно легко реализуется средствами языков с итераторами, без подключения сторонних библиотек.
  • 0
    Это не такая простая штука, чтобы поместиться в библиотеку.
    Коммерческие версии ПРОЛОГа имеют прекрасные возможности для интеграции.
    Например Arity/Prolog (сейчас бесплатный, поскольку фирма его не поддерживает) компилирует ПРОЛОГ-программу в obj — файл из которого можно сделать EXE, DLL или просто подлинковать. Кроме того, поддерживается встроенный C — прямо в сорсе можно вставлять фрагменты на C.
  • 0
    «Язык логического программирования PROLOG (далее – ПРОЛОГ) большинству программистов представляется чем-то запутанным и малопригодным для практического применения.»

    Да не, язык — огонь. Просто нет трансляторов нормальных практически применимых. Только на java может быть.
    • 0
      Из бесплатных — великолепный транслятор Arity/Prolog32. Это коммерческая разработка, лучшая в своем классе, но фирма ее не поддерживает, поэтому можно пользоваться ею бесплатно.
      • 0
        Arity's Prolog Compiler and Interpreter for Microsoft Windows open source

        Под линуксы и макос нет. Swi prolog близок к тому что нужно, но его тоже нереально встроить в нормальную программу.
        • 0
          А еcли поискать?
          SICStus PROLOG — есть для UNIX
  • –1
    15 лет назад в универе был у нас небольшой курс по ПРОЛОГ. Из трех лекций было ничерта не понятно. Но лабораторку делать надо (выход из лабиринта).
    Опыт у меня был только с Basic/Pascal/C/C++/ASM и логика ПРОЛОГа была совершенно чужда и непонятна.

    Помню что в последнюю ночь перед сдачей я сел и разобрался. Помню внезапное ощущение «озарения», когда я понял КАК оно обрабатывает предикаты и НАСКОЛЬКО по-другому, в отличие от известных мне языков, оно это делает.
    Ощущение что через приоткрытую дверь попал в совершенно новую огромную комнату с кучей неизвестных новых интересных вещей! Никогда не забуду эти ощущения.

    Лабораторку написал, она заработала. Лег спать, утром проснулся и нифига не понял как оно работает и вообще все забыл, кроме впечатлений.

    С тех пор меня это воспоминание всегда мотивирует на изучение новых вещей.
    А ПРОЛОГ я не знаю, но впечатления остались хорошие :)
    • –2
      Для того и написан этот текст, чтобы любой программист разобрался.
    • +2
      У нас был Turbo-Prolog, в нем можно было включить пошаговый trace режим. Помнится, это сильно помогло мне разобраться в его работе. Не сказал бы, что совсем все по-другому, все сводится к последовательному перебору вариантов и возможных веток.

      Скрытый текст
      У меня была такая история с лабораторкой.
      Нужно было выбрать тему, я выбрал игровые алгоритмы. Хотел написать игру в дурака. И написал, с графическим режимом, с управлением через клавиатуру. Первая сложность была хранить номер текущей выделенной карты. Делать UI на прологе — то еще удовольствие.
      Преподаватель оказался странный, с первого раза никогда не принимал. Отправил меня обратно, сказал добавить на каждом шаге вывод процесса принятия решения в текстовом виде, причем обязательно на русском, так как английский он не знал. Программа keyrus в BGI-графике не работала; функций для работы с двоичными данными, чтобы вручную загрузить русский шрифт по нужному адресу, я в этой версии пролога не нашел. Мысленно послал преподавателя подальше вместе с его требованиями и прологом. Переписал все на C++ (оказывается, это так удобно, когда переменные можно изменять), добавил русский шрифт, скомпилировал exe, в программе на прологе поставил штук 300 пробелов и написал «system(»fool.exe"), exit(0)". Сдал без проблем.
      • 0
        В любом ПРОЛОГе есть trace. Эта публикация еще не раскрывает все преимущества ПРОЛОГа. Буду продолжать.
  • +8
    Очень не хочется вступать в перепалки и обсуждать уже многократно обсуждавшиеся вещи, но…

    Любому программисту хорошо бы изучить и Пролог, и Лисп, и Хаскел, и Форт, и много чего ещё нестандартного, хотя бы для того, чтобы потом лучше программировать на «родном» языке.

    Однако довольно странно в очередной раз рассказывать о том, какой замечательный язык X, когда про этот язык уже всё давно известно, и все копья давно сломаны. Жизнь богаче и мудрее любых отдельных армий на этом фронте. Если господствуют Java, C++ и C#, значит, в этом имеется какой-то объективный смысл. У Пролога есть свой круг любителей и круг задач, с которым он справляется. Ну и прекрасно, чего же более? Если не хочется совсем погружаться с головой в чужой мир, есть, например, pyDatalog — с его помощью любой может поупражняться в логическом программировании, не вылезая из Питона.

    Какие-то вещи в логической парадигме делаются просто и удобно, какие-то с трудом. Ну объясните мне, чем first order logic хорошее средство для описания процессов, идущих во времени: сначала происходит то-то, потом то-то, а потом то-то. Мне кажется, что язык задумывался как реализация разных фантастических планов шестидесятых, но в итоге всё оказалось куда сложнее.

    Например, если почитать старые книги по Прологу, там объясняют, что вот ты тут декларируешь условия, цели и допустимые операции, а компьютер потом «думает сам», но потом оказывается, что реальность скромнее. Нельзя сказать, что сортированный список удовлетворяет таким-то критериям, а потом получить на выходе quicksort. Придётся программировать сортировку почти что явно, почти что как на любом императивном языке.

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

    То есть мы имеем по сути дырявую абстракцию: где-то работает, где-то нет. Неудивительно, что после таких исходных посылов многие быстро остывают и разочаровываются. А кто готов мириться, спокойно пользуются; за них рад. И не надо говорить сначала о том, какой язык «простой» и «удобный», а потом «элитарный». Тут уж одно из двух: простой и удобный — это Бейсик, а «элитарный» — это нечто из другой оперы.
  • –2
    Почему-то некоторые воспринимают ПРОЛОГ как готовую интеллектуальную систему, а потом обижаются, обнаружив, что не все там готово — надо еще самому разбираться, изучать язык. Как будто есть другие языки с логическим выводом!
    ПРОЛОГ — язык специализированный, его надо использовать для обработки символьных структур. Здесь он лучше всех.
    Цель данной публикации — показать его удобство и простоту.
    • +1
      Необходимо уточнить, по какому критерию лучше. По скорости работы, по хорошему распараллеливанию на много процессоров? Символьная задача — поисковик гугла. Зря они его на Прологе не написали.
      • –3
        Согласен с Вашей постановкой вопроса.
        Об эффективность языка Пролог можно говорить в таких аспектах — скорость программирования, качество программы.
        Конечно, следует говорить только о задачах обработки символьной информации.
        Раньше говорили так — программа на Прологе пишется в 10 раз быстрее, но сама программа работает медленно. Однако после появления компиляторов для ПРОЛОГа скорость у него вполне сравнима, а во многих случаях бывает и выше.
        Думаю, что любой компилятор хорошего качества с любого языка можно на Прологе написать раз в пять быстрее.
        Дело не только в том, что в Прологе не надо думать о стеках и проблемах динамической памяти, но и в том. что сама природа списков и рекурсии адекватна предметной области.
        Конечно, если надо поисковик писать, микросекунды считать, то нужен специализированный набор процедур.
        • +1
          в Прологе не надо думать о стеках и проблемах динамической памяти
          Зато надо думать, как бы логический вывод не улетел в бесконечную рекурсию, а это куда сложнее, чем придерживаться какого-нибудь простого правила типа «выделил память — не забудь освободить»

          качество программы

          За счёт чего? Строго типизированный язык не позволит мне передать слона в фунцкию, принимающую овощи. А на Прологе легко объявить «морковь сын зайца» вместо «морковь корм для зайца» (ну бывает, копипастил, опечатался). Пролог всё стерпит.
          • 0
            Любая программа может зациклиться. Зацикливание в ПРОЛОГе — это для начинающих.
            ПРОЛОГ не все стерпит, потому -что большинство переменных задаются в виде паттернов.
            • 0
              большинство переменных задаются в виде паттернов
              Приведите пример такого описания. Я хочу понять, как оно защищает от опечаток.
              • 0
                Конечно, ПРОЛОГ не защищает от опечаток в такой степени как это делается в языках с объявлением типов данных.
                Защита есть на уровне паттернов списков, которые я приводил в тексте — [A,B,C] — список из трех элементов, [1|T] — список с единицей в начале и т.д.
                Нужна ли статическая защита в ПРОЛОГе? Вот на Visual Prolog, где надо объявлять каждую переменную, я не могу писать. Может быть не только я — ведь он не получил широкого распространения.
                • +2
                  Это никакая не защита, просто не произойдёт сопоставление. Когда-нибудь, на каком-нибудь неоттестированном случае программа заглючит. Например, я напишу female(john, mary), подразумевая father(john, mary).
                  Или [A,B] вместо [A,B,C]. IDE/язык ничего не подскажут.

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

                  Отсюда и надёжность программ, и скорость написания. Может, в 1970-х по-другому подходили к производительности программистов, но сейчас основа — тесный интерактив программиста с машиной, и язык должен этому помогать.
        • +2
          Да если бы… Чтобы написать ту же злосчастную сортировку списка, надо прыгнуть через обруч задом наперёд, пытаясь вникнуть в логику этого языка (по сути борясь с декларативностью и обеспечивая неявную императивность).
          Конечно, есть странные задачи вроде поиска троюродных дядюшек в списке пар детей и братьев — здесь да, получится быстро. Видимо, авторы Пролога считали, что именно такие задачи предстоит решать на практике в основном.
          А списки и рекурсия есть везде, хоть в том же упомянутом Питоне. Равно как и отсутствие проблем с динамической памятью.
          • +1
            Попробуйте полюбить рекурсию. Все символьные объекты неизбежно рекурсивны.
            Пора уже понять, что процедурный подход в программировании — временное явление.
            Все модные языки — это сдача позиций перед неизбежностью декларативности символьных структур.
            • +2
              Пора уже понять, что процедурный подход в программировании — временное явление.

              Вот только что-то смены не видно.

              Попробуйте полюбить рекурсию.

              Вообще-то, рекурсия — основа алгоритмического подхода «разделяй и властвуй», вполне себе универсального (работающего что в императивной, что в декларативной парадигмах).

              Все символьные объекты неизбежно рекурсивны. [...] Все модные языки — это сдача позиций перед неизбежностью декларативности символьных структур.

              Я все-таки спрошу: что именно вы понимаете под символьными объектами и символьными структурами?
              • 0
                Насчет смены парадигм — в последние десятилетия прогресс в Software Engineering резко замедлился из-за экстенсивного роста спроса на программы — крупным фирмам и так хороши живется.

                Насчет рекурсии — как учил Дейкстра «структура программы должна соответствовать структуре данных». Если работаем с массивами и файлами — нужны циклы, если со списками (а это выражения на каком-то языке) — программа должны быть рекурсивной.
                О символьных структурах надо говорить, когда на вход программы поступает не числовые записи, а выражения на некотором языке.
                • +1
                  Насчет смены парадигм — в последние десятилетия прогресс в Software Engineering резко замедлился из-за экстенсивного роста спроса на программы — крупным фирмам и так хороши живется.

                  Так на основании чего вы делаете вывод, что процедурный подход — временный.

                  Насчет рекурсии — как учил Дейкстра «структура программы должна соответствовать структуре данных». Если работаем с массивами и файлами — нужны циклы, если со списками (а это выражения на каком-то языке) — программа должны быть рекурсивной.

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

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

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

                  Ну во-первых, они не обязательно декларативны. А во-вторых, что важнее, они не настолько распространены, чтобы можно было говорить, о том, что «все модные языки» сдают перед ними позиции.

                  Я, кстати, погуглил, и не нашел — а как на прологе реализовать «настоящий» QuickSort? Или, что интереснее, как на прологе решается 2-SAT?
                  • –1
                    1)Процедурный подход временный, поскольку решение проблемы автоматизации программирования неизбежно, так же как появление автомобиля без водителя. Программистам останется проектирование приложений и совершенствование интеллектуальных систем.
                    2. Не согласен
                    3.Трендовые (или модные) языки вынуждены работать с HTML, XML.
                    4.QuickSort есть в Интернете
                    5.2-SAT — как и всякую поисковую задачу удобно запрограммировать на ПРОЛОГе, но если нужно улучшить поиск, надо делать дополнительные правила поиска.
                    • +2
                      поскольку решение проблемы автоматизации программирования неизбежно

                      Серьезно?

                      Программистам останется проектирование приложений

                      А чем, по-вашему, отличается проектирование от программирования?

                      Не согласен

                      С чем конкретно и почему?

                      Трендовые (или модные) языки вынуждены работать с HTML, XML.

                      И что? Во-первых, задача разбора HTML сравнительно редка, во-вторых, после разбора — это обычное дерево, с которым можно работать более чем одним способом. И, самое главное, где сдача позиций-то?

                      QuickSort есть в Интернете

                      Я не нашел ни одной реализации, которая бы делала in-place (а без него QuickSort не имеет смысла по сравнению с merge sort).

                      2-SAT — как и всякую поисковую задачу удобно запрограммировать на ПРОЛОГе

                      Как именно?
                      • 0
                        Под проектированием я понимаю работу системного аналитика, который полностью, точно, специфицирует проект, т.е. программистам придется переквалифицироваться в системные аналитики.
                        Вы задаете очень интересные вопросы, был бы рад их обсуждать и дальше, но тема у нас немного другая.
                        Давайте подождем до публикации на эту тему — моей или Вашей.
                        • +2
                          Под проектированием я понимаю работу системного аналитика, который полностью, точно, специфицирует проект, т.е. программистам придется переквалифицироваться в системные аналитики.

                          Эмм, а я-то думал, что проектирование начинается после спецификации…

                          Впрочем, вы никогда не слышали утверждения, что единственная полная точная спецификация программного продукта — это его код? То, что вы описываете, это уже неоднократно предложенная (и пока еще ни разу не взлетевшая) идея программирования через требования.

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

                          Да ладно вам, quick sort — типовая задача, демонстрация того, как она решается (или не решается) в языке — это очень поучительно.
                          • 0
                            Так никто и не ответил мне — какие практические задачи по работе со списками приходится решать в повседневной работе программиста.
                            • +1
                              какие практические задачи по работе со списками приходится решать в повседневной работе программиста

                              Да никакие не приходится. Не нужны практикующим «императивным» программистам списки. Медленные они и памяти много жрут.

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

                              Haskell-программисты используют списки гораздо чаще, но там списки по сути являются ленивыми потоками, материализующимися по необходимости.
                              • 0
                                Я имел в виду списки для обработки символьных структур, а не для управления процессами. Видимо, с символьными списками Вы не сталкиваетесь.
                            • +2
                              какие практические задачи по работе со списками приходится решать в повседневной работе программиста

                              А вы где-то задавали этот вопрос? Я в нем, если честно, и смысла-то не вижу. В языках, где список — основная структура данных, — любая типовая задача решается через работу со списками. А в остальных языках задачи решаются с помощью тех структур данных (или других инструментов), которые для этих языков привычны.
                      • 0
                        Сдача позиций в том, что в императивные языки вставляют парадигмы функционального и логического программирования.
                        QuickSort, 2-SAT — тема для отдельных публикаций. Если Вы убедите меня, что это актуально для Вас и широких масс программистов, можно этим заняться.
                        • +1
                          это актуально для Вас и широких масс программистов

                          С моей точки зрения, для широких масс программистов не актуальны ни решения логических задачек, ни лексический анализ, ни квиксорт.
                          Да, после вашей статьи я начал таки читать The Art of Prolog (давно планировал начать, всё руки не доходили). В основном потому, что ваша статья читается тяжеловато и мало что объясняет, а понять, для каких задач действительно хорош Prolog, хочется.
                          • –1
                            Как раз мое выступление и предназначено, чтобы подвигнуть на изучение ПРОЛОГа.
                            А еще хотелось показать программистам, какие практические задачи можно решать на ПРОЛОГе. Для этого надо взглянуть на Вашу повседневную работу под другим углом. Но это будет не сразу.
                        • +1
                          Сдача позиций в том, что в императивные языки вставляют парадигмы функционального и логического программирования.

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

                          2-SAT — тема для отдельных публикаций. Если Вы убедите меня, что это актуально для Вас и широких масс программистов

                          То есть вы серьезно считаете, что можно «демонстрировать суть, природу языка» ПРОЛОГ и не говорить о SAT? Смешно, да.
                  • 0
                    Убрал повтор
            • +2
              А я разве её не люблю? Говорю же, «списки и рекурсия есть везде, хоть в Питоне».

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

              Из двух декларативно эквивалентных программ одна может работать моментально, а другая навсегда зацикливаться. Есть пример попроще: регулярные выражения, там ровно та же история происходит.

              То есть если бы вся эта механика реально работала, конечно, мы бы жили совсем в другом мире. К сожалению, на практике мы просто имеем некий инструмент неявного императивного программирования, причём достаточно простой внутри. И говорить, что пользование этим инструментом перевернёт наше представление о разработке ПО достаточно опрометчиво.
              • 0
                Ровно об этом я и пишу. Моя цель была — показать ПРОЛОГ без розовых очков, без утверждений о его теоретических возможностях, показать только его практически работающие свойства.
                Основное преимущество ПРОЛОГа — в его простоте.
                А переворот в программировании произойдет на основе искусственного интеллекта.
  • 0
    Так какой софт автор рекомендует использовать? Есть плагины для Eclipse, IntelliJ?
    • 0
      Насколько я знаю, у сообщества Java есть реализация Пролога.
      SWI Prolog рекламируется как универсальное средство, но сам я с ним не работал.
      Из коммерческих есть еще шведский SICStus Prolog.
      Я пользуюсь ARITY/Prolog32. У него хорошие средства интеграции с другими средами.
  • 0
    Автор, не могли бы вы следующих публикациях рассказать о методах отсечения дерева решений, для того чтобы иметь более производительную систему, чем система с прямым перебором решений.

    Понятное дело, что Prolog — это универсальная система записи предикатов и начальных состояний для решающей машины, которая обходит все возможные варианты решения, и подбирает окончательно правильное. В этом плане, это нисколько не отличается от кучи вложенных циклов, в которых участвуют зависимые переменные, согласно которым в дальнейшем находится решение. Интересуют именно методы сокращения вычислений, чтобы получать более быстрое решение, или определять что решения нет, т.к. предикаты или начальные условия являются взаимоисключающими.
    • +2
      Вопрос актуальный, буду им заниматься, наверное в третьей части, поскольку вторая часть запланирована под синтаксический анализ.
  • 0
    Условия головоломки можно узнать? В интернете среди начальных условий дается D=5, но в программе этого нет.
    • 0
      Там все в тексте. Можно копипастом скопировать в файл. запустить предикат s.
  • +1
    А почему в статье нет ссылки на первоисточник? http://www.mari-el.ru/mmlab/home/prolog/study_l.html
    • 0
      Данная статья сама является первоисточником в том смысле, что содержит оригинальное авторское изложение основных идей языка PROLOG. Учебников по этому языку достаточно много, так же как и публикаций различных авторов на эту тему.
  • 0
    Кстати, пришел в голову занятный вопрос: а как оценивать алгоритмическую сложность программы на Прологе?
    • 0
      Вытаскивать из пролога реализации всех предикатов — и вперед!
      • 0
        Я что-то не уверен, что этого достаточно.
    • 0
      наверное также, как оценивать алгоритмическую сложность SQL-запроса
  • +1
    Главная фишка пролога, отличающая его от всех остальных языков — это то, что поисковые и проверочные функции не различаются.
    Это позволяет экономить на писанине.
    Там, где на других языках пришлось бы делать 2^N функций

    bool check_compatibility(int x, int y);
    bool find_x_compatible_to_y(int& x, int y);
    bool find_y_compatible_to_x(int x, int& y);
    bool find_any_compatible(int& x, int& y);
    


    может оказаться достаточным

    compatible(X, Y) :- ..... .
    


    То есть, мы описываем некоторое уравнение, а среда исполнения находит план решения этого уравнения для заданного комплекта известных и неизвестных аргументов.
    Естественно, что уравнение логическое. Арифметику сюда уже просто так не подтянешь, — это к Вольфраму, а не к прологу.

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

    slow(X) :- ... . // медленная проверка/перебор
    fast(X) :- ... . // быстрая проверка/перебор
    
    check1(X) :- fast(X), slow(X).
    check2(X) :- slow(X), fast(X). // то же самое, что выше, но гораздо медленнее
    


    и всякие зацикливания

    // предикат удовлетворяет цепочкам, составленным из a и b
    abstring( [] ).
    abstring( [a|S] ) :- abstring(S).
    abstring( [b|S] ) :- abstring(S).
    
    // проверка вхождения
    belongs( C, [C] ).
    belongs( C, [_|Cs] ) :- belongs(C, Cs).
    
    // ну что, взорвёмся?
    abstring_with_item(C,S) :- abstring(S), belongs(C,S).
    
    ?- abstring_with_item(C,[a,a,a,a,a,b]) // пять раз найдёт, что C=a - ооочень эффективно
    ?- abstring_with_item(C,S) // будет выдавать решения исключительно вида C=a, S=[a], [a,a], [a,a,a]...
    ?- abstring_with_item(b,S) // зависнет
    
    /*
    

    • +1
      Последнее, кстати, лечится так
      ab(a).
      ab(b).
      
      abstring([]).
      abstring([C|S]) :- ab(C), abstring(S).
      

      только abstring(S) теперь порождает решения не в лексикографическом порядке, а по возрастанию длины.
    • +1
      Там, где на других языках пришлось бы делать 2^N функций

      … это как раз то место, где «в других языках» придумывают функции высшего порядка.
      • 0
        В прологе ФВП тоже есть.
        И разумеется, можно сделать DSL времени исполнения или даже времени компиляции, делающий то же, что и пролог — одно выражение, 2^N сигнатур…
        Просто в других языках это придётся изобретать на месте, либо прибегать к библиотекам (каких-нибудь там комбинаторов, какого-нибудь там синтаксического сахара), а в прологе это есть из коробки, и является, что ли, философией языка.
        • +1
          В прологе ФВП тоже есть.

          В прологе есть мета-предикаты. А функций, насколько я понимаю, нет. И с мета-предикатами все тоже непросто.
  • 0
    Как насчет написания автоматических торговых систем на нем? кто-то делает такое?
    • 0
      Тема интересная, как раз для ПРОЛОГа.
      • 0
        Где-то есть сообщество программистов на ПРОЛОГе?
        • –1
          Есть какие-то форумы, больше для студентов.
          Если есть потребность, можно организовать новое сообщество.
  • 0
    10 лет назад когда учился в ВУЗе, одним из первых сдал лабораторки все по Прологу, а потом написал Курсовик на тему поиска пути по схеме метро. А потом еще несколько аналогичных курсовиков своим согруппникам.
    Сейчас конечно все забыл.
    Можно как то применять пролог в теме FPGA или разработке цифровых схем?
    • –1
      Если есть интерес, напишите мне письмо.

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