الحساب مع أرقام الكنيسة

Question

أنا أعمل من خلال SICP ، و مشكلة 2.6 لقد وضعني في شيء من مأزق. في التعامل مع أرقام الكنيسة ، يبدو أن مفهوم تشفير الصفر و 1 ليكون وظائف تعسفية ترضي بعض البديهيات منطقيًا. بالإضافة إلى ذلك ، استخلاص الصيغة المباشرة للأرقام الفردية باستخدام تعريف الصفر ، ودالة add-1 أمر منطقي. لا أفهم كيف يمكن تشكيل عامل زائد.

حتى الآن لدي هذا.

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

النظر من خلال دخول ويكيبيديا ل حساب التفاضل والتكامل لامدا, ، وجدت أن تعريف Plus كان زائد: = λmnfx.mf (NFX). باستخدام هذا التعريف تمكنت من صياغة الإجراء التالي.

(define (plus n m)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

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

Answer 1

انها في الواقع بسيطة جدا. من المحتمل أن يُنظر إلى هذا على أنه Flamebait ، لكن Parens يجعل من الصعب رؤيتها-وهي طريقة أفضل لمعرفة ما يحدث هو إما أن تتخيل أنك في لغة مغطاة ، أو مجرد استخدام حقيقة أن المخطط له وظائف متعددة الحوائق و احتضن ذلك ... إليك تفسير يستخدم lambdas وحجة متعددة حيث يكون مناسبًا:

• يتم ترميز كل رقم n على أنه

  (lambda (f x) ...apply (f (f (f ... (f x)))) N times...)
  

• هذا يعني أن ترميز n هو في الواقع

  (lambda (f x) (f^N x))
  

  أين f^N هو الأسس الوظيفية.

• طريقة أبسط لقول هذا (على افتراض الكاري): يتم تشفير الرقم n على أنه

  (lambda (f) f^N)
  

  لذلك ن هو في الواقع أ "ارفع إلى قوة N" وظيفة

• الآن خذ تعبيرك (النظر داخل lambdaS هنا):

  ((m f) ((n f) x))
  

  حيث n هو ترميز رقم ، إنه هذا الأسعار ، لذلك هذا هو في الواقع:

  ((m f) (f^n x))
  

  ونفس الشيء ل m:

  (f^m (f^n x))
  

  والباقي يجب أن يكون واضحا ... لديك m تطبيقات f تقدم على n تطبيقات f تقدم على x.

• أخيرًا ، للمغادرة بعض متعة - إليك طريقة أخرى لتحديد plus:

  (define plus (lambda (m) (lambda (n) ((m add1) n))))
  

  (حسنًا ، ليس الكثير من المرح ، لأن هذا ربما يكون أكثر وضوحًا.)

Answer 2

^{(تأكد من فهمك وظائف الترتيب الأعلى).} في كنيسة ألونزو'س حساب Lambda Untyped الوظيفة هي نوع البيانات البدائية الوحيد. لا توجد أرقام أو منطقية أو قوائم أو أي شيء آخر ، وظائف فقط. يمكن أن يكون للوظائف وسيطة واحدة فقط ، ولكن يمكن أن تقبل الوظائف و/أو إرجاع الوظائف - ليس قيم هذه الوظائف ، ولكن الوظائف نفسها. لذلك لتمثيل الأرقام والملاءات والطرازات وأنواع أخرى من البيانات ، يجب أن تتوصل إلى طريقة ذكية لوظائف مجهولة للدفاع عنها. أرقام الكنيسة هي طريقة التمثيل الأعداد الطبيعية. ثلاثة بنيات بدائية في حساب التفاضل والتكامل اللامبدا غير المعقول هي:

1. λx.x, ، و تطابق وظيفي, ، يقبل بعض الوظائف ويعيدها على الفور.
2. λx.x x, ، التطبيق الذاتي.
3. λf.λx.f x, ، تطبيق الوظيفة ، يأخذ وظيفة ووسيطة ، ويطبق وظيفة على وسيطة.

كيف يمكنك تشفير 0 ، 1 ، 2 لا شيء آخر سوى الوظائف؟ نحتاج بطريقة ما إلى بناء فكرة كمية في النظام. لدينا وظائف فقط ، يمكن تطبيق كل وظيفة فقط على وسيطة واحدة. أين يمكن أن نرى أي شيء يشبه الكمية؟ مهلا ، يمكننا تطبيق وظيفة على معلمة عدة مرات! من الواضح أن هناك شعورًا بالكمية في 3 دعوات متكررة للوظيفة: f (f (f x)). لذلك دعونا نشفره في حساب حساب Lambda:

• 0 = λf.λx.x
• 1 = λf.λx.f x
• 2 = λf.λx.f (f x)
• 3 = λf.λx.f (f (f x))

وهلم جرا. ولكن كيف تذهب من 0 إلى 1 ، أو من 1 إلى 2؟ كيف يمكنك كتابة وظيفة ، بالنظر إلى رقم ، سيعيد رقمًا يزداد بمقدار 1؟ نرى النمط في أرقام الكنيسة التي يبدأ المصطلح بها دائمًا λf.λx. وبعد أن يكون لديك تطبيق متكرر محدود لـ F, ، لذلك نحن بحاجة إلى الدخول بطريقة ما في جسم λf.λx. ولفها في أخرى f. كيف يمكنك تغيير جسم التجريد دون تقليل؟ حسنًا ، يمكنك تطبيق وظيفة ، ولف الجسم في وظيفة ، ثم لف الجسم الجديد في تجريد Lambda القديم. لكنك لا تريد أن تتغير وسيطات ، وبالتالي تقوم بتطبيق التجريدات على قيم الاسم نفسه: ((λf.λx.f x) f) x → f x, ، لكن ((λf.λx.f x) a) b) → a b, ، وهو ليس ما نحتاجه.

