كم عدد الطرق التي يمكنني من خلالها كتابة فقرة إلى المخطط؟

تدعي لغات الشر أن لغات البرمجة الوظيفية هي "لغات كتابة واقعية". غالبًا ما يتم تعريف هذا على أنه لغة Haskell ، لكننا سنبدأ مع اللغة الوظيفية التي أثرت بشكل كبير على Haskell ومجموعة فرعية من أدوات البرمجة الوظيفية للعديد من اللغات الأخرى - Scheme. على الأقل map for-each ، تم filter reduce ، بالإضافة إلى apply و eval إلى لغات البرمجة المفضلة لدينا ، إن لم يكن من Scheme ، ثم من هناك.

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

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

للتجارب ، استخدمنا لهجة اللهجة القديمة الجيدة R5RS والمبدأ الشائع للفنون الجميلة "الحد الأدنى من الوسائل - الحد الأقصى للظهور".

تم إعداد جميع أمثلة المخطط في DrRacket 6.2 في وضع R5RS . تم إجراء قياسات وقت التشغيل في Guile 2.0 في بيئة OpenSUSE Leap 15 OS.

للبدء ، يمكنك أن تأخذ تعريفًا تكراريًا للعنصر وأن تقوم ببساطة بإعادة كتابة الصيغة في المخطط:

 (define (factorial-classic n) (if (zero? n) 1 (* n (factorial-classic (- n 1))))) 

كانت النتيجة هي تعريف وظيفة (من حيث المخطط - إجراء ، على الرغم من أنها في الواقع دالة) لحساب المصطلح ، والذي يمكن رؤيته في أدلة البرمجة التي لا تعد ولا تحصى ، بدءًا من الكتاب الخالد لـ H. Abelson و D. Sassman "بنية وتفسير برامج الكمبيوتر" .

يمكنك قراءة وفهم هذا الرمز مثل هذا: factorial $$$ن$ هل هناك $$$1$ لو $$$ن = 0 دولا$ خلاف ذلك - $$$n \ cdot (n-1)!$ . وهكذا ، يتوافق هذا الكود مع التعريف التكراري للعنصر ، المعتمد في الرياضيات. الشيء الوحيد الذي نحن لا نتحقق من الانتماء $$$ن$ أرقام غير سلبية.

كونه متكرر ، يحتوي الكود أعلاه على قيود واضحة على القيمة $$$ن$ : سوف تتراكم بيانات المكالمات العودية على المكدس حتى $$$ن$ لن يصل إلى 0. هذا يمكن أن يسبب تجاوز سعة مكدس في كبيرة $$$ن$ .

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

إذا استخدمت توصيات مؤلفي الكتاب أعلاه ، فيمكنك الحصول على ما يلي:

 (define (factorial-classic-tco n) (define (iteration product counter) (if (> counter n) product (iteration (* product counter) (+ counter 1)))) (iteration 1 1)) 

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

