Offene Fragen bei der Entwicklung einer kleinen Programmiersprache

[Ethon]

Hoi Leute.

Ich mache gerade Fortschritte bei der Entwicklung einer dynamischen Programmiersprache (ich orientiere mich an Python).

Jetzt habe ich folgende Fragen:

1. Ich generiere Code für eine virtuelle Stackmaschiene. Wenn ich etwas weiter bin würde ich gerne zu Übungszwecken einen JIT-Assembler schreiben. Reale Maschinen sind aber äußerst selten Stackmaschinen. Gibt es Algorithmen um Code für eine Stackmaschine effizient in Code für eine Maschine mit Registern ala x86 zu konvertieren?

2. Funktionsaufrufe sind keine Statements sondern Expressions. Wird jetzt

print("Hello, ")
print("World !")

ausgeführt dann gammelt jetzt der Rückgabewert von print() 2x auf dem Stack herum. Was ist die gängige Vorgehensweise um das zu verhindern? Testen ob das Statement in Wirklichkeit ein Ausdruck ist und wenn ja das Ergebnis vom Stack poppen?

3. Beispielscode:

Module1.bla

var foo = 123
var bar = foo + Module2::foo

Module2.bla

var foo = 456
var bar = foo + Module1::foo

Ich schätze mal ich müsste so jeder Funktion eine Referenz auf die Variablen-Map des Moduls mitgeben um soetwas realisieren zu können? Dh. bei einer Variabel-Dereferenzierung wäre die Suchreihenfolge Lokal -> Objekt falls Memberfunktion -> Modul-Lokal -> Global?

Danke und Grüße,
Ethon

[gary1195]

1. Das Stichwort ist Register allocation, so könntest du auch Code für eine VM mit Registern erzeugen. Ich vermute deine VM ist auf einem hohen Abstraktionsniveau mit dynamischer Typisierung, dadurch ist die Codeerzeugung für x86 kompliziert. Optimierten x86 o.ä. code zu erzeugen ist sowiso eine Wissenschaft für sich. Dich interessiert vll GNU lightning (jit-bibliothek) erzeugt nicht den tollsten Code aber fürs Probieren vll nicht schlecht.

2. Wenn ein Ergebnis nicht genutzt wird gibt mehrere Möglichkeiten
2.1 es wird verworfen POP
2.2a es ist ein Fehler Ergebnis müssen immer genutzt werden
2.2b es ist ein Fehler, es sei denn es ist ein Spezieller Wert (zB None), dann wie 2.1 (muss evtl zur Laufzeit geprüft werden)
2.3 du definierst print so, dass es keinen Wert zurückgibt
Dazu Frage: du müsstest doch wissen ob der Teil des ASTs einen Wert zurückgibt und müsstes deshalb entsprechenden Code erzeugen können.

3. bei Symboltabellen werden hier einfach verkettete Listen benutzt (wie du geschrieben hast) zB
Funktion: Lokal->Modul oder Lokal->Modul->Global (mit globaler Umgebung)
Closure: Lokal->Lokal-Erzeuger->Modul-Erzeuger->Global-Erzeuger
Methode(single-dispatch): Lokal->Objekt->Modul->Global

[Ethon]

Danke für deine Antwort.

1. Das Stichwort ist Register allocation, so könntest du auch Code für eine VM mit Registern erzeugen. Ich vermute deine VM ist auf einem hohen Abstraktionsniveau mit dynamischer Typisierung, dadurch ist die Codeerzeugung für x86 kompliziert. Optimierten x86 o.ä. code zu erzeugen ist sowiso eine Wissenschaft für sich. Dich interessiert vll GNU lightning (jit-bibliothek) erzeugt nicht den tollsten Code aber fürs Probieren vll nicht schlecht.

Ist ja nur zum Ausprobieren. Werde das selbst machen bzw. AsmJit verwenden.

Dazu Frage: du müsstest doch wissen ob der Teil des ASTs einen Wert zurückgibt und müsstes deshalb entsprechenden Code erzeugen können.

