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

Но грустнее дело обстоит с логическим, продукционным программированием, которое можно представить только на 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, там есть онлайн редактор, вот:

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

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

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

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

Автор: go-prolog

Источник