هل الترميز العددي للكنيسة للأعداد الطبيعية معقد بلا داع؟

Question

ال هيكل وتفسير برامج الكمبيوتر يعرض الكتاب الذي كنت أقرأه أرقام الكنيسة من خلال تحديد الصفر ووظيفة الزيادة

zero: λf. λx. x
increment: λf. λx. f ((n f) x)

بدا هذا الأمر معقدًا جدًا بالنسبة لي واستغرق الأمر وقتًا طويلاً حقًا لاكتشافه واستخلاصه (λf.λx. f x) و اثنان (λf.λx. f (f x)).

ألن يكون من الأسهل تشفير الأرقام بهذه الطريقة بدلاً من ذلك، حيث يكون الصفر هو لامدا الفارغة؟

zero: λ
increment: λf. λ. f

الآن أصبح من التافه استخلاص واحد (λ. λ) و اثنان (λ. λ. λ)، وما إلى ذلك وهلم جرا.

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

Answer 1

الترميز الخاص بك (صفر: λx.x, ، واحد: λx.λx.x, ، اثنين: λx.λx.λx.x, ، وما إلى ذلك) يجعل من السهل تحديد الزيادة والنقصان ولكن أبعد من ذلك، يصبح من الصعب جدًا تطوير أدوات الدمج للتشفير الخاص بك.على سبيل المثال، كيف يمكنك تحديد isZero?

الطريقة البديهية للتفكير في ترميز الكنيسة هي أن الرقم n ويمثلها عمل التكرار n مرات.وهذا يجعل من السهل تطوير أدوات التجميع مثل plus بمجرد استخدام التكرار المشفر في الرقم.لا حاجة لcombinators يتوهم للتكرار.

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

طريقة أخرى لترميز الأرقام ، هي التفكير في الأرقام مثل n = 0 | S n ، واستخدم ترميز الفانيليا للنقابات.

Answer 2

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