Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 16
Ох…
А в Универе Пролог был моим любимым языком.
Из-за этого подсознательно немного в штыки воспринимал Лисп.
А в Универе Пролог был моим любимым языком.
Из-за этого подсознательно немного в штыки воспринимал Лисп.
Пролог… Как много в этом слове. После курса логического программирования и решения задач типа «Маша любит Васю, Женя живет в крайнем доме. Кто из них учитель?» остался только один вопрос. Ну как там работает отсечение? Ну как??!!! Помню с потока никто не мог объяснить как оно работает, но кажды знал, что если поставить вослицательный знак в «этот» предикат все сразу решится.
Отсечение лучше не использовать никогда :) Начинающим программистам, лучше избегать отсечений в середине и даже не думать о том, что бывают группы отсечений как a :- b, !, c, !, d (это не 2 отсечения!).
В принципе все можно выразить отсечением в конце или в начале к этому надо и стремиться.
a :- b,!..
a :- c,…
Отсечение в конце означает, что если 1-й предикат выполнится, то альтернатив не будет. То есть выполнится хотя бы один раз b, c никогда вызываться не будет и b больше вызываться не будет, хотя b может давать например несколько ответов!
a :- !, b.
a :- c,…
Отсечение в начале c никогда не вызывается, а b вызывается столько раз, сколько альтернатив ответов в b.
Наверное основную сложность составляет то, что вы можете вызывать предикат A в рекурсии или в нескольких местах и тогда контекст возврата к b становится непонятным и пугающим, поэтому используйте основное правило на каждое отсечение писать 2 строчки комментариев, почему и как оно работает.
В принципе все можно выразить отсечением в конце или в начале к этому надо и стремиться.
a :- b,!..
a :- c,…
Отсечение в конце означает, что если 1-й предикат выполнится, то альтернатив не будет. То есть выполнится хотя бы один раз b, c никогда вызываться не будет и b больше вызываться не будет, хотя b может давать например несколько ответов!
a :- !, b.
a :- c,…
Отсечение в начале c никогда не вызывается, а b вызывается столько раз, сколько альтернатив ответов в b.
Наверное основную сложность составляет то, что вы можете вызывать предикат A в рекурсии или в нескольких местах и тогда контекст возврата к b становится непонятным и пугающим, поэтому используйте основное правило на каждое отсечение писать 2 строчки комментариев, почему и как оно работает.
Вы бы хоть объяснили алгоритм с точки зрения логического программирования. Не думаю, что тут много людей с этим знакомы, да и с синтаксисом Prolog. Я один, например, не понимаю, зачем предикат(или тут так любая функция называется?) вставляет что-то или ищет минимум?
Хотел немного помочь с форматированием, но как-то чересчур увлекся и получился аналогичный вариант решения, хотя идея та же.
% Вначале текущее множество рёбер устанавливается пустым.
% Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых
% к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса
% и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён.
% Пример запроса (картинка http://www.youtube.com/watch?v=vm_9-vnV7PE)
example(Res) :- city([edge(1,3,13), edge(1,4,19),edge(3,2,20),edge(4,2,4), edge(2,5,15), edge(4,7,17),edge(5,7,8),edge(5,6,22),edge(7,6,10)], Res).
city(DistanceCities, ResultConfiguration) :- city(DistanceCities, [], ResultConfiguration).
% city(DistanceCities, ExistingConfiguration, ResultConfiguration)
% ищем минимальное ребро : если найдено, то 1) продолжаем выделять ребра,
% добавив найденное к существующим ,если не найдено - 2) алгоритм завершен
city(Distances, Existing, ResultConfiguration) :-
(pick_minimum_edge_wo_cycle(Distances, Existing, Edge) ->
city(Distances, [Edge | Existing], Result), ResultConfiguration = [Edge | Result] ;
ResultConfiguration = [] ) .
% Выбирает минимальное ребро не образующее цикла,
% Нисходящая рекурсия сравнивает уже выбранное допустимое минимальное ребро
% на предыдущих шагах (1-й выбор []) с текущим ребром, проверяя допустимость
% Восходящая рекурсия возвращает результат и проверяет, что не [].
pick_minimum_edge_wo_cycle(Distances, Existing, Edge) :-
pick_minimum_edge_wo_cycle(Distances, Existing, [], Edge), not(Edge = []).
pick_minimum_edge_wo_cycle([], _, ToCompare, ToCompare).
pick_minimum_edge_wo_cycle([Edge|L], Existing, ToCompare, Result) :- (
(less_edge(Edge, ToCompare), no_cycle(Edge, Existing) ) ->
pick_minimum_edge_wo_cycle(L, Existing, Edge, Result) ;
pick_minimum_edge_wo_cycle(L, Existing, ToCompare, Result) ).
% Сравнение ребер - возвращает true если 1-е меньше 2-го
less_edge(edge(_X1, _Y1, Z1), edge(_X2, _Y2, Z2)) :- Z1 < Z2.
less_edge(edge(_X1, _Y1, _Z1), []).
% Проверка что нет цикла
no_cycle(edge(X, Y, _), Existing) :- not(search(X, Y, Existing, [])).
% реализует поиск пути от вершины Х к вершине Y
% алгоритм поиска - поиск в глубину.
search(X, Y, Edges,_):- member(edge(X,Y,_), Edges).
search(X, Y, Edges,_):- member(edge(Y,X,_), Edges).
search(X, Y, Edges, PassedVertices):- member(edge(X,Z, _),Edges),
not(member(Z, PassedVertices)), search(Z,Y,Edges,[Z|PassedVertices]).
search(X, Y, Edges, PassedVertices):- member(edge(Z,X, _),Edges),
not(member(Z, PassedVertices)), search(Z,Y,Edges,[Z|PassedVertices]).
Уникальная ситуация с прологом. Исторически сложилось так, что на всех компьютерных специальностях его преподают. Вместе с тем, нигде он не используется на практике. Студентам показывают невероятные возможности языка, а потом они уходят в недоумении: «Зачем оно нужно?».
Задавался тем же вопросом. 60-70-е годы — ладно, тот же Буран управлялся программой на Прологе.
Но вот сейчас он где-нибудь используется?
Но вот сейчас он где-нибудь используется?
Уникальная ситуация, поскольку и язык уникальный. А где его толком применишь? Только разве что для упорядочивания мышления.
А создателям Бурана это делает честь… Жаль, что он не взлетел.
А создателям Бурана это делает честь… Жаль, что он не взлетел.
Упоминания о том, что ПО Бурана писалось на ЯП под названием «Пролог» я встречал. Но ни где не видел ни подтверждения, ни опровержения того, что «тот» пролог и «этот» — одно и то же.
Что вообще можно почитать про ПО Бурана?
Желательно не обзор на пол-странички, а более детально.
Что вообще можно почитать про ПО Бурана?
Желательно не обзор на пол-странички, а более детально.
Я уже забыл особенности программирования на прологе (а они забываются быстро), но запомнил мысль, мелькающую у меня в голове во время изучения: на базе пролога можно создать мощнейшую СУБД. Может и бред… К сожалению, нет времени восполнить знания.
www.vldb.org/journal/VLDBJ3/P245.pdf
Почему этот проект не взлетел, неизвестно. Больше упоминаний о нём я не видел. Надо будет написать вопрос кому-нибудь из Мельбурнского университета, поинтересоваться. Сейчас там делают язык программирования Mercury — какой-то статически типизированный пролог.
Я тоже всегда считал что для общих задач программирования пролог подходит очень слабо. А вот как база данных и язык запросов он может дать большую фору SQL.
На нём в несколько символов записываются join'ы, в один запрос можно запросить информацию рекурсивно без хранимых процедур. Да и задание запросов сложными предикатами более гармонично чем хранимые процедуры SQL.
stackoverflow.com/questions/2117651/difference-between-sql-and-prolog
Есть ещё подмножество пролога под называнием Datalog. Этот язык ориентирован исключительно на базы данных, без всяких процедурных функций. Но, практических реализаций я не нашёл. Только прототипы и программы для обучения.
У меня тоже зреет мысль разработать субд на базе пролога. И хотя WAM реализуется достаточно быстро, на минимально готовый продукт уйдёт несколько человеколет. Да и рынок такая субд взорвёт не сразу. Поэтому придётся отложить реализацию до времён, когда появятся такие свободные ресурсы.
Почему этот проект не взлетел, неизвестно. Больше упоминаний о нём я не видел. Надо будет написать вопрос кому-нибудь из Мельбурнского университета, поинтересоваться. Сейчас там делают язык программирования Mercury — какой-то статически типизированный пролог.
Я тоже всегда считал что для общих задач программирования пролог подходит очень слабо. А вот как база данных и язык запросов он может дать большую фору SQL.
На нём в несколько символов записываются join'ы, в один запрос можно запросить информацию рекурсивно без хранимых процедур. Да и задание запросов сложными предикатами более гармонично чем хранимые процедуры SQL.
stackoverflow.com/questions/2117651/difference-between-sql-and-prolog
Есть ещё подмножество пролога под называнием Datalog. Этот язык ориентирован исключительно на базы данных, без всяких процедурных функций. Но, практических реализаций я не нашёл. Только прототипы и программы для обучения.
У меня тоже зреет мысль разработать субд на базе пролога. И хотя WAM реализуется достаточно быстро, на минимально готовый продукт уйдёт несколько человеколет. Да и рынок такая субд взорвёт не сразу. Поэтому придётся отложить реализацию до времён, когда появятся такие свободные ресурсы.
Введение в Пролог было в советских учебниках по ОИВТ. С русскоязычными именами предикатов.
Но увы, нам ничего, кроме бейсика на уроках информатики не давали.
Но увы, нам ничего, кроме бейсика на уроках информатики не давали.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача Прима-Краскала на языке Пролог