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

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

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

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

1. Итак

Тут ^[2]выбираем ближайшее к самым сложным задание, и пытаемся его решить на 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 ^[3], там есть онлайн редактор, вот:

Уппс. Вот что значит никого не обманывать, это высокий порог входа, обращения к библиотечным предикатам не правильные. Ищем правильные встроенные предикаты для работы с атомами.
И на картинке сообщение, что переменная 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 ^[4] (да, да, мы решаем задачу номер 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 как разминка для ума. Забавно на нем решать задачи, хоть данное решение и не обладало никакой оптимизацией. Добраться вручную до более сложных тестов, оказалось очень трудоемко, доказать полноту решения пока не удалось. А до размера хабр-статьи мне кажется я уже добрался.

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

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

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

Автор: go-prolog

Источник ^[6]