@lunar
interessant. Ich haette gedacht, dass die binaeren Schnittstellen einen geringeren Stellenwert haben, da ja bedingt durch den deklarativen Programmierstil die Trennung zwischen Typ-Schnittstelle & Implementation zwar vorhanden, aber weniger relevant ist. Und das ein Compiler eigentlich immer ueber alle notwendigen Deklarationen verfuegt, um den benoetigten Code zu generieren. Letztlich kann man ja sogar bei nem C++-compiler template-Spezialisierungen vornehmen, und fuer built-ins sollte sowas erst recht moeglich sein.
Meine funktionalen Programmier-Kenntnisse beziehen sich meistenteils auf OPAL von der TU Berlin, und AFAIK war das mit den Strings & Zahltypen da so. Die Definition ist definitiv seq[char], und auch natuerliche und ganze Zahlen sind algebraisch definiert - aber nicht implementiert.
Aber einen Beleg dafuer finde ich auf die Schnelle nicht, kann also sein, dass ich mich da irre.
Was ist ein string?
-
lunar
@deets: Es geht weniger um die Trennung zwischen Implementierung und Schnittstelle, sondern um den Zusammenhang zwischen Quelltext-Schnittstelle, Typschnittstelle und Binärschnittstelle. Das vom GHC genutzte Binärformat, nämlich Assembler, trägt keine Typinformationen, folglich müssen alle Listentypen dieselbe Binärschnittstelle tragen. Man könnte natürlich ein spezielles Bytecodeformat entwerfen, welches Typinformationen trägt. Dann wäre eine solche Optimierung möglich. Das ist bei Haskell aber halt nicht der Fall, denn eine Laufzeitumgebung für Bytecode muss auch erst einmal implementiert werden.
Mit C++-Templates ist die Situation nicht vergleichbar, da Templates keine Binärschnittstelle haben, kein Compiler implementiert extern-Deklarationen für Templates. Mithin muss immer die Implementierung vorliegen, Templates werden immer erst bei der Übersetzung des eigentlichen Programms kompiliert. Der GHC dagegen kompiliert polymorphe Funktionen aus.
Mit C++-Templates ist die Situation nicht vergleichbar, da Templates keine Binärschnittstelle haben, kein Compiler implementiert extern-Deklarationen für Templates. Mithin muss immer die Implementierung vorliegen, Templates werden immer erst bei der Übersetzung des eigentlichen Programms kompiliert. Der GHC dagegen kompiliert polymorphe Funktionen aus.
Du verwechselst zwei Dinge: die Implementierung und die tatsächliche Verwendung. Der wichtige Teil des Beispiels ist nicht der main-Abschnitt, sondern alles andere. Eine Tupel wird einfach in in ``Tuple<Type> t(...)`` übersetz, und "hallo" in ``String s; s[0]=h ...``. Das ist vollkommen transparent. Du schreibst in deinem Pythoncode auch nirgends ``PyObject``. Hoffe ich ^^ Während du dich also bereits ärgest, dass du für Tupel alles nochmal schreiben musst und viel mehr zu warten hast, freue ich mich, dass ich mit minimalem Mehraufwand bei der Verallgemeinerung bereits alles abgedeckt habeXynon1 hat geschrieben:Jupp, schönes Snippet. char* ist trotzdem schneller geschrieben
Einen einzeiligen Object-Typ von dem einfach alle anderen Typen erben wäre jetzt nicht so viel Arbeit gewesen.Xynon1 hat geschrieben:und wie bekomme ich da jetzt mehrere Datentypen rein? Bitte mach dir jetzt keine Mühe das auch noch einzubauen, ich weiß das geht. Mein Standpunkt war nur das es nicht so "einfach" ist.
Das Leben ist wie ein Tennisball.
-
deets
@lunar
Das mag ja konkret so sein, aber einen technischen Grund, das es so sein *muss* sehe ich nicht. Nimm psyco - der ist ja auch in der Lage, optimierten Code (bzw. mehrere Implementationen) fuer einen bestimmten Typ zu erzeugen - aus einer in Python per se generischen Funktion.
Natuerlich musst du dann guarding-statements einfuehren, die sicherstellen, dass du nicht in einen falschen Code-Pfad einspringst, der sich binaer nicht mit deinen Daten vertraegt. Aber es geht, wie psyco belegt. Und ich sehe auch nicht, dass ein funktionaler compiler die notwendigen funktionen in seiner stdlib nicht mitfuehren kann, um sie bei Bedarf als Sprungziele zu definieren. Es geht ja um ein klar definiertes sub-set von Typen, die immer bekannt sind.
Ist halt eine Frage des trade-offs: offensichtlich ist der Gewinn durch spezialisierung bei Zahltypen + strings ziemlich hoch, durch die deutlich kompaktere Darstellung & optimierte Befehle.
Ich schaue nochmal, ob ich da nicht einen Beleg fuer OPAL finde.
Das mag ja konkret so sein, aber einen technischen Grund, das es so sein *muss* sehe ich nicht. Nimm psyco - der ist ja auch in der Lage, optimierten Code (bzw. mehrere Implementationen) fuer einen bestimmten Typ zu erzeugen - aus einer in Python per se generischen Funktion.
Natuerlich musst du dann guarding-statements einfuehren, die sicherstellen, dass du nicht in einen falschen Code-Pfad einspringst, der sich binaer nicht mit deinen Daten vertraegt. Aber es geht, wie psyco belegt. Und ich sehe auch nicht, dass ein funktionaler compiler die notwendigen funktionen in seiner stdlib nicht mitfuehren kann, um sie bei Bedarf als Sprungziele zu definieren. Es geht ja um ein klar definiertes sub-set von Typen, die immer bekannt sind.
Ist halt eine Frage des trade-offs: offensichtlich ist der Gewinn durch spezialisierung bei Zahltypen + strings ziemlich hoch, durch die deutlich kompaktere Darstellung & optimierte Befehle.
Ich schaue nochmal, ob ich da nicht einen Beleg fuer OPAL finde.
-
deets
So, ich hab' nochmal geschaut. Und das hier gefunden:
http://projects.uebb.tu-berlin.de/opal/ ... umentation
Und da dann
http://projects.uebb.tu-berlin.de/opal/ ... cguide.pdf
Das beschaeftigt sich damit, wie man dem Opal-Compiler haendische Implementationen bestimmter Typen unterschieben kann. Was exemplarisch auch an ints und strings angerissen wird.
Oh, und natuerlich gibt's mit dem OCS auch einen "Interpreter" ,der macht halt den compilier-krams transparent im Hintergrund.
Es geht also Mich wundert, dass es augenscheinlich nicht verallgemeinerbar auf FPs ist, weil es ja schon viel bringen wuerde. Aber man lernt nie aus...
http://projects.uebb.tu-berlin.de/opal/ ... umentation
Und da dann
http://projects.uebb.tu-berlin.de/opal/ ... cguide.pdf
Das beschaeftigt sich damit, wie man dem Opal-Compiler haendische Implementationen bestimmter Typen unterschieben kann. Was exemplarisch auch an ints und strings angerissen wird.
Oh, und natuerlich gibt's mit dem OCS auch einen "Interpreter" ,der macht halt den compilier-krams transparent im Hintergrund.
Es geht also
Mich wundert, dass es augenscheinlich nicht verallgemeinerbar auf FPs ist, weil es ja schon viel bringen wuerde. Aber man lernt nie aus...-
lunar
@deets: pysco ist nicht vergleichbar. Als JIT-Compiler sieht psyco immer das vollständige Programm im Quelltext oder zumindest im Bytecode. Dementsprechend kann psyco auch Optimierungen vornehmen, die – wie eben bestimmte effiziente Implementierungen – die Binärschnittstelle und damit das gesamte Programm betreffen, da er ja das ganze Programm daran anpassen kann.
Um eine solche Optimierung vornehmen zu können, müsste der GHC ebenfalls die Implementierung aller verwendeten Funktionen kennen, um sie ggf. für eine spezialisierte Implementierung eines generischen Typs neu zu übersetzen. Das ist aber nicht der Fall, bei binär kompilierten Drittmodulen kennt der Compiler die Implementierung nicht, sondern nur die Typsignatur und die Binärschnittstelle. An diese Binärschnittstelle ist der Compiler mithin gebunden. Erwartet die Funktion eine verkettete Liste, muss der Compiler etwas übergeben, dass sich binär genauso verhält wie eine verkettete Liste. Ein Feld tut das halt nicht.
Man müsste wie gesagt entweder jedwede Funktion in mehreren Versionen kompilieren, oder (wie bei C++-Templates) die Implementierung offenlegen. Eine weitere Alternative wäre eine VM für ein spezielles Bytecode-Format statt Binärcode. Dann könnte die Laufzeitumgebung programmweite Optimierungen vornehmen, was dann das Pendant zu psyco wäre. Das alles ist aber bei Haskell eben nicht der Fall. Ich habe ja auch nicht behauptet, dass eine solche Optimierung unmöglich wäre, ich sage nur, dass unter den gegebenen Umständen in Haskell-Implementierungen nicht umzusetzen ist.
Den Zusammenhang zu Opal sehe ich nicht. Opal kompiliert offenbar in C (statt Binärcode), und hat ähnlich wie CPython bestimmte C-Strukturen, die Typen beschreiben. Das verlinkte Dokument beschreibt mithin nur, wie man eine bestimmten Typen selbst implementiert, anstatt die C-Implementierung durch den Compiler erzeugen zu lassen. Das beeinflusst ja die Binärschnittstelle nicht, denn ob man die Struktur erzeugen lässt, oder selbst implementiert, die Struktur hat so oder so dieselbe Schnittstelle.
Außerdem unterliegt Opal als Forschungssprache nicht denselben Einschränkungen wie Haskell, und ist insbesondere nicht an eine stabile ABI für Module gebunden.
Um eine solche Optimierung vornehmen zu können, müsste der GHC ebenfalls die Implementierung aller verwendeten Funktionen kennen, um sie ggf. für eine spezialisierte Implementierung eines generischen Typs neu zu übersetzen. Das ist aber nicht der Fall, bei binär kompilierten Drittmodulen kennt der Compiler die Implementierung nicht, sondern nur die Typsignatur und die Binärschnittstelle. An diese Binärschnittstelle ist der Compiler mithin gebunden. Erwartet die Funktion eine verkettete Liste, muss der Compiler etwas übergeben, dass sich binär genauso verhält wie eine verkettete Liste. Ein Feld tut das halt nicht.
Man müsste wie gesagt entweder jedwede Funktion in mehreren Versionen kompilieren, oder (wie bei C++-Templates) die Implementierung offenlegen. Eine weitere Alternative wäre eine VM für ein spezielles Bytecode-Format statt Binärcode. Dann könnte die Laufzeitumgebung programmweite Optimierungen vornehmen, was dann das Pendant zu psyco wäre. Das alles ist aber bei Haskell eben nicht der Fall. Ich habe ja auch nicht behauptet, dass eine solche Optimierung unmöglich wäre, ich sage nur, dass unter den gegebenen Umständen in Haskell-Implementierungen nicht umzusetzen ist.
Den Zusammenhang zu Opal sehe ich nicht. Opal kompiliert offenbar in C (statt Binärcode), und hat ähnlich wie CPython bestimmte C-Strukturen, die Typen beschreiben. Das verlinkte Dokument beschreibt mithin nur, wie man eine bestimmten Typen selbst implementiert, anstatt die C-Implementierung durch den Compiler erzeugen zu lassen. Das beeinflusst ja die Binärschnittstelle nicht, denn ob man die Struktur erzeugen lässt, oder selbst implementiert, die Struktur hat so oder so dieselbe Schnittstelle.
Außerdem unterliegt Opal als Forschungssprache nicht denselben Einschränkungen wie Haskell, und ist insbesondere nicht an eine stabile ABI für Module gebunden.
-
deets
@lunar
Zuerstmal sehe ich nicht, wieso Opal irrelevant sein sollte. Aus architektonischen Gruenden produziert es C als Zwischencode (wie andere Sprachen wie bigloo-scheme zB auch), aber die Ausgabe am Ende ist Binaercode - genausogut koennte man LLVM benutzen, oder eben direkt Opcodes ausspucken. Das macht doch keinen Unterschied.
Und es stimmt auch nicht, dass die haendisch geschriebenen Typen in Opal dasselbe sind wie eine Compiler-generierte Variante. Zum einen waeren sie dann ziemlich sinnlos. Und zum anderen ist zB der String-Typ als Baum von denotation-Objekten (die auch irgendwie strings sind) zusammengesetzt, und mitnichten eine sequenz von char-Objekten, wie es die Signatur vorgibt. Es ist also ganz offensichtlich nicht dieselbe Binaerschnittstelle wie sie der naive Opal-only Typ haette (sequence of char).
Was ich allerdings im Moment nicht pruefen kann (OSX & Opal geht leider nicht) ist, ob Opal tatsaechlich immer alle Definitionen zur Verfuegung haben muss oder nicht, und somit sozusagen on the fly Spezialisierungen generischer Funktionen baut. Vielleicht schaffe ich das nochmal, das zu verifizieren.
Aber lassen wir mal Opal beiseite. Ich habe immer noch Schwierigkeiten mir vorzustellen, dass deine Argumentation schluessig ist. Was du ja sagst ist, dass schon alleine die Signatur eines Typs ausreichen muss, um einer generischen Funktion genug "Futter" fuer ihre Implementation zu geben. So dass sie dann ein konsistentes ABI bieten kann, bzw. sich darauf verlaesst.
Doch wie vertraegt sich das zB mit einem Set-like Typen, der von seiner Signatur her komplett gleich ist, den ich aber in zwei Implementierungen vorliegen habe - einmal sortierte Liste, und einmal balancierter Baum? Damit kann doch eine generische Funktion ueber Sets sich eben nicht bis auf eine Strukturebene ausbilden, sondern muss im Grunde ueber Funktionspointer fuer den jeweils gegebenen Typ genau die Operation ausfuehren, welche ihre Logik verlangt - aber eben indirekt auf die Daten wirkt. Und wenn das geht, dann ist der Schritt, auch Konstruktoren und Selektoren einfach nur als Funktionen zu betrachten eigentlich logisch. Letztlich ist das eine Art vtable oder hashmap. Wenn das Haskell nicht so macht, wie baut es dann generische Funktionen fuer so einen Fall?
Ein Hinweis, dass auch Opal das so handhabt ist uebrigens, dass die Konstruktoren & Selektoren haendisch definierter Typen eine Namenskonvention haben *muessen*, abhaenging von Aritaet und soweiter. Diese Einschraenkueng waere deutlich weniger Sinnvoll, wenn ich pro Typ eh eine Spezialisierung kompiliere. Aber 100%ig wissen tue ich das wie gesagt leider nicht, mag also noch anderer Gruende haben.
Zuerstmal sehe ich nicht, wieso Opal irrelevant sein sollte. Aus architektonischen Gruenden produziert es C als Zwischencode (wie andere Sprachen wie bigloo-scheme zB auch), aber die Ausgabe am Ende ist Binaercode - genausogut koennte man LLVM benutzen, oder eben direkt Opcodes ausspucken. Das macht doch keinen Unterschied.
Und es stimmt auch nicht, dass die haendisch geschriebenen Typen in Opal dasselbe sind wie eine Compiler-generierte Variante. Zum einen waeren sie dann ziemlich sinnlos. Und zum anderen ist zB der String-Typ als Baum von denotation-Objekten (die auch irgendwie strings sind) zusammengesetzt, und mitnichten eine sequenz von char-Objekten, wie es die Signatur vorgibt. Es ist also ganz offensichtlich nicht dieselbe Binaerschnittstelle wie sie der naive Opal-only Typ haette (sequence of char).
Was ich allerdings im Moment nicht pruefen kann (OSX & Opal geht leider nicht) ist, ob Opal tatsaechlich immer alle Definitionen zur Verfuegung haben muss oder nicht, und somit sozusagen on the fly Spezialisierungen generischer Funktionen baut. Vielleicht schaffe ich das nochmal, das zu verifizieren.
Aber lassen wir mal Opal beiseite. Ich habe immer noch Schwierigkeiten mir vorzustellen, dass deine Argumentation schluessig ist. Was du ja sagst ist, dass schon alleine die Signatur eines Typs ausreichen muss, um einer generischen Funktion genug "Futter" fuer ihre Implementation zu geben. So dass sie dann ein konsistentes ABI bieten kann, bzw. sich darauf verlaesst.
Doch wie vertraegt sich das zB mit einem Set-like Typen, der von seiner Signatur her komplett gleich ist, den ich aber in zwei Implementierungen vorliegen habe - einmal sortierte Liste, und einmal balancierter Baum? Damit kann doch eine generische Funktion ueber Sets sich eben nicht bis auf eine Strukturebene ausbilden, sondern muss im Grunde ueber Funktionspointer fuer den jeweils gegebenen Typ genau die Operation ausfuehren, welche ihre Logik verlangt - aber eben indirekt auf die Daten wirkt. Und wenn das geht, dann ist der Schritt, auch Konstruktoren und Selektoren einfach nur als Funktionen zu betrachten eigentlich logisch. Letztlich ist das eine Art vtable oder hashmap. Wenn das Haskell nicht so macht, wie baut es dann generische Funktionen fuer so einen Fall?
Ein Hinweis, dass auch Opal das so handhabt ist uebrigens, dass die Konstruktoren & Selektoren haendisch definierter Typen eine Namenskonvention haben *muessen*, abhaenging von Aritaet und soweiter. Diese Einschraenkueng waere deutlich weniger Sinnvoll, wenn ich pro Typ eh eine Spezialisierung kompiliere. Aber 100%ig wissen tue ich das wie gesagt leider nicht, mag also noch anderer Gruende haben.
-
lunar
@deets: Um verschiedene Implementierungen mit derselben Schnittstelle zu versehen, nutzt Haskell Typklassen. Typklassen definieren ähnlich den Schnittstellen in Java eine Menge an Operationen, die Typen unterstützen müssen. Die Zuordnung eines Typen zu einer Typklasse geschieht allerdings explizit, wobei die generischen Operationen der Typklasse konkret für den speziellen Typen implementiert werden müssen. Typklassen sind die Basis generischer Operationen wie beispielsweise Gleichheit oder Ordnung.
Verwendet eine Funktion Funktionen einer Typklasse, so schlägt sich das in im Typschema der Funktion nieder. "sort" hat beispielsweise den Typen "(Ord a) => [a] -> [a]", ist also nur für Typen definiert, die Instanz der Typklasse "Ord" sind (diese Klasse definiert Vergleichsoperationen und somit die natürliche Ordnung eines Typen) (Beispiel mit nach Alter geordneten Personen).
Der Zugriff auf den Typen erfolgt also nur indirekt über die Operationen der Typklasse, wobei konkrete Typen explizit als Instanz einer Typklasse markiert werden. Mithin kann der Haskell-Compiler für die Typklasse eine ABI festlegen, und für Instanzen Wrapper erzeugen, welche dieser ABI entsprechen. Vor dem Aufruf von Funktionen, die eine Typklasse verlangen, können Objekte konkreter Typen dann in den entsprechenden Wrapper verpackt werden, die Funktion selbst muss den konkreten Typen gar nicht kennen.
Die ML-Familie nutzt statt Typklassen Funktoren, also Module höherer Ordnung, um die Problemstellung, identische Schnittstellen mit verschiedenen Implementierungen zu versehen, zu lösen.
Was die Namenskonvention händisch implementierter Opal-Typen angeht, so vermute ich, dass das primär erst einmal der Typprüfung dient. Um vollständige Typinferenz durchzuführen, muss der Compiler die Typschemen solcher Typen ebenfalls kennen. Opal kodiert diese Typen offenbar in der Signatur der C-Funktion, und erspart sich so die Notwendigkeit, die Typschemen zusätzlich zu speichern. Haskell erzeugt bei der Übersetzung von Modulen separate Dateien mit Typinformationen.
Und wie gesagt, ich sage ja nicht, dass eine solche Optimierung generell unmöglich ist. Im Gegenteil, man kann sie auf verschiedenste Weise umsetzen, aber halt jeweils mit anderen Nachteilen. Ich habe nur versucht zu erklären, warum Haskell und ML dergleichen nicht umsetzen, und das sind halt die einzigen rein funktionalen Sprachen ihrer Art, die auch praktisch eingesetzt werden.
Verwendet eine Funktion Funktionen einer Typklasse, so schlägt sich das in im Typschema der Funktion nieder. "sort" hat beispielsweise den Typen "(Ord a) => [a] -> [a]", ist also nur für Typen definiert, die Instanz der Typklasse "Ord" sind (diese Klasse definiert Vergleichsoperationen und somit die natürliche Ordnung eines Typen) (Beispiel mit nach Alter geordneten Personen).
Der Zugriff auf den Typen erfolgt also nur indirekt über die Operationen der Typklasse, wobei konkrete Typen explizit als Instanz einer Typklasse markiert werden. Mithin kann der Haskell-Compiler für die Typklasse eine ABI festlegen, und für Instanzen Wrapper erzeugen, welche dieser ABI entsprechen. Vor dem Aufruf von Funktionen, die eine Typklasse verlangen, können Objekte konkreter Typen dann in den entsprechenden Wrapper verpackt werden, die Funktion selbst muss den konkreten Typen gar nicht kennen.
Die ML-Familie nutzt statt Typklassen Funktoren, also Module höherer Ordnung, um die Problemstellung, identische Schnittstellen mit verschiedenen Implementierungen zu versehen, zu lösen.
Was die Namenskonvention händisch implementierter Opal-Typen angeht, so vermute ich, dass das primär erst einmal der Typprüfung dient. Um vollständige Typinferenz durchzuführen, muss der Compiler die Typschemen solcher Typen ebenfalls kennen. Opal kodiert diese Typen offenbar in der Signatur der C-Funktion, und erspart sich so die Notwendigkeit, die Typschemen zusätzlich zu speichern. Haskell erzeugt bei der Übersetzung von Modulen separate Dateien mit Typinformationen.
Und wie gesagt, ich sage ja nicht, dass eine solche Optimierung generell unmöglich ist. Im Gegenteil, man kann sie auf verschiedenste Weise umsetzen, aber halt jeweils mit anderen Nachteilen. Ich habe nur versucht zu erklären, warum Haskell und ML dergleichen nicht umsetzen, und das sind halt die einzigen rein funktionalen Sprachen ihrer Art, die auch praktisch eingesetzt werden.