[Projekt] Type Research Programming Language

Hier könnt ihr euch selbst, eure Homepage, euren Entwicklerstammtisch, Termine oder eure Projekte vorstellen.
Forumsregeln
Bitte Präfixe benutzen. Das Präfix "[Projekt]" bewirkt die Aufnahme von Bildern aus den Beiträgen des Themenerstellers in den Showroom. Alle Bilder aus dem Thema Showroom erscheinen ebenfalls im Showroom auf der Frontpage. Es werden nur Bilder berücksichtigt, die entweder mit dem attachement- oder dem img-BBCode im Beitrag angezeigt werden.

Die Bildersammelfunktion muss manuell ausgeführt werden, die URL dazu und weitere Details zum Showroom sind hier zu finden.

This forum is primarily intended for German-language video game developers. Please don't post promotional information targeted at end users.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

[Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Mein Projekt ist wohl eines der elaboratesten Text Adventures aller Zeiten und, für mich, eines der schwersten Puzzle, mit denen ich mich je befasst habe.
Gewissermaßen zehntausend Teile; alle schwarz.

Vor etwa vier Jahren habe ich angefangen, eine C-ähnliche Sprache zu bauen, weil ich eine Frage zu Programmiersprachen hatte, die keiner ohne dieses Experiment hätte beantworten können.
Tatsächlich hat man dabei relativ schnell gesehen, dass man, wenn man aus den Fehlern vergangener Jahrzehnte lernt, relativ einfach zu einer kompakten und spaßig zu benutzenden Sprache kommt.
Da ich wegen Corona gerade ohnehin nicht viele gute Hobbies habe und ich schon immer wissen wollte, ob ich eine effiziente Sprache ohne GC-Crap bauen kann, in der ein Array trotzdem eine Collection wie jede andere ist, habe ich das Ganze in den letzten Wochen soweit fertig gebaut, dass man es langsam benutzen kann.

Momentan implementierte Features sind:
  • Typen sind Werte, wie alle anderen Werte (ob das geht war die initiale Frage)
  • Statische Typ- und Namensbindung
  • Statisches und dynamisches Typsystem, z.B. Vergleich von Typen
  • Typen sind in der Sprache definiert, z.B. int oder ITable (ich hatte einfach keine Lust, das in C++ zu machen)
  • Templates wie in C++, nur dass sie komplett übersetzt ins binary gehen und man sie von anderen Paketen aus instantiieren kann und es kein fucking ODR gibt (ODR wird vom compiler durchgesetzt, identische Instanzen werden automatisch zusammengefügt)
  • Vererbung auf primitiven Typen und Structs (type), z.B. pointer
  • Dualität zwischen virtuellen Funktionen und ihren Realisierungen (beispiel). Das ist etwas, das ich an so ziemlich jeder verbreiten Programmiersprache wirklich vermisse
  • Method placement realizations. Weil es einfach nicht dasselbe ist, wenn man denselben Code kopiert und hofft, dass die Linkeroptimierung das zusammenfaltet.
  • Forward-flow-single-level-return-type-Inferenz (so ziemlich jedes Beispiel bisher) Die ganzen vars und vals, aber nicht nur das
  • Klassen und Interfaces (beispiel). Interfaces dürfen von Klassen erben und Felder definieren, d.h. deren Existenz versprechen. Und das ganze ohne die teils irren Konsequenzen von Mehrfachvererbung in C++
  • Der VTable pointer wird gesetzt bevor der Konstruktor aufgerufen wird (ffs, warum ist das in C++ anders?)
  • Elaboration order checks (beispiel) Im Prinzip kommen die aus Ada und dienen der Erkennung von zyklischen Abhängigkeiten bei Definitionen von quasi allem. Dadurch kann man sich auch die lästigen Vorwärtsdeklarationen sparen
  • Es gibt nur Expressions; das Resultat eines Blocks ist der letzte Ausdruck (beispiel)
  • In die Sprache eingebaute Tests, für die flexiblere Regeln gelten, als für Funktionen und die Sachen prüfen können, die man mit JUnit nicht prüfen kann (beispiel)
  • Apply/Update z.B. Arrays. Ein bisschen wie der Call-Operator in C++; letztlich ist der Trick aus Scala
  • Block Parameter, z.B. bool (und ja, da kommt exakt derselbe Code raus, wie wenn man das in C++ verwendet)
  • Generalized Binder (beispiel) hier sind cond und die foralls Funktionen, die der Compiler auflöst und inlined, damit man ohne viel tippen trotzdem effizienten Code bekommt
  • Operator overloading und overload resolution (beispiel)
  • Eine Paketverwaltung
Bestimmt habe ich noch ein paar Sachen vergessen, die mir einfach viel zu klar sind.
Wenn man das mal ausprobieren möchte:
Hier gibt's einen Installer, die Standardbibliothek und jede Menge Tests, die derzeit als Sprachspezifikation dienen.
Falls jemand Interesse hat, kann ich auch mal ein paar Tutorials schreiben.
Screenshot at 2021-05-10 17-54-30.png
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Krishty »

Liest sich echt interessant, und beide Daumen hoch dafür, dass die Sprache mit Installer/Standardbibliothek/Pipapo schon so weit ist!
Lord Delvin hat geschrieben: 10.05.2021, 20:12Der VTable pointer wird gesetzt bevor der Konstruktor aufgerufen wird (ffs, warum ist das in C++ anders?)
Wegen RAII. Da du dich noch im K’tor befindest, kann das Objekt nicht fertig konstruiert sein. Nun kannst du dir aussuchen, ob du entweder erst die Daten initialisierst und dafür keine virtuellen Funktionen aufrufen kannst, oder ob du virtuelle Funktionen aufrufen kannst und die damit rechnen müssen, uninitialisierte Daten vorzufinden.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
D-eath
Beiträge: 51
Registriert: 28.08.2009, 19:37
Alter Benutzername: TrunkZ
Echter Name: Thomas

Re: [Projekt] Type Research Programming Language

Beitrag von D-eath »

Tolle Arbeit.
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von xq »

Coole Sache! Programmiersprachen basteln ist ein toller Zeitvertreib, man hat immer was zu tun und lernt auch noch was
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Krishty hat geschrieben: 10.05.2021, 20:23 Liest sich echt interessant, und beide Daumen hoch dafür, dass die Sprache mit Installer/Standardbibliothek/Pipapo schon so weit ist!
Lord Delvin hat geschrieben: 10.05.2021, 20:12Der VTable pointer wird gesetzt bevor der Konstruktor aufgerufen wird (ffs, warum ist das in C++ anders?)
Wegen RAII. Da du dich noch im K’tor befindest, kann das Objekt nicht fertig konstruiert sein. Nun kannst du dir aussuchen, ob du entweder erst die Daten initialisierst und dafür keine virtuellen Funktionen aufrufen kannst, oder ob du virtuelle Funktionen aufrufen kannst und die damit rechnen müssen, uninitialisierte Daten vorzufinden.
Dessen bin ich mir bewusst. Das Problem ist nur, dass es dich manchmal zwingt, ziemlich seltsamen Code zu produzieren.
Ist ein Tradeoff und mit dem Forschungsprojekt bin ich fast immer auf der Seite "der Nutzer kann entscheiden".
Wenn ich noch für Forschung bezahlt werden würde, würde ich einen Checker dafür bauen. Du kannst ja abschätzen, ob es zu dem Zeitpunkt Zugriffe auf nicht initialisierte Werte gibt und eine Warnung ausgeben. Valgrind hilft dir da auch weiter. Beides wäre zu Zeiten, als man das für C++ entscheiden musste nicht möglich gewesen.
xq hat geschrieben: 11.05.2021, 14:58 Coole Sache! Programmiersprachen basteln ist ein toller Zeitvertreib, man hat immer was zu tun und lernt auch noch was
Das stimmt. Und Teile der Muster kannst du in anderen Sprachen per Konvention nachbauen und bekommst so zumindest einen Teil des Vorteils.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Krishty »

Lord Delvin hat geschrieben: 11.05.2021, 17:01Wenn ich noch für Forschung bezahlt werden würde, würde ich einen Checker dafür bauen. Du kannst ja abschätzen, ob es zu dem Zeitpunkt Zugriffe auf nicht initialisierte Werte gibt und eine Warnung ausgeben. Valgrind hilft dir da auch weiter. Beides wäre zu Zeiten, als man das für C++ entscheiden musste nicht möglich gewesen.
Halteproblem? Du weißt nicht, ob eine abgeleitete Funktion die Daten irgendwann noch initialisiert oder nicht? Aber du hast schon recht, Platz nach oben ist da mächtig viel.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Nein, so war das nicht gemeint. Man produziert eine Warnung, wenn es so sein *könnte*. Das kann man relativ effizient entscheiden und mit einer lokalen Analyse bis zu den fraglichen calls bekommt man da auch genug Präzision hin, um da rechtfertigbare Warnungen zu produzieren. Wenn man schon anfängt Funktionen in halbkonstruierten Objekten aufzurufen, dann muss man auch mit der Warnung leben, wenn man nicht beweisen kann, dass es kein Problem ist. Aka wenn es nicht völlig offensichtlich harmlos ist. Und das ganze halt richtig machen und nur bei Reads warnen und nicht bei Writes; aber das ist denke ich klar. Das ist für ein Hobby aber zu viel Aufwand; insbesondere weil mich vor allem die Typtheorie dahinter interessiert und für die ist es komplett egal.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Code: Alles auswählen

type Buffer := container.ArrayBuffer[int]

type T {

  type val left = new Buffer(20);
  type val right = new Buffer(20);

  test "copy" {
    left.clear()
    right.clear()
    var i = 0
    while(++i <= 20)
      right += i
    right.foreach i do (left += i)

    left.size() == 20U && right.size() == 20U &&
      right.forall i do (left.exists j do (i == j))
  }
}
Fehlt eigentlich nur noch das C-API und man könnte mal was größeres mit bauen.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Code: Alles auswählen

test "count" {
  2 == "two white spaces".bytes().count c do (
    c == 0x20i8
  )
}
Funktioniert zwar, erzeugt aber leider nach Optimierungen noch Code, weil opt nicht herausfinden kann, dass es sich um einen Iterator über konstante und bekannte Bytes handelt.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Explicit override & method slot placement.
Ist zugegenermaßen ein relativ seltenes Problem, aber dann nur sehr schmerzhaft und ggf. massiven Performanceeinbußen zu lösen.
Ein bisschen wie ein Amphibienauto, bei dem man entscheiden kann, ob beide Sichten einen eigenen Motor oder denselben Motor haben.

Durch die Placement-Realiesierung entsteht auch kein neuer Code. Es wird einfach die entsprechende Funktion in die VTable bzw. ITable eingetragen.
Wenn man die Lösung kennt, kann man erahnen, warum das in Java nicht geht :)

