السنن الكونية (2): كل شيء حسابات

( هذا المقال يعتبر "الرأي المقابل" أو "الوجه الآخر للعملة" لمقال سابق هو "النهضة بين التصوير والمنطق".)

 يسير الكون بعمليات حسابية.

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

 ونحن حين نفكّر نحاول أن نسبق الكون في حساباته على أمل أن نتحكم أو نؤثر في النتيجة النهائية. لو حاولت ان ترمي الكرة نحو السلّة، فإنك تحاول ان تحسب "ماذا ستفعل قوانين الطبيعة بالكرة؟" قبل ان يحدث هذا فعلا.. وآلة الحساب هي تدريب الرمي الذي تدربته قبل ذلك -- هذا التدريب قد ترك ارقاما في جهازك العصبي وهذه الارقام تقوم بعمل simulation للرمية قبل ان تحدث، 

وبهذا الsimulation يقوم جهازك العصبي بعمل حسابات عكسية ايضاً: تبدأ بالنتيجة المطلوبة ،وهي أن تسقط الكرة في السلة، وتنتهي بالرمية الصحيحة التي تؤدي لهذه النتيجة، أي أنك تستطيع تفعيل قوانين الطبيعة بالعكس في حساباتك!

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

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

 وكل شيء يمكن تسميته تفكيراً يمكن في رأيي تسميته حسابات. وسوف أظهر لك هذا بأمثلة كثيرة:

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

- حين تمسك بالشوكة لتأكل، فإنك تحسب حسابات (في حقيقتها معقدة جدا، يعرف هذا من عمل في مجال الروبوت) لكي توجه كل عضلة في جسمك بحيث تتحرك الشوكة في مسارها المطلوب

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

 لكن كيف يمكن لأنسان أن يتوقع كيف سيرد شخص آخر؟ نحن نتوقع هذا لأن الطرف الآخر هو الآخر يحسب حسابات بناءً على كلامنا، فلو عرفنا كيف يحسب هذا لأمكننا أن نسبقه في حساباته.

وبشكل عام فإن أي مجال يشتمل تخاطباً مع البشر، مثل التسويق، التأليف، الصحافة، الخ، يشتمل حسابات في صورة "كيف سيشعر الشخص لو قرأ أو سمع أو عرف كذا" 

(ربما لهذا أنا شخص قليل الكاريزما؛ لأن 'المعادلات' التي احسب بها مختلفة عن معظم الناس، وبالتالي حساباتي خاطئة فأقول شيئا احسبه سيسرّهم لكن يضايقهم)

  - ماذا عن الحسابات غير التنبؤية؟ ماذا عن شركة تحسب مرتبات موظفيها مثلا؟ هي في رأيي حسابات تنبؤية لكنها اكثر تجريدا من حساب شيء ظاهر كحركة الكرة. حين احسب لكل موظف مرتبه فأنا احسب المقدار الذي سيشعره انه أخذ مقابلا عادلا لعمله، أو يشعرني انني لم ابخسه حقه، وكل واحد فينا يشعر بهذه الاشياء عن طريق حسابات يقوم هو نفسه بها، وحين احسب المرتبات فأنا احاول ان اسبق 'حسابات المشاعر' أو 'حسابات العدل' هذه لكي تكون نتيجتها كما أتمنى.

وكثير من التفكير لا يبدو كحسابات لأننا نقوم به تلقائيا أو فطرياً، فأنت حين تتحدث مع خالك فإنك لا تمسك بورقة وقلم وتحسب بل أنك..تتحدث! هنا يأتي دور علم الـcomputer science، وهو في رأيي علم كل خطوة له يحول التفكير الفطري إلى حسابات رياضية.

 

  حساب مرتبات الموظفين » لعب الشطرنج »» الرسم »» التعرف على الوجوه »» حركات الروبوت »» التخاطب البشري

 

في كل خطوة من هؤلاء تحول شيء كنا نظنه "تفكيراً" فإذا هو..حسابات رياضية

 

أما البرمجة فجزء كبير منها هو فكرة "الحسابات العكسية" أو "التفكير بالعكس"، تبدأ بتخيل البرنامج النهائي كيف تريده أن يعمل، وتنتهي بالكود التي تجعله يعمل كما تخيلت، وقوانين الطبيعة هنا هي قواعد لغة البرمجة التي تستخدمها...لكن تنبٌه! الكمبيوتر ساينس يحول كل أنواع التفكير إلى حسابات، وبالتالي قواعد لغة البرمجة هذه تصلح لأن تحاكي 'قوانين الطبيعة' أو 'المعادلات' في أي مجال آخر

 

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

 

أو بمعنىً آخر..علّموا الأطفال البرمجة 

A Prolog for my Kalimat

I've tried twice to add program analysis to Kalimat, and each time I had trouble. Program analysis is collecting data about the program to use for IDE features like 'go to definition', autocomplete, 'find usages', and so on.

Basically this operation has 3 parts:

• Regularly parse the code in the editor windows (for speed most IDEs reparse only the changed parts of the code).
• Update a program database that holds information like what methods are defined in each class, where is some variable declared,...etc
• When you need to do some action like 'go to definition', query that database

Let's ignore part #1 and focus on updating and querying the program database. The first time I implemented it the solution was very ad-hoc: I stored things in hashtables, queried them with loops, and the code was very tedious, repetitive, and error-prone.

This was clearly not good, so I decided to use a real database: SQLite is a lightweight database engine that can be easily embedded in other programs, and also has the option to store data in memory instead of on disk. Perfect. In the second iteration the code for 'go to definition' looked something like this:

QSqlQuery q;
q = progdb.q("SELECT defining_token_pos, function_definitions.module_filename "
   "FROM function_definitions JOIN definitions ON definitions.id=function_definitions.def_id AND "
   "definitions.module_filename = function_definitions.module_filename WHERE (definitions.module_filename IN (SELECT imported FROM "
   "module_imports WHERE importer=?) OR definitions.module_filename=?) AND definitions.name in (SELECT lexeme FROM tokens WHERE pos <=? "
   "AND pos + length >=?)", filename, cursorPos, cursorPos, filename);
