Занимательный пролог

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


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


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


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


1. Итак


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


2. Задача 44. 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).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like? or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
Input:
s = "aa"
p = '*'
Output: true

Explanation: '*' matches any sequence.

Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:
Input:
s = "adceb"
p = "*a *b"

Output: true
Explanation: The first "star" matches the empty sequence, while the second * matches the substring "dce".

Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false

3. Вот это ход


Вот это да ))) (модераторы извините), выпала задача в которой необходимо реализовать предикат. Чудеса, не придется даже делать никакого ввода/вывода, который может быть затруднителен в такой среде. На входе простые типы, на выходе булево. Элементарно.


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


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


atom_to_list('',[]). %-для пустой строки и список пустой
atom_to_list(Str,[H|T]) :- atom_concat(Ch,Rest,Str),atom_lenght(Ch,1),atom_to_list(Rest,T). %-первый символ голова, а список из остатка строки это его хвост

Простите за мой английский, проверим это в наилучшей на сейчас среде swi-prolog.org, там есть онлайн редактор, вот:
image
Уппс. Вот что значит никого не обманывать, это высокий порог входа, обращения к библиотечным предикатам не правильные. Ищем правильные встроенные предикаты для работы с атомами.
И на картинке сообщение, что переменная H оказалась невостребована, какой-то недостаток в логике, голова списка это первый символ, а на ее месте должна быть Ch.


Вот немного документации:


atom_concat(?Atom1, ?Atom2, ?Atom3)
Atom3 forms the concatenation of Atom1 and Atom2. At least two of the arguments must be instantiated to atoms. This predicate also allows for the mode (-,-,+), non-deterministically splitting > the 3rd argument into two parts (as append/3 does for lists). SWI-Prolog allows for atomic arguments. Portable code must use atomic_concat/3 if non-atom arguments are involved.

atom_length(+Atom, -Length)
True if Atom is an atom of Length characters. The SWI-Prolog version accepts all atomic types, as well as code-lists and character-lists. New code should avoid this feature and use write_length/3 to > get the number of characters that would be written if the argument was handed to write_term/3.

3.1 Атом в список атомов


Вот так


3.2 Собственно конечный автомат


Вообразим себе такой граф, который читает символы из шаблона и проверяет на соответствие символам во входной строке. Черновик решения:


%InpitList, PattList
test_pattrn([],[]). %- все хорошо когда оба пустые
test_pattrn([Ch|UnpTail],[Ch|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail).
%'?' Matches any single character.
test_pattrn([Ch|UnpTail],['?'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail).
%'*' Matches any sequence of characters (including the empty sequence).
test_pattrn([Ch|UnpTail],['*'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]).
test_pattrn([],['*'|PatTail]):-test_pattrn([],PatTail).

Сделаем итоговый интерфейс:
isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!,test_pattrn(SL,PL),!.


Вот все примеры из постановки задачи:



4. Арбитр


Вроде решение готово, теперь включаем арбитра. На сайте leetcode.com (да, да, мы решаем задачу номер 44), будет получать тесты, попробуем их последовательно выполнить нашей реализацией. Одна незадача, там не принимают программы на Prolog.


Ничего, по одному получим все задания:


class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if s=="aa" and p=="a":return False  
        if s=="aa" and p=="*":return True
        if s=="cb" and p=="?a":return False
        if s=="adceb"and p=="*a*b":return True
        if s=="acdcb" and p=="a*c?b":return False
        if s=="aab" and p=="c*a*b":return False
        if s=="mississippi" and p=="m??*ss*?i*pi":return False
        if s=="aa" and p=="aa":return True 
        if s=="aaa" and p=="aa":return False
        if s=="aa" and p=="a*":return True
        if s=="ab" and p=="?*":return True
        if s=="a" and p=="a":return True
        if s=="a" and p=="aa":return False
        if s=="aa" and p=="aaa":return False
        if s=="abefcdgiescdfimde" and p=="ab*cd?i*de":return True
        if s=="zacabz" and p=="*a?b*":return False
        if s=="leetcode" and p=="*e*t?d*":return False
        if s=="missingtest" and p=="mi*ing?s*t":return False
        if s=="aaaa" and p=="***a":return True
        if s=="" and p=="":return True
        if s=="" and p=="*":return True
        if s=="" and p=="a":return False
        if s=="" and p=="?":return False
        if s=="a" and p=="":return False
        if s=="a" and p=="a*":return True
        if s=="a" and p=="?*":return True
        if s=="a" and p=="*":return True
        if s=="b" and p=="?":return True
        if s=="b" and p=="??":return False
        if s=="bc" and p=="??":return True
        if s=="bcd" and p=="??":return False
        if s=="b" and p=="?*?":return False
        if s=="b" and p=="*?*?":return False
        if s=="b" and p=="*?*?*":return False
        if s=="c" and p=="*?*":return True
        if s=="cd" and p=="*?":return False
        if s=="cd" and p=="?":return False
        if s=="de" and p=="??":return True
        if s=="fg" and p=="???":return False
        if s=="hi" and p=="*?":return True
        if s=="ab" and p=="*a":return False
        if s=="aa" and p=="*a":return True
        if s=="cab" and p=="*ab":return True
        if s=="ab" and p=="*ab":return True
        if s=="ac" and p=="*ab":return False
        if s=="abc" and p=="*ab":return False
        if s=="cabab" and p=="ab*":return True
        if s=="cabab" and p=="*ab":return True
        if s=="ab" and p=="ab":return True
        if s=="ab" and p=="*?*?*":return True
        if s=="ac" and p=="ab":return False
        if s=="a" and p=="ab":return False
        if s=="abc" and p=="ab":return False
        if s=="" and p=="ab*":return False
        if s=="a" and p=="ab*":return False
        if s=="ab" and p=="ab*":return True
        if s=="ac" and p=="ab*":return False
        if s=="abc" and p=="ab*":return True
        if s=="" and p=="*a*":return False
        if s=="a" and p=="*a*":return True
        if s=="b" and p=="*a*":return True

Вот это список тестов, кто-то хорошо постарался введя к этой задачке такой чек-лист.


И это не все тесты, пока остановимся:



Вот готовая программа, плюс немного тестов:


%-для пустой строки и список пустой
atom_to_list('',[]).
%-первый символ голова, а список из остатка строки это его хвост
atom_to_list(Str,[Ch|T]) :- 
    atom_concat(Ch,Rest,Str),atom_length(Ch,1),
    atom_to_list(Rest,T). 

is_letter(X):-X@>=a, X@=<z.

%InpitList, PattList
test_pattrn([],[]). %- все хорошо когда оба пустые
test_pattrn([Ch|UnpTail],[Ch|PatTail]):-
    is_letter(Ch),test_pattrn(UnpTail,PatTail).
%'?' Matches any single character.
test_pattrn([Ch|UnpTail],['?'|PatTail]):-
    is_letter(Ch),test_pattrn(UnpTail,PatTail).
%'*' Matches any sequence of characters (including the empty sequence).
test_pattrn([Ch|UnpTail],['*'|PatTail]):-
    is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]).
