Реализация переборного механизма пролога на Python

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

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


в традиционных языках представляется чем-то вроде следующей вложенной конструкции

for Y in pred1(X) {
  for Z in pred2(Y) {
    pred3(Z)
  }
}


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

Однако, мы отвлеклись. Собственно, мне захотелось проверить справедливость приведенного свойства на примере задачи определения правильности скобочной структуры. Оказалось, что прологовский переборно-откатный механизм хорошо вписывается в питоновские генераторы. Вот что получилось в итоге.

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.

Собственно, интерес тут представляет только функция brackets_3, которая, в целом, эквивалентна исходному пролог-решению.