Hier noch mein Testfall zur Illustration:

Code: Alles auswählen

/**
 * Test explicit override with multiple arguments.
 */
interface I {
  def fun (x : T) : int = 1
}
interface J <: I {
  def fun (x : I) : int = 2
}

class S {
  def fun (x : T) : int = 3
}

class T <: S, I, J {

  override [S.fun]
  def fun(x : T) := S.fun;

  // a second override of a function that would be folded into the one above
  // requires explicit this
  override [I.fun]
  type def fun(this : J, x : I) := J.fun;

  test "call T" <: noCompile {
    var x = new T

    // note: out of duality, we will get an overload resolution error here
    val r = x.fun(x)
    delete x
    3 == r
  }
  test "call S" {
    var t = new T
    var x : S = t

    val r = x.fun(t)
    delete x
    3 == r
  }
  test "call I" {
    var t = new T
    var x : I = t

    val r = x.fun(t)
    delete x
    2 == r
  }
  test "call J" {
    var t = new T
    var x : J = t

    val r = x.fun(t)
    delete x
    2 == r
  }
}
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Wenn dir nach über vier Jahren auffällt, dass deine Semikoloninferenz total dämlich ist, weil es innerhalb von runden Klammern nur eine Expression geben kann...naja hab's gefixt. Jetzt geht das so: https://github.com/tyr-lang/test.confor ... ce/mar.tyr

