Interpreter implementieren: Typensystem

Konrad Rudolph

Hi Dr. P.,

so langsam freunde ich mich damit an. Wobei ich es wohl eher so machen werde, dass 'QuotedExpression' nicht eine Expression enthält sondern eine List, und zusammen mit 'String' von einer Klasse 'Sequence' abgeleitet wird. Gut, damit ich solche Änderungen machen kann, muss ich das Projekt jetzt aber erstmal auf eine Versionskontrolle umstellen.

phlox81

Konrad Rudolph schrieb:

phlox, ich glaube Du verstehst das Interpreter-Entwurfsmuster nicht. Die von Dir vorgeschlagene Vererbungshierarchie würde einfach nicht funktionieren. Der Witz ist ja gerade, dass sich einfach jedes Wisp-Programm als 'Expression'-Objekt auffassen lässt und ich kann 'Eval' darauf ausführen. Und je nachdem, wie das Programm konktet aussieht, wird es dann korrekt evaluiert, weil die verschiedenen Sprachkomponenten eben wissen, wie sie selbst evaluiert werden müssen.

Ja mag sein das ich das Interpretermuster nicht unbedingt verinnerlicht habe Oder einfach da was mit dem Value verwechsle.
Trotzdem bin ich der meinung das es einen Unterschied macht, ob du nun eine Expression oder eine SingleExpression/AtomExpression hast, und ich der Meinung bin, das für es Sinnvoller währe die Expression von SingleExpression oder einer Basisklasse ExpressionBase abzuleiten, anstatt Atom von nicht-ATomic basisklassen abzuleiten.
Wobei ich hier davon ausgehe, das es Unterschiede im Interface dieser Klassen geben könnte, wenn da nur eine Eval Methode ist, ist das natürlich wurscht.

phlox

Konrad Rudolph

So, vielen Dank nochmal an alle. Die Umstellung ist jetzt wie von Doktor Prokt vorgeschlagen erfolgt und es funktioniert genauso wie vorher, nur dass ich weniger Klassen brauche.

Auch wenn dein Problem gelöst scheint, hier noch einmal ein paar Anmerkungen:

Ich mag durchaus falsch liegen, kann mir aber beim besten Willen nicht vorstellen dass das Interpreter Pattern allzu geeignet ist einen [L/W]isp-Interpreter zu implementieren.

Mir erschließt sich der Sinn deiner Value-Vererbungslinie nicht ganz so. Selbst wenn du darauf bestehst, erscheint es mir sinnvoller einfach alle Typen die ein Value sein können mit einem entsprechendem Interface auszustatten.

So wie's derzeit in deinem Diagramm abgebildet ist geht's auf jeden Fall nicht:

