Продовження (англ. continuation) являє стан програми в певний момент, який може бути збережено і використано для переходу в цей стан. Продовження містять всю інформацію, щоб продовжити виконання програми з певної точки. Стан глобальних змінних зазвичай не зберігається, однак для функціональних мов це несуттєво (вибіркове збереження/відновлення значень глобальних об'єктів в Scheme досягається окремим механізмом dynamic-wind). Продовження схожі на goto Бейсика або setjmp/longjmp Сі, так як також дозволяють перейти в будь-яке місце програми. Але продовження, на відміну від goto, дозволяють перейти тільки на ділянку програми з певним станом, яке має бути збережено заздалегідь, у той час, як goto дозволяє перейти в ділянку програми з неинициализированными змінними.
Scheme був першим промисловим мовою, в якому реалізовані повноцінні продовження. Bruce Duba ввів продовження в Standard ML.
Формально, callcc — це функція вищого порядку, що дозволяє абстрагувати динамічний контекст наявної функції у вигляді функції, яка і називається «продовженням».
Більш наочно, продовження — це «вся решта програми від даної точки», або «функція, яка ніколи не повертає керування в точку виклику»[]. У процесі вивчення функціонального програмування багато відчувають труднощі з розумінням сутності продовжень. Традиційне пояснення цього поняття зводиться до «розширення (ускладнення) поняття співпрограми», але в педагогічному сенсі таке пояснення вважається марним[]. Причина труднощі розуміння полягає в тому, що продовження фактично являють собою альтернативне обґрунтування поняття «поведінки» («дзвінка» у самому широкому розумінні), тобто іншу семантичну модель, і в цьому сенсі початковий перехід від «звичайного» функціонального програмування до програмування з інтенсивним використанням продовжень можна порівняти з початковим переходом від імперативного до функціонального програмування.
Продовження являють собою математичне обгрунтування всього близько виконання програми, від goto і циклів до рекурсії, винятків, генераторів[en]*, сопрограмм і механізму повернення[]. Як наслідок, вони дозволяють реалізувати всі ці елементи у мові за допомогою єдиної конструкції.
Програмування в стилі передачі продовжень (англ. Continuation-passing style, CPS) — це стиль програмування, при якому передача управління здійснюється через механізм продовжень. Стиль CPS вперше представили Джеральд Джей Сассман[en] і Гай Стіл мл[en], одночасно з мовою Scheme.
Такий стиль дуже скрутний для використання людиною, і зазвичай є стратегією оптимізації в компіляторах.
Direct style
(define (pyth x y) (sqrt (+ (* x x) (* y y))))
(define (factorial n) (if (= n 0) 1 ; NOT tail-recursive (* n (factorial (- n 1)))))
(define (factorial n) (f-aux n 1)) (define (f-aux n a) (if (= n 0) a ; tail-recursive (f-aux (- n 1) (* n a))))
Continuation passing style
(define (pyth& x y k) (*& x x (lambda (x2) (*& y y (lambda (y2) (+& x2 y2 (lambda (x2py2) (sqrt& x2py2 k))))))))
(визначити (факторіал& N к) (=& н 0 (лямбда (б) (якщо B ; продовження зростає (1) ; в рекурсивном виклику (-& н 1 (лямбда (нм 1) (факторіал& нм 1 (лямбда (Ф) (*& н fк)))))))))
(визначити (факторіал& N к) (ф-ОКС& N 1)) (визначити (Ф-ОКС& Н А К) (=& н 0 (лямбда (б) (якщо B ; продовження зберігається (а) ; в рекурсивном виклику (-& н 1 (лямбда (нм 1) (*& Н А (лямбда (НТА) (Ф-ОКС& K нм 1 НТА)))))))))
Можна помітити, що в чистому CPS фактично не існує самих продовжень — всякий виклик виявляється хвостовим. Якщо мову не гарантує оптимізацію хвостових викликів (англ. Tail call optimization, TCO), то при кожному вкладеному виклику callcc зростає і саме продовження, і стек викликів. Зазвичай це небажано, але часом використовується цікавим способом (див. компілятор Chicken Scheme[en]). Спільне використання стратегій оптимізації TCO і CPS дозволяє повністю усунути динамічний стек з виконуваною програми. Ряд компіляторів функціональних мов працює саме таким чином, наприклад компілятор SML/NJ для мови Standard ML.
Існує кілька різновидів продовжень. Найбільш поширена з них - необмежені (undelimited continuations) продовження, реалізовані за допомогою функції call/cc або її аналогів. Такі продовження дійсно представляють собою стан всієї програми (або однієї її нитки) в певний момент. Виклик такого продовження не схожий на виклик функції, оскільки він відповідає "стрибка" у збережений стан програми і не повертає ніякого значення; таке продовження зазвичай не можна викликати кілька разів. Обмежені (delimited continuations) продовження абстрагируют залежність результату деякого блоку програми від результату деякого подвираженія цього блоку. У певному сенсі вони відповідають сегменту стека викликів, а не всьому стеку. Такі продовження можуть використовуватися як функції, викликатися кілька разів і т. п. Вони абстрагуються з допомогою механізму shift/reset: reset обертає зовнішній блок, shift діє як call/cc, але отримує в якості аргументу не глобальне продовження, а обмежена - залежність значення блоку reset від значення на місці блоку shift. Існують і інші різновиди, наприклад prompt/control.
Багато мови програмування надають цю можливість під різними іменами, наприклад: Scheme: call/cc (короткий запис для call-with-current-continuation) Standard ML: SMLofNJ.Cont.callcc, див. також Concurrent ML Сі: setcontext et al. (UNIX System V GNU libc) Ruby: callcc Smalltalk: Continuation currentDo: у більшості сучасних реалізацій продовження можуть бути реалізовані на чистому Smalltalk, не вимагаючи спеціальної підтримки у віртуальній машині. Rhino : Continuation Haskell : callCC (в модулі Control.Монада.Cont) Factor : callcc0 і callcc1 Python : yield Scala : Існує плагін для підтримки обмежених продовжень. PHP: Є підтримка. C#: конструкції yield return і await.
В будь-якій мові, що підтримує замикання, можна писати програми в стилі передачі продовжень (англ. Continuation-passing style, CPS) і вручну реалізувати call/cc. Зокрема це поширена практика в Haskell, де легко будуються «монади, передають продовження» (для прикладу, монада Cont та трансформер монад ContT бібліотеки mtl).
