.

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

Ετυμολογία

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

Αντί να "επιστρέφει" τιμές όπως στο γνώριμο ευθύ στυλ προγραμματισμού, μια συνάρτηση που είναι γραμμένη σε στυλ περάσματος συνεχειών παίρνει ρητά μια παράμετρο που είναι η "συνέχεια", δηλ. μια συνάρτηση που πρόκειται να λάβει το αποτέλεσμα του υπολογισμού της αρχικής συνάρτησης. Όμοια, όταν μια υπορουτίνα καλείται μέσα σε μια συνάρτηση γραμμένη σε CPS, η καλούσα συνάρτηση πρέπει να δώσει μια διαδικασία που θα κληθεί με το αποτέλεσμα της υπορουτίνας. Η συγγραφή κώδικα με αυτή τη μορφή κάνει ρητά πολλά πράγματα που είναι έμμεσα στο ευθύ στυλ. Σε αυτά περιλαμβάνονται: η επιστροφή από μια διαδικασία, που εμφανίζεται ως κλήση κάποιας συνέχειας, οι ενδιάμεσες τιμές, που αποκτούν όλες πια όνομα, η σειρά με την οποία αποτιμώνται οι παράμετροι, που γράφεται ρητά, και οι κλήσεις ουράς (tail calls), που απλά καλούν μια διαδικασία με την ίδια συνέχεια που δόθηκε στην καλούσα συνάρτηση.

Ένα πρόγραμμα μπορεί να μετατραπεί αυτόματα από ευθύ στυλ σε CPS. Οι μεταγλωττιστές συναρτησιακών και λογικών γλωσσών συχνά χρησιμοποιούν το CPS ως ενδιάμεση αναπαράσταση, όπου ένας μεταγλωττιστής για προστακτικές ή διαδικαστικές γλώσσες προγραμματισμού θα χρησιμοποιούσε μορφή στατικής μοναδικής ανάθεσης (static single assignment form, SSA) - ισχύει όμως ότι η SSA και το CPS είναι ισοδύναμα [3] (τεχνικά υπάρχουν δομές του CPS που δε μεταφράζονται σε SSA, αλλά δε συναντώνται στην πράξη). Οι μεταγλωττιστές για συναρτησιακές γλώσσες προγραμματισμού χρησιμοποιούν τη μορφή ANF (Administrative Normal Form) αντί ή σε συνδυασμό με το CPS. Το CPS χρησιμοποιείται περισσότερο από μεταγλωττιστές παρά από προγραμματιστές ως τοπικό ή καθολικό στυλ.
Παραδείγματα

Κάθε διαδικασία στο CPS παίρνει μια επιπλέον παράμετρο που αναπαριστά τι πρέπει να γίνει με το αποτέλεσμα που υπολογίζει η συνάρτηση. Αυτό το χαρακτηριστικό, μαζί με ένα περιοριστικό στυλ που απαγορεύει πολλές από τις δομές που χρησιμοποιούνται συχνά, έχουν ως αποτέλεσμα να αποκαλύπτεται η σημασιολογία του προγράμματος και να γίνεται ευκολότερη η ανάλυσή της. Αυτό το στυλ διευκολύνει επίσης την έκφραση ασυνήθιστων δομών, όπως οι εντολές χειρισμού εξαιρέσεων catch/throw και άλλοι τρόποι μη-τοπικής μεταφοράς του ελέγχου.

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

