Was ist ein string?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

mutetella hat geschrieben:Hat man mir damals nicht gerade deshalb auch Python empfohlen, weil ich mir dann über solche Dinge keinen Kopf machen muss...? :mrgreen:
Und warum tust du es dann immer?

Die Frage ist immer, ob man sich mit den Implementierungsdetails auseinandersetzen will oder ob man lieber gegen eine definierte Semantik programmiert.
Ich bevorzuge letzteres, du scheinst da wohl mehr auf ersteres zu stehen ;)

Die Antwort auf deine urspruengliche Frage ist - wenn man nicht in die Implementierungsdetails gehen will: Ein Python-Primitivum. Fertig.

@EyDu:
Da waer ich jetzt vorsichtig, wie DasIch schon geschrieben hat, sind das da keine Tupel, sondern Listen. Und die vorrangige Eigenschaft der Haskell-Tupel ist, dass man da verschiedene Datentypen mischen kann.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Xynon1 hat geschrieben:Das streite ich auch gar nicht ab, nur das Tuples in einer statisch typisierten Sprache genauso "einfach" wie Strings umzusetzen sind, kann ich irgendwie nicht glauben. Ich möchte nicht behaupten das es schwer ist, aber ist es nicht etwas komplexer eine Sequenz mit unterschiedlichen Datentypen umzusetzen, als eine mit gleichen?
Gut, ein Beispiel in wenigen Minuten zusammengeschrieben. Die untere Hälfte besteht nur aus Beispiel und syntaktischem Zucker, lediglich die Klasse ist wirklich interessant.
cofi hat geschrieben:@EyDu:
Da waer ich jetzt vorsichtig, wie DasIch schon geschrieben hat, sind das da keine Tupel, sondern Listen. Und die vorrangige Eigenschaft der Haskell-Tupel ist, dass man da verschiedene Datentypen mischen kann.
Wenn man möchte, kann man sich natürlich in unwichtigen Beispielen verfangen und dieses vollkommen überziehen ;-) Es ging um die prinzipielle Machbarkeit.
Das Leben ist wie ein Tennisball.
lunar

Der Verweis aus Haskell ist nur bedingt sinnvoll, zu unterschiedlich sind Typsystem und Semantik von Haskell und Python.

Haskells Definition einer Zeichenkette als eine Liste von Zeichen ist wohl auch auch weniger Resultat gründlichen Entwurfs, sondern eine aus der Not geborene Entscheidung. Generische Funktionen wie "map" sind in Haskell für Listen definiert, nicht aber für allgemeine iterierbare Objekte, da Haskell für letzteres keine Typklasse bietet. Aus praktischen Erwägungen ist es also sinnvoll, Zeichenketten als [Char] zu definieren, da man ansonsten all diese generischen Funktionen für Zeichenketten nochmals implementieren müsste.

@deets: Der GHC, die verbreiteste Haskell-Implementierung, kompiliert Zeichenketten in eine verkettete Liste von Zeichen, und nicht in ein Feld. Es findet keine spezielle Optimierung statt, insbesondere keine besondere Implementierung. Listen verschiedener Typen sind zwar algebraisch verschieden, müssen aber zur Implementierung polymorpher Listenfunktionen letztlich eine gemeinsame Binärschnittstelle besitzt. Eine spezielle Implementierung für einen bestimmten Listentypen erzeugt allerdings auch eine spezielle Binärschnittstelle.

Folglich muss die Optimierung entweder unter Verzicht auf eine stabile Binärschnittstelle über den gesamten Programm inklusive aller verwendeten Module durchgeführt werden, oder jedwede polymorphische Funktion für jede spezielle Implementierung eines Listentyps sowie für generische Listen kompilieren. Beides ist nicht praktikabel und mithin im GHC nicht implementiert. "String" ist in Haskell daher chronisch ineffizient, so dass man oft Data.Bytestring für I/O verwendet und nur bei Bedarf umwandelt.

Die Sprachen der ML-Familie, zur der wohl alle anderen, praktisch genutzte Sprachen mit deselben Typsystem wie Haskell gehören, definieren Zeichenketten daher nicht als Liste von Zeichen, sondern einen eigenen Typen für Zeichenketten. Dann wird semantisch klar getrennt zwischen diesen Typen, so dass man sie auch unterschiedlich implementieren kann. Der Nachteil ist natürlich, dass man generische Listenfunktionen dann nicht auf Zeichenketten anwenden kann.
Xynon1
User
Beiträge: 1267
Registriert: Mittwoch 15. September 2010, 14:22

@EyDu
Jupp, schönes Snippet. char* ist trotzdem schneller geschrieben :P 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.
Zuletzt geändert von Xynon1 am Dienstag 10. Mai 2011, 17:46, insgesamt 1-mal geändert.
Traue keinem Computer, den du nicht aus dem Fenster werfen kannst.
Xynon auf GitHub
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

cofi hat geschrieben:Und warum tust du es dann immer?
Weil ich glaube, dass gerade beim Programmieren ein theoretisches Verständnis dessen, was Du ein Primitivum nennst sich letztlich in 'besserem' Code niederschlägt.
Und wenn ich mehr über die Hintergründe, die ja spätestens bei ihrer Anwendung im Vordergrund stehen, erfahre, umso mehr Spaß macht das alles letztlich...
cofi hat geschrieben:... oder ob man lieber gegen eine definierte Semantik programmiert.
Was meinst Du damit: gegen eine definierte Semantik?

mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
deets

@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.
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.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Xynon1 hat geschrieben:Jupp, schönes Snippet. char* ist trotzdem schneller geschrieben :P
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 habe ;-)
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.
Einen einzeiligen Object-Typ von dem einfach alle anderen Typen erben wäre jetzt nicht so viel Arbeit gewesen.
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.
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...
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.
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.
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.
Antworten