Naja, es ist theoretisch soetwas möglich:

function foo()
{
    return 1;
}

foo = function() { doNothing(); }

Von daher weiß ich zur Zeit der Codegenerierung relativ wenig darüber.
Auch könnte eine Funktion auf C++-Seite definiert sein, dann habe ich überhaupt keine Information über die Semantiken der Funktion.

3. bei Symboltabellen werden hier einfach verkettete Listen benutzt (wie du geschrieben hast) zB
Funktion: Lokal->Modul oder Lokal->Modul->Global (mit globaler Umgebung)
Closure: Lokal->Lokal-Erzeuger->Modul-Erzeuger->Global-Erzeuger
Methode(single-dispatch): Lokal->Objekt->Modul->Global

Gut, dann passt das ja so.

....

Apropos Return:
Ich habe das return Statement so implementiert dass ich eine Exception mit dem Rückgabewert werfe und das Call-Statement diese Exception fängt und damit den Rückgabewert hat. Ist das eine zu wüste Vergewaltigung des C++-Exceptionsystems?
Afaik wirft Python sogar Exceptions um das Ende einer Iteration zu signalisieren.

[Ethon]

Mal ne andere Frage: Warum verwenden viele Sprachen wie auch C++ ein Semikolon um ein Statement abzuschließen ... das ist doch Prinzip garnicht nötig? Oder wo ist es das?

[pytarius]

Ethon schrieb:

Ich habe das return Statement so implementiert dass ich eine Exception mit dem Rückgabewert werfe und das Call-Statement diese Exception fängt und damit den Rückgabewert hat. Ist das eine zu wüste Vergewaltigung des C++-Exceptionsystems?
Afaik wirft Python sogar Exceptions um das Ende einer Iteration zu signalisieren.

Es kommt drauf an, was man unter Exceptions versteht.
Ausschliesslich als Ausnahmebehandlung: Dann ist das eine Vergewaltigung.
Als besseren/billigeren longjump: Dann ist das ok.

Selbst in C++ wäre es unter Umständen schneller,

try {
  for (auto it=...;; ++it)
    ...
} catch(end_of_iteration) {}

zu schreiben, weil man sich damit die Abfrage it!=end spart.

Du kannst es gerne so machen, aber es ist um einiges einfacher und effizienter, das return wie in C zu implementieren. Und es würde z.B. überhaupt nicht zu C++ passen, das Muster müsste sich in deiner Sprache dann wiederholen um konsistent zu wirken.

Warum verwenden viele Sprachen wie auch C++ ein Semikolon um ein Statement abzuschließen ... das ist doch Prinzip garnicht nötig? Oder wo ist es das?

Doch, selbst "1-1" hat zwei Interpretationen:

1-1;
1; -1;

Jede Sprache hat ein Semikolon. Manche nehmen ";", manche nehmen Whitespaces.

Eine echte Sprache (nicht Assembler, Brainf*ck oder sonstige Spässe), die kein Semikolon benötigt, ist mir nicht bekannt.

[Ethon]

Eine echte Sprache (nicht Assembler, Brainf*ck oder sonstige Spässe), die kein Semikolon benötigt, ist mir nicht bekannt.

Lua zum Bleistift.

pytarius schrieb:

Doch, selbst "1-1" hat zwei Interpretationen:

1-1;
1; -1;

Jede Sprache hat ein Semikolon. Manche nehmen ";", manche nehmen Whitespaces.

