Роль логического программирования, и стоит ли планировать его изучение на 2021-й

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

Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.

"Мда" - думаете Вы, и этим все сказано. Сложно! И тут наш отважный герой должен бы был перейти по второй ссылке, но я позволю себе сделать небольшую вставку, описав главное действующее лицо: Вы, по моей задумке, новичок в программировании, а даже если и нет, то точно не знакомы с логическим его обличием. Если же читатель уже несколько (или даже много) искушен знаниями в этой области, то рекомендую прочитать статью Что такое логическое программирование и зачем оно нам нужно, раз уж в вас горит интерес и любопытство к теме, а изучение материала ниже оставьте менее опытным коллегам.

Итак, пришло время второй ссылки. Что это будет? Статья на Хабре? Может быть статья на ином ресурсе? Прочитав пару первых абзацев на разных сайтах, вы, скорее всего, мало что поймете, так как, во-первых, материал обычно ориентирован на знающего читателя, во-вторых, хорошей и понятной информации по теме не так много в русскоязычном интернете, в-третьих, там почему-то постоянно речь идёт о некоем "прологе" (речь о языке программирования Prolog, разумеется), но сам язык, кажется, использует мало кто (почётное 35 место в рейтинге TIOBE). Однако наш герой не теряет мотивации и, спустя некоторое время, натыкается на эту самую статью, желая, все-таки понять:

  • Что такое логическое программирование

  • Какова история его создания и фундаментальные основы (серьезно, какому новичку это может быть интересно?)

  • Зачем и где его применяют

  • Стоит ли лично вам его изучать

Что ж, постараюсь ответить просто и понятно, обходя страшные термины и не вспоминая исторических личностей.

Что такое логическое программирование

В школе на уроках информатики многие, если не все, слышали про Pascal (а кто-то даже писал на нем). Многие также могли слышать про Python, C/C++/C#, Java. Обычно программирование начинают изучать именно с языков из этого набора, поэтому все привыкли, что программа выглядит как-то так:

Начать
Команда1
Команда2
Если УСЛОВИЕ
  Команда3
Иначе
  Команда4
Закончить

Этот яркий, но малоинформативный пример призван показать, что обычно команды выполняются одна за другой, причем мы ожидаем, что следующие инструкции (команды) могут использовать результат работы предыдущих. Также мы можем описывать собственные команды, код которых будет написан подобным образом. Остановимся на том, что как завещал Фон Нейман, так компьютер и работает. Машина глупа, она делает то, что скажет программист, по четкому алгоритму, последовательно выполняя инструкции. Не может же, в конце концов, компьютер, подобно мыслящему живому существу, делать выводы, строить ассоциативные ряды… Или может?

Давайте устроимся поудобнее рядом со своим компьютером и порассуждаем о жизни и смерти вместе с Аристотелем:

Всякий человек смертен.

Сократ - человек.

Следовательно, Сократ смертен.

Звучит логично. Но есть ли способ научить компьютер делать выводы как Аристотель? Конечно! И вот тут мы вспомним о Prolog-e, который так часто мелькает при поиске информации о логическом программировании. Как несложно догадаться, Prolog (Пролог) является самым популярным чисто логическим языком программирования. Давайте рассуждения об этом языке оставим на следующие разделы статьи, а пока что продемонстрируем "фишки" логических языков, используя Пролог.

Напишем небольшую программу, где перечислим, кто является людьми (ограничимся тремя) и добавим правило "всякий человек смертен":

% Всё, что после знака процента в строке - комментарии
human('Plato'). % Платон - человек
human('Socrates'). % Сократ - тоже человек
human('Aristotle'). % Конечно, человеком был и Аристотель
% ...и др. философы

mortal(X) :- human(X). % Читаем так: "X смертен, если X - человек"

Что ж, давайте спросим у компьютера, смертен ли Сократ:

?- mortal('Socrates').
true.

Компьютер выдал нам сухое "true", но мы, конечно, вне себя от счастья, так как вот-вот получим премию за успешное прохождение нашим умным устройством теста Тьюринга.

