LOOP (programlama dili) - LOOP (programming language) - Wikipedia

DÖNGÜ tam olarak yakalayan bir dildir ilkel özyinelemeli fonksiyonlar.[1]Dilde desteklenen işlemler yalnızca atama, toplama ve döngü yürütme başlamadan önce sabit olan birkaç kez döngüdür.

LOOP dili, 1967 tarihli bir makalede, Albert R. Meyer ve Dennis M. Ritchie. [2]Meyer ve Ritchie, LOOP dili ile LOOP arasındaki yazışmayı gösterdi. ilkel özyinelemeli fonksiyonlar.

Dennis M. Ritchie, aynı zamanda yayınlanmamış doktorasının da konusu olan LOOP dilini formüle etti. tez.[3][4]

Tarafından da sunuldu Uwe Schöning, ile birlikte GİT ve SÜRE.[5]

Özellikleri

Her biri ilkel özyinelemeli işlev LOOP hesaplanabilir ve bunun tersi de geçerlidir.[6]

Kıyasla GİT programlar ve SÜRE programlar, LOOP programları her zaman bitirmek.[7] Bu nedenle, LOOP programları tarafından hesaplanabilen işlevler kümesi, uygun bir alt kümedir. hesaplanabilir işlevler (ve böylelikle WHILE ve GOTO program fonksiyonları ile hesaplanabilenin bir alt kümesi).[8]

DÖNGÜ hesaplanabilir olmayan toplam hesaplanabilir fonksiyonun bir örneği, Ackermann işlevi.[9]

Resmi tanımlama

Sözdizimi

DÖNGÜ programları sembollerden oluşur DÖNGÜ, YAPMAK, SON, :=, +, - ve ; yanı sıra herhangi bir sayıda değişken ve sabit. DÖNGÜ programları aşağıdakilere sahiptir sözdizimi değiştirilmiş Backus-Naur formu:

Buraya, değişken isimlerdir ve sabitler.

Anlambilim

Eğer P bir LOOP programıdır, P bir işleve eşdeğerdir . Değişkenler vasıtasıyla bir LOOP programında, fonksiyonun argümanlarına karşılık gelir , ve program yürütülmeden önce uygun değerlerle başlatılır. Diğer tüm değişkenlere sıfır başlangıç ​​değeri verilir. Değişken şu değere karşılık gelir bağımsız değişken değerleri verildiğinde alır vasıtasıyla .

Formun bir açıklaması

xben := 0

değişkenin değeri anlamına gelir 0 olarak ayarlanmıştır.


Formun bir açıklaması

xben : = xben + 1

değişkenin değeri anlamına gelir 1 artırılır.


Formun bir açıklaması

P1; P2

alt programların sıralı yürütülmesini temsil eder ve , bu sırayla.


Formun bir açıklaması

DÖNGÜ x DO P SON

kısmi programın tekrar tekrar yürütülmesi anlamına gelir toplamda zamanlar, nerede değer ifadenin çalıştırılmasının başında kullanılır. Bile değerini değiştirir kaç defa etkilemeyecek döngüde yürütülür. Eğer sıfır değerine sahipse içinde yürütülmez DÖNGÜ Beyan. Bu izin verir şubeler LOOP programlarında, kısmi bir programın koşullu yürütülmesi bir değişkenin sıfır veya bir değerine sahip olmasına bağlıdır.

Örnek programlar

Görev

Aşağıdaki LOOP programı x değişkeninin değerini atarben değişken x'ej.

xj : = 0; DÖNGÜ xben DO xj : = xj + 1END

Yeni ufuklar açan makalelerinde [10] Meyer & Ritchie atamayı yaptı temel bir ifade. Yukarıdaki programın gösterdiği gibi, atama gereksizdir ve temel ifadeler listesinden çıkarılabilir. Diğer LOOP programlarında bir alt program olarak kullanılabilir. LOOP sözdizimi, yukarıdakileri bir alt yordam olarak çağırmaya eşdeğer olan aşağıdaki ifadeyle genişletilebilir:

xj : = xben

Açıklama: Tüm değişkenlerin küresel olduğu unutulmamalıdır. Yeni ifadenin bir alt rutine eşdeğer olduğu olduğu anlamına gelmez bir alt program. Normalde bir aktivasyon kaydı tüm yan etkileri önler. Ancak bu durumda x dışında başka bir değişken yokj etkilenir, bu nedenle x şartı ile yan etkiler meydana gelmezjprogramın çalıştırılmasının bu noktasında sıfır olmayan bir değer içerebilecek olan, 0 olarak başlatılır.

Projeksiyon

Atama programının özel bir durumu programdır (genişletilmiş gösterimi kullanıyoruz):

x0 : = xben

Bu program k-ary projeksiyon fonksiyonunu hesaplar , sıralı bir k-tuple'dan i'inci koordinatı çıkarır.

