REFAL

REFAL
Semantiikka toiminnallinen / sentiaalinen
Kieliluokka ohjelmointikieli ja toiminnallinen ohjelmointikieli
Toteutustyyppi täytäntöönpanosta riippuvainen
Esiintyi 1966
Tekijä Valentin Turchin
Tyyppijärjestelmä kirjoittamaton
Murteet REFAL-2, REFAL-5, REFAL+, REFAL-0
Verkkosivusto refal.net

REFAL ( Recursive Functions Algorithmic ) on yksi vanhimmista toiminnallisista ohjelmointikielistä , joka keskittyy symbolisiin laskelmiin : merkkijonojen käsittely (esim. algebralliset laskutoimitukset); käännös kielestä (keinotekoinen tai luonnollinen) toiselle; tekoälyyn liittyvien ongelmien ratkaiseminen . Yhdistää matemaattisen yksinkertaisuuden käytännön keskittymiseen suurten ja monimutkaisten ohjelmien kirjoittamiseen.

Kielen erottuva piirre on kuvioiden sovituksen ja termien uudelleenkirjoituksen käyttö pääasiallisena funktioiden määrittelytavana.

Perusperiaatteet

Refal-ohjelma voi koostua yhdestä tai useammasta moduulista (tiedostosta), joista jokainen puolestaan ​​koostuu .

Refal - funktio on järjestetty lausejoukko , joka koostuu kuviosta ja mallista . Jokin lauseke annetaan funktion syötteelle ; funktion arviointi koostuu lausekkeen vertaamisesta vuorotellen ensimmäisestä, toisesta jne. lauseesta otettuihin näytteisiin. Jos seuraava sovitus onnistuu, niin samasta lauseesta otetun mallin perusteella muodostetaan uusi Refal-lauseke, joka on funktion tulos. Jos funktion argumenttia ei voitu verrata mihinkään käytettävissä olevista näytteistä (virhe), tallennetaan virhe (koko ohjelma kaatuu). Tämän välttämiseksi funktion loppuun sijoitetaan usein lause, jonka näytteellä voit kohdistaa mitä tahansa lauseketta yleisesti. Joissakin Refalin nykyaikaisissa toteutuksissa (esimerkiksi Refal+) minkä tahansa funktiolausekkeen epäonnistuminen virheen sijaan aiheuttaa itse funktion epäonnistumisen.

Refal-kielen lausekkeet ovat termisarjoja , jotka voivat olla:

Tilanteesta riippuen ilmaisulle voidaan asettaa rajoituksia; esim. näytteissä on kiellettyä käyttää kulmasulkeja sisältäviä lausekkeita, eikä muuttujia voi olla Refal-koneen näkökentässä .

Refal-muuttujia käytetään kuvioissa, ja niiden tyypistä riippuen ne voidaan sovittaa yhteen merkkiin (eli mihin tahansa termiin, paitsi aaltosulkeissa olevaan lausekkeeseen), yksittäiseen termiin (mielivaltainen) tai mielivaltaiseen lausekkeeseen (eli mielivaltaisen pituisten termien sarja). Vastaavia muuttujatyyppejä kutsutaan S-muuttujiksi, T-muuttujiksi ja E-muuttujiksi. Refal-2-murre tuki myös V-muuttujia, jotka kartoitettiin mielivaltaiseen ei- tyhjään lausekkeeseen; nykyiset murteet eivät tue tällaisia ​​muuttujia.

Refal-kielen semantiikkaa kuvataan virtuaalikoneella nimeltä "refal-machine" tai "refal-machine". Koneessa on näkökenttä , joka voi sisältää mielivaltaisen ref-lausekkeen, joka ei sisällä ref-muuttujia.

Ohjelman suoritus koostuu refal-koneen vaiheista , joista jokainen suorittaa funktion soveltamisen lausekkeeseen. Tätä varten viittauskone etsii näkökentästään vasemmanpuoleisimpia sisimpiä aktiivisia lausekkeita. toisin sanoen löydetään parillisia kulmasulkuja, jotka eivät sisällä muita kulmasulkuja, ja jos tällaisia ​​pareja on useita, valitaan se, joka on tekstillisesti muiden näkökentässä vasemmalla. Kulmasulkeissa olevan lausekkeen ensimmäisen termin on oltava tunnistemerkki, joka toimii funktion nimenä; loppuosaa lausekkeesta käytetään funktion argumenttina.

Kuten edellä mainittiin, funktion muodostavien lauseiden joukossa on ensimmäinen lause, jonka kuvio voidaan sovittaa funktion argumentin kanssa; sovituksen aikana kuvion sisältämille muuttujille annetaan arvot. Sitten samasta lauseesta otettu malli otetaan pohjaksi funktion arvioinnin tuloksen muodostamiselle; yksinkertaisesti sanottuna tulos on lauseke, joka saadaan mallista korvaamalla muuttujat niiden arvoilla. On huomattava, että malli voi sisältää vain muuttujia, jotka ovat mallissa; näin ollen kaikki malliin sisältyvät muuttujat korvataan vastaavilla lausekkeilla tulosta luotaessa, eikä tulos enää sisällä muuttujia. Toisaalta malli voi hyvinkin sisältää lausekkeita kulmasuluissa.

