استخدام Haskell State Monad رائحة رمز؟

Question

الله أكره مصطلح "رائحة الكود" ، لكن لا يمكنني التفكير في أي شيء أكثر دقة.

أنا أقوم بتصميم لغة ومترجم رفيع المستوى مساحة بيضاء في وقت فراغي للتعرف على بناء البرمجيات ، وتصميم اللغة ، والبرمجة الوظيفية (يتم كتابة برنامج التحويل البرمجي في Haskell).

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

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

أريد أن أتعلم كيف أفكر في هاسكل (بدلاً من ذلك ، في النموذج الوظيفي) - وليس في C مع بناء جملة Haskell. هل يجب أن أحاول حقًا القضاء على/تقليل استخدام موناد الحالة ، أم أنه "نمط تصميم" وظيفي شرعي؟

Answer 1

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

هذا يعني أن استخدام أحاديات مثل الحالة أو ST أو تلك المصممة خصيصًا ، أو مجرد وجود بنية بيانات تحتوي على بيانات الحالة التي تنقلها إلى أماكن قليلة ، ليس بالأمر السيئ. (في الواقع ، فإن Monads مجرد مساعدة في القيام بذلك بالضبط!) ومع ذلك ، فإن وجود حالة تسير في كل مكان (نعم ، هذا يعني أنك ، IO Monad!) رائحة سيئة.

مثال واضح إلى حد ما على ذلك كان عندما كان فريقي يعمل على دخولنا إلى مسابقة برمجة ICFP 2009 (الرمز متاح على git: //git.cynic.net/haskell/icfp-contest-2009). انتهى بنا المطاف بعدة أجزاء معيارية مختلفة لهذا:

• VM: الجهاز الظاهري الذي يدير برنامج المحاكاة
• وحدات التحكم: عدة مجموعات مختلفة من الإجراءات التي تقرأ إخراج المحاكاة وإنشاء مدخلات تحكم جديدة
• الحل: توليد ملف الحل بناءً على إخراج وحدات التحكم
• المرئيات: عدة مجموعات مختلفة من الإجراءات التي تقرأ كل من منافذ الإدخال والمخرجات وإنشاء نوع من التصور أو سجل ما يجري مع تقدم المحاكاة

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

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

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

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

إجابة واحدة تقول ، "لا تستخدم monads." من وجهة نظري ، هذا هو بالضبط للخلف. Monads هي بنية تحكم ، من بين أشياء أخرى ، يمكن أن تساعدك على تقليل كمية التعليمات البرمجية التي تمس الحالة. إذا نظرت إلى محللين أحاديين كمثال ، فإن حالة التحليل (أي ، النص الذي يتم تحليله ، إلى أي مدى وصل المرء إلى ذلك ، يجب أن يركض أي تحذيرات تراكمت ، إلخ) عبر كل مجموعة مستخدمة في المحلل. . ومع ذلك ، لن يكون هناك سوى عدد قليل من المجموعات التي تتلاعب بالفعل بالدولة مباشرة ؛ أي شيء آخر يستخدم واحدة من هذه الوظائف القليلة. يتيح لك ذلك رؤية بوضوح وفي مكان واحد من كمية صغيرة من التعليمات البرمجية التي يمكن أن تغير الحالة ، والسبب بسهولة أكبر حول كيفية تغييرها ، مما يجعل من السهل التعامل معه.

Answer 2

لقد كتبت العديد من المترجمين في Haskell ، وموناد الدولة هو حل معقول للعديد من مشاكل التحويل البرمجي. لكنك تريد أن تبقيها مجردة --- لا تجعل من الواضح أنك تستخدم موناد.

إليك مثال من برنامج التحويل البرمجي Glasgow Haskell (الذي فعلته ليس اكتب؛ أنا فقط أعمل حول بعض الحواف) ، حيث نقوم ببناء الرسوم البيانية لتدفق التحكم. فيما يلي الطرق الأساسية لصنع الرسوم البيانية:

empyGraph    :: Graph
mkLabel      :: Label -> Graph
mkAssignment :: Assignment -> Graph  -- modify a register or memory
mkTransfer   :: ControlTransfer -> Graph   -- any control transfer
(<*>)        :: Graph -> Graph -> Graph

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

withFreshLabel :: (Label -> Graph) -> Graph
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition
             -> Graph   -- code in the 'then' branch
             -> Graph   -- code in the 'else' branch 
             -> Graph   -- resulting if-then-else construct

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

موناد الدولة مخبأة تحتها ؛ على الرغم من أنه لا يتعرض للعميل ، فإن تعريف Graph هو شيء مثل هذا:

type Graph = RealGraph -> [Label] -> (RealGraph, [Label])

أو أكثر دقة قليلا

type Graph = RealGraph -> State [Label] RealGraph
  -- a Graph is a monadic function from a successor RealGraph to a new RealGraph

مع مخبأ موناد الدولة خلف طبقة من التجريد ، فإنه ليس رائحته على الإطلاق!

Answer 3

هل نظرت إلى نعمة القواعد (اي جي)؟ (مزيد من المعلومات حول ويكيبيديا و مقالة - سلعة في قارئ موناد)؟

مع AG يمكنك إضافة صفات إلى شجرة بناء الجملة. يتم فصل هذه السمات في توليفها و وارث صفات.

سمات توليفها هي الأشياء التي تنشئها (أو توليفها) من شجرة بناء الجملة الخاصة بك ، قد يكون هذا هو الرمز الذي تم إنشاؤه ، أو جميع التعليقات ، أو أي شيء آخر تهتم به.

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

في جامعة أوتريخت نستخدم سمة نظام القواعد (uuagc) لكتابة المترجمين. هذا هو معالج مسبق يولد رمز Haskell (.hs الملفات) من المقدمة .ag الملفات.

---

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

في هذه الحالة ، يمكنك كتابة نوع التعليمات البرمجية يدويًا التي تعزو لك القواعد التي تولدها لك ، على سبيل المثال:

data AbstractSyntax = Literal Int | Block AbstractSyntax
                    | Comment String AbstractSyntax

compile :: AbstractSyntax -> [Label] -> (Code, Comments)
compile (Literal x) _      = (generateCode x, [])
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls
                             in (labelCode l code', comments)
compile (Comment s ast) ls = let (code, comments') = compile ast ls
                             in (code, s : comments')

generateCode :: Int -> Code
labelCode :: Label -> Code -> Code

Answer 4

من المحتمل أنك قد ترغب في الحصول على functor تطبيق بدلاً من موناد:

http://www.haskell.org/haskellwiki/applicative_functor

أعتقد أن الورقة الأصلية تشرحها أفضل من الويكي ، ولكن:

http://www.soi.city.ac.uk/~ross/papers/applicative.html

Answer 5

لا أعتقد أن استخدام موناد الدولة هو رائحة رمز عندما تستخدم لنمذجة الحالة.

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

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

Answer 6

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

Answer 7

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

تسمى الورقة "لماذا تهم البرمجة الوظيفية"أقترح عليك أن تقرأها. إنها قراءة جيدة.

Answer 8

لنكن حذرين بشأن المصطلحات هنا. الدولة ليست في حد ذاتها سيئة. اللغات الوظيفية لها حالة. ما هي "رائحة الكود" هي عندما تجد نفسك تريد تعيين قيم المتغيرات وتغييرها.

بالطبع ، هناك Monad State Monad موجود لهذا السبب-كما هو الحال مع I/O ، إنه يتيح لك القيام بأشياء غير آمنة وغير وظيفية في سياق مقيد.

لذا ، نعم ، ربما تكون رائحة رمز.