Συνέχεια (πληροφορική)

Μια συνέχεια (continuation) επαναφέρει ένα στιγμιότυπο μιας υπολογιστικής διεργασίας σε ένα δοσμένο σημείο της εκτέλεσής της. Περιλαμβάνει πληροφορίες όπως η τρέχουσα στοίβα της διεργασίας (με όλα τα δεδομένα των οποίων ο χρόνος ζωής είναι μέσα στη διεργασία, π.χ. οι "τοπικές μεταβλητές") και η θέση της διεργασίας στον υπολογισμό. Ένα τέτοιο στιγμιότυπο μπορεί στη συνέχεια να κληθεί και να συνεχιστεί. Η "τρέχουσα συνέχεια" ("current continuation") ή "συνέχεια του υπολογιστικού βήματος" ("continuation of the computation step") είναι η συνέχεια, η οποία, από την πλευρά του κώδικα που εκτελείται, θα προέκυπτε από το τρέχον σημείο του προγράμματος που εκτελείται.

Ο όρος συνέχειες μπορεί επίσης να σημαίνει συνέχειες πρώτης τάξης, οι οποίες είναι σχήματα κώδικα που επιτρέπουν σε μια γλώσσα προγραμματισμού να αποθηκεύει την κατάσταση του υπολογισμού σε κάποιο σημείο και να μπορεί αργότερα, σε κάποιο άλλο σημείο του προγράμματος, να επιστρέφει σε αυτήν.

Τα προγράμματα πρέπει να κρατούν θέσεις στη μνήμη για τις μεταβλητές που χρησιμοποιούν οι συναρτήσεις τους. Οι περισσότερες γλώσσες προγραμματισμού χρησιμοποιούν μια στοίβα κλήσεων για να αποθηκεύουν τις μεταβλητές που χρειάζονται γιατί με αυτόν τον τρόπο έχουν γρήγορη και απλή δέσμευση μνήμης και αυτόματη αποδέσμευση. Υπάρχουν επίσης γλώσσες προγραμματισμού που χρησιμοποιούν σωρό για αυτόν το σκοπό, ο οποίος επιτρέπει μεγαλύτερη ευελιξία αλλά έχει υψηλότερο κόστος δέσμευσης και αποδέσμευσης μνήμης. Και οι δύο αυτές διαφορετικές υλοποιήσεις έχουν πλεονεκτήματα και μειονεκτήματα όσον αφορά τις συνέχειες.

Σχεδόν όλες οι γλώσσες έχουν κάποιον τρόπο για να αλλάζουν τη σειρά των βημάτων εκτέλεσης (δηλ. την τροποποίηση της συνέχειας ενός υπολογιστικού βήματος). Η εντολή goto είναι η πιο βασική μορφή από αυτές. Δομές ελέγχου όπως οι εντολές if, οι βρόχοι και οι εντολές return, break και exit, είναι πιο δομημένοι (και περιορισμένοι) τρόποι να τροποποιηθεί η σειρά των εντολών που εκτελούνται και στην πραγματικότητα μπορούν να θεωρηθούν σαν περιορισμένες εντολές goto.

Υπάρχουν και πιο πολύπλοκα σχήματα κώδικα. Για παράδειγμα στη C, η εντολή setjmp μπορεί να χρησιμοποιηθεί για να γίνει άλμα από τη μέση μιας συνάρτησης σε μια άλλη συνάρτηση, με την προϋπόθεση ότι η άλλη συνάρτηση είναι χαμηλότερα στη στοίβα (για παράδειγμα, μπορεί να περιμένει την αρχική συνάρτηση να τελειώσει την εκτέλεσή της). Άλλα πιο πολύπλοκα παραδείγματα είναι οι συρρουτίνες στη Simula, τα τάσκλετ στην Stackless Python, οι γεννήτριες στην Icon και την Python, οι συνέχειες στη Scala (από την έκδοση 2.8), οι ίνες στη Ruby (από την έκδοση 1.9.1), ο μηχανισμός οπισθοδρόμησης (backtracking) στην Prolog, και τα νήματα.

