Υλοποίηση Συναρτησιακών Γλωσσών Προγραμματισμού Με Το Μετασχηματισμό Διακλαδιζόμενων Διαστάσεων

Abstract

ΠΕΡΙΛΗΨΗΟ συναρτησιακός προγραμματισμός αναπτύχθηκε μέσα από τη μαθηματική θεωρία του λ-λογισμού, που προτάθηκε από τον A. Church στη δεκαετία του 1930. Στις συναρτησιακές γλώσσες, ο προγραμματιστής κωδικοποιεί το πρόβλημα που θέλει να επιλύσει με τη χρήση αναδρομικά ορισμένων συναρτήσεων. Η ανάπτυξη του συναρτησιακού προγραμματισμού έχει παίξει καθοριστικό ρόλο στην εξέλιξη του κλάδου των γλωσσών προγραμματισμού. Επιπλέον, έχει αποτελέσει την κινητήρια δύναμη πίσω από την ανάπτυξη νέων τεχνικών μεταγλώττισης, ισχυρών συστημάτων τύπων και μετασχηματισμών, εργαλείων απόδειξης θεωρημάτων όπως το Coq και το Isabelle, και πολλών άλλων σημαντικών καινοτομιών στο χώρο του προγραμματισμού και της πληροφορικής γενικότερα.H παρούσα διπλωματική εργασία έχει ως θέμα μία εναλλακτική μέθοδο υλοποίησης των συναρτησιακών γλωσσών προγραμματισμού που υποστηρίζουν οκνηρή αποτίμηση καισυναρτήσεις υψηλής τάξης, μέσω απλών νοηματικών γλωσσών προγραμματισμού μηδενικής τάξης. Η εργασία προσβλέπει στη διερεύνηση αυτής της προσέγγισης και στη σύγκρισή της με τις παραδοσιακές, αλλά αρκετά πολύπλοκες, μεθόδους υλοποίησης των συναρτησιακών γλωσσών προγραμματισμού. Στο πλαίσιο της εργασίας, αρχικά κατασκευάστηκε ένας συντακτικός και σημασιολογικός αναλυτής, που ελέγχει αν το αρχικό πρόγραμμα ανήκει στην υψηλότερης τάξης συναρτησιακή γλώσσα HOFL. Στη συνέχεια, το πρόγραμμα τάξης Ν μεταγλωττίζεται από τη HOFL στην υψηλότερης τάξης νοηματική γλώσσα HOIL, χωρίς να τροποποιηθεί η τάξη του. Για τη μείωση της τάξης του προγράμματος HOIL από Ν-στή σε μηδενική, υπεύθυνος είναι ο μετασχηματισμός διακλαδιζόμενων δαστάσεων, που παρουσιάστηκε από τον Α. Yaghi (1984) και τροποιήθηκε, κατόπιν, από τους Π.Ροντογιάννη και W. W. Wadge (1997, 1999). Tελικό αποτέλεσμα του μετασχηματισμού αυτού είναι ένα μηδενικής τάξης πρόγραμμα HOIL, το οποίο μεταφράζεται μετά στημηδενικής τάξης νοηματική γλώσσα ZOIL. Το ZOIL πρόγραμμα μεταγλωττίζεται σε C και, με τη χρήση ενός μεταγλωττιστή της C, καταλήγει σε ένα εκτελέσιμο προς χρήση. Στην παρούσα εργασία, έμφαση έχει δοθεί στο περιβάλλον εκτέλεσης και σε θέματα απόδοσης του τελικού προγράμματος. Επιχειρείται η σύγκριση αυτής της υλοποίησης με παραδοσιακές υλοποιήσεις συναρτησιακών γλωσσών. Παρότι τα αποτελέσματα των μετρήσεων απόδοσης δεν καθιστούν την υλοποίηση αυτή ευνοϊκά συγκρίσιμη με τις πιο προηγμένες παραδοσιακές υλοποιήσεις για προγράμματα υψηλής τάξης, ενισχύουν την άποψη ότι ο μετασχηματισμός διακλαδιζόμενων διαστάσεων μπορεί να συμβάλλει καθοριστικά στην υλοποίηση συναρτησιακών γλωσσών και ενθαρρύνουν περαιτέρω έρευνα.