لهذا add1 هو λn.λf.λx.f ((n f) x): تطبيق n إلى f وثم x لتقليل التعبير إلى الجسم ، ثم تقدم f لهذا الجسم ، ثم تجريده مرة أخرى مع λf.λx.. ممارسه الرياضه: نرى أيضًا أنه صحيح ، تعلم بسرعة β تخفيض وتقليل (λn.λf.λx.f ((n f) x)) (λf.λx.f (f x)) إلى الزيادة 2 في 1.

الآن فهم الحدس وراء لف الجسم في استدعاء وظيفة أخرى ، كيف يمكننا تنفيذ إضافة رقمين؟ نحن بحاجة إلى وظيفة ، معطى λf.λx.f (f x) (2 و λf.λx.f (f (f x)) (3) ، سيعود λf.λx.f (f (f (f (f x)))) (5). انظر إلى 2. ماذا لو استطعت يحل محل انها x مع جسم 3 ، هذا هو f (f (f x))؟ للحصول على جسم من 3 ، من الواضح ، فقط قم بتطبيقه على f وثم x. تطبيق الآن 2 على f, ، ولكن بعد ذلك ، قم بتطبيقه على الجسم 3 ، وليس ل x. ثم لفها في λf.λx. تكرارا: λa.λb.λf.λx.a f (b f x).

استنتاج: لإضافة رقمين a و b معا ، وكلاهما ممثل كأرقام الكنيسة ، تريد ذلك يحل محل x في a مع جسم b, ، لهذا السبب f (f x) + f (f (f x)) = f (f (f (f (f x)))). لتحقيق ذلك ، تقدم a إلى f, ، ثم إلى b f x.

Answer 3

إجابة إيلي صحيحة من الناحية الفنية ، لكن منذ أن تم طرح هذا السؤال على #apply لم يتم تقديم الإجراء ، لا أعتقد أن المؤلفين يعتزمون أن يكون لدى الطالب معرفة ذلك أو مفاهيم مثل الكاري لتكون قادرة على الإجابة على هذا السؤال.

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

; The effect of procedure #add-1 on `one`, and `two` was the composition of `f` 
; onto `one` and `f` onto `two`.
;
; one   : (λ (f) (λ (x) (f x)))
; two   : (λ (f) (λ (x) (f (f x))))
; three : (λ (f) (λ (x) (f (f (f x)))))
;
; Thus one may surmise from this that an additive procedure in this system would
; work by composing one number onto the other.
;
; From exercise 1.42 you should already have a procedure called #compose.
;
; With a little trial and error (or just plain be able to see it) you get the
; following solution.

(define (adder n m)
  (λ (f)
    (let ((nf (n f))
          (mf (m f)))
      (compose nf mf))))