Ιστορία

Η παλαιότερη περιγραφή των συνεχειών έχει γίνει από τον Άντριαν φαν Βαϊνγκάρντεν το Σεπτέμβριο του 1964. Ο Βαϊνγκάρντεν μίλησε στο "IFIP Working Conference on Formal Language Description Languages", στο Μπάντεν μπάι Βίεν, στην Αυστρία. Σαν μέρος του φορμαλισμού ενός προεπεξεργαστή για την Algol 60, χρειάστηκε ένα μετασχηματισμό από κανονικές διαδικασίες σε στυλ περάσματος συνεχειών (continuation-passing style).

Ο Κρίστοφερ Στρέιτσι, ο Κρίστοφερ Π. Ουόντσγουερθ και ο Τζον Σ. Ρέινολντς έκαναν γνωστό τον όρο συνέχεια (continuation) αργότερα με τη δουλειά τους στη δηλωτική σημασιολογία που χρησιμοποιεί εκτενώς συνέχειες για να μπορεί να αναλύει ακολουθιακά προγράμματα σε σημασιολογία συναρτησιακού προγραμματισμού.

Η συνέχεια εφευρέθηκε από τον Στιβ Ράσελ στη δεύτερη υλοποίηση της Lisp για τον IBM 704, αν και δεν της έδωσε όνομα.

Συνέχειες πρώτης τάξης

Συνέχειες πρώτης τάξης είναι η ικανότητα μιας γλώσσας να ελέγχει πλήρως τη σειρά εκτέλεσης των εντολών της. Μπορούν να χρησιμοποιηθούν για άλμα μέσα σε μια συνάρτηση που κάλεσε την τρέχουσα συνάρτηση ή σε μια συνάρτηση που έχει τελειώσει η εκτέλεσή της. Οι συνέχειες πρώτης τάξης μπορούν να θεωρηθούν ότι αποθηκεύουν την κατάσταση του προγράμματος. Όμως πρέπει να σημειωθεί ότι οι πραγματικές συνέχειες πρώτης τάξης δεν αποθηκεύουν τα δεδομένα του προγράμματος αλλά μόνο το πλαίσιο της εκτέλεσης (execution context). Αυτό περιγράφεται από την περιγραφή της "συνέχειας-σάντουιτς":

Ας πούμε ότι είστε στην κουζίνα μπροστά από το ψυγείο, θέλοντας ένα σάντουιτς. Παίρνετε τη συνέχεια εκείνη τη στιγμή και τη βάζετε στην τσέπη σας. Μετά παίρνετε λίγες φέτες γαλοπούλα και ψωμί από το ψυγείο και φτιάχνετε ένα σάντουιτς, το οποίο τώρα βρίσκεται στον πάγκο της κουζίνας. Καλείτε τη συνέχεια που έχετε στην τσέπη σας και βρίσκεστε πάλι μπροστά στο ψυγείο θέλοντας ένα σάντουιτς. Αλλά ευτυχώς υπάρχει ήδη ένα σάντουιτς στον πάγκο και τα υλικά που θα χρειάζονταν για να το φτιάξετε πια δεν υπάρχουν. Οπότε το τρώτε. :-)

Η Scheme ήταν το πρώτο σύστημα επιπέδου παραγωγής που παρείχε αρχικά την "catch" και μετά την call/cc. Ο Μπρους Ντούμπα εισήγαγε την call/cc στην Standard ML.

