Στυλ περάσματος συνεχειών

Στο συναρτησιακό προγραμματισμό, το στυλ περάσματος συνεχειών (continuation-passing style, CPS) είναι ένα στυλ προγραμματισμού στο οποίο η ροή του ελέγχου δίνεται ρητά από το πέρασμα συνεχειών.

Ετυμολογία

Ο Gerald Jay Sussman και ο Guy L. Steele, Jr. συνέλαβαν τη φράση "continuation-passing style" στο κείμενό τους AI Memo 349 (1975), ορίζοντας την πρώτη έκδοση της γλώσσας προγραμματισμού Scheme.

Εισαγωγή

Αντί να "επιστρέφει" τιμές όπως στο γνώριμο ευθύ στυλ προγραμματισμού, μια συνάρτηση που είναι γραμμένη σε στυλ περάσματος συνεχειών παίρνει ρητά μια παράμετρο που είναι η "συνέχεια", δηλ. μια συνάρτηση που πρόκειται να λάβει το αποτέλεσμα του υπολογισμού της αρχικής συνάρτησης. Όμοια, όταν μια υπορουτίνα καλείται μέσα σε μια συνάρτηση γραμμένη σε CPS, η καλούσα συνάρτηση πρέπει να δώσει μια διαδικασία που θα κληθεί με το αποτέλεσμα της υπορουτίνας. Η συγγραφή κώδικα με αυτή τη μορφή κάνει ρητά πολλά πράγματα που είναι έμμεσα στο ευθύ στυλ. Σε αυτά περιλαμβάνονται: η επιστροφή από μια διαδικασία, που εμφανίζεται ως κλήση κάποιας συνέχειας, οι ενδιάμεσες τιμές, που αποκτούν όλες πια όνομα, η σειρά με την οποία αποτιμώνται οι παράμετροι, που γράφεται ρητά, και οι κλήσεις ουράς (tail calls), που απλά καλούν μια διαδικασία με την ίδια συνέχεια που δόθηκε στην καλούσα συνάρτηση.
Ένα πρόγραμμα μπορεί να μετατραπεί αυτόματα από ευθύ στυλ σε CPS. Οι μεταγλωττιστές συναρτησιακών και λογικών γλωσσών συχνά χρησιμοποιούν το CPS ως ενδιάμεση αναπαράσταση, όπου ένας μεταγλωττιστής για προστακτικές ή διαδικαστικές γλώσσες προγραμματισμού θα χρησιμοποιούσε μορφή στατικής μοναδικής ανάθεσης (static single assignment form, SSA) - ισχύει όμως ότι η SSA και το CPS είναι ισοδύναμα  (τεχνικά υπάρχουν δομές του CPS που δε μεταφράζονται σε SSA, αλλά δε συναντώνται στην πράξη). Οι μεταγλωττιστές για συναρτησιακές γλώσσες προγραμματισμού χρησιμοποιούν τη μορφή ANF (Administrative Normal Form) αντί ή σε συνδυασμό με το CPS. Το CPS χρησιμοποιείται περισσότερο από μεταγλωττιστές παρά από προγραμματιστές ως τοπικό ή καθολικό στυλ.

Συνέχειες και αντικείμενα

Ο προγραμματισμός με συνέχειες είναι χρήσιμος επειδή ο κώδικας που κάνει την κλήση δε χρειάζεται να περιμένει μέχρι να τερματίσει η κλήση. Για παράδειγμα, στον προγραμματισμό γραφικών διασυνδέσεων χρήστη (User Interface, UI), μια ρουτίνα μπορεί να ορίσει τα πεδία ενός παραθύρου διαλόγου και να τα δώσει, μαζί με μια συνέχεια, στο πλαίσιο που αναλαμβάνει τη διασύνδεση. Όταν ο χρήστης πατήσει το κουμπί "OK", το πλαίσιο καλεί τη συνάρτηση της συνέχειας με τα ενημερωμένα πεδία. Αν και αυτό το στυλ προγραμματισμού χρησιμοποιεί συνέχειες, δεν είναι πλήρως CPS.
function Confirm_name(){
    fields.name = name;
    framework.Show_dialog_box(fields, Confirm_name_continuation);}function Confirm_name_continuation(fields){
    name = fields.name;}
Μια παρόμοια ιδέα μπορεί να χρησιμοποιηθεί όταν η συνάρτηση πρέπει να εκτελεστεί σε διαφορετικό νήμα ή σε διαφορετικό επεξεργαστή. Η συνάρτηση που καλείται μπορεί να εκτελεστεί τότε σε ένα "νήμα-εργάτη" (worker thread), καλώντας μετά τη συνάρτηση της συνέχειας στο αρχικό νήμα με τα αποτελέσματα του νήματος-εργάτη. Για παράδειγμα, στη Java αυτό μπορεί να γίνει με τη χρήση της βιβλιοθήκης Swing:
void buttonHandler() {
    // Εκτελείται στο νήμα του Swing για το UI.
    // Μπορούμε να έχουμε πρόσβαση σε πολλά στοιχεία του UI και στα δεδομένα τους.
    final int parameter = getField();

    new Thread(new Runnable() {
        public void run() {
            // Βρισκόμαστε σε ξεχωριστό νήμα.
            // Μπορούμε να συνδεθούμε σε κάποια βάση δεδομένων ή σε
            // κάποιο πόρο που να μας μπλοκάρει, όπως το δίκτυο, για να
            // ζητήσουμε δεδομένα.
            final int result = lookup(parameter);

            javax.swing.SwingUtilities.invokeLater(new Runnable() {
                public void run() {
                    // Είμαστε πάλι στο νήμα του UI και μπορούμε να χρησιμοποιήσουμε τα
                    // δεδομένα που λάβαμε για να γεμίσουμε τα στοιχεία του UI.
                    setField(result);
                }
            });
        }
    }).start();}

