AST - Modul

[Jaga]

Hi zusammen,
hat von euch jemand schonmal was mit den Abstract Syntax Trees gemacht und könnte mir ein kleines Tutorial verschaffen.
Ich würde gerne eine Ableitungsfunktion selbst schreiben.

Danke für eure Hilfe

[BlackJack]

@Jaga: Die Frage ist ob man sich mit dem `ast`-Modul nicht mehr Ballast in den AST holt als nötig ist. Sich also um mehr Python-spezifische Knoten und Attribute kümmern muss als man für das eigentliche Problem benötigt. Ich würde wahrscheinlich eher selbst einen Parser schreiben der Formeln in eine geeignete AST-Struktur überführt. Für die Knoten braucht man dann ja auch Methoden für die Ableitung, die das `ast`-Modul natürlich nicht bietet. Für's parsen fand ich `pyparsing` immer ganz nützlich. Gibt aber auch andere Parserbibliotheken.

[Sirius3]

Hi Jaga,
mit schnell mal ein kleines Tutorial ist es bei abstrakten Syntaxbäumen nicht getan. Geh am besten in Deine lokale Unibibliothek und such in der Informatikabteilung einen der 1000 Seitenwälzer zu diesem Thema und arbeite ihn durch.
Ansonsten läßt sich ein Funktionenparser viel einfacher konkret als abstrakt implementieren:
Ein Ausdruck besteht aus Termen die mit + oder - verbunden werden, Terme aus Faktoren die mit * oder / verbunden werden und Faktoren wiederum aus einem Teil, der potenziert werden soll (keine Ahnung wie da der Fachbegriff ist) und der Potenz, wobei hier zu beachten ist, das Potenzieren rechtsassoziativ ist. Und dieser letzte Teil kann dann wiederum ein Klammerausdruck sein, womit wir wieder rekursiv von vorne anfangen, eine Funktion, eine Variable oder eine Zahl.
Am besten implementierst Du jeden einzelnen Typ als Klasse, die dann Methoden zum Berechnen des Wertes hat, oder ihre Ableitungsregel implementiert (z.B: (f+g)'=f'+g', (f*g)'=f'*g+g'*f).
Als ich damals in der 10. Klasse war, hab ich mich genau an so eine Aufgabe gewagt, ohne irgendeine Ahnung von AST gehabt zu haben.

[Jaga]

was würdet ihr mir dann raten zu tun?

[BlackJack]

@Jaga: `sympy` verwenden natürlich.

Oder eben sehr viel lesen und lernen. Und dann fang doch einfach mal mit den Klassen für so einen Baum an, der einen Ausdruck repräsentiert. Im ersten Schritt dann die `__str__()`-Methode auf den Klassen so implementieren, dass eine Zeichenkette mit dem Ausdruck erzeugt wird.

Danach kannst Du dann den Parser schreiben der die Zeichenkette mit dem Ausdruck in einen Baum überführt. Dann kannst Du einen „round trip” machen, also einen Ausdruck aus einer Zeichenkette in den Baum überführen und den per ``print`` wieder zu einem Ausdruck als Zeichenkette umwandeln. Spätestens nach dem zweitem „round trip” sollten Eingabe und Ausgabe gleich sein, wenn alles richtig funktioniert. Beim ersten mal muss das noch nicht sein, wenn man binäre Teilausdrücke der einfachhalt halber grundsätzlich klammert auch wenn das nicht wirklich notwendig wäre.

Wenn Zeichenkette→AST und AST→Zeichenkette funkioniert kannst Du die Ableitung auf dem Baum einbauen. Und dann wärst Du auch ”schon” am Ziel. Die Frage ist halt wieviel wissen Dir auf dem Weg dahin noch fehlt und wie lange es dauert das zu lernen.

[Hyperion]

was würdet ihr mir dann raten zu tun?

Vielleicht verrätst Du uns erst einmal, in welchem Rahmen Dein Ableitungstool enstehen soll? Bist Du Schüler oder Student? Ist das eine freiwillige Aufgabe oder eine verpflichtende? Wie / inwelchem Umfang ist Python dort bisher vermitelt worden? Wer hat Dir diese Aufgabe erteilt? Ist das im Wissen um die Komplexität geschehen? Bist Du sicher, dass Du das wirklich universell lösen sollst?

Ich nannte Dir ja in einem der unzähligen anderen Threads zu diesem Thema schon die Option, das ganze für einfache Polynome zu implementieren - allerdings ohne symbolische Eingabe der Formel, sondern mittels Abfragen der Koeffizienten. Evtl. *reicht* das ja als Lösung!

Fragen über Fragen...

[Jaga]

@ Hyperion
Also ich bin Schüler und die ganze Ableitungsgeschichte soll in einen Funktionsplotter eingebaut werden. Das Ganze ist der Praxisteil meiner Seminararbeit (W-Seminar mit dem Titel " Softwareentwicklung mit Python " ). Allerdings beruht hier sehr viel auf "learning by doing so do it yourself" sprich jeder Seminarteilnehmer erhielt ein Thema (z.B. Mathematik in Python oder Eclipse und und und..). Folglich wurden uns nur oberflächlich die verschiedenen Themen präsentiert. Mei Plotter zeihnet schon nun nahezu jeden Funktion und deshalb würde ich gerne ALLE Funktionen ableiten können. Mir war außerdem bewusst dass die Ableitung selbst zu schreiben nicht gerade leicht wird, aber das Sympy - Modul war nur als Notlösung gedacht.

Hier mein Code bisher:

Code: Alles auswählen

import matplotlib.pyplot as plt
import numpy as np
import Tkinter
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg, NavigationToolbar2TkAgg
import parser
import re


REPLACE_DIC = {'sin' : 'np.sin',
               'arcsin' : 'np.arcsin',
               'sinh' : 'np.sinh',
               'arcsinh' : 'np.arcsinh',
               'cos' : 'np.cos',
               'arccos' : 'np.arccos',
               'cosh' : 'np.cosh',
               'arccosh' : 'np.arccosh',
               'tan' : 'np.tan',
               'arctan' : 'np.arctan',
               'tanh' : 'np.tanh',
               'arctanh' : 'np.arctanh',
               'ln' : 'np.log',
               'log' : 'np.log',
               'log10' : 'np.log10',
               'exp' : 'np.exp',
               '^' : '**',
               'sqrt' : 'np.sqrt',
               'pi' : 'np.pi',
               
               }
class App():

    def __init__(self, master):

        self.master = master
        master.protocol("WM_DELETE_WINDOW", self.ende)
        self.initUI()

    def ende(self):
        self.master.destroy()
        self.master.quit()

    def initUI(self):
        

        
        self.master.title("Funktionsplotter")

           
        
        
        self.label_funktion = Tkinter.Label(self.master, text = "Funktion: f(x)")
        self.label_funktion.grid(row = 0, column = 0)

        self.entry_funktion = Tkinter.Entry(self.master, width = 150)
        self.entry_funktion.grid(row = 0, column = 1)

        self.label_startwert = Tkinter.Label(self.master, text = "Startwert der Funktion:")
        self.label_startwert.grid(row = 2, column = 0)

        self.entry_startwert = Tkinter.Entry(self.master, width = 15)
        self.entry_startwert.grid(row = 2, column = 1)

        self.label_endwert = Tkinter.Label(self.master, text = "Endwert der Funktion:")
        self.label_endwert.grid(row = 3, column = 0)

        self.entry_endwert = Tkinter.Entry(self.master, width = 15)
        self.entry_endwert.grid(row = 3, column = 1)

        self.label_genauigkeit = Tkinter.Label(self.master, text = "Abstand zwischen zu berechnenden Punkten:")
        self.label_genauigkeit.grid(row = 4, column = 0)

        self.entry_genauigkeit = Tkinter.Entry(self.master, width = 15)
        self.entry_genauigkeit.grid(row = 4, column = 1)

        self.plot_button = Tkinter.Button(self.master, text = "Funktion plotten", command = self.plot)
        self.plot_button.grid(row = 0, column = 4)

        self.hinzufueg_button = Tkinter.Button(self.master, text = "Zum Plot hinzufügen", command = self.hinzufuegen)
        self.hinzufueg_button.grid(row = 2, column = 4)

        

        fig = plt.figure()
        self.canvas = FigureCanvasTkAgg(fig, master=self.master)
        self.toolbar = NavigationToolbar2TkAgg(self.canvas, self.master)
        self.canvas.get_tk_widget().grid(row=5, column=1)
        self.toolbar.grid(row=7, column=1)



    def formel_berechnen(self,):
            self.x = np.arange(float(self.entry_startwert.get()),
                                float(self.entry_endwert.get()),
                                float(self.entry_genauigkeit.get()))

            x = self.x
            formula_raw = self.entry_funktion.get().replace('e^x', 'exp(x)')
            formula_raw_exp = formula_raw.replace('e^', 'exp')
            formula_list = re.split('(\W)', formula_raw_exp)
            formula_replace = [REPLACE_DIC.get(item,item) for item in formula_list]
            formula_finish = ''.join(formula_replace)
            form = parser.expr(formula_finish).compile()
            try:
                self.y = eval(form)
                self.legend = self.entry_funktion.get()
            except NameError:
                self.y = np.sin(self.x)
                self.legend = 'sin(x)'
            
            return (self.x,self.y,self.legend)
        
    
        

    def plot(self):
            self.formel_berechnen()
            plt.clf()
            plt.plot(self.x,self.y, label=self.legend)
            plt.grid('on')
            plt.xlabel('x - Achse')
            plt.ylabel('y - Achse')
            plt.legend()
            plt.gcf().canvas.draw()

    def hinzufuegen(self):
            self.formel_berechnen()
            plt.plot(self.x,self.y, label=self.legend)
            plt.legend()
            plt.gcf().canvas.draw()

    


            