Kommt doch darauf an wie die Grammatik definiert ist ... meine Grammatik ist greedy und matcht was geht. So ist aber zb. diese C Grammatik ( http://www.lysator.liu.se/c/ANSI-C-grammar-y.html ) für den Standard auch definiert ...

1; -1; macht ja auch keinen Sinn - sowas muss man doch nicht übersetzen können.
Fällt dir ein sinnvolles Beispiel ein wo solche Doppeldeutigkeiten auftreten können? Mir eben nicht ...

[Ethon]

Kleiner Showoff weil ich auf mein Baby mittlerweile recht stolz bin.

puts = native "puts" from "libc.so" defined (s : "string8") -> "int32"

result = 0
for i in 0..1000
{
    if i % 3 == 0 || i % 5 == 0
        result += i
}

puts(i)

(Bin gerade dabei http://projecteuler.net Probleme zu lösen da ich Probleme habe andere nette Testaufgaben für meine Sprache zu finden - wer welche kennt, bitte her damit!)

Von dem was man sehen kan (ist ja nicht viel): Irgendetwas auszusetzen?

[Gast]

Ethon schrieb:

Von dem was man sehen kan (ist ja nicht viel): Irgendetwas auszusetzen?

Nee, nur interessierte Nachfragen. Wie hast Du das Einbinden der lib realisiert? Und wenn Du magst, kannst Du ja auch mal die Grammatik oder weitere Beispiele zeigen.

[Ethon]

Wie hast Du das Einbinden der lib realisiert?

Primär über libffi. Anhand der Angaben nach "defined" baue ich das ffi_cif zusammen bzw. konvertiere ich die Parameter zurecht.

native "puts" from "libc.so" defined (s : "string8") -> "int32"

ist ein Ausdruck der Objekt vom Typ "native_function" zurückgibt.
Jede Bibliothek ist refcounted, jedes native_function Objekt hat eine Referenz auf das Bibliothekshandle - ich entlade die Bibliothek wenn sie nicht mehr referenziert wird. Danke das ist besser als die Bibliothek im Speicher zu belassen.

Und wenn Du magst, kannst Du ja auch mal die Grammatik oder weitere Beispiele zeigen.

Jetzt wirds peinlich: Ich habe mir keine genaue Grammatik aufgeschrieben.
Ich habe mir die C++-Operatoren-Präzedenzregeln als Vorlage genommen und mir anhand dessen einen Recursive-Descent Parser zusammengeschustert.
Hab halt mit nem Matheparser begonnen und baue seitdem Funktionalität dazu.

Mal sehen ob ich damit auf die Schnauze fliege. Wenn ist es mir aber auch egal, dann kipp ich das Projekt in die Tonne und versuche mich an einem self compiling C-Compiler. :p

[ipsec]

Ethon schrieb:

da ich Probleme habe andere nette Testaufgaben für meine Sprache zu finden - wer welche kennt, bitte her damit!

http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems
Da das Probleme für funktionale Sprachen sind, musst du sie eventuell etwas adaptieren.

Ethon schrieb:

Von dem was man sehen kan (ist ja nicht viel): Irgendetwas auszusetzen?

Auszusetzen nicht direkt. Aber hat deine Sprache irgendwelche Konzepte, die es besonders interessant machen könnten, sie sich anzusehen? Bei dem kurzen Programmstück sehe ich abgesehen von leicht abgewandelter Syntax keine großartigen Unterschiede zu gängigen Skriptsprachen.

[Gast]

@Ethon
Danke für die Antwort.
Kannst Du weitere Beispiele zeigen, vielleicht ein Quicksort?
Welche Sprachelemente hast Du bereits implementiert? Funktionen? Ein Modulsystem? Ist die Sprache Objektorientiert?
Wenn Du mir alles notwendige zukommen lässt, würde ich vielleicht mal ein wenig damit programmieren. Mangels Grammatik bräuchte ich dann aber auch den Quellcode um sie mir aus dem Parser rauszufischen.

[Ethon]

Upps, habe die Antwort jetzt erst gelesen, wurde mir unter den neuen Beiträgen nicht angezeigt.

Ich Idiot habe es versäumt regelmäßige Backups zu machen und der Projektordner ist einer Dummheit zum Opfer gefallen.
Musste mit einem sehr alten Stand weiterarbeiten, was nicht schlecht ist, ich habe ein paar Dinge jetzt anders gemacht, aber Funktionalität ist recht mau.

Funktionen sind implementiert. (Defaultparameter auch, aber keine named Parameter)
Modulsystem steht die Planung.
Objektorientierung is theoretisch dabei, Builtin-Typen wie Integer verhalten sich wie Objekte, allerdings fehlt mir noch jedes Konzept wie nutzerdefinierte Klassen umgesetzt werden sollen. Ich möchte es halt schön hinbekommen.

Eines der Probleme bezüglich Objektorientierung ist dass ich Refcounting und keinen GC verwende. (Und das auch so bleiben soll)
Jetzt muss ich mir halt genau überlegen wie ich zyklische Referenzen lösen kann.

Vermutlich werde ich einfach mal eine dumme struct ala C implementieren die nur ein Container für andere Objekte ist.

Der ganze Krempel ist auf Github oben, wenn Interesse besteht kann ich ja mal nen Link posten.

----

Aus aktuellem Anlass: Wäre es für euch intuitives Verhalten wenn der Ausdruck

5.sqrt == 2

wahr wäre?
Ich nutze jetzt GMP für ints/floats und GMP bietet für Integer standardmäßig nur eine Wurzelfunktion bereit, die den abgeschnitten Integer + Rest zurückgibt.

Bei floats sieht es anders aus, zb. wäre dieser Ausdruck false:

5.float.sqrt == 2

Bin mir halt nicht sicher ob eine implizite Konvertierung nach float sinnvoller wäre als einen abgeschnittenen Integer zurückzugeben.
Meinungen?

[volkard]

Bei 5.sqrt würde ich 2.23 hoffen. Wer den int haben will, kann ja 5.sqrt.int schreiben.

Basic mag ich da. 5/2==2.5 aber 5\2==2.

[8589934592]

Ich habe in dieser Beziehung immer debug (win32) sehr gemocht bzw. die Intellowlevelebene, weil man beim Teilen das Ergebnis im AX Register hat, den Rest im DX Register (und die klassische Registervergrößung mit diesem beiden Registern). Wäre schön, wenn das an Taschenrechner auch könnte, bzw. wenn eine Funktion divmod, die zwei Werte ausspuckt, einfach mal Standard wäre, und nicht getrennt in div und mod oder ungefragt Fließkomma und aufgedrängtes Rundungsverhalten.

Bei Wurzeln gibt es ja immer mehrere Möglichkeiten. Hier fände ich Transparenz gut, und Auswahlmöglichkeiten (auch Anzahl der Nachkommastellen), wie auch eine, Schätzfunktion bzw. -hilfe.
Aber wie wäre es, einfach mehrere Werte auszugeben, den Floatwert und den Integerwert mit Rest, Anzahl der Nachkommastellen und Schätzbereich(e).

Wenn das alles nicht geht, dann würde ich die Funktion selber mit Heron und der FPU machen, also standardmäßig Fließkomma mit maximaler Bitbreite.
Grammatisch finde ich sqrt 5 mit Fließkommaausgabe am sinnvollsten. FP für Wurzeln ist letzlich auch generell intuitiver, weil die FPU für größere Bitbreiten/Zahlen näher liegt.

Aber einen C-Sprachtyp als Vorbild/Orientierung empfinde ich nicht unbedingt als gute Wahl. Auch wenn python eine Menge kann und u.a. Hackers Liebling ist, syntaktisch sollte man sich auch Haskell und Fortran(und Basic) gut anschauen, und auch Lisp und (Entwicklung nach) Closure. Aber nicht nur, Programmiersprachen sind selten isoliert, sondern Anwendungsgebunden, hier kommt es auch immer aufs drumherum an, Compilerauswahl und -Installationsmöglichkeiten, Betriebsysteme, Bibliotheken, Plugins, DesktopundGUI, Community, Weiterpflege usw.

Ansonsten: Zeig mal, (oder probier mal) wie man einfache Sachen angehen kann, wie z.B. Registerwerte manipulieren (für OS Programming), mathematische Funktionen, Kettenbrüche, Analysis, Fakultätsberechnung, Quicksort, Heron-Wurzel (mit Schritt-Liste) und Cäsar-Verschlüsselung oder Konvertierungen zwischen Zahlensystemen (und welche?) eine Bitmap/Farbtabelle für einen Desktop(Betriebsystem) erstellen, oder einen simplen Texteditor o.ä. aber auch wie komplizierte Schleifenverschachtelungen aussehen würden.

(ach so, damit der Stack nicht vollgeschrieben wird, kann man Jumps machen statt calls (mit ret), grundlegende Funktionen zusammenlegen, und je nach Funktionsaufruf den Navigationswert im Speicher zurücksetzen, also die Startadresse bzw. die Speicheradresse(n) vom (wenn sich hier was bewegt) und im Stack.

Auf abstrakterer Ebene hilft die Beschäftigung mit Stackoverflows weiter z.B.
http://en.wikipedia.org/wiki/Stack_overflow )

[Ethon]

volkard schrieb:

Bei 5.sqrt würde ich 2.23 hoffen. Wer den int haben will, kann ja 5.sqrt.int schreiben.

Basic mag ich da. 5/2==2.5 aber 5\2==2.

Macht Sinn, danke.
Die Basic-Syntax gefällt mir nicht. Sehen beide zu ähnlich aus.

Ich habe in dieser Beziehung immer debug (win32) sehr gemocht bzw. die Intellowlevelebene, weil man beim Teilen das Ergebnis im AX Register hat, den Rest im DX Register (und die klassische Registervergrößung mit diesem beiden Registern). Wäre schön, wenn das an Taschenrechner auch könnte, bzw. wenn eine Funktion divmod, die zwei Werte ausspuckt, einfach mal Standard wäre, und nicht getrennt in div und mod oder ungefragt Fließkomma und aufgedrängtes Rundungsverhalten.

Kommt halt bei einer Skriptsprache doof wenn Ergebnisse von grundlegenden Operationen nicht einfach verwendet werden können. Also zb. bei deinem Divisions-Beispiel.
Soetwas könnte man natürlich als Library anbieten aber mein /-Operator darf schon ein float zurückgeben.

Wenn das alles nicht geht, dann würde ich die Funktion selber mit Heron und der FPU machen, also standardmäßig Fließkomma mit maximaler Bitbreite.
Grammatisch finde ich sqrt 5 mit Fließkommaausgabe am sinnvollsten. FP für Wurzeln ist letzlich auch generell intuitiver, weil die FPU für größere Bitbreiten/Zahlen näher liegt.

Bei mir sind Integer/Floats multiple-precision da ich GMP für die Implentierung nutze. Erstmal möchte ich da nicht allzuviel selbst implementieren.

Ansonsten: Zeig mal, (oder probier mal) wie man einfache Sachen angehen kann, wie z.B. Registerwerte manipulieren (für OS Programming), mathematische Funktionen, Kettenbrüche, Analysis, Fakultätsberechnung, Quicksort, Heron-Wurzel (mit Schritt-Liste) und Cäsar-Verschlüsselung oder Konvertierungen zwischen Zahlensystemen (und welche?) eine Bitmap/Farbtabelle für einen Desktop(Betriebsystem) erstellen, oder einen simplen Texteditor o.ä. aber auch wie komplizierte Schleifenverschachtelungen aussehen würden.

Wie gesagt, im Moment steht noch nicht allzuviel.
Low-Level Kram kommt in die Sprache garnicht rein, es ist eben ein dynamisch typisierte Scriptsprache. Im Moment ist es relativ leicht nativen Code zu nutzen (Bindings sind leicht zu schreiben (wenn auch noch nicht komfortabel implementiert) und es gibt eingebauten Support für C-Funktionen in DLLs.)

Faktultät:

x = 1123
fak_of_x = x!

[volkard]

Ethon schrieb:

volkard schrieb:

Bei 5.sqrt würde ich 2.23 hoffen. Wer den int haben will, kann ja 5.sqrt.int schreiben.

Macht Sinn, danke.

Dann beachte aber, daß es (gut, aber nur in der hand des compilerbauers) allen Deiner Verantwortung unterliegt,
5.sqrt.int
und
5.sqrt
was vollkommen verschiedenes machen zu lassen! Erstere Version ist evtl viel schneller.
Kann es möglich sein (besser, in der hand des bibliotheksschreibers!!!!!), daß der Anwender beschreiben kann, daß .sqrt.int vorrangich matcht vor .sqrt ?
Und wäre das überhaupt tragfähig für viele andere Optimierungen oder nur eine Eintagsfliege?

[Sone]

Basic mag ich da. 5/2==2.5 aber 5\2==2.

Diese Syntax ist irritierend.

Kaum zu unterscheiden, wobei Code flink lesbar und verständlich sein soll.
Einen Strich auf verschiedene Seiten zu kippen ist für einen Menschen nicht schnell genug unterscheidbar und kann und wird zu vielen Missverständnissen führen/geführt haben.

Du hast, beiläufig gesprochen, Ethon falsch zitiert.

[volkard]

Sone schrieb:

Basic mag ich da. 5/2==2.5 aber 5\2==2.

Diese Syntax ist irritierend.

Kaum zu unterscheiden, wobei Code flink lesbar und verständlich sein soll.
Einen Strich auf verschiedene Seiten zu kippen ist für einen Menschen nicht schnell genug unterscheidbar und kann und wird zu vielen Missverständnissen führen/geführt haben.

Nö, wenn mans ein wenig gewohnt ist, kein Problem.

Sone schrieb:

Du hast, beiläufig gesprochen, Ethon falsch zitiert.

Hab's nur auf die Nicht-Basic-Sache reduziert. Bin sicher, es war in seinem Sinne.

[Sone]

volkard schrieb:

Nö, wenn mans ein wenig gewohnt ist, kein Problem.

Nun, du wirst es wissen.

Sone schrieb:

Du hast, beiläufig gesprochen, Ethon falsch zitiert.

Hab's nur auf die Nicht-Basic-Sache reduziert. Bin sicher, es war in seinem Sinne.

Oh, ich hätte schwören können, du hast die Basic-Syntax zitiert... nun, ich bin blind.

Wie willst du aber auch die Basic-Syntax auf das Radizieren anwenden?

Bei 5.sqrt würde ich 2.23 hoffen. Wer den int haben will, kann ja 5.sqrt.int schreiben.

Das ist nicht so hübsch wie bei C++, wo man das alles auf das Typsystem reduzieren kann. Hat diese Skriptsprache eigentlich ein statisches Typsystem?

bibliotheksschreibers!!!!!

Was ist denn da so überaus wichtig, dass du es mit fünf Ausrufezeichen hervorhebst?????

[Ethon]

volkard schrieb:

Ethon schrieb:

volkard schrieb:

Bei 5.sqrt würde ich 2.23 hoffen. Wer den int haben will, kann ja 5.sqrt.int schreiben.

Macht Sinn, danke.

Dann beachte aber, daß es (gut, aber nur in der hand des compilerbauers) allen Deiner Verantwortung unterliegt,
5.sqrt.int
und
5.sqrt
was vollkommen verschiedenes machen zu lassen! Erstere Version ist evtl viel schneller.
Kann es möglich sein (besser, in der hand des bibliotheksschreibers!!!!!), daß der Anwender beschreiben kann, daß .sqrt.int vorrangich matcht vor .sqrt ?
Und wäre das überhaupt tragfähig für viele andere Optimierungen oder nur eine Eintagsfliege?

Naja, das sind ja Properties.

Integer(5).sqrt().int()

wäre es mit Funktionsaufrufen.

Da zu optimieren würde einiges an statischer Analyse verlangen auf die ich schlichtweg wenig lust habe.
Machen die wenigsten Scriptsprachen, also versuchen zu erraten was der Nutzer ausdrücken wollte und dementsprechend optimieren.
Durch die Dynamik ist das auch reichlich schwer.

Da würde ich zb.

(5).trunc_sqrt

bevorzugen.

(Die Zahl muss btw in Klammern da der Parser sonst ein Float-Literal matcht. Hat mich einiges an Verwunderung gekostet )