Οι συνέχειες επίσης χρησιμοποιούνται σε μοντέλα υπολογισμού όπως η δηλωτική σημασιολογία, το μοντέλο Actor, οι λογισμοί διεργασιών (process calculi) και ο λ-λογισμός. Αυτά τα μοντέλα απαιτούν από τους προγραμματιστές ή τους μηχανικούς της σημασιολογίας να γράφουν μαθηματικές συναρτήσεις στο λεγόμενο στυλ περάσματος συνεχειών. Αυτό σημαίνει ότι κάθε συνάρτηση καταναλώνει μια άλλη συνάρτηση που αναπαριστά το υπόλοιπο του υπολογισμού σε σχέση με αυτήν την κλήση συνάρτησης. Για να επιστρέψει κάποια τιμή, η συνάρτηση καλεί αυτήν τη "συνάρτηση συνέχειας" με μια τιμή επιστροφής - για να διακόψει τον υπολογισμό επιστρέφει μια τιμή.

Οι προγραμματιστές συναρτησιακών γλωσσών που γράφουν τα προγράμματά τους σε στυλ περάσματος συνεχειών έχουν την εκφραστική δύναμη να αλλάζουν τη ροή του ελέγχου με αυθαίρετους τρόπους. Το κόστος είναι ότι πρέπει να διατηρούν τις αναλλοίωτες του ελέγχου και των συνεχειών με το χέρι, κάτι που είναι αρκετά πολύπλοκο.

Χρήσεις

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

Παραδείγματα

