Implementing a bridging mechanism of a prolog in Python

As it is known (some), the prologue has the remarkable property that the call of each predicate in the general case generates several (although, maybe not one) return points. This means that if at a certain step the call of the next predicate fails, the execution will be rolled back to the nearest point of return, and the execution will continue with new alternative data returned by the predicate that generated the return. When all returns at a certain point are exhausted, a rollback to the previous, previous-previous, etc. will be performed. return points. Probably, the savvy reader has already realized that what is written in the prologue is a linear set of predicates, such as



pred1(X, Y), pred2(Y, Z), pred3(Z).





in traditional languages ​​it seems something like the following nested construction

')

for Y in pred1(X) {

for Z in pred2(Y) {

pred3(Z)

}

}





In principle, it is on this remarkable property that the convenience, conciseness and declarativeness of the solutions of some classes of problems in the prologue are based (text analysis, search tasks, ...). Probably, after reading the previous part of this message, you will understand in general terms the solution I have given earlier one entertaining problem .



However, we were distracted. Actually, I wanted to check the validity of the given property by the example of the problem of determining the correctness of the bracket structure . It turned out that the prologovsky re-choice kickback mechanism fits well into the Python generators. That's what happened in the end.

def take_one(s, a):

"" "

takes exactly 1 letter

" ""

if len(s)==0:

return

elif s[0]==a:

yield a, s[1:]

else :

return



def take_one_of(s, letters):

"" "

takes exactly 1 of letters

" ""

if len(s)==0:

return

elif s[0] in letters:

yield s[0], s[1:]

else :

return





def take_ones(s):

for o, t in take_one(s, '1' ):

for oo, t1 in take_ones(t):

yield o+oo, t1

yield '' , s

'' '

for oo, t in take_ones(' 11111abc '):

print ' > ', oo, t

' ''



def brackets(s):

for a, t0 in take_one(s, '(' ):

for b, t1 in brackets(t0):

for c, t2 in take_one(t1, ')' ):

for d, t3 in brackets(t2):

yield a+b+c+d, t3



yield '' , s



def bracket(a, brackets=dict(zip( '([{' , ')]}' ))):

return brackets[a]



def brackets_3(s):



" brackets --> bracket(Close), brackets, Close, brackets."

for a, t0 in take_one_of(s, '([{' ):

for b, t1 in brackets_3(t0):

for c, t2 in take_one(t1, bracket(a)):

for d, t3 in brackets_3(t2):

yield a+b+c+d, t3



" brackets --> []."

yield '' , s



def phrase(gen, s):

"" "

only if the whole string matched

" ""

for h, t in gen(s):

if t== '' :

return h

'' '

def tst(gen, s):

for d in gen(s):

print d



tst(brackets_3, "[]()")

tst(brackets_3, "[]")

' ''



def check():

assert phrase(brackets, '()((()()))(()(()))()' ) != None

assert phrase(brackets, '()((()()))(()(())))()' ) == None



assert phrase(brackets_3, "[[[]]][][[]][()]{}[]" ) != None

assert phrase(brackets_3, "[[[)]]][][[]][()]{}[]" ) == None

assert phrase(brackets_3, "[[[(())(){}]]][][[]][()]{}[]" ) != None

assert phrase(brackets_3, "[[[(())(){}]]][][[]][()]{}[(]" ) == None



check()



* This source code was highlighted with Source Code Highlighter .

Actually, only the function brackets_3 is of interest here, which, in general, is equivalent to the original prolog-solution.