Παραμετρικός πολυμορφισμός

Στις γλώσσες προγραμματισμού και στη θεωρία τύπων, ο παραμετρικός πολυμορφισμός είναι ένας τρόπος να κάνουμε μια γλώσσα πιο εκφραστική, διατηρώντας ταυτόχρονα την στατική ασφάλεια τύπων. Χρησιμοποιώντας παραμετρικό πολυμορφισμό, μία συνάρτηση ή ένας τύπος δεδομένων μπορεί να γραφεί γενικά ώστε να χειρίζεται πανομοιότυπα τις τιμές ανεξάρτητα από τον τύπο τους[1]. Τέτοιες συναρτήσεις και τύποι δεδομένων ονομάζονται γενικές συναρτήσεις και γενικοί τύποι δεδομένων αντίστοιχα και σχηματίζουν τη βάση του γενικού προγραμματισμού.

Για παράδειγμα, μία συνάρτηση append η οποία συνενώνει δύο λίστες μπορεί να κατασκευαστεί έτσι ώστε να μην νοιάζεται για των τύπο των στοιχείων της λίστας: μπορεί να συνενώσει λίστες ακεραίων, λίστες πραγματικών αριθμών, λίστες συμβολοσειρών κτλ. Έστω ότι η μεταβλητή τύπου a δηλώνει τον τύπο των στοιχείων της λίστας. Τότε η append έχει τύπο [a] × [a] → [a], όπου [a] δηλώνει τον τύπο της λίστας από στοιχεία τύπου a. Λέμε ότι ο τύπος της append είναι παραμετρικός με παράμετρο το a για όλες τις τιμές του a. (Σημειώστε ότι αφού υπάρχει μόνο μία μεταβλητή τύπου, η συνάρτηση δεν μπορεί να εφαρμοστεί σε οποιοδήποτε ζευγάρι λιστών: το ζευγάρι λιστών καθώς επίσης και το αποτέλεσμα, πρέπει να αποτελείται από στοιχεία του ίδιου τύπου.) Οπουδήποτε εφαρμόζεται η συνάρτηση append, αποφασίζεται μία τιμή για το a.

Σύμφωνα με τον Christopher Strachey, ο παραμετρικός πολυμορφισμός μπορεί να αντιπαρατεθεί με τον πολυμορφισμό ad-hoc, ο οποίος ονομάζεται και υπερφόρτωση, και στον οποίο μια πολυμορφική συνάρτηση μπορεί να έχει ένα πλήθος διακριτών και ίσως και ετερογενών υλοποιήσεων ανάλογα με τον τύπο των παραμέτρων στις οποίες εφαρμόζεται. Ως εκ τούτου, ο πολυμορφισμός ad-hoc polymorphism μπορεί γενικά να υποστηρίξει μόνο έναν περιορισμένο αριθμό διακριτών τύπων, καθώς πρέπει να παρέχεται ξεχωριστή υλοποίηση για κάθε τύπο.

Ιστορία

[Επεξεργασία | επεξεργασία κώδικα]

Ο παραμετρικός πολυμορφισμός εισήχθη για πρώτη φορά στις γλώσσες προγραμματισμού στην ML τo 1976. Σήμερα υπάρχει στις Standard ML, OCaml, Ada, Haskell, Visual Prolog και άλλες. Οι γλώσσες Java, C#, Visual Basic .NET και Delphi (CodeGear) πρόσφατα εισήγαγαν, η κάθε μια ξεχωριστά, το χαρακτηριστικό των "generics", για παραμετρικό πολυμορφισμό. Κάποιες υλοποιήσεις του πολυμορφισμού τύπων είναι επιφανειακά όμοιες με τον παραμετρικό πολυμορφισμό καθώς εισάγουν πτυχές ad-hoc. Ένα παράδειγμα είναι η εξειδίκευση προτύπων της C++.