Так, теперь стоит успокоиться и разобраться, что же произошло. Вначале мы записали т. н. факты, то есть знания нашей программы о мире. В нашем случае ей известно лишь то, что Платон, Сократ и Аристотель - люди. Но что за странная запись "human('Socrates')." и почему это выглядит как функция? На самом деле "human" и "mortal" - предикаты от одной переменной. Да, тут уже пошли термины, но постараюсь объяснять их просто и понятно для тех, кто привык к императивному нормальному программированию.

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

% слова с большой буквы Prolog считает переменными, поэтому их следует заключать в кавычки
like('Petya', 'Milk'). % программа знает, что Петя любит молоко
good('Kesha'). % Кеша хороший
number_of_sides('Triangle', 3). % у треугольника три вершины

like('Misha', X). % не является фактом, так как значение переменной X не определено

Помимо фактов в логической программе присутствуют правила вывода. В данном случае это "mortal(X) :- human(X).". Набор правил вывода - это знания нашей программы о том, как выводить (искать/подбирать) решение. Правила записываются следующим образом:

a(X,Y,Z) :- b(X), c(Y,Z), d().

Предикат a от трех аргументов вернет истину, если удастся доказать истинность предикатов b, c и d. Читаются правила справа налево следующим образом: "Если b от X истинно И c от Y, Z истинно И d истинно, то a от X, Y, Z истинно".

Уже на таком небольшом примере видно, что мы не описываем четко последовательность действий, приводящую к нужному результату. Мы описываем необходимые условия, при выполнении которых результат будет достигнут. Тут будет к слову упомянуть, что раз компьютер сам для нас выводит способ достижения результата на основе известных правил, то и использовать один и тот же код можно по-разному:

% Опишем набор фактов о том, кто что обычно ест на завтрак в семье Пети
eat(father, cheese).
eat(father, apple).
eat(father, melon).
eat(mother, meat).
eat(sister, meat).
eat('Petya', cheese).
eat(brother, orange).

Теперь начнём делать запросы к программе (всё те же предикаты):

?- eat(father, apple). % ест ли отец яблоки
true.

?- eat(father, meat).  % ест ли отец мясо
false.

?- eat(sister, X). % что ест сестра
X = meat.

?- eat(X, cheese). % кто ест сыр
X = father ;
X = 'Petya'.

?- eat(X, Y). % кто что ест
X = father,
Y = cheese ;
X = father,
Y = apple ;
X = father,
Y = melon ;
X = mother,
Y = meat ;
X = sister,
Y = meat ;
X = 'Petya',
Y = cheese ;
X = brother,
Y = orange.

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

Какие задачи и как можно решать с помощью логического программирования

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

d(X,X,1) :- !. % производная X по X = 1
d(T,X,0) :- atomic(T). % производная константы = 0
d(U+V,X,DU+DV) :- d(U,X,DU), d(V,X,DV). % производная суммы = сумме производных
d(U-V,X,DU-DV) :- d(U,X,DU), d(V,X,DV). 
d(-T,X,-R) :- d(T,X,R).
d(C*U,X,C*W) :- atomic(C), C\=X, !, d(U,X,W). % производная константы, умноженной на выражение = константе на производную от выражения
d(U*V,X,Vd*U+Ud*V) :- d(U,X,Ud), d(V,X,Vd). % производная произведения
d(U/V,X,(Ud*V-Vd*U)/(V*V)) :- d(U,X,Ud), d(V,X,Vd). 

Запустим:

?- d((x-1)/(x+1),x,R).   
R =  ((1-0)*(x+1)-(1+0)*(x-1))/((x+1)*(x+1)).

Пусть производная получилась довольно громоздкой, но мы и не ставили цель её упростить. Главное, из примера видно, что правила вывода производной на Prolog-е описываются очень близким образом к их математическому представлению. Чтобы сделать подобное на привычных языках программирования, пришлось бы вводить понятие дерева выражений, описывать каждое правило в виде функции и т. д. Тут же мы обошлись 8-ю строками. Но здесь важно остановиться и задуматься: компьютер не начал работать как-то иначе, он все ещё обрабатывает последовательности команд. Стало быть, те самые деревья, которые где-то все-таки должны быть зашиты, чтобы программа работала, действительно присутствуют, но в неявном виде. Деревья эти именуют "деревьями вывода", именно они позволяют подбирать нужные значения переменных, перебирая все возможные варианты их значений (существует механизм отсечения, который является надстройкой над логической основой языка, но не будем об этом).