(let ((odd? (lambda (n) (if (= n 0) #f (not (even? (- n 1))))))
      (even? (lambda (n) (if (= n 0) #t (not (odd? (- n 1)))))))
  (if (even? 43) 'even 'oddness))

Apropos quote. Wozu QuotedExpression? Die Klasse würde ich ganz rausschmeißen und dafür schlicht den Parser ein wenig umbauen:

if (Scanner.Lookahead is QuoteChar)
  return new List().append(theQuoteSymbol).append(readList());

Sprich das Apostroph ist nur ein wenig syntactic sugar der 'expr in (quote expr*)* umwandelt.

Mit dem Backtick kannst du ähnlich verfahren.

Wenn du auf Closures nicht verzichten willst, denk dran deinen Lambdas das entsprechende Environment (Context?) mitzugeben.

Bezüglich Literal etc. habe ich eurer Diskussion vielleicht einfach nicht folgen können, wenn du mit Literal allerdings schlicht 'String', 'Bool' und so meinst, quasi alles was in C mit Literal bezeichnet wird, dann
- solltest du Literal besser nicht mit Identifier zusammenfassen,
- ist ein Identifier/Symbol ein Literal und desweiteren
- ist Literal synonym zu Atom.

Konrad Rudolph

'finix schrieb:

Ich mag durchaus falsch liegen, kann mir aber beim besten Willen nicht vorstellen dass das Interpreter Pattern allzu geeignet ist einen [L/W]isp-Interpreter zu implementieren.

Wieso nicht? Der Interpreter läuft eigentlich bereits spitze. Allerdings ist Wisp ≠ Lisp. Ich kann gar kein Lisp (klar, einfache Dinge kann ich lesen und auch verstehen).

Mir erschließt sich der Sinn deiner Value-Vererbungslinie nicht ganz so. Selbst wenn du darauf bestehst, erscheint es mir sinnvoller einfach alle Typen die ein Value sein können mit einem entsprechendem Interface auszustatten.

So wie's derzeit in deinem Diagramm abgebildet ist geht's auf jeden Fall nicht:
(let ((odd? (lambda (n) (if (= n 0) #f (not (even? (- n 1))))))
      (even? (lambda (n) (if (= n 0) #t (not (odd? (- n 1)))))))
  (if (even? 43) 'even 'oddness))

Stimmt, als Interface wär's auch gegangen. Allerdings sehe ich nicht, wo sich Dein Code und mein Klassendiagramm widersprechen. Ich habe zwar noch nicht versucht, eine mutuelle Rekursion zu implementieren (ich teste das morgen mal, jetzt habe ich leider keine Zeit mehr), aber prinzipiell sollte das klappen.

Apropos quote. Wozu QuotedExpression? Die Klasse würde ich ganz rausschmeißen und dafür schlicht den Parser ein wenig umbauen:
if (Scanner.Lookahead is QuoteChar)
  return new List().append(theQuoteSymbol).append(readList());
Sprich das Apostroph ist nur ein wenig syntactic sugar der 'expr in (quote expr*)* umwandelt.

Hmm, Mist. Daran habe ich gar nicht gedacht. Ursprünglich wäre das in meinen Gedanken auch gar nicht gegangen, weil die Argumente vor Aufruf einer Funktion evaluiert wurden. Das ist jetzt allerdings nicht mehr überall so (ich unterscheide zwischen Macros, welche ihre Argumente nicht evaluieren und keinen eigenen Ausführungskontext erzeugen und Funktionen, welche beides tun).

Mit dem Backtick kannst du ähnlich verfahren.

Welchen Backticks?

Wenn du auf Closures nicht verzichten willst, denk dran deinen Lambdas das entsprechende Environment (Context?) mitzugeben.

Ja, erfolgt sowieso.

Bezüglich Literal etc. habe ich eurer Diskussion vielleicht einfach nicht folgen können, wenn du mit Literal allerdings schlicht 'String', 'Bool' und so meinst, quasi alles was in C mit Literal bezeichnet wird, dann
- solltest du Literal besser nicht mit Identifier zusammenfassen,
- ist ein Identifier/Symbol ein Literal und desweiteren
- ist Literal synonym zu Atom.

Ja. 'Literal' habe ich inzwischen vollkommen rausgeschmissen.

Konrad Rudolph schrieb:

[Interpreter Pattern]

Wieso nicht? Der Interpreter läuft eigentlich bereits spitze. Allerdings ist Wisp ≠ Lisp. Ich kann gar kein Lisp (klar, einfache Dinge kann ich lesen und auch verstehen).

War lediglich 'ne ad hoc Intuition. Kann, wie gesagt, auch komplett falsch liegen.

Hat auch nichts speziell mit Lisp oder so zu tun. Ich stelle mir bloß vor dass das Interpreter Pattern bei dieser Komplexität keinerlei Vorteile bringt, die Sache eher noch verkompliziert. Und natürlich die Fixierung auf direkte Interpretation des AST.

Konrad Rudolph schrieb:

Stimmt, als Interface wär's auch gegangen. Allerdings sehe ich nicht, wo sich Dein Code und mein Klassendiagramm widersprechen. Ich habe zwar noch nicht versucht, eine mutuelle Rekursion zu implementieren (ich teste das morgen mal, jetzt habe ich leider keine Zeit mehr), aber prinzipiell sollte das klappen.

Ungeschicktes Beispiel meinerseits, konnte's als Unreg leider nicht editieren. Ich meinte eigentlich bloß dass dir ein SymbolValue fehlt.

Btw, wie hast du denn deine Funktionsaufrufe implementiert? Mutuelle Rekursion sollte doch eigentlich kein Problem darstellen.

Konrad Rudolph schrieb:

Hmm, Mist. Daran habe ich gar nicht gedacht. Ursprünglich wäre das in meinen Gedanken auch gar nicht gegangen, weil die Argumente vor Aufruf einer Funktion evaluiert wurden.

Ich dachte das wäre klar - der ganze Sinn von quote ist ja das die Argumente nicht evaluiert werden. Mir ging's nur darum dass ' eigentlich nichts besonderes ist, oder sein muss.

Wisp>(car ''foo)
quote

Konrad Rudolph schrieb:

Das ist jetzt allerdings nicht mehr überall so (ich unterscheide zwischen Macros, welche ihre Argumente nicht evaluieren und keinen eigenen Ausführungskontext erzeugen und Funktionen, welche beides tun).

Weise Entscheidung Denk dran dass es neben quote und Makros noch ein paar weitere SpecialForms wie z.B. if gibt.

Konrad Rudolph schrieb:

Mit dem Backtick kannst du ähnlich verfahren.

Welchen Backticks?

Den Backticks für backquote/quasiquote.

Konrad Rudolph schrieb:

Wenn du auf Closures nicht verzichten willst, denk dran deinen Lambdas das entsprechende Environment (Context?) mitzugeben.

Ja, erfolgt sowieso.

Wusste nicht ob es in deinem Diagramm nur ausgeblendet war, oder du nicht dran gedacht hast oder so.

Konrad Rudolph

'finix schrieb:

Hat auch nichts speziell mit Lisp oder so zu tun. Ich stelle mir bloß vor dass das Interpreter Pattern bei dieser Komplexität keinerlei Vorteile bringt, die Sache eher noch verkompliziert. Und natürlich die Fixierung auf direkte Interpretation des AST.

Ach, so kompliziert ist das gar nicht. Ob es effizient ist, ist natürlich nochmal ne ganz andere Frage, darum mache ich mir dann später Gedanken.

Außerdem, was wäre denn eine (einfachere) Alternative? Enweder ich müsste das ganze in eine Bytecodeform übertragen und einen Interpreter für diesen Bytecode schreiben oder ich kompiliere das ganze in eine existierende Sprache. Auch nicht unbedingt einfacher. Die wohl einfachste Möglichkeit wäre, das ganze per 'System.Linq.Expression' in .NET-Lambdas zu überführen, zu kompilieren und auszuführen. Aber genau diesen Part wollte ich ja mal selbst bauen.

Evtl. hänge ich da irgendwann mal einen 'Compile'-Interpreter ran, der genau das macht, und vergleiche dann die Resultate.

Zum Glück ist das ganze auch eher akademisch, sodass nicht das Überleben von Ariane-Raketen von der Effizienz meines Interpreters abhängt.

Ungeschicktes Beispiel meinerseits, konnte's als Unreg leider nicht editieren. Ich meinte eigentlich bloß dass dir ein SymbolValue fehlt.

Du meinst sowas wie '#t' und '#f'? Ja, wie gesagt, Wisp ist nicht Lisp.

Btw, wie hast du denn deine Funktionsaufrufe implementiert? Mutuelle Rekursion sollte doch eigentlich kein Problem darstellen.

Tut sie auch nicht. Im Moment kopiere ich für den Funktionsaufruf einfach den aktuellen Kontext, rufe für jeden Parameter eine 'RebindArgument'-Methode auf und gut is'. Das ganze ist zwar ebenfalls nicht besonders effizient aber sollte sich das als kritisch herausstellen, kann man das ganze lokal anpassen.

Konrad Rudolph schrieb:

Denk dran dass es neben quote und Makros noch ein paar weitere SpecialForms wie z.B. if gibt.

Wieso sollte man 'if' nicht als Makro implementieren? Bei mir sieht die aktuelle Implementierung so aus:

[Macro("if", NumberOfArguments = 3)]
public static Value MacroIf(Context context, IEnumerable<Expression> arguments) {
    var cond = arguments.First().Eval(context) as Bool;
    var true_part = arguments.Skip(1).First();
    var false_part = arguments.Last();

    if (cond == null)
        throw new InvalidOperationException("Invalid type. List must yield boolean value.");

    return (cond is True ? true_part : false_part).Eval(context);
}

Konrad Rudolph schrieb:

Ungeschicktes Beispiel meinerseits, konnte's als Unreg leider nicht editieren. Ich meinte eigentlich bloß dass dir ein SymbolValue fehlt.

Du meinst sowas wie '#t' und '#f'? Ja, wie gesagt, Wisp ist nicht Lisp.

Nein, mit Symbol meine ich das was bei dir unter Identifier läuft.
(Und wenn ich nicht weiß wie Wisp genau aussehen soll halte ich mich "an Lisp angelehnt" - ist ja auch nicht schlimm, denke ich.)

Konrad Rudolph schrieb:

Im Moment kopiere ich für den Funktionsaufruf einfach den aktuellen Kontext, rufe für jeden Parameter eine 'RebindArgument'-Methode auf und gut is'.

Da musst du eigentlich nichts kopieren. Gib deinem Context einfach einen baseContext mit:

Context.GetValue(identifier):
  value = self.symbolTable[identifier]
  return value ? value : self.baseContext.GetValue(identifier)

Lambda.Invoke(args):
  frame = new Context()
  frame.bind(self.parameters, map(Eval, args))
  frame.baseContext = self.context
  currentContext = frame
  return evalBody()

Konrad Rudolph schrieb:

Wieso sollte man 'if' nicht als Makro implementieren? Bei mir sieht die aktuelle Implementierung so aus:

Wenn es möglich ist spricht natürlich nichts dagegen 'if' als Makro zu implementieren. Aber deine aktuelle Implementation sollte sich auch bei deiner Terminologie nicht wirklich Makro nennen, oder?

Konrad Rudolph

'finix schrieb:

Konrad Rudolph schrieb:

Ungeschicktes Beispiel meinerseits, konnte's als Unreg leider nicht editieren. Ich meinte eigentlich bloß dass dir ein SymbolValue fehlt.

Du meinst sowas wie '#t' und '#f'? Ja, wie gesagt, Wisp ist nicht Lisp.

Nein, mit Symbol meine ich das was bei dir unter Identifier läuft.

Ach so. Aber sowas gibt es doch.

(Und wenn ich nicht weiß wie Wisp genau aussehen soll halte ich mich "an Lisp angelehnt" - ist ja auch nicht schlimm, denke ich.)

Ja, ist schon prinzipiell die richtige Annahme.

[Zum Context:]
Da musst du eigentlich nichts kopieren. Gib deinem Context einfach einen baseContext mit:

Ja, das ist natürlich wesentlich besser.

Konrad Rudolph schrieb:

Wieso sollte man 'if' nicht als Makro implementieren? Bei mir sieht die aktuelle Implementierung so aus:

Wenn es möglich ist spricht natürlich nichts dagegen 'if' als Makro zu implementieren. Aber deine aktuelle Implementation sollte sich auch bei deiner Terminologie nicht wirklich Makro nennen, oder?

Hmm, da sehe ich den Einwand jetzt nicht. Ein Macro ist bei mir einfach ein 'Callable', bei dem die Argumente nicht pauschal vor dem Aufruf evaluiert werden, und wo kein neuer Aufrufkontext erstellt worden ist. Innerhalb des Makros kann das natürlich nachgeholt werden.

finix

Konrad Rudolph schrieb:

'finix schrieb:

mit Symbol meine ich das was bei dir unter Identifier läuft.

Ach so. Aber sowas gibt es doch.

Aber nicht als Runtime.Value

Wisp>(def foo 'bar)
Wisp>foo
error: can't print the value of foo

Konrad Rudolph schrieb:

Hmm, da sehe ich den Einwand jetzt nicht. Ein Macro ist bei mir einfach ein 'Callable', bei dem die Argumente nicht pauschal vor dem Aufruf evaluiert werden, und wo kein neuer Aufrufkontext erstellt worden ist. Innerhalb des Makros kann das natürlich nachgeholt werden.

Dein if ist derzeit als SyntaxPrimitive oder BuiltIn, oder wie auch immer du es nennen magst, implementiert. Du kannst es natürlich auch Makro nennen, aber bei aller Liebe zur Neuerfindung deiner eigenen Terminologie, sollte der Begriff IMAO immer noch Codetransformationen vorbehalten sein.

Konrad Rudolph

Hi Finix,

hier sind wir wieder an dem Punkt, dass Code und Daten in Wisp doch etwas Unterschiedliches sind. Weder (let ((foo 'bar)) foo) noch (car ''foo) sind in Wisp definiert.

Eventuell war es ne Fehlentscheidung, das so zu machen, aber die Sprache soll sich (wenn überhaupt) an Programmieranfänger richten, und da empfand ich es als hilfreich, einige Eigenheiten der Konvention zu opfern.

Was die Terminologie betrifft gebe ich Dir recht, das war keine gute Entscheidung. Das werde ich dann wohl umbenennen.

Helium

Nurmal so am rande: hast du dir schonmal die DLR angessehen?

Konrad Rudolph

Helium schrieb:

Nurmal so am rande: hast du dir schonmal die DLR angessehen?

Ja. Ist übrigens ein ziemlich cooles Projekt, falls sich hier noch andere Leute herumtreiben, die sich für sowas interessieren: Einen Blick auf die DLR kann ich nur empfehlen.

Dass mein eigenes System hoffnungslos überflüssig ist, ist mir schon klar. Das ganze ist auch in erster Linie eine Fingerübung für mich. Quasi ein persönliches Forschungspraktikum. Übrigens hat's der Thread hier ganz schön in sich: Solche Diskussionen sind der Grund, aus dem ich überhaupt Foren frequentiere. Man lernt einfach im „Vorbeilesen“ jede Menge.