Η πιο γενική μορφή πολυμορφισμού είναι ο μη κατηγορηματικός πολυμορφισμός υψηλής τάξης. Δύο δημοφιλείς περιορισμοί αυτής της μορφής είναι ο πολυμορφισμός περιορισμένης τάξης(για παράδειγμα, βαθμού-1 ή πολυμορφισμός prenex) και ο κατηγορηματικός πολυμορφισμός. Μαζί αυτοί οι δύο περιορισμοί δίνουν τον "κατηγορηματικό πολυμορφισμό prenex", ο οποίος είναι στην ουσία η μορφή πολυμορφισμού που βρίσκεται στην ML και σε κάποιες πρώτες εκδόσεις της Haskell.

Πολυμορφισμός υψηλής τάξης

[Επεξεργασία | επεξεργασία κώδικα]
Τάξης-1 (prenex) πολυμορφισμός
Σε ένα prenex πολυμορφικό σύστημα, οι μεταβλητές τύπων δεν πρέπει να αρχικοποιούνται σε κάποιον πολυμορφικό τύπο. Αυτό μοιάζει πολύ με αυτό που λέγεται "ML-style" ή "Let-πολυμορφισμός" (τεχνικά μιλώντας ο Let-πολυμορφισμός της ML έχει μερικούς ακόμα συντακτικούς περιορισμούς).
Αυτός ο περιορισμός κάνει την διαφορά ανάμεσα στους πολυμορφικούς και στους μη πολυμορφικούς τύπους πολύ σημαντική! Ως εκ τούτου στα κατηγορηματικά συστήματα οι πολυμορφικοί τύποι αναφέρονται μερικές φορές και ως σχήματα τύπων για να τους διακρίνουμε από τους συνήθεις (μονομορφικούς) τύπους, οι οποίοι μερικές φορές καλούνται μονοτύποι'. Μία συνέπεια αυτού είναι ότι όλοι οι τύποι μπορούν να γραφούν σε μια μορφή στην οποία όλοι οι ποσοδείκτες βρίσκονται στην πιο εξωτερική (prenex) θέση.
Για παράδειγμα, θεωρήστε την συνάρτηση append που περιγράφηκε παραπάνω, η οποία έχει τύπο [a] × [a] → [a]! Για να εφαρμόσει κανείς την συνάρτηση αυτή σε ένα ζευγάρι λιστών, η μεταβλητή τύπου a στον τύπο της συνάρτησης πρέπει να αντικατασταθεί με έναν τύπο τέτοιον ώστε ο τύπος των ορισμάτων της συνάρτησης να ταιριάζει με τον τύπο του αποτελέσματος της. Σε ένα μη κατηγορηματικό σύστημα, ο τύπος που αντικαθίσταται μπορεί να οποιοσδήποτε τύπος, συμπεριλαμβανομένου και κάποιου τύπου που είναι και ο ίδιος πολυμορφικός; ως εκ τούτου η append μπορεί να εφαρμοστεί σε ζευγάρια λιστών οποιουδήποτε τύπου- ακόμα και σε λίστες πολυμορφικών συναρτήσεων όπως είναι και στην ίδια την append.
Ο πολυμορφισμός στην γλώσσα ML καθώς επίσης και στις συγγενικές της είναι κατηγορηματικός. Αυτό συμβαίνει διότι η κατηγορηματικότητα, μαζί με άλλους περιορισμούς, κάνει το σύστημα τύπων αρκετά απλό ώστε να γίνει δυνατή η εξαγωγή τύπων. Στις γλώσσες προγραμματισμού στις οποίες είναι απαραίτητη η ρητή επισημείωση τύπων όταν εφαρμόζουμε μία πολυμορφική συνάρτηση, ο περιορισμός την κατηγορηματικότητας είναι λιγότερο σημαντικός. Ως εκ τούτου αυτές οι γλώσσες είναι γενικά μη κατηγορηματικές. Η Haskell επιτυγχάνει να κάνει εξαγωγή τύπων χωρίς την κατηγορηματικότητα αλλά με μερικές επιπλοκές.
Πολυμορφισμός τάξης-k
Για κάποια προκαθορισμένη τιμή k, πολύμορφισμός τάξης-k είναι ένα σύστημα στο οποίο ένας ποσοδείκτης δεν πρέπει να εμφανίζεται στα αριστερά k ή περισσοτέρων δεικτών(όταν ο τύπος απεικονίζεται ως δέντρο).[1]
Η Εξαγωγή τύπων για πολυμορφισμός τάξης-2 είναι αποφάσιμη, αλλά η ανακατασκευή για τάξη-3 και πάνω δεν είναι.[1]
Πολυμορφισμός τάξης-n ("υψηλής τάξης")
Πολυμορφισμός τάξης-n είναι ο πολυμορφισμός στον οποίο οι ποσοδείκετες μπορούν να εμφανίζονται στα αριστερά ενός αυθαίρετου αριθμού δεικτών.