Давайте на простом примере рассмотрим, что из себя представляет перебор, а затем то, чем он может быть опасен.

speciality(X,tech_translator) :- studied_languages(X), studied_technical(X). % X - технический переводчик, если изучал языки и технические предметы
speciality(X,programmer) :- studied(X,mathematics), studied(X, compscience). % X - программист, если изучал математику и компьютерные науки
speciality(X,lit_translator) :- studied_languages(X), studied(X,literature). % X - литературный переводчик, если изучал языки
studied_technical(X) :- studied(X,mathematics). % X изучал технические предметы, если изучал математику
studied_technical(X) :- studied(X,compscience). % ...или компьютерные науки
studied_languages(X) :- studied(X,english). % X изучал языки, если изучал английский
studied_languages(X) :- studied(X,german). % ...или немецкий

studied(petya,mathematics). % Петя изучал математику
studied(petya,compscience). % ...компьютерные науки
studied(petya,english). % ...и английски
studied(vasya,german). % Вася изучал немецкий
studied(vasya,literature). %...и литературу

Спросим, кто из ребят, известных компьютеру - технический переводчик:

?- speciality(X,tech_translator).
X = petya ;
X = petya ;
false.

Ага…то есть Петя, Петя и ложь… Что-то не так, подумает программист и попробует разобраться. На самом деле, перебирая все варианты значений X, Пролог пройдёт по такому дереву:

Дерево будет обходиться в глубину, то есть сначала рассматривается всё левое поддерево для каждой вершины, затем правое. Таким образом, Пролог дважды докажет, что Петя - технический переводчик, но больше решений не найдёт и вернёт false. Стало быть, половина дерева нам, в общем-то, была не нужна. В данном случае, перебор не выглядит особенно страшным, всего-то обработали лишнюю запись в базе. Чтобы показать "опасность" перебора, рассмотрим другой пример:

Представим, что перед нами в ячейках расположены три чёрных и три белых шара (как на картинке выше), которые требуется поменять местами. За один ход шар может или передвинуться в соседнюю пустую клетку, или в пустую клетку за соседним шаром ("перепрыгнуть" его). Решать будем поиском в ширину в пространстве состояний (состоянием будем считать расположение шаров в ячейках). Суть этого метода заключается в том, что мы ищем все пути длины 1, затем все их продления, затем продления продлений и т. д., пока не найдем целевую вершину (состояние). Почему поиск в ширину? Он первым делом выведет самый оптимальный путь, то есть самый короткий. Как может выглядеть код решения:

% Обозначения: w - белый шар, b - чёрный, e - пустая ячейка
is_ball(w). % w - шар
is_ball(b). % b - шар

near([X,e|T],[e,X|T]) :- is_ball(X). % если фишка рядом с пустой ячейкой, то можно переместиться
near([e,X|T],[X,e|T]) :- is_ball(X).
jump([X,Y,e|T],[e,Y,X|T]) :- is_ball(X), is_ball(Y). % если за соседним шаром есть пустая ячейка, то можно переместиться
jump([e,Y,X|T],[X,Y,e|T]) :- is_ball(X), is_ball(Y).

% предикат перемещения. Мы или рассматриваем первые элементы списка, или убираем первый элемент и повторяем операцию
move(L1,L2) :- near(L1,L2). 
move(L1,L2) :- jump(L1,L2).
move([X|T1],[X|T2]) :- move(T1,T2).

% предикат продления текущего пути. Если из состояния X можно перейти в состояние Y и
% Y не содержится в текущем пути, то Y - удачное продление
prolong([X|T],[Y,X|T]) :- move(X,Y), not(member(Y,[X|T])).

% Первый аргумент - очередь путей, второй - целевое состояние, третий - результат, то есть найденный путь
bdth([[X|T]|_],X,R) :- reverse([X|T], R). % Поиск в ширину нашел решение, если первый элемент пути совпадает с целью (путь наращивается с начала, так что перевернем результат)
bdth([P|QI],Y,R) :- bagof(Z,prolong(P,Z),T), append(QI,T,QO), !, bdth(QO,Y,R). % Ищем все возможные продления первого пути и кладём в очередь, рекурсивно запускаем поиск
bdth([_|T],Y,R) :- bdth(T,Y,R). % Если продлений на предыдущем шаге не нашлось, то есть bagof вернул false, убираем первый путь из очереди
bsearch(X,Y,R) :- bdth([[X]],Y,R). % Удобная обёртка над предикатом bdth

% Предикат, который решает нашу задачу и выводит результат и длину найденного пути на экран
solve :- bsearch([w,w,w,e,b,b,b],[b,b,b,e,w,w,w],P), write(P), nl, length(P, Len), write(Len), nl.

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

Со стороны улучшения алгоритма можно предложить использовать поиск в глубину. Но как же, он ведь не даст оптимального результата? Сделаем просто: ограничим глубину поиска. Так мы точно не забьём стек и, возможно, получим ответ. Поступим так: проверим, есть ли пути длины 1, затем длины 2, затем длины 4 и т. д. Получим так называемый поиск с итерационным заглублением:

% Первый аргумент - текущий путь, второй - целевое состояние, третий - результат, то есть найденный путь
dpth_id([X|T],X,R,0) :- reverse([X|T], R). % Успешное окончание поиска
dpth_id(P,Y,R,N) :- N > 0, prolong(P,P1), N1 is N - 1, dpth_id(P1,Y,R,N1). % Если счётчик >0, то уменьшаем его и продолжаем поиск рекурсивно
generator(1). % Изначально предикат вернет 1
generator(N) :- generator(M), N is M + 1. % Рекурсивно получаем 2, 3, 4 и т. д.
isearch(X,Y,R) :- generator(D), dpth_id([X],Y,R,D). % Удобная обертка, которая будет вызывать поиск от каждого натурального значения глубины.

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

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

near([w,e|T],[e,w|T]).
near([e,b|T],[b,e|T]).
jump([w,X,e|T],[e,X,w|T]) :- is_ball(X).
jump([e,X,b|T],[b,X,e|T]) :- is_ball(X).

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

Зачем и где применяют логическое программирование

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

  • Анализ естественного языка: Пример с производной - классический пример разбора выражений. Но если мы заменим арифметические операторы, переменные и числа на слова, добавим правила, скажем, английского языка, то сможем получить программу, разбирающую текст на структурные элементы. Занимательно, что одновременно мы получим и программу, способную генерировать текст. Но если логическое программирование можно удобно и эффективно использовать для анализа и разбора текста, то в задачах генерации качественного текста скорее придется обращаться к нейросетям. Тут важно отметить, что рассуждая об анализе и генерации предложений нельзя не упомянуть сложность решения подобных задач. Человек при составлении и восприятии текста ориентируется не только на набор слов и их значений, но и на свою картину мира. К примеру, если в базе лежит факт "Миша починил Маше компьютер", то на вопрос "Разбирается ли Миша в компьютерах?" программа не сможет ответить, не смотря даже на то, что решение вроде как "на поверхности". Именно из-за низкой скорости и особенностей использования на чисто логических языках не занимаются тем, что мы ждем увидеть, загуглив "нейросети" (поиск котиков на картинке, например, не для Пролога). Но вот задачи синтаксического разбора, текстовой аналитики и т. п. на логических языках решать очень даже комфортно.

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

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

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

Стоит ли планировать его изучение на 2021-й

Тут оставлю своё субъективное мнение, разделённое на две части:

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

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

И здесь остаётся лишь пожелать продуктивного 2021-го года!

Хочется выразить особую благодарность Дмитрию Сошникову за знакомство с этой удивительной парадигмой.

Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 16

    +4

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


    По существу статьи. Как мне кажется, самыми показательными примерами эффективного применения Прлога являются те самые задачки из серии "Эйнштейн говорил, что эту задачу может решить только один процент населения". Ну там еще обычно перечисляется гора фактов про то кто курит трубку, кто любит бифштекс, а кто женат на миссис Хопкинс. Ещё есть серия детективно-логических задачек с распутыванием фактов.
    В институте же меня, как обладателя большой шоблы родственников разного колена, сильнее всего торкнуло применение пролога для работы с базой данных родственных связей. Кто там кому шурин, кто кому деверь, тётя или внучатый племянник — разбираться в этом страшная морока. А прога щёлкает и перебирает сочетания и хитросплетения связей на раз-два, причем описывается всё на заглядение прозрачно и читабельно.


    А ещё большой не закрытый гештальт у меня подвис с прологом в применении его для системы квестов в игровой индустрии. Когда я ворвался неопытный в первый свой геймдев-проект (ага, ММОРПГ в открытом мире=), у меня не хватило времени на внедрение пролога для квестовой логики, я ограничилася обычными тупыми конечными автоматами. Однако, какой потенциал!


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

      0
      Спасибо за такую позитивную оценку!
      Идеи действительно интересные, а комментарий читается с удовольствием.

      Насчёт логических задач про «того самого студента»: действительно, их решение доставляет удовольствие, это ярко и способно занять на часы, но, всё же, и тут моё личное мнение, новичок не сразу свяжет их с практическим применением пролога. Но решать определенно стоит!
        +1
        > Ещё есть серия детективно-логических задачек с распутыванием фактов…
        Можно ссылку?
        > по принципу известной игры «Зоопарк»
        И на это ссылку, плз. Подозреваю, что это нечто похожее на Акинатора
          +1

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

            0
            где-то видел описание такой программы на бейсике, которая угадывает животных, а если не угадывает, то предлагает задать вопрос про задуманное животное и тут же ответить на него

            Нашёл.
            Это журнал «Наука и жизнь» №12 за 1986, В. Щеглов, «Животные (игра)».

            Лично для меня пропуском в мир программирования стал цикл статей «Человек с микрокалькулятором» в этом журнале, посвященный калькулятору Б3-34.
              0

              Офигеть! Как? Это в голове такой индекс по статьям из журналов?
              Не затруднит фоточку со статьёй сюда запостить? Очень интересно.

                0
                Офигеть! Как?

                Помню, что, на заре моей компьютерной грамотности, оную я черпал именно из журнала «Наука и жизнь». Первые шаги в освоении каких-либо знаний обычно запоминаются прочно. Вот и я вспомнил, что читал разбор этой программы на Бэйсике. Рубрики, посвященные азам программирования, назывались «Человек с микрокалькулятором» и «Человек и компьютер», про микрокалькулятор здесь явно не в кассу. Вбиваю в Яндекс «наука и жизнь человек и компьютер»:
                yandex.ru/search/?text=наука%20и%20жизнь%20человек%20и%20компьютер
                и вон третья ссылка со словами "Архив публикаций рубрик «Человек и компьютер», «Человек с микрокалькулятором» и других публикаций на тему программируемых калькуляторов из журнала «Наука и жизнь»." намекает, что там и надо смотреть.
                Остаётся только пробежать страницу глазами, найти упоминанние статьи «животные» и понять, что это и есть искомое.

                Вот такой нехитрый алгоритм.
                Ссылки на саму статью в перечне нет, соответственно и фото предоставить не могу.

                ЗЫ. Да вот вам ссылочка:
                http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/_''Nauka_i_jizn'''_1980-89_.html
                http://publ.lib.ru/ARCHIVES/N/%27%27Nauka_i_jizn%27%27%27/''Nauka_i_jizn''',1986,N12.[djv-fax].zip
        +2
        Спасибо за статью.
        А можно с помощью логического программирования вычислять, скажем, линейную или логическую регрессию?
        Учил Пролог в школе, но применений в реальной практике не могу пока найти.
          0
          К сожалению, я не являюсь специалистом в области анализа данных, поэтому дать ответа, который бы удовлетворил Ваш интерес, не смогу.

          Замечу только, что Пролог (с учётом механизма отсечения (cut)) обладает полнотой по Тьюрингу, а значит на нем реализуема любая вычислимая функция.
            +2

            Пролог не делает никаокго волшебства по сравнению с императивными программами. Напротив, нужно изголяться и оптимизировать её перебор дерева решений всякими отсечениями. В среднем, как верно отметил, кажется, автор статьи, пролог будет медленнее, чем хорошо оптимизированное решение императивным способом.
            Однако, языки программирования придуманы не для компьютеров, а для людей, чтобы на них легче было изъясняться и легче читать. Пролог позволяет лаконично формулировать условия задач, которые совместимы с дискретной логикой. Также можно исхитриться и делать решения в обратимых линейных операциях вроде сложения, вычитания. Умножение на ноль уже будет вносить трудности, а всякие синусы и прочие нелинейности и подавно.
            Если дерево решений не разнесёт комбинаторным взрывом, то можно добиваться достаточно эффективных решений, чтобы соблазниться простойтой и читабельностью пролога и не погрязнуть в его слабых местах.
            На прологе хорошо решать задачи, связанные с контролем зависимостей (даже. вроде, кто-то говорил, что в системах кнтроля версий таки используетя). В геймдеве, как я упоминал. роль пролога, мне кажется, недооценена. Экспертные системы, втом числе со взвешенными правилами тоже можно легко формализовать на этом языке. Код н апрологе вполне можно обрабатывать как данные. например, автоматически генерировать факты на основе данных из БД и внешнего мира, генерировать просты предикаты логических зависимостей, взвешивать эти предикаты и осуществлять рейтингование варантов решений.


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


            Нет ничего хуже, чем "Умный" Дом, основанный, скажем, на нейронных сетях, который не может "объяснить" почему он принял то или иное решение. таким домом трудно управлять. Он — слишком "черный ящик", а в черном ящике жить не очень уютно.


            Ещё. мне кажется, пролог еще вспомнят в контексте всяких голосовых помощников и электронных секретарей. Оптимальные решение конфликтов с расписаниями, логика доступности локаций, логика учета интересов…

            +2

            Это, пожалуй, уже четвёртая или пятая вводная статья по прологу на хабре с плюс-минус одинаковыми примерами, на которых далеко не уедешь. Решить условный судоку, примеры кода для которого размазаны по всему интернету, легко, но стоило мне попробовать решить головоломку посложнее из одной из компьютерных игр — мозгов, чтобы описать модель, не хватило без опыта-то.


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


            1. Каково состояние языка и отрасли сейчас? Компиляторы/интерпретаторы, диалекты, как часто выходят новые версии и т.д. (читайте — «живое» ли оно ещё).
            2. Рекомендуемые книги, курсы? Насколько они свежие и соответствуют текущим реалиям?
            3. Есть ли конкретные опенсорс-проекты, в которых пролог используется? Думаю, может быть полезно, если захочется подсмотреть best practices.
            4. Всё остальное, что может помочь в изучении.

            Считайте это реквестом :)

              +1
              Спасибо за фидбек!
              Хочу отметить, что целью написания статьи было именно замотивировать изучать логическое программирование (!= Пролог), так как те вводные статьи, которые я нашел, недостаточно просты и понятны.

              Ответы на вопросы 1 и 3, как мне кажется, неплохо даны здесь: habr.com/ru/company/ruvds/blog/525014

              На второй вопрос: курсы — увы, и здесь, думаю, всё ясно; книги широко представлены в тех статьях, о которых Вы упомянули, и во многих других.

              Думаю, было бы действительно полезно и нужно собрать подробные ответы на эти вопросы, но это материал для отдельной статьи. Не отрицаю, что она может появиться и за моим авторством :)
                0

                Спасибо заранее! Буду ждать.

              +1
              Ровно то же самое я читал и десять лет назад, и двадцать. Судя по всему, Пролог застыл на определенной точке и зашел в тупик.

              А задачки типа эйнштейновой куда проще решать специализированными программами, работающими по принципу constraint programming. Например, очень удобная MiniZinc.
                +1

                Мне было бы интересно посмотреть на решение задачи, где исходные данные поступают из текстового файла некоторого формата. Например банальный word-count.

                  +1

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

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

                  Самое читаемое