Janus (vaqtni qaytaradigan hisoblash dasturlash tili) - Janus (time-reversible computing programming language)

Yanus a vaqtni qaytarib beradigan da yozilgan dasturlash tili Caltech 1982 yilda.^[1] The operatsion semantika til bilan rasmiy ravishda ko'rsatilgan dastur inverteri va teskari o'z-o'zini tarjimon, 2007 yilda Tetsuo Yokoyama va Robert Glyuk tomonidan.^[2] Yanus invertori va tarjimoni TOPPS tadqiqot guruhi da DIKU.^[3] Boshqa bir Janus tarjimoni amalga oshirildi Prolog 2009 yilda.^[4] Quyida 2007 yilgi maqolada keltirilgan til qisqacha bayon qilinadi.

Janus - bu global do'konga ega bo'lgan majburiy dasturlash tili (bu erda hech qanday stek yoki uyni ajratish mavjud emas). Janus - bu qaytariladigan dasturlash tili, ya'ni u mahalliy inversiya bo'yicha deterministik oldinga va orqaga hisoblashni qo'llab-quvvatlaydi.

Sintaksis

Biz Yanus sintaksisini aniqlaymiz Backus-Naur shakli.

Janus dasturi bu bir yoki bir nechta o'zgaruvchan deklaratsiyalar ketma-ketligi bo'lib, undan keyin bir yoki bir nechta protsedura deklaratsiyalari ketma-ketligi:

<dastur> ::= <v-dekl> <v-dekls> <p-dekl> <p-parchalar><v-dekls> ::= <v-dekl> <v-dekls> | ""<p-parchalar> ::= <p-dekl> <p-parchalar> | ""

Eslatma, 2007 yilgi maqolada ko'rsatilgan Janus,^[2] nol yoki undan ortiq o'zgaruvchiga imkon beradi, lekin bo'sh do'kondan boshlanadigan dastur bo'sh do'konni ishlab chiqaradi. Hech narsa qilmaydigan dastur ahamiyatsiz ravishda o'zgartirilishi mumkin va amalda qiziq emas.

O'zgaruvchan deklaratsiya o'zgaruvchini yoki bir o'lchovli qatorni belgilaydi:

<v-dekl> ::= <v> | <v> "[" <v> "]"

E'tibor bering, o'zgaruvchan deklaratsiyalar hech qanday ma'lumotga ega emas. Buning sababi, Janusdagi barcha qiymatlar (va barcha konstantalar) manfiy bo'lmagan 32-bitli tamsayılar, shuning uchun barcha qiymatlar 0 dan 2 gacha³² - 1 = 4294967295. Shunga qaramay, Janus tarjimoni mezbonlik qilganiga e'tibor bering TOPPS muntazam foydalanadi ikkitasini to‘ldiruvchi 32-bitli tamsayılar, shuning uchun u erda barcha qiymatlar -2 orasida³¹ = -2147483648 va 2³¹ - 1 = 2147483647. Barcha o'zgaruvchilar 0 qiymatiga moslashtiriladi.

Massivlarning o'lchamlari uchun nazariy chegaralar yo'q, ammo aytilgan tarjimon kamida 1 o'lchamini talab qiladi.^[3]

Jarayon deklaratsiyasi kalit so'zdan iborat protsedura, undan keyin noyob protsedura identifikatori va bayonoti keltirilgan:

<p-dekl> ::= "protsedura" <id> <s>

Janus dasturining kirish nuqtasi - protsedura asosiy. Agar bunday protsedura mavjud bo'lmasa, dastur matnidagi so'nggi protsedura kirish nuqtasidir.

Bayonot - bu topshiriq, almashtirish, if-then-else, tsikl, protsedura chaqiruvi, protsedurani bekor qilish, o'tkazib yuborish yoki qatorlar qatori:

<s> := <x> <mod-op> "=" <e> | <x> "[" <e> "]" <mod-op> "=" <e>     | <x> "<=>" <x>     | "agar" <e> "keyin" <s> "boshqa" <s> "fi" <e>     | "dan" <e> "qil" <s> "pastadir" <s> "gacha" <e>     | "qo'ng'iroq" <id> | "qo'ng'iroq qilmaslik" <id>     | "o'tkazib yuborish" | <s> <s>

Topshiriqlar orqaga qaytarilishi uchun chap tomonidagi o'zgaruvchining topshiriqning ikki tomonidagi ifodalarda ko'rinmasligi talab qilinadi. (Eslatma, massiv katakchasini tayinlash topshiriqning ikkala tomonida ham ifodalangan.)

Almashish (<x> "<=>" <x>) ahamiyatsiz qaytariladigan.

