0,0
рейтинг
20 декабря 2008 в 23:47

Разработка → Немного о Prolog'е

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

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



Условие задачи: Сократ — человек. Все люди смертны.
Найти: Смертен ли Сократ?

Запишем условие в терминах языка пролога (со знака % начинаются комментарии):
% Сократ - человек
human(sokrat).
% Платон - тоже человек
human(platon).

% Чтобы некто был смертным, он должен быть человеком
mortal(Someone) :- human(Someone).


* This source code was highlighted with Source Code Highlighter.

теперь спросим пролог систему, смертен ли Сократ:
?- mortal(sokrat).

Yes % да

?- mortal(stranger).

No % нет, поскольку пролог система не знает ничего о stranger и потому, не может ответить на вопрос

% Мы можем спросить какие смертные существа известны системе:
?- mortal(Who).

Who = platon ;

Who = sokrat


* This source code was highlighted with Source Code Highlighter.

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

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

Собственно, хочу привести для примера решение на прологе задачи о расстановке на шахматной доске 8 ферзей, так чтоб они не били друг друга, основанное на приведенном в книге Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта (кстати, очень хорошая книга, рекомендую).
% будем искать решение как набор 8 координат вида X/Y каждого из ферзей
% при этом понятно, что поскольку все вертикали так или иначе будут заняты
% задача сводится к отысканию соответствующих Y - координат
getSolution(S):-
    S=[1/_,2/_,3/_,4/_,5/_,6/_,7/_,8/_],
    solution(S).

% доска 0x0 без ферзей очевидно является решением
solution([]).

% доска NxN является решением, если является решением её под-доска (N-1)*(N-1),
% а первый ферзь не бьет ферзей на этой под-доске.
solution([X/Y | Others]) :-
    solution(Others),
    member(Y, [1, 2, 3, 4, 5, 6, 7, 8]),
    nokill(X/Y, Others).
         
% очевидно что ферзь с любыми координатами не бьет ферзей из пустого массива,
% поскольку просто некого бить
nokill(_, []).        

% ферзь не бьет набор ферзей если он не бьет первого ферзя из набора
% и не бьет остальных ферзей набора        
nokill(X/Y, [X1/Y1 | Others]) :-
    Y =\= Y1,   % на разных горизонталях  
    Y1-Y =\= X1-X, % на разных диагоналях
    Y1-Y =\= X-X1,
    nokill(X/Y, Others).


* This source code was highlighted with Source Code Highlighter.

Чтоб получить необходимые координаты ферзей, спросим у пролог системы решения, основанные на представленном описании.
1 ?- getSolution(P).

P = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1] ;

P = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1] ;

P = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1] ;

P = [1/3, 2/6, 3/4, 4/2, 5/8, 6/5, 7/7, 8/1] ;

P = [1/5, 2/7, 3/1, 4/3, 5/8, 6/6, 7/4, 8/2] ;
...


* This source code was highlighted with Source Code Highlighter.


Кстати, а как это будет выглядеть на вашем любимом языке программирования? =)

Кстати, тут можно посозерцать решение той же задачи на рефале, еще одном интересном языке функционального программирования, идейно перекликающимся с прологом, кстати, создатель которого — наш соотечественник Валентин Федорович Турчин (вики).
Владимир Губарьков @xonix
карма
131,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

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

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

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

  • –2
    хабракат еще никому не навредил
    • +5
      спасибо, запамятовал
    • +2
      Кроме тех, кто о нем упоминает, конечно. Вы разве не замечали, что комментарий типа «вставь хабракат» всегда набирает от двух-трех до 10-20 минусов?
      • +10
        конечно заметил, но кто-то же должен сказать, иначе если автор не вспомнит то так и останется )
        • 0
          А может в личку?
          • +1
            наверное тогда, это будет не наглядно и не агитационно для других пользователей?!
            • 0
              Надоело ведь первый пост про хабракат видеть.
    • +8
      Kеenn прав, я очень дружелюбный.
  • +4
    «Дело в том, что пролог, по сути единственный язык, предлагающий качественно другой подход к программированию, чем хорошо известные императивный, ООП»

    Прям уж единственный? ;)
    • 0
      на сколько знаю, да ) у Вас другие сведения?
      Эрланг, например, выходил из пролога, даже синтаксис похож, но этим все ограничивается, ибо это обычный функциональный язык
      • +1
        Нам в университете объясняли, что пролог относится к логическим языкам программирования, и что путать логические и функциональные языки, такие, как эрланг или лисп нельзя.
        • +2
          я где-то написал обратное? oO )
      • 0
        en.wikipedia.org/wiki/Mercury_programming_language
        • 0
          согласен, я даже знал о нем, только он гораздо менее известен чем пролог, кстати реализаций разных прологов существует просто уйма (десятки)
          • 0
            Они всё еще используются?
            • +1
              как ни странно да, довольно часто, например в составе разных систем для решения узко-специализированных задач, да и на прологе можно клепать вполне себе удобные DSL-и.
              Возможно это будет неожиданность, но даже согласно индексу Tiobe популярности языков программирования www.tiobe.com/index.php/content/paperinfo/tpci/index.html пролог (27 место) обгоняет таких зубров как Erlang (29) и Haskell (33)
            • 0
              пролог тоже мало используется
      • –2
        нет не единственный. есть определенное количество не императивных яп, которое не ограничивается прологом и ерлангом…
        • +3
          речь идет о том, что пролог — практически единственный в своем роде язык логического программирования, прочитайте внимательно, пролог и эрланг — совершенно разные вещи
      • 0
        Педантично говоря, как минимум два других логических языка известны и используются куда более. SQL и язык Makefile.
  • +18
    круто! Мне понравилось, спасибо. ИМХО, вот чего многие ждут от хабра =), именно таких статей.
    • 0
      Пожалуйста, рад что понравилось, сам уже где-то год прусь прологом, позже еще напишу 1-2 статьи, есть интересные идеи )
      • +1
        буду ждать! Я даже заказал уже книгу на books.ru под авторством Братко. Серьезно, конечно, вряд ли займусь, но очень увлекательно и главное познавательно.
        • 0
          Мне недавно такая книга в бумажном виде буквально случайно обломилась, был безмерно рад, почитываю на досуге ) И есть в эл. виде. Если надо, могу поделиться.
        • 0
          отличная книга. рекомендую
        • 0
          Есть в электронном виде. Я по ней в вузе учился. Кажись вот тут: foxweb.net.ru/oplata/55
      • 0
        Единственное — в конце слишком много «кстати» :-)
  • +2
    Да, пролог один из моих любимых яхыков, правда я на нем даавно ничгео не делал, но во время активного программирования ИИ и экспертных систем мне он очень полюбился. Использовал в основном swi-Prolog.
    Кстати видел проект, веб программирования на нем, к сожалению сайтов сейчас не вспомню.
    • 0
      да, тоже использую SWI ) Turbo и Vip не нравится тем, что надо описывать тип предикатов, а Vip к тому же еще чересчур «развитый» пролог, видимо далеко ушедший от классического Edinburg Prolog
      • 0
        swi еще легче всех в случае необходимости привязывается к с++. Да и вообще, к нему быстро привыкаешь)
  • +1
    топики в личном блоге не попадают на главную

    рекомендую перенести в тематический блог
    • 0
      Прошу прощения за ламерство, не посоветуете, как и в какой блог можно перенести? ) Есть ли что-то типа logic programming или declarative programming? Как на хабре посмотреть список существующих блогов? Спасибо.
      • +1
        в редактировании поста сверху есть комбобокс с блогами

        чтобы перенести в блог — надо сначала к нему присоедениться (нажать иконку штепселя)

        поиска по блогам здесь нет, есть список блогов: habrahabr.ru/top/blogs/

        я думаю, лучше всего перенести в «Языки программирования» → habrahabr.ru/blogs/programming/
        • 0
          спасибо, перенес
  • +7
    На самом деле Prolog — интересная игрушка для обучения, но как практический инструмент — он оставляет желать лучшего. Ибо провоцирует неряшливое программирование. Причём даже в этом примере это видно. Обратите внимание на то, что solution перебирает все возможные горизонтали, а не только те, которые ещё неиспользованы. Попробуйте внести коррективы — и вы увидите что красота и простота куда-то исчезают и код всё больше начинает описывать не задачу, а её решение. То же произойдёт и при более невинном действии: обобщении на доску NxN. А ведь задача-то просто идеально ложится на парадигму Пролога! А попробуйте написать на Прологе программу, решающую известную головоломку пятнашки и сравните её с версией на C++ — там уже далеко не факт, что решение на Прологе будет визуально изящнее и проще для понимания…

    P.S. Видел в обной книжке по Прологу как сортировку порождали из двух процедур: одна — описывала все перестановки, другая — описывала отсортированные массивы. Несомненно решение работает, но… в учебнике какого ещё языка вы можете обнаружить алгоритм сортировки со сложностью O(N!)??? Вот эта сортировка для меня и осталась символом Пролога: языка, который может быть простым, красивым, изящным… или быстрым и эффективным — но не одновременно!
    • +1
      это просто примеры программирования, на самом деле сравнивать эти языки не корректно. Пролог — язык логики предикатов, да вообще, чтобы правильно на нем программировать нужно изучить довольно много теории по этой теме. И имея простые знания алгоритмов и программирования на обычных языках даёт ложное ощущение неправильности и тд. Почитайте в интеренете статьи о прологе. Я не в коем случае не утверждаю что пролог идеальный вариант, нет конечно, но то что он незаменим для тех кто собирается\программирует системы ИИ это факт. Да и на практике бывает удобен, особенно при интеграции с С++ (например в swi-Prolog это удачно реализовано).
      Насколько я помню из универа прологом прониклись мимнимум студентов. Очень многие кто потом стал удачным программистом(с, java и тд) пролог просто не поняли, и пытались на него перенести стандартную логику программирования.
      • +1
        Логика предикатов — это такая же лженаука как и теория релиционных баз данных. Она существует в каком-то одном мире, Prolog — в каком-то другом. Использовать её можно только в теоретических выкладках, но не в том случае, когда вас интересует результат.

        Хороший пример — вот те самые пятнашки. Если задача ставится как «написать программу, которая возвращает для каждой позиции минимальное число ходов для приведения её к каноническому виду или 'NO' если это невозможно», то вы можете применить логику предикатов и быстро-быстро получить как-бы правильную программу.

        Но когда я говорю об этой задаче я формулирую её иначе: «написать программу, которая вот для этих ста позиций, написанных вот на этом листке бумажки, после запуска её вот на этом компьютере выдаст 100 ответов за имеющиеся у нас 1.5 часа», то теория предикатов немедленно выбрасывается в окно и приходится насиловать уже саму пролог-систему, работа которой сводится к выполнению простого алгоритма.

        P.S. Компьютер о котором идёт речь вполне нормальный — Core 2 Quad, 4GB RAM, etc. Суть в том, что сложные случаи туда всё равно еле-еле влазят (если использовать A*) и нужно
        1. Очень аккуратно использовать имеющиеся у вас ресурсы и понимать что сколько «стоит».
        2. Понимать где можно чуть-чуть «срезать углы» чтобы используя немалую память сократить рассчёты (при другой структуре программы — используя имеющийся у нас быстрый процессор сократить потребление памяти).
        Когда вы используете Пролог сделать это можно только рассматривая Пролог-машину как Пролог-машину, а не как нечто сугубо теоретическое построенное на логике предикатов.
        • +2
          да ладно вас словами бросаться. исчисление предикатов — простая и строгая мат.модель, позволяющая формально ОПИСАТЬ и ИНТЕРПРЕТИРОВАТЬ логику мышления. это формальная модель знаний

          так же как ТРБД — формальная модель данных

          пролог используется так называемые хорновские дизъюнкты и работает методом резолюций.

          этим моделям много лет, и они работают

          просто не надо применять этот инструментарий для сортировки массива и построения GUI
          кесарю — кесарево

          выделяйте задачи ИИ, формализуйте их, скармливайте прологу и используйте решение в программах на других языках
          • +1
            выделяйте задачи ИИ, формализуйте их, скармливайте прологу и используйте решение в программах на других языках
            То есть определение наилучшего хода в игре (а фактически к этому упомянутая мной задача сводится) — это уже не «задача ИИ»? А что тогда «задача ИИ»?
            • 0
              ИИ очень большая область. Вас удивляет что не для всех задач из этой области одинаково хорошо подходит один, очень специализированный, инструмент?
            • 0
              Вы поставили другую задачу: _эффективное_ определение наилучшего хода в игре. По сути дела, если вы захотите решать эту задачу стандартным (не логическим ЯП), вы просто оптимально (с точки зрения упомянутых вами ресурсов) кодируете процесс решения в неком мегаавтокоде, перенося часть runtime интеллекта программы в интеллект стадии проектирования/разработки/компиляции.

              Что касается использования именно Пролога или его неиспользования, то тут сейчас всё дело в привычке, т.к. сейчас элементы его функциональности присутствуют и в других языках программирования, либо такие элементы довольно тривиально и с достаточно небольшой долей boilerplate-кода там реализуются (максимум, через написание препроцессора).
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Логика предикатов и реляционная алгебра — простые и понятные математические инструменты с наработанным аппаратом.
            Если бы они так и оставились математическими инструментами — я был бы счастлив. Скажем машина Тьюринга — простой математический инструмент, который позволяет получить много полезных теоретических результатов, но никто ведь не применяет её всеръёз в практическом программировании! Вот и логика предикатов с реляционной алгеброй относятся к тому же виду…

            Лженаукой теория предикатов и реляционная алгебра становятся когда их пытаются предствить чем-то большим нежели математическую модель… В конце-концов никому и в голову не приходит ввести в компьютере действительные числа «по науке» (вначале ввести натуральные числа, затем целые как пару «знак+удаление от нуля», затем рациональные как пару целых с хитрой операцией равенства, после чего действительные как бесконечный в теории и произвольной длины на практике набор рациональных чисел) — так почему все с упорством, достойным лучшего применения, пытаются сделать системы на основании теории предикатов и/или реляционной алгебры?
            Отрицать значение реляционной алгебры вообще как-то странно, если честно, трудно найти более практичную теорию, породившую целую индустрию приложений, основанных на реляционных СУБД.
            Практичность этой теории просто поражает воображение, она породила даже не одну индустрию, а две:
            1. Описание задачи в терминах реляционной модели.
            2. Приведение того, что наработано в пункте 1 к виду, который хоть как-то можно использовать.
            Честно говоря я бы предпочёл чтобы ни одной из них не было, а был просто инструмент, которым можно пользоваться… или не пользоваться. В конце-концов наличие Дейкстры не обозначает что мы будем пытаться все задачи оптимизации свести к нему!

            И не протестую ни против реляционной алгебры, ни против логики предикатов в математике — это полезные математические модели. Но, к сожалению, их применимость к реальному миру довольно-таки ограничена.
            • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Логика предикатов — это такая же лженаука как и теория релиционных баз данных.

          Как не странно теория реляционных баз данных позволяет создавать эффективные системы хранения и доступа к данным. Может покажете мне то чем вы ее собираетесь заменить и насколько эффективнее ваше решение будет работать?
          Опять же есть старое изречение про то что на любом языке программирования можно написать все что угодно, но трудоемкость в зависимости от языка будет разная. Знание императивной, декларативной и функциональной парадигмы полезно и выбор лучшей парадигмы часто может экономить время.
          • 0
            Как не странно теория реляционных баз данных позволяет создавать эффективные системы хранения и доступа к данным.
            Теория позволяет? Чёрта с два: система, созданная «по теории» работает, как правило, с черепашьей скоростью и требует неуёмных ресурсов.
            Может покажете мне то чем вы ее собираетесь заменить и насколько эффективнее ваше решение будет работать?
            Посмотрите на реальные большие системы (mail.ru, facebook, etc) и справните с идеалом. От красивой теории не остаётся камня на камне к моменту когда это всё, наконец, начинает с удовлетворительной скоростью работать.
            • 0
              Чёрта с два: система, созданная «по теории» работает, как правило, с черепашьей скоростью и требует неуёмных ресурсов.

              Да ну? Может обоснуете? По сравнению с чем они работают медленно? Какие есть универсальные решения которые работают со сравнимой скоростью и требуют существенно меньше ресурсов а?

              Посмотрите на реальные большие системы (mail.ru, facebook, etc) и справните с идеалом.

              Многие большие системы испольузют СУБД тот же Skype и E-bay. К тому же в узкоспециализированной задаче лучше использовать то ПО которое лучше подходит. В случае если данные не могут быть просто уложены в реляционную СУБД и плохо нормализуются, то не надо ее там использовать. Реально же быстрых универсальных систем с отличной от РСУБД идеологией и сравнимым быстродействием и требованиями к ресурсам просто нет. Если вы считаете что есть, то приводите примеры и показывайте чем они лучше. Пока же я вижу выкрики вида:
              — Я сказал это плохо! Это ограничено!
              Но при этом вы забывате, что компьютер сам по себе является ограниченной системой основанный на так вами нелюбимых математических моделях.
              • 0
                Да ну? Может обоснуете? По сравнению с чем они работают медленно?
                По сравнению с тем, что может выдать железо.
                Какие есть универсальные решения которые работают со сравнимой скоростью и требуют существенно меньше ресурсов а?
                А кто вам сказал что такие решения существуют? Первый и самый главный обман этой лженауки: реляционная алгебра «продаётся» как универсальное решение для эффективного хранения и обработки данных. А она таковой не является и, похоже, не может являться. Если за почти 40 лет не удалось сделать эффективной универсальной системы, то, скорее всего, она просто не может быть создана.
                Многие большие системы испольузют СУБД тот же Skype и E-bay.
                Использовать СУБД != использовать теорию реляционных баз данных. Многие из этих систем используют СУБД не как реляционную базу, а как быструю реализацию B+tree и имеют толстую прослойку поверх, собственно, СУБД.
                Реально же быстрых универсальных систем с отличной от РСУБД идеологией и сравнимым быстродействием и требованиями к ресурсам просто нет.
                В вашем высказывании слишком много слов. Вот так:
                Реально же быстрых универсальных систем с отличной от РСУБД идеологией и сравнимым быстродействием и требованиями к ресурсам просто нет.
                будет правильно. А дальше уже можно можно выбирать что вам нужно — медленная и неэффективная униварсальная система (РСУБД) или быстрое, но ограниченное решение (скажем bigtable или S3).

                И то же самое касается Prolog'а и теории предикатов — либо гибкое, но неэффективное универсальное решение (Prolog), либо эффективные, но более ограниченные альтернативы.
                • +1
                  А кто вам сказал что такие решения существуют? Первый и самый главный обман этой лженауки: реляционная алгебра «продаётся» как универсальное решение для эффективного хранения и обработки данных.

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

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

                  Почему это не удалось? РСУБД активно используются. И они эффективны для структурированных данных. Если данные не структурованы или не поддаются структуризации, то необходимо подумать о других системах.

                  Использовать СУБД != использовать теорию реляционных баз данных. Многие из этих систем используют СУБД не как реляционную базу, а как быструю реализацию B+tree и имеют толстую прослойку поверх, собственно, СУБД.

                  Это вы про 1C? :] Вы знаете что такое использование СУБД часто не эффективно?

                  будет правильно. А дальше уже можно можно выбирать что вам нужно — медленная и неэффективная униварсальная система (РСУБД) или быстрое, но ограниченное решение (скажем bigtable или S3).

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

                  Я так понял у вас аргументов кроме это лженаука и это медленно нет? Если да. То считаю, что слив засчитан. Если нет, то будьте добры приведите реальную альтернативу РСУБД которая будет так же удобна в использовании.
                  • 0
                    Если данные укладываются в реляционную схему данных то это действительно так.
                    Мегаглубокая мысля: все задачи, которые реляционный подход хорошо решает — он таки хорошо решает. Фантастика просто.
                    Многие предметные области в нее хорошо укладываются.
                    Вот не замечал я как-то этого на практике. Web-форум? Нужны древовидные структуры. Сбор данных в эксперименте? Нужно работать с данными разных типов (где-то одна камера, а где-то серия). И т.д. и т.п. Даже классика (банковское дело) включает в себя разнородные объекты идущие в одном списке (скажем транзакции по счёту). Я ещё ни разу не видел задачи сколько-нибудь осмысленной сложности, которая бы хорошо легла на реляционную модель. Это всегда сводится к «выкручиванию рук» заказчикам, чтобы это можно было хоть сколько-нибудь эффективно реализовать. Про мозги разработчиков, которые вынуждены придумывать всевозможные извращения для того, чтобы засунуть нетривиальные структуры в прокрстово ложе реляционного подхода я вообще молчу.
                    Это вы про 1C? :] Вы знаете что такое использование СУБД часто не эффективно?
                    1С и Wikipedia и Adwords/Adsense. Насчёт эффективности — всё зависит от того, кто и как пишет систему.

                    bigitable и S3 полезны для хранения нестуктурированных данных по ключу. В случае когда требуется хранить структурированные данные, они будут неуклюжи.
                    Подумайте на досуге — где хранятся данные blogger'а, youtube, gmail'а и прочих систем.
                    • 0
                      Вот не замечал я как-то этого на практике. Web-форум? Нужны древовидные структуры. Сбор данных в эксперименте? Нужно работать с данными разных типов (где-то одна камера, а где-то серия). И т.д. и т.п. Даже классика (банковское дело) включает в себя разнородные объекты идущие в одном списке (скажем транзакции по счёту). Я ещё ни разу не видел задачи сколько-нибудь осмысленной сложности, которая бы хорошо легла на реляционную модель. Это всегда сводится к «выкручиванию рук» заказчикам, чтобы это можно было хоть сколько-нибудь эффективно реализовать. Про мозги разработчиков, которые вынуждены придумывать всевозможные извращения для того, чтобы засунуть нетривиальные структуры в прокрстово ложе реляционного подхода я вообще молчу.

                      Все перечисленное как раз таки поддается нормализации, а реализация скрывается от пользователя приложением. Если к компьютеру так подходить как вы подходите к РСУБД, то знаете ли он тоже штука ограниченная и руки выкручивает, надо писать на каких-то специализированных языках, кодировать слова и все окружающие объекты каким-то дебильным двоичным кодом, что-то компилировать. Если надо я могу продолжить. И знаете от сюда следует, что компьютерные науки это лженаука! Она хороши в виде моделей, но так использовать ну просто никак.

                      Видите какие я замечательные выводы получил на пустом месте? Это называется демогогия.

                      1С и Wikipedia и Adwords/Adsense. Насчёт эффективности — всё зависит от того, кто и как пишет систему.

                      1C кривые руки. У Wikipedia есть большие объемы сырых данных, но на самом деле она работает на РСУБД, хотя в этом случае подход может и не сильно эффективен. Можете скачать MediaWiki и убедиться. Adwords/Adsensce кстати наоборот можно очень неплохо уложить в РСУБД.

                      Подумайте на досуге — где хранятся данные blogger'а, youtube, gmail'а и прочих систем.

                      Подумайте на досуге как они работают с этими данными и почему это именно так. А так же почему много где работают с РСУБД и почему.

                      И так где факты и аргументы что реляционная логика лженаука и использование ее не оправдано?
    • 0
      Вы пожалуй немного утрируете) Точнее то что Вы сказали на счет того что при оптимизации наглядность и декларативность теряются — тут я полностью согласен, и с этим ничего не поделать. Те же отсечения (!) — уже уход от декларативности, меж тем как во многих алгоритмах без этого буквально не обойтись. Но не все так плохо. Я согласен, что вычислительные задачи решать на прологе может и не очень разумно, но, например, символьные преобразования, или, например, написание парсеров, компиляторов, грамматик, etc, может быть очень даже удобно.
      Кстати, задача и так написана для доски NxN, ну почти ) только слегка поменять в 2 местах…
      По поводу сортировки — что то плохая вам книжка попалась )
      Вот например быстрая сортировка:
      sort1([], []) :-!.
      sort1([H | T], Res) :-
        findall(A, (member(A, T), H<A), HMore),
        findall(B, (member(B, T), H>=B), HLess),
        sort1(HMore, HMoreSorted),
        sort1(HLess, HLessSorted),
        append(HLessSorted, [H | HMoreSorted], Res).


      * This source code was highlighted with Source Code Highlighter.

      Работа:

      20 ?- sort1([1,4,2,3,7,5,-7],R).

      R = [-7, 1, 2, 3, 4, 5, 7]
      • +3
        На Прологе можно запрограммировать практически любой алгоритм, как и любую программу на Прологе можно с лёгкостью перевести на любой другой язык программирования. Да это верно для практически любых языков программирования. Все они, в конечном итоге, реализуют одну и ту же машину Тьюринга. Я про другое. Пролог с его логикой предикактов — это самообман. Вам кажется что вы можете забыть о таких «мелких земных вещах» как процессор, память и винчестер, погрузиться в логику предикатов и творить, творить, творить! А на самом деле забывать про них нельзя — и тогда не полезнее ли учитывать все эти проблемы в программе явно? Используя тот же Erlang и Haskell?

        В частности за это я ненавижу C++: в нём закрывающая фигурная скобка может неожиданно оказаться источником бурной деятельности. И я вовсе не уверен что идеома RAII стоит того, чтобы с этим мириться.
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            khim, ты несколько погорячился насчет «явного учета мелких земных вещей» в Erlang и Haskell. Они это тоже неплохо абстрагируют — получить перерасход памяти вполне несложно, а бороться с ним достаточно сложно.
            Как только ты поднимаешься над C — ты начинаешь терять контроль над «мелкими земными вещами». Но в Erlang'е они всё ещё неплохо контролируются, в Heskell'е — похуже, в Prolog'е — это становится настолько сложно, что может перекрыть все выгоды от самого языка. Пресловутое «отсечение» уже очень сильно ломает всю теоретическую базу логики предикатов…
    • 0
      «Каждая вещь необходимо приносит пользу, будучи употребленной на своем месте» ;)
  • 0
    class human
    {
       string Name;

       public human (string _Name)
       {
         Name = _name;
       }
    }

    Запишем условие в терминах языка C# (со знака // начинаются комментарии):<br>

    private human human = new human();
    List<human> humans = new List<human>();

    bool Exists(string Name)
    {
      for (int i = 0; i < humans.Count; i++)
      {
        if(humans[i].name.Equals(Name))
        {
          return true;
         }
      }
    }

    // Сократ - человек
    humans.Add(new human("sokrat"))
    // Платон - тоже человек
    humans.Add(new human("platon"))
    // Чтобы некто был смертным, он должен быть человеком

    теперь спросим C# систему, смертен ли Сократ:<br>

    bool isMortal = Exists("sokrat")
    True // да

    isMortal = Exists("stranger");
    False // нет, поскольку C# система не знает ничего о stranger и потому, не может ответить на вопрос

    // Мы можем спросить какие смертные существа известны системе:<br>

    for (int i = 0; i < humans.Count; i++)
    {
      string who = humans[i].name; //не совсем видимо правильно вас понял...
    }



    * This source code was highlighted with Source Code Highlighter.
    • 0
      Как понимаю, пост шуточный )
      Несколько замечаний:
      1) Классы, насколько помню в C# именуются с большой буквы
      2) метод Exists у Вас нигде не возвращает false -> вероятно, не скомпилится
      3) лучше использовать properties, а не непосредственный доступ к полям класса (инкапсуляция, однако=) )

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

      П.С. Вообще-то предполагалась к решению задачка о ферзях )
      • +1
        да шуточный… :)))
      • +1
        1 — хоть с русской «ы»
        2 — да, но там и без этого косяки
        3 — для примера и так нормально =)

        а по поводу статьи — все таки без знания синтаксиса пролога и без понимания как оно работает «внутре» сложно понимать приведенные примеры
        • 0
          Кстати, для тех кто, как я не поняли пример с ферзями, тут вроде рассмотрено подробнее: isr.by.ru/prolog/ch4_5.htm
      • 0
        Вот о ферзях на Питоне. Программу давно когда-то написал, уже не помню, что она делает и как, а каментов нет :)
        dpaste.com/101445/
    • 0
      var Human= function( name ){ this.name= name }; // класс людей
      Human.prototype.mortal= true; // по умолчанию — все люди смертны

      var Socrat= new Human( 'Сократ' ); // сократ — человек
      var Platon= new Human( 'Платон' ); // платон — человек
      Platon.mortal= false; // но он периодически бэкапится в клонов
      • 0
        тогда напишите плз аналог вот такого, интересно будет сравнить:

        % люди
        human(platon).
        human(sokrat).

        % собаки
        dog(tuzik).
        dog(sharik).

        % кошки
        cat(tom).

        % мыши
        mouse(jerry).

        % животное это либо кошка либо собака, либо мышь
        animal(X) :-
          dog(X);
          cat(X);
          mouse(X).

        % возрасты наших living creatures
        age(platon, 80).
        age(sokrat, 70).
        age(tuzik, 10).
        age(sharik, 7).
        age(tom, 5).
        age(jerry, 3).

        % смертный -> либо человек, либо животное.
        mortal(Someone) :-
          human(Someone);
          animal(Someone).

        * This source code was highlighted with Source Code Highlighter.


        И запросы:
        % смертные
        ?- mortal(Who).

        Who = platon;

        Who = sokrat;

        Who = tuzik;

        Who = sharik;

        Who = tom;

        Who = jerry

        % смертные люди
        ?- mortal(Who), human(Who).

        Who = platon;

        Who = sokrat;

        No

        % смертные животные не старше 5 лет
        ?- mortal(Who), animal(Who), age(Who, Age), Age=<5.

        Who = tom,
        Age = 5;

        Who = jerry,
        Age = 3
        • +2
          var animals= new DB(
          { mortal: DB.Index.Boolean({$: this.mortal }) // все животные делятся на смертных и бессмертных
          , mortalHuman: DB.Index.Boolean{$: this.mortal && this.human } // все животные делятся на смертных людей и остальных
          , mortalAnimalByAge: DB.Index.Number({$: this.mortal && this.animal && this.human && this.age }) // сортируем смертных животных по возрастам
          });

          // определения классов, как в прошлом случае

          var Platon= animals.add( Human().$set({ age: 11 }) );
          var Tom= animals.add( Cat().$set({ age: 3 }) );

          alert( animals.select.mortal( false ) ); // бессмертные животные
          alert( animals.select.mortalHuman( true ) ); // смертные человеки
          alert( animals.select.mortalAnimalByAge( 5, '
  • 0
    % Чтобы некто был смертным, он должен быть человеком

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

    % Кстати, а как это будет выглядеть на вашем любимом языке программирования? =)

    а насколько медленно это будет работать на прологе? и/или насколько больше памяти она будет кушать? чисто декларативные языки нежизнеспособны в условиях ограниченных ресурсов.
    • +1
      На самом деле ошибки нету. В том плане, что, да, формально
      «Все люди смертны» и «чтобы некто был смертным он должен быть человеком» не одно и то же, но в рамках замкнутой системы знаний, в которой лежит лишь 2 факта о том что платон и сократ — люди, этого достаточно чтоб сделать правильный вывод.
      «Людям проще» — не факт, и не всегда, есть задачи где не проще, просто они об этом не знают (почитайте Пола Грэма про парадокс языка програмирования Блаб)
      «На сколько медленно» — в настоящее время скорость разработки программы (или прототипа) часто куда важнее скорости работы программы.
      • 0
        что ты будешь делать, когда систему знаний потребуется расширить? проведёшь ревизию всего кода?

        скорость разработки важнее незначительной разницы в скорости.
        • 0
        • 0
          по поводу скорости — да ладно…
          программы на питоне в среднем могут на порядок быть медленнее C, и используют же. А Java раза в 3-4 может быть медленнее, и при этом она популярнее чем C!
          К тому же, мы же не говорим о 100% pure prolog решении, это действительно нецелесообразно. Обычно это часть сложной логики, но при этом не критичная к скорости, имхо.
          • +2
            накладные расходы на виртуализацию — это ничто по сравнению с потерями от неверно выбранного алгоритма.
      • 0
        «Другая особенность нашего софта заключалась в том, что он был написан на языке программирования Lisp. Viaweb вначале состоял из двух частей: редактора, написанного на Lisp'е, который использовался для построения сайтов, и системы обработки заказов, написанной на C. Большую часть первой версии составлял Lisp, так как система обработки заказов была маленькая. Позже мы добавили еще два модуля, генератор изображений на C, и программу для администрирования, написанную большей частью на *Perl'е*»

        лисп — весь из себя «мощный», а сделать программу администрирования оказалось проще и быстрее на каком-то перле.
        • 0
          вообще говоря, лисп ничем не мощнее ассемблера. самомодификация, макросы и пр вполне умеет и ассм. разница лишь в том, что ассм использует абстракции реальной тьюринговой машины, а лисп — виртуальной списочной. но оба далеки от современных языков высокого уровня, где доступны абстракции предметной области.
        • 0
          Большим молотком сложно попасть по маленькой мухе)
  • +1
    Могу подсказать ещё один похожий язык.

    Мы задаём только набор характеристик объектов, которые нам нужны, и не задаём способ их хранения, поиска и т. д.

    Это — SQL. Хотя это и не язык программирования ;)
    • 0
      > SQL. Хотя это и не язык программирования.

      Позвольте поинтересоваться, почему это SQL-ю отказано в праве быть ЯП?
      • –1
        Потому что это я зык запросов :) Как, например, HTML/XML языки разметок
  • 0
    Круто. Почему-то напомнило две вещи:
    — определения типов в Хаскеле
    — тройки RDF (с помощью них тоже можно из фактов получать другие факты)

    * ушел учить Пролог.
  • 0
    Мы на прологе в универе компилятор писали — прикольное занятие :)
    • +1
      А мы экспертную систему! А компиляторы — на паскале.
      • 0
        а мы экспертную систему. А однопроходный компилятор Паскаля на Си
  • +1
    Так как в erlang'е я пока не силён то переведу-ка я алгоритм на scheme:

    (define (getsolution n)
      (solution n (do ((i n (- i 1)) (ls '() (cons `(,i . X) ls))) ((= i 0) ls))))

    (define (solution n start)
      (if (null? start)
        '(())
        (do ((sl (solution n (cdr start)) (cdr sl))
             (ls '() (do ((i n (- i 1))
                          (ls ls
                              (if (nokill `(,(caar start) . ,i) (car sl))
                                (cons (cons `(,(caar start) . ,i) (car sl)) ls)
                                ls)))
                         ((= i 0) ls))))
            ((null? sl) ls))))

    (define (nokill a b)
      (let ((x (car a)) (y (cdr a)))
        (if (null? b)
          #t
          (let ((x1 (caar b)) (y1 (cdar b)))
            (cond
              ((= y y1) #f)
              ((= (- y1 y) (- x1 x)) #f)
              ((= (- y1 y) (- x x1)) #f)
              (else (nokill a (cdr b))))))))

    По-моему вполне понятно, хотя, конечно, и сложнее версии на Прологе…
    • +2
      По всей видимости, Scheme — язык смайлов.
      Где ещё в листинге программы увидишь столько скобок ((=

      Надо будет изучить поближе.
      • +3
        «Где ещё в листинге программы увидишь столько скобок „

        В лиспе
        • +3
          Scheme — диалект Lisp.
      • 0
        Много скобок будет в любом lisp-подобном языке. А программа такая длинная получилась потому что я буквально перевёл её на scheme. Если бы я писал сразу на scheme, то было бы что-нибудь подобное:

        (define (solution min max unfilled l)
          (if (= unfilled 0)
            (begin
              (let p ((n 1) (l l))
                (write n) (write-char #\/) (write (car l))
                (if (not (null? (cdr l))) (begin (write-char #\ ) (p (+ n 1) (cdr l)))))
              (newline))
            (if (<= min max)
              (begin
                (if (nokill min 1 l) (solution 1 max (- unfilled 1) (cons min l)))
                (solution (+ min 1) max unfilled l)))))

        (define (nokill a d l) (cond ((null? l) #t)
                                     ((= a (car l)) #f)
                                     ((= (- a (car l)) d) #f)
                                     ((= (- (car l) a) d) #f)
                                     (else (nokill a (+ d 1) (cdr l)))))

        (solution 1 8 8 '())

        Половина программы посвящена красивому выводу результата — это не самое сильное место scheme…
        • 0
          Очень познавательно, спасибо.
          Я и сам программист с большим опытом работы, но столкнуться с lisp-подобными языками в работе не довелось.

          Для расширения кругозора почитаю что это за зверь такой — Scheme, возможно даже сумею разобраться в вашем листинге :)
          Для повседневной работы мне хватает Python, Java и JavaScript (каждый для своей ниши).
          А какую реальную нишу занимает Scheme? Или вы его используете как хобби?
          • 0
            А какую реальную нишу занимает Scheme? Или вы его используете как хобби?
            Генерация кода (autogen) и обработка XML (SXML) в основном. В принципе для этого можно использовать и Python, но так получилось что я сначала встретил Scheme, а потом уже Python.
  • 0
    Спасибо за статью!
    Всколыхнуло.
    И порадовало — "* This source code was highlighted with Source Code Highlighter".
    Не знает Пролог?
    • 0
      да, не знает) применил чисто для правильного формирования отступов )
      • +2
        Можно поменять надпись на:

        * This source code was not highlighted with Source Code Highlighter
  • +2
    Спасибо за статью! Очень жаль, что предложений работы на прологе очень мало.

    Очень сильно извиняюсь, что придираюсь, но очень долго меня мучат смутные сомненья по поводу первой фразы, «Язык пролог незаслуженно обладает довольно узкой известностью».
  • 0
    У меня в университете преподают turbo prolog в рамках расширения кругозора, по началу всю голову сломал с ним, а когда разберёшься очень уж интересно. особенно интересно там получаются рекурсии.

    rec(A):-a<>5,write(a),nl,Z=A+1,rec(Z),fail.
    • 0
      А что в этой рекурсии интересного?
    • 0
      turbo prolog — это симбиоз пролога и очень хорошо знакомого ребятам из борланда паскаля, работал он быстро, конечно, но на настоящий пролог был мало похож. Потому и популярности не снискал — ни то, ни се.
  • +7
    Ферзи на python:

    def noKill(x, y):
        return x[0] != y[0] and x[1] != y[1] and (x[0] - x[1] != y[0] - y[1]) and (x[1] - x[0] != y[0] - y[1])
    
    def dfs(x):
        if 8 == len(x):
            print x
        else:
            for y in xrange(8):
                nw = (len(x), y)
                if all(map(lambda ix: noKill(ix, nw), x)):
                    x.append(nw)
                    dfs(x)
                    x.pop()
    
    dfs([])
    
    • +1
      Python — язык придуманный программистами, для программистов.
      Лично меня он подкупил возможностью писать сложные вещи просто (изящно), так как и ваш листинг.
    • 0
      если верно x[0] - x[1] != y[0] - y[1], то верно и x[1] - x[0] != y[0] - y[1] и можно одно убрать :)

      • 0
        упс, фигню сказал… виноват, невнимателен!
  • 0
    > Язык пролог незаслуженно обладает довольно узкой известностью

    Ну прям уж такой узкой :) Любой студент ИИВТ изучает Пролог в обязательном порядке. Я даже экспертную систему на нём делал.

    Всем: foxweb.net.ru/files/?cat=9 — тут я собрал готовые задачи в рамках специальности «Программное обеспечение вычислительной техники и автоматизированных систем».
  • 0
    Пришлось изучать Пролог в рамках дисциплины «Интеллектуальные системы».
    Мне, честно говоря, он крайне по понравился.
    Все задачи, поставленные передо мной, я бы решил в разы быстрее на привычном мне языки, будь то c, php и аналоги.
    Если кого-нибудь интересует, то могу предоставить примеры задач на обычные логические высказывания, рекурсию и работу со списками.
  • +1
    Хаха, как раз сдавали зачет на прошлой неделе по Прологу. Есть и тема курсовой — написать Базу Знаний с удобным интерфейсом управления, плюс всё это загрузку из файла и обратно.

    Если честно, в начала изучения подумал что он просто как разновидность других языков. Но только углубившись можно понять, что это совершенно другая модель, другой подход и другая логика.
  • –1
    Иэх, как раз вчера получил зачёт по Прологу в институте :)
  • +3
    Короче, как показывают комментарии, пролог очень хорошо известен всем, но пишут на нем только курсовые :)
    • –1
      Тут просто не очень много разработчиков систем ИИ. А если присмотреться к _объемным_ комментам выше то можно понять что и разработчиков моделей не очень много.
  • 0
    ?- mortal(stranger).

    No % нет, поскольку пролог система не знает ничего о stranger и потому, не может ответить на вопрос


    Прошу прощения, что задаю возможно идиотский вопрос, но откуда оно знает что если не истина то ложь? Это некий базисный предикат или что? Ну я имею в виду что откуда система знает что если есть правило А и оно не выполняется, то результат будет выбран по умолчанию из оставшегося. А если ответ формулируется как тернарное отношение например? Или те же «да», «нет», «не знаю».

    С моей точки зрения ответ на вопрос о Страннике — как раз «не знаю», ибо нет явной возможности доказать или опровергнуть, что Станник смертен.

    Опять же, возможно, существуют еще некие отношения, пока не известные системе которые говорят, например, что странником был Сократ. А мы уже дали однозначный ответ…
    • 0
      ещё можно вспомнить про парадокс лжеца ;-)
    • +2
      С моей точки зрения ответ на вопрос о Страннике — как раз «не знаю», ибо нет явной возможности доказать или опровергнуть, что Станник смертен.
      С вашей точки зрения — да. А с точки зрения Пролога — нет. Ибо предполагаются что в программе записаны все знания и никаких других знаний нет. Можно туда добавить и вариант «не знаю» и оформить всё хозяйство с использованием нечёткой логики, но это всё офомляется как надстройка над обычной бинарной логикой.
      • 0
        А с точки зрения Пролога — нет. Ибо предполагается, что в программе записаны все знания и никаких других знаний нет.


        Ага, понятно. Спасибо.
      • 0
        Поставил swi немного поигрался. Будет с чем поиграться в рождественские праздники.

        По поводу true/false. swi пишет fail вместо false. Т.е. он не утверждает, что «ложь», он просто говорит, что не смог доказать, что «истина».
    • +1
      это тонкий вопрос, он довольно обстоятельно рассматривается в рекомендуемой книжке И. Братко.
  • 0
    А нам его в этом семестре давали, неплохая прочистка мозга от засилия императивных языков :)
  • 0
    О! Мило! Спасибо автору, хоть и с «запозданием» лично для меня =))) ибо как раз где то неделю две назад заинтересовался данным языком =)

    ЗЫ Треубем ЛИСПа и другой «экзотики» =))
  • 0
    Джина из бутылки выпустили.
    Да, я не ошибся. комментарий именно в тему Пролога.
  • 0
    Нахлынули воспоминания…

    В институте на прологе решал задачу про «грабителя и полицейских» и писал пролог на прологе.
    Было забавно. Дома развлекался тем, что написал программку, которая «немного» могла разговаривать.
    (т.е. обрабатывать очень простые английские вопросы и отвечать на них).
    Пытался даже устроиться работать на прологе (в Питере была такая контора 3 года назад, сейчас не знаю).
  • 0
    Что касается применения пролога и его быстродействия…

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

    Пролог также хорош для академических исследований. Я на эстонской школе по computer science слушал доклад PhD из
    Испании, который рассказывал как очень просто написать компилятор компиляторов на прологе и на основе его сделать,
    к примеру, компилятор java. При этом использовался похожий на этот подход.
  • 0
    В своё время программировал на прологе. Начинал с задачи по определению родственных связей в библии. Кто кому дед, кто кому сын и т.д. Потом дошли до экспертных систем. Было интересно. Хороший опыт
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Изучил в прошлом году. Интересный язык. Существуют даже IDE для разработки на нём программ, честно говоря, сложно представить как это выглядит :)

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