كيف يعمل اللغز Yin-Yang؟

https://stackoverflow.com/questions/2694679

01-10-2019
|

سؤال

أحاول فهم دلالات الاتصال/CC في المخطط ، وتظهر صفحة ويكيبيديا على الاستمرارية لغز Yin-Yang كمثال:

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))) )
    (yin yang))

يجب أن يخرج @*@**@***@****@..., ، لكني لا أفهم لماذا ؛ كنت أتوقع إخراجها @*@*********...

هل يمكن لأي شخص أن يشرح بالتفصيل لماذا يعمل لغز Yin-Yang بالطريقة التي يعمل بها؟

المحلول

لا أعتقد أنني أفهم هذا الأمر تمامًا ، لكن لا يمكنني التفكير إلا في واحد (الى ابعد حد توضيح يدوي) شرح لهذا:

يتم طباعة أول @ و * yin و yang يتم ربطها لأول مرة في let*. (yin yang) يتم تطبيقه ، ويعود إلى الأعلى ، مباشرة بعد الانتهاء من المكالمة الأولى/CC.
تتم طباعة @ و * التالي ، ثم يتم طباعة آخر * لأنه هذه المرة ، yin يتم إعادة ربطها بقيمة المكالمة الثانية/CC.
(yin yang) يتم تطبيقه مرة أخرى ، ولكن هذه المرة إنها تنفذ في الأصل yangبيئة, ، أين yin مرتبط بالمكالمة الأولى/CC ، لذلك يعود التحكم إلى طباعة @آخر. ال yang تحتوي الحجة على الاستمرار الذي تم إعادة تكوينه في الممر الثاني ، والذي سيؤدي ذلك كما رأينا بالفعل ، إلى الطباعة **. لذلك في هذا الممر الثالث ، @* سيتم طباعتها ، ثم يتم استمرار استمرار طباعة النجوم المزدوجة هذا ، لذلك ينتهي به الأمر 3 نجوم ، ثم يتم إعادة تكوين استمرار النجوم الثلاثي ، ...

نصائح أخرى

فهم مخطط

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

بادئ ذي بدء ، أجد شخصيا call/cc x أن تكون أكثر صعوبة في الفهم من البديل المكافئ ، x get/cc. لا يزال المكالمات x ، اجتيازها الاستمرار الحالي, ، لكن بطريقة ما يكون أكثر قابلية للتمثيل في دوائر عقلي.

مع وضع ذلك في الاعتبار ، البناء (call-with-current-continuation (lambda (c) c)) يصبح ببساطة get-cc. نحن الآن وصولنا إلى هذا:

(let* ((yin
         ((lambda (cc) (display #\@) cc) get-cc))
       (yang
         ((lambda (cc) (display #\*) cc) get-cc)) )
    (yin yang))

والخطوة التالية هي جسم Lambda الداخلي. (display #\@) cc, ، في بناء الجملة الأكثر دراية (بالنسبة لي ، على أي حال) print @; return cc;. بينما نحن في ذلك ، دعنا نعيد كتابة أيضًا lambda (cc) body كما function (arg) { body }, ، قم بإزالة مجموعة من الأقواس ، وتغيير مكالمات الوظائف إلى بناء جملة C-like ، للحصول على هذا:

(let*  yin =
         (function(arg) { print @; return arg; })(get-cc)
       yang =
         (function(arg) { print *; return arg; })(get-cc)
    yin(yang))

لقد بدأ الأمر أكثر منطقية الآن. إنها الآن خطوة صغيرة لإعادة كتابة هذا تمامًا في بناء جملة تشبه C (أو يشبه JavaScript ، إذا كنت تفضل) ، للحصول على هذا:

var yin, yang;
yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);

انتهى الجزء الأصعب الآن ، لقد قمنا بفك تشفير هذا من المخطط! أنا فقط أمزح؛ كان الأمر صعبًا لأنه لم يكن لدي أي خبرة سابقة في المخطط. لذلك ، دعنا نتعرف على كيفية عمل هذا بالفعل.

تمهيدي على الاستمرارية

راقب جوهر Yin و Yang بشكل غريب: يحدد وظيفة ثم يدعوها على الفور. يبدو مثل (function(a,b) { return a+b; })(2, 3), والتي يمكن تبسيطها 5. لكن تبسيط المكالمات داخل Yin/Yang سيكون خطأً ، لأننا لا نمررها قيمة عادية. نحن نمر الوظيفة أ استمرار.

الاستمرار هو وحش غريب من النظرة الأولى. النظر في البرنامج أبسط بكثير:

var x = get-cc;
print x;
x(5);

بدءًا x تم تعيينه على كائن الاستمرار الحالي (دب معي) ، و print x يتم تنفيذها ، طباعة شيء مثل <ContinuationObject>. حتى الان جيدة جدا.

لكن الاستمرار يشبه الوظيفة ؛ يمكن استدعاؤه بحجة واحدة. ما تفعله هو: خذ الحجة ، ثم القفز إلى أينما تم إنشاء هذا الاستمرار ، واستعادة كل السياق ، وجعله كذلك get-cc يعيد هذه الحجة.

في مثالنا ، الحجة هي 5, ، لذلك نحن نقفز بشكل أساسي إلى منتصف ذلك var x = get-cc بيان ، فقط هذه المرة get-cc عائدات 5. لذا x يصبح 5, ويمضي البيان التالي للطباعة 5. بعد ذلك نحاول الاتصال 5(5), ، وهو خطأ في النوع ، ويتعطل البرنامج.

لاحظ أن استدعاء الاستمرار هو أ القفز, ، وليس مكالمة. لا يعود أبدًا إلى حيث تم استمرار الاستمرار. هذا مهم.

كيف يعمل البرنامج

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

yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);

يتم ضرب السطر الأول 1 و 2 ، فهي بسيطة الآن: احصل على الاستمرار ، واتصل بالوظيفة (ARG) ، والطباعة @, ، عودة ، تخزين هذا الاستمرار في yin. نفس الشيء مع yang. لقد طبعنا الآن @*.

بعد ذلك ، نسمي الاستمرار في yin, ، تمريره yang. هذا يجعلنا نقفز إلى السطر 1 ، داخل هذا GET-CC ، وجعله يعود yang في حين أن. قيمة ال yang يتم تمريره الآن إلى الوظيفة التي تطبع @, ثم يعيد قيمة yang. حاليا yin تم تعيين ذلك الاستمرار yang لديها. بعد ذلك ، ننتقل فقط إلى السطر 2: الحصول على C/C ، طباعة *, ، تخزين C/C في yang. لدينا الآن @*@*. وأخيرا ، نذهب إلى السطر 3.

تذكر ذلك yin الآن لديه استمرار عندما تم تنفيذ السطر 2 لأول مرة. لذلك نقفز إلى السطر 2 ، طباعة ثانية * والتحديث yang. لدينا الآن @*@**. أخيرًا ، اتصل yin استمرار مرة أخرى ، والتي ستقفز إلى السطر 1 ، طباعة أ @. وهلم جرا. بصراحة ، في هذه المرحلة ، يرمي عقلي استثناءًا خارجًا ويفقد كل شيء. لكن على الأقل وصلنا إلى @*@**!

من الصعب اتباع هذا ، بشكل أكثر صعوبة ، من الواضح. الطريقة المثالية للقيام بذلك هي أن تتجول في أحد الأخطاء التي يمكن أن تمثل التواصل ، لكن للأسف ، لا أعرف أيًا منها. أتمنى أن تكون قد استمتعت بهذا ؛ أنا بالتأكيد.

تأملات أولاً ، الإجابة المحتملة في النهاية.

أعتقد أن الكود يمكن إعادة كتابته مثل هذا:

; call (yin yang)
(define (yy yin yang) (yin yang))

; run (call-yy) to set it off
(define (call-yy)
    (yy
        ( (lambda (cc) (display #\@) cc) (call/cc (lambda (c) c)) )
        ( (lambda (cc) (display #\*) cc) (call/cc (lambda (c) c)) )
     )
)

أو مع بعض عبارات العرض الإضافية للمساعدة في معرفة ما يحدث:

; create current continuation and tell us when you do
(define (ccc)
    (display "call/cc=")
    (call-with-current-continuation (lambda (c) (display c) (newline) c))
)

; call (yin yang)
(define (yy yin yang) (yin yang))

; run (call-yy) to set it off
(define (call-yy)
    (yy
        ( (lambda (cc) (display "yin : ") (display #\@) (display cc) (newline) cc) 
            (ccc) )
        ( (lambda (cc) (display "yang : ") (display #\*) (display cc) (newline) cc) 
            (ccc) )
     )
)

او مثل هذا:

(define (ccc2) (call/cc (lambda (c) c)) )
(define (call-yy2)
    (
        ( (lambda (cc) (display #\@) cc) (ccc2) )
        ( (lambda (cc) (display #\*) cc) (ccc2) )
    )
)

الإجابة المحتملة

قد لا يكون هذا صحيحًا ، لكنني سأذهب.

أعتقد أن النقطة الأساسية هي أن استمرار "يسمى" يعيد المكدس إلى بعض الحالة السابقة - كما لو لم يحدث شيء آخر. بالطبع لا يعلم أننا نراقبها من خلال العرض @ و * الشخصيات.

نحدد في البداية yin لتكون استمرارا A هذا سيفعل هذا:

1. restore the stack to some previous point
2. display @
3. assign a continuation to yin
4. compute a continuation X, display * and assign X to yang
5. evaluate yin with the continuation value of yang - (yin yang)

ولكن إذا اتصلنا yang استمرار ، هذا يحدث:

1. restore the stack to some point where yin was defined
2. display *
3. assign a continuation to yang
4. evaluate yin with the continuation value of yang - (yin yang)

نبدأ هنا.

أول مرة من خلالك تحصل عليها yin=A و yang=B كما yin و yang يتم تهيئة.

The output is @*

(كلاهما A و B يتم حساب الاستمرارية.)

حاليا (yin yang) يتم تقييمه على النحو (A B) لأول مرة.

نحن نعرف ماذا A يفعل. يفعل هذا:

1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B, we don't compute it.
4. compute another continuation B', display * and assign B' to yang

The output is now @*@*

5. evaluate yin (B) with the continuation value of yang (B')

حاليا (yin yang) يتم تقييمه على النحو (B B').

نحن نعرف ماذا B يفعل. يفعل هذا:

1. restore the stack - back to the point where yin was already initialised.
2. display *
3. assign a continuation to yang - this time, it is B'

The output is now @*@**

4. evaluate yin with the continuation value of yang (B')

منذ استعادة المكدس إلى حد yin=A, (yin yang) يتم تقييمه على النحو (A B').

نحن نعرف ماذا A يفعل. يفعل هذا:

1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B', we don't compute it.
4. compute another continuation B", display * and assign B" to yang

The output is now @*@**@*

5. evaluate yin (B') with the continuation value of yang (B")

نحن نعرف ماذا B' يفعل. يفعل هذا:

1. restore the stack - back to the point where yin=B.
2. display *
3. assign a continuation to yang - this time, it is B"

The output is now @*@**@**

4. evaluate yin (B) with the continuation value of yang (B")

حاليا (yin yang) يتم تقييمه على النحو (B B").

نحن نعرف ماذا B يفعل. يفعل هذا:

1. restore the stack - back to the point where yin=A and yang were being initialised.
2. display *
3. assign a continuation to yang - this time, it is B'"

The output is now @*@**@***

4. evaluate yin with the continuation value of yang (B'")

منذ استعادة المكدس إلى حد yin=A, (yin yang) يتم تقييمه على النحو (A B'").

.......

أعتقد أن لدينا نمط الآن.

في كل مرة ندعو (yin yang) نحن نحلق من خلال كومة من B استمرارية حتى نعود إلى متى yin=A ونحن نعرض @. نحن حلقة من خلال كومة B الاستمرارية كتابة أ * كل مرة.

(سأكون سعيدًا حقًا إذا كان هذا صحيحًا تقريبًا!)

شكرا على السؤال.

Yinyang اللغز مكتوبة في مخطط. أفترض أنك تعرف بناء الجملة الأساسي للمخطط.

لكني أفترض أنك لا تعرف let* أو call-with-current-continuation, ، سأشرح هاتين الكلمة الرئيسية.

يشرح `let*`

إذا كنت تعرف ذلك بالفعل ، فيمكنك تخطيه Explain call-with-current-continuation

let*, الذي يبدو let, ، أعمال مثل let, ، ولكن سيقوم بتقييم متغيراتها المحددة ( (yin ...) و (yang ...)) واحد تلو الآخر وبشغف. هذا يعني أنه سيتم تقييمه أولاً yin, ، و بعد yang.

يمكنك قراءة المزيد هنا:باستخدام مخطط LET IN

يشرح `call-with-current-continuation`

إذا كنت تعرف ذلك بالفعل ، فيمكنك تخطيه Yin-Yang puzzle.

من الصعب بعض الشيء شرح call-with-current-continuation. لذلك سأستخدم استعارة لشرح ذلك.

صورة معالج كان يعرف تعويذة ، والتي كانت call-with-current-continuation. بمجرد أن يلقي التعويذة ، فإنه سيخلق عالمًا جديدًا ، ويرسله إلى نفسه. لكنه يستطيع لا تفعل شيئا في الكون الجديد ولكن في انتظار شخص ما يتصل باسمه. ذات مرة تم استدعاؤه, ، سيعود المعالج إلى الكون الأصلي ، وامتلاك الرجل المسكين - "شخص ما" - في متناول اليد ، ويذهب في حياته المعالج. إذا لم يتم استدعاؤه ، عندما انتهى الكون الجديد ، عاد المعالج أيضًا إلى الكون الأصلي.

حسنًا ، لنكن أكثر تقنية.

call-with-current-continuation هي وظيفة تقبل وظيفة كمعلمة. بمجرد الاتصال call-with-current-continuation مع وظيفة F, ، سوف يحزم بيئة الجري الحالية ، والتي تسمى current-continuation, كمعلمة C, ، وأرسلها للعمل F, وتنفيذ F. لذلك يصبح البرنامج بأكمله (F C). أو أن تكون أكثر جافا سكريبت: F(C);. C يتصرف مثل وظيفة. إذا C لا يسمى في F, ، ثم هو برنامج عادي ، متى F عائدات، call-with-current-continuation له قيمة Fقيمة الإرجاع. لكن اذا C يسمى مع معلمة V, ، سوف يغير البرنامج بأكمله مرة أخرى. يتغير البرنامج إلى أ حالة متى call-with-current-continuation تم استدعاؤه. لكن الآن call-with-current-continuation تعطي قيمة ، وهي V. ويستمر البرنامج.

لنأخذ مثالاً.

(define (f return)
  (return 2)
  3)
(display (f whatever)) ;; 3
(display (call-with-current-continuation f)) ;; 2
(display (call-with-current-continuation (lambda (x) 4))) ;; 4

الأول display انتاج 3, من السبب.

لكن الثانية display انتاج 2. لماذا ا؟

دعنا نغطس فيه.

عند التقييم (display (call-with-current-continuation f)), ، سيتم تقييمه أولاً (call-with-current-continuation f). نحن نعلم أنه سيغير البرنامج بأكمله

(f C)

النظر في تعريف f, لديها (return 2). يجب علينا تقييم (C 2). هذا عندما continuation يطلق عليها. لذلك يغير البرنامج بأكمله مرة أخرى

(display (call-with-current-continuation f))

لكن الآن، call-with-current-continuation له قيمة 2. لذلك يصبح البرنامج:

(display 2)

اللغز يين يانغ

دعونا نلقي نظرة على اللغز.

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
      (yin yang))

لنجعلها أكثر قابلية للقراءة.

(define (id c) c)
(define (f cc) (display #\@) cc)
(define (g cc) (display #\*) cc)
(let* ((yin
         (f (call-with-current-continuation id)))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

دعنا ندير البرنامج في دماغنا.

الجولة 0

let* اجعلنا نتقييم yin أول. yin هو

(f (call-with-current-continuation id))

لذلك نحن نقيم (call-with-current-continuation id) أول. يحزم البيئة الحالية التي نسميها C_0 للتمييز مع الاستمرار الآخر في الخط الزمني ، ويدخل في عالم جديد تمامًا: id. ولكن id فقط يعود C_0.

يجب أن نتذكر ماذا C_0 هو. C_0 هو برنامج مثل هذا:

(let* ((yin
         (f ###))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

### هو عنصر نائب ، والذي سيتم ملؤه في المستقبل بالقيمة C_0 استعادة.

ولكن id فقط يعود C_0. لا يتصل C_0. إذا استدعاء ، فسوف ندخل C_0عالم. لكن هذا لم يفعل ذلك ، لذلك نواصل التقييم yin.

(f C_0) ;; yields C_0

f هي وظيفة مثل id, ، ولكن له تأثير جانبي - الإخراج @.

لذا فإن إخراج البرنامج @ ودع yin أن تكون C_0. الآن يصبح البرنامج

(let* ((yin C_0)
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

بعد، بعدما yin تقييم ، نبدأ في التقييم yang. yang هو

(g (call-with-current-continuation id))

call-with-current-continuation هنا إنشاء استمرار آخر ، اسمه C_1. C_1 هو:

(let* ((yin C_0)
       (yang
         (g ###)))
      (yin yang))

### هو عنصر نائب. لاحظ أنه في هذا الاستمرار ، yinيتم تحديد قيمة S (هذا ما let* فعل). نحن على يقين من ذلك yinقيمة C_0 هنا.

حيث (id C_1) هو C_1, ، لذا yangقيمة

(g C_1)

g له تأثير جانبي - الإخراج *. لذلك البرنامج يفعل.

yangقيمة s الآن C_1.

الآن ، عرضنا @*

لذلك يصبح الآن:

(let* ((yin C_0)
       (yang C_1))
      (yin yang))

كلاهما yin و yang يتم حلها ، يجب علينا التقييم (yin yang). إنه

(C_0 C_1)

المقدسة ش*ر!

ولكن أخيرًا ، C_0 يسمى. لذلك نطير إلى C_0 الكون وننسى كل شيء عن هذه sh*ts. لن نعود أبدًا إلى هذا الكون مرة أخرى.

الجولة 1

C_0 خذ مع C_1 الى الخلف. يصبح البرنامج الآن (إذا نسيت ماذا C_0 تعود إلى ، عد لرؤيتها):

(let* ((yin
         (f C_1))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

آه ، نجد ذلك yinلا يتم تحديد قيمة S بعد. لذلك نحن نقيمها. في عملية التقييم yin, ، نخرج أ @ كما fتأثير جانبي. ونحن نعرف yin هو C_1 حاليا.

نبدأ في التقييم yang, ، جئنا عبر call-with-current-continuation تكرارا. نحن نمارس. نخلق استمرار C_2 و التي تعني:

(let* ((yin C_1)
       (yang
         (g ###)))
      (yin yang))

ونحن نعرض أ * كما g التنفيذ. ونحن نأتي إلى هنا

(let* ((yin C_1)
       (yang C_2))
      (yin yang))

لذلك حصلنا على:

(C_1 C_2)

أنت تعرف إلى أين نحن ذاهبون. نحن ذاهبون إلى C_1عالم. نتذكر ذلك من الذاكرة (أو نسخ ولصق من صفحة الويب). هو الآن:

(let* ((yin C_0)
       (yang
         (g C_2)))
      (yin yang))

نحن نعرف في C_1عالم ، yinتم تحديد قيمة. لذلك نبدأ في التقييم yang. كما نمارسنا ، سأخبرك مباشرة أنه يعرض * ويصبح:

(C_0 C_2)

الآن لقد طبعنا @*@**, ، ونحن ذاهبون إلى C_0الكون يأخذ مع C_2.

الجولة 2

كما نمارسنا ، سأخبرك أننا نعرض "@" ، yin هو C_2, ، ونخلق استمرارًا جديدًا C_3, ، و التي تعني:

(let* ((yin C_2)
       (yang
         (g ###)))
      (yin yang))

ونحن نعرض *, yang هو C_3, ، ويصبح

(C_2 C_3)

ويمكننا الاستمرار. لكنني سأتوقف هنا ، لقد أوضحت لك ما هي أول مخرجات Yin-Yang Puzzle.

لماذا عدد `*` يزيد؟

الآن رأسك مليء بالتفاصيل. سأجعل ملخصًا لك.

سأستخدم بناء الجملة مثل Haskell لتبسيط. و cc هو اختصار ل call-with-current-continuation.

متي #C_i# هو قوسين من قبل #, ، هذا يعني أن الاستمرار هو إنشاء هنا. ; يعني الإخراج

yin = f cc id
yang = g cc id
yin yang

---

yin = f #C_0# ; @
yang = g cc id
yin yang

---

yin = C_0
yang = g #C_1# ; *
yin yang

---

C_0 C_1

---

yin = f C_1 ; @
yang = g #C_2# ; *
yin yang

---

C_1 C_2

---

yin = C_0
yang = g C_2 ; *
yin yang

---

C_0 C_2

---

yin = f C_2 ; @
yang = g #C_3#; *
yin yang

---

C_2 C_3

---

yin = C_1
yang = g C_3 ; *
yin yang

---

C_1 C_3

---

yin = C_0
yang = g C_3 ; *
yin yang

---

C_0 C_3

إذا لاحظت بعناية ، فسيكون ذلك واضحًا لك ذلك

هناك الكثير من الأكوان (في الواقع لا حصر لها) ، ولكن C_0 هو الكون الوحيد الذي بدأه f. بدأ آخرون من قبل g.
C_0 C_n يقوم دائمًا باستمرار جديد C_max. انه بسبب C_0 هو الكون الأول الذي g cc id لديها ليس تم تنفيذها.
C_0 C_n عرض أيضا @. C_n C_m الذي لن يعرضه 0 *.
الوقت حسب الوقت يتم استنتاج البرنامج C_0 C_n, ، وسأثبت ذلك C_0 C_n يتم فصل المزيد والمزيد من التعبير الآخر ، مما يؤدي إلى @*@**@***...

القليل من الرياضيات

يفترض $C_n$ (n! = 0) هو أكبر ترقيم في جميع الاستمرارية ، ثم C_0 C_n يسمى.

الافتراض: متى C_0 C_n يسمى، C_n هو الحد الأقصى الحالي للاستمرار المرقم.

حاليا $C_{n+1}$ يتم إنشاؤه بواسطة C_0 C_n مثله:

yin = f C_n ; @
yang = g #C_{n+1}#
yin yang

لذلك نستنتج أن:

نظرية I. إذا C_0 C_n يسمى ، سوف ينتج استمرار $C_{n+1}$ , ، بحيث yin هو C_n.

ثم الخطوة التالية هي C_n C_{n+1}.

yin = C_{n-1}
yang = g C_{n+1} ; *
yin yang

السبب yin هو C_{n-1} هل هذا عندما C_n يجري خلقها طاعة نظرية أنا.

وثم C_{n-1} C_{n+1} يسمى ، ونحن نعرف متى C_{n-1} تم إنشاؤه ، كما أنه يطيع نظرية أنا. اذا لدينا C_{n-2} C_{n+1}.

C_{n+1} هو invariation. لذلك لدينا النظرية الثانية:

نظرية II. إذا C_n C_m أيّ n < m و n > 0 يسمى ، سوف يصبح C_{n-1} C_m.

وقد فحصنا يدويًا C_0 C_1 C_2 C_3. يطيعون الافتراض وجميع النظريات. ونحن نعرف كيف أولا @ و * تم إنشاؤه.

حتى نتمكن من كتابة أنماط أدناه.

C_0 C_1 ; @ *
C_[1-0] C_2 ; @ * *
C_[2-0] C_3 ; @ * * *
...

هذا ليس صارمًا ، لكنني أود أن أكتب:

Qed

كما قال إجابة أخرى ، نقوم أولاً بتبسيط (call-with-current-continuation (lambda (c) c)) مع get-cc.

(let* ((yin
         ((lambda (cc) (display #\@) cc) get-cc))
       (yang
         ((lambda (cc) (display #\*) cc) get-cc)) )
    (yin yang))

الآن ، اثنين من lambda هي مجرد وظيفة متطابقة مرتبطة مع الآثار الجانبية. دعنا نسمي هذه الوظائف f (إلى عن على display #\@) و g (إلى عن على display #\*).

(let* ((yin (f get-cc))
       (yang (g get-cc)))
    (yin yang))

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

يتطلب تعريفات f و g. في تعبير الخطوة ، نكتب

s0 f g =>

الخطوة الأولى هي حساب yin, ، ولكن يتطلب تقييم (f get-cc), وتتطلب لاحقا get-cc.

تحدث تقريبا، get-cc يمنحك قيمة تمثل "الاستمرار الحالي". دعنا نقول هذا s1 لأن هذه هي الخطوة التالية. لذلك نكتب

s0 f g => s1 f g ?
s1 f g cc =>

لاحظ أن المعلمات لا تنطلق ، مما يعني f و g في s0 و s1 ليست ضرورية كما هي فقط لاستخدامها في الخطوة الحالية. هذا يجعل معلومات السياق صريحة. الآن ، ما هي القيمة cc؟ نظرًا لأنه "استمرار الحالي" ، فهو نوع من الشيء نفسه s1 مع f و g ملزمة بنفس القيمة.

s0 f g => s1 f g (s1 f g)
s1 f g cc =>

مرة واحدة لدينا cc, ، يمكننا التقييم f get-cc. أيضا ، منذ ذلك الحين f لا يستخدم في الكود التالي ، ليس علينا نقل هذه القيمة.

s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin =>

التالي هو مشابه ل yang. ولكن الآن لدينا قيمة أخرى لنقلها: yin.

s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin => s3 g yin (s3 g yin)
s3 g yin cc => s4 yin (g cc)
s4 yin yang =>

أخيرًا ، الخطوة الأخيرة هي التقديم yang إلى yin.

s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin => s3 g yin (s3 g yin)
s3 g yin cc => s4 yin (g cc)
s4 yin yang => yin yang

هذا انتهى من بناء تعبير الخطوة. ترجمته مرة أخرى إلى المخطط بسيط:

(let* ([s4 (lambda (yin yang) (yin yang))]
       [s3 (lambda (yin cc) (s4 yin (g cc))]
       [s2 (lambda (yin) (s3 yin ((lambda (cc) (s3 yin cc))))]
       [s1 (lambda (cc) (s2 (f cc)))])
      (s1 s1))

أمر التقييم التفصيلي (هنا Lambda داخل جسم s2 تم التعبير عنه ببساطة كتقييم جزئي s3 yin عوضا عن (lambda (cc) (s3 yin cc))):

(s1 s1)
=> (s2 (f s1))
=> @|(s2 s1)
=> @|(s3 s1 (s3 s1))
=> @|(s4 s1 (g (s3 s1)))
=> @*|(s4 s1 (s3 s1))
=> @*|(s1 (s3 s1))
=> @*|(s2 (f (s3 s1)))
=> @*@|(s2 (s3 s1))
=> @*@|(s2 (s3 s1))
=> @*@|(s3 (s3 s1) (s3 (s3 s1)))
=> @*@|(s4 (s3 s1) (g (s3 (s3 s1))))
=> @*@*|(s4 (s3 s1) (s3 (s3 s1)))
=> @*@*|(s3 s1 (s3 (s3 s1)))
=> @*@*|(s4 s1 (g (s3 (s3 s1))))
=> @*@**|(s4 s1 (s3 (s3 s1)))
=> @*@**|(s1 (s3 (s3 s1)))
=> ...

(تذكر ، عند التقييم s2 أو s4, ، سيتم تقييم المعلمة أولاً

هذا لغز قديم من سيد التورط ديفيد مادور ، الذي أنشأ Unlambda. تمت مناقشة اللغز comp.lang.scheme عدة مرات.

حل جميل من تايلور كامبل:https://groups.google.com/d/msg/comp.lang.scheme/puedvrkyy5w/uijtc_t1loej

المنشور الأصلي من ديفيد مادور (1999):https://groups.google.com/d/msg/comp.lang.scheme/fysq_wplxsw/awxez_uxw20j

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow