Programmdesign eines Interpreters

[picocat]

Ich habe einen guten Grund, die komplexen Zahlen auszuschließen. Ich kenne mich nicht gut damit aus und möchte mich auch ehrlich gesagt nicht weiter damit beschäftigen (die übersteigen stark meine Vorstellungskraft).

Ok, hier mal ein Beispielausdruck:

fakultaet(x:uint) := if(x=0,1,x*fakultaet(x-1))
zahl := 5
ergebnis := fakultaet(zahl)

oder aber

fakultaet(x:uint):uint := if(x=0,1,x*fakultaet(x-1))
zahl:uint := 5
ergebnis:uint := fakultaet(zahl)

wobei ja die Datentypen automatisch erkannt werden können, eine zusätzliche Deklaration also unnötig wäre.

Dynamische Typisierung bezog sich eher darauf, dass die Datentypen automatisch erkannt werden. In gewissen Sinne aber trotzdem statisch, da stimme ich zu.

Das Problem bei einer Lockerung der Einschränkungen wäre, dass die Syntax verkompliziert würde. Schließlich soll noch mit eingebunden werden, dass man physikalisch rechnen kann (also dass Einheiten mit benutzt werden können).

Und zum Schluss noch ein Hinweis: Überladung soll es nicht geben.

Ich hoffe meine (unsere) Intentionen sind klarer geworden

PS: Eine Frage hätte ich noch - was bedeutet "Policy-Klasse" und was ist ein "Quasi-Pimpl"?

[.filmor]

Pimpl steht für Pointer to Implementation (oder so ähnlich, kann auch von der Namensgebungskonvention vieler Programmierer kommen, die Zeiger mit p beginnen lassen, was dann in pImpl oder ähnlichem endet), siehe http://www.gamedev.net/reference/articles/article1794.asp.
Eine Policy gibt eine Richtlinie an, das Verhalten der Klasse. So könntest du z.B. bestimmte Funktionen in eine Policy auslagern, wodurch du, durch Übergabe eines anderen Template-Parameters, das Verhalten der Klasse (bzw. eines Objektes der Klasse) in bestimmten Fällen ändern kannst. SmartPointer werden dafür gerne als Beispiel genommen. Dort kann z.B. das Verhalten für Nullpointer (Dereferenzierung, Übergabe etc.) oder bei der Zerstörung des SmartPointers (z.B. Aufruf von delete für den Pointer, Verringern eines Verweiszählers etc.) in Policies ausgelagert werden.

In deinem Beispiel seh ich ehrlich gesagt nichts mathematisches, eigentlich ist das nur ein Beispiel für eine funktionale Programmiersprache. Ersteres fände ich deutlich interessanter, das gibts afaik noch nicht so richtig

[picocat]

Hallo,

warum siehst du dort nichts Mathematisches? Ich meine, ich kann in diesem Codestück natürlcih nicht alle Varianten darstellen. Aber geplant ist auch noch folgendes:

x := abs({1,2,3,4})
y := det({1,2,3;4,5,6;7,8,9})

usw. usf. Also alle Dinge, die man bei mathematischen Problemen braucht.

Eine Idee hätte ich noch, und zwar folgende:

class Fraction { }; // Bruchimplementation
class Exact { }; // Implementation reeller Zahlen
//...

template<class T>
class Scalar
{
  protected:
    T value;
  public:
    Scalar(const T& val);
    T getVal();
//...
};

template<class T> Scalar<T> operator + (const Scalar<T>& first,const Scalar<T>& second)
{
  return Scalar<T>(first.getVal()+second.getVal());
}

Da habe ich aber noch Probleme damit:

• Wie kann ich alle verschiedenen Skalare in eine Map ablegen? Ohne weiteres geht das sicherlich nicht.
• Weiterhin kann ich nicht einfach so einen Scalar<Fraction> in einen Scalar<Exact> umwandeln, obwohl dass eigentlich kein Problem sein darf.
• Diese Lösung ist eigentlich überhaupt nicht optimiert.

Jetzt gäbe es noch eine zweite Variante:

class Exact { }; // Implementation reeler Zahlen
class Fraction : public Exact { };
//...

Funktioniert aber so auch nicht, weil ich nicht vorhatte, eine homogene Implementation durchzuführen. Dies wäre auch wenig zweckmäßig - einen Exact wollte ich in einen String packen, aber warum einen Bruch? Der lässt sich in zwei ints aufspalten.

Also was tun?

PS: Wie sollte eine math. Sprache mit dem Paradigma, einfach zu sein, deiner Meinung nach aussehen?

[picocat]

