Convert Tail-Call Recursive Code to Loop
A quick search for "python tail call optimization" results in this SO answer which has a PyPI package, tco. Converting your code to return lists rather than generators should be all you need.


  recursion is the only way to do looping in a logic programming language


This is wrong.

If you want it to stay as a generator, then you'll have to manually handle the stack. The following doesn't account for order so if you need that then you'll have to figure that out yourself.

def evaluate_and(and_clauses, binds={}):
    stack = [(clauses, binds)]
    while stack:
        and_clauses, binds = stack.pop()
        if and_clauses == []:
            yield binds
        else:
            head, *tail = and_clauses
            possible = evaluate(head, binds)
            for p in possible:
                stack.append((tail, p))