Möglichkeiten zur Suche bzw. Abfrage von Objekten

[BlackJack]

@mutetella: `left_value()` bleibt `None` weil Du immer nur `next()` verwendest und nie `send()` was man braucht um in den laufenden Generator auch Werte hinein zu schicken.

Ein Tupel deshalb damit der Code der die Generatoren abarbeitet weiss was er da zurück bekommt — einen Generator, also etwas wo man einen Wert wieder hinein schicken muss, oder einen ausgerechneten Wert als letztes Element des Generators.

[mutetella]

@BlackJack: Ich kapier' das einfach mit dem Tupel nicht. Weshalb schicke ich dem Generator nicht `True` oder `False` je nachdem, ob `submit()` wieder einen Generator generiert oder letztlich einen Wert ausgibt?
Mir ist auch nicht klar, ob ich den Ausdrucksbaum hinabsteigen soll oder ob das eher ein ping-pong ist. Wobei, wenn ich hinabsteige bräuchte es das, was ich noch nicht verstehe, ja überhaupt nicht, oder?

Ich bin gerade hier:

Code: Alles auswählen

def submit(self):
    left_value = yield self.left.submit()
    if isinstance(left_value, types.GeneratorType):
        pass # welchem Generator soll ich denn nun was schicken???
    yield left_value

Wenn ich dem Generator nun ein `None` sende, dann stehe ich beim ersten `yield`. Und da stehe ich dann.

Ich weiß g'rad gar nicht mehr, was ich innerhalb von `submit()` eigentlich auswerten soll. Eigentlich geht es doch nur darum, zu schauen, ob `submit()` einen Generator oder einen Wert sendet. Wenn's ein Generator ist, dann geh' ich da solange hinein, bis ich einen Wert habe, oder???

mutetella

[BlackJack]

@mutetella: Das ist eher ein Ping-Pong. Du gibst den Generator für den linken Unterausdruck zurück und ein `bool` das dem Aufrufer sagt das das nicht das Ergebnis von dem `submit()` ist sondern dass der Aufrufer den Generator der da zurück gegeben wurde solange auswerten soll bis letztendlich ein Wert heraus kommt und den Wert, muss der dann zurück schicken. Denn das ist dann ja der Wert für den linken Unterausdruck den man gerne an `left_value` binden möchte und dann am Ende zurückgeben möchte.

Was der Aufrufer nicht machen wird ist einen Generator wieder reinzusenden, sondern nur Werte. (Falls der Wert zufällig ein Generator ist, dann darf man mit dem in dem Ping-Pong-Teil des Codes nichts spezielles machen, nur in dem Teil der mit den Werten arbeitet.)

[BlackJack]

Okay, ich hab's ein wenig umgeändert so dass nicht mehr ein Tupel zurückgegeben wird bei dem das erste Element aussagt was das zweite Element bedeutet — Wert oder Generator — sondern ein Tupel mit Wert und Generator, wobei eines der beiden Elemente jeweils immer `None` ist. Der Aufrufer kann dann am Generator-Element erkennen was er tun muss, je nach dem ob er da `None` geliefert bekommt, oder etwas anderes. Haskell hätte dafür den `Either`-Typ.

Am einfachsten wäre `Constant`. Dann das `Equals` was ich ja schon mal gepostet habe, und bei `Or` Kurzschlussauswertung:

Code: Alles auswählen

class Constant(object):
    def __init__(self, value):
        self.value = value

    def submit(self, _obj):
        yield (self.value, None)


class Equals(object):
    def __init__(self, left, right):
        self.left, self.right = left, right

    def submit(self, obj):
        left_value = yield (None, self.left.submit(obj))
        right_value = yield (None, self.right.submit(obj))
        yield (left_value == right_value, None)


class Or(object):
    def __init__(self, left, right):
        self.left, self.right = left, right

    def submit(self, obj):
        left_value = yield (None, self.left.submit(obj))
        if left_value:
            yield (left_value, None)
        else:
            right_value = yield (None, self.right.submit(obj))
            yield (right_value, None)


