ننتهي اليوم من سلسلة مقالاتنا حول البرمجة الوظيفية. اتضح 11 أجزاء. أعتقد أن هذا إنجاز. في هذه المقالة ، نقوم بتطبيق آلة حاسبة بسيطة مكدس (المعروف أيضًا باسم "تدوين البولندية العكسي"). يتم تنفيذ التطبيق بالكامل تقريبًا على الوظائف ، بنوع خاص واحد فقط ، وعمومًا دون مقارنة بالعينة ، لذلك يعد هذا اختبارًا ممتازًا للمفاهيم التي تمت تغطيتها في سلسلتنا.
أريد أن أشكر @ kleidemos بشكل منفصل. كان هو الذي كان بمثابة المترجم الرئيسي ومدير سلسلة كاملة من المقالات. شكرا لك
إذا لم تكن معتادًا على مثل هذه الآلة الحاسبة ، فستعمل على النحو التالي: يتم دفع الأرقام على المكدس ، والعمليات ، مثل الجمع والضرب ، واختيار الأرقام من أعلى الحزمة ، ثم إعادة نتيجة العملية.
مخطط حساب بسيط على المكدس:
قبل تصميم مثل هذا النظام ، يجب أن تفكر في كيفية استخدامه. باتباع بناء جملة يشبه الشكل الرابع ، سنعطي كل إجراء تسمية مناسبة بحيث يمكنك في المثال أعلاه كتابة شيء مثل:
EMPTY ONE THREE ADD TWO MUL SHOW
ربما يكون من المستحيل الحصول على بناء الجملة هذا بالضبط ، ولكن دعونا نحاول الاقتراب من ذلك قدر الإمكان.
كومة نوع البيانات
أولاً ، تحتاج إلى تعريف بنية البيانات للمكدس. للبساطة ، يمكنك استخدام قائمة أرقام الفاصلة العائمة.
type Stack = float list
لكن من الأفضل لفه بنوع حالة واحدة لجعل النوع أكثر مرئية ، مثل هذا:
type Stack = StackContents of float list
لماذا من الأفضل أن تفعل ذلك بالضبط ، يمكنك أن تقرأ هنا .
قم الآن بإنشاء مكدس جديد باستخدام StackContents :
let newStack = StackContents [1.0;2.0;3.0]
لاستخراج محتوى من رصة موجودة ، استخدم النمط المطابق لـ StackContents :
let (StackContents contents) = newStack // "contents" // float list = [1.0; 2.0; 3.0]
دفع وظيفة
بعد ذلك ، نحتاج إلى طريقة لوضع الأرقام على هذه المجموعة. للقيام بذلك ، ما عليك سوى إضافة قيمة جديدة إلى أعلى القائمة باستخدام " :: ".
مثال وظيفة:
let push x aStack = let (StackContents contents) = aStack let newContents = x::contents StackContents newContents
تحتوي هذه الميزة على عدد من الميزات التي تستحق المناقشة.
أولاً ، يجب الانتباه إلى أن بنية list غير قابلة للتغيير ، مما يعني أن الوظيفة يجب أن تأخذ مكدسًا موجودًا وتعيد واحدة جديدة. هذا ليس مجرد تغيير إلى مكدس موجود. في الواقع ، جميع الوظائف في هذا المثال سيكون لها تنسيق مماثل:
Input: Stack - Output: Stack
ثانيا ، لماذا تذهب المعلمات في هذا الترتيب؟ لماذا يجب أن يذهب المكدس أولاً أو آخر؟ في القسم الخاص بتصميم الوظائف مع التطبيق الجزئي ، قيل إن المعلمة الأكثر تغييرًا يجب أن تستمر. سيكون من الممكن قريبًا التحقق من اتباع هذه التوصيات.
أخيرًا ، يمكن جعل الوظيفة أكثر إيجازًا عن طريق التطابق مع النمط في معلمة الدالة نفسها ، بدلاً من let في الوظيفة.
النسخة المعاد كتابتها:
let push x (StackContents contents) = StackContents (x::contents)
أفضل بكثير!
بالمناسبة ، انظر إلى توقيعها الجميل:
val push : float -> Stack -> Stack
كما ذكرنا سابقًا ، يخبرنا التوقيع كثيرًا.
في هذه الحالة ، يمكنني تخمين ما تفعله هذه الوظيفة ، فقط من خلال توقيعها ، حتى دون أن أعرف أنها تسمى "دفع".
هذا سبب آخر كان من الجيد وجود أسماء كتابة صريحة. إذا كانت المكدس مجرد قائمة بأرقام الفاصلة العائمة ، فلن تكون الوظيفة ذاتية التوثيق.
بطريقة أو بأخرى ، تحقق:
let emptyStack = StackContents [] let stackWith1 = push 1.0 emptyStack let stackWith2 = push 2.0 stackWith1
يعمل عظيم!
كومة أعلى علوية باستخدام دفع
مع هذه الوظيفة البسيطة ، يمكنك بسهولة تحديد العملية التي تدفع رقمًا محددًا في المجموعة.
let ONE stack = push 1.0 stack let TWO stack = push 2.0 stack
لكن انتظر لحظة! ترى أن المعلمة stack مذكورة على جانبي التعبير؟ في الواقع ، ليس من الضروري ذكرها مرتين. بدلاً من ذلك ، يمكنك حذف المعلمة وكتابة دالة مع تطبيق جزئي:
let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0
من الواضح الآن أنه إذا كانت وظيفة push بها ترتيب مختلف للمعايير ، فيجب ذكر stack مرتين.
يجدر أيضًا تحديد دالة تنشئ مكدسًا فارغًا:
let EMPTY = StackContents []
تحقق من الوظائف المستلمة:
let stackWith1 = ONE EMPTY let stackWith2 = TWO stackWith1 let stackWith3 = THREE stackWith2
هل هذه المداخن الوسيطة مزعجة؟ هل من الممكن التخلص منها؟ بالطبع! لاحظ أن وظائف ONE و TWO و THREE لها نفس التوقيع:
Stack -> Stack
لذلك ، فهي مرتبطة تماما معا! إخراج وظيفة واحدة يمكن إدخالها إلى ما يلي:
let result123 = EMPTY |> ONE |> TWO |> THREE let result312 = EMPTY |> THREE |> ONE |> TWO
ظهرت من المكدس
مع إضافة إلى المكدس أحسب ، ولكن ماذا عن وظيفة pop ؟
عند الاسترجاع من المكدس ، من الواضح أنه من الضروري إرجاع الجزء العلوي من المكدس ، لكن هل هذا صحيح؟
في نمط وجوه المنحى ، والجواب هو نعم . ولكن في حالة OOP ، سيتم تغيير المكدس خلف الكواليس ، بحيث تتم إزالة العنصر العلوي.
ومع ذلك ، في أسلوب وظيفي ، المكدس غير قابل للتغيير. هناك طريقة واحدة فقط لإزالة العنصر العلوي - إنشاء مكدس جديد بدون هذا العنصر. من أجل أن يتمكن المتصل من الوصول إلى المكدس الجديد المخفض ، يجب إرجاعه مع العنصر العلوي.
بمعنى آخر ، يجب أن ترجع الدالة pop قيمتين ، العنصر العلوي والمكدس الجديد. إن أبسط طريقة للقيام بذلك في F # هي ببساطة استخدام tuple.
التنفيذ:
/// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack)
وظيفة الناتجة هي أيضا بسيطة جدا.
كما كان من قبل ، contents استخراج contents مباشرة من المعلمة.
ثم ، contents فحص contents باستخدام match..with تعبير.
ثم يتم فصل العنصر العلوي عن بقية القائمة ، ويتم إنشاء مكدس جديد استنادًا إلى العناصر المتبقية ، وأخيراً يتم إرجاع كل هذا كزوج tuple.
حاول تشغيل هذا الرمز ومعرفة ما يحدث. سوف تحصل على خطأ ترجمة!
اكتشف المترجم حالة لم يتم حلها - ماذا يحدث إذا كانت المكدس فارغة؟
عليك أن تقرر كيفية التعامل معها.
أفضل عادةً استخدام حالة خاصة للخطأ ، لكن في هذه الحالة بالذات ، فضلت وضع استثناء. إصدار ثابت من pop مع معالجة حالة فارغة:
let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow"
تحقق:
let initialStack = EMPTY |> ONE |> TWO let popped1, poppedStack = pop initialStack let popped2, poppedStack2 = pop poppedStack
واختبار استثناء:
let _ = pop EMPTY
وظائف الحساب
الآن وقد أصبحت الإضافة والحذف في مكانها الصحيح ، يمكنك البدء في العمل مع وظائف الإضافة والضرب:
let ADD stack = let x,s = pop stack // let y,s2 = pop s // let result = x + y // push result s2 // let MUL stack = let x,s = pop stack // let y,s2 = pop s // let result = x * y // push result s2 //
الاختبار عبر الإنترنت:
let add1and2 = EMPTY |> ONE |> TWO |> ADD let add2and3 = EMPTY |> TWO |> THREE |> ADD let mult2and3 = EMPTY |> TWO |> THREE |> MUL
إنه يعمل!
إعادة بيع الوقت ...
من الواضح ، يتم تكرار كمية كبيرة من التعليمات البرمجية في هاتين الوظيفتين. كيف يمكننا إصلاح هذا؟
تقوم كلتا الدالتين باستخراج قيمتين من المكدس ، وتطبيق دالة ثنائية معينة عليها ، ثم دفع النتيجة مرة أخرى إلى المكدس. يمكنك إخراج الشفرة العامة إلى الدالة الثنائية ، والتي تأخذ دالة رياضية بمعلمتين:
let binary mathFn stack = // let y,stack' = pop stack // let x,stack'' = pop stack' // let z = mathFn xy // push z stack''
لاحظ أنه في هذا التطبيق ، يتم تمييز إصدارات مختلفة من الكائن "نفسه" بعدد مختلف من علامات اقتباس. وذلك لأن اللواحق العددية يمكن أن تؤدي بسهولة إلى الارتباك.
السؤال: لماذا المعلمات لديها هذا الترتيب بالضبط ، بدلا من mathFn قادمة بعد stack ؟
الآن بعد أن أصبحت لديك وظيفة binary ، أصبح من السهل تحديد ADD ووظائف أخرى:
أول محاولة لتنفيذ ADD باستخدام binary :
let ADD aStack = binary (fun xy -> x + y) aStack
ولكن يمكنك التخلص من لامدا ، لأنه يمثل التعريف الدقيق للوظيفة المدمجة + :
let ADD aStack = binary (+) aStack
مرة أخرى ، يمكن استخدام تطبيق جزئي لإخفاء المعلمة المكدس. التعريف النهائي:
let ADD = binary (+)
تعريف الوظائف الرياضية الأخرى:
let SUB = binary (-) let MUL = binary (*) let DIV = binary (../)
جربه عبر الإنترنت:
let div2by3 = EMPTY |> THREE|> TWO |> DIV let sub2from5 = EMPTY |> TWO |> FIVE |> SUB let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB
وبالمثل ، يمكنك إنشاء وظيفة مساعدة للعمليات الأحادية
let unary f stack = let x,stack' = pop stack push (fx) stack'
وحدد بعض الوظائف الأحادية:
let NEG = unary (fun x -> -x) let SQUARE = unary (fun x -> x * x)
الوضع التفاعلي:
let neg3 = EMPTY |> THREE|> NEG let square2 = EMPTY |> TWO |> SQUARE
وضع كل ذلك معا | وضع كل ذلك معا
في المتطلبات الأولية ، تم ذكر أننا نود أن نكون قادرين على إظهار النتائج ، لذلك يجدر تحديد وظيفة SHOW.
let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack //
يرجى ملاحظة أنه في هذه الحالة ، يتم تجاهل الإصدار الجديد من المكدس المستلم عبر بروتوكول pop . النتيجة النهائية هي الحزمة الأصلية ، كما لو أنها لم تتغير أبدًا.
أخيرًا ، يمكنك كتابة المثال التالي من المتطلبات الأصلية
EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW
المضي قدما
إنه ممتع ، لكن ماذا يمكنك أن تفعل؟
يمكنك تحديد العديد من الوظائف الإضافية:
/// let DUP stack = // let x,_ = pop stack // push x stack /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let START = EMPTY
باستخدام هذه الوظائف الإضافية ، يمكنك كتابة بعض الأمثلة الأنيقة:
START |> ONE |> TWO |> SHOW START |> ONE |> TWO |> ADD |> SHOW |> THREE |> ADD |> SHOW START |> THREE |> DUP |> DUP |> MUL |> MUL // 27 START |> ONE |> TWO |> ADD |> SHOW // 3 |> THREE |> MUL |> SHOW // 9 |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5
باستخدام التكوين بدلا من الأنابيب
لكن هذا ليس كل شيء. في الواقع ، هناك طريقة أخرى مثيرة للاهتمام لتمثيل هذه الوظائف.
كما ذكرنا سابقًا ، لديهم جميعًا نفس التوقيع:
Stack -> Stack
نظرًا لأن المدخلات والمخرجات من نفس النوع ، يمكن أيضًا دمج هذه الوظائف باستخدام مشغل التكوين >> ، وليس فقط من خلال مشغلي خطوط الأنابيب.
بعض الأمثلة:
// let ONE_TWO_ADD = ONE >> TWO >> ADD START |> ONE_TWO_ADD |> SHOW // let SQUARE = DUP >> MUL START |> TWO |> SQUARE |> SHOW // let CUBE = DUP >> DUP >> MUL >> MUL START |> THREE |> CUBE |> SHOW // let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2 START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW
في كل من هذه الأمثلة ، يتم تعريف وظيفة جديدة باستخدام تكوين وظائف أخرى. هذا مثال جيد على نهج "اندماجي" لبناء الوظائف.
الناقلون مقابل التركيب
لقد رأينا طريقتين مختلفتين لاستخدام نموذجنا ؛ باستخدام الناقلات والتكوين. لكن ما الفرق؟ ولماذا يفضل واحد على الآخر؟
الفرق هو أن خطوط الأنابيب هي ، إلى حد ما ، عملية "تحول في الوقت الحقيقي". في وقت استخدام خط الأنابيب ، يتم تنفيذ العمليات على الفور ، من خلال نقل مكدس معين.
من ناحية أخرى ، فإن التكوين يشبه "الخطة" التي نريد تنفيذها ، وبناء الوظائف من مجموعة من المكونات دون تطبيق مباشر.
على سبيل المثال ، يمكنك إنشاء "خطة" لحساب مربع الرقم من خلال مجموعة من العمليات الصغيرة:
let COMPOSED_SQUARE = DUP >> MUL
لا أستطيع إعطاء ما يعادلها على أساس خطوط الأنابيب.
let PIPED_SQUARE = DUP |> MUL
سيؤدي هذا إلى خطأ ترجمة. أحتاج إلى بعض مثيل مكدس محدد للتعبير للعمل:
let stackWith2 = EMPTY |> TWO let twoSquared = stackWith2 |> DUP |> MUL
وحتى في هذه الحالة ، يمكنني الحصول على إجابة فقط لهذا الإدخال المحدد ، وليس خطة حسابية معممة تستند إلى أي إدخال ، كما في المثال مع COMPOSED_SQUARE .
هناك طريقة أخرى لإنشاء "خطة" تتمثل في تمرير لامدا صراحة إلى وظائف بدائية أكثر:
let LAMBDA_SQUARE = unary (fun x -> x * x)
هذه طريقة أكثر وضوحًا (والأكثر ترجيحًا على الأرجح) ، ولكن يتم فقد كل مزايا وضوح النهج التكويني.
بشكل عام ، إذا كان ذلك ممكنا ، يجب أن نسعى جاهدين لنهج تكويني!
كود كامل
كود كامل لجميع الأمثلة أعلاه:
// ============================================== // // ============================================== type Stack = StackContents of float list // ============================================== // // ============================================== /// let push x (StackContents contents) = StackContents (x::contents) /// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow" // ============================================== // () // ============================================== // // // let binary mathFn stack = let y,stack' = pop stack let x,stack'' = pop stack' let z = mathFn xy push z stack'' // // // let unary f stack = let x,stack' = pop stack push (fx) stack' // ============================================== // () // ============================================== /// let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack // /// let DUP stack = let x,s = pop stack push x (push xs) /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let DROP stack = let _,s = pop stack // s // // ============================================== // , // ============================================== // // ------------------------------- let EMPTY = StackContents [] let START = EMPTY // // ------------------------------- let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0 // // ------------------------------- let ADD = binary (+) let SUB = binary (-) let MUL = binary (*) let DIV = binary (../) let NEG = unary (fun x -> -x) // ============================================== // , // ============================================== let SQUARE = DUP >> MUL let CUBE = DUP >> DUP >> MUL >> MUL let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2
الخاتمة
لدينا آلة حاسبة بسيطة كومة مقرها. لقد رأينا كيف يمكنك ، بدءًا من بضع عمليات بدائية ( push ، pop ، binary ، unary ) وغيرها ، بناء DSL كامل ، سهل التنفيذ والاستخدام.
كما تعتقد ، كان هذا المثال يعتمد إلى حد كبير على اللغة الرابعة. أوصي بشدة بالكتاب المجاني "Thinking Forth" ، الذي لا يروي فقط عن اللغة Forth ، ولكن أيضًا عن طرق أخرى ( غير موجهة للكائنات!) لتحليل المهام التي تنطبق بنفس القدر على البرمجة الوظيفية بشكل عام.
حصلت على فكرة عن هذا المقال من مدونة آشلي فينيللو الرائعة. إذا كنت تريد الغوص بشكل أعمق في مضاهاة لغة قائمة على المكدس استنادًا إلى F # ، فابدأ بها. إستمتع!
موارد إضافية
هناك العديد من البرامج التعليمية لـ F # ، بما في ذلك المواد لأولئك الذين يأتون مع تجربة C # أو Java. قد تكون الروابط التالية مفيدة كلما تعمقت في F #:
موصوفة أيضًا عدة طرق أخرى لبدء التعلم F # .
أخيرًا ، يعتبر مجتمع F # صديقًا للمبتدئين جدًا. هناك دردشة نشطة للغاية في Slack ، بدعم من F # Software Foundation ، مع غرف مبتدئين يمكنك الانضمام إليها بحرية . نحن نوصي بشدة أن تفعل هذا!
لا تنسَ زيارة موقع مجتمع الناطقين بالروسية F # ! إذا كانت لديك أي أسئلة حول تعلم اللغة ، فسيسعدنا مناقشتها في غرف الدردشة:
حول مؤلفي الترجمة
ترجم بواسطة kleidemos
تم إجراء تغييرات في التحرير والتحرير من خلال جهود مجتمع الناطقين باللغة الروسية من مطوري F # . نشكر أيضًا @ schvepsss و @ shwars على إعداد هذه المقالة للنشر.