Programmdesign eines Interpreters

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

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

Danke

picocat

Ich hab das ganze jetzt mal so verändert.

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

class Fraction : public Scalar
{
  public:
    virtual Fraction& add(const Scalar& other)
    {
      if (typeid(other)==typeid(Fraction)) this->add((Fraction&)other);
      if (typeid(other)==typeid(UInteger)) this->add((UInteger&)other);
      if (typeid(other)==typeid(Integer))  this->add((Integer&) other);
    }

    virtual Fraction& add(const Fraction& other);
    virtual Fraction& add(const UInteger& other);
    virtual Fraction& add(const Integer& other);
};

Für wie elegant haltet ihr das?

Was ich allerdings noch nicht verstehe, ist folgendes:

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

class Fraction : public Scalar
{
  public:
    virtual Fraction& add(const Scalar& other)
    {
      this->add(other);
    }

    virtual Fraction& add(const Fraction& other);
    virtual Fraction& add(const UInteger& other);
    virtual Fraction& add(const Integer& other);
};

Eigentlich müsste die vtable zur Laufzeit doch erkennen, dass z. B. add(const Fraction&) aufzurufen ist. Allerdings kommt es zu einer Endlosrekursion.

volkard

Lars Hupel schrieb:

Für wie elegant haltet ihr das?

nö, nicht so. dynamic_cast und typeid sind nur für notfälle da.

das einzige, was du machen musst, ist vorher mit virtuellen funktonen die richtigen statischen funktionen rauszufinden. siehe buch "mehr effektiv c++ programmieren". das ist der code, den du nicht verstanden hattest.

//stufe 0
Scalar* add(const Scalar& a,const Scalar& b)
{
     //leider mit new anlegen, weil du den typ des ergebnisses 
     //ja noch gar nicht kennen tust
     //oder hab ich nen trick übersehen, wie du dafür sorgst, daß alle typen 
     //dieser hiearchie gleich groß sind und mutieren können?

     //beide typen unbekannt. ich mache einen belannt. 
     //durch den virtuel-trick wird der typ von a bekannt gemacht. 
     return a->add(b);
}

class Scalar
{
   public:
    //stufe 1
    virtual Scalar* add(const Scalar& b)=0;
    //stufe 2
    virtual Scalar* add(const Fraction& b)=0;
    virtual Scalar* add(const UInteger& b)=0;
    virtual Scalar* add(const Integer& b)=0;
};

class Fraction : public Scalar
{
  public:
    //stufe 1
    Scalar* add(const Scalar& b)
    { 
     //aha, der typ von a ist bekannt. nur mach ich den von b mit dem 
     //gleichen trick auch bekannt
     b->add(*this);//trick 17. beachte, daß der genaue typ von this bekannt ist
    }

    //stufe 2
    Fraction* add(const Fraction& b);
    Fraction* add(const UInteger& b);
    Fraction* add(const Integer& b);
};

sind bestimmt noch fehler drin, hoffe, es klappt trotzdem bei dir.

picocat

Hallo, danke erstmal. Aber irgendwie verstehe ich deinen Code noch nicht so ganz. Was legst du mit new an? Außerdem funktioniert das nicht so ganz was du da machst. Schließlich heißt es Fraction::add(const Fraction&) und nicht Fraction::add(const Fraction&) const. Das heißt wiederum, dass du für einen const Fraction& nicht add aufrufen kannst, weil diese Funktion nicht konstant ist.

(Möglicherweise haben wir uns missverstanden. add() soll Ersatz für operator += () sein, also die Variable verändern. Ich hab mir das so angewöhnt. Aber vielleicht macht es ja weniger Ärger, wenn es den operator + () ersetzt.)

vllt gehts ja besser wenn add als operator + agiert? dann kannst du es als const machen

picocat

Hallo,

ich hab jetzt mal versucht das ganze zu implementieren. Das funktioniert aber nicht so toll - es gibt Compilerfehler.

Meine "Interpretation":

#include <iostream>

class Fraction;

class Scalar
{
   public:
    //stufe 1
    virtual Scalar& add(const Scalar& b)=0;
    //stufe 2
    virtual Scalar& add(const Fraction& b)=0;
};

//stufe 0
Scalar& add(const Scalar& a,const Scalar& b)
{
     return a.add(b);
}

class Fraction : public Scalar
{
  public:
    //stufe 1
    Scalar& add(const Scalar& b)
    {
     b.add(*this);
    }

    //stufe 2
    Fraction& add(const Fraction& b)
    {
      //code
    }

};

int main()
{
  Fraction f;
}

Die Fehler:

C:\Dokumente und Einstellungen\user\Desktop\Unbenannt1.cpp: In function `Scalar& add(const Scalar&, const Scalar&)':
C:\Dokumente und Einstellungen\user\Desktop\Unbenannt1.cpp:17: error: passing `const Scalar' as `this' argument of `virtual Scalar& Scalar::add(const Scalar&)' discards qualifiers

C:\Dokumente und Einstellungen\user\Desktop\Unbenannt1.cpp: In member function `virtual Scalar& Fraction::add(const Scalar&)':

C:\Dokumente und Einstellungen\user\Desktop\Unbenannt1.cpp:26: error: passing `const Scalar' as `this' argument of `virtual Scalar& Scalar::add(const Fraction&)' discards qualifiers

Ich glaube da fehlen noch ein paar Codestücke in meiner Implementation, richtig? Was meinst du außerdem mit Stufe 0 etc. Und welchen Code hatte ich nicht verstanden? Außerdem brauche ich doch keine statischen Funktionen. Könntest du mir deinen Code bitte etwas näher erläutern?

CStoll

Da steht doch der Fehler genau da - du hast ein const Scalar und willst darauf eine nicht-konstante Methode anwenden. Also entweder du deklarierst die Add()-Methode als konstant (dann darf sie aber nicht mehr ihr this-Objekt ändern) oder du erzeugst dir eine temporäre Variable, auf die du addieren kannst:

Scalar add(const Scalar& a,const Scalar& b)
{
  Scalar tmp=a;
  tmp.add(b);
  return tmp;
}