Am Ende grob 20 Zeilen Code und vielleicht eine Stunde Arbeit, das wirklich richtig zu machen. Würde mich nicht wundern, wenn ich jetzt nicht tatsächlich sogar dieselben Regeln hätte wie Scala.
Je mehr ich mich damit auseinandersetze, umso mehr wundert es mich, dass es noch Sprachen ohne gibt.

Edit: Und direkt noch dabei gelernt, dass ich mir damit vor Jahren mal eine etwas obskure Mehrdeutigkeit eingekauft habe. Den letzten Satz nehme ich trotzdem nicht zurück :)
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Jonathan »

Lord Delvin hat geschrieben: 14.10.2021, 20:43 Je mehr ich mich damit auseinandersetze, umso mehr wundert es mich, dass es noch Sprachen ohne gibt.
Magst du das erläutern? Also, ohne groß darüber nachgedacht zu haben, ist es nützlich Ausdrücke mit Semikola abzuschließen, weil man so beim Parsen leichter erkennen kann, wann der eine aufhört und der andere anfängt, insbesondere wenn man kein fixes "1 Ausdruck = eine Zeile" haben will.
Aber gibt es darüber hinaus jetzt noch weitere, überraschende Erkenntnisse, weshalb ein explizites Abschließen von Ausdrücken toll ist? Aus der Anwendersicht sehe ich den Vorteil nicht wirklich, in Python etwa muss man eben mehrzeilige Ausdrücke klammern und man darf vermutlich nicht zwei in eine Zeile schreiben, was aber eh vermutlich als unsauberer Code verboten werden sollte. Also wird dadurch am Ende bloß der Parser simpler, robuster und schneller? (was ja z.B. bei C++ kein soo tolles Argument wäre, schließlich gibt es glaube ich weniger Sprachen die schlimmer zu parsen sind als C++, da hilft dann ein Semikolon auch nicht mehr so viel).
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Also der Parser wird dadurch erstmal eine ganze Ecke langsamer und viel komplexer, was aber relativ egal ist, weil der Parser selbst nur einen winzigen Bruchteil der Laufzeit bei compilierten Sprachen verbraucht und in aller Regel generiert oder gekauft ist :)

Nein es geht mir im Prinzip darum, dass du faktisch, wenn du im Team arbeitest, deinen Code sowieso einheitlich formatieren musst.
Das bedeutet, dass du eigentlich ein Statement pro Zeile hast.
Mehrere Statements pro Zeile hat man extrem selten.
Mehrere Zeilen pro Statement vor allem dann, wenn sie relativ komplex werden, z.B. wenn du eine Lambda-Expression oder sowas hast.
Da ist es dann aber auch nicht schlimm im Zweifel eine runde Klammer zu verwenden.