def main():
     
     root = Tkinter.Tk()
     app = App(root)
     root.mainloop()

if __name__ == '__main__':
    main()

Und hier die Kriterien aus dem Pflichtenheft:

Musskriterien:
- Kartesisches Koordinatensystem mit horizontaler x – Achse und vertikaler y – Achse
- Beschriftung der Achsen
- Verstellbarkeit der Einheiten der Achsen
- Karomuster als Hintergrund
- Fenster zur Eingabe der Funktion
- Möglichkeit zur Farbänderung des Graphen
- Zeichnen von Tangenten und Normalen an best. Punkten
- mögliches Einzeichnen der senkrechten, waagrechten und schrägen Asymptoten

Wunschkriterien:
- Berücksichtigung von trigonometrischen und logarithmischen Funktionen
- Berücksichtigung spezieller Zahlen wie e oder π
- Buttons zur Zahlen-/ Funktionseingabe
- Streckung/ Stauchung des Graphen mit der Maus
- gleichzeitige Darstellung mehrerer Graphen in verschiedenen Farben

Abgrenzungskriterien:
- kein sphärisches Koordinatensystem möglich
- keine Möglichkeit Punkte im Koordinatensystem zu markieren


Ich hoffe du kannst mir irgendwie weiterhelfen.

[Hyperion]

Ok, also mein Rat wäre: "Mache" doch auch Softwareentwicklung, wenn das schon im Titel steht. D.h. *nutze* sinnvolle Bibliotheken, die Dich zum Ziel führen. Das Ziel ist es offensichtlich *nicht*, einen Parser für mathematische Terme zu schreiben, sondern einen Funktionsplotter! Insofern verstehe ich Deine Abneigung gegen Sympy nicht - zumal Du ja auch Numpy benutzt...

Im Sinne der Softwareentwicklung muss man sich bei jedem Projekt die Frage stellen, *was* man für sein Projekt braucht, *was* es da ggf. an *fertigen* Modulen gibt und ggf. *welche* man dafür benutzen will. Da können viele kriterien ausschlaggebend sein, etwa die Lizenz, die "Reife" einer Lib, usw.

Natürlich kann man auch zu dem Punkt gelangen, dass man sich entscheidet, etwas selber zu implementieren, aber das ist Abwägungssache. Und Du hast uns bisher nichts genannt, was das rechtfertigen würde

