هاسكل بالعربي – الجزء التالت

في القرن ال17 كده الاخ جوتفريد ليبنز (اللي اخترع التفاضل بشكل منفصل عن نيوتن) عمل مكنة لطيفة كده و روشة بتجمع الارقام وتطرحها و بتشتغل يدوي, و خدته الاحلام بقي يعمل مكنة متطورة اكتر بتعمل جمل رياضية و تثبت صحتها او عدم صحتها و قعد باقي حياته بالفعل عال logic و الformal languages. 

في 1928 فيه 2 علماء رياضيات (ديفيد هلبرت) و (وليام اكرمان) اعادوا احياء هذه المشكلة ﻷنهم كانوا مركزين بشكل كبير في ابحاثهم علي علم المنطق, و سألوا سؤال :

هل ممكن يبقي فيه خوارزمية (مجموعة من الخطوات الرياضية) بتقدر انها تاخد كinput جملة منطقية و تقرر هل ممكن اثبات الجملة دي انطلاقا من البديهيات (axioms) اللي شغال بيها سيستم معين ؟

يعني مثلا, هل ممكن اديك بديهيات علم الجبر و اديك اثبات جبري, و انت تقولي هل الجملة دي قابلة للاثبات بالبديهيات دي ولا ﻷ عن طريق خوارزمية ما؟ و اتسمت المشكلة دي “مشكلة القرار” او بالالماني Entscheidungsproblem 

فضل السؤال ده تمن سنين لحد ما في خلال 1936 جه الان تيورنج و الوزنو تشرش و جاوبوا السؤال بشكل مستقل, بطريقتين مختلفين..

اجابة السؤال ده كانت “ﻷ, مفيش خوارزمية بتعمل كده” , و الاجابة دي كانت ميلاد الكمبيوتر ساينس 

ايه اللي حصل؟

الان تيورينج كان لسا مخترع ماكينة رياضية من الautomata اللي اتكلمنا عليها, لكنها نوع جديد متقدم, بيقدر يعمل و يحل اي خوازرمية رياضية, و قدر بالماكينة الرياضية دي يثبت ان مشكلة القرار للاسف حلها سلبي – الماكينة دي اسمها ال Turing Machine , اللي بعد كده هيكون النموذج الرياضي لكل الكمبيوترات..

و في نفس الوقت كان الوزنو تشرش شغال علي حل نفس المشكلة, لكن ب-استخدام لغة الوصف الرياضية بتاعته اللي قولنا عليها Lambda Calculus و وصل لنفس النتيجة و نشرها في نفس السنة – في الوقت ده الان تيورنج لاحظ ان :

Lambda Calculus == Turing Machines 

و ان النموذجين الرياضيين دول مكافئين لبعض, و ممكن نحول منهم لبعضهم, ممهدا الطريق ب-ده لنظرية لغات البرمجة. 

ايه علاقة ده بالبرمجة , و ايه هو التيورنج ماشين و اللامبدا كالكولاس , و ازاي قدروا يثبتوا المسألة دي ؟ 

*باقي البوست رياضيات عنيفة شوية*

اولا : التيورنج ماشين : 
زي ما اتكلمنا البوست اللي فات, التيورنج ماشين هي نموذج رياضي عام لالة بتقدر تحل اي خوارزمية قابلة للحساب (Computable) و مش موضوعنا اوي ازاي تكون الدالة قابلة للحساب. (بس نقدر من هنا نعرف ليه الComputer اسمه كده, عشان بCompute) 

ايه هي التيورنج ماشين؟ 
هي عبارة عن شريط زي شريط الكاسيت بس لا نهائي – و ليه راس بتقراه, و الشريط متقسم لخانات, كل خانة بتشيل symbol زي ال1 او 0 كده, و في الراس دي register بيخزن حالة الخانات دي او يبدلها, بحركة الراس عالشريط تقدر تحسب اي خوارزمية 

يعني الحركة دي لوفسرناها بشكل تكنيكال شوية المكنة دي بتقدر :
– تعمل read / write operation
– تعمل random data access 
– تعمل rule based data manipulation , يعني تعدل عالداتا بناء عالstates التانية ﻷنها عندها accepted و rejected states 

و بشكل نظري, لو اديت التيورنج ماشين وقت و ذاكرة لا نهائية تقدر تحسب اي حاجة ممكن تتحسب في الدنيا. 

لو حبينا نوصفها زي ما عملنا البوست اللي فات مع mealy and moore machines بشكل موازي للاوتوماتا : 

