Art Löschen in Haskell?

Question

ich einen Vortrag Hinweis auf Haskell lesen, wenn ich auf diesem Absatz kam (http://www.seas.upenn.edu/~cis194/lectures/02-lists.html):

Dieses „nicht darum kümmern,“ ist das, was die „parametrisch“ in parametrischen Polymorphismus Mitteln. Alle Haskell-Funktionen müssen in ihren Typparametern parametrisch sein; Die Funktionen müssen auf der Grundlage der Auswahlmöglichkeiten für diese Parameter keine Bedeutung haben oder Entscheidungen treffen. Eine Funktion kann nicht eine Sache tun, wenn a Int ist und eine andere Sache, wenn a Bool ist. Haskell bietet einfach keine Möglichkeit, eine solche Operation zu schreiben. Diese Eigenschaft einer Sprache wird parametrisch genannt.

Es gibt viele tiefe und tiefgreifende Konsequenzen der Parameterik. Eine Konsequenz ist etwas, das als Typ-Löschung bezeichnet wird. Da ein ausgeführtes Haskell-Programm aufgrund von Typinformationen niemals Entscheidungen treffen kann, können alle Typinformationen während der Kompilierung gelöscht werden. Trotz wie wichtig Typen beim Schreiben von Haskell-Code sind, sind sie beim Ausführen von Haskell-Code völlig irrelevant. Diese Eigenschaft verleiht Haskell eine enorme Geschwindigkeitssteigerung im Vergleich zu anderen Sprachen wie Python, die Typen zur Laufzeit beibehalten müssen. (Typ Löschung ist nicht die einzige Sache, die Haskell schneller macht, aber Haskell getaktet manchmal zu 20x schneller als Python.)

Was ich nicht verstehe ist, wie „alle Haskell Funktionen“ parametrisch sind? Sind Typen in Haskell nicht explizit/statisch? Auch ich verstehe nicht wirklich, wie Typ Löschung verbessert kompilieren Zeit Laufzeit?

Entschuldigung, wenn diese Fragen wirklich grundlegend sind, bin ich zu Haskell neu.

EDIT:

Noch eine Frage: Warum hat der Autor sagt, dass „Trotz, wie wichtig Typen sind, wenn der Code Haskell schreiben, sie völlig irrelevant sind, wenn Haskell Code ausgeführt“?

Answer 1

Was ich nicht verstehe ist, wie sind "alle Haskell-Funktionen" parametrisch?

Es heißt nicht alle Haskell Funktionen parametrisch sind, heißt es:

Alle Haskell Funktionen parametrisch sein müssen in ihren Typparametern.

A Haskell Funktion braucht keine Typparameter haben.

Noch eine Frage: Warum sagt der Autor: "Trotz wie wichtig Typen beim Schreiben von Haskell-Code sind, sind sie beim Ausführen von Haskell-Code völlig irrelevant"?

Im Gegensatz zu einer dynamisch typisierte Sprache, wo Sie müssen während der Laufzeit prüfen, ob (zum Beispiel) zwei Dinge sind Zahlen, bevor Sie versuchen, sie zusammen zu fügen, Ihr laufendes Haskell Programm weiß, dass, wenn Sie versuchen, sie zusammen fügen , dann müssen sie Zahlen sein, weil der Compiler sich vorher davon überzeugt hat.

Sind nicht Typen explizit/statisch in Haskell?

Arten in Haskell können oft abgeleitet werden, in diesem Fall müssen sie nicht explizit sein. Aber Sie haben Recht, dass sie statisch sind, und das ist eigentlich der Grund, warum sie zur Laufzeit nicht wichtig sind, weil "statisch" bedeutet, dass der Compiler sicherstellt, dass alles den richtigen Typ hat, bevor das Programm überhaupt ausgeführt wird.

Answer 2

Implementierungen dynamisch typisierter Sprachen müssen normalerweise Typinformationen für jeden Wert im Speicher speichern. Das ist nicht schlecht für Lisp-ähnliche Sprachen, die nur ein paar Typen haben und sie mit ein paar Tag-Bits identifizieren können (obwohl solche eingeschränkten Typen zu anderen Effizienzproblemen führen). Es ist viel schlimmer für eine Sprache mit vielen Arten. Mit Haskell können Sie Typinformationen zur Laufzeit übertragen, aber Sie müssen sich explizit dazu äußern, damit Sie auf die Kosten achten können. Zum Beispiel bietet das Hinzufügen des Kontexts Typeable a zu einem Typ einen Wert mit diesem Typ, der zur Laufzeit auf eine Darstellung des Typs a verweist. Etwas subtiler sind Typklassen-Instanzwörterbücher normalerweise auf Kompilierzeit spezialisiert, aber in ausreichend polymorphen oder komplexen Fällen können sie zur Laufzeit überleben. In einem Compiler wie dem scheinbar verlassenen JHC und einer wahrscheinlichen Möglichkeit für den noch kaum gestarteten Compiler THC könnte dies dazu führen, dass einige Typinformationen zur Laufzeit in Form von Pointer-Tagging durchsickern. Aber diese Situationen sind ziemlich leicht zu identifizieren und verursachen nur selten ernsthafte Leistungsprobleme.

Answer 3

Typen können in Haskell gelöscht werden, da der Typ eines Ausdrucks entweder zur Kompilierungszeit bekannt ist (wie True) oder sein Typ zur Laufzeit nicht von Bedeutung ist (wie []).

Es gibt jedoch eine Einschränkung, es wird davon ausgegangen, dass alle Werte eine Art von einheitlicher Darstellung haben. Die meisten Haskell-Implementierungen verwenden Zeiger für alles, weshalb der tatsächliche Typ dessen, worauf ein Zeiger verweist, keine Rolle spielt (außer für den Garbage Collector). Sie können sich jedoch eine Haskell-Implementierung vorstellen, die eine nicht einheitliche Repräsentation und dann einige Typinformationen verwendet muss aufbewahrt werden.

Answer 4

Andere haben bereits geantwortet, aber vielleicht können einige Beispiele helfen.

Python, zum Beispiel, gibt Informationen erst zur Laufzeit behält:

>>> def f(x): 
... if type(x)==type(0): 
...  return (x+1,x) 
... else: 
...  return (x,x) 
... 
>>> f("hello") 
('hello', 'hello') 
>>> f(10) 
(11, 10) 

Die Funktion oben gegebene jedes Argument x das Paar kehrt (x,x), außer wennx vom Typ int. Die Funktion testet diesen Typ zur Laufzeit, und wenn x als int gefunden wird, verhält sie sich in einer speziellen Weise und gibt stattdessen (x+1, x) zurück.

Um dies zu erreichen, muss die Python-Laufzeit die Typen verfolgen. Das heißt, wenn wir

>>> x = 5 

Python tun kann, nicht nur die Byte speichern Darstellung 5 im Speicher. Es muss auch diese Darstellung mit einem Typ-Tag int markieren, so dass, wenn wir type(x) tun, das Tag wiederhergestellt werden kann.

Bevor Sie irgendeinen Vorgang wie x+1 ausführen, muss Python das Typenschild überprüfen, um sicherzustellen, dass wir wirklich an int s arbeiten. Wenn x zum Beispiel eine str ist, löst Python eine Ausnahme aus.

Statisch überprüfte Sprachen wie Java benötigen zur Laufzeit keine solchen Prüfungen.Zum Beispiel, wenn wir

SomeClass x = new SomeClass(42); 
x.foo(); 

der Compiler hat bereits geprüft, es gibt in der Tat eine Methode foo für x bei der Kompilierung ausgeführt, so gibt es keine Notwendigkeit, dass wieder zu tun. Dies kann die Leistung im Prinzip verbessern. (Eigentlich ist die JVM hat einige Laufzeitprüfungen bei Klassenladezeit, aber wir diejenigen, für die der Einfachheit halber ignorieren)

Trotz der oben Java hat zu Store-Typ-Tags wie Python funktioniert, da es sich um eine hat type(-) analog:

if (x instanceof SomeClass) { ... 

Daher Java ermöglicht eine Funktion zu schreiben, die „speziell“ auf einigen Arten verhalten können.

// this is a "generic" function, using a type parameter A 
<A> A foo(A x) { 
    if (x instanceof B) { // B is some arbitrary class 
     B b = (B) x; 
     return (A) new B(b.get()+1); 
    } else { 
     return x; 
    } 
} 

Die obige Funktion foo() nur ihr Argument zurück, es sei denn, es ist vom Typ B, für die ein neues Objekt stattdessen erstellt wird. Dies ist eine Konsequenz der Verwendung von instanceof, die erfordert, dass jedes Objekt zur Laufzeit ein Tag trägt.

Um ehrlich zu sein, ein solches Tag ist bereits vorhanden, um virtuelle Methoden implementieren zu können, so dass es nichts mehr kostet. Das Vorhandensein von instanceof macht es jedoch möglich, das obige ungleichmäßige Verhalten auf Typen zu verursachen - einige Typen können unterschiedlich behandelt werden.

Haskell, hat stattdessen keinen solchen type/instanceof Operator. Ein parametrischer Haskell Funktionstyp mit

foo :: a -> (a,a) 

Muss verhalten auf die gleiche Weise auf allen Arten. Es gibt keine Möglichkeit, ein "spezielles" Verhalten zu verursachen. Konkret, foo xmuss zurückgeben (x,x), und wir können dies nur sehen, indem Sie sich die Typ Anmerkung oben. Um den Punkt zu betonen, muss man den Code (!!) nicht ansehen, um diese Eigenschaft zu beweisen. Dies ist, was parametricity vom obigen Typ gewährleistet.