Εξαντλητικότητα Ταιριάσματος Προτύπων Για Γενικευμένους Αλγεβρικούς Τύπους Δεδομένων

Abstract

Ο Glasgow Haskell Compiler (GHC) είναι αυτή τη στιγμή ο κορυφαίος μεταγλωττιστής για τη γλώσσα Haskell. Πέραν του προτύπου της Haskell 2010, υποστηρίζει πολυάριθμες επεκτάσεις, συμπεριλαμβανομένων των Γενικευμένων Αλγεβρικών Τύπων. Δυστυχώς, ενώ οι γενικευμένοι αλγεβρικοί τύποι έχουν ενσωματωθεί πλήρως στο σύστημα τύπων της Haskell, ο εντοπισμός μη εξαντλητικών ταιριασμάτων προτύπων σε περιπτώσεις που περιέχουν γενικευμένους αλγεβρικούς τύπους αποδείχτηκε ελλιπής.Ο στόχος αυτής της διπλωματικής εστιάζει στο σχεδιασμό ενός μηχανισμού για τον εντοπισμό μη εξαντλητικών ταιριασμάτων προτύπων, ο οποίος θα διαχειρίζεται τόσο ταιριάσματα προτύπων επί Αλγεβρικών Τύπων όσο και Γενικευμένων Αλγεβρικών Τύπων, με ενιαίο τρόπο. Ο βασικός μας ισχυρισμός είναι ότι ο έλεγχος της εξαντλητικότητας ταιριάσματος προτύπων θα πρέπει να αντιμετωπίζεται πλέον περισσότερο ως σημασιολογικό, παρά συντακτικό ζήτημα. Αντί να είναι διαχωρισμένο απο τον έλεγχο τύπων, θεωρούμε πως πρέπει να ενσωματωθεί σε αυτόν, έτσι ώστε να είναι δυνατή η αξιοποίηση των τοπικών περιορισμών που εισαγάγονται απο ταιριάσματα γενικευμένων αλγεβρικών τύπων.Στην παρούσα εργασία παρουσιάζουμε έναν τέτοιο μηχανισμό, ως επέκταση του τρέχοντος, ο οποίος είναι εύληπτος, εύκολα υλοποιήσιμος και αποδοτικός. Εκτός απο το σχεδιασμό, υλοποιήσαμε μερικώς την επέκταση μας στον GHC, συνεπώς παραθέτουμε και τεχνικές πληροφορίες, σχετικά με την υλοποίηση μας. Τέλος, συγκρίνουμε την απόδοση και τα αποτελέσματα που δίνει ο GHC με και χωρίς την επέκτασή μας, δείχνοντας ότι ο μηχανισμός μας είναι πράγματι ορθός και αποδοτικός, με αποτέλεσμα να μπορεί να ενσωματωθεί στο μέλλον στον εν λόγω μεταγλωττιστή.