Entspricht Haskells Typensystem formal dem von Java? [geschlossen]

66

Mir ist klar, dass einige Dinge in einer Sprache einfacher / schwieriger sind als in der anderen, aber ich interessiere mich nur für typbezogene Funktionen, die in der einen möglich und in der anderen unmöglich / irrelevant sind. Um es genauer zu machen, lassen Sie uns die Haskell-Typ-Erweiterungen ignorieren, da es so viele gibt, die alle möglichen verrückten / coolen Sachen machen.

GlenPeterson
quelle
4
Ich bin auch neugierig zu hören, wie die langatmigen Kategorietheoretiker diese Frage beantworten. Obwohl ich bezweifle, dass ich es besonders verstehen werde, bin ich immer noch an einer Detaillierung interessiert. Meine Neigung zu den Dingen, die ich gelesen habe, ist, dass der Compiler mit dem HM-Typensystem eine Menge über die Funktionsweise Ihres Codes wissen kann, weshalb er in der Lage ist, so viele Typen abzuleiten und so viele Garantien für das Verhalten zu geben. Aber das ist nur mein Bauchgefühl und ich bin mir sicher, dass es noch andere Dinge gibt, die ich überhaupt nicht kenne.
Jimmy Hoffa
1
Dies ist eine großartige Frage - es ist an der Zeit, sie an die Follower für die großartige Haskell / JVM-Debatte zu twittern!
Martijn Verburg
6
@ m3th0dman: Scala unterstützt Funktionen höherer Ordnung genauso wie Java. In Scala werden erstklassige Funktionen wie in Java einfach als Instanzen abstrakter Klassen mit einer einzigen abstrakten Methode dargestellt. Sicher, Scala hat syntaktischen Zucker zum Definieren dieser Funktionen und eine umfangreiche Standardbibliothek von vordefinierten Funktionstypen und Methoden, die Funktionen akzeptieren. Aus Sicht des Typsystems , worum es bei dieser Frage geht, gibt es keinen Unterschied . Wenn Scala das kann, kann es auch Java, und tatsächlich gibt es von Haskell inspirierte FP-Bibliotheken für Java.
Jörg W Mittag
2
@ m3th0dman: Darum geht es in dieser Frage nicht.
Phil
7
@ m3th0dman Das sind ganz normale Typen. Listen haben nichts Besonderes, außer ein paar synaktische Feinheiten. Sie können auf einfache Weise Ihren eigenen algebraischen Datentyp definieren, der bis auf die Literal-Syntax und die Namen der Konstruktoren dem integrierten Listentyp entspricht.
SEPP2K 08.10.12

Antworten:

63

("Java", wie hier verwendet, ist als Standard Java SE 7 definiert . "Haskell", wie hier verwendet, ist als Standard Haskell 2010 definiert .)

Dinge, die Javas Typsystem hat, aber Haskells nicht:

  • nomineller Subtyp Polymorphismus
  • teilweise Laufzeit Typinformationen

Dinge, die das Typensystem von Haskell hat, aber das von Java nicht:

  • begrenzter Ad-hoc-Polymorphismus
    • führt zu "Constraint-basiertem" Subtyp-Polymorphismus
  • höherwertiger parametrischer Polymorphismus
  • Haupttypisierung

BEARBEITEN:

Beispiele für jeden der oben aufgeführten Punkte:

Einzigartig für Java (im Vergleich zu Haskell)

Nomineller Subtyp Polymorphismus

/* declare explicit subtypes (limited multiple inheritance is allowed) */
abstract class MyList extends AbstractList<String> implements RandomAccess {

    /* specify a type's additional initialization requirements */
    public MyList(elem1: String) {
        super() /* explicit call to a supertype's implementation */
        this.add(elem1) /* might be overridden in a subtype of this type */
    }

}

/* use a type as one of its supertypes (implicit upcasting) */
List<String> l = new ArrayList<>() /* some inference is available for generics */

Informationen zum Typ der Teillaufzeit

/* find the outermost actual type of a value at runtime */
Class<?> c = l.getClass // will be 'java.util.ArrayList'

/* query the relationship between runtime and compile-time types */
Boolean b = l instanceOf MyList // will be 'false'

Einzigartig für Haskell (im Vergleich zu Java)

Eingeschränkter Ad-hoc-Polymorphismus

-- declare a parametrized bound
class A t where
  -- provide a function via this bound
  tInt :: t Int
  -- require other bounds within the functions provided by this bound
  mtInt :: Monad m => m (t Int)
  mtInt = return tInt -- define bound-provided functions via other bound-provided functions

-- fullfill a bound
instance A Maybe where
  tInt = Just 5
  mtInt = return Nothing -- override defaults

-- require exactly the bounds you need (ideally)
tString :: (Functor t, A t) => t String
tString = fmap show tInt -- use bounds that are implied by a concrete type (e.g., "Show Int")

Polymorphismus des Subtyps "Constraint-based" (basierend auf begrenztem Ad-hoc-Polymorphismus)