Wäre es vielleicht auch zu empfehlen, ein ganz anderes Sprachen-Design vorzunehmen? Ich meine, die meisten Skriptsprachen sind nur äußerst locker typisiert (siehe CSL oder JavaScript). Aber ist denn ein "Variant"-Datentyp wirklich elegant?

[Cpt. Tanga]

evtl. hilfreich:
http://www.softgames.de/developia/viewarticle.php?cid=17852
mfg.

[.filmor]

Ehrlich gesagt sehe ich keinen Grund, eine klassische Typisierung zu benutzen. Schließlich wirst du es außschließlich mit Zahltypen verschiedener Bereiche zu tun haben. Du hast also quasi einen Datentyp, aus dem die anderen durch Einschränkung abgeleitet werden können. Oder du nimmst einen Grundtyp (wie z.B. $\in \mathbb{N}$ und leitest aus ihm die höheren ab. Das alles impliziert, dass es sinnvoller ist, eher Intervalle und Mengen als (abgeleitete) Datentypen zuzulassen, als Typen mit eher informatischen Bezeichnungen wie uint einzuführen oder gar variants einzuführen
zB:

f(x) := 1/x
    {x in |R | x != 0}
// gut, das != ist ein Stilbruch, passt hier eigentlich nicht hin
|Z := |N & -|N & 0
|Q := |N / |N
|R := |N ^ (1 / |N) // x^n = a -> n-te wurzel aus a = x
// ODER
|Z := x {x in |R | x = int (x)}
|N := x {x in |Z | x > 0}
|Q := p/q {p,q in |Z | p/q}

Sowas halt.

[picocat]

Danke für den Ratschlag und die Anregung. Aber es ist ja so, dass wir nur ein halbes Jahr lang Zeit haben und ja auch noch was anderes zu tun haben. Insofern stellt sich jetzt die Frage: Ist dieser Umfang schaffbar (zumal wir mit solchen Dingen überhaupt keine Ahnung haben)?

[picocat]

Und noch ein weiteres Problem fällt mir gerade auf: Warum ist es zweckmäßig, die Wertebereiche so dynamisch einzugrenzen? Schließlich wollen wir ja keinen Gleichungslöser basteln, für den das so relevant wäre.

[.filmor]

Eigentlich wird ja nicht der Wertebereich, sondern der Definitionsbereich eingeschränkt. Das ist quasi der "Typersatz", du sagst damit, dass f(x) mit jedem x aus der Definitionsmenge aufgerufen werden kann. Ich sage nicht, dass es nicht auch sinnvollere Ansätze gibt, aber imho ist für eine rein mathematische, deklarative Programmiersprache "Element der Menge" der einzig sinnvolle Typ. uint etc. sind eigentlich Sachen, die nur Programmierer/Informatiker, nicht Mathematiker etwas angehen.

[picocat]

Danke erst einmal für deinen Vorschlag, aber den kann ich nicht verwerten. Ich meine, z. B. bei 1/x, muss man dem Interpreter doch nicht sagen, dass nicht durch 0 dividiert werden darf. Der kriegt das ja eigentlich selber mit und kann dann einen Fehler ausgeben. Diese Definitionen, dass da Werte nicht mit angegeben werden dürfen, dienen ja in der Mathematik (die auf dem Blatt Papier ausgeführt wird) "nur" der Vollständigkeit. Die Definitionsbereiche müssen aber da sein, weshalb auch der ganze Kram mit exact und fraction usw. usf. mit rein muss. Aber was darüber hinausgeht, finde ich fraglich. Denn wie gesagt: Der Interpreter soll keine Gleichungen lösen, sondern wie ein Taschenrechner mit sehr vielen Funktionen agieren.

[Ben04]

@.filmor Dein R kann keine transentdente Zahlen aufnehmen. Pi wäre ein beispiel.

@Lars Hupel Sag doch mal wo du deine Sprache anwenden willst. Welche Aufgaben soll sie denn erfüllen? Ich meine für eine Fakultät auszurechnen ist C doch unschlagbar elegant. Soll man sie benutzen um eine Zahl zu finden die bestimmte Eigenschaften aufweist? In dem Fall wäre wohl etwas in Richtung Prolog angebracht.

Desweiteren glaub ich nicht, dass eine Zahl aus N von einer Zahl aus R abgeleitet sein sollte. Eine Zahl aus N ist restriktiver als eine aus R jedoch sollte eine abgeleitete Klasse die Basisklasse erweiteren und nicht einschränken. Umgedreht geht es meiner Meinung nach auch nicht. Nicht jede Zahl aus R hat die gleichen Eigenschaften als eine aus N. Ich glaub eine Zahl aus N sollte implicit konvertibar in eine aus R sein. Mit short und int ist es ja auch so.

[.filmor]

Stimmt, aber die kann der Rechner sowieso nur angenähert verwenden. Immerhin sind die meisten irrationalen Zahlen so abgedeckt, unendliche Kettenbrüche bringen nur etwas, wenn sie ein System haben (wie z.B. e oder der Goldene Schnitt). π ist also gar nicht unterzubringen. Aber die "echte" Definition der Reellen Zahlen hab ich nicht so ganz verstanden und könnte sie demnach hier nicht einbringen. (Übrigens fehlt hier sowieso die Hälfte + 1 der Zahlen (jaja, ich weiß |R ist überabzählbar), der Exponent müsste 1 / |Z\{0} und die Basis |N_0 lauten).
Außerdem können die Grundbereiche ja durchaus fest einprogrammiert sein, das war nur ein Beispiel, wie man die Mengen aufbauen könnte. Ich glaub da setz ich mich mal dran, das gefällt mir.

[picocat]

Hallo,

also angewandt werden soll die Sprache, um "mal eben schnell" einen Taschenrechner zur Verfügung zu haben. Aber ein Taschenrechner mit mehr Funktionen. Intention war, dass es mich genervt hat, für irgendwelche Brute-force-behafteten Probleme immer den Compiler anzuwerfen. Dass man keine tollen Performances aus so einem Konzept herausholen kann, ist mir klar.

Jetzt weiß ich aber immer noch nicht, wie ich am besten eine Hierarche aufbauen sollte. Zweckmäßig wäre vielleicht ein Konzept, wobei alle Grunddatentypen separat entwickelt werden, sprich Brüche etc. Dann gibt es eine Klasse, die z. B. vier verschiedene Pointer enthält, jenachdem, welchen Datentyp er enthält (per enum überprüfbar). Bei einer Operation zweier Variablen würde dann ein Ergebnis bringen, welches vom Datentyp des höherwertigen wäre. Beispiel:

class Variable
{
  protected:
    Exact *ex;
    Fraction<int> *frac;
    int *i;
    unsigned integer *ui;
  public:
    Variable() : ex(0), frac(0), i(0), ui(0) { }
};

So z. B. Aber ich habe die Vermutung, dass dies eleganter geht. Möglicherweise müsste ich dafür auf den Templatecharakter von Fraction verzichten. Aber das ginge ja.

Da gäbe es die Möglichkeit

Datentyp
|- Skalar
   |- natürliche Zahl
   |- ganze Zahl
   |- rationale Zahl etc.
|- Geometrie etc.

Das funktioniert aber nicht, wenn ich die Datentyp-/Skalar-Basisklassen rein virtuell mache, weil eine Templateklasse offenbar keine rein virtuellen Methoden implementieren kann. Zumindest meckert der Compiler, wenn es heißt:

class Scalar
{ //...
  public:
    virtual Scalar& add(const Scalar& other) = 0;
};

template<class T>
class Fraction : public Scalar
{ //...
  public:
    Fraction add(const Fraction& other) { /*...*/ }
};

Ich kann dann ein Fraction nicht instanziieren.

[picocat]

Ich grüble jetzt aber schon die ganze Zeit an dem Problem, warum ich die virtuelle Methode nicht implementieren kann. Im Grunde genommen wird ja eine Templateklasse bei Instanziierung vom Compiler generiert. Kann der da keine vtable erstellen? Oder wisst ihr eine bessere Möglichkeit?

[camper]

Fraction add(const Fraction& other) ist keine virtuelle function. das pur virtuelle add der basisklasse hatte eine andere signatur und wird durch dieses neue add versteckt und nicht implementiert. möglich wäre stattdessen

template<class T>
class Fraction : public Scalar
{ //...
  public:
    Fraction& add(const Scalar& other) { /*...*/ }
};

oder etwas anderes zu Scalar& referenz-kompatibles als rückgabetyp. Das LSP verlangt, dass in (öffentlich) abgeleiten klassen die anforderungen an rückgabewerte (nur) verschärft werden können (kovarianz) und die anforderungen an parameter veringert (kontravarianz). letzteres ist in C++ allerdings nicht zulässig, hauptsächlich weil referenzen auf const nicht unbedingt direkt gebunden werden (also temporaries erzeugen) und so ein schlupfloch entstehen würde.

in diesem konkreten fall habe ich allerdings sowieso zweifel, dass eine klassenhierarchie überhaupt zweckmäßig ist. für binäre operation bräuchte man doch dem grunde nach eine double-dispatch methode, sofern nicht immer beide operanden vom selben typ sein sollen. virtuelle funktionen helfen hier nicht unbedingt weiter und double-dispatch lässt sich auch gut ohne vererbung implementieren.

[picocat]

Lars Hupel schrieb:

Datentyp
|- Skalar
   |- natürliche Zahl
   |- ganze Zahl
   |- rationale Zahl etc.
|- Geometrie etc.

Das könnte besser klappen. Dann könnte man Operationen wie folgt definieren:

Exact operator + (const Exact& first,const Fraction& second);
Fraction operator - (const Fraction& first,int second);
// etc.

camper schrieb:

in diesem konkreten fall habe ich allerdings sowieso zweifel, dass eine klassenhierarchie überhaupt zweckmäßig ist. für binäre operation bräuchte man doch dem grunde nach eine double-dispatch methode, sofern nicht immer beide operanden vom selben typ sein sollen. virtuelle funktionen helfen hier nicht unbedingt weiter und double-dispatch lässt sich auch gut ohne vererbung implementieren.

Worum handelt es sich bei double-dispatch und LSP?

[camper]

LSP = Liskovsches Substitutionsprinzip, einfach mal googlen

virtuelle funktionen sind eine form von single-dispatch: der konkrete funktion, die aufgerufen wird, hängt vom dynamischen typ eines parameters (des impliziten objekt parameters) ab. dem gegenüber wählt double-dispatch die aufzurufende funktion anhand des dynamischen typs zweier parameter aus (es macht einen unterschied, ob ich zwei integer, ein integer und eine rationale zahl oder zwei rationale zahlen addiere) - die brutalstmöglich einfache methode, das zu erreichen, sind dynamic_cast orgien...

wenn ich das problem richtig verstehe, ist der 'zahlentyp' in einem solchen intepreter grundsätzlich eine dynamische angelegenheit. man könnte sich auch leicht operationen vorstellen, die den 'typ' einer variablen ändern. möglicherweise würde ein single-element container (boost::any kommt in den sinn) Scalar, der dann jeweils zu einem zeitpunkt einen wert eines zahlentyps enthält, dienlich sein. selbstverständlich könnten dann immer noch alle zahlentyp von etwas abstrakteren abgeleitet sein - das wäre dann aber eher ein implementationsdetail, und nicht teil des interfaces von Scalar.

[picocat]

Sorry dass ich erst jetzt schreibe. Habe nicht immer Internet verfügbar.

Also LSP weiß ich jetzt was das ist.

Also ehrlich gesagt habe ich keine Lust auf dynamic_cast, was ja wohl auch verständlich ist. Ich finde solchen Code nicht so elegant

Jetzt ist das Problem, wie eine elegante Lösung aussieht. Um mein Problem noch einmal klar zu umreißen:

• Einmal im Skript deklariert, soll der Datentyp einer Variable fest bleiben. Jedoch soll der Datentyp automatisch erkannt werden bzw. ggf. explizit angegeben werden.
• Eine Basisklasse ist wichtig, da ich vorhabe, eine Symboltabelle à la "std::mapstd::string,Scalar* zu erstellen. Mehrere Symboltabellen wären zwar einfacher, aber durchaus lästig und unelegant.
• Ganz wichtig: Die einzelnen Typen haben verschiedene Wertigkeiten. Das heißt, eine reelle Zahl z. B. 1, rationale Zahl 2, ganze Zahl 3 etc. Wenn eine Operation auf Operanden angewandt wird, so soll das Ergebnis die Wertigkeit des jenigen Operanden übernehmen, der die kleinere Wertigkeitszahl hat. Bsp: $x \in \mathbb{R}; y \in \mathbb{N}; x + y = z; z \in \mathbb{R}$
• Ich gebe zu, ich bin faul, also möchte ich mir gerne explizite Casts und enums (so was wie SCALAR_R, SCALAR_Q, SCALAR_N etc.) ersparen.

Wenn ich jetzt meinen Ansatz mal auf folgendes Minimalbeispiel reduziere:

class Scalar
{
  public:
    virtual Scalar& add(const Scalar& other);
};

class Fraction : public Scalar
{
  public:
    virtual Fraction& add(const Fraction& other);
    virtual Fraction& add(const UInteger& other);
    virtual Fraction& add(const Integer& other);
};

Wie kriege ich (elegant ) den Compiler dazu, dass er das so kompiliert, wie ich will Also ich meine, dass bei folgendem Snippet

Fraction f;
Scalar& s = f;
s.add(f);

Fraction::add und nicht Scalar::add aufgerufen wird. Wie geht das? Muss ich vielleicht meinen Ansatz komplett umstrukturieren

[picocat]

push

[Rich2403]

Oja, das selbe Problem hab ich auch... Hat den keiner eine Lösung?

Danke