Pythonでのプロローグ列挙メカニズムの実装

（一部の人には）知られているように、プロローグには、一般的な場合に各述語を呼び出すと、いくつかの（おそらく1つではない）戻り点が生成されるという注目すべき特性があります。 つまり、あるステップで次の述語の呼び出しが失敗した場合、実行は最も近いリターンポイントにロールバックされ、リターンを生成した述語によって返された新しい代替データで実行が続行されます。 特定のポイントですべてのリターンが使い果たされると、前、前、前などへのロールバックが実行されます。 リターンポイント。 おそらく、精通した読者は、プロローグに書かれているものが次のような線形の述語のセットであることをすでに認識しています。



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









従来の言語では、次のネストされた構造のようなもののようです



for Y in pred1(X) {

for Z in pred2(Y) {

pred3(Z)

}

}









原則として、プロローグ上の問題のいくつかのクラスの解決策の利便性、簡潔性、および宣言性が基づいているのは、まさにこの注目すべき特性に基づいています（構文解析、検索タスクなど）。 おそらく、このメッセージの前の部分を読んだ後、一般的な用語で、以前に私から与えられた面白い問題の解決策を理解するでしょう。



しかし、気が散りました。 実際、 ブラケット構造の正しさを判断する問題の例を使用して、このプロパティの有効性を確認したかったのです。 プロローグの折りたたみ可能なメカニズムは、Pythonジェネレーターとうまく適合することが判明しました。 結果は次のとおりです。

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だけです。これは、一般に、元のプロローグソリューションと同等です。