-- declare that a bound implies other bounds (introduce a subbound)
class (A t, Applicative t) => B t where -- bounds don't have to provide functions

-- use multiple bounds (intersection types in the context, union types in the full type)
mtString :: (Monad m, B t) => m (t String)
mtString = return mtInt -- use a bound that is implied by another bound (implicit upcasting)

optString :: Maybe String
optString = join mtString -- full types are contravariant in their contexts

Höherwertiger parametrischer Polymorphismus

-- parametrize types over type variables that are themselves parametrized
data OneOrTwoTs t x = OneVariableT (t x) | TwoFixedTs (t Int) (t String)

-- bounds can be higher-kinded, too
class MonadStrip s where
  -- use arbitrarily nested higher-kinded type variables
  strip :: (Monad m, MonadTrans t) => s t m a -> t m a -> m a

Haupttypisierung

Es ist schwierig, ein direktes Beispiel dafür zu geben, aber es bedeutet, dass jeder Ausdruck genau einen maximal allgemeinen Typ (seinen Haupttyp genannt ) hat, der als kanonischer Typ dieses Ausdrucks betrachtet wird. In Bezug auf den Polymorphismus des Subtyps "Constraint-based" (siehe oben) ist der Haupttyp eines Ausdrucks der eindeutige Subtyp jedes möglichen Typs, als den dieser Ausdruck verwendet werden kann. Das Vorhandensein von Principal Typing in (nicht erweitertem) Haskell ermöglicht eine vollständige Typinferenz (dh eine erfolgreiche Typinferenz für jeden Ausdruck, ohne dass Typanmerkungen erforderlich sind). Erweiterungen, die die Haupttypisierung unterbrechen (von denen es viele gibt), unterbrechen auch die Vollständigkeit der Typinferenz.

Pthariens Flamme
quelle
7
Nicht lals einzelne Buchstabenvariable verwenden, es ist SEHR schwer zu unterscheiden 1!
recursion.ninja
5
Es kann erwähnenswert sein, dass Sie, obwohl Sie absolut Recht haben, dass Java über einige Laufzeit-Typinformationen verfügt und Haskell nicht, die typisierbare Typklasse in Haskell verwenden können, um etwas bereitzustellen, das sich für viele Typen wie Laufzeit-Typinformationen verhält (mit neuerem PolyKinded) Klassen auf dem Weg, es werden alle Typen iirc sein), obwohl ich denke, es hängt von der Situation ab, ob es tatsächlich Typinformationen zur Laufzeit übergibt oder nicht.
3
@ DarkOtter Mir ist bekannt Typeable, aber Haskell 2010 hat es nicht (vielleicht wird es Haskell 2014?).
Pthariens Flamme
5
Was ist mit (geschlossenen) Summentypen? Sie sind einer der wichtigsten Mechanismen für die Codierung von Einschränkungen.
Tibbe
3
Nullability? Solidität (keine Kovarianzschwelle)? Geschlossene Summentypen / Musterübereinstimmungen? Diese Antwort ist viel zu eng
Peaker
32

Javas Typensystem weist keinen höherwertigen Polymorphismus auf. Haskells Typensystem hat es.

Mit anderen Worten: In Java können Typkonstruktoren über Typen abstrahieren, nicht jedoch über Typkonstruktoren, wohingegen in Haskell Typkonstruktoren über Typkonstruktoren und Typen abstrahieren können.

Auf Englisch: In Java kann ein generischer Typ keinen anderen generischen Typ aufnehmen und parametrisieren.

public void <Foo> nonsense(Foo<Integer> i, Foo<String> j)

In Haskell ist das ganz einfach

higherKinded :: Functor f => f Int -> f String
higherKinded = fmap show
Jörg W. Mittag
quelle
28
Stört es Sie, diesmal wieder auf Englisch bei uns vorbeizuschauen? : P
Mason Wheeler
8
@ Matt: Als Beispiel kann ich schreibe dies nicht in Java, aber ich kann das Äquivalent in Haskell schreiben: <T<_> extends Collection> T<Integer> convertStringsToInts(T<string> strings). Die Idee hier wäre, dass wenn jemand es so nennt, dass convertStringsToInts<ArrayList>es eine Arrayliste von Strings nimmt und eine Arrayliste von ganzen Zahlen zurückgibt. Und wenn sie stattdessen verwendet werden convertStringsToInts<LinkedList>, ist dies auch bei verknüpften Listen der Fall.
8.
8
Ist das nicht eher ein höherwertiger Polymorphismus als Rang 1 gegen n?
Adam
8
@ JörgWMittag: Mein Verständnis ist, dass es um höherrangigen Polymorphismus geht, wo man das forallin seine Typen setzen kann. In Haskell ist ein Typ a -> bimplizit forall a. forall b. a -> b. Mit einer Erweiterung können Sie diese forallexplizit machen und verschieben.
Tikhon Jelvis
8
@Adam ist recht: Höherer Rang und höheres kinded sind total unterschiedlich. GHC kann mit einigen Spracherweiterungen auch höherrangige Typen (dh alle Typen) ausführen. Java kennt weder höherwertige noch höherrangige Typen.
Ingo
11