Selef

Önceki işlev şu şekilde tanımlanır:

.

Bu fonksiyon, değişkeni ayarlayan aşağıdaki LOOP programı ile hesaplanabilir. -e .

/ * ön koşul: x2 = 0 * / DÖNGÜ x1 DO x0 : = 0; DÖNGÜ x2 DO x0 : = x0 + 1 SON; x2 : = x2 + 1END

Bu program, diğer LOOP programlarında bir alt program olarak kullanılabilir. LOOP sözdizimi, yukarıdakileri bir alt yordam olarak çağırmaya eşdeğer olan aşağıdaki ifadeyle genişletilebilir:

x0 : = x1 ∸ 1

Açıklama: Yine yan etkilere dikkat edilmelidir. Önceki program x değişkenini değiştirir2, başka bir yerde kullanılıyor olabilir. X ifadesini genişletmek için0 : = x1 ∸ 1, x değişkenleri ilklendirilebilirn, xn + 1 ve xn + 2 (yeterince büyük bir n için) 0'a, x1 ve 0 ise, kodu bu değişkenler üzerinde çalıştırın ve sonucu kopyalayın (xn) x'e0. Bir derleyici bunu yapabilir.

İlave

Aşağıdaki programda değişken değişkenlerin toplamına ayarlanır ve .

DÖNGÜ x1 DO x0 : = x0 + 1END; DÖNGÜ x2 DO x0 : = x0 + 1END

Bu program, diğer LOOP programlarında bir alt program olarak kullanılabilir. LOOP sözdizimi, yukarıdakileri bir alt yordam olarak çağırmaya eşdeğer olan aşağıdaki ifadeyle genişletilebilir:

x0 : = x1 + x2

Kesme çıkarma

İkinci döngünün üzerindeki 'toplama' programında ise x0 Artırmak yerine, program değişkenlerin farkını (0'da kesilir) hesaplar ve .

x0 : = x1DÖNGÜ x2 DO x0 : = x0 ∸ 1END

Daha önce olduğu gibi, LOOP sözdizimini şu ifadeyle genişletebiliriz:

x0 : = x1 ∸ x2

Çarpma işlemi

Aşağıdaki LOOP programı değişkenin değerini ayarlar değişkenlerin ürününe ve .

DÖNGÜ x1 DO x0 : = x0 + x2SON

Bu çarpma programı, önceki örnekteki toplama alt yordamı tarafından sunulan sözdizimini kullanır. Çarpma burada değeri eklenerek yapılır. toplamda kez, sonuçları kaydetme .

Eğer öyleyse

İf x ile bir if-then-else ifadesi1 > x2 sonra P1 yoksa P2:

xn1 : = x1 ∸ x2; xn2 : = 0; xn3 : = 1; DÖNGÜ xn1 DO xn2 : = 1; xn3 : = 0END; DÖNGÜ xn2 P1END YAPIN; DÖNGÜ xn3 P2END YAPIN;

Ayrıca bakınız

Notlar ve referanslar

  1. ^ Herbert Enderton (2012). Hesaplanabilirlik Teorisi. Akademik Basın.
  2. ^ Meyer, Albert R.; Ritchie, Dennis M. (1967). Döngü programlarının karmaşıklığı. ACM '67: 1967 22. ulusal konferansı tutanakları. doi:10.1145/800196.806014.
  3. ^ "Dennis Ritchie'nin Kayıp Tezini Keşfetmek". CHM. 2020-06-19. Alındı 2020-07-14.
  4. ^ "Program yapısı ve hesaplama karmaşıklığı taslağı | 102790971 | Bilgisayar Tarihi Müzesi". www.computerhistory.org. Alındı 2020-07-14.
  5. ^ Schöning, Uwe (2008). Teoretische Informatik-kurz gefasst (5 ed.). Londra: Oxford University Press. s. 105. ISBN  978-3-8274-1824-1. DNB 986529222.
  6. ^ Schöning, Uwe (2008). Teoretische Informatik-kurz gefasst (5 ed.). Londra: Oxford University Press. s. 105. ISBN  978-3-8274-1824-1. DNB 986529222.
  7. ^ Schöning, Uwe (2008). Teoretische Informatik-kurz gefasst (5 ed.). Londra: Oxford University Press. s. 93. ISBN  978-3-8274-1824-1. DNB 986529222.
  8. ^ Schöning, Uwe (2001). Teoretische Informatik-kurz gefasst (4 ed.). Londra: Oxford University Press. s. 122. ISBN  3-8274-1099-1.
  9. ^ Schöning, Uwe (2008). Teoretische Informatik-kurz gefasst (5 ed.). Londra: Oxford University Press. s. 112. ISBN  978-3-8274-1824-1. DNB 986529222.
  10. ^ Meyer & Ritchie: Döngü programlarının karmaşıklığı, ACM 1967

Dış bağlantılar