Wenn du die Semikolon-Separierung jetzt optional durch ein Zeilenende realisierst, hast du das Problem, dass du Mehrdeutigkeiten bekommst, die du irgendwie bearbeiten musst.
Die für mich tatsächlich etwas überraschende Einsicht ist, dass da überwiegend das passiert, was man ohnehin erwartet.
Das ist jetzt für mich natürlich etwas einfacher, weil die Mehrheit meiner Mehrdeutigkeiten entweder völlig üblich sind (if then if then else?) oder eben daher kommen.

Wenn die Sprachsyntax halbwegs sauber ist, dann ist Semikolon-Inferenz komplett orthogonal zu quasi allem anderen in der Sprache.

Ich denke, was mir auch erst gestern Abend so richtig klar geworden ist, ist dass die Regeln die ich jetzt habe, im Prinzip auch mit einem normalen LL-Parser realisierbar wären, wenn man die Regeln für transparente Tokens etwas anpassen würde. Das sind aber Details und es macht am Ende keinen Sinn das auch so zu implementieren, weil du am Ende sowieso immer Java- oder C++-Code generierst und den dann ausführst. Dem ist egal ob da jetzt noch ein Funktionsaufruf drin steckt, der eigentlich nicht in die Sprachklasse passt.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Krishty »

Lord Delvin hat geschrieben: 15.10.2021, 17:25Also der Parser wird dadurch erstmal eine ganze Ecke langsamer und viel komplexer, was aber relativ egal ist, weil der Parser selbst nur einen winzigen Bruchteil der Laufzeit bei compilierten Sprachen verbraucht und in aller Regel generiert oder gekauft ist :)
Höh?! Ohne Whole Program Optimization ist das genau gegenteilig meiner Erfahrung – hier bspw. ein Post von Aras Pranckevičius:
Bild

Der lange grüne Balken in der Mitte war ein Bug, aber auch ohne den ist das alles andere als „winzig“. Grund ist AFAIK, dass Parsing immer auf maximal ein Byte Fortschritt pro Takt limitiert ist, sofern man nicht zu krassen SIMD-Maßnahmen greift, die sich auch nicht durch Lex/Yacc o. ä. Parser-Generatoren nutzen lassen.

Just sayin
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Helmut »

Deine Zeitleiste zeigt einen Compilerlauf von C++. Und in C++ kann man das Parsen nicht von dem anderen Kram trennen, den der Compiler sonst machen muss (Typechecking, Templateinstanziierung Overloadresolution), weil die Sprache historisch gewachsen ist. In praktisch allen anderen typisierten Sprachen trennt man das Parsen von dem Rest, und dann macht das Parsen tatsächlich nur einen Bruchteil der Zeit aus.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Krishty »

Hey Helmut, lange nicht gesehen!

Hast du Quellen? Ich schraube wegen was anderem an Parsern und laufe da mit der Performance ständig gegen eine Wand.

Was ich sonst noch finde, sind JavaScript (ein Viertel in einem Google-Symbolbild) und weitaus optimistischer Scala (0.5 % der Kompilierzeit eines großen Projekts; scheint aber auch stark optimiert zu bauen). Ich erinnere mich aber auch an irgend ein Statement des LLVM-Teams, das zu einer Sprache (war es Go?) meinte: Der andere Compiler ist so viel schneller als wir, weil er Parsen und Kompilieren nicht so trennen muss wie wir, denn LLVM muss ja halbwegs generisch bleiben.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Ok, um das etwas zu präzisieren:
Ich würde mit Whole Program Optimization rechnen.
Im IDE-Modus würde ich tatsächlich sogar noch teure Analysen sehen, die man vielleicht nicht immer mitrechnet.

JavaScript finde ich als vergleich etwas schwierig; meine Erfahrung ist da, dass der eigentlich Transport, sprich Download, des Codes eher das Problem ist. Da würde ich jetzt aber nicht so sehr in die Debatte einsteigen, weil es mit sehr vielen Annahmen verbunden ist und für mich ehrlich gesagt keine Rolle spielt. Bei JIT-Sprachen muss man die JIT-Zeit auch sauber einrechnen, was relativ schwierig ist, weil die nicht konstant ist.

Wenn du eine Sprache hast, die du ohne semantische Analyse gar nicht parsen kannst, dann ist meine Aussage mit Vorsicht zu genießen.
Da kann es einem auch passieren, dass man ohnehin nichts mehr Richtung Semikoloninferenz einbauen kann.
In dem Fall ist es aber auch schwer seriös Zeit auf einzelne Phasen im Front-End zuzuteilen.

Obwohl Tyr zwar eher wie Scala ist, könnte ich eine vergleichbare Aufstellung nicht machen, weil sich bei mir mehrere Phasen überlagern.
Wenn es dich wirklich interessiert könnte ich ein paar Timer einbauen und schauen, wie die Verteilung bei mir für getrennte Phasen aussieht.
Parsen ist getrennt.
Ich würde erwarten, dass ich selbst bei den relativ kleinen Programmen meiner Sprachtestsuite schon den wesentlichen Teil mit Typisierung/Overloadresolution/Templateinstantiierung zubringe. Vielleicht kann man's über den Profiler trennen.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Also ich habe jetzt einfach mal den Profiler bei der Testsuite-Ausführung mitlaufen lassen:
Parser+AST: 15,2s (236 calls)
Sem. Analyse: 37,7s (217 calls)
Codegen: 9,7s (496 calls (aus 141 überlebenden Programmen))