Turing Machine is a 7-tuple (Q, X, ∑, δ, q0, B, F) where :
– Q is a finite set of states
– X is the tape alphabet
– ∑ is the input alphabet
– q0 is the initial state
– B is the blank symbol
– F is the set of final states
– δ is a transition function; 
δ : Q × X → Q × X × {Left_shift, Right_shift}.

بناء عال alphabet بتاعة الماشين و الstates بتقدر تحدد امتي التيورنج ماشين بتتحرك و تاخد قرارات, ناخد مثال؟ 

تعالي ناخد الماشين دي 
Q = {q0, q1, q2, qf}
X = {a, b}
∑ = {1}
q0 = {q0}
B = blank symbol
F = {qf }

و عايزين نعمل الجدول اللي بيحدد قراراتها او ازاي بتحسب الالحوزيثم بتاعتها : 

لو الشريط عليه a :
هتروح q0 لو دخلك واحد , و معاها في الδ حركة لليمين و تكون اصلا في q1 

هتروح q1 لو انت في q0 و اتحركت شمال من عندها والانبوت كان 1 
هتروح q2 انت في الqf و اتحركت يمين و الانبوت 1 

و العكس بالعكس مع b.

المثال ده بسيط جدا بيوضح بس ازاي ممكن تعمل finite automata بالturing machine, ممكن يتعمله extension ﻷي خوارزمية موجودة. 

من التيورنج ماشين بنقدر نطلع الموديل الفيزيكال للكمبيوترات الموجودة حاليا, سواء الharvard model او الvon neumann model

بسبب التيورنج ماشين بقي عندنا علم التشفير, علم الخوارزميات والداتا ستراكشر و عندنا الcomputer architecture و كمان الماشين ليرننج 

ثانيا اللامبدا كالكولاس : 

قبل ما نعرف يعني ايه الموضوع ده, محتاجين نتكلم عن تعريف “الدالة” او الFunction , و ده اللي اتفق الناس انها عبارة علاقة بين فئتين (sets) الاشياء جوا واحدة منهم علي علاقة بالتانية عن طريق mapping او توصيل بينهم, علي شكل 
F : X->Y 
يعني لما بتدخل للدالة دي x بيتعمله تحويل لقيمة Y
بعدها الx و y دول sets اصلا, و بنقول في شكل رياضي ايه العلاقة بين الاتنين بشكل ما زي 

y = x+3 = f(x) 
يعني كل عنصر بيخش للدالة دي بيتجمع عليه 3. 

جه بقي عم الونزو و قالك احنا ممكن نعبر عن اي خوارزمية بالطريقة دي, عبارة عن مجموعة functions , و استعمل الفكرة دي عشان يصمم نوع من علم الحساب (Calculus) بيقدر يدحله دوال و يعملها evaluation او يحسب قيمتها, و منه يجيب حساب الخوارزمية , ازاي؟ 

بيتم تعريف الlambda calculus علي انه : 
M ::= x | λx.M | M M

– حيث انه الx ده اسم متغير
– و ال λx.M دي دالة ما
– و ال M ده مصطلح ما

تعالي ناخد خطوة لقدام 

لو عندك حاجة زي كده : 
λx.x+1 

نفصصه : 
λx 
معناها دالة λ بتاخد انبوت x 
النقطة . معناها ان الدالة دي بتعمل عملية عالانبوت
العملية دي x+1 

يعني : 
λx.x+1 
مساوية في المعني ل 
f(x) = x+1 

لو جينا نحلها : 
(λx.x+1)3 = f(3) = 4 

ده مثال بسيط, لكن و احنا ماشيين في haskell هنتعلم ازاي نستعمل حاجات اكثر عنفا زي الrecursion و الcurrying (متشغلش بالك بيهم دلوقتي) 

بسبب اللامبدا كالكولاس بقي عندنا لغات البرمجة, و افكار كتيرة جواها زي الOOP و الFP و static typing و ال lexical scoping

ازاي اللامبدا كالكولاس و التيورنج ماشيين متكافئين؟ 

الاتنين متكافئين, ﻷن من الممكن التعبير عن التيورنج ماشين بالكامل بال lambda calculus ﻷنها automata قابلة للتحويل لمعادلات و دوال 

و العكس بالعكس ممكن تعبر عن اللامبدا كالكولاس ﻷنها (لغة) عن طريق تحويلها لتيورنج ماشيين.

من هنا هنخش البوست الجاي علي مبادئ لغة Haskell , ﻷنها اكتر لغة بتطبق ال lambda calculus بشكل محترم و بيحافظ عالfunctional programming 

و للحديث بقية.

2 thoughts on “هاسكل بالعربي – الجزء التالت

Add yours

Leave a Reply to rk Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

Create your website at WordPress.com
Get started
%d bloggers like this: