Prolog *

Введение

Многие считают, что язык программирования prolog является сугубо научным и устаревшим языком для обучения студентов. Большинство в университете «напрягали» именно этим языком на предметах, хоть немного приближенных к теме искусственного интеллекта, эта тема не обошла и меня.

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

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

1. Полюбите Рефал. Немедленно!

Всем известно, что есть такой язык программирования — Рефал. Рефал разработан в 1966 году нашим соотечественником Валентином Турчиным. Судьба у Рефала сложная, но язык до сих пор жив и развивается. Для интересующихся приведем несколько ссылок:

• Самостоятельное изучение Рефала-5. Взгляд студента
• Журнал «Практика функционального программирования», выпуск №7(светлая ему память!). Статьи «Язык РЕФАЛ — взгляд со стороны» и «Суперкомпиляция: идеи и методы»

Сильно утрируя, можно сказать, что Рефал — это смесь Лиспа и Пролога. В синтаксисе языка есть одна интересная особенность — сопоставление с образцом т.н. «прямым выводом».

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

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

Прочитав статью о Prolog, я решил написать небольшое дополнение к ней в виде 2 небольших задач.
Вот они:
1. Интерпретатор языка brainfuck
2. Машина Тьюринга

В этом топике пойдет речь о задаче Прима-Краскала (“жадный алгоритм”) и ее решении на языке «Пролог».

Начали!

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

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

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

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

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

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

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

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

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

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

Продолжаем неделю задачи Эйнштейна на Хабре. В дополнение к трём представленным решениям

1. Регулярным языком
2. Хаскеллем
3. Прологом

позвольте представить еще одно на Mercury.

Напомним Википедию:

Mercury — язык функционально-логического программирования со строгой типизацией…

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

Импорт фактов в базу пролога из файла в формате CSV

Для того чтобы работать с фактами базы данных в прологе их (факты) необходимо импортировать из внешнего источника.


На схеме условно показаны три области активностей:
Желтая — подготовка промежуточного файла. Для простого импорта это может быть просто сохранение документа в формате CSV. Для работы по регламенту возможна настройка компонентов БД (например MS SQL Server Integration Services) для периодической выгрузки. Данная активность в статье не рассматривается.
Красная — импорт данных из CSV файла в базу фактов.
Зеленая — работа с базой фактов в Прологе.
Примечание. Стрелками показаны потоки данных.

Вот тут наткнулся на, в общем-то, простую задачку состоящую в парсинге текстового файла, содержащего 5 миллионов float'ов (и подсчете их суммы). Файл генерируется следующим C#-кодом:

static void Main(string[] args)
{
  using (Stream stm = new FileStream(@"d:\numbers_large.txt", FileMode.Create))
  {
    TextWriter wr = new StreamWriter(stm);
    System.Random r = new System.Random();
    for (int i = 0; i < 5000000; i++)
    {
      double d=10000*r.NextDouble() * (r.NextDouble() > 0.7 ? -1.0 : 1.0);
      wr.Write("{0} ", d);
    }
    wr.Flush();
  }


Задача ставилась в контексте обсуждения производительности haskell'я в применении его к задачам парсинга. Я знал, что на прологе подобные задачи решаются красиво и непринужденно используя технику DCG (Definite clause grammar: 1, 2, 3, 4). Фактически, это описание грамматик на языке Пролог, и парсинг по ним, основанный на переборно-откатном принципе работы пролога.

Ну то есть обычно получается очень кратко и красиво (например, вот решение задачки о сбалансированности скобок этим методом: программа из 7 строк), но, я подозревал, что не всегда быстро. Собственно, это мне захотелось проверить.

Эта головоломка уже знакома Хабрахабру по этой публикации.

Суть головоломки в следующем (цитируя bor1s):

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

Пройти головоломку online можно по ссылке: http://freeweb.siol.net/danej/riverIQGame.swf.

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

Копаясь в поиске сайта, наткнулся на занимательную задачку и не смог отказать себе в удовольствии потратить 10 минут времени для решения её на полюбившемся мне прологе.

<br>% ((((1?2)?3)?4)?5)?6<br>solve(Formula) :-<br>    Signs = [+, -, *, //],<br>    member(Op1, Signs),<br>    member(Op2, Signs),<br>    member(Op3, Signs),<br>    member(Op4, Signs),<br>    member(Op5, Signs),<br>    A =.. [Op1, 1, 2],<br>    B =.. [Op2, A, 3],<br>    C =.. [Op3, B, 4],<br>    D =.. [Op4, C, 5],<br>    Formula =.. [Op5, D, 6],<br>    35 =:= Formula.<br>

Результат работы кода:

На правах развлечения в пятничный вечер.

<br>bracket("]") --> "[".<br>bracket(")") --> "(".<br>bracket("}") --> "{".<br><br>brackets --> bracket(Close), brackets, Close, brackets.<br>brackets --> [].<br><br>check(BracesStr) :-<br>    phrase(brackets, BracesStr), !.<br>

?- check("[[[]]][][[]][()]{}[]").
true.

?- check("[[[)]]][][[]][()]{}[]").
false.

P. S. Решение на вашем любимом ЯП приветствуется )

Довольно оживленное обсуждение предыдущей стати (http://habrahabr.ru/blogs/programming/47416/) показало, что тема пролога оказалась интересна сообществу.
Чтобы заинтересовать еще более читателя и вместе с тем облегчить ему начало работы с этим языком, я решил написать немного начальных данных о прологе.

Кратко основные особенности.

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

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