Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17354
Title: Βελτιστοποίηση κλήσεων αναδρομής ουράς σε συναρτησιακές γλώσσες με πολλαπλά είδη αποτίμησης
Authors: Μπουγουλιάς, Παναγιώτης
Παπασπύρου Νικόλαος
Keywords: Βελτιστοποίηση κλήσης ουράς
οκνηρή αποτίμηση
στατική ανάλυση
διερμηνέας
Issue Date: 28-Aug-2019
Abstract: Οι συναρτησιακές γλώσσες προγραμματισμού είναι διάσημες για τη χρήση αναδρομής αντί για «βρόχους», κάτι που υπάρχει και χαρακτηρίζει τις προστακτικές γλώσσες προγραμματισμού. Ενώ η αναδρομή είναι καλύτερη από τους βρόχους σε ό,τι αφορά την καθαρότητα του κώδικα, καθώς είναι άμεσα συνδεδεμένη με το μαθηματικό ορισμό των συναρτήσεων, έχει ένα βασικό ελάττωμα το οποίο συνδέεται με τη χρήση της μνήμης για την εκτέλεση των προγραμμάτων. Το πρόβλημα αυτό είναι ότι ένας αλγόριθμος που χρησιμοποιεί σταθερό χώρο μνήμης για την εκτέλεση του σε μια προστακτική γλώσσα προγραμματισμού, μπορεί να χρησιμοποιήσει γραμμικό χώρο σε συναρτησιακή, εξαιτίας της αναδρομής. Η λύση αυτού του προβλήματος, που δόθηκε στη δεκαετία του ’70 για τη γλώσσα Scheme, ήταν η χρήση της βελτιστοποίησης κλήσεων ουράς, μια πολύ απλή αλλά, όπως αποδείχθηκε, πολύ αποτελε- σματική τεχνική για την εξάλειψη του παραπάνω προβλήματος. Εκτός από τη Scheme, η βελτιστοποί- ηση αυτή περιλαμβάνεται στις υλοποιήσεις των περισσότερων συναρτησιακών γλωσσών με αυστηρή σημασιολογία, όπως η SML/NJ και η OCaml, καθώς και σε υλοποιήσεις προστακτικών γλωσσών, όπως ο ”Clang” μεταγλωττιστής για τη C/C++, κάτι το οποίο φανερώνει την αξία της συγκεκριμένης βελτιστοποίησης για τη εξάλειψη του κόστους δέσμευσης μνήμης εξαιτίας της αναδρομής. Ο σκοπός αυτής της διπλωματικής διατριβής είναι να ενσωματώσει αυτή την ευρέως γνωστή βελτιστοποίηση μεταγλωττιστή (βελτιστοποίηση κλήσεων ουράς) για συναρτησιακές γλώσσες προ- γραμματισμού με αυστηρή αποτίμηση σε συναρτησιακή γλώσσα προγραμματισμού με πολλαπλά είδη αποτίμησης (κλήση κατά αξία, κλήση κατ’ όνομα και κλήση κατ’ ανάγκη). Συγκεκριμένα στην περί- πτωση της κλήσης κατ’ ανάγκης, οι τιμές που υπακούουν σε αυτή τη σημασιολογία ”δραπετεύουν” από τη εμβέλεια του ονόματος τους πιο εύκολα απ’ ότι στην κλήση κατ’ αξία, με αποτέλεσμα να είναι αρκετά πιο δύσκολο να βρεθούν οι κλήσεις ουράς. Προσθέτοντας επισημειώσεις αυστηρότητας στη γλώσσα, μπλέκοντας δηλαδή την αυστηρή με την οκνηρή σημασιολογία, με παρόμοιο τρόπο όπως τα BangPatterns της Haskell, πραγματοποιούμε μια στατική ανάλυση η οποία εντοπίζει τις βελτιστο- ποιήσιμες κλήσεις ουράς σε μια τέτοια γλώσσα. Στη συνέχεια, υλοποιούμε τη βελτιστοποιήση κατά το χρόνο εκτέλεσης. , μετασχηματίζοντας με κατάλληλο τρόπο το πλαίσιο που αντιπροσωπεύει την αντίστοιχη κλήση συνάρτησης. Με την υλοποίηση αυτή, από την εκτέλεση προγραμμάτων ως ανα- φορά, παρατηρούμε ότι η βελτιστοποίηση μας είτε βελτιώνει το χρόνο εκτέλεσης είτε δεν τον αλλάζει, με αρκετές περιπτώσεις να προσεγγίζουν το σταθερό χώρο μνήμης που προσφέρει η βελτιστοποίηση κλήσης ουράς στις συναρτησιακές γλώσσες προγραμματισμού με αυστηρή σημασιολογία.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17354
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
bougoulias_thesis.pdf436.49 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.