Codegen ist ohne jede Optimierung und die Zeiten sind alle auf dem Mainthread, d.h. ohne AST- und IR-Serialisierung.
Die Unterschiede zwischen Parser und Analyse calls kommen aus Abbrüchen in fail-Tests.
Bei Codegen hat man einen Call pro Test (bei grob 4 Tests/Programm in der Testsuite).

Alles, was ich momentan auf der Roadmap habe, wird das Verhältnis weiter Richtung mehr Kosten in hinteren Phasen verschieben.

Wie sich das bei größeren Programmen verschieben würde, ist seriös kaum zu sagen. Das größte bis jetzt ist unter 2kLoC. Das ist einfach keine Grundlage :)

EDIT: Wenn ich so drüber nachdenke, stammen die Zahlen für C++ in meinem Kopf aus Programmanalysewerkzeugen. Das ist natürlich nur bedingt repräsentativ, wenn die ausgeführten Analysen die Kosten von LTO deutlich übersteigen, weil das die meisten Menschen in der Praxis so nicht hätten.

EDIT 2: Hab's nochmal laufen lassen; der Parser selbst sind etwa 10s.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Helmut »

Krishty hat geschrieben: 16.10.2021, 13:25 Hey Helmut, lange nicht gesehen!

Hast du Quellen? Ich schraube wegen was anderem an Parsern und laufe da mit der Performance ständig gegen eine Wand.

Was ich sonst noch finde, sind JavaScript (ein Viertel in einem Google-Symbolbild) und weitaus optimistischer Scala (0.5 % der Kompilierzeit eines großen Projekts; scheint aber auch stark optimiert zu bauen). Ich erinnere mich aber auch an irgend ein Statement des LLVM-Teams, das zu einer Sprache (war es Go?) meinte: Der andere Compiler ist so viel schneller als wir, weil er Parsen und Kompilieren nicht so trennen muss wie wir, denn LLVM muss ja halbwegs generisch bleiben.
Hi Krishty!
ja, hin und wieder schaue ich noch vorbei :)
Mit dem Scala Link lieferst du ja selber eine Quelle ;) Ansonsten ist hier noch eine Messung von Rust: https://www.reddit.com/r/rust/comments/ ... ling_tool/. Es streamt auch Jonathan Blow beim Profilen seiner Sprache Jai hin und wieder seinen Fortschritt. Auch da sieht man, dass das Parsen zeitlich praktisch irrelevant ist, allerdings habe ich da jetzt keinen Link gefunden.
Der Link mit JavaScript ist, wie auch schon gesagt wurde, nicht wirklich vergleichbar, weil es eine interpretierte und nicht typisierte Sprache ist.
Mich wundert es ein bisschen, dass du da so skeptisch bist. Hast du hier nicht mal einen Meshimporter vorgestellt, der Dateien im Textformat extrem schnell laden kann?

@Lord Delvin
Verstehe ich das richtig, dass du für 2k LOC mehr als 10s zum Parsen benötigst?
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Krishty »

Helmut hat geschrieben: 16.10.2021, 22:45Mich wundert es ein bisschen, dass du da so skeptisch bist. Hast du hier nicht mal einen Meshimporter vorgestellt, der Dateien im Textformat extrem schnell laden kann?
Ja; STL und VRML 2.0; demnächst noch ein paar andere. Tatsächlich ist der Parser dabei der limitierende Faktor; bis hin zu dem Punkt, dass das Inlining meiner isspace()-Version über fast zehn Prozent Leistung entscheidet. Oder dass es sich lohnt, auf einen spezialisierten Parser umzuschalten, wenn die Datei Leerzeichen statt Tabs zur Einrückung verwendet (so viel zu superschlauer Branch Prediction). In der Zeit von HDDs war das Parsing kein Problem weil eh niemals mehr als 40 MiB/s eintrudelten; mit SSDs ist es deutlicher Flaschenhals.

Wo du Jonathan Blows Compiler erwähnst: Sprach er nicht mal von einer „Schallmauer“ bei einer Million Zeilen pro Sekunde? Mit SSDs werden an die 400 Millionen Zeichen pro Sekunde eingeschaufelt; das entspricht eher einer Anforderung von 10 Millionen Zeilen/s. Wenn die Datei aus dem Page Cache kommt, hast du quasi RAM-Bandbreite (auf meinem Low-End-System 40 GiB/s, also an die Milliarde Zeilen pro Sekunde).

(Jetzt darf jeder für sich ein 40 MiB großes PDF öffnen und zählen, wie lange das dauert. Und dabei ist das bloß in Teilen textbasiert und die dicken Ressourcen liegen schon binär vor!)

Ist natürlich nicht Lord Delvins Anwendungsfall, denn niemand wird ein GiB Quelltext einer Programmiersprache kompilieren und erwarten, dass das in zwei Sekunden fertig ist.
… oder?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Schrompf »