test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail).

isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!,
    test_pattrn(SL,PL),!.

%unit-tests framework
assert_are_equal(Goal, false):-not(Goal),!,writeln(Goal->ok).
assert_are_equal(Goal, true):-Goal,!,writeln(Goal->ok).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).

%main goal
:-assert_are_equal(isMatch(aa,a),false).
:-assert_are_equal(isMatch(aa,'*'),true).
:-assert_are_equal(isMatch(cb,'?a'),false).
:-assert_are_equal(isMatch(adceb,'*a*b'),true).
:-assert_are_equal(isMatch(acdcb,'a*c?b'),false).
:-assert_are_equal(isMatch(aab,'c*a*b'),false).
:-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false).
:-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true).
:-assert_are_equal(isMatch(zacabz,'*a?b*'),false).
:-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false).
:-assert_are_equal(isMatch(aaaa,'***a'),true).
:-assert_are_equal(isMatch(b,'*?*?*'),false).

Вот результаты испытаний:


isMatch(aa, *)->ok
isMatch(cb, ?a)->ok
isMatch(adceb, *a*b)->ok
isMatch(acdcb, a*c?b)->ok
isMatch(aab, c*a*b)->ok
isMatch(mississippi, m??*ss*?i*pi)->ok
isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok
isMatch(zacabz, *a?b*)->ok
isMatch(leetcode, *e*t?d*)->ok
isMatch(aaaa, ***a)->ok
isMatch(b, *?*?*)->ok
true

5. Заключение


Prolog как разминка для ума. Забавно на нем решать задачи, хоть данное решение и не обладало никакой оптимизацией. Добраться вручную до более сложных тестов, оказалось очень трудоемко, доказать полноту решения пока не удалось. А до размера хабр-статьи мне кажется я уже добрался.


На каком примере это решение провалиться?


Как вам мой вызов, жители Хабра?


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

Поделиться публикацией

Похожие публикации