Ευθύ στυλ	Στυλ περάσματος συνεχειών
(define (pyth x y) (sqrt (+ (* x x) (* y y))))	(define (pyth& x y k) (& x x (lambda (x2) (& y y (lambda (y2) (+& x2 y2 (lambda (x2py2) (sqrt& x2py2 k))))))))
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))	(define (factorial& n k) (=& n 0 (lambda (b) (if b (k 1) (-& n 1 (lambda (nm1) (factorial& nm1 (lambda (f) (*& n f k)))))))))
(define (factorial n) (f-aux n 1)) (define (f-aux n a) (if (= n 0) a (f-aux (- n 1) (* n a))))	(define (factorial& n k) (f-aux& n 1 k)) (define (f-aux& n a k) (=& n 0 (lambda (b) (if b (k a) (-& n 1 (lambda (nm1) (*& n a (lambda (nta) (f-aux& nm

Ευθύ στυλ

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

(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))

(define (pyth& x y k)
 (*& x x (lambda (x2)
          (*& y y (lambda (y2)
                   (+& x2 y2 (lambda (x2py2)
                              (sqrt& x2py2 k))))))))

(define (factorial n)
 (if (= n 0)
     1
     (* n (factorial (- n 1)))))

(define (factorial& n k)
  (=& n 0 (lambda (b)
           (if b
               (k 1)
               (-& n 1 (lambda (nm1)
                        (factorial& nm1 (lambda (f)
                                         (*& n f k)))))))))

(define (factorial n) (f-aux n 1))
(define (f-aux n a)
 (if (= n 0)
     a
     (f-aux (- n 1) (* n a))))

(define (factorial& n k) (f-aux& n 1 k))
(define (f-aux& n a k)
 (=& n 0 (lambda (b)
          (if b
              (k a)
              (-& n 1 (lambda (nm1)
                       (*& n a (lambda (nta)
                                (f-aux& nm

Στις εκδόσεις CPS, οι βασικές εντολές, όπως η +& και η *& είναι επίσης σε CPS, όχι σε ευθύ στυλ - για να λειτουργήσουν τα παραπάνω παραδείγματα σε ένα σύστημα Scheme πρέπει να γραφούν αυτές οι CPS εκδόσεις τους, για παράδειγμα η *& ορίζεται ως εξής:

(define (*& x y k)
(k (* x y)))

Στη γενική περίπτωση, μπορεί να γραφτεί μια ρουτίνα μετατροπής:

(define (cps-prim f)
(lambda args
(let ((r (reverse args)))
((car r) (apply f
(reverse (cdr r)))))))
(define *& (cps-prim *))
(define +& (cps-prim +))

Η κλήση μιας διαδικασίας γραμμένης σε CPS από μια διαδικασία σε ευθύ στυλ απαιτεί να περαστεί μια συνέχεια που να δεχτεί το αποτέλεσμα της διαδικασίας σε CPS. Στο παραπάνω παράδειγμα (θεωρώντας ότι υπάρχουν οι εκδόσεις CPS των βασικών εντολών), η κλήση θα γινόταν (factorial& 10 (lambda (x) x)).

Οι μεταγλωττιστές διαφέρουν όσον αφορά το πώς είναι διαθέσιμες οι βασικές εντολές σε CPS. Στα παραπάνω χρησιμοποιήθηκε η απλούστερη σύμβαση, αν και κάποιες φορές δίνονται βασικές εντολές τύπου αλήθειας (boolean) που παίρνουν δύο εκφράσεις που θα κλήθούν σε δύο πιθανές περιπτώσεις, ώστε η (if (= a b) c d) σε ευθύ στυλ να μεταφράζεται σε (=& a b (lambda () (k c)) (lambda () (k d))). Όμοια, μερικές φορές η εντολή if δε συμπεριλαμβάνεται στο CPS, αλλά υπάρχει μια συνάρτηση if& που παίρνει τρεις παραμέτρους: μια συνθήκη αλήθειας και δύο εκφράσεις που αντιστοιχούν στους δύο κλάδους της εντολής.

Οι παραπάνω μετασχηματισμοί δείχνουν ότι το CPS είναι καθολικός μετασχηματισμός - η συνάρτηση factorial σε ευθύ στυλ παίρνει, όπως θα ήταν αναμενόμενο, μία παράμετρο. Η αντίστοιχη factorial& σε CPS παίρνει δύο: την παράμετρο και μια συνέχεια. Κάθε συνάρτηση που καλεί μια συνάρτηση σε CPS πρέπει είτε να της δώσει μια νέα συνέχεια ή να της περάσει τη δική της ενώ οι κλήσεις από μια συνάρτηση σε CPS σε μια σε ευθύ στυλ θα έχει έμμεσες συνέχειες (implicit continuations). Επομένως, για να μην υπάρχει στοίβα συναρτήσεων, πρέπει ολόκληρο το πρόγραμμα να είναι σε 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 θα μπορούσε να εξηγήσει κάποια φαινόμενα της φυσικής γλώσσας [1].

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

Η ίδια η κλασική λογική έχει απευθείας σχέση με το χειρισμό της συνέχειας ενός προγράμματος, όπως στον τελεστή ελέγχου call-with-current-continuation της Scheme.[4]
Δείτε επίσης

Η κατασκευή ενός μεταγλωττιστή βασισμένου σε CPS για τη γλώσσα προγραμματισμού ML περιγράφεται στο: Appel, Andrew W. (1992). Compiling with Continuations. Cambridge University Press. ISBN 0-521-41695-7.
Olivier Danvy and Andrzej Filinski (1992). «Representing Control, A Study of the CPS Transformation». Mathematical Structures in Computer Science 2 (4): 361–391. doi:10.1017/S0960129500001535.
Richard A. Kelsey (March 1995). «A Correspondence between Continuation Passing Style and Static Single Assignment Form». ACM SIGPLAN Notices 30 (3): 13–22. doi:10.1145/202530.202532.
Andrew W. Appel (April 1998). «SSA is Functional Programming». ACM SIGPLAN Notices 33 (4): 17–20. doi:10.1145/278283.278285.
Danvy, Olivier; Millikin, Kevin; Nielsen, Lasse R. (2007). «On One-Pass CPS Transformations». BRICS, Department of Computer Science, University of Aarhus, σσ. 24. RS-07-6. ISSN 0909-0878
R. Kent Dybvig (2003). The Scheme Programming Language. Prentice Hall, σελ. 64. Σύνδεσμος: "Section 3.4. Continuation Passing Style".

Αναφορές

Gerald Jay Sussman, Guy L. Steele, Jr. (Δεκέμβριος 1975). «Scheme: An interpreter for extended lambda calculus». AI Memo 349: 19. «That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function. This is the key idea.».
Gerald Jay Sussman, Guy L. Steele, Jr. (Δεκέμβριος 1998). «Scheme: A Interpreter for Extended Lambda Calculus» (reprint). Higher-Order and Symbolic Computation 11 (4): 405–439. doi:10.1023/A:1010035624696. «We believe that this was the first occurrence of the term "continuation-passing style" in the literature. It has turned out to be an important concept in source code analysis and transformation for compilers and other metaprogramming tools. It has also inspired a set of other "styles" of program expression.».
* Richard A. Kelsey (March 1995). «A Correspondence between Continuation Passing Style and Static Single Assignment Form». ACM SIGPLAN Notices 30 (3): 13–22. doi:10.1145/202530.202532.

Timothy Griffin. (Ιανουάριος 1990). «A formulae-as-type notion of control». Proceedings of the Conference on the Principles of Programming Languages 17: 47–58.

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Continuation-passing style της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).

Εγκυκλοπαίδεια Πληροφορικής

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License