سبک ادامه دهی با انتقال پارامتر

در برنامه‌نویسی تابعی، روشِ "ادامه‌دهی با انتقال پارمتر" یا CPS، یک روش برنامه‌نویسی است که در آن flow|کنترل به شکل مستقیم و به فرم یک تداوم منتقل می‌شود (یک تداوم، نمایشی خلاصه از وضعیت کنترل یک برنامه کامپیوتری است و در یک زمان خاص از فرایند اجرا، جریان کامپیوتری را نشان می‌دهد). اين روش در تضاد با روش مستقيم (direct style) است كه همان سبک معمول برنامه‌نویسی است. "جرالد جی ساسمن" و "گای ال استیل جونیور"، در گزارش‌ها "اِی.آی مِمو ۳۴۹" در سال ۱۹۷۵ این عبارت را ابداع کردند که باعث به کار افتادن اولین ورژن زبان برنامه‌نویسی "اسکیم" شد. "جان سی رینولدز" شرح مفصلی از اکتشافات متعددِ تداوم‌ها ارائه می‌دهد.

مثال‌ها

تابعی که به روش " ادامه‌دهی با انتقال پارمتر " نوشته شده باشد یک آرگومانِ اضافه دریافت خواهد کرد: یک تداوم صریح؛ یعنی یک تابع با یک آرگومان. وقتی تابع نوشته شده با روش " ادامه‌دهی با انتقال پارمتر " مقدار نهایی خود را حساب کند، با صدا زدن تابع تداوم و دادن مقدار نهایی به آن به عنوان آرگومان، آن را برمی‌گرداند. این بدان معناست که هنگام فراخوانی یک تابع CPS، تابع صدا زده شده وظیفه دارد که عملکرد و رویه‌ای فراهم کند تا همراه با مقدار بازگشتی زیر-روال فراخوانی شود.( زیر-روال مجموعه‌ای از دستورالعمل‌ها با نام یا آدرس خاصی هستند که هنگام احضار توسط برنامه اصلی اجرا می‌شوند). بيان كردن كد به این شکل، چیزهایی را صریح و مستقیم می‌کند که در روش برنامه‌نویسی مستقیم، به صورت ضمنی هستند. این‌ها عبارتند از : بازگشت‌های رویه‌ها، که به عنوان فراخوانی تداوم‌ها آشکار می‌شود؛ مقادیر میانی، که همگی اسم‌های داده شده هستند؛ ترتیب ارزیابی آرگومان‌ها، که صریح و مستقیم شده‌اند؛ و فراخوانی انتهایی که به سادگی یک رویه را با همان تداومِ تغییر نیافته که به صداکننده انتقال داده شده بود، فراخوانی می‌کند. برنامه‌ها می‌توانند به شکل خودکار از روش مستقیم به روش CPS تغییر پیدا کنند. کامپایلرهای تابعی و منطقی معمولاً از CPS به عنوان یک نمایش میانی استفاده می‌کنند در جایی که یک کامپایلر برای یک زبان برنامه‌نویسی امری یا رویه‌ای از فرم تخصیص تک‌ایستا (SSA) استفاده می‌کند. SSA به شکل رسمی معادل با زیرمجموعه‌ای از CPS است ( به استثنای جریان کنترل غیرمحلی، که زمانی که CPS به عنوان نمایش میانی استفاده می‌شود، اتفاق نمی‌افتد). کامپایلرهای تابعی همچنین می‌توانند به جای استفاده از thunk در CPS، که زیربرنامه‌ای است برای تزریق محاسبات به زیربرنامه دیگر، از فرم آنرمال (ANF) استفاده کنند (اما فقط برای زبان‌هایی که نیاز به تکنیک ارزیابی مشتاقانه دارند (تکنیک مشتاقانه یک روش است که در آن یک عبارت، به محض اینکه به یک متغیر محدود شود یا به عنوان یک آرگومان انتقال داده شود، ارزیابی می‌شود.)). CPS بیشتر توسط کامپایلرها استفاده می‌شود تا به عنوان یک سبک کلی یا محلی توسط برنامه‌نویس‌ها. در CPS هر تابع، یک آرگومان اضافه می‌گیرد که نمایان‌کننده این است که باید روی نتیجه‌ای که تابع محاسبه می‌کند، چه عملی انجام شود. این موضوع، همراه با یک سبک محدود‌کننده که انواع مدل‌هایی که معمولاً در دسترس هستند را ممنوع می‌کند، استفاده می‌شود تا معانی برنامه‌ها را نماش دهد و درنتیجه، تحلیل آن‌ها را ساده‌تر کند. این روش همچنین، بیان ساختارهای کنترل غیرمعمولی مثل پرتاب کردن/گرفتن یا سایر انتقال‌های غیرمحلی را آسان می‌کند. راز CPS این است که به یاد داشته باشیم : یک) هر تابعی یک آرگومان اضافی با عنوان "تداوم" تابع می‌گیرد و دو) هر آرگومانی در یک فراخوانی تابع باید یا یک متغیر باشد یا عبارت لامبدا (نه یک عبارت پیچیده‌تر). تاثیر این کار این است که عبارت انگاری پشت‌ورو می‌شود؛ زیرا قسمت‌های داخلی عبارات باید زودتر ارزیابی شوند، که در نتیجه CPS ترتیب ارزیابی را نیز همانند جریان کنترل صریح و مستقیم می‌کند. تعدادی مثال از کد به روش مستقیم و CPS متناظر با آن در پایین دیده می‌شود. این مثال‌ها به زبان برنامه‌نویسی اسکیم نوشته شده‌اند؛ طبق قرارداد تابع تداوم با "k" نمایش‌ داده شده است:

Direct style	Continuation passing style
(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 ; NOT tail-recursive (* n (factorial (- n 1)))))	(define (factorial& n k) (=& n 0 (lambda (b) (if b ; growing continuation (k 1) ; in the recursive call (-& 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 ; tail-recursive (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 ; unmodified continuation (k a) ; in the recursive call (-& n 1 (lambda (nm1) (*& n a (lambda (nta) (f-aux& nm1 nta k)))))))))

توجه کنید که در ورژن CPS، متغیرهای اولیه استفاده‌شده، مثل &+ و &* خودشان CPS هستند نه روش مستقیم، بنابراین برای اینکه مثال‌های بالا در سيستم زبان اسكيم كار كنند نياز داريم كه ورژن 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) (display x) (newline)))

در بین کامپایلرها تنوعی برای ارائه توابع اولیه در CPS وجود دارد. در مثال‌های بالا ما از ساده‌ترین قرارداد استفاده کردیم، با این حال گاهی اوقات مقادیر اولیه بولین ارائه می‌شوند که دو thunk می‌گیرند تا در دو حالت متفاوت فراخوانی بشوند، پس به جای فراخوانیِ

(=& n 0 (lambda (b) (if b ...)))

در داخل تعریفِ

f-aux&

به این شکل نوشته خواهد شد:

(=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...)))

به همین شکل، گاهی اوقات بخش "if" خودش در CPS موجود نیست بلکه یک تابع به شکل زیر تعریف خواهد شد:

if&

که سه آرگومان دریافت خواهد کرد: یک شرط با مقدار درست یا غلط، و دو thunk متناظر با دو بازوی شرط. متن بالا نشان می‌دهد که CPS یک تحول جهانی است. فاکتوریلِ روش مستقیم، همان‌طور که انتظار می‌رود، یک آرگومان دریافت خواهد کرد؛ اما فاکتوریل CPS که یک & در آخر اسم خود دارد دو آرگومان می‌گیرد: خود آرگومان معمول و یک تداوم. هر تابعی که یک تابع CPS شده را فراخوانی می‌کند باید یا تداوم جدیدی ارائه کند یا تداوم خودش را منتقل کند؛ هر فراخوانی از یک تابع CPS شده به یک تابع غیرCPS از یک تداوم ضمنی استفاده خواهد کرد. درنتیجه، برای مطمئن شدن از نبود یک استک مربوط به توابع، کل برنامه باید به CPS نوشته شده باشد.

