Call/CC في لوا - ممكن؟

Question

مقال ويكيبيديا عن استمرار يقول:
"بأي لغة تدعم الإغلاق, ، من الممكن كتابة البرامج بأسلوب المرور المستمر و قم بتنفيذ CALL/CC يدويًا."

إما أن يكون هذا صحيحًا وأحتاج إلى معرفة كيفية القيام بذلك أو أنه غير صحيح ويجب تصحيح هذا البيان.

إذا كان هذا صحيحًا ، فالرجاء إظهار كيفية تنفيذ Call/CC في LUA لأنني لا أستطيع رؤية كيف.

أعتقد أنني سأكون قادرًا على تنفيذ Call/CC يدويًا إذا كان Lua لديه وظيفة coroutine.clone كما هو موضح هنا.

إذا لم تكن عمليات الإغلاق كافية لتنفيذ CALL/CC ، فما الذي هو مطلوب؟

النص أدناه هو قراءة اختيارية.
PS: LUA لديه استمرارية واحدة مع طاولة Coroutine. ستسمح لي وظيفة coroutine.clone باستنساخها لاتصالها عدة مرات ، وبالتالي إجراء مكالمة/CC بشكل فعال (ما لم أسيء فهم الاتصال/CC). ومع ذلك ، فإن وظيفة الاستنساخ غير موجودة في لوا. اقترح شخص ما على قناة Lua IRC أن أستخدم مكتبة بلوتو (تنفذ التسلسل) لمرشدة coroutine ، ونسخها ثم قم بإلغاء تحديدها واستخدامها مرة أخرى. على الرغم من أن ذلك قد ينجح ، فأنا مهتم أكثر بالتنفيذ النظري لـ Call/CC وفي العثور على الحد الأدنى الفعلي للميزات التي تحتاجها اللغة للسماح بتنفيذها اليدوي.

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

ملاحظة: هذه الأمثلة مأخوذة من المثال الأول على مقالة ويكيبيديا على Callcc. نسخة مخطط

(define call/cc call-with-current-continuation)