CPS και κλήσεις ουράς

Στο CPS δεν υπάρχουν έμμεσες συνέχειες — κάθε κλήση είναι κλήση ουράς (tail call). Αυτό είναι φυσιολογικό, επειδή πάντα περνιέται μια συνέχεια. Αυτό σημαίνει ότι η χρήση CPS χωρίς βελτιστοποίηση κλήσης ουράς (tail call optimization, TCO) θα έχει ως συνέπεια να μεγαλώνει, τόσο η συνέχεια που κατασκευάζεται στη διάρκεια των αναδρομικών κλήσεων, (για κλήσεις που δεν είναι τύπου ουράς, αλλιώς μένει ίδια), όσο και της ίδιας της στοίβας της συνάρτησης. (Αυτό συνήθως δεν είναι επιθυμητό αλλά έχει κάποιες χρήσεις, για παράδειγμα ο μεταγλωττιστής της Chicken Scheme το χρησιμοποιεί με ιδιαίτερο τρόπο).
Ο συνδυασμός CPS και TCO δε χρειάζεται έμμεση επιστροφή από κλήση συνάρτησης, επομένως δε χρειάζεται και στοίβα στο χρόνο εκτέλεσης. Αυτό χρησιμοποιείται από πολλούς μεταγλωττιστές και διερμηνείς συναρτησιακών γλωσσών ως βασικό στοιχείο της λειτουργίας τους.

Χρήση και υλοποίηση

Το στυλ περάσματος συνεχειών μπορεί να χρησιμοποιηθεί για να υλοποιηθούν οι συνέχειες και οι τελεστές της ροής ελέγχου (control flow) στις συναρτησιακές γλώσσες που δεν έχουν συνέχειες ως αντικείμενα πρώτης τάξης (first-class continuations) αλλά έχουν συναρτήσεις ως αντικείμενα πρώτης τάξης και βελτιστοποίηση κλήσης ουράς. Όταν δεν υπάρχει η βελτιστοποίηση, μπορούν να χρησιμοποιηθούν τεχνικές όπως τα τραμπολίνα (trampolining), δηλ. η χρήση επανάληψης που διαδοχικά καλεί συναρτήσεις που επιστρέφουν thunks. Επίσης, χωρίς συναρτήσεις πρώτης τάξης, οι κλήσεις ουράς μπορούν να μετατραπούν σε εντολές goto σε μια επανάληψη σαν την παραπάνω.
Η συγγραφή κώδικα σε CPS, αν και είναι δυνατή, είναι δύσκολη και μπορεί να οδηγήσει σε λάθη. Για αυτό το λόγο υπάρχουν διάφορες μεταφράσεις, συνήθως σαν ένα ή δύο περάσματα από τον καθαρό λ-λογισμό, που μετατρέπουν εκφράσεις που βρίσκονται σε ευθύ στυλ, σε εκφράσεις σε CPS. Η συγγραφή σε κώδικα σε στυλ τραμπολίνου είναι πολύ δύσκολη, συνήθως γίνεται αυτόματα από κάποιο μετασχηματισμό, για παράδειγμα κατά τη διάρκεια της μεταγλώττισης.
Οι συναρτήσεις που χρησιμοποιούν πάνω από μια συνέχεια μπορούν να οριστούν έτσι ώστε να αντιστοιχούν σε διάφορους τρόπους ελέγχου της ροής, όπως το εξής παράδειγμα σε Scheme:
(define (/& x y ok err)
 (=& y 0.0 (lambda (b)
            (if b
                (err "div by zero!" x y)
                (ok (/ x y))))))

Χρήση σε άλλες επιστήμες

Εκτός από την επιστήμη υπολογιστών, το στυλ περάσματος συνεχειών έχει γενικότερο ενδιαφέρον ως εναλλακτική μέθοδος για τη σύνθεση πολύπλοκων εκφράσεων από απλούστερες. Για παράδειγμα, στη σημασιολογία της γλωσσολογίας, ο Chris Barker και οι συνεργάτες του πρότειναν ότι η έκφραση του νοήματος προτάσεων μέσω CPS θα μπορούσε να εξηγήσει κάποια φαινόμενα της φυσικής γλώσσας .
Στα μαθηματικά, ο ισομορφισμός Curry-Howard μεταξύ προγραμμάτων και μαθηματικών αποδείξεων συσχετίζει τη μετάφραση του στυλ περάσματος συνεχειών με μια παραλλαγή της ενσωμάτωσης με διπλή άρνηση (double-negation embedding) της κλασικής λογικής στην ιντουισιονιστική (κατασκευαστική) λογική. Σε αντίθεση με την απλή μετάφραση διπλής άρνησης, που αντιστοιχεί ατομικές προτάσεις p σε προτάσεις ((p → ⊥) → ⊥), το στυλ περάσματος συνεχειών αντικαθιστά το ⊥ από τον τύπο της τελκής έκφρασης. Το αποτέλεσμα τότε δίνεται από το πέρασμα της ταυτοτικής συνάρτησης ως συνέχεια στην έκφραση CPS, όπως στο παραπάνω παράδειγμα.
Η ίδια η κλασική λογική έχει απευθείας σχέση με το χειρισμό της συνέχειας ενός προγράμματος, όπως στον τελεστή ελέγχου call-with-current-continuation της Scheme.