Ich glaube durchaus, dass da deutlich mehr geht, aber bei uns - die wir gigantische XML-Dateien lesen müssen - ist da die Forschung erst am Anfang. Ich habe mal nen vektorisierten Parser angefangen, der mit 16/32 Bytes pro Schritt ein paar tausend Keywords aus ner Liste auseinanderhalten soll. Liegt seit Ewigkeiten in irgendnem Experimente-Branch. Der bisherige Parser ist ne klassische Ein-Byte-Lesen-Und-StateMachine-Durchlaufen und schafft damit vielleicht 100MB pro Sekunde, aber wir parsen parallel mehrere Teile des XML-Files und setzen die Teilstücke des DOMs dann zusammen.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Helmut hat geschrieben: 16.10.2021, 22:45 @Lord Delvin
Verstehe ich das richtig, dass du für 2k LOC mehr als 10s zum Parsen benötigst?
Nein, das war ein Misverständnis. Das sind alle Conformancetests zusammen und im Java-Profiler.
Für die 2k LoC brauche ich *mit Testausführung* 0.6s.
Momentan habe ich noch ANTLR v4 Parser mit ParseTree-Generierung, wenn ich es richtig im Kopf habe. Da ist nicht allzuviel zu erwarten.
Zum debuggen praktisch und insgesamt zu wenig Einfluss auf das Endergebnis.

EDIT: Die Gesamtausführung aller Tests ist ohne Profiler in 21s erledigt. D.h. die absoluten Zahlen oben sind mit äußerster Vorsicht zu genießen. Um an bessere Zahlen zu kommen müsste ich wirklich eigene Performancecounter einbauen.
Krishty hat geschrieben: 17.10.2021, 00:29 Ist natürlich nicht Lord Delvins Anwendungsfall, denn niemand wird ein GiB Quelltext einer Programmiersprache kompilieren und erwarten, dass das in zwei Sekunden fertig ist.
… oder?
Ich sag' mal wenn du 10MB JavaScript auslieferst und immer noch eine Responsetime von 100ms erwartest ;)

Aber für das, was ich jetzt hier vor habe, kann ich mir nicht vorstellen, dass es so ist. Ehrlich gesagt kann ich mir nicht mal vorstellen, dass man in der Lage wäre, das resultierende Binary in der Zeit zu schreiben.

Beim Parsen bzw. Entwerfen von Datenformaten gelten ganz andere Regeln. Da würde man auch nicht die Lebenszeit des Entwicklers beim Schreiben des Codes optimieren, weil da viel einfach maschinengeneriert und -gelesen ist.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Die TODO-Liste für 0.6 leert sich zunehmend. Heute habe ich endlich die CStrings fertig, die ich als Anwendungsfall für mein C-API einbauen wollte.
Hat tatsächlich noch eine Spracherweiterung für super Konstruktor-/Destruktor-Aufrufe erfordert, da man hier implizite Casts braucht, die i.A. nicht typkorrekt wären.
Im folgenden mal der Code zum CString mit Erklärung. Würde mich interessieren, was die Community hier von meiner Syntax denkt. Vielleicht hat ja noch jemand eine gute Idee, die ich nicht hatte :)

Code: Alles auswählen

// import; macht FlatArray sichtbar
with container.FlatArray;

/**
 * char const* with a \0 terminator
 */
 // CString ist ein Subtyp von FlatArray, d.h. eine echte untermenge von char* in C.
 // Das gibt es in der C-Familie meines Wissens so nicht; in Ada gibt es das aber auch
 // anm.: type ist ein struct oder ein anderer flacher typ in C und kann nicht dispatchen, da es keine Laufzeittypinformationen hat