Κατηγορηματικός και μη κατηγορηματικός πολυμορφισμός

[Επεξεργασία | επεξεργασία κώδικα]
Κατηγορηματικός πολυμορφισμός
Στον ένα σύστημα παραμετρικού κατηγορηματικού πολυμορφισμού, ένας τύπος που περιέχει μία μεταβλητή τύπου δεν πρέπει να χρησιμοποιείται με τρόπο ώστε το να είναι πολυμορφικό τύπος.
Μη κατηγορηματικό πολυμορφισμός (πολυμορφισμός "πρώτης κλάσης")
Καλείται επίσης και πολυμορφισμός πρώτης τάξης. Ο μη κατηγορηματικό πολυμορφισμός επιτρέπει μια μεταβλητή σε έναν τύπο να έχει οποιονδήποτε τύπο, συμπεριλαμβανομένων και πολυμορφικών τύπων, όπως και το ίδιο .
Στην θεωρία τύπων, οι πιο συχνά μελετούμενοι μη κατηγορηματικοί λ-λογισμοί με τύπους, στηρίζονται στον λάμδα κύβο, ιδιαίτερα στο σύστημα F. Οι θεωρίες κατηγορηματικών τύπων περιλαμβάνουν την θεωρία τύπων Martin-Löf και την NuPRL.

Περιορισμένος παραμετρικός πολυμορφισμός

[Επεξεργασία | επεξεργασία κώδικα]

Ο Luca Cardelli και ο Wegner αναγνώρισαν το 1985 τα πλεονεκτήματα των περιορισμών στις παραμέτρους τύπων.[2] Πολλές λειτουργίες απαιτούν κάποια γνώση των τύπων δεδομένων αλλά μπορούν σε αντίθετη περίπτωση να δουλέψουν παραμετρικά. Για παράδειγμα, για να ελέγξουμε αν ένα αντικείμενο περιλαμβάνεται σε μία λίστα χρειάζεται να συγκρίνουμε τα αντικείμενα για ισότητα. Στην Standard ML, οι παράμετροι τύπων της μορφής ’’a είναι περιορισμένοι έτσι ώστε να είναι διαθέσιμη η λειτουργία της ισότητας, ως εκ τούτου η συνάρτηση θα είχε τον τύπο ’’a × ’’a list → bool και το ’’a μπορεί να είναι μόνο ένας τύπος με την ισότητα ορισμένη. Στην Haskell, o περιορισμός επιτυγχάνεται απαιτώντας οι τύποι να ανήκουν σε μία κλάση τύπου. Ως εκ τούτου η ίδια συνάρτηση έχει τον τύπο στην Haskell. Στις περισσότερες αντικειμενοστραφείς γλώσσες προγραμματισμού που υποστηρίζουν παραμετρικό πολυμορφισμό, οι παράμετροι μπορούν να περιοριστούν ώστε να είναι υποτύποι κάποιου τύπου (δείτε Πολυμορφισμός υποτύπων και το άρθρο Generic programming).

Παραπομπές

[Επεξεργασία | επεξεργασία κώδικα]
  1. ↑ 1,0 1,1 1,2 Pierce, B. C. 2002 Types and Programming Languages. MIT Press.
  2. ↑ Cardielli, Luca. On Understanding Types, Data Abstraction, and Polymorphism ACM Computing Surveys.

Δείτε επίσης

[Επεξεργασία | επεξεργασία κώδικα]