Ergänzend zu den anderen Antworten verfügt das Typensystem von Haskell über keine Untertypisierung , während objektorientierte Sprachen wie Java eingegeben werden.

In der Theorie der Programmiersprache ist Subtypisierung (auch Subtyp-Polymorphismus oder Inklusions-Polymorphismus ) eine Form des Typ-Polymorphismus, bei der ein Subtyp ein Datentyp ist, der mit einem anderen Datentyp (dem Supertyp ) durch einen Begriff der Substituierbarkeit verwandt ist , dh, dass Programmelemente, typischerweise Subroutinen oder Funktionen, die geschrieben wurden, um Elemente des Supertyps zu bearbeiten, können auch Elemente des Subtyps bearbeiten. Wenn S ein Subtyp von T ist, wird die Subtyp-Beziehung oft mit S <: T geschrieben, um zu bedeuten, dass jeder Term vom Typ S in einem Kontext, in dem S sicher verwendet werden kann, verwendet werden kannein Begriff vom Typ T wird erwartet. Die genaue Semantik der Subtypisierung hängt entscheidend von den Einzelheiten dessen ab, was "sicher in einem Kontext wo verwendet" in einer gegebenen Programmiersprache bedeutet. Das Typsystem einer Programmiersprache definiert im Wesentlichen eine eigene Subtypisierungsrelation, die durchaus trivial sein kann.

Aufgrund der Untertypisierungsbeziehung kann ein Begriff zu mehr als einem Typ gehören. Subtypisierung ist daher eine Form des Typpolymorphismus. In der objektorientierten Programmierung bezieht sich der Begriff "Polymorphismus" üblicherweise nur auf diesen Subtyp Polymorphismus , während die Techniken des parametrischen Polymorphismus als generische Programmierung betrachtet würden ...

Petr Pudlák
quelle
4
Dies bedeutet jedoch nicht, dass Sie keinen Ad-hoc-Polymorphismus erhalten. Sie tun dies nur in einer anderen Form (Typklassen statt Subtyp-Polymorphismus).
3
Subclassing ist kein Subtyping!
Frank Shearar
8

Eine Sache, die bisher niemand erwähnt hat, ist die Typinferenz: Ein Haskell-Compiler kann normalerweise auf die Art der Ausdrücke schließen, aber Sie müssen dem Java-Compiler Ihre Typen im Detail mitteilen. Streng genommen ist dies ein Merkmal des Compilers, aber das Design des Sprach- und Typsystems bestimmt, ob eine Typinferenz möglich ist. Insbesondere interagiert die Typinferenz schlecht mit Javas Subtyp-Polymorphismus und Ad-hoc-Überladung. Im Gegensatz dazu bemühen sich die Designer von Haskell, keine Features einzuführen, die sich auf die Typinferenz auswirken.

Eine andere Sache, die die Leute bisher noch nicht erwähnt haben, sind algebraische Datentypen. Das heißt, die Fähigkeit, Typen aus Summen ('oder') und Produkten ('und') anderer Typen zu konstruieren. Java-Klassen eignen sich gut für Produkte (Feld a und Feld b). Aber sie rechnen nicht wirklich (zB Feld a ODER Feld b). Scala muss dies als mehrere Fallklassen kodieren, was nicht ganz dasselbe ist. Und während es für Scala funktioniert, ist es ein bisschen schwierig zu sagen, dass Java es hat.

Haskell kann auch Funktionstypen mit dem Funktionskonstruktor -> erstellen. Während Javas Methoden Typensignaturen haben, können Sie diese nicht kombinieren.

Das Typensystem von Java ermöglicht eine Art Modularität , die Haskell nicht hat. Es wird eine Weile dauern, bis es ein OSGi für Haskell gibt.

GarethR
quelle
1
@MattFenwick, ich habe den 3. Absatz auf der Grundlage Ihres Feedbacks geändert. Die beiden Arten von Systemen behandeln Funktionen sehr unterschiedlich.
GarethR
Ich würde ADTs nicht als Merkmal des Typsystems bezeichnen. Sie können sie mit OO-Wrappern vollständig (wenn auch umständlich) emulieren.
linksum den
@ Linksaroundabout Ich denke, das ist wohl. Zum Beispiel könnte es Dinge geben, die für ein Typensystem einer Sprache typisch sind, die aber mit Entwurfsmustern in einer anderen Sprache implementiert werden könnten. Offensichtlich ist der Entwurfsmuster-Weg im Vergleich zu einem einheimischen ein Workaround. Die Problemumgehung aufgrund eines schwächeren Typsystems.
Hi-Angel
Die gewählte Antwort erwähnte "Vollständige Typinferenz" im Abschnitt "Haupttypisierung". Java kann gewissermaßen Summen mit Subtypen und Laufzeittypinformationen emulieren, aber wie Sie sagen, ist dies nicht dasselbe, da die Summe kein ganzheitliches Attribut des Typsystems ist.
Shelby Moore III