public type CString <: FlatArray[byte] {

  /**
   * Create from a Tyr String.
   */
   // das ist der Konstruktor; Ich fand es schon immer beknackt den Typnamen zu wiederholen
   // anm.: String ist mehr sowas wie ein Iterator<char*>; konzeptionell längenkodiert und nicht terminiert
  new (from : String) {
    // super konstruktoraufruf; hat die Form T.new(params); kein explizites this erlaubt
    // anm.: derzeit gibt es bei expliziten Konstruktordefinitionen keine impliziten Superkonstruktorcalls; Reihenfolge ist frei
    // rationale: mir war die erzwungene Sicherheit hier schon öfter im Weg; perspektivisch würde ich das über ein property (d.h. attribut/annotation) lösen
    // anm.: effektiv ist das ein malloc-Aufruf
    FlatArray[byte].new(from.size()+1U);

    // vielleicht nicht ultra effizient, jedes byte einzeln zu kopieren; das ist der Preis, den man zahlt, wenn man den Iterator-Weg geht
    // anm.: vermutlich muss ich perspektivisch die literale doch auch \0-terminieren, die falsche länge abspeichern und habe so zwei sichten auf einmal und kann für literale einen eigenen Konstruktor verwenden, der dann effektiv ein nop ist; ist gerade aber noch nicht das Thema
    var i = 0
    // Typinferenz für c ist neu in 0.6
    from.bytes().foreach c do {
      // ruft die update-Funktion von flatarray auf
      this(i) = c;
      ++i
    }
    // Literale sind in Tyr strikt getypt und es gibt keine impliziten konvertierungen, weswegen man den 'i8' postfix braucht
    this(i) = 0i8
  }

  /** release the string's memory */
  // das ist der destruktor; hat keine expliziten parameter, ein implizites this; wäre für Klassen dispatchend
  delete {
    // superkonstruktoraufruf; hier wird die this-Referenz implizit in den Supertyp gecastet, was man momentan nicht explizit machen kann
    // anm.: effektiv ist das ein free-Aufruf
    FlatArray[byte].delete;
    // für type muss das rücksetzen auf null explizit gemacht werden, da nicht jeder type einen Nullwert hat
    // bei class-Instanzen macht es der Destruktorcall-Hüllcode d.h. es ist nicht aus Versehen zu verhindern
    this = null
  }

  /** print the string to stdout */
  // hier wird eine funktion CString.print definiert
  // die Realisierung erfolgt indem man aus der externen Bibliothek "c" das Symbol "puts" nimmt
  // in der Paketdefinition von tyr.lang findet man die deklaration zu dieser Bibliothek:
  // extern c from libc
  // externe bibliotheken werden an abhängige pakete vererbt, da man die Bibliothek ja ohnehin laden muss
  // die Symboldefinition wird zur Compilezeit geprüft
  // anm.: extern ist hier ein Schlüsselwort, das als alternative zu ';', '=', ':=' oder '{' über die Realisierungsart entscheidet
  type def print (this : CString) : int extern c.puts;

  // und hier ein kleiner Test, der die Verwendung demonstriert und prüft
  test "hello" {
    var s = new CString("hello\n");
    s.print()
    delete s
    null == s
  }
}
EDIT: falls das nicht klar ist, Ausgabe ist:

Code: Alles auswählen

running 1 tests
=== start test hello ===
hello

=== end test: success ===
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Meine Mühen DWARF zu erzeugen tragen langsam Früchte:

Code: Alles auswählen

==5925== 16 bytes in 1 blocks are definitely lost in loss record 2 of 2
==5925==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==5925==    by 0x40126D: ??? (mar.tyr:20)
==5925==    by 0x40146B: main (mar.tyr:11)
Jetzt muss ich den ganzen ****haufen nurnoch irgendwie dazu bringen, auch meine Funktionsnamen zu fressen.

EDIT: Keine Ahnung wie das gehen soll. Immerhin bin ich jetzt an einem Punkt, an dem es zum Arbeiten reicht:

Code: Alles auswählen

==28812== Invalid read of size 4
==28812==    at 0x401504: ??? (tyr.lang/container/arrayBuffer.tyr:45)
==28812==    by 0x401251: ??? (test/main.tyr:12)
==28812==    by 0x40131A: ??? (test/main.tyr:18)
==28812==    by 0x401457: ??? (test/main.tyr:50)
==28812==    by 0x40220B: main (unkown:0)
==28812==  Address 0x4a5e200 is 0 bytes after a block of size 320 alloc'd
==28812==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==28812==    by 0x401B6E: ??? (tyr.lang/container/arrayBuffer.tyr:174)
==28812==    by 0x401CC9: ??? (tyr.lang/container/arrayBuffer.tyr:149)
==28812==    by 0x4015E9: ??? (tyr.lang/container/arrayBuffer.tyr:70)
==28812==    by 0x4012C6: ??? (test/main.tyr:21)
==28812==    by 0x4013A1: ??? (test/main.tyr:44)
==28812==    by 0x4020E9: main (unkown:0)
EDIT2: Und gleich mal einen gruseligen Bug in der Containerbibliothek gefixt.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Heute mal wieder ein Update mit Bild :)
screenshot.png
Tatsächlich habe ich schon zum Jahreswechsel mal geschaut, wie weit man kommt, wenn man wirklich versuchen würde eine echte Anwendung oder ein Minispiel zu schreib. An dem Punkt gerade muss man einfach mal Sachen ausprobieren und schauen, was einen in der Praxis wirklich nervt.

Mich hat dann auch überrascht, was ich gut finde, was funktioniert und was ich noch brauche, damit man zumindest mal ein gut nutzbares C-Bibliotheks-API bauen kann.
Bei meinen typisierten Literalen habe ich noch eine Variante nachgerüstet, die keine Punkte enthalten muss, wenn man den Postfix hat, z.B. 1f. Das braucht man in C nicht, weil man da den impliziten cast von 1 nach 1.0f hat.
Etwas anderes, das man vielleicht noch einbauen sollte, ist irgendeine Art ArrayView, womit man z.B. 3 Werte aus einem Farbarray an die entsprechende OpenGL-Funktion reichen kann ohne die Zeigerarithmetik selbst explizit machen zu müssen. Da das aber reine Bibiliothekserweiterung ist, habe ich da noch nichts gemacht. Wird bei bedarf einfach eingebaut und erfordert kein Sprachrelease.

