REVAL

REVAL
Semantik funktionell / sentential
Språkklass programmeringsspråk och funktionellt programmeringsspråk
Utförandetyp implementeringsberoende
Framträdde i 1966
Författare Valentin Turchin
Typ system oskrivet
Dialekter REFAL-2, REFAL-5, REFAL+, REFAL-0
Hemsida refal.net

REFAL ( Recursive Functions Algorithmic ) är ett av de äldsta funktionella programmeringsspråken , fokuserat på symboliska beräkningar : bearbetning av teckensträngar (till exempel algebraiska beräkningar); översättning från ett språk (konstgjort eller naturligt) till ett annat; lösa problem relaterade till artificiell intelligens . Kombinerar matematisk enkelhet med ett praktiskt fokus på att skriva stora och komplexa program.

Ett utmärkande drag för språket är användningen av mönstermatchning och termomskrivning som det huvudsakliga sättet att definiera funktioner.

Grundläggande principer

Ett Refal-program kan bestå av en eller flera moduler (filer), som var och en i sin tur består av .

En refalfunktion är en ordnad uppsättning meningar som består av ett mönster och en mall . Ett uttryck ges till ingången av funktionen ; utvärderingen av en funktion består i att jämföra uttrycket i tur och ordning med de stickprov som tagits från den första, andra, etc. meningarna. Om nästa matchning lyckas, baserat på mallen hämtad från samma mening, bildas ett nytt Refal-uttryck, som blir resultatet av funktionen. Om det inte gick att jämföra funktionsargumentet med något av de tillgängliga exemplen (fel) registreras ett fel (hela programmet kraschar). För att undvika detta placeras ofta en mening i slutet av funktionen, med ett exempel på vilket du kan matcha vilket uttryck som helst i allmänhet. I vissa moderna implementeringar av Refal (till exempel Refal+) genererar felet i ett funktionsuttryck istället för ett fel felet i själva funktionen.

Refal- språkuttryck är sekvenser av termer som kan vara:

Beroende på situationen kan begränsningar läggas på uttrycket; i exempel är det förbjudet att använda uttryck som innehåller vinkelparenteser, och variabler kan inte finnas i synfältet för Refal-machine.

Refalvariabler används i mönster och kan, beroende på deras typ, matchas till ett enda tecken (det vill säga vilken term som helst, förutom ett uttryck inom klammerparenteser), en enstaka term (godtyckligt) eller ett godtyckligt uttryck (det vill säga, en sekvens av termer av godtycklig längd). Motsvarande typer av variabler kallas S-variabler, T-variabler och E-variabler. Refal-2-dialekten stödde också V-variabler, som mappades till ett godtyckligt icke- tomt uttryck; moderna dialekter stöder inte sådana variabler.

Semantiken för Refal-språket beskrivs i termer av en virtuell maskin som kallas "refal-machine" eller "refal-machine". Maskinen har ett synfält som kan innehålla ett godtyckligt ref-uttryck som inte innehåller ref-variabler.

Exekveringen av programmet består av stegen i refalmaskinen, som var och en utför appliceringen av en funktion på ett uttryck. För att göra detta söker hänvisningsmaskinen i sitt synfält efter det längst till vänster av de innersta aktiva uttrycken; med andra ord hittas parade vinkelparenteser som inte innehåller andra vinkelparenteser, och om det finns flera sådana par väljs den som textmässigt ligger till vänster om de andra i synfältet. Den första termen i ett uttryck inom vinkelparenteser måste vara ett etiketttecken som fungerar som namn på en funktion; resten av uttrycket används som funktionsargument.

Som nämnts ovan, bland meningarna som utgör en funktion, finns det den första vars mönster kan matchas med funktionsargumentet; under matchning tilldelas värden till variablerna som finns i mönstret. Därefter tas mallen hämtad från samma mening som grund för att bilda resultatet av funktionsutvärderingen; Enkelt uttryckt är resultatet ett uttryck som erhålls från mallen genom att ersätta variablerna med deras värden. Det bör noteras att en mall endast kan innehålla variabler som finns i mallen; alltså kommer alla variabler som ingår i mallen att ersättas av motsvarande uttryck när resultatet genereras, och resultatet kommer inte längre att innehålla variabler. Å andra sidan kan mallen mycket väl innehålla uttryck inom vinkelparenteser.

I slutet av steget ersätter remissautomaten i sitt synfält det nyberäknade aktiva uttrycket (inklusive dess begränsningsvinkelparenteser) med resultatet som erhålls under funktionsberäkningen. Det bör noteras att antalet vinkelfästen i remissmaskinens synfält kan öka i detta fall.

Körningen av programmet avslutas när det inte finns fler vinkelparenteser i synfältet för refalmaskinen. Uttrycket som för närvarande visas deklareras som ett resultat av exekvering av återvalsprogrammet.

Exekveringsexempel

Tänk på det enklaste exemplet på att köra ett program i Refal. Låt följande funktion ges:

palindrom { s.1 e.2 s.1 = <Palindrom e.2>; s.1=Sant; /* tomt */ = Sant; e.1=False; }

Den här funktionen analyserar ett uttryck och returnerar tokentecken som ett resultat Trueom uttrycket är ett palindrom och Falseannat. Funktionen har namnet Palindrom. Låt oss förtydliga att det s.1 är en variabel av S-typ e.1och att det e.2 är variabler av E-typ. Funktionskroppen består alltså av fyra satser, varav den första fungerar om funktionsargumentet är ett uttryck som börjar och slutar med samma tecken; den andra kommer att användas om argumentet består av exakt ett tecken; den tredje används för ett tomt argument, och slutligen är det fjärde lämpligt för alla andra fall.

Observera att mönstret i den första meningen innehåller ett aktivt uttryck, som är ett rekursivt funktionsanrop Palindrom. Detta återspeglar det faktum att om de första och sista tecknen matchar, kan de kasseras och resten av uttrycket kontrolleras för palindromicitet.

Låt följande aktiva uttryck visas i synfältet för hänvisningsmaskinen:

<Palindrom 'abcba'>

Sedan kommer exekveringen att bestå av tre steg, varefter följande uttryck kommer att finnas i synfältet:

<Palindrom 'bcb'> <Palindrom 'c'> Sann

De två första stegen använde den första meningen, det sista steget det andra. Eftersom synfältet efter det tredje steget inte längre innehåller vinkelfästen, är remissmaskinens arbete avslutat här.

Historik

Den första versionen av REFAL a skapades 1966 av Valentin Turchin som ett metaspråk för att beskriva semantiken i andra språk. Därefter, som ett resultat av uppkomsten av tillräckligt effektiva implementeringar på en dator, började det hitta praktisk användning som ett programmeringsspråk.

För närvarande är språkets huvuddialekter REFAL-2 ( 1970 -talet ), REFAL-5 ( 1985 ) och REFAL+ ( 1990 ), som skiljer sig från varandra i syntaxdetaljer och en uppsättning "ytterligare verktyg" som utökar originalversionen.

Programexempel

Följande dialektprogram REFAL-5 vänder och skriver ut indatasträngen:

$ENTRY Gå { = <Prout<Omvänd<Kort>>>; } omvänd { e.Text = <DoReverse() e.Text>; } Gör omvänd { (e.Scanned) = e.Scanned; (e.Scanned) s.Next e.Tail = <DoReverse (s.Next e.Scanned) e.Tail>; }

Samma program kan skrivas på olika sätt:

$ENTRY Gå { = <Prout<Omvänd<Kort>>>; } omvänd { /* Om strängen inte är tom, linda det första tecknet till slutet */ s.First e.Tail = <Omvänd e.Tail> s.First; /* Bearbeta tom sträng */ /* tom */ = /* tom */; }

Följande program på REFAL-5-dialekten får som indata en datasträng som representerar decimalrepresentationen av något naturligt tal N, varefter det beräknar och skriver ut Fibonacci- talet med talet N:

$ENTRY Gå { = <Prout<Symb<FN<Numb<Card>>>>; } FN { /* Anropa en hjälpfunktion som implementerar den restrekursiva slingan. */ s.Number = <DoFN s.Number 0 1>; } /* Funktionen implementerar en residual-rekursiv loop. Loop Invariant <DoFN s.Counter s.Current s.Next> s.Räknare -- antal återstående iterationer. s.Current -- Fibonacci-nummer som motsvarar den aktuella iterationen. s.Next -- värdet på Fibonacci-talet för nästa iteration. */ DoFN { 0 s.Current s.Next = s.Current; s.Counter s.Current s.Next = <DoFN <Sub s.Counter 1> s.Next <Lägg till s.Current s.Next>>; }

Anteckningar

Litteratur

Länkar


 Programmeringsspråk