def submit(expression, obj):
    pass # Diese Funktion ist gesucht. :-)


def main():
    expression = Or(
        Equals(Constant(4711), Constant(23)), Equals(Constant(42), Constant(42))
    )
    result = submit(expression, None)
    print result


if __name__ == '__main__':
    main()

Gesucht ist jetzt eine Lösung für die `submit()`-Funktion, die das ganze nicht rekursiv auswertet. Also eine Schleife und ein eigener, selbst verwalteter „Aufrufstapel” der nicht durch das Rekursionslimit begrenzt ist. Eigentlich ganz einfach, wenn man den Knoten im Hirn erst einmal gelöst hat. Ich habe da 10 Zeilen stehen, die allesamt recht einfach sind. Also keine komplizierten Ausdrücke.

[mutetella]

Puh.... ich glaub', jetzt hab' ich es...

Code: Alles auswählen

def submit(expression, obj):
    stack = [expression.submit(obj)]
    value = None
    while stack:
        try:
            value, expression = stack[-1].send(value)
        except StopIteration:
            stack.pop()
        if value is None:
            stack.append(expression)
    return value

Kann man das grundsätzlich so lassen oder geht noch was?
Die Wand, gegen die ich immer wieder gelaufen bin, war die Vorstellung, die `submit()`-Methoden müssten sich gegenseitig den Ball zuwerfen bis letztlich alles wieder bei der 'Boss-Expression' landet. Dass `submit()` eine eigenständige Funktion ist, hast Du zwar erwähnt, irgendwie wollte sich das aber in meinem Hirn nicht festsetzen...

Dabei lernt man auf jeden Fall etwas.

Danke für die Herausforderung!

mutetella

[BlackJack]

@mutetella: Meine Version sieht so aus:

Code: Alles auswählen

def submit(expression, obj):
    stack = list()
    value, frame = None, expression.submit(obj)
    while True:
        if frame is None:
            stack.pop()
            if not stack:
                return value
        else:
            stack.append(frame)
        value, frame = stack[-1].send(value)

Ist etwas anders strukturiert, aber grundsätzlich wohl das selbe. Was nicht so schön bei Dir ist, dass Du `value` auf `None` testest und dann etwas bestimmtes machst. Das bedeutet Dein Code kommt nicht damit klar wenn der Wert *tatsächlich* `None` ist, also nicht dafür steht das es keinen Wert gibt. Bei `expression` ist das eindeutig.

Falls Du noch nicht genug Hirngymnastik hattest, kannst Du ja noch überlegen wie man das machen könnte wenn Python keine Generatorfunktionen hätte.

[mutetella]

... dass Du `value` auf `None` testest ...

Stimmt, ich hab's in

Code: Alles auswählen

if expression is not None:
    stack.append(expression)

geändert. Ansonsten hab' ich es gelassen, weil ich ``return`` immer gerne am Ende habe.

Falls Du noch nicht genug Hirngymnastik hattest, kannst Du ja noch überlegen wie man das machen könnte wenn Python keine Generatorfunktionen hätte.

Noch ein wenig holprig, mein 38. Entwurf, aber es funktioniert schon mal:

Code: Alles auswählen

class Equal(object):
    def __init__(self, left, right):
        self.left, self.right = left, right

    def submit(self, obj):
        left_value = yield (None, self.left.submit(obj))
        right_value = yield (None, self.right.submit(obj))
        yield (left_value == right_value, None)

    def genless_submit(self, obj):
        self.wannabe = lambda: None
        self.wannabe.obj = obj
        self.wannabe.returns = [self.left, self.right]
        self.wannabe.values = []
        def send(value):
            if value is not None:
                if len(self.wannabe.values) == 2:
                    raise StopIteration
                self.wannabe.values.append(value)
            try:
                return (None, self.wannabe.returns.pop(0).submit(
                    self.wannabe.obj))
            except IndexError:
                return (self.wannabe.values[0] == self.wannabe.values[1], 
                        None)
        self.wannabe.send = send
        return self.wannabe

