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


      У того, кто в детстве не писал на Прологе — нет сердца, а у того, кто пишет на нём сегодня — нет мозгов. (оригинал)

      Если вас всегда терзали мучительные сомнения — что за фигня это Логическое Программирование (ЛП) и вообще зачем оно нужно? То это статья для вас.


      Можно по-разному разделить языки программирования на группы (часто их называют парадигмами программирования), например, вот так:


      • структурное: программа разбивается на блоки — подпрограммы (изолированные друг от друга), а основными элементами управления являются последовательность команд, ветвление и цикл.
      • объектно-ориентированное: задача моделируется в виде объектов, которые отправляют друг другу сообщения. Объекты обладают свойствами и методами. Абстракция. Инкапсуляция. Полиморфизм. Ну в общем, все в курсе.
      • функциональное: базовым элементом является функция и сама задача моделируется в виде функции, а, точнее, чаще всего в виде их композиции, если f(.) и g(.) — это функции, то f(g(.)) — это их композиция.
      • логическое: вот тут, как правило, начинается феерия — если про первые три написаны сотни статей, книг, обзоров, презентаций и учебников, то здесь мы в лучшем случае видим что-то про Prolog и разработки времён Pink Floyd и Procol Harum (ну хоть с музыкой им тогда повезло) и на этом история заканчивается.

      Вот эту оплошность я и собираюсь сегодня исправить.


      Важнейший тезис этой статьи:


      Логическое программирование != Prolog.

      И вообще последний вам скорее всего не нужен. А вот первое вполне может быть.


      Структура статьи:


      • Что такое Пролог и почему он вам скорее всего не нужен
      • Зачем оно надо, или краткое введение в Answer Set Programming
      • Решаем задачи на ASP
      • Комбинаторная оптимизация
      • Вероятностное ЛП: ProbLog
      • ЛП на классической логике FO(.) и IDP
      • Sketched Answer Set Programming
      • Экспериментальный анализ
      • Тестирование и корректность программ
      • Заключение
      Читать дальше →
    • Диагностическая медицинская экспертная система на Prolog

      Вступление


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

      Использовалась реализация Prolog — Visual Prolog, с встроенными библиотеками GUI. Но если
      вы хотите написать GUI на Qt/C++, то в документации есть инструкция, как импортировать программу в DLL, и скомпилировать ее вместе с C/C++ проектом. Отсюда следует, что совместить можно и с другими языками.

      Вообще когда я работал над этим проектом, я не нашел примеров достаточно не примитивных, но в то же время и не настолько больших, как наворочен
      Читать дальше →
    • Используем Пролог

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


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


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


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


        Так вот, задача такова:


        1. Trapping Rain Water II
          Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
          Note:
          Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
          Example:

          image

          Given the following 3x6 height map:
          [
          [1,4,3,1,3,2],
          [3,2,1,3,2,4],
          [2,3,3,2,3,1]
          ]
          Return 4.


        Читать дальше →
      • Ищем убийцу на Прологе

        • Перевод
        Каждое воскресенье в нашей компании принято устраивать весёлые викторины, это одна из них.

        Загадка


        Чтобы найти убийцу мистера Бодди, нужно узнать, где находился каждый человек и какое оружие было в комнате. Подсказки разбросаны по всей викторине (вы не можете ответить на первый вопрос, пока не прочитаете все десять).

        • Для начала, представим подозреваемых. Есть три мужчины (Джордж, Джон, Роберт) и три женщины (Барбара, Кристина, Иоланда). Каждый человек находится в отдельной комнате (ванная, столовая, кухня, гостиная, кладовая, кабинет). В каждой комнате найдено подозрительное оружие (сумка, огнестрельное оружие, газ, нож, яд, верёвка). Вопрос: кого нашли на кухне?
        • Подсказка 1. При мужчине на кухне нет ни верёвки, ни ножа, ни сумки. Оружие не является огнестрельным. Вопрос: какое оружие найдено на кухне?
        Читать дальше →
        • +30
        • 7,3k
        • 9
      • Декларативное мышление

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


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


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


          Что же, введение затянулось....

          Читать дальше →
        • Разминки с Прологом

            Путешественники, привет.


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


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


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


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


            Хватит вызывать заинтересованность, начинаю...

            Читать дальше →
            • +16
            • 3,1k
            • 4
          • Занимательный пролог #3

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


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


              Я написал реализацию которая в среднем была вот такого вида скорости, значит есть еще 90 процентов решений, которых я не заметил, что кто-то знает как ее решить еще быстрее и он молчит, и посмотрев две предыдущие статьи не сказал: ах, если это вопрос производительности, тогда все понятно — тут пролог не подходит. Но с производительностью сейчас все нормально, представить себе программу, которая будет запущена на слабом железе не возможно, "в конце концов, зачем об этом думать?"


              Вызов


              Решить задачу еще быстрее, там был питон и было время, и есть на питоне более быстрое решение?



              Мне сообщают "Runtime: 2504 ms, faster than 1.55% of Python3 online submissions for Wildcard Matching."

              Читать дальше →
            • Занимательный пролог #2

                Привет, сообщество разработчиков, надо довести дело до конца.


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


                Попробую продолжить выпендриваться демонстрировать.


                Коротко напомню задачу:


                Wildcard Matching

                Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and ''.
                '?' Matches any single character.
                '
                ' Matches any sequence of characters (including the empty sequence).
                The matching should cover the entire input string (not partial).


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


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


                Зачем было делать так много тестов, хочу проверить дальше...


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


                Итак, выбираю Питон.

                Читать дальше →
              • Занимательный пролог

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


                Но грустнее дело обстоит с логическим, продукционным программированием, которое можно представить только на Prolog.


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


                Итого цель статьи: решить во время написания статьи задачу, которая была еще не известна на начало поста и показать свой код мысли, подтвердив это ходом и полученным рабочим решением. Но для этой проверки нужен арбитр, сам себя не рецензируешь-то. Выберу в этой роли leetcode.com.


                1. Итак


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


                2. Задача 44. Wildcard Matching

                Читать дальше →
              • Автоматическое порождение программ, обратная задача и некоторые связанные с ними решения

                  Здравствуйте, уважаемые читатели. В этой статье речь пойдет об одном подходе к автоматическому порождению программ по блочной модели задачи, к решению обратной задачи (восстановления модели исходной проблемы по уже порожденной программе), а также к решению проблемы верификации порожденных программ. Сама по себе тема очень серьезная, но статью я, по возможности, постараюсь сделать популярной (без тяжеловесного обзора аналогов, строго оформленной теоретической части и прочих сложностей), с примерами и описанием различных применений.
                  Читать дальше →
                  • +10
                  • 2,4k
                  • 9

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