Η γλώσσα προγραμματισμού Scheme περιλαμβάνει τον τελεστή ροής κλήση-με-τρέχουσα-συνέχεια (call-with-current-continuation) (συντομογραφία: call/cc) με τον οποίο ένα πρόγραμμα σε Scheme μπορεί να αλλάζει τη ροή του ελέγχου:

 (define the-continuation #f)

 (define (test)
   (let ((i 0))
     ; η call/cc καλεί την πρώτη παράμετρο της συνάρτησης, περνώντας της
     ; μια μεταβλητή συνέχειας που αναπαριστά ένα σημείο στο πρόγραμμα
     ; σαν παρέμτρο σε αυτήν τη συνάρτηση.
     ;
     ; Σε αυτήν την περίπτωση, η παράμετρος της συνάρτησης δεσμεύει τη
     ; συνέχεια στη μεταβλητή the-continuation.
     ;
     (call/cc (lambda (k) (set! the-continuation k)))
     ;
     ; Την επόμενη φορά που καλείται η συνέχεια, αρχίζουμε εδώ.
     (set! i (+ i 1))
     i))

Ορίζει μια συνάρτηση test που θέτει την the-continuation σε μια μελλοντική κατάσταση εκτέλεσης της ίδιας:

> (test)
1
> (the-continuation)
2
> (the-continuation)
3
> ; αποθηκεύει την τρέχουσα συνέχεια (που θα τυπώσει 4 τώρα)
> (define another-continuation the-continuation)
> (test) ; resets the-continuation
1
> (the-continuation)
2
> (another-continuation) ; χρησιμοποιεί την προηγούμενη αποθηκευμένη συνέχεια
4

Για μια πιο απλή εισαγωγή σε αυτόν το μηχανισμό, δείτε το άρθρο κλήση-με-τρέχουσα-συνέχεια.

Συρρουτίνες

Αυτό το παράδειγμα δείχνει μια πιθανή χρήση των συνεχειών στην υλοποίηση συρρουτινών σαν ξεχωριστά νήματα.

 ;;; Μια απλή ουρά για χρονοπρογραμματισμό νημάτων.
 ;;; Κρατά τις συνέχειες που "πρόκειται να τρέξουν".

   (define *queue* '())

   (define (empty-queue?)
     (null? *queue*))

   (define (enqueue x)
     (set! *queue* (append *queue* (list x))))

   (define (dequeue)
     (let ((x (car *queue*)))
       (set! *queue* (cdr *queue*))
       x))

   ;;; Αρχίζει ένα νέο νήμα που θα τρέξει το (proc).

   (define (fork proc)
     (call/cc
      (lambda (k)
        (enqueue k)
        (proc))))

   ;;; Αφήνει τον επεξεργαστή σε κάποιο άλλο νήμα, αν υπάρχει τέτοιο.

   (define (yield)
     (call/cc
      (lambda (k)
        (enqueue k)
        ((dequeue)))))

   ;;; Τελειώνει το υπάρχον νήμα, ή ολόκληρο το πρόγραμμα
   ;;; αν δεν υπάρχουν άλλα νήματα.

   (define (thread-exit)
     (if (empty-queue?)
         (exit)
         ((dequeue))))

Οι παραπάνω συναρτήσεις επιτρέπουν τον ορισμό και την εκτέλεση νημάτων μέσω συνεργατικής πολυδιεργασίας (cooperative multitasking), δηλ. νήματα που αφήνουν τον έλεγχο στο επόμενο που περιμένει στην ουρά:

   ;;; Το σώμα ενός τυπικού νήματος σε Scheme που κάνει κάποια εργασία:

   (define (do-stuff-n-print str)
     (lambda ()
       (let loop ((n 0))
         (format #t "~A ~A\n" str n)
         (yield)
         (loop (1+ n)))))

   ;;; Δημιουργεί δύο νήματα και τα αρχίζει.
   (fork (do-stuff-n-print "This is AAA"))
   (fork (do-stuff-n-print "Hello from BBB"))
   (thread-exit)

Ο προηγούμενος κώδικας τότε τα παράγει την εξής έξοδο:

 This is AAA 0
 Hello from BBB 0
 This is AAA 1
 Hello from BBB 1
 This is AAA 2
 Hello from BBB 2
 ...

Υποστήριξη σε γλώσσες προγραμματισμού

Πολλές γλώσσες προγραμματισμού έχουν συνέχειες πρώτης τάξης, με διάφορες ονομασίες, πιο συγκεκριμένα:

• C: setcontext κλπ. (UNIX System V και GNU libc)
• Factor: callcc0 και callcc1
• Haskell: Η Μονάδα Συνεχειών (Continuation Monad) στην Control.Monad.Cont
• Icon, Unicon : create, suspend, @ operator: coexpressions
• Parrot: Continuation PMC; χρησιμοποιεί στυλ περάσματος συνεχειών για όλοκληρη τη ροή ελέγχου
• Perl: Coro και Continuity
• Pico: call(exp()) και continue(aContinuation, anyValue)
• JavaScript Rhino : Continuation
• Mythryl: callcc
• Ruby: callcc
• Scala: Responder
• Scheme: call-with-current-continuation (συνήθως με τη συντομογραφία call/cc)
• Smalltalk: Continuation currentDo:, στα περισσότερα σύγχρονα περιβάλλοντα Smalltalk οι συνέχειες μπορούν να υλοποιηθούν χωρίς επιπλέον υποστήριξη από την εικονική μηχανή.
• Standard ML of New Jersey: SMLofNJ.Cont.callcc
• Unlambda: c, η λειτουργία ελέγχου ροής για κλήση με την τρέχουσα συνέχεια

Σε κάθε γλώσσα που υποστηρίζει κλεισίματα και αναδρομή ουράς, μπορούμε να γράψουμε προγράμματα σε στυλ περάσματος συνεχειών και να υλοποιήσουμε την call/cc. (Στο στυλ περάσματος συνεχειών η call/cc γίνεται μια απλή συνάρτηση που μπορεί να γραφεί σαν συνάρτηση του λ-λογισμού.) Αυτό είναι συνηθισμένο στη Haskell, όπου είναι εύκολο να κατασκευαστεί μια "Μονάδα που περνάει συνέχειες" (για παράδειγμα, η μονάδα Cont και ο μετασχηματιστής μονάδων ContT στη βιβλιοθήκη mtl). Η υποστήριξη για αναδρομή ουράς χρειάζεται γιατί στο στυλ περάσματος συνεχειών μια συνάρτηση δεν επιστρέφει ποτέ: όλες οι κλήσεις συναρτήσεων είναι κλήσεις ουράς.

Συνέχειες στην ανάπτυξη λογισμικού για τον Ιστό

Μια περιοχή που χρησιμοποιεί πρακτικά τις συνέχειες είναι η ανάπτυξη λογισμικού ιστού. Η χρήση των συνεχειών προστατεύει τον προγραμματιστή από την έλλειψη κατάστασης (state) στο πρωτόκολλο HTTP. Στο παραδοσιακό μοντέλο προγραμματισμού για τον Ιστό, η έλλειψη κατάστασης ανακλάται στη δομή του προγράμματος, οδηγώντας σε κώδικα που βασίζεται σε ένα μοντέλο ακατάλληλο να εκφράσει υπολογιστικά προβλήματα. Οι συνέχειες επιτρέπουν κώδικα που έχει τις χρήσιμες ιδιότητες της αναστροφής του ελέγχου(inversion of control), αποφεύγοντας τα προβλήματά του. Το Inverting back the inversion (Αγγλικά) είναι μια δημοσίευση που προσφέρει μια καλή εισαγωγή στην εφαρμογή των συνεχειών στον προγραμματισμό λογισμικού Ιστού.

Κάποιοι από τους πιο γνωστούς εξυπηρετητές Ιστού που υποστηρίζουν συνέχειες είναι ο PLT Scheme Web Server(documentation), το UnCommon Web Framework και το Weblocks Web framework για την Common Lisp, το πλαίσιο Seaside για την Smalltalk, το Ocsigen/Eliom για την OCaml, το Continuity για την Perl, το Wee για τη Ruby, και το πλαίσιο Nagare για την Python. Το πλαίσιο εφαρμογών ιστού Apache Cocoon επίσης παρέχει συνέχειες (βλ. το εγχειρίδιο του Cocoon).

Είδη συνεχειών

Η υποστήριξη συνεχειών διαφέρει αρκετά κατά περίπτωση. Μια γλώσσα προγραμματισμού υποστηρίζει επανακαλούμενες (re-invocable) συνέχειες αν μια συνέχεια μπορεί να καλείται συνεχώς (ακόμα και όταν έχει επιστρέψει). Τέτοιες συνέχειες εισήχθησαν από τον Πίτερ Τζ. Λάντιν με τον τελεστή J (Jump) που μετέφερε τη ροή του ελέγχου πίσω στο μέσο μιας κλήσης διαδικασίας. Έχουν ονομαστεί και "re-entrant" στη γλώσσα προγραμματισμού MzScheme. Όμως αυτή η χρήση του όρου "re-entrant" μπορεί να προκαλέσει πρόβλημα σε σχέση με τη χρήση της σε συζητήσεις σχετικά με τον πολυνηματικό προγραμματισμό.

Ένα περιορισμένο είδος είναι η συνέχεια διαφυγής που μπορεί να χρησιμοποιηθεί για να μεταφερθούμε από το τρέχον περιβάλλον εκτέλεσης σε ένα άλλο που το περικλείει. Πολλές γλώσσες που δεν επιτρέπουν ρητά συνέχειες επιτρέπουν χειρισμό εξαιρέσεων, ο οποίος είναι ισοδύναμος με τις συνέχειες διαφυγής και μπορεί να χρησιμοποιηθεί για τους ίδιους σκοπούς. Οι setjmp/longjmp της C είναι επίσης ισοδύναμες: μπορούν να χρησιμοποιηθούν μόνο για να ξετυλίξουν τη στοίβα. Οι συνέχειες διαφυγής μπορούν επίσης να χρησιμοποιηθούν για να υλοποιήσουν βελτιστοποίηση κλήσης ουράς.

Μειονεκτήματα

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

Γλωσσολογία

Κάποια φαινόμενα στις φυσικές γλώσσες έχουν περιγραφεί με τη χρήση φραγμένων συνεχειών.

Ανεπίσημα, οι συνέχειες μπορούν να εξηγήσουν την ομοιότητα μεταξύ των προτάσεων "η Alice βλέπει τον Bob"—τυπικά, ${\mbox{sees}}({\mbox{Alice}},{\mbox{Bob}})$—και "η Alice βλέπει όλους τους ανθρώπους", δηλ.. ${\mbox{sees}}\left({\mbox{Alice}},everyone\right)\rightsquigarrow \forall {x}\,{\mbox{sees}}\left({\mbox{Alice}},x\right)$.

Δείτε τη δημοσίευση του Κρις Μπάρκερ Continuations in Natural Language για λεπτομέρειες. Δείτε επίσης τη γραμματική Μόνταγκιου.

Δείτε επίσης

• Φραγμένη συνέχεια
• Κλείσιμο
• Στυλ περάσματος συνεχειών
• Ροή ελέγχου
• Συρρουτίνα
• Δηλωτική σημασιολογία
• GOTO

Περαιτέρω διάβασμα

• Peter Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. August 1965. Reprinted in Higher Order and Symbolic Computation, 11(2):125-143, 1998, with a foreword by Hayo Thielecke.
• Drew McDermott and Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259. May 1972.
• Daniel Bobrow: A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
• Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
• Christopher Strachey and Christopher P. Wadsworth. Continuations: a Mathematical semantics for handling full jumps Technical Monograph PRG-11. Oxford University Computing Laboratory. January 1974. Reprinted in Higher Order and Symbolic Computation, 13(1/2):135—152, 2000, with a foreword by Christopher P. Wadsworth.
• John Reynolds. Definitional Interpreters for Higher-Order Programming Languages Proceedings of 25th ACM National Conference, pp. 717–740, 1972. Reprinted in Higher-Order and Symbolic Computation 11(4):363-397, 1998, with a foreword.
• John Reynolds. On the Relation between Direct and Continuation Semantics Proceedings of Second Colloquium on Automata, Languages, and Programming. LNCS Vol. 14, pp. 141–156, 1974.
• Gerald Sussman and Guy Steele. SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, December 1975. Reprinted in Higher-Order and Symbolic Computation 11(4):405-439, 1998, with a foreword.
• Robert Hieb, R. Kent Dybvig, Carl Bruggeman. Representing Control in the Presence of First-Class Continuations Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 66–77.
• Will Clinger, Anne Hartheimer, Eric Ost. Implementation Strategies for Continuations Proceedings of the 1988 ACM conference on LISP and Functional Programming, pp. 124–131, 1988. Journal version: Higher-Order and Symbolic Computation, 12(1):7-45, 1999.

Εξωτερικοί σύνδεσμοι

• Continuations for Curmudgeons by Sam Ruby (Αγγλικά)
• Teach Yourself Scheme in Fixnum Days by Dorai Sitaram features a nice chapter on continuations. (Αγγλικά)
• Continuations and Stackless Python by Christian Tismer (Αγγλικά)
• On-line proceedings of the Fourth ACM SIGPLAN Workshop on Continuations Αρχειοθετήθηκε 2010-12-02 στο Wayback Machine. (Αγγλικά)
• On-line proceedings of the Second ACM SIGPLAN Workshop on Continuations (Αγγλικά)
• Continuation, functions and jumps Αρχειοθετήθηκε 2010-12-02 στο Wayback Machine. (Αγγλικά)
• Rhino With Continuations (Αγγλικά)
• Continuations in pure Java from the RIFE web application framework (Αγγλικά)
• Debugging continuations in pure Java Αρχειοθετήθηκε 2021-05-16 στο Wayback Machine. from the RIFE web application framework (Αγγλικά)
• Comparison of generators, coroutines, and continuations, source of the above example (Αγγλικά)