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

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

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

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)))))))))

توجه کنید که در ورژن سی.پی.اس، متغیرهای اولیه استفاده‌شده، مثل &+ و &* خودشان سی.پی.اس هستند نه روش مستقیم، بنابراین برای اینکه مثال‌های بالا در سيستم زبان اسكيم كار كنند نياز داريم كه ورژن سی.پی.اس آن‌ها را بنویسیم. برای مثال &* به این وسیله تعریف می‌شود:

(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 +))

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

(factorial& 10 (lambda (x) (display x) (newline)))

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

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

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

f-aux&

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

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

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

if&

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

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

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

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))

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

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)))

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

pyth' 3 4 id == 5.0

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

Control.Monad.Cont

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

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_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

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

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

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

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

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

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();
}

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

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

Chicken Scheme

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

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

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

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

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

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

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

((p → ⊥) → ⊥)

نگاشت می‌کند، سی.پی.اس نماد

⊥

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

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

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

ارجاعات

• 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 ML 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.
• Chicken Scheme compiler, a Scheme to C compiler that uses continuation-passing style for translating Scheme procedures into C functions while using the C-stack as the nursery for the generational garbage collector
• 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".