Was ich komplett unterschätzt habe sind enums. Ist nicht das erste Mal und ich bin da in guter Gesellschaft :-/
Das wird vermutlich im nächsten Release auf eine Art C++-Style enum rauslaufen, also im Prinzip eine Sicht auf einen Zahlentyp.
Dazu gibt's vermutlich noch irgendeine form von tagged union, bei der man ein enum mit einer union verbindet um die C-Style enum-Polymorphie gut abbilden zu können. Erfordert vermutlich auch ein passendes switch.

IDE ist zwar etwas, an das man sich gewöhnt hat und das man mittelfristig auch mehr braucht als es jetzt existiert. Allerdings kommt man momentan noch ganz gut ohne aus. Was man da bauen müsste wären Fehleranzeige, Goto-Definition und Syntaxhighlighting; in der Reihenfolge. Wenn man bedenkt dass ich die Informationen alle im Compiler habe, aber mir nicht klar ist, wie ich da einen passenden Language Server baue, ist das eigentlich ein bisschen traurig.

Daneben habe ich mal zur Vorbereitung des Releases eine Roadmap geschrieben. Auch ein bisschen um mir selbst klar zu machen, was ich warum mache und was ich noch machen will.

Ehrlich gesagt ist mir noch nicht klar, was ein guter Zeitpunkt ist, um das Projekt aktiv zu bewerben.
Jetzt wird auf jeden Fall erstmal das 0.6 Release zusammengestellt und freigegeben.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Endlich geschafft. War eine Menge Arbeit.

https://github.com/tyr-lang/releases/re ... tag/v0.6.0

Falls jemand Interesse hätte schreibe ich gerne ein paar Tutorials :)
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [Projekt] Type Research Programming Language

Beitrag von Jonathan »

Lord Delvin hat geschrieben: 09.03.2022, 18:53 Was ich komplett unterschätzt habe sind enums. Ist nicht das erste Mal und ich bin da in guter Gesellschaft :-/
Wieos? Also, was ist an denen so schwer? Ich hätte jetzt irgendwie erwartet, dass sie halt im Prinzip wie z.b. ints funktionieren, nur halt mit anderen und strengeren Typ-Regeln (d.h. man hat ein paar Konstanten des enum-Typs und kann die zum Vergleichen und zuweisen benutzen, alles andere (Mischen von Typen, arithmetische Operationen) ist im Prinzip verboten, aber das läuft letztendlich nur auf Typregeln hinaus, die man anderswo sowieso schon hat. Oder übersehe ich da was?
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Nein, so war das nicht gemeint. Ich habe unterschätzt wie schnell man die eigentlich haben will. War ja in Java auch so, dass es die erst mit 5 gab. Man kann natürlich auch für jeden Wert eine Konstante definieren, aber das ist nicht dasselbe. Und ein switch über enums hätte ich schon gerne.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: [Projekt] Type Research Programming Language

Beitrag von Chromanoid »

Schon mal überlegt Enums wegzulassen und dafür das switch Statement bei Dir irgendwie klug via hash-basierter Jump-Tabelle zu bauen? Ich finde Enums finden immer schnell ihre Grenzen, weil sie prinzipiell nicht gut erweiterbar sind. Also das Konzept von Enums ist ganz nett, aber union types müssten reichen und schöner sein, finde ich.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: [Projekt] Type Research Programming Language

Beitrag von Lord Delvin »

Chromanoid hat geschrieben: 11.03.2022, 21:01 Schon mal überlegt Enums wegzulassen und dafür das switch Statement bei Dir irgendwie klug via hash-basierter Jump-Tabelle zu bauen? Ich finde Enums finden immer schnell ihre Grenzen, weil sie prinzipiell nicht gut erweiterbar sind. Also das Konzept von Enums ist ganz nett, aber union types müssten reichen und schöner sein, finde ich.
Das gibt es prinzipiell jetzt schon. Müsste mal schauen, ob die CT-evaluation schon reicht, um Literalkonstanten wie Literale auflösen zu können. Also sowas wie

Code: Alles auswählen

type T {
  type val one = 1
  type val two = 2
  
  type def use(x : int) = switch (x) {
    if one : one
    if two : two
    else 0
  }
}
Ungeprüft würde ich erwarten, dass es jetzt noch nicht geht und mit dem nächsten Release sehr wahrscheinlich gehen wird.
Die Realisierung der Switchstatements ist eigentlich nicht mal das Thema; nicht zuletzt weil das ohnehin Clang für mich macht und ich davon ausgehe, dass die einfach irgendwas effizientes aussuchen, jenachdem ob die cases dicht/zusammenhängend sind oder eben nicht.

Ich mag enums auch eher nicht, weil sie gerade in C oft als Ersatzobjektorientierung missbraucht werden. Allerdings braucht man da nicht groß jammern, wenn das Ziel ist, das bestehende C API zu recyclen.
Und wenn ich mir anschaue, was wir auf der Arbeit so machen, müsste ich mir fast überlegen, ob ich nicht StringLiteral als Basistyp gleich mitmache. Das hätte bei mir natürlich die hässliche Konsequenz, dass ich das switch auf String bauen müsste, was bei nicht-materialisierten Strings ziemlich teuer sein kann. Ist einem in dem Fall aber vielleicht egal, weil man ohnehin denselben Code von Hand schreiben würde.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Antworten