| REFAL | |
|---|---|
| Szemantika | funkcionális / szentenciális |
| Nyelvóra | programozási nyelv és funkcionális programozási nyelv |
| A végrehajtás típusa | megvalósítás függő |
| Megjelent | 1966 |
| Szerző | Valentin Turchin |
| Típusrendszer | gépeletlen |
| Dialektusok | REFAL-2, REFAL-5, REFAL+, REFAL-0 |
| Weboldal | refal.net |
A REFAL ( Recursive Functions Algorithmic ) az egyik legrégebbi funkcionális programozási nyelv , amely a szimbolikus számításokra összpontosít : karakterláncok feldolgozása (például algebrai számítások); fordítás egyik nyelvről (mesterséges vagy természetes) a másikra; mesterséges intelligenciával kapcsolatos problémák megoldása . A matematikai egyszerűséget ötvözi a nagy és összetett programok írásának gyakorlati fókuszával.
A nyelv megkülönböztető jellemzője a mintaillesztés és a kifejezések átírása , mint a funkciók meghatározásának fő módja.
A Refal program egy vagy több modulból (fájlból) állhat, amelyek mindegyike .
A refal függvény mondatok rendezett halmaza, amely egy mintából és egy sablonból áll . Valamilyen kifejezést kap a függvény bemenete ; egy függvény értékelése abból áll, hogy a kifejezést összevetjük az első, második stb. mondatból vett mintákkal. Ha a következő illesztés sikeres, akkor az ugyanabból a mondatból vett sablon alapján egy új Refal kifejezés jön létre, ami a függvény eredménye lesz. Ha a függvény argumentumát nem lehetett összehasonlítani a rendelkezésre álló mintákkal (hiba), akkor hiba kerül rögzítésre (a teljes program összeomlik). Ennek elkerülésére gyakran a függvény végére tesznek egy mondatot, amelynek egy mintájával általánosságban bármilyen kifejezést illeszthetünk. A Refal egyes modern megvalósításaiban (például a Refal+) bármely függvénykifejezés meghibásodása hiba helyett maga a függvény hibáját generálja.
A Refal nyelvi kifejezések kifejezések sorozatai , amelyek lehetnek:
A helyzettől függően korlátozások vonatkozhatnak a kifejezésre; Például a mintákban tilos a szögletes zárójelet tartalmazó kifejezések használata, és a változók nem lehetnek jelen a Refal-gép látómezejében.
A Refal változókat mintákban használják, és típusuktól függően egyetlen karakterhez (vagyis bármely kifejezéshez, kivéve a kapcsos zárójelben lévő kifejezést), egyetlen kifejezéshez (tetszőleges) vagy tetszőleges kifejezéshez (azaz tetszőleges hosszúságú tagok sorozata). A megfelelő típusú változókat S-változóknak, T-változóknak és E-változóknak nevezzük. A Refal-2 dialektus támogatta a V-változókat is, amelyek egy tetszőleges, nem üres kifejezésre lettek leképezve ; a modern nyelvjárások nem támogatják az ilyen változókat.
A Refal nyelv szemantikáját a „refal-gép” vagy „refal-gép” nevű virtuális gép segítségével írják le. A gépnek van egy látómezeje , amely tartalmazhat tetszőleges ref-kifejezést, amely nem tartalmaz ref-változókat.
A program végrehajtása a refal gép lépéseiből áll , amelyek mindegyike egy függvény alkalmazását hajtja végre egy kifejezésre. Ehhez a hivatkozó gép a látómezőjében megkeresi a legbelső aktív kifejezések bal szélső részét; más szóval olyan páros szögzárójeleket találunk, amelyek nem tartalmaznak más szögzárójelet, és ha több ilyen pár van, akkor az kerül kiválasztásra, amelyik a látómezőben szövegesen balra van a többitől. A szögletes zárójelekbe zárt kifejezés első tagjának egy címkekarakternek kell lennie, amely egy függvény neveként szolgál; a kifejezés többi részét a függvény argumentumaként használjuk.
Mint fentebb említettük, a függvényt alkotó mondatok között van az első, amelynek mintája illeszthető a függvény argumentumával; az egyeztetés során a mintában szereplő változókhoz értékeket rendelnek. Ezután az ugyanabból a mondatból vett sablont vesszük alapul a függvényértékelés eredményének kialakításához; leegyszerűsítve, az eredmény egy kifejezés, amelyet a sablonból kapunk úgy, hogy a változókat az értékükre cseréljük. Meg kell jegyezni, hogy egy sablon csak olyan változókat tartalmazhat, amelyek jelen vannak a sablonban; így az eredmény generálásakor a sablonban szereplő összes változót a megfelelő kifejezésekre cseréljük, és az eredmény már nem tartalmaz változókat. Másrészt a sablon szögletes zárójelben tartalmazhat kifejezéseket.
A lépés végén a hivatkozó automata lecseréli a látómezőjében az újonnan számított aktív kifejezést (beleértve a korlátozó szögzárójeleket is) a függvényszámítás során kapott eredménnyel. Megjegyzendő, hogy ebben az esetben az ajánlógép látómezejében lévő szögletes zárójelek száma növekedhet.
A program végrehajtása akkor ér véget, ha a refal gép látómezejében már nincs szögzáró. Az éppen megtekintett kifejezés a refal program végrehajtásának eredményeként lesz deklarálva.
Tekintsük a Refal program futtatásának legegyszerűbb példáját. Legyen megadva a következő függvény:
palindrom { s.1 e.2 s.1 = <Palindrom e.2>; s.1=Igaz; /* üres */ = Igaz; e.1=Hamis; }Ez a függvény elemzi a kifejezést, és eredményeként visszaadja a token karaktert, Trueha a kifejezés palindrom, és Falsenem. A függvény neve Palindrom. Tisztázzuk, hogy s.1 egy S-típusú változó, e.1és e.2 E-típusú változókról van szó. Így a függvénytörzs négy tagmondatból áll, amelyek közül az első akkor működik, ha a függvény argumentuma olyan kifejezés, amely ugyanazzal a karakterrel kezdődik és végződik; a második akkor kerül felhasználásra, ha az argumentum pontosan egy karakterből áll; a harmadik üres érvelésre szolgál, végül a negyedik minden más esetre alkalmas.
Vegye figyelembe, hogy az első mondatban szereplő minta egy aktív kifejezést tartalmaz, amely egy rekurzív függvényhívás Palindrom. Ez azt a tényt tükrözi, hogy ha az első és az utolsó karakter egyezik, akkor eldobhatók, és a kifejezés többi részének palindromicitása ellenőrizhető.
A következő aktív kifejezés jelenjen meg az ajánlógép látómezejében:
<Palindrom 'abcba'>Ezután a végrehajtás három lépésből áll, ami után a következő kifejezések kerülnek a látómezőbe:
<Palindrom 'bcb'> <Palindrom 'c'> IgazAz első két lépés az első mondatot használta, az utolsó lépés a másodikat. Mivel a harmadik lépés után a látómező már nem tartalmaz szögletes zárójeleket, itt fejeződik be a referáló gép munkája.
A REFAL a első változatát 1966 -ban Valentin Turchin készítette metanyelvként más nyelvek szemantikájának leírására. Ezt követően a kellően hatékony megvalósítások számítógépen való megjelenése következtében kezdett gyakorlati alkalmazásra találni, mint programozási nyelv.
Jelenleg a nyelv fő dialektusai a REFAL-2 ( 1970 -es évek ), a REFAL-5 ( 1985 ) és a REFAL+ ( 1990 ), amelyek szintaktikai részletekben és az eredeti verziót bővítő "további eszközök" halmazában különböznek egymástól.
A következő REFAL-5 nyelvjárási program megfordítja és kiírja a bemeneti adatsort:
$ENTRY Menj { = <Prout<Reverse<Card>>>; } fordított { e.Text = <DoReverse() e.Text>; } DoReverse { (e.Scanned) = e.Scanned; (e.Scanned) s.Next e.Tail = <DoReverse (s.Next e.Scanned) e.Tail>; }Ugyanaz a program másképp is írható:
$ENTRY Menj { = <Prout<Reverse<Card>>>; } fordított { /* Ha a karakterlánc nem üres, akkor tördelje az első karaktert a végére */ s.First e.Tail = <Reverse e.Tail> s.First; /* Üres karakterlánc feldolgozása */ /* üres */ = /* üres */; }A következő program a REFAL-5 nyelvjárásban bemenetként kap egy adatsort, amely valamely N természetes szám decimális reprezentációját reprezentálja, majd kiszámítja és kiírja az N számmal rendelkező Fibonacci -számot:
$ENTRY Menj { = <Prout<Symb<FN<Numb<Card>>>>; } FN { /* Hívjon egy segédfüggvényt, amely megvalósítja a maradék-rekurzív hurkot. */ s.Szám = <DoFN s.Number 0 1>; } /* A függvény egy maradék-rekurzív hurkot valósít meg. Hurok invariáns <DoFN s.Counter s.Current s.Next> s.Counter -- a fennmaradó iterációk száma. s.Current -- az aktuális iterációnak megfelelő Fibonacci-szám. s.Next -- a Fibonacci-szám értéke a következő iterációhoz. */ DoFN { 0 s.Current s.Next = s.Current; s.Számláló s.Aktuális s.Következő = <DoFN <Sub s.Counter 1> s.Next <Add s.Current s.Next>>; }
| Programozási nyelvek | |
|---|---|
| |