| REFAL | |
|---|---|
| Semantik | funktionel / sentential |
| Sprog klasse | programmeringssprog og funktionelt programmeringssprog |
| Udførelsestype | implementeringsafhængig |
| Dukkede op i | 1966 |
| Forfatter | Valentin Turchin |
| Type system | uskrevet |
| Dialekter | REFAL-2, REFAL-5, REFAL+, REFAL-0 |
| Internet side | refal.net |
REFAL ( Recursive Functions Algorithmic ) er et af de ældste funktionelle programmeringssprog , fokuseret på symbolske beregninger : behandling af tegnstrenge (f.eks. algebraiske beregninger); oversættelse fra et sprog (kunstigt eller naturligt) til et andet; løse problemer relateret til kunstig intelligens . Kombinerer matematisk enkelhed med praktisk fokus på at skrive store og komplekse programmer.
Et karakteristisk træk ved sproget er brugen af mønstermatching og termomskrivning som den vigtigste måde at definere funktioner på.
Et Refal-program kan bestå af et eller flere moduler (filer), som hver på sin side består af .
En refalfunktion er et ordnet sæt sætninger bestående af et mønster og en skabelon . Nogle udtryk er givet til input af funktionen ; evalueringen af en funktion består i at sammenligne udtrykket på skift med stikprøverne fra den første, anden osv. sætning. Hvis den næste matchning lykkes, dannes et nyt Refal-udtryk baseret på skabelonen taget fra samme sætning, som vil være resultatet af funktionen. Hvis det ikke var muligt at sammenligne funktionsargumentet med nogen af de tilgængelige eksempler (fejl), registreres en fejl (hele programmet går ned). For at undgå dette placeres en sætning ofte i slutningen af funktionen, med en prøve, som du kan matche ethvert udtryk generelt. I nogle moderne implementeringer af Refal (f.eks. Refal+) genererer fejl i et funktionsudtryk i stedet for en fejl fejl i selve funktionen.
Refal- sprogudtryk er sekvenser af termer , som kan være:
Afhængig af situationen kan der lægges begrænsninger på udtrykket; for eksempel er det i samples forbudt at bruge udtryk, der indeholder vinkelparenteser, og variabler kan ikke være til stede i synsfeltet på Refal-machine.
Refal-variabler bruges i mønstre og kan, afhængigt af deres type, matches til et enkelt tegn (det vil sige ethvert led, undtagen et udtryk i klammer), et enkelt led (vilkårligt) eller et vilkårligt udtryk (dvs. en sekvens af led af vilkårlig længde). De tilsvarende typer af variabler kaldes S-variable, T-variable og E-variable. Refal-2 dialekten understøttede også V-variabler, som blev afbildet til et vilkårligt ikke- tomt udtryk; moderne dialekter understøtter ikke sådanne variabler.
Semantikken i Refal-sproget er beskrevet i form af en virtuel maskine kaldet "refal-machine" eller "refal-machine". Maskinen har et synsfelt , som kan indeholde et vilkårligt ref-udtryk, der ikke indeholder ref-variable.
Udførelsen af programmet består af trinene i refal-maskinen, som hver udfører anvendelsen af en funktion til et udtryk. For at gøre dette søger henvisningsmaskinen i sit synsfelt efter det længst til venstre af de inderste aktive udtryk; der findes med andre ord parrede vinkelparenteser, som ikke indeholder andre vinkelparenteser, og hvis der er flere sådanne par, vælges det, der tekstmæssigt står til venstre for de andre i synsfeltet. Det første led i et udtryk omgivet af vinkelparenteser skal være et etikettegn, der tjener som navn på en funktion; resten af udtrykket bruges som funktionsargument.
Som nævnt ovenfor er der blandt de sætninger, der udgør en funktion, den første, hvis mønster kan matches med funktionsargumentet; under matchning tildeles værdier til variablerne indeholdt i mønsteret. Derefter tages skabelonen fra samme sætning som grundlag for at danne resultatet af funktionsevalueringen; Forenklet sagt er resultatet et udtryk opnået fra skabelonen ved at erstatte variablerne med deres værdier. Det skal bemærkes, at en skabelon kun kan indeholde variabler, der er til stede i skabelonen; således vil alle variabler inkluderet i skabelonen blive erstattet af de tilsvarende udtryk ved generering af resultatet, og resultatet vil ikke længere indeholde variable. På den anden side kan skabelonen godt indeholde udtryk i vinkelparenteser.
I slutningen af trinnet erstatter henvisningsautomaten i sit synsfelt det nyligt beregnede aktive udtryk (inklusive dets begrænsende vinkelparenteser) med resultatet opnået under funktionsberegningen. Det skal bemærkes, at antallet af vinkelbeslag i referencemaskinens synsfelt kan stige i dette tilfælde.
Udførslen af programmet afsluttes, når der ikke er flere vinkelbeslag i synsfeltet på refalmaskinen. Det udtryk, der aktuelt er i udsigt, erklæres som et resultat af eksekvering af refal-programmet.
Overvej det enkleste eksempel på at køre et program i Refal. Lad følgende funktion gives:
palindrom { s.1 e.2 s.1 = <Palindrom e.2>; s.1=Sandt; /* tomme */ = Sand; e.1=Falsk; }Denne funktion analyserer et udtryk og returnerer token-tegnet som et resultat True, hvis udtrykket er et palindrom og Falseandet. Funktionen har navnet Palindrom. Lad os præcisere, at det s.1 er en S-type variabel e.1og e.2 er E-type variabler. Funktionslegemet består således af fire klausuler, hvoraf den første vil fungere, hvis funktionsargumentet er et udtryk, der starter og slutter med det samme tegn; det andet vil blive brugt, hvis argumentet består af præcis ét tegn; det tredje bruges til et tomt argument, og endelig er det fjerde egnet til alle andre tilfælde.
Bemærk, at mønsteret i den første sætning indeholder et aktivt udtryk, som er et rekursivt funktionskald Palindrom. Dette afspejler det faktum, at hvis de første og sidste tegn matcher, kan de kasseres, og resten af udtrykket kontrolleres for palindromicitet.
Lad følgende aktive udtryk vises i referencemaskinens synsfelt:
<Palindrom 'abcba'>Derefter vil udførelsen bestå af tre trin, hvorefter følgende udtryk vil være i synsfeltet:
<Palindrom 'bcb'> <Palindrom 'c'> RigtigtDe første to trin brugte den første sætning, det sidste trin det andet. Da synsfeltet efter det tredje trin ikke længere indeholder vinkelbeslag, afsluttes referencemaskinens arbejde her.
Den første version af REFAL a blev skabt i 1966 af Valentin Turchin som et metasprog til at beskrive andre sprogs semantik. Efterfølgende, som et resultat af fremkomsten af tilstrækkeligt effektive implementeringer på en computer, begyndte det at finde praktisk brug som et programmeringssprog.
I øjeblikket er sprogets hoveddialekter REFAL-2 ( 1970'erne ), REFAL-5 ( 1985 ) og REFAL+ ( 1990 ), som adskiller sig fra hinanden i syntaksdetaljer og et sæt "yderligere værktøjer", der udvider den originale version.
Følgende REFAL-5 dialektprogram vender og udskriver inputdatastrengen:
$ENTRY Gå { = <Prout<Omvendt<Kort>>>; } baglæns { e.Text = <DoReverse() e.Text>; } DoReverse { (e.Scanned) = e.Scanned; (e.Scanned) s.Next e.Tail = <DoReverse (s.Next e.Scanned) e.Tail>; }Det samme program kan skrives forskelligt:
$ENTRY Gå { = <Prout<Omvendt<Kort>>>; } baglæns { /* Hvis strengen ikke er tom, skal du ombryde det første tegn til slutningen */ s.First e.Tail = <Omvendt e.Tail> s.First; /* Behandle tom streng */ /* tom */ = /* tom */; }Følgende program i REFAL-5 dialekten modtager som input en datastreng, der repræsenterer decimalrepræsentationen af et naturligt tal N, hvorefter det beregner og udskriver Fibonacci - tallet med tallet N:
$ENTRY Gå { = <Prout<Symb<FN<Numb<Card>>>>; } FN { /* Kald en hjælpefunktion, der implementerer den resterende-rekursive sløjfe. */ s.Number = <DoFN s.Number 0 1>; } /* Funktionen implementerer en residual-rekursiv løkke. Loop Invariant <DoFN s.Counter s.Current s.Next> s. Tæller -- antal resterende iterationer. s.Current -- Fibonacci-nummer svarende til den aktuelle iteration. s.Next -- værdien af Fibonacci-tallet for den næste iteration. */ DoFN { 0 s.Current s.Next = s.Current; s.Tæller s.Nuværende s.Næste = <DoFN <Sub s.Counter 1> s.Next <Add s.Current s.Next>>; }
| Programmeringssprog | |
|---|---|
| |