mutetella

[mutetella]

Ich greif` das Thema nochmals auf... Bin gerade dabei, docstrings zu schreiben und weiß wieder einmal nicht genau, wie ich die Dinge benennen soll. Ist folgendes soweit korrekt?

• Constant('word') -> 'term', 'literal'
• NotEqual(Constant(100), Constant(100)) -> 'expression'
• And(NotEqual(Constant(100), Constant(100)), Contains(Constant('b'), Constant(['a', 'b', 'c']))) -> 'compound expression', 'pattern'

mutetella

[mutetella]

Oh Mann... ich bekomm' einfach die Kurve nicht...!

Ich hab' mein Modul dahingehend erweitert, dass Treffer samt (left, right) zurückgegeben werden, damit ich diese dann in der Ausgabe hervorheben kann. Zudem werden Ergebnisse von Abfragen, die mit `And` verkettet sind, erst dann zurückgegeben, wenn auch beide Seiten der `And` Bedingungen erfüllt sind. Hier liegt aber der Knackpunkt: Wenn ich eine `And` Kette wiederum mit `And` verknüpfe, werden beide Seiten separat behandelt, also:

Code: Alles auswählen

In [17]: left = And(Contains(Constant('bla'), Key('test')), Contains(Constant('alb'), Key('test')))

In [18]: submit(left, {'test': 'alb bla'})
Out[18]: defaultdict(<type 'list'>, {'test': ['bla', 'alb'], 'obj': {'test': 'alb bla'}})

Soweit gut, beide Bedingungen treffen zu.

Code: Alles auswählen

In [19]: right = Contains(Constant('lab'), Key('test'))

In [20]: submit(right, {'test': 'alb bla'})
Out[20]: defaultdict(<type 'list'>, {})

Hier wird korrekterweise nichts zurückgegeben, da die Bedingung nicht zutrifft.

Code: Alles auswählen

In [21]: submit(And(left, right), {'test': 'alb bla'})
Out[21]: defaultdict(<type 'list'>, {'test': ['bla', 'alb'], 'obj': {'test': 'alb bla'}})

Hier wird der Treffer aus `left` ausgegeben, weil dieses `And` auch zutrifft. Ich möchte allerdings, dass auch `right` berücksichtigt wird und somit nichts zurückgegeben wird.

Hier der Code:

Code: Alles auswählen

class Key(object):
    def __init__(self, name):
        self.name = name

    def submit(self, obj):
        yield (None, None, (obj[self.name], self.name), None)


class Constant(object):
    def __init__(self, value):
        self.value = value

    def submit(self, obj=None):
        yield (None, None, self.value, None)


class Contains(object):
    def __init__(self, left, right):
        self.left, self.right = left, right

    def submit(self, obj):
        left_value = yield (None, None, None, self.left.submit(obj))
        right_value = yield (None, None, None, self.right.submit(obj))
        result = left_value in right_value[0]
        if result:
            yield (None, (right_value[1], left_value), result, None)
        else:
            yield (None, None, result, None)


class And(object):
    def __init__(self, left, right):
        self.left, self.right = left, right

    def submit(self, obj):
        left_value = yield (True, None, None, self.left.submit(obj))
        right_value = yield (True, None, None, self.right.submit(obj))
        result = left_value and right_value
        yield (False, result, result, None)


def submit(expression, obj):
    stack = [expression.submit(obj)]
    result = collections.defaultdict(list)
    reserved_matches = collections.defaultdict(list)
    value = None
    reserve = None
    while stack:
        try:
            reserve_, match, value, expression = stack[-1].send(value)
            reserve = reserve_ if reserve_ is not None else reserve
            if match is not None:
                if reserve is None:
                    result[match[0]].append(match[1])
                elif reserve:
                    reserved_matches[match[0]].append(match[1])
                elif not reserve:
                    if match:
                        for key in reserved_matches:
                            result[key].extend(reserved_matches[key])
                    reserved_matches = collections.defaultdict(list)
                    reserve = None
        except StopIteration:
            stack.pop()
        if expression is not None:
            stack.append(expression)
    if result:
        result['obj'] = obj
    return result

Das Ergebnis aus `left` müsste also noch so lange in `reserved_matches` bleiben, bis klar ist, dass keine weitere `And` Bedingung mehr zutreffen muss... Allerdings weiß `left` ja nicht, dass es ein left innerhalb einer `And` Verkettung ist.... Könnte mich jemand bitte aus meinem Sumpf ziehen??

mutetella

[BlackJack]

@mutetella: Ich denke Du versuchst das an der falsche Stelle zu lösen. Jeder Teilausdruck sollte zurückliefern worauf er matcht. Ein `And` wertet dann seine beiden Teilausdrücke aus und gibt die Matches von den denen nur dann weiter „nach oben” wenn beide gematcht haben. Ansonsten verwirft das `And` die Treffer seiner Teilausdrücke.

[bwbg]

sma hatte doch mal einen Parser vorgestellt, in welchem ähnlich verfahren worden ist. Vielleicht kannst Du dort Inspiration finden.

[mutetella]

@bwbg: Danke für den Hinweis, das schaue ich mir gerne an, wobei mir scheint, dass sma dadurch, dass er Funktionen und keine Werte weiterreicht, etwas anderst vorgeht. Wobei das letztlich wohl aufs selbe hinausgeht...

mutetella

[mutetella]

Ok, wieder eine Lektion im Fach "Weniger ist oft mehr!"...

Hab' jetzt diesen ganzen `reserve_...` Irrsinn innerhalb `submit` entfernt und, wie BlackJack sagte, in die `And` verlagert, wo die Auswertung letztlich ja auch hingehört (ähnlich wie in sma's Parser):

Code: Alles auswählen

class Key(object):
    def __init__(self, name):
        self.name = name

    def submit(self, obj):
        yield ((obj[self.name], self.name), None)


class Constant(object):
    def __init__(self, value):
        self.value = value

    def submit(self, obj=None):
        yield ((self.value, None), None)


class Contains(object):
    def __init__(self, left, right):
        self.left, self.right = left, right

    def submit(self, obj):
        left_value = yield (None, self.left.submit(obj))
        right_value = yield (None, self.right.submit(obj))
        if left_value[0] in right_value[0]:
            yield (((right_value[1], left_value[0]),), None)
        else:
            yield (False, None)


class And(object):
    def __init__(self, left, right):
        self.left, self.right = left, right

    def submit(self, obj):
        left_value = yield (None, self.left.submit(obj))
        if left_value:
            right_value = yield (None, self.right.submit(obj))
            if right_value:
                yield (left_value + right_value, None)
            else:
                yield (False, None)
        else:
            yield (False, None)


def submit(expression, obj):
    stack = [expression.submit(obj)]
    value = None
    result = collections.defaultdict(list)
    while stack:
        try:
            value, expression = stack[-1].send(value)
        except StopIteration:
            stack.pop()
        if expression is not None:
            stack.append(expression)
    if value:
        result['obj'] = obj
        for k, v in value:
            result[k].append(v)
    return result

Jetzt klappt's auch mit verschachtelten `And` expressions:

Code: Alles auswählen

In [164]: left = And(
Contains(Constant('bla'), Key('foo')),
Contains(Constant('bumm'), Key('foo'))
)

In [165]: right = And(
Contains(Constant('bim'), Key('foo')),
Contains(Constant('bam'), Key('foo'))
)

In [166]: submit(And(left, right), {'foo': 'bla bumm bim bam'})
Out[166]: defaultdict(<type 'list'>, {'foo': ['bla', 'bumm', 'bim', 'bam'], 'obj': {'foo': 'bla bumm bim bam'}})

In [167]: submit(And(left, right), {'foo': 'bla bumm bim'})
Out[167]: defaultdict(<type 'list'>, {})

Passt doch so, oder hab' ich was übersehen, das mir übermorgen um die Ohren fliegt?

mutetella