Wenn es Dich persönlich interessiert: Prima, versuche das (nebenbei!) umzusetzen in Deiner Freizeit. Später kannst Du es ggf. in Dein Projekt einbauen. Aber um erst einmal zu einem vernünftigen Ergebnis zu kommen, nutze doch einfach die Lib, die das bereits gelöst hat, was Du suchst.

Wenn ich mir den Code so ansehe, fallen mir da leider auch ganz viele konzeptionelle Fehler auf... ich denke da ist es sinnvoller, an denen zu arbeiten als sich mit einer komplexen (wenn vielleicht auch spaßigeren) Sache wie einem Parser rumzuschlagen.

Beispiel:
- eine Klasse ``app`` zu nennen ist... niemals sinnvoll, es sei denn, ein Rahmenwerk würde dies fordern

- Deine Klasse macht viel zu viel! Du verletzt damit das SRP Insbesondere das Berechnen der Werte gehört nicht in eine Klasse für die Darstellung!

- im Grunde kannst Du obige Punkte verbessern, indem Du eine klare Trennung von GUI und Logik durchführst. Schreibe also Funktionalität zum Berechnen der zu plottenden Werte, zum Plotten an sich und für die reine GUI.

- Beachte PEP8! Du wechslst auch in Deinem Benennungsstil, was es noch unübersichtlicher macht.

- Benutze Doc-Strings, am besten mit Notation, die Sphinx versteht.

- Versuche wenigstens einige Dinge mittels Unit-Tests abzudecken! Sich darin einzuarbeiten ist wesentlich sinnvoller, als einen Formel-Parser zu bauen. Speziell das Wandeln einer Formel von der Eingabe zu einer maschinell auswertbaren Struktur sollte man relativ einfach testen können. Das scheint ja ein Kernpunkt bei Deinem Projekt zu sein. Aber auch das Berechnen von Werten an sich und ggf. auch Sonderfälle.

Vermutlich musst Du ja nicht nur den reinen Quellcode "abgeben", sondern auch beschreiben, wieso und wie Du etwas umgesetzt oder weggelassen hast. Da würde ich dann eher auf Funktionalität verzichten und anmerken, dass das in einer späteren Iteration nachgeliefert werden muss, und das damit rechtfertigen, dass der Code wartbar, erweiterbar und idiomatisch sauber ist.

[pillmuncher]

@Jaga: Nimm Sympy. Wirklich. Das kann schon alles, was du brauchst. Dadurch wirst du erheblich schneller fertig werden, als wenn du mit Gewalt versuchst, selber etwas zu basteln. Und in der gesparten Zeit kannst du anschließend die Grundbegriffe von Lisp oder Prolog lernen, denn da ist es supersimpel einen symbolischen Differentiator zu bauen. Hier ein Beispiel in Prolog. IMO kann man nicht früh genug damit anfangen, deklarative Sprachen zu lernen, zusätzlich zu den prozeduralen. Das hilft einem, unterschiedliche Perspektiven auf gegebene Probleme haben zu können, und wie Alan Kay immer sagt: A change in perspective is worth 80 IQ points.

[BlackJack]

@Jaga: Vor allem sollte man sich nicht in solch umfangreichen Nebensächlichkeiten verlieren wenn noch nicht alle Sollkriterien erfüllt sind.

* Es gibt noch keine Einheiten an den Achsen.
* Die Farbe kann nicht festgelegt werden.
* Tangenten, Normalen, und Asymptoten einzeichnen geht noch nicht.

Der letzte Punkt ist sicher eine Sache die nicht mal eben in fünf Minuten gemacht ist.

Ebenfalls sinnvoll wäre es wahrscheinlich in der GUI nicht *alles* in *ein* Container-Widget zu stecken, sondern die Bedienelemente sinnvoll in `Frame`\s zusammenzufassen. Das macht Änderungen und das Umarrangieren der einzelnen Gruppen einfacher. Zum Beispiel kann man alles zum Bearbeiten einer Formel in einem Widget zusammenfassen und kann sich dann entscheiden ob man das wie die Aufgabe fordert in einem eigenen Fenster anzeigt, oder in das Hauptfenster integriert. Die Erweiterung bei den Wunschkriterien der Darstellung mehrerer Graphen wird dann auch einfacher, denn wenn man ein Eingabewidget für eine Funktion + Farbe geschrieben hat, kann man das mehrfach für die verschiedenen Funktionen verwenden.

