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

pred1(X, Y), pred2(Y, Z), pred3(Z).


в традиционных языках представляется чем-то вроде следующей вложенной конструкции

for Y in pred1(X) {
  for Z in pred2(Y) {
    pred3(Z)
  }
}


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

Однако, мы отвлеклись.

Вот тут наткнулся на, в общем-то, простую задачку состоящую в парсинге текстового файла, содержащего 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 минут времени для решения её на полюбившемся мне прологе.

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


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

?- findall(F, solve(F), L).
L = [ (1+2+3)*4+5+6, (1+2)*3*4+5-6, 1*2*3*4+5+6].


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

bracket("]") --> "[".
bracket(")") --> "(".
bracket("}") --> "{".

brackets --> bracket(Close), brackets, Close, brackets.
brackets --> [].

check(BracesStr) :-
    phrase(brackets, BracesStr), !.


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

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

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

Хм. Изобретал, писал статью, анализировал, и вот доанализировался. Выходит что на масштабах расспараллеливания, более крупных, чем автоматический внутри процессора, самый удобный метод описания взаимосвязи между параллельными компонентами программы - это файлы, хитрые, конечно, больше похожие на память, но файлы. При этом все попытки изобрести суперпупергипер систему для распараллеливания сводятся к созданию простой и эффективной распределённой файловой системы, не привязанной к дискам, конечно (привет Робу Пайку и Plan9). Но что самое занятное, всё это очень тесно связано с функциональным программированием и математикологическими предложениями Хорна. Можно на всё и так смотреть. Хых. Может быть, кину сюда статью, если условия публикации и карма позволят. Надо ещё попробовать в png выкладывать архивы : ) Руки всё не доходят.