سلسلة المخرج

في الرياضيات ، وتحديدًا في مجال حساب التفاضل والتكامل اللامدا ، تُعدّ الموجهات أو سلاسل الموجهات آليةً لتتبع المتغيرات الحرة في الحدّ . وبشكلٍ عام، يمكن فهمها كنوعٍ من التخزين المؤقت للمتغيرات الحرة؛ أي كتقنيةٍ لتحسين تحديد مواقع المتغيرات الحرة بسرعة في جبر الحدّ أو في تعبير لامدا. وقد قدّم كيناواي وسليب سلاسل الموجهات عام 1982، ثمّ طوّرها سينوت وفرنانديز وماكي ^{[ 1 ]} كآليةٍ لفهم تكلفة التعقيد الحسابي لاختزال بيتا والتحكّم بها .

في عملية اختزال بيتا، يتم تعريف قيمة التعبير الموجود على اليسار على أنها تلك الموجودة على اليمين:

${\displaystyle (\lambda xE)y\equiv E[x:=y]\,}$أو${\displaystyle (\lambda xE)y\equiv E[y/x]}$ (استبدل جميع قيم x في E (الجسم) بـ y )

على الرغم من بساطة هذه العملية من الناحية النظرية، إلا أن تعقيدها الحسابي قد يكون كبيرًا: إذ تقوم خوارزمية بسيطة بفحص التعبير E بحثًا عن جميع مواضع المتغير الحر x . ومن الواضح أن هذه الخوارزمية من رتبة O ( n ) بالنسبة لطول التعبير E. لذا، يُصبح من الضروري تتبع مواضع المتغيرات الحرة في التعبير. يمكن محاولة تتبع موضع كل متغير حر، أينما وُجد في التعبير، لكن هذا قد يُصبح مكلفًا للغاية من حيث التخزين؛ علاوة على ذلك، فإنه يُوفر مستوى تفصيل غير ضروري. تشير سلاسل التوجيه إلى أن النموذج الأمثل هو تتبع المتغيرات الحرة بشكل هرمي، من خلال تتبع استخدامها في المصطلحات المكونة.

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

${\displaystyle t::=f(t_{1},t_{2},\dots ,t_{n})}$

حيث f دالة من الرتبة n ، بدون متغيرات حرة ، و${\displaystyle t_{i}}$هي مصطلحات قد تحتوي أو لا تحتوي على متغيرات حرة. لنرمز بـ V إلى مجموعة جميع المتغيرات الحرة التي قد تظهر في مجموعة جميع المصطلحات. يكون الموجه حينها هو الخريطة

${\displaystyle \sigma _{t}:V\to P(\lbrace 1,2,\dots ,n\rbrace )}$

من المتغيرات الحرة إلى مجموعة القوى${\displaystyle P(X)}$من المجموعة${\displaystyle X=\lbrace 1,2,\dots ,n\rbrace }$القيم التي يأخذها${\displaystyle \sigma _{t}}$هي ببساطة قائمة بمؤشرات${\displaystyle t_{i}}$حيث يظهر متغير حر معين. على سبيل المثال، إذا كان المتغير الحر${\displaystyle x\in V}$يحدث في${\displaystyle t_{3}}$و${\displaystyle t_{5}}$ولكن ليس بأي حال من الأحوال، عندها يكون المرء قد حصل على${\displaystyle \sigma _{t}(x)=\lbrace 3,5\rbrace }$.

وبالتالي، لكل مصطلح${\displaystyle t\in T}$في مجموعة جميع الحدود T ، يتم الاحتفاظ بدالة${\displaystyle \sigma _{t}}$وبدلاً من العمل فقط مع الحدود t ، يتم العمل مع الأزواج.${\displaystyle (t,\sigma _{t})}$وبالتالي، يتم استبدال التعقيد الزمني لإيجاد المتغيرات الحرة في t بالتعقيد المكاني للحفاظ على قائمة بالمصطلحات التي يظهر فيها متغير ما.

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

• نظام إعادة كتابة المصطلحات
• استبدال صريح
• التخزين المؤقت

• ف. ر. سينوت. " إعادة النظر في سلاسل التوجيه: نهج عام للتمثيل الفعال للمتغيرات الحرة في إعادة الكتابة من الرتبة العليا. " مجلة المنطق والحوسبة 15 (2)، الصفحات 201-218، 2005.