Πρόβλημα Funarg
Ο τεχνικός όρος funarg είναι συντομογραφία της αγγλικής έκφρασης «functional argument» («συναρτησιακή παράμετρος»). Στη θεωρητική πληροφορική το λεγόμενο πρόβλημα funarg αναφέρεται στη δυσκολία υλοποίησης συναρτήσεων σαν αντικείμενα πρώτης τάξης σε υλοποιήσεις γλωσσών βασισμένες σε στοίβα.
Η δυσκολία εμφανίζεται μόνο όταν το σώμα μιας συνάρτησης αναφέρεται απευθείας (δηλ. όχι μέσω περάσματος παραμέτρων) σε αναγνωριστικά που έχουν οριστεί στο περιβάλλον που ορίστηκε η συνάρτηση, αλλά όχι στο περιβάλλον που αυτή καλείται.[1] Γενικά υπάρχουν δύο βασικές λύσεις: είτε να απαγορευτούν αυτές οι αναφορές, ή να δημιουργηθούν κλεισίματα.[2]
Υπάρχουν δύο εκδοχές του προβλήματος funarg. Το πρόβλημα funarg προς τα πάνω (upwards funarg problem) προκύπτει από την επιστροφή (ή διάδοση με κάποιον άλλον τρόπο "προς τα πάνω") μιας συνάρτησης από μια κλήση κάποιας άλλης συνάρτησης. Το πρόβλημα funarg προς τα κάτω (downwards funarg problem) προκύπτει από το πέρασμα μιας συνάρτησης σαν παράμετρο σε μια κλήση άλλης συνάρτησης.
Πρόβλημα funarg προς τα πάνω Επεξεργασία
Όταν μια συνάρτηση καλεί μια άλλη κατά την εκτέλεση ενός προγράμματος, η τοπική κατάσταση του κώδικα που κάνει την κλήση (συμπεριλαμβανομένων των παραμέτρων και των τοπικών μεταβλητών) πρέπει να διατηρηθεί ώστε η εκτέλεση να συνεχιστεί όταν η συνάρτηση που καλείται επιστρέψει. Στα περισσότερα μεταγλωττισμένα προγράμματα, αυτή η τοπική κατάσταση αποθηκεύεται στη στοίβα κλήσεων, σε μια δομή δεδομένων που ονομάζεται εγγραφή δραστηριοποίησης ή πλαίσιο στοίβας. Αυτό το πλαίσιο στοίβας τοποθετείται στην κορυφή της στοίβας, ή δεσμεύεται χώρος για αυτό, όταν καλείται μια συνάρτηση, και αφαιρείται από την κορυφή, ή αποδεσμεύεται ο χώρος του, όταν η συνάρτηση επιστρέψει. Το πρόβλημα funarg προς τα πάνω εμφανίζεται όταν η συνάρτηση που κάνει την κλήση αναφέρεται σε κατάσταση μιας συνάρτησης που έχει κληθεί και έχει επιστρέψει. Επομένως, η εγγραφή δραστηριοποίησης που περιλαμβάνει τις μεταβλητές κατάστασης της συνάρτησης που κλήθηκε δεν πρέπει να διαγραφεί όταν η συνάρτηση επιστρέψει, με αποτέλεσμα να παραβιάζεται το παράδειγμα κλήσης συνάρτησης με στοίβα.
Μια λύση στο πρόβλημα funarg προς τα πάνω είναι να αποθηκεύονται απλά όλες οι εγγραφές δραστηριοποίησης στο σωρό αντί για τη στοίβα, και να χρησιμοποιείται κάποια μορφή συλλογής απορριμμάτων) ή καταμέτρησης αναφορών για την αποδέσμευση της μνήμης των εγγραφών δραστηριοποίησης που δε χρειάζονται άλλο. Η διαχείριση των εγγραφών δραστηριοποίησης με σωρό είναι λιγότερο αποδοτική από αυτή με στοίβα, και άρα αυτή η στρατηγική μπορεί να μειώσει σημαντικά την απόδοση του προγράμματος. Επιπλέον, επειδή οι πιο πολλές συναρτήσεις σε ένα πρόγραμμα συνήθως δε δημιουργούν παραμέτρους "funarg" προς τα πάνω, η επιβάρυνση αυτή συνήθως δε χρειάζεται.
Κάποιοι μεταγλωττιστές με έμφαση στην αποδοτικότητα, χρησιμοποιούν μια υβριδική προσέγγιση, στην οποία οι εγγραφές δραστηριοποίησης μιας συνάρτησης δεσμεύονται στη στοίβα αν ο μεταγλωττιστής μπορεί να βρει, μέσω στατικής ανάλυσης, ότι η συνάρτηση δε δημιουργεί funarg προς τα πάνω. Αλλιώς, οι εγγραφές δραστηριοποίησης δεσμεύονται στο σωρό.
Παράδειγμα Επεξεργασία
Ο παρακάτω εμπνευσμένος από Haskell ψευδοκώδικας ορίζει τη σύνθεση συναρτήσεων:
compose f g = λx → f (g x)
Ο τελεστής λ κατασκευάζει μια νέα συνάρτηση, η οποία -- σε αυτήν την περίπτωση -- έχει μόνο μια πράμετρο, τη x, και επιστρέφει το αποτέλεσμα της αρχικής εφαρμογής της g στη x και στη συνέχεια της εφαρμογής της f σε αυτό το αποτέλεσμα. Αυτή η συνάρτηση λ διατηρεί τις συναρτήσεις f και g (ή δείκτες σε αυτές) σαν εσωτερική κατάσταση.
Το πρόβλημα που εμφανίζεται σε αυτήν την περίπτωση εμφανίζεται αν η συνάρτηση compose δεσμεύει χώρο για τις μεταβλητές παραμέτρους f και g στη στοίβα. Όταν η compose επιστρέψει, το πλαίσιο στοίβας που περιέχει τις f και g διαγράφεται. Όταν η εσωτερική συνάρτηση λx προσπαθήσει να έχει πρόσβαση στη g, θα καταλήξει σε μια περιοχή της μνήμης που έχει διαγραφεί.
Πρόβλημα funarg προς τα κάτω Επεξεργασία
Ένα funarg προς τα κάτω μπορεί επίσης να αναφέρεται στην κατάσταση μιας συνάρτησης όταν αυτή δεν εκτελείται. Επειδή όμως, εξ ορισμού, η παρουσία ενός funarg προς τα κάτω περιέχεται στην εκτέλεση της συνάρτησης που το δημιούργησε, η εγγραφή δραστηριοποίησης για τη συνάρτηση μπορεί συνήθως να αποθηκευτεί στη στοίβα. Όμως, η ύπαρξη funarg προς τα κάτω προϋποθέτει μια δενδρική δομή κλεισιμάτων και εγγραφών δραστηριοποίησης που μπορεί να περιπλέξουν την κατανόηση της κατάστασης του προγράμματος.
Το πρόβλημα funarg προς τα κάτω περιπλέκει την αποδοτική μεταγλώττιση της αναδρομής ουράς και του κώδικα σε στυλ περάσματος συνεχειών. Σε αυτές τις ειδικές περιπτώσεις, ο προγραμματιστής (συνήθως) θέλει η συνάρτηση να εκτελείται σε περιορισμένο χώρο στοίβας, και η "γρηγορότερη" συμπεριφορά μπορεί να μην είναι επιθυμητή.
Πρακτικές επιπτώσεις Επεξεργασία
Ιστορικά, το πρόβλημα funarg προς τα πάνω έχει αποδειχτεί πιο δύσκολο. Για παράδειγμα, η γλώσσα προγραμματισμού Pascal επιτρέπει σε συναρτήσεις να περνιούνται σαν παράμετροι αλλά όχι να επιστρέφονται σαν αποτελέσματα και οι υλοποιήσεις της Pascal πρέπει να χειρίζονται μόνο το πρόβλημα funarg προς τα κάτω αλλά όχι και αυτό προς τα πάνω. Η γλώσσα Oberon (απόγονος της Pascal) επιτρέπει συναρτήσεις σαν παραμέτρους και σαν αποτελέσματα αλλά η συνάρτηση που ανατίθεται πρέπει να μην είναι εμφωλευμένη. Η γλώσσα προγραμματισμού C ιστορικά έχει αποφύγει τη βασική δυσκολία του προβλήματος funarg απαγορεύοντας ορισμούς συναρτήσεων μέσα σε άλλες συναρτήσεις: επειδή το περιβάλλον κάθε συνάρτησης είναι ίδιο, και περιέχει μόνο καθολικές και στατικά δεσμευμένες μεταβλητές και συναρτήσεις, ένας δείκτης στον κώδικα της συνάρτησης την περιγράφει απόλυτα. Η Apple έχει προτείνει και έχει υλοποιήσει μια σύνταξη για κλεισίματα για τη C που λύνει το πρόβλημα funarg προς τα πάνω, μετακινώντας δυναμικά τα κλεισίματα από τη στοίβα στο σωρό, όταν χρειάζεται. Η γλώσσα προγραμματισμού Java το χειρίζεται απαιτώντας το περιβάλλον που χρησιμοποιείται από εμφωλευμένες συναρτήσεις σε ανώνυμες εσωτερικές κλάσεις να δηλώνεται πάντα σαν final.
Στις συναρτησιακές γλώσσες, οι συναρτήσεις είναι τιμές πρώτης τάξης και μπορούν να περαστούν παντού. Επομένως, οι υλοποιήσεις της Scheme ή της Standard ML πρέπει να αντιμετωπίζουν τόσο το πρόβλημα Funarg προς τα πάνω, όσο και αυτό προς τα κάτω, κάτι που συνήθως επιτυγχάνεται με την αναπαράσταση των συναρτήσεων με κλεισίματα στο σωρό, όπως έχει ήδη περιγραφεί. Ο μεταγλωττιστής της Objective Caml χρησιμοποιεί μια υβριδική τεχνική (βασισμένη στην ανάλυση προγράμματος) για να μεγιστοποιεί την απόδοσή.
Δείτε επίσης Επεξεργασία
Παραπομπές Επεξεργασία
Εξωτερικί σύνδεσμοι Επεξεργασία
- Joel Moses. The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem. MIT AI Memo 199, 1970. (Αγγλικά)
- Andrew W. Appel, Zhong Shao. An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures. Princeton CS Tech Report TR-450-94, 1994. (Αγγλικά)