if(q.next()) { 
   docContainer->OpenOrSwitch(q.value(1).toString());
   ((MyEdit *)currentEditor())->;jumpToPos(q.value(0).toInt()); return;
}

It might look complex but the idea is simple, what the query's trying to say is "Find the filename and position of the function definition that has the same name as the name under the cursor. When looking for a function definition, look in the current module or any module imported by the current module".

This works, but has a lot of drawbacks

1- The query isn't recursive. If the current file imports module A, the IDE will look there for definitions, but if we import 'A', and 'A' imports 'B', the IDE will not look there. We want all modules reachable from the current module to be found.

SQL isn't very friendly with recursion so I probably would've had to implement recursion myself with C++ code.

2- The bigger problem is that the SQL here is too complex. Sure it beats loops and hashtables but it's still big, and that's only for 'go to definition'! How about when I add public and private definitions? namespaces?

What I need is a reasoning system. Luckily there's one: Prolog.

Actually I don't need the full Prolog language; a subset of Prolog has been created to support complex queries (much more complex than SQL), this subset is called Datalog, and it's successfully used in program analysis in many research projects.

I set out to find a nice Datalog implementation for my aims, but didn't find something sufficient: there's an excellent library called BDDBDDB but it's in Java, and there's another one called simply 'Datalog' written in C and Lua that seemed not straightforward to integrate with Kalimat (nb: Kalimat is written in C++/Qt).

Then I looked at open source Prolog implementations like SWI or Ciao, and while very powerful and fast, they didn't seem easy to integrate with a standalone C++ app, especially an app like Kalimat that has to run on both Windows and Linux. I might be wrong but I felt it wasn't easy.

So what did I do? Why, created a new Prolog implementation of course! It's called SmallProlog (and nicknamed 小さい Prolog), specially designed for integration with C++/Qt.

Using Prolog from C++ has never been easier:

PrologEngine engine;
engine.load(prologCode);
engine.call("predicate", arg1, arg2, [](QMap<QString, QVariant> sol){ 
 // do stuff with each solution
});

The expression [ ](QMap<QString,QVariant> sol){ ... } is a lambda expression, a new feature of C++. You define here an anonymous function that gets called whenever the Prolog engine finds a solution. The 'solution' will be a map from variable names to their values.

Under the hood the engine stores facts in a SQLite database, but this time the queries are generated for us from a higher level and more expressive language.

So how does 'go to definition' look now?

usagesOfProc(DefModule,DefPos,UseModule,UsePos):-
    visibleFrom(UseModule,DefModule),
    procInvokation(UseModule,Name,UsePos),
    proc(DefModule,Name,DefPos,_,_,_)
    .
  
visibleFrom(Mod1, Mod2):-
    visibleFrom2(Mod1,Mod2,[Mod1]).
visibleFrom2(M1,M1,_).
visibleFrom2(M1,M2,Visited):-
    imports(M1,Temp),
    not(member(Temp,Visited)),
    visibleFrom2(Temp, M2,[Temp|Visited]).

The second predicate, called visibleFrom, can take a Kalimat module and give us all the other modules reachable (recursively) from the first module, including itself.

It can also work in the opposite direction: given a module it can give us all modules that 'see' it. The power & elegance of Prolog at work.

The first predicate, called usagesOfProc, takes a module & a position of a function call, and gives us another module and position where the function is defined.

It can also work in the opposite direction: given a function definition, it can give us all files and positions where the function is called.

So when I implemented 'go to definition' I was also implementing 'find usages'; write a feature and get one for free! The power & elegance of Prolog at work.

Aside: I wish the makers of Prolog implementations marketed them as languages for more than industrial and vertical market type applications, and made them trivial to integrate with all types of other languages.

Also, to help myself with debugging, I made a Prolog console where I can query the Kalimat program database live, while the IDE is running:

It's an experiment, and it's still unfinished so I don't know if it'll work as I desire or not, but I'm very excited about it. Aren't you? :)

رسم الصيغ الرياضية بلغة كلمات (الجزء الثاني)

الهدف من المشروع هو برنامج يرسم الصيغ الرياضية، مثلاً يقول له المستخدمم س^2 + 5 فيرسم البرنامج شكل الـparabola المعروف.

• في الجزء الأول تحدثنا عن الإعراب، الدالة التي تأخذ نصاً مثل 12+13 وتعود بالمصفوفة ["+"، 12، 13] التي تمثل ما يسمى بشجرة الإعراب parse tree.

لو كنت قد قرأت الجزء الأول فأنت إذاً جاهز الآن لنختتم هذه السلسلة.

حساب قيمة التعبير

حسناً. لدينا الآن شجرة إعراب مثل 100 أو ["+"، س، 12]، ماذا نفعل بها؟ نريد دالة اسمها تقييم تأخذ الشجرة وتعود بالقيمة التي تعبر عنها.

• لو كانت "الشجرة" في صورة قيمة عددية، نعود بتلك القيمة.
• لو كانت الشجرة هي المتغير س (كقيمة نصية)، فإننا لا نستطيع أن نفعل شيئاً بأنفسنا، لذلك سوف نقدم عاملاً إضافياً parameter للدالة تقييم به قيمة س المطلوبة.
• لو كانت الشجرة في صورة مصفوفة مثل ["+"، أ، ب] سوف نقوم بالآتي:
• ناد الدالة تقييم مع الفرع الأيمن أ لحساب قيمته
• ناد الدالة أيضاً مع الفرع الأيسر ب
• نفذ العملية الحسابية وارجع بالنتيجة.

كل هذا يعطينا الكود التالية، الدالة تأخذ الشجرة "ت" وقيمة "س" المحددة من البرنامج، وتحسب قيمة الصيغة الرياضية:

دالة تقييم (ت، س):
    إذا ت ~ ["+"، ؟أ، ؟ب]:
        ارجع ب: تقييم (أ، س)+ تقييم (ب، س)
    وإلا إذا ت ~ ["-"، ؟أ، ؟ب]:
        ارجع ب: تقييم (أ، س)- تقييم (ب، س)
    وإلا إذا ت ~ ["×"، ؟أ، ؟ب]:
        ارجع ب: تقييم (أ، س)× تقييم (ب، س)
    وإلا إذا ت ~ ["÷"، ؟أ، ؟ب]:
        مقام = تقييم (ب، س)
        إذا مقام <> 0 :
            ارجع ب: تقييم (أ، س)÷ مقام 
        وإلا :
            اطبع "خطأ: قسمة على صفر" 
            ارجع ب: 0 
        تم 
    وإلا إذا ت ~ ["^"، ؟أ، ؟ب]:
        ارجع ب: أس (تقييم (أ، س)، تقييم (ب، س))
    وإلا إذا ت ~ "س" :
        ارجع ب: س 
    وإلا :
          -- لو وصلنا إلى هنا فقيمة ت هي اصلا عدد
         ارجع ب: ت 
    تم 
نهاية

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

إجراء ارسم.المحاور ():
    ارسم.خط (400، 0)- (400، 599)
    ارسم.خط (0، 300)- (799، 300)
نهاية

الآن سوف نكتب الدالة التي ترسم فعلاً. خطتنا كالآتي:

الدالة سوف تأخذ عاملين: من.س و إلى.س،  لكي نستطيع أن نقول مثلاً ارسم س^2 من س=-4 إلى س=4

سوف تقوم الدالة بالآتي:

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

هذا يعطينا الكود :

إجراء ارسم.الدالة (التعبير، من.س، إلى.س):
    أ = من.س 
    أ.قديم = لاشيء 
    ص.قديم = لاشيء 
    مقياس.س = 20 
    مقياس.ص = 15 
    
    كرر مادام أ <= إلى.س :
        ص = تقييم (التعبير، أ)
        إذا ليس أ.قديم = لاشيء :
            س1 = - أ × مقياس.س + 400 
            ص1 = - ص × مقياس.ص + 300 
            س2 = - أ.قديم × مقياس.س + 400 
            ص2 = - ص.قديم × مقياس.ص + 300 
            ارسم.خط (س1، ص1)- (س2، ص2)، 4 
        تم 
        أ.قديم = أ 
        ص.قديم = ص 
        أ = أ + 0.1 
        انتظر (30)
    تابع 
نهاية

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

لا يبقى إلا ان نربط كل المكونات ببعضها!

اقرأ "الصيغة؟"، الصيغة 
اقرأ "من؟"، # أ 
اقرأ "إلى؟"، # ب 

الصيغة = تبديل (الصيغة، " "، "")
الشجرة = تعبير (الصيغة)
ارسم.المحاور ()
ارسم.الدالة (الشجرة، أ، ب)

ماذا فعلنا؟

• قرأنا الصيغة من المستخدم (وقيم س التي سنبدأ وننتهي بها)
• حذفنا المسافات من الصيغة
• أعربناها لنحصل على شجرة الإعراب بواسطة الدالة تعبير
• رسمنا المحاور
• نادينا ارسم.الدالة وأعطيناها الشجرة وقيم من.س وإلى.س
• ارسم.الدالة سوف تنادي تقييم باستمرار لكي تحسب قيمة الصيغة عند كل قيمة لـ س
• ....وترسم الخطوط المطلوبة!

كم سطراً كتبنا؟ للأسف تجاوزنا حاجز المائة قليلاً: 109. لكن لو حذفنا السطور الفارغة بين تعريفات الدوال...الخ سيكون العدد أقل من المائة.

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

يمكنك عزيزي القاريء أن تجرب عمل نسخة متقدمة من البرنامج تضيف إمكانية استخدام الدوال مثل جتا، جا، أو تضيف الثابتين ط (π) و هـ (e) أوتقدم بعض المساعدة للمستخدم. لمَ لا تجرب؟ :)

رسم الصيغ الرياضية بلغة كلمات

نريد برنامجاً يأخذ صيغة رياضية ويرسمها!

وإمعاناً في التحدي، نريد أن نكتب هذا البرنامج في مائة سطر من الكود أو أقل. هل سنقدر يا ترى؟ أعتقد أنك ستستمتع كثيراً بهذا المقال عزيزي القاري.

الجزء الأول: كيف نفهم الصيغة الرياضية؟

يوجد في علوم الحاسب ما يسمى parsing (الإعراب). لو أعربنا التعبير الحسابي س^2+5 فسيكون لنا النتيجة التالية:

هذه الرسمة اسمها "شجرة الإعراب" أو parse tree، وهي تشبه الشجرة لأن لها جذراً وفروعاً. كيف نعبر عن هذه الشجرة بقيمة في لغة كلمات؟ هناك طرق كثيرة: يمكن أن نستخدم الفصائل والكائنات، أو المصفوفات، أو القواميس...فلنستخدم طريقة بسيطة: سوف تكون كل شجرة عبارة من مصفوفة من ثلاثة عناصر: العملية الحسابية نفسها، والقيمتان التي تجري عليهما العملية. مثلاً إن قمنا بإعراب التعبير "4+5" سوف نحصل على المصفوفة ["+"، 4، 5]. لو أعربنا القيمة النصية "(4+5)×2" سوف نحصل على ["×"، ["+"، 4، 5]، 2]. أي أن الشجرة هي عملية ضرب بين ["+"، 4، 5] وبين 2.

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

لاحظ أن الإعراب لا يعود دائماً بمصفوفات..لو أعربنا مثلاً التعبير 12 فإن "الشجرة" ما هي إلا العدد 12 نفسه.

رائع. الآن علينا أن نفكر: مم تتكون الصيغ الرياضية؟ سوف نسمي الصيغة في صورتها النهائية "تعبير حسابي"، وهذا التعبير مكون من حد واحد أو أكثر. ما الذي يفصل بين الحدود في التعبير الواحد؟ علامات الجمع والطرح. أي أن التعبير يكون في صيغة حد1 + حد2 - حد3....الخ، أو مكون من حد واحد.

كيف نعبر عن هذا رياضياً؟ هناك طريقة اسمها Parse Expression Grammar أو PEG تسمح لنا أن نكتب القاعدة بهذه الطريقة:

تعبير = حد "+" تعبير       (هذه قاعدة 1#)

أو       حد "-" تعبير       (قاعدة 2#)

أو       حد                  (قاعدة 3#)

ما معنى هذا الوصف؟ معناه أن التعبير يمكن أن يكون حداً واحداً أو مجموعة من الحدود يفصل بينها + و -. مثلاً يمكن أن نبدأ بالحد "2×3". نحن نعرف أن هذا تعبير من قاعدة #3 من التعريف. ماذا عن 1 + 2×3؟ نعرف أن هذا أيضاً تعبير (من قاعدة #1 التي تقول أن حد + تعبير = تعبير، وبالتالي سمحت لنا بإضافة حد في المقدمة). ماذا عن 5 - 1 + 2×3؟ هذا أيضاً تعبير من جزء 2# من التعريف

لو شعرت أن الأمر صعب فلا تقلق: الموضوع ببساطة هو recursion مثلما تعلمت في البرمجة. المسألة هي أن التعبير يمكن أن يكون حداً أو يكون حد + حد + حد ....، أو حد + حد - حد - حد ....الخ.

ماذا عن الحدود نفسها؟ الحد هو "أس" واحد أو أكثر تفصل بينها علامات  ×، ÷

هذه كلها حدود:

5^2 × 6

6 ÷ 3

18

6^س

كيف نكتبها بطريقة PEG؟ هكذا:

حد = أس "×" حد

أو     أس "÷" حد

أو أس

وهي كما ترى نفس طريقة التعبيرات. لاحظ أن قيمة عادية مثل "18" نعتبرها أس رغم غياب علامة ^، مثلما اعتبرنا أن 12 هو تعبير رغم غياب علامة + أو -

ماذا عن الأسس؟ هي ببساطة مجموعة من واحد أو أكثر من التعبيرات الأولية يفصل بينها علامة ^. كل هذه أسس:

س^2

2^س

س^2^3

س

12

والقاعدة (كما خمنت) هي:

أس = أولي "^" أس

أو     أولي

ولكن ما هو التعبير الأولي؟؟؟ إنه رقم، أو المتغير س، أو تعبير بين أقواس:

أولي = "س"

أو     رقم

أو  "(" تعبير ")"

لم يبق ما نعرّفه سوى الأرقام نفسها. الرقم هو خانة واحدة أو أكثر (الخانة هي الرمز 0، أو 1، أو 2...إلى 9).

رقم = خانة رقم

أو خانة

خانة = من "0" إلى "9"

الرقم هو خانات لا يفصل بينها شيء. لهذا لم نقل مثلاً رقم = خانة + رقم بل قلنا مباشرةً رقم = خانة رقم....

ولكن ما فائدة كل هذا؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

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

قواعد تعبير :
    تعبير = حد "+" تعبير 
    أو حد "-" تعبير 
    أو حد 

    حد = أس "×" حد 
    أو أس "÷" حد 
    أو أس 

    أس = أولي "^" أس 
    أو أولي 


    أولي = رقم 
    أو "س" 
    أو "(" تعبير ")" 

    رقم = خانة رقم
    أو خانة 

    خانة = من "0" إلى "9" 
نهاية 

اطبع تعبير ("1+2+3")

في السطر الأخير نجرب القواعد الجديدة. سوف يطبع مفسر كلمات لك القيمة......لاشيء :(

لماذا؟ في الواقع سوف تقوم كلمات بإعراب التعبير، لكننا لم نطلب منها أن تعطينا شجرة إعراب، لذلك سوف تعود لنا بالقيمة لاشيء. هيا نغير ذلك الموقف! فلنبدأ بشيء بسيط كالأرقام:

رقم = خانة:أ رقم:ب => أ + ب 
أو خانة 

خانة = من "0" إلى "9"

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

يمكن أن نقرأ السطر كله كالآتي: الرقم مكون من خانة هي أ، ورقم أصغر هو ب، وحين نجدهما نعود بالقيمة أ + ب.

لاحظ أن أ و ب هما نصان، فلو أعربنا الرقم "123" فسيكون أ = "1" و ب يساوي "23" (الأرقام تقرأ من اليسار) وبهذا يكون الرقم كله هو أ + ب = "123"

ماذا عن السطر الثاني الذي يقول أو خانة؟ نحن لم نخبره بأي قيمة يعود، لكن لو رأى مفسر كلمات قاعدة ما هي الا استدعاء قاعدة أخرى (نحن لم نفعل سوى استدعاء "خانة") فسيعود بنفس القيمة الآتية من القاعدة المستدعاه. كأني بالضبط قلت أو خانة:أ => أ

ماذا عن السطر خانة = من "0" إلى "9"؟ حين تكون القاعدة ما هي إلا قيمة نصية فالقيمة العائدة منها هي نفس القيمة النصية.

إذاً قد عرفنا ماذا يرجع من رقم. ماذا عن شيء مثل تعبير؟

تعبير = حد:أ "+" تعبير:ب => ["+"، أ، ب]
أو حد:أ "-" تعبير:ب => ["-"، أ، ب]
أو حد:أ => أ

باللغة البشرية:
التعبير هو حد اسمه أ، ثم علامة "+"، ثم تعبير أصغر اسمه ب ، وفي تلك الحالة ارجع بالمصفوفة ["+"، أ، ب]
أو هو حد اسمه أ، ثم علامة "-"، ثم تعبير أصغر اسمه ب، وهنا ارجع بالمصفوفة ["-"، أ، ب]
أو هو مجرد حد اسمه أ، وفي تلك الحالة ارجع بذلك الحد.

سهل، أليس كذلك؟ بنفس الطريقة نعدل "حد" و "أس" و"أولي" ليكون لدينا القواعد كلها:

قواعد تعبير :
    تعبير = حد : أ "+" تعبير : ب => ["+"، أ، ب]
    أو حد : أ "-" تعبير : ب => ["-"، أ، ب]
    أو حد : أ => أ 

    حد = أس:أ "×" حد:ب => ["×"، أ، ب]
    أو أس:أ "÷" حد:ب => ["÷"، أ، ب]
    أو أس:أ => أ 

    أس = عامل:أ "^" أس:ب => ["^"، أ، ب]
    أو عامل 

    عامل = رقم:أ => كعدد (أ)
    أو "س" 
    أو "(" تعبير : أ ")" => أ 

    رقم = خانة : أ رقم : ب => أ + ب 
    أو خانة 

    خانة = من "0" إلى "9" 
نهاية 

لاحظ أننا في هذا الجزء التالي قد حولنا الرقم من قيمة نصية إلى قيمة عددية:

عامل = رقم:أ => كعدد (أ) 

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

سوف تصنع لنا كلمات دالة اسمها "تعبير" (لأننا قد سمينا القواعد "تعبير")، وهذه الدالة إن أعطيناها نصاً فستعطينا شجرة إعراب. جرب أن تضيف هذا السطر في آخر البرنامج:
اطبع تعبير("12+13×14")

سوف يظهر المخرج التالي:

["+"، 12، ["×"، 13، 14]]


في الواقع الكود السابقة ليست دقيقة لأن العمليات الرياضية + - ÷ × بها خاصية left associativity. أي أن تعبير مثل 1-2-5 المفروض أن يكون (1-2)-5، لكن برنامجنا يعتبره 1-(2-5)، أي أنه يعود بالشجرة ["-"، 1، ["-"، 2، 5] بدلاً من الشجرة الصحيحة وهي ["-"، ["-"، 1، 2]، 5]

سبب المشكلة هو أنه كان المفروض في القواعد أن نقول:
تعبير = تعبير + حد
ولكننا قلنا
تعبير = حد + تعبير

للأسف لا يمكن استخدام الطريقة الصحيحة في هذا الإصدار من كلمات بسبب مشكلة اسمها left recursion (هناك طرق لحل تلك المشكلة لكنها لم تطبق في كلمات بعد). لذلك علينا الحذر: البرنامج سيعطي نتائجاً خاطئة في المدخلات أ-ب-ج أو أ÷ب÷ج، ولكن يمكننا استخدام الأقواس في تلك الحالات.

على العموم قد أنهينا جزء إعراب الصيغ الرياضية، ومازال لدينا 70 سطراً أيضاً!

البقية في الجزء الثاني

Solving an ACM problem with Kalimat (part 2)

• هذا المقال تكملة للجزء الأول الذي تجده هنا، لكن في الواقع الجزء الثاني يتضمن كل المعلومات المطلوبة ولا تحتاج لقراءة الجزء الأول لتفهمه.
• مسألة الـACM نفسها هنا

 ما المطلوب من المسألة؟ كتابة برنامج به وصف لمجموعة من المبان، وحذف الخطوط المتقاطعة بحيث يظهر فقط المحيط العام لتلك المبان، كما توضح الصورة:

كيف نحل هذه المسألة؟ من حسن الحظ أن شرح السؤال نفسه يلمح لنا بالحل!

The skyline vector should represent the "path" taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline.

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

في البداية ستسير النملة أفقياً حتى تصطدم بجدار بمبنى:

فإن وجدت المبنى ستبدأ في التحرك رأسياً لتتسلقه

إن وجدت نفسها عند سفح مبنى من جديد، فستبدأ في تسلقه، وإن وجدت نفسها عند هضبة فستنزل

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

وكيف تنتقل بين الحالات؟

إن كانت واقفة على الأرض:

• تسير إلى سفح أول مبنى أمامها

إن كانت واقفة على سطح مبنى:

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

إن كانت عند سفح:

• تصعد لأعلى المبنى، ثم تكون حالتها "على سطح مبنى"

إن كانت عند هضبة:

• إن كان هناك سطح مبنى يعوق هبوطها، تنزل إلى سطح ذلك المبنى ثم تصبح حالتها "على سطح مبنى"
• إن لم يكن هناك عائق تنزل إلى الأرض (ص = 0) وتصبح حالتها "على الأرض"

الملخص:

لم يبق سوى كتابة الكود التي تمثل هذا الرسم، ثم نستطيع جميعنا أن نعود إلى البيت ونأكل الساندوتشات التي أعدتها أمهاتنا :)


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

الآن إلى الكوووود!!


كما نعلم، مجموعة البيانات المدخلة هي مصفوفة من ثلاثيات، مثل [[12، 10، 20]، [15، 8، 22]، [20، 12، 30]]، وكل ثلاثية تعبر عن مبنى [الحافة اليسرى، الارتفاع، الحافة اليمنى]. فلنبدأ بشيء بسيط: دوال قصيرة لاستخراج بيانات كل مبنى مما يجعل البرنامج أسهل في القراءة:

دالة يسار ( مبنى ) :
    ارجع ب: مبنى [ 1 ] 
نهاية 

دالة سطح ( مبنى ) :
    ارجع ب: مبنى [ 2 ] 
نهاية 

دالة يمين ( مبنى ) :
    ارجع ب: مبنى [ 3 ] 
نهاية

الآن نرى الإجراء الأساسي لحل المسألة:

بداية.البحث مشترك 

إجراء إجابة ( صف.المباني ) :
    بداية.البحث = 1 
    على.الأرض ( 0 ، 0 ، صف.المباني ) 
نهاية 

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

ماذا أخذ الإجراء على.الأرض؟ أخذ قيم س، ص، ومصفوفة المباني.

جميل جداً. الآن ننظر للإجراء نفسه:

إجراء على.الأرض(س ، ص ، المباني) :
 

 لكل أ من بداية.البحث إلى عدد(المباني) :
        إذا يسار(المباني [أ]) > س :
            س = يسار(المباني[أ]) 
            اطبع س 
            حدث.بداية.البحث(س، المباني) 
            وكل إلى عند.سفح(س، ص، المباني[أ] ، المباني) 
        تم 
    تابع 
         -- إن وصل التنفيذ هنا فمعنى ذلك
         -- أن النملة على الأرض ولا يوجد
         -- مبان على يمينها: أي أن الرحلة
         -- قد انتهت
 نهاية

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

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

الآن نرى عند.سفح:

إجراء عند.سفح ( س ، ص ، مبنى ، المباني ) :

    ص = سطح ( مبنى ) 
    اطبع ص 
    وكل إلى عند.سطح ( س ، ص ، مبنى ، المباني ) 
نهاية 

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

سهلة دي مش كدة؟

إجراء عند.سطح(س، ص، مبنى، المباني) :

 لكل أ من بداية.البحث إلى عدد(المباني) :
        م = المباني [أ] 
         -- لو وجدنا مبنى خارجاً تماماً عن حدود المبنى الحالي،
         -- فكل المباني التي تليه هي الأخرى خارجة عن الحدود
         -- وبالتالي لا داع للاستمرار في البحث
        إذا يسار(م) > يمين(مبنى) : اذهب إلى نهاية.البحث 
 

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

لا تنزعج! الكود أبسط مما يبدو عليها. هي ببساطة تقوم بالآتي:
1- نفذ لكل مبنى م في المباني التي على يمين النملة:

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

2- لو انتهت الحلقة ولم نجد عقبة، إذاً فنحن على سطح مبنى بلا عقبات. هيا نسير إلى نهاية السطح (نغير س ونطبعها)، ثم ننتقل إلى حالة عند.هضبة

لو كنت لاتزال تجد صعوبة، انظر إلى الصور مرة أخرى.

الآن نصل إلى عند.هضبة:

إجراء عند.هضبة(س، ص، مبنى، المباني) :

 أعلى.عقبة = لاشيء 
    لكل أ من 1 إلى عدد(المباني) :
        م = المباني[أ] 
        إذا م <> مبنى وأيضا يمين(م) > س وأيضا يسار(م) < س :
             -- لقد وجدنا مبنى يقطع مبنانا
             -- وهو بالتأكيد ليس أعلى منه لأنه لو كان أعلى
             -- لكنا عليه بدلا من المبنى الحالي
 
             -- لو كنا مازلنا في بداية البحث، نعطي
             -- قيمة مبدئية للمتغير أعلى.عقبة
            إذا أعلى.عقبة = لاشيء :
                أعلى.عقبة = م 
            تم 
             
             -- سوف نختار أعلى مبنى فيهم لنهبط إليه
            إذا سطح(م) > سطح(أعلى.عقبة):
                أعلى.عقبة = م

            تم 
        تم 
    تابع 

    إذا أعلى.عقبة = لاشيء :
        ص = 0 
        اطبع ص 
        وكل إلى على.الأرض(س، ص، المباني) 
    وإلا :
        ص = سطح(أعلى.عقبة) 
        اطبع ص 
        وكل إلى عند.سطح(س، ص، أعلى.عقبة، المباني) 
    تم 
نهاية

مرة أخرى: الأمر أبسط مما يبدو عليه. الدالة جزءان:

الجزء الأول بين "لكل...تابع" يبحث عن أعلى مبنى يحتوي النقطة س التي تقف فيها النملة (يمينه أكبر من س ويساره اقل منها). لأن هذا الشرط ينطبق على المبني الحالي الذي تقف النملة عليه؛ لابد أن نضع جزءاً من الشرط يتأكد أن م هو مبنى مختلف عن المبنى الحالي.

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

• خارج الـloop، يجعل قيمة المتغير أعلى.عقبة تساوي لاشيء.
• داخل الـloop، يعطي هذا المتغير قيمة أولية هي أول مبنى يصلح يجده، وذلك عن طريق الشرط إذا أعلى.عقبة = لاشيء :... هذا الجزء يتم تنفيذه مرة واحدة فقط.
• داخل الـloop أيضاً، يتم كل مرة مقارنة م بأعلى عقبة، لحساب قيمة max في المتغير أعلى.عقبة بالطريقة المعروفة.

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

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

أخيراً هذا هو الإجراء حدث.بداية.البحث

إجراء حدث.بداية.البحث (س، المباني) :
    
    لكل أ من بداية.البحث إلى عدد( المباني ) :
        إذا يسار (المباني [أ]) > س :
            بداية.البحث = أ 
            اذهب إلى النهاية 
        تم 
    تابع 
    علامة النهاية 
نهاية

الإجراء يستخدم القيمة القديمة لـ بداية.البحث، حتى يجد أول مبنى على يمين النملة (يمينه أكبر من س)، وهنا يسجل رقم ذلك المبنى في بداية.البحث ويخرج.

هل يعمل البرنامج؟ القيم المطبوعة هي نفس النتيجة المكتوبة في موقع المسألة (ولكني لم أختبره على مدخلات أخرى)

يمكنك أن تختبره أنت إن أردت! الكود كاملةً تجدها هنا:

-- هذا البرنامج حل لمسألة Skyline problem من مسائل الـACM
 -- تجد المسألة هنا: http://uva.onlinejudge.org/external/1/105.html
 
-- اختبارات()
 حل.المسألة ( ) 

إجراء حل.المسألة ( ) :
    صف.المباني = [ ] 
    ملف.المدخلات = افتح.ملف ( "input.txt" ) 
    كرر مادام ليس ملف.المدخلات : منته ( ) :
        س = ملف.المدخلات : اقرأ.سطر ( ) 
        الثلاثية = تفصيص ( س ، " " ) 
        الثلاثية [ 1 ] = كعدد ( الثلاثية [ 1 ] ) 
        الثلاثية [ 2 ] = كعدد ( الثلاثية [ 2 ] ) 
        الثلاثية [ 3 ] = كعدد ( الثلاثية [ 3 ] ) 
        صف.المباني = صف.المباني + [ الثلاثية ] 
    تابع 
    اغلق.ملف ( ملف.المدخلات ) 
    إجابة ( صف.المباني ) 
نهاية 


بداية.البحث مشترك 

إجراء إجابة ( صف.المباني ) :
    بداية.البحث = 1 
    على.الأرض ( 0 ، 0 ، صف.المباني ) 
نهاية 


بداية.البحث مشترك 
إجراء على.الأرض ( س ، ص ، المباني ) :

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

 ص = سطح ( مبنى ) 
    اطبع ص 
    وكل إلى عند.سطح ( س ، ص ، مبنى ، المباني ) 
نهاية 

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

إجراء عند.هضبة ( س ، ص ، مبنى ، المباني ) :

    أعلى.عقبة = لاشيء 
    لكل أ من 1 إلى عدد ( المباني ) :
        م = المباني [ أ ] 
        إذا م <> مبنى وأيضا يمين ( م ) > س وأيضا يسار ( م ) < س :
             -- لقد وجدنا مبنى مختلف يقطع مبنانا
             -- وهو بالتأكيد ليس أعلى منه لأنه لو كان أعلى
             -- لكنا عليه بدلا من المبنى الحالي
 
             -- لو كنا مازلنا في بداية البحث، نعطي
             -- قيمة مبدئية للمتغير أعلى.عقبة
             إذا أعلى.عقبة = لاشيء :
                أعلى.عقبة = م 
            تم 
            عقبة2 = م 
             -- سوف نختار أعلى مبنى فيهم لنهبط إليه
            إذا سطح ( عقبة2 ) > سطح ( أعلى.عقبة ) :
                أعلى.عقبة = عقبة2 
            تم 
        تم 
    تابع 
    إذا أعلى.عقبة = لاشيء :
        ص = 0 
        اطبع ص 
        وكل إلى على.الأرض ( س ، ص ، المباني ) 
    وإلا :
        ص = سطح ( أعلى.عقبة ) 
        اطبع ص 
        وكل إلى عند.سطح ( س ، ص ، أعلى.عقبة ، المباني ) 
    تم 
نهاية 

إجراء حدث.بداية.البحث ( س ، المباني ) :
    
    لكل أ من بداية.البحث إلى عدد ( المباني ) :
        إذا يسار ( المباني [ أ ] ) > س :
            بداية.البحث = أ 
            اذهب إلى النهاية 
        تم 
    تابع 
    علامة النهاية 
نهاية 


دالة يسار ( مبنى ) :
    ارجع ب: مبنى [ 1 ] 
نهاية 

دالة سطح ( مبنى ) :
    ارجع ب: مبنى [ 2 ] 
نهاية 

دالة يمين ( مبنى ) :
    ارجع ب: مبنى [ 3 ] 
نهاية

خطط وأهداف(3): صنع المعنى

أريد أن أفتح شركة وأسميها Makesense. ما الهدف منها؟ تحويل الـcomputer science إلى أرباح.

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

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

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

كيف أريدها أن تكون؟ أريدها أن تكون حرة. أريدها أن تكون غنية. أريدها أن تكون إنسانية. أريد فيها علم مستشري. وأريدها أيضاً عملية وواقعية.

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

المكاتب لديهم هناك على عجلات، لكي تدفع مكتبك إلى الفريق الذي تريد أن تعمل فيه.

غنية أي لا يكون العمل فيها من نوع واحد أو على رتيبة واحدة؛ هناك فريق يعمل في البحث واسترجاع البيانات، فريق في تطوير الأدوات البرمجة، فريق في الرؤية بالكمبوتر - ربما تصنيف عينات النباتات بالكاميرا - فريق يبتكر نوعاً جديداً من الألعاب. فريق في الروبوت..

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

ومن يدري؟ ربما يكون هناك فريق أو أكثر يعمل في جهاز أوراق...

إنسانية يعني لا نريد لنظام الشركة أن يفضل المؤسسة على الإنسان. هل أنت موهوب لكن لديك مشاكل صحية؟ أو مشاكل في النوم؟ أو تريد وقتاً اكثر لأسرتك وأولادك؟ تحدث معنا! ربما يكون هناك فرصة لكي نكيف لك بيئة عمل مناسبة، نستفيد من مواهبك وحبك للبرمجة وفي نفس الوقت لا نضغط عليك أو نلزمك بما لا تطيق.

وربما يمكن عمل طريقة اكثر ديموقراطية لإدارة الشركة. أوهل يمكن تطبيق شيء مثل الديموقراطية التشاركية أو التخطيط بالمشاركة؟ لماذا لا يحدد العاملون انفسهم كيف يراد أن تدار الشركة التي يعملون فيها؟

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

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

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

لا اقول انني قد وضعت خطة محكمة في اللحظة الحالية (هذه الأمور تأتي بالممارسة والتجربة والتطوير المستمر)، لكن هناك نقاط مهمة للبدء:

- لابد من حسن اختيار الموظفين جدا، ولابد أن تشارك الشركة كلها في عملية التعيين: المبرمج هو الذي يقوم بالinterview للمبرمج، وهذه مسؤولية لا تقل أهمية عن كتابة الكود (بل هي اعلى رتبة منها). لمزيد من التفاصيل ارسلك لمقال هو من افضل مقالات إدارة الشركات التي قرأتها في حياتي: Engineering management at Facebook

أيضاً عند تعيين شخص فإن الإنترفيو لن تكون فقط لقدراته البرمجية، كما يقولون في شركة Valve:

Do not interview only technical skills, check if the candidate is able to run a company, because he will be

- لابد من طرق للتقييم والتقويم.

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

شيء أخير: شركة مايكروسوفت تسمي طاقمها Microsofties، وشركة جوجل تسميهم Googlers، فماذا نسمي طاقمنا نحن؟ ماذا عن Sense Makers؟ :)

ألا تريد أن تكون جزءاً من الحلم؟

أهمية علم لغات البرمجة

My area of interest is programming language theory (PLT). This is an area separate from compilers, but related.

It discusses things like programming paradigms (imperative, logic, functional, object oriented,...), language semantics, type systems, programming language features, and other things.

The problem is; most programmers think 'languages' are a solved problem. They think that the best possible languages are the familiar ones like C++ or Java, and that effort should now focus on e.g the libraries. That is completely not true!

So, let's discuss some lesser-known languages and how they offer completely new ways to programming.

There is a new language called OPA - derived from the ML family - that makes web application development significantly faster. Projects that take months to develop can be made in OPA in weeks.

A large part of the power of this language comes from its type system, Which lets you describe only once the shape of your data and then generates client-side (running on the web browser) and server-side code from the same description, thus eliminating many causes for error.

Or how about Google's Go language, which focuses on speed of compilation, safety, simplicity and concurrency?

Then we have Subtext, a language (part of a series) that attempts to simplify the reading and understanding of programs?

Or Lisp, where you can define new syntax for the language, having components written with "mini-languages" inside a larger program?

Or...we know that C is fast and powerful, but very unsafe and hard-to-debug. How about a language that has the same speed and low level capabilities, but much more safe and expressive? Enter BitC.

Speaking of low-level; Mozilla (the creators of Firefox) are working on a new language for systems programming called Rust. It should be useful for the same type of programs that are written in C++ but with features like this (from their site):

• Memory safe. No null pointers, wild pointers, etc. Automatic storage management.
• Dynamic execution safety: task failure / unwinding, trapping, logging.RAII / dtors.
• Typestate system: ability to define complex invariants that hold over data structures.
• Very lightweight tasks (coroutines). Cheap to spawn thousands-to-millions.

Finally, how about F# from Microsoft, a functional programming language that is now part of Visual Studio, described on its site as "...It is a simple and pragmatic language, and has particular strengths in data-oriented programming, parallel I/O programming, parallel CPU programming, scripting and algorithmic development"

In summary, programming language theory is not simply about academic research: real companies like Google, Mozilla, and Microsoft are working on serious projects that help them in making money or beating their competition.

I think this field is very worthy of study, even if so few people pay attention to it...

فيديو: مواد كلية الحاسبات وأهميتها - حاسبات عين شمس نموذجاً

لا يتعدى هذا الفيديو 35 دقيقة لكنه غني جداً بالمعلومات عن المواد وأهميتها علمياً وبرمجياً وفي سوق العمل. قدمته في الكلية منذ فترة قريبة والآن هو على الإنترنت للجميع. مشاهدة ممتعة!

الslides المقدمة في الفيديو تجدها هنا

(لو أعجبك هذا البوست فقد يعجبك أيضاً هذا: حاسبات للقرن الواحد والعشرين)

Computer Science and great products

Do you need a good knowledge of computer science to make a great product? It certainly depends on what you're trying to do, but an important point is that the more CS you know the more enabled you are to make useful and impressive software.

The rest of this blog post is a case study in how CS is being used to shape my homegrown programming language for children, كلمات.

First the obvious: It would not have been made without knowledge of compilers. We got that out of the way.

Another thing is that it runs on a small virtual machine called (appropriately) SmallVM. Basically it's a program that reads assembly-like instructions and executes them. Do you know the "basic computer assembler/emulator" sometimes given in computer architecture courses? It's like the big brother of that :)

SmallVM doesn't just run instructions though; it also knows about classes and objects and has a garbage collector. That means it required knowledge about language runtimes in general.

Notice that currently the language runs programs at an acceptable speed. If I want programs to run really fast I need to go deeper: Compiler optimizations, better garbage collection, and perhaps modern VM tricks like polymorphic inline caches.

Do you know that with these techniques a language like Java or C# can reach performance comparable to C++? I hope that I or someone after me learns from those techniques and further improves on Kalimat/SmallVM.

All of this has been about the current version of the language, what about future versions? Here are some ideas I'm thinking about and how computer science can help...

Future idea #1: Gradual typing.

Currently Kalimat is dynamically typed. This means that a variable can take values of any type in the language, and obviously there are no type declarations. This is an example of a program that uses dynamic typing:

Notice how (a) There are no type declarations for the parameters or return value and (b) The program accepts any array of objects as long as each object has a method called نتيجته.

Now I've been thinking: If a child learns my language and afterwards wants to "graduate" into something like C++ ...etc then type declarations and static typing would be new to him or her, but on the other hand if I change Kalimat to require type declarations then it will be harder to teach it to children since the program will require type declarations everywhere, and those will (a) Need explaining (b) Need more syntax memorization and (c) Distract from the actual programming ideas like loops...etc

So the solution? Gradual typing! It means that the language is dynamically typed as usual but with optional static typing. When you declare the type of a variable the compiler will enforce it; otherwise the variable is dynamically typed.

If I decide to implement this feature, I imagine a future version of Kalimat where children would learn programming without being confused by types, and then at some future learning stage they would be introduced to type declarations, watch how the language checks for type errors, and see autocomplete at work!

Future idea #2: GUI programming.

Kalimat currently supports simple graphics like lines and rectangles, but in a future version I hope it supports GUI elements like Forms, Buttons, Textboxes...etc

It would be possible to copy the current event handling models of e.g C#, but I want to take seriously the idea of "a children's programming language". GUI programming is sometimes confusing even for college students! If there's a model that can make it simpler then I should do what I can to seek and use that model.

Again, computer science comes to help! There is a model for parallel programming called CSP, or Communicating Sequential Processes. It started from work by Tony Hoare (the same guy who invented quicksort) and it lead to many implementations and languages. It is also related to the actor model used in languages like Erlang.

So, a couple of days ago I read a paper about how to use CSP to greatly simplify GUI programming. To understand how this works I need to explain a little about the CSP model. Also my explanation is not 100% correspondent to the content of the paper (the idea was further developed in future papers, the paper itself is not current. Also my explanation is simplified).

Imagine that a program is composed of several processes that run independently. To communicate with each other they use a special type of object called a channel. There are two operations associated with a channel:

1- x = receive(ch) ; Which waits until data is available on the channel then returns it in x.

2- send(x, ch); Which waits until some process is ready to receive from the channel and then sends the data in x.

There is also a special command, spawn(p1, p2,...) that launches several processes in parallel.

Now we can talk about GUIs. Suppose we have a graphics application that can be used to draw lines and triangles. If we can assign a channel to each event then we can do this:

Finally we will launch both processes in the main function:


To implement something like this in a traditional GUI library you would need a lot of code in several places. If you studied design patterns you could use the state pattern, for example, to organize your code. But with CSP you write GUI code the same way you think about it. To draw a line you receive two points and join them together. Simple as that.

Now imagine if all this was part of Kalimat.. it would be an Arabic children's programming language that has an easier GUI library than the default library of most modern professional languages!

We need a lot of computer science to implement such a feature. How will we run the processes? Do we use multi-threading and rely on the operating system to schedule the work; or do we modify SmallVM to make it run several processes concurrently and write our own scheduler? Does that mean we will need to revisit what we learned in the operating systems course? :D

Finally

What I want to say in this article is...I'm grateful for all what I've learned in FCIS, without which I wouldn't have been the programmer I am today, that's one thing.

The other thing, and this is important, is that it took me a lot of years learning computer science topics to know all of this. It doesn't have to be about programming languages: Any CS topic; be it operating systems, computer vision, AI, or anything else can open the doors to great products. Products you can use to make money, or improve society, or move science further. But it will take years of hard work and learning.

Why not start now?