في حين أن اللغة

Question

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

لأولئك منكم الذين يمكن أن نفهم قواعد اللغة هنا هي لغة قواعد:

S -> S;S | while C do S od | id := E

E -> E + T | T | E - T

T -> T * F | F | F / T

F -> id | cons | (E)

C -> E = E | E > E | E < E | E >= E | E <= E | E != E | C and C | C or C | not(C)

هذا نسخ من صفي الملاحظات ، لذلك لا ألوم لي إذا كان هناك شيء مفقود أو غير صحيحة!

قطعة من التعليمات البرمجية لتنفيذ هذا:

if d = 0 do
    x := 1
else
    x := a / d

على أي حال, إذا كنت ترغب في المضي قدما لكتابة هذا باستخدام لغة القواعد المذكورة أعلاه ، والمضي قدما.وإلا استمر في الكتابة في أي لغة كنت أكثر راحة في.ولكن هناك بعض المحاذير!

• لا إذا كانت البيانات أو أي نوع آخر من التحكم في التدفق الأخرى من حين الحلقات.
• لا الغش:النحوي أعلاه لا تشمل أي كسر بيانات عودة البيانات ، أو استثناءات.لا تستخدم لهم.

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

Answer 1

هنا هو بلدي رمز:

continue := True
while d = 0 and continue do
    x := 1
    continue := False
od
while d != 0 and continue do
    x := a/d
    continue := False
od

Answer 2

فإنه يمكن القيام به مع واحد في حين حلقة ، ولكن ليس هذا واضح:

while d == 0 do
  d := 1;
  a := 1
od
x := a / d;

شرح, إذا كان d = 0 ، ثم د 1, أيضا سوف يكون 1.بهذا تنتهي الحلقة.

الآن x هو a / d ... وهذا أمر جيد لأنه إذا د 0 ، a / d يقيم إلى 1.

Answer 3

سيكون هذا العمل ؟

td := d
x := 1

while td != 0 do
    x := a / d
    td := 0
od

Answer 4

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

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

Answer 5

دون استخدام تفاصيل صحيحة أو خاطئة الفروع ، دون تكرار المسند:

statementIncomplete := True
while d = 0 and statementIncomplete do
    x := 1
    statementIncomplete := False
od
while statementIncomplete do
    x := a/d
    statementIncomplete := False
od

Answer 6

هذا هو التوسع إيمون الجواب.

دلالات if <condition> then <stmt> else <stmt> fi هو ما يلي:

• تقييم <condition>;
• إذا كان ذلك صحيحا ، تنفيذ بيان بين then و else;
• وإلا تنفيذ العبارة بين else و fi.

دلالات while <condition> do <stmt> od هو ما يلي:

• تقييم <condition>;
• إذا كانت كاذبة ، while بيان يتم التنفيذ ؛
• وإلا تنفيذ العبارة بين do و od, و تنفيذ while البيان مرة أخرى.

للتعبير عن if A then B else C حيث while, إجراء التحول التالية:

السماح gensymN يكون اسم لا تستخدم أي متغير ؛ ثم تنبعث منها البرمجية التالية

gensymN := 0;
while gensymN = 0 and A do B; gensymN = 1; od;
while gensymN = 0 do C; gensymN = 1; od

دلالات هذا البرنامج هو:

• تعيين إلى 0 gensymN.
• تقييم gensymN = 0 and A (صحيح المنتدى A هو صحيح)
• إذا كان هذا صحيحا ، ثم:
  • تنفيذ B
  • تنفيذ gensymN = 1
  • تقييم gensymN = 0 and A (انها كاذبة)
  • تقييم gensymN = 0 (انها كاذبة)
• آخر (إذا gensymN = 0 and A كانت كاذبة):
  • تقييم gensymN = 0 (صحيح)
  • تنفيذ C
  • تنفيذ gensymN := 1
  • تقييم gensymN = 0 (انها كاذبة)

مراعاة ما يلي البنى التحتية المذكورة أعلاه:

• أنه (فعال) يقيم A;
• إذا كان هذا صحيحا ، فإنه ينفذ B, وإلا C.
• وبصرف النظر عن A, B و C, البرنامج (جزء) فقط يعبث gensymN, التي ليست موجودة في مدخلات البرنامج.

وبالتالي هذا البرنامج له نفس دلالات كما

if A then B else C fi; gensymN := 1

حاشية واحدة:إذا A هو صحيح عند تقييمها ، سيتم تقييمها مرة أخرى (إلا إذا and قصيرة-الدائرة).إذا كانت اللغة تسمح بتخزين القيم المنطقية في المتغيرات ، يمكن للمرء أن أقدم أحد أكثر زائف متغير و لا dummy := A; <insert the above program here, with dummy instead of A>.ثم اثنين التقييمات dummy هي في الأساس مجرد الحمل.إذا كان تقييم التعبيرات المنطقية لا يمكن أن يكون لها آثار جانبية ، ومنع التقييم الثاني ليس من الضروري صحة;قد يكون (أو لا) يكون الأمثل.

اتخاذ أعلاه كما الناعمة "البرهان" ، مع لشروط الفقرة السابقة ، أن هذا هو الصحيح تماما العامة ترجمة if إلى while.كامل عمومية يحدد هذا (= إيمون) في الجواب بعيدا عن الآخرين من وجهة نظري.