سؤال تقييم اللغة: حريصة مقابل كسول

Question

كنت أقرأ مركز شريرام، وقد حصلت على عالقة في هذه الأسئلة:

1. هل يمكنك إثبات أن الأنظمة الحريصة والكسل ستنتج دائما نفس الإجابة؟ (يطلب شريرام أن ننظر إلى اللغة التي طورها ولكن هل هناك طريقة أخرى لإثبات ذلك وكيف؟)

2. سوف يقلل التقييم الحريص دائما مع عدد أقل من الخطوات؟

هنا هو رمز الاستبدال والتقييم الحريص في عباءة.

;; Gets W-lang and returns the computed number
;; (evaluate (let x (num 10) (let y x x)) -> 10
;; (evaluate (let x (num 10) (let y (add x (num 10)) y)) ->20
;; (evaluate (let x 10 (let x x x ))) -> 10
;; (evaluate (let x 10 (let x (+ 10 x) 
;;                            (let y (let y (+ 10 x) y)
;;                                   (+ x y))))-> 50

(defn evaluate[W-lang]
  (condp = (first W-lang)
    'num (second W-lang)
    'add (+ (evaluate (second W-lang))
            (evaluate (third W-lang)))
    'sub (- (evaluate (second W-lang))
            (evaluate (third W-lang)))
    'let (evaluate (subst (second W-lang)(third W-lang) 
                          (forth W-lang)))))


;; subst: symbol value W-Lang -> W-lang
;; substitutes the symbol and returns a W-Lang
(defn subst[id value W-lang]
    (cond
      (symbol? W-lang) (if (= id W-lang) value W-lang)
      (seq? W-lang)
      (condp = (first W-lang)
      'num (list 'num (first (rest W-lang)))
      'add (list 'add (subst id value (second W-lang))
                      (subst id value (third W-lang)))
      'sub (list 'sub (subst id value (second W-lang))
                      (subst id value (third W-lang)))
      'let 
      (if (= (second W-lang) id)
        (list 'let (second W-lang) 
                    (subst id value (third W-lang))
                    (forth W-lang))
        (list 'let(second W-lang)
                   (subst id value (third W-lang))
                  (subst id value (forth W-lang))))
      W-lang)))

Answer 1

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

2. أما بالنسبة للتسريح مقابل كسول، أيهما قادر على المزيد من الحساب غير الضروري؟ أي واحد يضع الحد العلوي على حساب إضافي؟

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

إذا كنت تريد البراهين، فلا أعتقد أن كتاب شريرام هو المكان المناسب لتعلم تقنية دليل لغات البرمجة. كتاب Glynn Winskel حول الدلالات الرسمية لغات البرمجة هو جيد جدا، لكنه متقدم إلى حد ما. ما لم تكن متطورة رياضيا، سيكون من الصعب بدون معلم.

ربما تكون أفضل حالا في تخطي أجزاء دليل من أشياء شريرام، أو تحاول كتاب مدرسي أكثر سهولة في المستخدمين مثل بنيامين بيرس أنواع لغات البرمجة.

---

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

Answer 2

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