; callcc CPS-transformed (thanks to the people from the #scheme channel at freenode.net)
(define cpscallcc
  (lambda (consumer k)
    (let ((cc (lambda (result) (k result))))
      (consumer cc k))))

; this is the continuation we will use to display the "returned" values
(define main-continuation
  (lambda (result)
    (display "--> ")
    (display result)
    (newline)))

; define f function non-CPS
(define (f return)
  (return 2)
  3)

; these are my past attempts at defining a CPS f function
;(define (cps-f return k)
;  (k (return 2)) 3)
;(define (cps-f return k)
;  (k (lambda ()
;       (return 2)
;       3)))

; this is what I came up with - I'm not sure if this is correctly CPS-transformed but I     believe so
(define (cps-f return k)
  (return 2)
  (k 3))

; call the non-CPS f function
(display (f (lambda (x) x))) ; displays 3
(newline)

; call the non-CPS f function with call/cc (I don't understand what this does)
(display (call/cc f)) ; displays 2
(newline)

; now call the CPS version of the f function
(cps-f (lambda (x) x) main-continuation)  ; displays --> 3

; now call the CPS version of the f function with the CPS version of call/cc
(cpscallcc cps-f main-continuation)  ; displays --> 2 but then it also displays --> 3 afterwards -> I'm not sure why it displays the 3 afterwards, as it should only display the 2 just like the non-CPS versions above

نسخة لوا

-- callcc CPS-version
cpscallcc = function(consumer, k)
    local cc = function(result)
        return k(result)  -- ?or k(result)
    end
    return consumer(cc, k)  -- ?or return consumer(cc,k)
end

-- define f function non-CPS
f = function(ret)
    ret(2)
    return 3
end

-- define f function CPS-version (again, not sure this is correct)
cps_f = function(ret, k)
    ret(2)
    k(3)
end

-- call the non-CPS f function
print(f(function(x) return x end))

-- we cant call the non-CPS f function with callcc because
-- Lua doesnt have callcc, but the line below displays the correct expected output (maybe by accident)
--cpscallcc(f, print)

-- now call the CPS version of the f function
cps_f( function(x) return x end, print )  -- displays 3

; now call the CPS version of the f function with the CPS version of call/cc
cpscallcc( cps_f, print) -- displays 2 and then 3 just like the Scheme version!!
-- so apparently the translation from Scheme to Lua is correct...

أنا أستخدم DrScheme و Lua لنظام التشغيل Windows - لأي شخص يريد المساعدة في التغلب على هذين من السهل تنزيل وتثبيت أدوات تعمل فقط.

Answer 1

هناك شروطان أساسيان لتنفيذ Call/CC يدويًا لكل اقتباس ويكيبيديا:

1. يجب أن تدعم اللغة الإغلاق
2. يجب أن تكتب برنامجك بأسلوب المرور المستمر (CPS)

أظن أنك لن تحب #2.

لكتابة برنامجك بأسلوب المرور المستمر:

1. يجب أن تأخذ كل وظيفة حجة استمرار
2. يجب أن تعود الوظائف عن طريق استدعاء استمرارها

لذلك ، باستخدام k كاسم وسيطة الاستمرار ، ستبدو الوظيفة:

function multiplyadd(k, x, y, z) return k(x * y + z) end

قد يستخدم toplevel print كاستمرار لها ، لذلك التذرع multiplyadd في المستوى الأعلى سيبدو مثل:

multiplyadd(print, 2, 4, 1)

مع هذا السقالة ، يمكننا تحديد Call/CC كما

function callcc(k,f) return f(k,k) end

لاحظ أن ما سبق multiplyadd في الواقع الغش منذ ذلك الحين * و + ليست في CPS. من الممل للغاية إضافة جميع المشغلين في نموذج CPS ، واستبدل جميع وظائف مكتبة LUA بمكافئات CPS ، وترجمة/إنشاء جميع التعليمات البرمجية الخاصة بك إلى CPS ؛ يرى التفاصيل هنا.

Answer 2

أعتقد أنك نسيت الجزء حول كتابة برنامجك بأسلوب المرور المستمر. بمجرد القيام بذلك ، تكون Call/CC تافهة (في LUA أو في أي لغة أخرى) ، لأن الاستمرار ستكون معلمة صريحة لجميع الوظائف (Call/CC المدرجة).

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

Answer 3

الإجابة على سؤال حول خطط الاتصال/CC في لوا: لا توجد خطط للاتصال/CC في لوا. يعد التقاط استمرار مكلفًا للغاية أو يتطلب بعض الكود الذي يتجاوز ما يمكن أن يفعله برنامج التحويل البرمجي LUA. هناك أيضًا المشكلة التي قد تتضمنها استمرارية LUA أجزاء في C.

ومع ذلك ، مع Coroutines ، يمكننا بالفعل تنفيذ Call/CC1 في LUA (استمرارية طلقة واحدة). هذا جيد بما يكفي للعديد من استخدامات الاستمرارية.

Answer 4

العبارة الرئيسية هي

من الممكن تنفيذ البرامج في نمط التماس الاستمرار

(منجم التأكيد.) يمكنك القيام بذلك عن طريق أخذ برامج "على الطريقة المباشرة" العادية وتحويلها إلى نمط التمرير (CPS) من خلال تحويل البرنامج يسمى تحويل CPS. المفتاح هو أن تحويل CPS من call/cc هي وظيفة بسيطة.

هذا ليس عمليًا للمبرمجين. يحول CPS استخدامان:

• كفكرة نظرية لدراسة ميزات اللغة ، وخاصة عوامل التحكم
• كتمريرة في برنامج التحويل البرمجي الذي يستخدم CPS كلغة وسيطة

لا تريد الذهاب إلى أي مكان بالقرب من إجراء تحويلات CPS على رمز LUA ، خاصة ليس باليد.

Answer 5

من الممكن: برنامج التحويل البرمجي إلى Lua TypeScript https://github.com/roblox-ts/roblox-ts + Call-CC في JS https://github.com/zaoqi/callcc.js/blob/master/callcc.js

Answer 6

إليك CPS-Convert in Scheme ، فقط تمرير كل وظيفة تريد تحويلها.

(define (cps-convert function . functions)
  # Since "help" is called at 2 different places...
  (define (help) (error "syntax: (cps-convert f1 f2 ...)"))
  # Single function converter
  (define (convert func)
    # "name" contains the function's name prefixed with "cps-"
    (let ([name (string->symbol
                          (string-append "cps-" (symbol->string func)))])
      # Dirty hack to define "cps-*" in the global environment
     `(eval '(begin
                   # Necessary to prevent the function from being evaluated
                   (define ,name #f)
                                # Magic
                   (set! ,name (lambda (k . args) (k (func args)))))
                 # Global environment
                 (interaction-environment))))
  # Prerequisite... Call help if condition not met
  (if (symbol? function)
      # function is a symbol
      (cond
        # If there is only one function to convert
        [(null? functions) (convert function)]
        # Else ensure every other "functions" are symbols and convert each
        [(every symbol? functions) (apply convert function functions)]
        # Oops! Condition not met!
        [else (help)])
      # Else clause from previous "if"
      (help)))