لقد كان كلاسيكيا. لكن المخطط هو المرونة في حد ذاته ، فهل من الممكن كتابة الشيء نفسه بطريقة مختلفة اختلافًا جذريًا؟ ويفضل أن يكون أقصر؟ على سبيل المثال ، وفقا لهذا الإدخال $$$ن! = 1 \ cdot 2 \ cdot 3 \ cdot ~ \ cdots ~ \ cdot n$ شكل تسلسل من $$$1$ قبل $$$ن$ (أو من $$$ن$ قبل $$$1$ ) ومن ثم طيها عن طريق الضرب؟ لحسن الحظ ، في هذا المخطط ، يكون هذا الأمر بسيطًا جدًا بفضل إجراء apply المضمن ، والذي يطبق إجراء مع عدد اعتباطي من الوسائط على القائمة:

 (define (iota n) (define (iteration sequence i) (if (> in) sequence (iteration (cons i sequence) (+ i 1)))) (iteration '() 1)) (define (factorial-fold n) (apply * (iota n))) 

يشتهر Scheme بملاءمته لإجراء العمليات الحسابية الرمزية بسبب "وحدة الشفرة والبيانات" (كما يقولون أحيانًا عن لغات عائلة Lisp). نحن نستخدم هذه الميزة: نقوم بتكوين تعبير لحساب عامل الرقم $$$ن$ ثم احسبها:

 (define (factorial-eval n) (define expression `(* ,@(iota n))) (eval expression (interaction-environment))) 

يعني الرمز "رجوع علامة اقتباس مفردة" quasiquotation. بدون شبه الاقتباس ، يمكن الحصول على تعبير لمزيد من الحساب باستخدام الكود (cons '* (iota n)) . يعني الاقتباس المفرد (الاقتباس ، الاقتباس) أنه يجب استبدال * في التعبير تمامًا كاسم (رمز) ، وليس القيمة المقابلة (هنا - الإجراء). لذلك ، مع $$$ن = 3 دولارا$ نحصل (* 3 2 1) . هذه القائمة هي تعبير في المخطط. يمكن تنفيذ قيمته في بيئة مناسبة ، والأهم من ذلك كله - في بيئة (interaction-environment) بيئة (interaction-environment) تحتوي على الإجراءات المضمنة والإجراءات المحددة من قبلنا في البرنامج. في الواقع ، هذا هو ما نقوم به في جسد factorial-eval .

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

 ghci> take 4 [1 ..] [1,2,3,4] 

ينشئ التعبير [1 ..] قائمة لانهائية من الأعداد الصحيحة. يحصل تعبير take 4 على أول 4 عناصر من هذه القائمة. نظرًا لأن عناصر القائمة اللاحقة تظل غير مطلوبة ، فلن يتم احتسابها.

في هاسكل الحصول على $$$n!$ من قائمة لا حصر لها يمكنك كتابة مثل هذا:

 factorials :: [Integer] factorials = next 0 1 where next n fact = let n' = n + 1 in fact : next n' (fact * n') factorial :: Integer -> Integer factorial n = factorials !! fromIntegral n 

 ghci> take 7 $ factorials [1,1,2,6,24,120,720] ghci> factorial 6 720 

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

في لغات عائلة Lisp ، يتم إنشاء قوائم من أزواج. من أجل إنشاء قوائم لا حصر لها ، نقدم نوع "الزوج البطيء" - الزوج الذي يكون فيه العنصر الأول هو القيمة المحسوبة ، والثاني هو الوعد لحساب القيمة. للقيام بذلك ، نحتاج إلى استكمال "الثالوث المقدس" في لغات عائلة ليسب ( cons ، car ، cdr ) بإصداراتها البطيئة:

 (define-syntax lazy-cons (syntax-rules () ((_ first second) (cons first (delay second))))) (define lazy-car car) (define (lazy-cdr lazy-pair) (force (cdr lazy-pair))) 

يتم تطبيق مُنشئ الزوج الكسول lazy-cons شكل ماكرو. يتم ذلك لتجنب حساب قيمة العنصر الثاني من الزوج عند إنشائه.

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

 (define (lazy-list-ref lazy-list index) (if (zero? index) (lazy-car lazy-list) (lazy-list-ref (lazy-cdr lazy-list) (- index 1)))) (define (generate-factorials) (define (next nn!) (define n+1 (+ n 1)) (lazy-cons n! (next n+1 (* n! n+1)))) (next 0 1)) 

هنا n! و n+1 هي أسماء المتغيرات. في المخطط ، مقارنة باللغات الأخرى ، هناك عدد قليل جدًا من الأحرف التي لا يمكن استخدامها في المعرفات.

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

الآن يمكنك تحديد $$$n!$ كيف تحصل عليه $$$ن$ العنصر العاشر من قائمة الفصائل:

 (define lazy-factorials (generate-factorials)) (define (factorial-lazy n) (lazy-list-ref lazy-factorials n)) 

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

بالمناسبة ، الكود الموجود في Scheme قريب جدًا من ذلك في Haskell. لذلك ، تلقي بيان !! يتوافق تقريبًا مع إجراء lazy-list-ref مُنشئ lazy-list-ref : يتوافق مع lazy-cons . في المقابل ، لأن هاسكل ، على الرغم من أنه يعلن عن نموذج حساب كسول ، فإنه ، على عكس delay / force في المخطط ، فإنه لا يتذكر القيم المحسوبة.

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

 (define factorial-memoized (let ((memo '())) (lambda (n) (let ((memoized (assq n memo))) (if memoized (cadr memoized) (if (zero? n) 1 (let ((computed (* n (factorial-memoized (- n 1))))) (set! memo (cons (list n computed) memo)) computed))))))) 

 (define proc (let ((static-var initial-value)) (lambda args ...))) 

 (define count (let ((n 0)) (lambda () (set! n (+ n 1)) n))) 

 (define count ((lambda (n) (lambda () (set! n (+ n 1)) n)) 0)) 

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

بطبيعة الحال ، تحسين ذيل العودية هو ممكن هنا أيضا:

 (define factorial-memoized-tco (let ((memo '())) (lambda (n) (define (iteration product counter) (cond ((> counter n) product) (else (set! memo (cons (list counter product) memo)) (iteration (* product counter) (+ counter 1))))) (iteration 1 1)))) 

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

 (define (factorial-do n) (define product 1) (do ((i 1 (+ i 1))) ((> in) product) (set! product (* product i)))) 

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

 (define-syntax for (syntax-rules () ((_ (variable init test step) . body) (let loop ((variable init)) (if test (begin (begin . body) (loop step))))))) 

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

تحديد مضروب باستخدام for :

 (define (factorial-for n) (define product 1) (for (i 1 (<= in) (+ i 1)) (set! product (* product i))) product) 

 for → _ i → variable 1 → init (<= in) → test (+ i 1) → step (set! product (* product i)) → body 

 (define (factorial-for n) (define product 1) (let loop ((i 1)) ;   (if (<= in) ;  (begin (begin (set! product (* product i))) ;  (loop (+ i 1))))) ;  for product) 

هناك خيار آخر يشبه ضرورة الحلقة - مع الإجراء المضمن for-each إجراء:

 (define (factorial-for-each n) (define product 1) (for-each (lambda (i) (set! product (* product i))) (iota n)) product) 

لغة مخطط عظيم وقوي! ماذا عن الأداء؟

سوف نستخدم GNU Guile لقياس الأداء - في هذه البيئة ، يمكنك قياس الوقت الذي يستغرقه لتقييم التعبير بكل بساطة.

يعمل Guile كالتالي: يقوم بتجميع التعليمات البرمجية المصدر للبرنامج إلى bytecode ، والتي يتم تنفيذها بعد ذلك بواسطة الجهاز الظاهري. هذه مجرد واحدة من التطبيقات وواحدة من عدة طرق ممكنة لتشغيل برنامج Scheme ، وهناك طرق أخرى: Racket (تستخدم مجموعة JIT) ، و Chicken Scheme (يستخدم تفسيرًا أو ترجمة "صادقة" إلى مجموعة فرعية من C) ، إلخ. من الواضح أن كلا من القيود وأداء البرامج في هذه البيئات قد يختلفان قليلاً.

سنتخذ قياسات بقيمة معينة $$$ن$ . ما ينبغي أن يكون $$$ن$ ؟ لذلك الذي أعظم $$$ن$ سوف تكون قادرة على "التعامل" مع الخيارات المقترحة. مع إعدادات Guile 2.0 الافتراضية ، على جهاز كمبيوتر به Intel Core i5 و 4 جيجابايت من ذاكرة الوصول العشوائي ، حصلت على ما يلي:

من هنا ، تم إجراء اختبارات الأداء في $$$ن = 8 \ ، 000 دولا$ . يتم عرض النتائج في الجدول أدناه ، حيث $$$t_ {run}$ - المهلة الزمنية $$$t_ {GC}$ - جامع القمامة وقت التشغيل في ثوان.
بالنسبة لجميع الإجراءات باستثناء الكسل والمذكرة ، يتم الحصول على أصغر قيم لوقت التشغيل والوقت المقابل لهواة جمع القمامة ، ويتم الحصول عليها من نتائج ثلاث عمليات بدء في $$$ن = 8 \ ، 000 دولا$ .
بالنسبة إلى الإجراءات الموضحة والكسلية ، تتم الإشارة إلى وقت تنفيذ المكالمة الأولى ، ثم أصغر المكالمات الثلاثة.

لدينا 4 خيارات يمكن أن تعمل بشكل كبير $$$ن$ . في $$$ن = 100 \ ، 000 دولا$ لديهم أوقات الحساب وجمع القمامة التالية:

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

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