Комментарии 25
    0
    Немного занимался Прологом. Не зацепило, а жаль. Штука интересная.
      0
      Подозреваю, что будут проваливаться паттерны вида a*b*c*d на строках вида aabbccbbccdd
      +2
      Очень рад, что кто-то напомнил, что есть такой замечательный язык Пролог… Сам-то я периодически пишу на нем — когда не очень понимаю задачу :).
      Что касается вашей задачи — вот текст для swi-prolog
      run(X,Y):-
        atom_chars(X,XX),
        atom_chars(Y,YY),
        !,match(XX,YY).
        
      match([],[ * ]).
      match([],[]).
      match([H|T],[A|P]) :-
       (A = ? ; A = H), match(T,P).
      match([H|T],[ * | P]):- match(T,[ * |P]); match(T,P).

      Ну здесь run просто драйвер. Надеюсь, что правильно понял исходную задачу…
        0
        Спасибо, протестировал,
        на такой реализации получаем одну ошибку
        isMatch(aa, a)->ok
        isMatch(aa, *)->ok
        isMatch(cb, ?a)->ok
        isMatch(adceb, *a*b)->failed:expected-true
        isMatch(acdcb, a*c?b)->ok
        isMatch(aab, c*a*b)->ok
        isMatch(mississippi, m??*ss*?i*pi)->ok
        isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok
        isMatch(zacabz, *a?b*)->ok
        isMatch(leetcode, *e*t?d*)->ok
        isMatch(aaaa, ***a)->ok
        isMatch(b, *?*?*)->ok
        isMatch(aabbccbbccdd, a*b*c*d)->ok
        true


          0
          Точно! у меня пропущен еще один вариант проверки:
          match([H|T],[ * | P]):- match(T,[ * |P]);match([H|T],P); match(T,P).
        0
        isMatch(leetcode, *e*t?d*)->ok
          0
          по-моему тут ошибка, между t и d два символа
            0
            выше я привел код предиката match — он дает false на вашем примере — это действительно так. К сожалению, у автора немного не верный предикат…
              0
              Тут надо смотреть тест, в нем проверка на false
              :-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false).
              А сообщение о правильном прохождении.
                0
                Да, не посмотрел… Тогда, по уму, надо делать так, чтобы выводило isNotMatch(...)->ok для таких случаев.
                  0
                  Ну, это был намек на unit testing ),
                  функции типа Assert.AreEqual(expected, actual)
                  тест зеленый — ok, иначе выведет сообщение…
            –1
            Не считаю, что декларативность это противоположность императивности. Это альтернативные подходы. И основная проблема в том, что декларативность сперва должна быть запрограммирована императивностью.

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

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

                Именно про это я говорил, когда имел ввиду «все нюансы».
              0
              Даже в вашем маленьком примере видно, что чисто декларативный подход не работает в реальном мире.
              Вот этот «предикат»:
              isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!,
                  test_pattrn(SL,PL),!.

              На самом деле является эмуляцией императивного программирования на декларативном языке программирования.
                0

                Предикаты нужно воспринимать так:
                строка соответствует шаблону если строку можно превратить в список атомов и шаблон можно превратить в список атомов и список из строки соответствует правилу соответствия шаблону

                  0
                  В декларативном подходе порядок выполнения условий неважен, попробуйте поменять порядок выполнения условий в этом «предикате».
                    0

                    Тут речь не про порядок, а коммутативность операции И.
                    Ответить могу цитатой из известной книги Братко И.:


                    Но, к сожалению,
                    декларативный подход не всегда позволяет решить все задачи. По мере дальнейшего
                    изучения материала этой книги станет очевидно, что процедурные аспекты не могут
                    полностью игнорироваться программистом по практическим причинам, связанным с
                    обеспечением вычислительной эффективности, особенно при разработке больших
                    программ. Тем не менее необходимо стимулировать декларативный стиль мышления
                    при разработке программ Prolog и игнорировать процедурные аспекты до такой степени,
                    которая является допустимой с точки зрения практических ограничений.
                0
                имхо. что бы впечатлить кого то на хабре, надо привести пример какой то крутой системы которая на prolog написана, а приводить веселый пример людям которые в большинстве «ниасилили» декларативное программирование, это как то странно
                  0
                  это пример про занимательность решения задач, про удобство программирования на пролог, далее выбираем следующую задачу из leetcode.com и быстро решаем ))
                  0
                  Если решить задачку, будут ли какие нибудь плюшки?
                    0

                    Отвечу цитатой из книги Ф. Брукса:


                    Почему заниматься программированием интересно? Какими радостями вознаграждаются те, кто им занимается? Во-первых, это просто радость, получаемая при создании чего-либо своими руками. Как ребенок радуется, делая куличики из песка, так и взрослый получает удовольствие, создавая какие-либо вещи, особенно если сам их и придумал. Я думаю, что этот восторг — отражение восторга Господа, творящего мир, восторга, проявляющегося в индивидуальности и новизне каждого листочка и каждой снежинки.
                      0
                      Очень жаль, а то уже второй день бьюсь над задачкой.
                      Сейчас вот думаю, продолжать или нет.

                      А у вас собственно получилось или еще есть баги?
                      Я не знаю пролог, и потому не могу оценить ваше решение.

                        +1

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

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

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