سی.پی.اس در هَسکِل

در این بخش ما یک تابع به اسم

pyth

می‌نویسیم که با استفاده از قضیه فیثاغورث، هیپوتنوز را محاسبه می‌كند. {هیپوتنوز به معنای طولانی‌ترین ضلع مثلث قائم الزاویه نسبت به طول قاعده و عمود بر آن است.} یک پیاده‌سازی سنتی از این تابع به شکل زیر خواهد بود:

pow2 :: Float -> Float
pow2 a = a ** 2

add :: Float -> Float -> Float
add a b = a + b

pyth :: Float -> Float -> Float
pyth a b = sqrt (add (pow2 a) (pow2 b))

برای اینکه این تابع سنتی را به CPS تبدیل کنیم، نیاز داریم امضای تابع، یعنی شیوه تعریف ورودی و خروجی‌های آن را عوض کنیم. تابع یک آرگومان دیگه از جنس تابع دریافت خواهد کرد و نوع نتیجه برگشتی آن، به این تابع وابسته خواهد بود:

pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)

add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)

-- Types a -> (b -> c) and a -> b -> c are equivalent, so CPS function
-- may be viewed as a higher order function
sqrt' :: Float -> ((Float -> a) -> a)
sqrt' a = \cont -> cont (sqrt a)

pyth' :: Float -> Float -> (Float -> a) -> a
pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\anb -> sqrt' anb cont)))

ابتدا مربع "a" را در تابع محاسبه می‌کنیم و یک تابع لامبدا را به عنوان تداوم انتقال می‌دهیم، که مربع "a" را به عنوان آرگومان خواهد پذیرفت. و همین‌طور ادامه خواهد یافت تا به نتیجه محاسبات برسیم. برای به دست آوردن نتیجه این تابع می‌توانیم تابع "id" را به عنوان آرگومان نهایی منتقل کنیم که مقداری را که به آن ارسال شده بدون تغییر برمی‌گرداند:

pyth' 3 4 id == 5.0

کتابخانه mtl که با GHC قابل دسترس می‌شود، دارای ماژولی به نام زیر است:

Control.Monad.Cont

این ماژول تایپ Cont را ارائه می‌دهد، که تابع‌های مفیدی مثل تابع Monad را پیاده‌سازی می‌کند. قطعه زیر تابع pyth' را که در بالا نشان دادیم با استفاده از تایپ Cont نشان می‌دهد:

pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)

pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = do
  a2 <- pow2_m a
  b2 <- pow2_m b
  anb <- cont (add' a2 b2)
  r <- cont (sqrt' anb)
  return r

نه تنها سینتکس زبان تمیزتر شده است، بلکه این تایپ به ما این امکان را می‌دهد تا از فانکشن

callCC

با تایپ زیر استفاده کنیم:

MonadCont m => ((a -> m b) -> m a) -> m a

این تابع یک آرگومان از جنس تابع دارد؛ این آرگومان، تابع را نیز می‌پذیرد، که تمام محاسبات پس از فراخوانی آن را کنار می‌گذارد. برای مثال، بیایید اجرای تابع pyth را، اگر حداقل یکی از آرگومان‌های آن منفی باشد با برگرداندن صفر بشکنیم:

pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = callCC $ \exitF -> do -- $ sign helps to avoid parentheses: a $ b + c == a (b + c)
  when (b < 0 || a < 0) (exitF 0.0) -- when :: Applicative f => Bool -> f () -> f ()
  a2 <- pow2_m a
  b2 <- pow2_m b
  anb <- cont (add' a2 b2)
  r <- cont (sqrt' anb)
  return r

تداوم به عنوان شئ

برنامه‌نویسی با تداوم‌ها، همچنین می‌تواند زمانی مفید باشد که صدا زننده نمی‌خواهد منتظر کامل شدن تابعِ صداشده بماند. به عنوان مثال در برنامه‌نويسی رابط کاربری (UI)، یک روال می‌تواند کادرهای محاوره‌ای تنظیم کند و آن‌ها را به همراه یک تابع تداوم، به چارچوب UI ارسال کند. وقتی کاربر دکمه "OK" را فشار دهد، فریمورک تابع تداوم را با فیلدهای به‌روزشده صدا می‌زند. با اینکه این روش کد‌ زدن از تداوم‌ها استفاده می‌كند،‌ اما به‌طور كامل CPS نیست.

function confirmName() {
    fields.name = name;
    framework.Show_dialog_box(fields, confirmNameContinuation);
}

function confirmNameContinuation(fields) {
    name = fields.name;
}

زمانی که تابع باید در یک رشته یا پردازدنده متفاوت اجرا شود، می‌توان از ایده مشابهی استفاده کرد. فریمورک، می‌تواند تابع صدازده‌شده را در یک رشته کارگر اجرا کند، سپس تابع تداوم را در رشته اولیه با نتیجه رشته کارگر فراخوانی کند. کد زیر به زبان Java 8 و با استفاده از فریمورکd "UI" به نام Swing نوشته شده است:

void buttonHandler() {
    // This is executing in the Swing UI thread.
    // We can access UI widgets here to get query parameters.
    int parameter = getField();

    new Thread(() => {
        // This code runs in a separate thread.
        // We can do things like access a database or a 
        // blocking resource like the network to get data.
        int result = lookup(parameter);

        javax.swing.SwingUtilities.invokeLater(() => {
            // This code runs in the UI thread and can use
            // the fetched data to fill in UI widgets.
            setField(result);
        });
    }).start();
}

فراخوانی‌های نهایی

هر فراخوانی در CPS یک فراخوانی نهایی است، و تداوم مستقیماً منتقل می‌شود. استفاده از CPS بدون بهینه‌سازی فراخوانی نهایی (TCO)، نه تنها باعث می‌شود که تداوم ساخته‌شده به‌طور بالقوه در طول بازگشت رشد کند، بلکه حتی برای فراخوان پشته (کال استک) نیز همین اتفاق می‌افتد. این اتفاق معمولاً نامطلوب است، اما به روش‌های جالبی مورد استفاده قرار گرفته است – به کامپایلر

Chicken Scheme

مراجعه کنید. همان‌طور که CPS و TCO مفهوم بازگشت ضمنی تابع را حذف می‌کنند، استفاده ترکیبی از آن‌ها می‌تواند نیاز به استکِ زمانِ اجرا (run-time stack) را نیز حذف کند. بسیاری از کامپایلرها و مفسرهای زبان‌های برنامه‌نویسی تابعی، از این توانایی به روش‌های جدیدی استفاده می‌کنند.

استفاده و پیاده‌سازی

از روش "ادامه‌دهی با انتقال پارمتر" می‌توان برای پیاده‌سازی تداوم‌ها و کنترل عملگر‌های جریان در یک زبان تابعی که دارای تداوم‌های کلاس-اول نیست اما دارای توابع کلاس-اول و بهینه‌سازی فراخوانی نهایی است، استفاده کرد. بدون بهینه‌سازی فراخوانی نهایی، می‌توان از تکنیک‌هایی مانند ترامپولین کردن، یعنی استفاده از حلقه‌ای که به‌طور مکرر توابع برگشت‌دهنده‌ی thunk را فراخوانی می‌کند، استفاده کرد. بدون توابع درجه یک، حتی می‌توان در چنین حلقه‌ای فراخوانی‌های نهایی را به فقط گوتوس(gotos، اصطلاح مربوط به فراخوانی‌های نهایی) تبدیل کرد. کد زدن در CPS، اگرچه غیر ممکن نیست، اغلب مستعد خطاست. ترجمه‌های مختلفی وجود دارد که معمولاً به عنوان تبدیل‌های یک انتقاله یا دوانتقاله از محاسبات لامبدای خالص تعریف می‌شوند که عبارات سبک مستقیم را به عبارت CPS تبدیل می‌کنند. با این حال، کد زدن به سبک ترامپولین بسیار دشوار است. زمانی که این روش استفاده می‌شود، معمولاً هدف نوعی تغییر شکل است، مانند کامپایل کردن. توابعِ استفاده‌کننده از بیش از یک تداوم را می‌توان برای گرفتن پارادایم‌های مختلف جریان کنترل تعریف کرد؛ به عنوان مثال (به زبان اسکیم):

(define (/& x y ok err)
 (=& y 0.0 (lambda (b)
            (if b
                (err (list "div by zero!" x y))
                (ok (/ x y))))))

شایان ذکر است که تبدیل CPS از نظر مفهومی یک جاسازی یوندا است. همچنین شبیه جاسازی محاسبات لامبدا در محاسبات عدد پی نیز هست.

استفاده در زمینه‌های دیگر

در خارج از علوم کامپیوتر، CPS به عنوان جایگزینی برای روش مرسوم برای ترکیب عبارات ساده به عبارات پیچیده مورد توجه عمومی است. برای مثال، در معناشناسی زبانی، کریس بارکر و همکارانش پیشنهاد کرده‌اند که تعیین نشانه‌های جملات با استفاده از CPS ممکن است پدیده‌های خاصی را در زبان طبیعی توضیح دهد. در ریاضیات، ایزومورفیسم کوری-هاروارد بین برنامه‌های کامپیوتری و برهان‌های ریاضی، ترجمه روش "ادامه دهی به روش انتقال پارامتر" را به تنوعی از تعبیه‌های دو نفی منطق کلاسیک به منطق شهودی (سازنده) مرتبط می‌کند. برخلاف ترجمه دو نفی معمولی، که گزاره‌های اتمی پی را به

((p → ⊥) → ⊥)

نگاشت می‌کند، CPS نماد

⊥

را با تایپ عبارت نهایی جایگزین می‌کند. بر این اساس، نتیجه با انتقال تابع همانی به عنوان تداوم عبارت CPS، مانند مثال بالا، به دست می‌آید. منطق کلاسیک به خودی خود مربوط به دستکاری تداوم برنامه‌ها به‌طور مستقیم است، همان‌طور که در عملگر کنترلیِ فراخوانی-با-تداوم-فعلی در اسکیم که مشاهده‌ای به دلیل تیم گریفین(با استفاده از عملگر کنترل سیِ بسیار مربوط) است نیز همین‌گونه است.

همچنین ببینید

بازگشت نهایی درحین تکنیک ترامپولین

ارجاعات

• Continuation Passing C (CPC) - programming language for writing concurrent systems, designed and developed by Juliusz Chroboczek and Gabriel Kerneis. github repository
• The construction of a CPS-based compiler for ام‌ال is described in: Appel, Andrew W. (1992). Compiling with Continuations. Cambridge University Press. ISBN 978-0-521-41695-5.
• Danvy, Olivier; Filinski, Andrzej (1992). "Representing Control, A Study of the CPS Transformation". Mathematical Structures in Computer Science. 2 (4): 361–391. CiteSeerX 10.1.1.46.84. doi:10.1017/S0960129500001535. S2CID 8790522.
• چیکن (پیاده‌سازی اسکیم), a اسکیم (زبان برنامه‌نویسی) to سی (زبان برنامه‌نویسی) compiler that uses continuation-passing style for translating Scheme procedures into C functions while using the C-stack as the nursery for the بازیافت حافظه
• Kelsey, Richard A. (March 1995). "A Correspondence between Continuation Passing Style and Static Single Assignment Form". ACM SIGPLAN Notices. 30 (3): 13–22. CiteSeerX 10.1.1.3.6773. doi:10.1145/202530.202532.
• Appel, Andrew W. (April 1998). "SSA is Functional Programming". ACM SIGPLAN Notices. 33 (4): 17–20. CiteSeerX 10.1.1.34.3282. doi:10.1145/278283.278285. S2CID 207227209.
• Danvy, Olivier; Millikin, Kevin; Nielsen, Lasse R. (2007). "On One-Pass CPS Transformations". BRICS Report Series: 24. ISSN 0909-0878. RS-07-6. Retrieved 26 October 2007.
• Dybvig, R. Kent (2003). The Scheme Programming Language. Prentice Hall. p. 64. Direct link: "Section 3.4. Continuation Passing Style".