Vaiheen lopussa viittausautomaatti korvaa näkökentässään juuri lasketun aktiivisen lausekkeen (mukaan lukien sen rajoittavat kulmasulut) funktiolaskennan aikana saadulla tuloksella. On huomioitava, että kulmasulkujen määrä lähetyskoneen näkökentässä voi tässä tapauksessa kasvaa.

Ohjelman suoritus päättyy, kun refal-koneen näkökentässä ei ole enää kulmasulkuja. Tällä hetkellä näkyvissä oleva lauseke ilmoitetaan refal-ohjelman suorittamisen tuloksena .

Toteutusesimerkki

Harkitse yksinkertaisinta esimerkkiä ohjelman suorittamisesta Refalissa. Olkoon seuraava funktio:

palindromi { s.1 e.2 s.1 = <Palindrom e.2>; s.1=Tosi; /* tyhjä */ = Tosi; e.1=Epätosi; }

Tämä funktio jäsentää lausekkeen ja palauttaa sen tuloksena merkkimerkin, Truejos lauseke on palindromi tai Falsemuuten. Funktiolla on nimi Palindrom. Selvitetään, että s.1 se on S-tyypin muuttuja e.1ja e.2 ovat E-tyypin muuttujia. Siten funktion runko koostuu neljästä lauseesta, joista ensimmäinen toimii, jos funktion argumentti on lauseke, joka alkaa ja päättyy samaan merkkiin; toista käytetään, jos argumentti koostuu täsmälleen yhdestä merkistä; kolmatta käytetään tyhjään argumenttiin, ja lopuksi neljäs sopii kaikkiin muihin tapauksiin.

Huomaa, että ensimmäisen lauseen kuvio sisältää aktiivisen lausekkeen, joka on rekursiivinen funktiokutsu Palindrom. Tämä kuvastaa sitä tosiasiaa, että jos ensimmäinen ja viimeinen merkki täsmäävät, ne voidaan hylätä ja loput lausekkeesta tarkistaa palindromiteetin varalta.

Anna seuraavan aktiivisen lausekkeen näkyä viittauskoneen näkökentässä:

<Palindrom 'abcba'>

Sitten suoritus koostuu kolmesta vaiheesta, jonka jälkeen seuraavat lausekkeet ovat näkökentässä:

<Palindrom 'bcb'> <Palindrom 'c'> Totta

Kahdessa ensimmäisessä vaiheessa käytettiin ensimmäistä lausetta, viimeisessä vaiheessa toista. Koska kolmannen vaiheen jälkeen näkökentässä ei enää ole kulmasulkuja, ohjekoneen työ valmistuu tähän.

Historia

REFAL a :n ensimmäisen version loi Valentin Turchin vuonna 1966 metakieleksi muiden kielten semantiikan kuvaamiseen. Myöhemmin, kun riittävän tehokkaita toteutuksia ilmestyi tietokoneeseen, se alkoi löytää käytännön käyttöä ohjelmointikielenä.

Tällä hetkellä kielen päämurteet ovat REFAL-2 ( 1970 ), REFAL-5 ( 1985 ) ja REFAL+ ( 1990 ), jotka eroavat toisistaan ​​syntaksiyksityiskohtien ja joukon "lisätyökaluja", jotka laajentavat alkuperäistä versiota.

Ohjelmaesimerkkejä

Seuraava REFAL-5 murreohjelma kääntää ja tulostaa syötetyn tietojonon:

$ENTRY Mene { = <Prout<Käänteinen<kortti>>>; } käänteinen { e.Teksti = <DoReverse() e.Teksti>; } DoReverse { (e.Skannattu) = e.Skannattu; (e.Scanned) s.Next e.Tail = <DoReverse (s.Next e.Scanned) e.Tail>; }

Sama ohjelma voidaan kirjoittaa eri tavalla:

$ENTRY Mene { = <Prout<Käänteinen<kortti>>>; } käänteinen { /* Jos merkkijono ei ole tyhjä, rivitä ensimmäinen merkki loppuun */ s.First e.Tail = <Reverse e.Tail> s.First; /* Käsittele tyhjä merkkijono */ /* tyhjä */ = /* tyhjä */; }

Seuraava REFAL-5-murteen ohjelma vastaanottaa syötteenä tietojonon, joka edustaa jonkin luonnollisen luvun N desimaaliesitystä, minkä jälkeen se laskee ja tulostaa Fibonacci -luvun numerolla N:

$ENTRY Mene { = <Prout<Symb<FN<Num<Kortti>>>>; } FN { /* Kutsu apufunktiota, joka toteuttaa jäännösrekursiivisen silmukan. */ s.Number = <DoFN s.Number 0 1>; } /* Funktio toteuttaa jäännösrekursiivisen silmukan. Loop Invariant <DoFN s.Counter s.Current s.Next> s.Laskuri -- jäljellä olevien iteraatioiden määrä. s. Current -- Fibonacci-luku, joka vastaa nykyistä iteraatiota. s.Next -- Fibonacci-luvun arvo seuraavalle iteraatiolle. */ DoFN { 0 s.Nykyinen s.Seuraava = s.Virta; s.Laskuri s.Nykyinen s.Seuraava = <DoFN <Sub s.Counter 1> s.Next <Lisää s.Current s.Next>>; }

Muistiinpanot

Kirjallisuus

Linkit


 Ohjelmointikielet