مرحبا أقدم إليكم الجزء الثالث من ترجيمي للدليل لتطبيق لغة برمجة جافا سكريبت الخاصة بي - البرنامج التعليمي PL .

من المترجم

سنقوم بإنشاء لغة البرمجة الخاصة بنا - ((باللغة الأصلية - λanguage). في عملية الإنشاء ، سنستخدم الكثير من التقنيات المثيرة للاهتمام ، مثل النسب العودية ونمط نقل التحكم وتقنيات التحسين الأساسية. سيتم إنشاء نسختين من المترجم الشفهي - المترجمين العاديين والمترجمين الفوريين CPS ، المترجم الشفهي في JavaScript.

مؤلف النسخة الأصلية هو Mihai Bazon ، مؤلف مكتبة UglifyJS الشهيرة (أداة لتقليل وتنسيق رمز JS).

ملاحظة: يوجد خطأ في المترجم والمترجم: في التعبيرات مثل a() && b() أو a() || b() a() || b() يتم تنفيذ كلا الجزأين دائمًا. هذا ، بالطبع ، خاطئ لأن a() خطأ لـ && عامل التشغيل ، أو غير صحيح لـ || ، ثم لا تلعب قيمة b() أي دور. هذا ليس من الصعب إصلاحه.

CPS مترجم

لغتنا has لها عيبان:

• يقتصر العودية على مكدس JS ، لذلك ليس لدينا طريقة طبيعية للقيام بحلقات.
• المترجم بطيء ، لذلك العودية بطيئة للغاية.

الآن سنقوم بتصحيح الخلل الأول دون الانتباه إلى حقيقة أن المترجم الفوري سوف يصبح أبطأ. سنقوم بإعادة كتابة المترجم الفوري بأسلوب "نمط التمرير المستمر" (CPS).

ما هو "النقل المستمر"

يمكنك القيام بذلك في NodeJS طوال الوقت:

 fs.readFile("file.txt", "utf8", function CC(error, data){ //   - "" //     'return', // 'readFile'  ,  . }); 

في كل خطوة يوجد رد اتصال يتم الاتصال به عندما تحتاج إلى المتابعة. يجعل نمط النقل المستمر نقل التحكم "صريحًا" - لا تستخدم return أو throw أو break أو المتابعة. لا توجد القفزات الضمنية في التعليمات البرمجية. لا يمكنك حتى استخدام أو while حلقات مع وظائف غير متزامن. في هذه الحالة ، لماذا نحتاجها في لغة البرمجة؟

من الصعب وسهل ارتكاب أخطاء كتابة التعليمات البرمجية بأسلوب إرسال استمرارية ، لكننا لن نعيد كتابة المترجم الشفهي إلا بهذا النمط.

evaluate الوظيفة

ستتلقى دالة evaluate ثلاث وسائط: تعبير (AST) ، سياق (بيئة) ، والدالة التي سيتم استدعاؤها عندما تكون النتيجة. هنا هو الكود ، لكل جزء هناك تفسير:

 function evaluate(exp, env, callback) { switch (exp.type) { 

بالنسبة للثوابت ، سنعود فقط إلى قيمتها. لكن تذكر أنه ليس لدينا return - بل ندعو فقط رد الاتصال وننقل القيمة.

  case "num": case "str": case "bool": callback(exp.value); return; 

العقدة var بسيطة أيضًا - احصل على المتغير من السياق وقم بتمريره إلى الوظيفة:

  case "var": callback(env.get(exp.value)); return; 

بالنسبة إلى assign العقد ، نحتاج إلى الحصول على قيمة التعبير الأيسر ( right ). للقيام بذلك ، ندعو evaluate ، ويمر في وظيفة سوف تحصل على النتيجة (على الجانب الأيمن من التعبير). ثم ندعو callback مع القيمة المتغيرة ، ووضع المتغير في السياق الحالي:

  case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function(right){ callback(env.set(exp.left.value, right)); }); return; 

تقريبًا نفس الشيء بالنسبة إلى العقد من النوع binary ، ولكن هنا نحتاج أولاً إلى الحصول على قيمة الحقل left ، وعندها فقط قيمة الحقل right . ثم ندعو فقط رد الاتصال ، لتمرير نتيجة العملية:

  case "binary": evaluate(exp.left, env, function(left){ evaluate(exp.right, env, function(right){ callback(apply_op(exp.operator, left, right)); }); }); return; 

تبدو عقدة let أكثر تعقيدًا ، لكنها في الحقيقة بسيطة. لدينا بعض المتغيرات. قد يكون حقل def (القيمة الأولية) فارغًا ، وفي هذه الحالة سنقوم بتعيينه على false . ولكن إذا كانت هناك قيمة ، فعلينا أن ندعو إلى evaluate بشكل متكرر للحصول عليه.

إذا كنت قد عملت مع NodeJS من قبل ، فقد قمت بذلك عدة مرات من قبل. بسبب عمليات الاسترجاعات ، لا يمكننا استخدام ، لذلك ، يجب علينا تفسير هذه التعبيرات واحدًا تلو الآخر (تخيل أن وظيفة evaluate غير متزامنة). تحصل الدالة loop أدناه (تسمى فورًا) على السياق ورقم التعريف الذي يجب معالجته:

• إذا كان هذا الرقم يساوي عدد المتغيرات ( vars.length ) ، فهذا يعني أننا قد حددنا بالفعل كل التعبيرات حتى نتمكن من تنفيذ نص التعبير. يرجى ملاحظة أننا هذه المرة لا ندعو callback ، ولكن نجح في evaluate ، والذي سوف نسميها بعد ذلك.
• إذا كان هذا الرقم أقل ، فأنت بحاجة إلى حساب التعريف الحالي وتمرير وظيفة تستدعي loop(scope, i + 1) ، قبل نسخ السياق.
  

    case "let": (function loop(env, i){ if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function(value){ var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; 

ستتم معالجة عقدة lambda في وظيفة منفصلة ، كما كان من قبل:

  case "lambda": callback(make_lambda(env, exp)); return; 

من أجل تفسير if ، نحن أولاً تفسير الشرط. إذا لم تكن خاطئة ، فسنفسر تعبير "في then ، وفي حالة أخرى ، نفسر else إذا كان هناك تعبير ، أو نرجع false إن لم يكن. كما كان من قبل ، في then ، else ، فإننا نعبر عن callback أنه "إجراء يجب القيام به بعد تنفيذ" التعبير:

  case "if": evaluate(exp.cond, env, function(cond){ if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; 

يتم تفسير عقدة prog بشكل مشابه لعقدة let ، ولكن مع اختلاف أننا لسنا بحاجة لنسخ السياق أو تحديد المتغيرات. ومرة أخرى ، لدينا وظيفة loop تأخذ رقم تعبير. عندما تكون مساوية لـ prog.length ، فإننا قد أكملنا جميع التعبيرات prog.length ببساطة نتيجة التعبير الأخير (بكلمة "return" أعني أننا ندعو callback به). يرجى ملاحظة أننا نتذكر القيمة الأخيرة من خلال تمريرها كوسيطة إلى وظيفة loop (في البداية ، تكون false للحالة عندما يكون الجسم فارغًا):

  case "prog": (function loop(last, i){ if (i < exp.prog.length) evaluate(exp.prog[i], env, function(val){ loop(val, i + 1); }); else { callback(last); } })(false, 0); return; 

للحصول على عقدة من النوع call نحتاج إلى تفسير func ومن ثم يتم ترتيب جميع الوسائط. ومرة أخرى ، هناك وظيفة loop تعمل على نفس المبدأ مثل let أو prog ، مع الاختلاف الذي تقوم به الآن بإنشاء صفيف نتيجة لذلك:

  case "call": evaluate(exp.func, env, function(func){ (function loop(args, i){ if (i < exp.args.length) evaluate(exp.args[i], env, function(arg){ args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; 

حسنًا ، النهاية القياسية: إذا كنا لا نعرف ما يجب فعله ، فعليك استثناء:

  default: throw new Error("I don't know how to evaluate " + exp.type); } } 

قد تلاحظ أن كل case أعلاه تنتهي بكلمة return . ولكن لا توجد قيمة معادة - يتم تمرير النتيجة دائمًا إلى وظيفة callback .

وظيفة جديدة make_lambda

في هذا المترجم ، ستتلقى جميع الوظائف "استمرار" كحجة أولى - الوظيفة التي يجب أن نسميها لتمرير النتيجة. بعد ذلك هي الحجج المعتادة لهذه الوظيفة. إليك الرمز الجديد لوظيفة make_lambda :

 function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; } 

انه لا يختلف كثيرا. يضيف متغيرات جديدة إلى سياق جديد. أيضًا ، يجب أن نعتبر أن الوسيطة الأولى هي callback . أخيرًا ، يتم استخدام دالة evaluate لتنفيذ رمز الوظيفة في سياق جديد ، ولكن كما حدث من قبل ، نقوم بتمرير callback .

بالمناسبة ، هذا هو المكان الوحيد الذي استخدمت فيه الحلقة. هذا لأنه يتم حساب قيم الوسيطة بالفعل عند معالجة عقدة call .

وظائف محلية

في هذا المترجم ، تتلقى الدالات الأصلية callback كالوسيطة الأولى. يجب أن نتذكر هذا عندما نحدد وظائف الأصلي. فيما يلي نموذج التعليمة البرمجية للمترجم الجديد:

 var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; var ast = parse(TokenStream(InputStream(code))); var globalEnv = new Environment(); // define the "print" primitive function globalEnv.def("print", function(callback, txt){ console.log(txt); callback(false); // call the continuation with some return value // if we don't call it, the program would stop // abruptly after a print! }); // run the evaluator evaluate(ast, globalEnv, function(result){ // the result of the entire program is now in "result" }); 

اختبار قليلا

دعنا نحاول حساب أرقام فيبوناتشي مرة أخرى:

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(10)) ); 

ولكن ، إذا حاولنا إيجاد الرقم 27 ، فسنحصل على تجاوز سعة مكدس. بشكل عام ، تنمو المكدس الآن بشكل أسرع بكثير ، لذا اتضح أنه لا يمكننا الآن حساب عدد Fibonacci إلا في الثاني عشر (على الأقل في متصفحي). هذا ليس جيدًا جدًا ، لذلك تحتاج إلى إصلاحه بطريقة أو بأخرى.

نحن نحمي المكدس

في مترجم CPS ، ينمو المكدس بشكل أسرع لأن المترجم الشفوي يستدعي دائمًا الوظائف بشكل متكرر ، ولا يُرجع النتيجة أبدًا. رغم أننا عدنا إلى المترجم الفوري ، إلا أننا نحتاج إليهم ، لكن في حالة العودية العميقة جدًا ، لم نتمكن من الوصول إليهم أبدًا.

دعنا نتخيل كيف يبحث مجموعتنا عن برنامج بسيط للغاية. سأعرض الكود الزائف ولم env بإضافة env لأنه لا يلعب أي دور هنا:

 print(1 + 2 * 3); ## : evaluate( print(1 + 2 * 3), K0 ) evaluate( print, K1 ) K1(print) #  'var',      evaluate( 1 + 2 * 3, K2 ) evaluate( 2 * 3, K3 ) evaluate( 2, K4 ) K4(2) # 2  ,      evaluate( 3, K5 ) #    3,      K5(3) K3(6) #  2*3 evaluate( 1, K6 ) #  ,  K6(1) K2(7) #  1+2*3 print(K0, 7) # ,     'print' K0(false) #  . 'print'  'false'. 

فقط بعد آخر مكالمة ، فإن سلسلة طويلة من return عديمة الفائدة تقلل من الرصة. إذا استخدمنا مساحة كبيرة من المكدس لبرنامج بسيط ، فمن الصعب تخيل ما سيحدث لـ fib(13) .

حماية المكدس

في مترجمنا الجديد ، ببساطة ليست هناك حاجة إلى كومة. كل ما يجب القيام به بعد حدوث بعض التعبير في callback ، والذي يتم تمريره كوسيطة. إذن لدينا هنا سؤال: ماذا لو مكّن JavaScript من "تفريغ" المكدس. ثم يمكننا إسقاط المكدس ، وسيعمل الإعادة العميقة بلا حدود.

دعونا نتخيل أن لدينا وظيفة GUARD يمكنها القيام بذلك. يحصل على قيمتين: الوظيفة التي يجب الاتصال بها ، والحجج التي يجب أن يتم تمريرها. يتحقق: إذا كانت الحزمة مكدسة للغاية ، فسوف تقوم بمسح المكدس واستدعاء الوظيفة التي تم تمريرها. في حالة أخرى ، لا تفعل شيئًا.

باستخدام الوظيفة الجديدة ، نعيد كتابة المترجم الفوري كما هو موضح أدناه. لن أعلق على كل حالة على حدة ، فهناك الكود الذي تم وصفه مسبقًا ، ولكن باستخدام وظيفة GUARD :

 function evaluate(exp, env, callback) { GUARD(evaluate, arguments); switch (exp.type) { case "num": case "str": case "bool": callback(exp.value); return; case "var": callback(env.get(exp.value)); return; case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(env.set(exp.left.value, right)); }); return; case "binary": evaluate(exp.left, env, function CC(left){ GUARD(CC, arguments); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(apply_op(exp.operator, left, right)); }); }); return; case "let": (function loop(env, i){ GUARD(loop, arguments); if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function CC(value){ GUARD(CC, arguments); var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; case "lambda": callback(make_lambda(env, exp)); return; case "if": evaluate(exp.cond, env, function CC(cond){ GUARD(CC, arguments); if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; case "prog": (function loop(last, i){ GUARD(loop, arguments); if (i < exp.prog.length) evaluate(exp.prog[i], env, function CC(val){ GUARD(CC, arguments); loop(val, i + 1); }); else { callback(last); } })(false, 0); return; case "call": evaluate(exp.func, env, function CC(func){ GUARD(CC, arguments); (function loop(args, i){ GUARD(loop, arguments); if (i < exp.args.length) evaluate(exp.args[i], env, function CC(arg){ GUARD(CC, arguments); args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; default: throw new Error("I don't know how to evaluate " + exp.type); } } 

بالنسبة للوظائف المجهولة ، نحتاج إلى إضافة اسم حتى نتمكن من تمريرها إلى وظيفة GUARD . لقد استخدمت اسم CC ( current continuation ). يمكنك استخدام arguments.callee ، لكن هذا هو واجهة برمجة تطبيقات قديمة.

أيضا ، نفس التغيير في make_lambda :

 function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { GUARD(lambda, arguments); // <--  var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; } 

تنفيذ GUARD بسيط للغاية. كيفية الخروج من مكالمة عميقة؟ باستخدام استثناءات. للقيام بذلك ، سيكون هناك متغير عالمي يشير إلى مقدار العودية التي يمكننا القيام بها. إذا وصل إلى الصفر ، فإننا نرمي كائن Continuation ، حيث سيكون هناك استمرار - دالة ووسيطات:

 var STACKLEN; function GUARD(f, args) { if (--STACKLEN < 0) throw new Continuation(f, args); } function Continuation(f, args) { this.f = f; this.args = args; } 

وفي النهاية ، نحتاج إلى حلقة من شأنها التقاط أشياء Continuation . يجب علينا استدعاء المترجم الشفهي من خلال هذه الحلقة حتى يعمل كل شيء:

 function Execute(f, args) { while (true) try { STACKLEN = 200; return f.apply(null, args); } catch(ex) { if (ex instanceof Continuation) f = ex.f, args = ex.args; else throw ex; } } 

تقبل الدالة Execute الوظيفة المراد استدعاؤها والوسيطات الخاصة بها. إنها تعمل في حلقة ، ولكن عليك الانتباه إلى return إذا كانت الوظيفة تعمل دون تجاوز سعة المكدس ، فنحن نتوقف على الفور. STACKLEN إعادة تعيين STACKLEN كل مرة نبدأ تكرار حلقة. قيمة 200 - يناسب بشكل جيد. عندما Continuation كائن Continuation ، فإننا نستبدل وظيفة وسيطات جديدة ، ونواصل الحلقة. أيضًا ، بسبب استثناء ، يتم مسح المكدس ، بحيث يمكننا المتابعة.

لبدء المترجم الفوري ، نستخدم الآن Execute :

 Execute(evaluate, [ ast, globalEnv, function(result){ console.log("*** Result:", result); }]); 

اختبار

ستعمل وظيفة fib الآن:

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(20)) ); # 6765, ~300ms 

إنه لأمر مؤسف ، ولكن إذا حاولت العثور على fib(27) ، fib(27) الأمر حوالي أربعة أضعاف طول المترجم العادي. ولكن بعد ذلك لدينا الآن العودية لانهائية:

 sum = λ(n, ret) if n == 0 then ret else sum(n - 1, ret + n); # compute 1 + 2 + ... + 50000 time( λ() println(sum(50000, 0)) ); # 1250025000, ~700ms 

بالطبع ، اللغة sl أبطأ بكثير من JavaScript. فقط تخيل ، كل وصول إلى متغير يمر عبر كائن Environment . ليس من المنطقي محاولة تحسين المترجم الشفهي - فلن نحقق مكاسب كبيرة في الأداء. لتحسين الأداء ، هناك حل واحد: تجميع اللغة في JS ، وهذا ما سنفعله. في البداية ، دعونا نرى الأشياء المثيرة للاهتمام التي يمكننا القيام بها مع مترجم CPS.

استمرار

الآن بعد أن أصبح المترجم يعمل بأسلوب إرسال الاستمرارية ، تتلقى جميع الوظائف ، كل من وظائف λ language ووظائف JS الأصلية ، وظيفة الاستمرار كحجة أولى لإرجاع النتيجة (هذه الوسيطة مطلوبة لوظائف JavaScript ، على الرغم من أنها غير مرئية لوظائف λ language).

callback متغير يعني استمرار البرنامج بأكمله. كل ما سوف يقوم به البرنامج بعد ذلك. سوف نسمي هذا المتغير "استمرار الحالي" ، أو k في التعليمات البرمجية.

أيضًا ، إذا لم نتسبب في استمرار ، فسيتوقف البرنامج. لا يمكننا القيام بذلك من اللغة make_lambda لأن make_lambda يستدعي المتابعة على أي حال. ولكن يمكننا القيام بذلك من وظيفة أصلية. لقد قمت بعمل لإظهار كيف يعمل هذا:

 globalEnv.def("halt", function(k){}); 

هذه وظيفة لا تفعل شيئًا. تتلقى الاستمرارية ( k ) ، لكنها لا تسميها:

 println("foo"); halt(); println("bar"); 

الاستنتاج:

 foo 

إذا قمت بحذف استدعاء halt() ، فسيكون الإخراج: foo / bar / ***Result: false (لأن آخر println يُرجع false ). ولكن مع halt() وهذا فقط مخرجات foo . * الآن لا توجد نتيجة حتى لأن halt() لا يتسبب في استمرار ، وبالتالي ، فإن رد الاتصال الذي أجتزناه evaluate - الذي يعرض السلسلة ***Result ، لا يُطلق عليه مطلقًا. الوظيفة التي تسمى evaluate لا تلاحظ توقف البرنامج. في NodeJS ، سيكون ذلك تسديدة في القدم.

تخيل أننا بحاجة إلى وظيفة sleepe توقف البرنامج دون إيقاف المتصفح (وبالتالي ، بدون حلقات غبية). يمكننا بسهولة تنفيذ ذلك باستخدام وظيفة أصلية:

 globalEnv.def("sleep", function(k, milliseconds){ setTimeout(function(){ Execute(k, [ false ]); //   ,  'false' }, milliseconds); }); 

هناك إزعاج بسيط يتمثل في أنه يتعين علينا استخدام Execute ، لأن setTimeout سوف يتسبب في رد اتصال ، مما يؤدي إلى Continuation ، ولن يقوم أحد بالقبض عليه. إليك كيفية استخدامه:

 let loop (n = 0) { if n < 10 { println(n); sleep(250); loop(n + 1); } }; println("And we're done"); 

الاستنتاج:

 0 1 2 3 4 5 6 7 8 9 And we're done ***Result: false 

ملاحظة ، هناك تأخير بسيط بين كل سطر. يمكنك محاولة تشغيل هذا الرمز في المقالة الأصلية .

هذا بالفعل شيء لا يمكنك القيام به في JavaScript العادي ، باستثناء استخدام النقل اليدوي للاستمرار (وأيضًا ، لا يمكنك استخدام حلقة for ):

 (function loop(n){ if (n < 10) { console.log(n); setTimeout(function(){ loop(n + 1); }, 250); } else { println("And we're done"); //    } })(0); 

تخيل كيف يمكنك استخدام واجهة برمجة تطبيقات NodeJS بلغة::

 globalEnv.def("readFile", function(k, filename){ fs.readFile(filename, function(err, data){ // error handling is a bit more complex, ignoring for now Execute(k, [ data ]); // hope it's clear why we need the Execute }); }); globalEnv.def("writeFile", function(k, filename, data){ fs.writeFile(filename, data, function(err){ Execute(k, [ false ]); }); }); 

الاستخدام:

 copyFile = λ(source, dest) { writeFile(dest, readFile(source)); }; copyFile("foo.txt", "bar.txt"); 

وكل هذا يعمل بشكل غير متزامن. لا مزيد من الجحيم رد الاتصال.

هنا مثال أكثر إثارة للاهتمام. كتبت الوظيفة الأصلية التالية:

 globalEnv.def("twice", function(k, a, b){ k(a); k(b); }); 

يأخذ البرنامج الوسيطتين a و b ويدعو إلى الاستمرار مرتين ، مرة واحدة لكل وسيطة. لنحاول الاتصال بها:

 println(2 + twice(3, 4)); println("Done"); 

الاستنتاج:

 5 Done ***Result: false 6 Done ***Result: false 

الاستنتاج غريب إذا لم تكن قد عملت مطلقًا مع تجاوزات مستمرة من قبل ، لكن حاول فهم هذا الرمز بنفسك. بعض التلميحات: يبدأ البرنامج مرة واحدة ، لكنه يعرض النتيجة مرتين.

التعميم: CallCC

كنا نلعب بالنار عندما كتبنا وظائف محلية. لا توجد طريقة في اللغة لمقاطعة تنفيذ الاستمرارية الحالية. سوف CallCC تساعد في حل هذه المشكلة. الاسم هو اختصار الوظيفة من المخطط - call-with-current-continuation (والذي يسمى عادةً استدعاء / سم في المخطط).

 globalEnv.def("CallCC", function(k, f){ f(k, function CC(discarded, ret){ k(ret); }); }); 

يقوم بإعادة ضبط الاستمرارية الحالية إلى وظيفة يمكن استدعاؤها مباشرة من لغة λ. ستتجاهل هذه الوظيفة استمرارها الأصلي discarded CallCC بدلاً من ذلك الاستمرار الذي تم تمريره إلى وظيفة CallCC .

باستخدام هذه الوظيفة ، يمكننا تنفيذ (بالفعل مباشرة في اللغة ، وليس من خلال وظائف أصلية!) مجموعة كبيرة من عبارات التحكم لتدفق التنفيذ التي لم نفكر فيها من قبل - بدءًا من الاستثناءات ونهاية return . لنبدأ من الأخير.

return التنفيذ

 foo = λ(return){ println("foo"); return("DONE"); println("bar"); }; CallCC(foo); 

الاستنتاج:

 foo ***Result: DONE 

تتلقى الدالة foo وسيطة تقوم بنفس طريقة return من JavaScript (ولكن تسمى وظيفة عادية). إنه يتخطى الاستمرارية الحالية (والتي من شأنها إخراج 'شريط') ويخرج من الوظيفة ، ويعيد القيمة المحددة ("تم"). بالطبع ، هذا يعمل فقط إذا قمت باستدعاء دالة باستخدام CallCC لتمرير الاستمرارية CallCC . يمكننا إنشاء غلاف لهذا:

 with-return = λ(f) λ() CallCC(f); foo = with-return(λ(return){ println("foo"); return("DONE"); println("bar"); }); foo(); 

الاستنتاج:

 foo ***Result: DONE 

ميزة هذه الطريقة هي أننا لم نعد بحاجة إلى استخدام CallCC عندما نسمي foo . سيكون من الرائع ، بالطبع ، إذا لم نكن بحاجة إلى قبول return كوسيطة أو استخدام الدالة with-return ، ولكن في اللغة لا توجد طريقة لإضافة السكر النحوي مباشرةً منه ، لهذا نحن بحاجة على الأقل إلى تعديل المحلل اللغوي (+1 لـ Lisp).

التحولات

على سبيل المثال ، نحتاج إلى كتابة برنامج يبحث عن جميع أزواج الأعداد الصحيحة الموجبة التي تصل إلى 100 بحيث إذا كانت الضرب تعطي 84. هذه ليست مهمة صعبة ويمكنك أن تتخيل على الفور حلقتين متداخلتين لحلها ، ولكن هنا نذهب بطريقة مختلفة. سنقوم بإنشاء وظيفتين: guess fail . الأول سيختار الرقم ، والثاني يقول لها "جرب رقمًا آخر". سوف نستخدمها مثل هذا:

 a = guess(1); #  -  >= 1 b = guess(a); #  -  >= a if a * b == 84 { #    : print(a); print(" x "); println(b); }; fail(); #    `guess`     

:

 fail = λ() false; guess = λ(current) { CallCC(λ(k){ let (prevFail = fail) { fail = λ(){ current = current + 1; if current > 100 { fail = prevFail; fail(); } else { k(current); }; }; k(current); }; }); }; a = guess(1); b = guess(a); if a * b == 84 { print(a); print(" x "); println(b); }; fail(); 

, , a , 84 , b , 84 / a . guess : start end — . , .

try catch Common Lisp

— catch throw . :

 f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); })); #  EXIT 

• catch(TAG, function) , , TAG ', function .
• throw(TAG, value) , , TAG ' , value .

:

 ##  , 'throw'   . ##       `error`, ##     JavaScript.    . throw = λ(){ println("ERROR: No more catch handlers!"); halt(); }; catch = λ(tag, func){ CallCC(λ(k){ let (rethrow = throw, ret) { ##   ,     . throw = λ(t, val) { throw = rethrow; #   ,   . if t == tag then k(val) else throw(t, val); }; ##      . ret = func(); ##       (  'throw') ##    .   . throw = rethrow; # XXX ##  . ret; }; }); }; 

مثال:

 # ... f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); })); 

catch , , , . , , , CallCC . , . " " — — . , , , catch / throw , .

. , catch . , throw , , catch , . على سبيل المثال:

 exit = false; #  . x = 0; # :   ,   'exit()'  CallCC( λ(k) exit = k ); ## 'exit()'   ... if x == 0 then catch("foo", λ(){ println("in catch"); x = 1; #  exit(); }); println("After catch"); throw("foo", "FOO"); 

الاستنتاج:

 After catch After catch ERROR: No more catch handlers! 

'After catch' , 'ERROR: No more catch handlers!'. - , 'After catch' , . , '' , catch . , 'XXX' catch , throw , catch .

( , .)

CallCC (, , CallCC ). , — CallCC .

Yield

, , yield :

 foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); # 1 println(foo()); # 2 println(foo()); # 3 println(foo()); # DONE 

yield , . , return . , , yield , .

:

 fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

fib . . yield . , , 50 , 50 .

, , , , .

, .

yield , , . , , return . , , yield , yield , . , . :

 with-yield = λ(func) { ## with-yield     λ() { CallCC(λ(kret){ # kret     let (yield) { ##  yield yield = λ(value) { # yield  ,    CallCC(λ(kyld){ # kyld    yield... func = kyld; # ...     kret(value); #  . }); }; ## , ,  ,   yield. func(yield); }; }); }; }; 

yield , . , , , "DONE".

, . , - , , 4 :

 println(foo()); foo(); 

.

№1: yield

, , , , yield ( kyld , , ) :

  yield(2); yield(3); "DONE"; 

yield ? yield , , yield . , . , yield return , :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); # 'return'  ,     }); #        . }; # λ(val) { # CallCC(λ(kret){ # return = kret; # <-  func(val || yield); }); }; }; }; 

, , yield , yield ( ). yield .

, , println(foo()) :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; func(val || yield); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); 

, . , print(foo()); foo() . , println(foo()) ? ...

№2: WTF?

. : , foo() . , ? — .

 println(foo()); ## yield 1 <-----------------  ---------------------------+ println(foo()); ## yield 2 | println(foo()); ## yield 3 | println(foo()); ##   "DONE",   foo()  -->--+ 

with-yield :

  func(val || yield); #... 

yield , , #... . , , ( "DONE" ), , "DONE" , . foo() , "DONE" . :

 println(foo()); println("bar"); println(foo()); println(foo()); foo(); 

: 1, bar, 2, 3, DONE, bar, DONE, bar, ... .

func - , . , "no more continuations" :

  val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); 

:

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); println(foo()); 

, :

 1 2 3 DONE NO MORE CONTINUATIONS NO MORE CONTINUATIONS NO MORE CONTINUATIONS ***Result: false 

1, 2, 3, DONE , "NO MORE CONTINUATIONS" . , :

 print("A. "); println(foo()); print("B. "); println(foo()); print("C. "); println(foo()); print("D. "); println(foo()); ##   : A. 1 B. 2 C. 3 D. DONE B. NO MORE CONTINUATIONS C. NO MORE CONTINUATIONS D. NO MORE CONTINUATIONS ***Result: false 

, : , , , , "B." .

, yield , :

 with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 ***Result: false 

, (, ), " ".

: reset shift

yield : reset shift . " " — , . reset , shift , CallCC .

, reset shift — . reset , shift , reset .

, with-yield :

 with-yield = λ(func) { let (yield) { ## 'yield'  'shift'     ##  'reset'.  ,   ,    ##   'func' — ,   `func()` ##    ,    . yield = λ(val) { shift(λ(k){ func = k; #    val; #    }); }; ##  `with-yield`      ##   'reset',    ,  ##   'yield' ( )    ##    λ(val) { reset( λ() func(val || yield) ); }; } }; 

, reset . , , , reset . , . , .

:

 with-yield = λ(func) { let (yield) { yield = λ(val) { shift(λ(k){ func = k; val; }); }; λ(val) { reset( λ() func(val || yield) ); }; } }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); #  1 println(foo()); #  2 println(foo()); #  3 println(foo()); #  DONE 

reset shift

, . . . , , , . Scheme ( — Oleg Kiselyov ). .

, ( CallCC ) . :

 var pstack = []; function _goto(f) { f(function KGOTO(r){ var h = pstack.pop(); h(r); }); } globalEnv.def("reset", function(KRESET, th){ pstack.push(KRESET); _goto(th); }); globalEnv.def("shift", function(KSHIFT, f){ _goto(function(KGOTO){ f(KGOTO, function SK(k1, v){ pstack.push(k1); KSHIFT(v); }); }); }); 

, reset , shift _goto , — . . _goto ( KGOTO ). , f ( CallCC ) - KGOTO , . , f , , KGOTO , , .

reset ( KRESET ) _goto(th) . , , , _goto . , , KGOTO KRESET .

, shift KGOTO , KGOTO pstack , SK , , shift ( shift — KSHIFT ). SK — — ( k1 ) . , shift2 , , pstack.push(k1); :

 println(reset(λ(){ 1 + shift( λ(k) k(k(2)) ); })); println(reset(λ(){ 1 + shift2( λ(k) k(k(2)) ); })); 

الاستنتاج:

 4 3 ***Result: false 

shift ( k ), reset . — 1 shift :

 1 + [?] 

k , ? . — k(k(2)) . 2 , k(2) 3. , k(3) 3 , 4.

shift2 : k(2) .

CallCC

, , CallCC , . , JS, , , . , CallCC , .

— goto , ( ):

 pstack = NIL; goto = false; reset = λ(th) { CallCC(λ(k){ pstack = cons(k, pstack); goto(th); }); }; shift = λ(f) { CallCC(λ(k){ goto(λ(){ f(λ(v){ CallCC(λ(k1){ pstack = cons(k1, pstack); k(v); }); }); }); }); }; let (v = CallCC( λ(k){ goto = k; k(false) } )) { if v then let (r = v(), h = car(pstack)) { pstack = cdr(pstack); h(r); } }; 

— !