Das `parser`-Modul macht hier übrigens keinen Sinn. Es gibt bereits in den eingebauten Funktionen eine `compile()`-Funktion die letztendlich das selbe leisten kann was Du dort machst. Bei `eval()` möchtest Du eigentlich auch nicht einfach so dass der Benutzer nahezu beliebigen Python-Code ausführen kann. Man sollte dort ein Wörterbuch mit dem zur Verfügung stehenden Namensraum angeben und den Schlüssel '__builtins__' explizit auf irgendeinen Wert abbilden (beispielsweise `None`) damit man besser kontrollieren kann welche Funktionen der Benutzer tatsächlich verwenden kann. In das Wörterbuch kann man auch die ganzen Numpy-Funktionen werfen und sich damit das Ersetzen in der Formelzeichenkette sparen.

[EyDu]

Schöne Fingerübung für einen Sonntagnachmittag. Irgendwie muss man sich um seine Arbeit drücken ...

Natürlich komplett ohne Prüfungen, Fehlerbehandlung oder Beschreibungen der Methoden:

Code: Alles auswählen

"""
python drv.py function min_x max_x sampling

E.g.:
    python drv.py "x**2" -10 10 0.1
    python drv.py "sin(x) -10 10 0.1
"""

import functools
import matplotlib.pyplot as plt
import numpy as np
import sys

from collections import namedtuple
from sympy.parsing.sympy_parser import parse_expr as parse_expression


def on_mouse_move(ax, fig, data, event):
    x = event.xdata
    y = evaluate_at(data.expression, x)
    m = evaluate_at(data.derivative, x)

    ax.cla()
    
    #plot expression and derivative
    plot_graphs(ax, data.xs, data.ys_expression, data.ys_derivative)
    
    #plot tangent
    b = y - m*x
    y_left = m*data.xs[0] + b
    y_right = m*data.xs[-1] + b
    ax.plot([data.xs[0], data.xs[-1]], [y_left, y_right], "-", color="pink")
    
    #plot current point
    ax.plot([x], [y], "o", color="green")
    
    fig.canvas.draw()


def evaluate_at(expression, x):
    return float(expression.evalf(subs={"x":x}))


def evaluate(expression, xs):
    return [evaluate_at(expression, x) for x in xs]


def plot_graphs(ax, xs, ys_expression, ys_derivative):
    #lilmits
    ax.set_xlim([xs[0], xs[-1]])
    
    ys = ys_expression + ys_derivative
    low, high = min(ys), max(ys)
    height = high - low
    delta = 0.1*height
    ax.set_ylim([low-delta, high+delta])
    
    #plot
    ax.plot(xs, ys_expression, "-", color="blue")
    ax.plot(xs, ys_derivative, "-", color="red")
    

def main():
    expression = sys.argv[1]
    x0 = float(sys.argv[2])
    xn = float(sys.argv[3])
    step = float(sys.argv[4])

    expression = parse_expression(expression)
    derivative = expression.diff("x")
    
    xs = np.arange(x0, xn, step)
    ys_expression = evaluate(expression, xs)
    ys_derivative = evaluate(derivative, xs)
    
    #prepare plot
    fig = plt.figure()
    ax = fig.add_subplot(111)
    
    #status data
    Data = namedtuple(
        "Data",
        ["expression", "derivative",
         "xs", "ys_expression", "ys_derivative"])
    
    data = Data(
        expression, derivative,
        xs, ys_expression, ys_derivative)
    
    #register events
    fig.canvas.mpl_connect(
        "motion_notify_event",
        functools.partial(
            on_mouse_move, ax, fig, data))
    
    #plot
    plot_graphs(ax, xs, ys_expression, ys_derivative)
    plt.show()


if __name__ == "__main__":
    main()

[Jaga]

habt ihr nen link zum einem Sympy - Tutorial?

[webspider]

Bitte sehr