Shartlarning qaytarilishi uchun biz ikkalasini ham ta'minlaymiz sinov (the <e> keyin "agar") va an tasdiqlash (the <e> keyin "fi"). Semantikasi bu sinov kerak keyin filialning bajarilishidan oldin ushlab turing va tasdiqlang kerak keyin ushlab turing. Aksincha, test kerak emas else-filial bajarilishidan oldin ushlab turing va tasdiqlang kerak emas keyin ushlab turing. Ters teskari dasturda tasdiq testga, test esa tasdiqga aylanadi. (Yanusdagi barcha qiymatlar tamsayı bo'lgani uchun, 0 qiymatini ko'rsatadigan odatiy C-semantika qo'llaniladi.)

Qaytadan aylantirilishi uchun biz ham xuddi shunday tasdiqlaymiz ( <e> keyin "dan") va sinov (the <e> keyin "gacha"). Semantika shundan iboratki, tasdiq tasdiqlanishi kerak faqat kirish paytida pastadirga va sinov o'tkazilishi kerak faqat chiqish paytida pastadirdan. Ters teskari dasturda tasdiq testga, test esa tasdiqga aylanadi. Qo'shimcha <e> keyin "pastadir" test noto'g'ri deb baholangandan keyin ishni bajarishga imkon beradi. Ish keyinchalik tasdiqning yolg'onligini ta'minlashi kerak.

Jarayon qo'ng'iroq qiling protsedura bayonotlarini oldinga yo'nalishda bajaradi. Jarayon chaqirilmaydi protsedura bayonotlarini orqaga qarab yo'naltiradi. Protseduralarda parametrlar mavjud emas, shuning uchun barcha o'zgaruvchan o'tish global do'konga yon ta'sirlar orqali amalga oshiriladi.

Ifoda - bu doimiy (butun son), o'zgaruvchi, indekslangan o'zgaruvchi yoki ikkilik amalning qo'llanilishi:

<e> ::= <v> | <x> | <x> "[" <e> "]" | <e> <bin-op> <e>

Yanusdagi doimiyliklar (va Janus tarjimoni mezbonlik qiladi TOPPS ) allaqachon yuqorida muhokama qilingan.

Ikkilik operator - bu C ning o'xshashlariga o'xshash semantikaga ega bo'lgan quyidagilardan biri:

<bin-op> ::= "+" | "-" | "^" | "*" | "/" | "%" | "&" | "|" | "&&" | "||" | ">" | "<" | "=" | "!=" | "<=" | ">="

O'zgartirish operatorlari ikkilik operatorlarning kichik to'plamidir, chunki ular barcha v, ${ displaystyle lambda v '. oplus chap (v', v o'ng)}$ bu ikki tomonlama funktsiya va shuning uchun teskari, bu erda ${ displaystyle oplus}$ modifikatsiya operatori:

<mod-op> ::= "+" | "-" | "^"

Teskari funktsiyalar "-", "+"va "^"navbati bilan.

Belgilangan o'zgaruvchining topshiriqning har ikki tomonidagi ifodada ko'rinmasligini cheklash, Yanusning xulosa tizimi oldinga va orqaga qarab deterministik ekanligini isbotlashga imkon beradi.

Misol

Biz Janus protsedurasini yozamiz fib topish n-chi Fibonachchi raqami, n> 2 uchun i = n, x1 = 1 va x2 = 1:

protsedura fib i = n do x1 + = x2 x1 <=> x2 i - = 1 dan i = 2 gacha

Tugatilgandan so'ng, x1 bo'ladi (n−1) - Fibonachchi raqami va x2 n^th Fibonachchi raqami. men n-dan 2-ga o'tadigan iterator o'zgaruvchisi. As men har bir iteratsiyada kamayadi, taxmin (i = n) faqat birinchi takrorlashdan oldin to'g'ri keladi. Sinov (i = 2) faqat tsiklning oxirgi takrorlanishidan keyin to'g'ri bo'ladi (i> 2 ni nazarda tutgan holda).

Jarayonga quyidagi muqaddimani nazarda tutib, biz 4-Fibonachchi raqamini in bilan yakunlaymiz x2:

i n x1 x2 protsedura asosiy n + = 4 i + = n x1 + = 1 x2 + = 1 chaqiriq fib

E'tibor bering, agar biz uni n≤2, ayniqsa manfiy tamsayılar bilan ishlashni amalga oshiradigan bo'lsak, bizning asosiy ishimiz biroz ko'proq ishlashi kerak edi.

Ning teskari tomoni fib bu:

protsedura fib i = 2 dan i + = 1 x1 <=> x2 x1 - = x2 tsikldan i = n gacha

Ko'rib turganingizdek, Yanus lokal inversiyani amalga oshiradi, bu erda tsikl testi va tasdiqlash almashtiriladi, bayonotlar tartibi o'zgartiriladi va tsikldagi har bir bayonotning o'zi teskari bo'ladi. Teskari dastur yordamida x1 (n-1) bo'lganda n ni topish mumkin.^th va x2 - n^th Fibonachchi raqami.

Adabiyotlar